11.3 Recursive Functions

We now add support for recursive functions—that is, functions that can make a call to themselves in their body.

11.3.1 Adding Support for Recursion in Camille

To support recursion in Camille, we add the following rules to the grammar and corresponding pattern-action rules to the PLY parser generator:

Example expressions in this version of Camille follow:

11.3.2 Recursive Environment

To support recursion, we must modify the environment. Specifically, we must ensure that the environment stored in the closure of a recursive function contains the function itself. To do so, we add a new function extend_environment_recursively to the environment interface. Three possible representations of a recursive environment are a closure, abstract syntax, and a list-of-lists.

Closure Representation of Recursive Environment

The closure representation of a recursive environment is the same as the closure representation of a non-recursive environment except for the following definition of the extend_environment_recursively function:

The recursive environment is initially created as a Python closure or lambda expression (line 3). As usual with a closure representation of an environment, that Python closure is invoked when apply_environment is called. At that time, the closure for the recursive function is created (lines 7–8), and contains the recursive environment (line 8) originally created (line 3). Thus, the environment containing the recursive function is found in the closure representing the recursive function.

The relationship between the and functions is specified as follows:

1. If name is one of the names in fun_names, and parameters and body are the corresponding formal parameter list and function body in parameterlists and bodies, respectively, then

   

   where e’ is

   

2. Else,

   

Abstract-Syntax Representation of Recursive Environment

To create an abstract-syntax representation of a recursive environment, we augment the abstract-syntax representation of a non-recursive environment with a new set of fields for a recursively-extended-environment-record:

We must also add a new function extend_environment_recursively to the interface and augment the definition apply_environment in the implementation to handle the new recursively-extended-environment-record (lines 30–36):

The circular structure of the abstract-syntax representation of a recursive environment is presented in Figure 11.7. In this figure, <<if zero?(x) then 1 else (odd dec1(x))>> represents the abstract-syntax representation of a Camille expression (i.e., TreeNode). In general, in this chapter, << x >> represents the abstract-syntax representation of x. Notice that the environment contained in the closure of each recursive function is the environment containing the closure, not the environment in which the closure is created.

List-of-Lists Representation of Recursive Environment

In the closure and abstract-syntax representations of a recursive environment just described, a new closure is built each time a function is retrieved from the environment (i.e., when apply_environment is called). This is unnecessary (and inefficient) since the environment for the closure being repeatedly built is always the same. If we use a list-of-lists (i.e., ribcage) representation of a recursive environment, we can build each closure only once, in the extend_environment_recursively function, when the recursive function is encountered:

Everything else from the list-of-lists representation of a non-recursive environment remains the same in the list-of-lists representation of a recursive environment. The circular structure of the list-of-lists representation of a recursive environment is shown in Figure 11.8.

11.3.3 Augmenting evaluate_expr with New Variants

The final modification we must make to support recursive functions is an augmentation of the evaluate_expr function to process the new variants of TreeNode that we added to support recursion—that is, ntLetRec, ntLetRecStatement, ntLetRecAssignment, and ntRecFuncDecl.

We start by discussing how the bindings in a letrec expression are represented in the abstract-syntax tree. Subtrees of the ntLetrecStatement variant are traversed in the same way as the ntLetStatement and ntLetStarStatement variants. However, the semantics of these expressions differ in how values are added to the environment. Specifically, ntLetRecAssignment returns a list containing three lists: a list of identifiers to which each function is bound, the parameter lists of each function, and the body of each function.

The following augmented definition of evaluate_expr describes how a letrec expression is evaluated:

Conceptual Exercises for Section 11.3

Exercise 11.3.1 Even though the make-closure function is called in the definition of the extend-environment-recursively for the closure representation of a recursive environment, the closure is still created every time the name of the recursive function is looked up in the environment. Explain.

Exercise 11.3.2 Can a let* expression evaluated using dynamic scoping achieve the same result (i.e., recursion) as a letrec expression evaluated using lexical scoping? In other words, does a let* expression evaluated using dynamic scoping simulate a letrec expression? Explain.

Programming Exercises for Section 11.3

Table 11.2 summarizes the properties of the new versions of the Camille interpreter developed in the following programming exercises. Figure 11.9 presents the dependencies between the non-recursive and recursive versions of Camille developed thus far, including in these programming exercises.

Table 11.2 New Versions of Camille, and Their Essential Properties, Created in the Section 11.3.3 Programming Exercises. (Key: ASR = abstract-syntax representation; CLS = closure; LOLR = list-of-lists representation.)

Exercise 11.3.3 Build an abstract-syntax representation of a nameless, recursive environment (Figure 11.10). Complete Programming Exercise 9.8.9, but this time make the abstract-syntax representation of the nameless environment recursive.

Exercise 11.3.4 (Friedman, Wand, and Haynes 2001, Exercise 3.34, p. 95) Build a list-of-lists representation of a nameless, recursive environment (Figure 11.11). Complete Programming Exercise 9.8.5.b or 11.2.9.b, but this time make the list-oflists representation of the nameless environment recursive.

Exercise 11.3.5 Build a closure representation of a nameless, recursive environment. Complete Programming Exercise 9.8.7, but this time make the closure representation of the nameless environment recursive.

Exercise 11.3.6 (Friedman, Wand, and Haynes 2001) Augment the solution to Programming Exercise 11.2.10 with letrec. In other words, extend Camille 2.0(nameless ASR) with letrec. Alternatively, modify Camille 2.1(named ASR) to use a nameless environment. Reuse the abstract-syntax representation of a recursive, nameless environment built in Programming Exercise 11.3.3.

Exercise 11.3.7 (Friedman, Wand, and Haynes 2001, Exercise 3.34, p. 95) Augment the solution to Programming Exercise 11.2.9 with letrec. In other words, extend Camille 2.0(nameless LOLR) with letrec. Alternatively, modify Camille 2.1(named LOLR) to use a nameless environment. Reuse the list-of-lists representation of a recursive, nameless environment built in Programming Exercise 11.3.4.

Exercise 11.3.8 (Friedman, Wand, and Haynes 2001) Augment the solution to Programming Exercise 11.2.11 with letrec. In other words, extend Camille 2.0(nameless CLS) with letrec. Alternatively, modify Camille 2.1(named CLS) to use a nameless environment. Reuse the closure representation of a recursive, nameless environment built in Programming Exercise 11.3.5.

Exercise 11.3.9 Modify the Camille interpreter defined in this section to use dynamic scoping to bind references to declarations. For instance, in the recursive Camille function pow shown here the reference to the identifier s in the expression *(s, (pow -(t,1))) in line 5 is bound to 3, not 2; thus, the return value of the call to (pow 2) on line 10 is 9 (under dynamic scoping), not 4 (under static/lexical scoping).

Example: