Tutorial

The tutorial provides an introduction to writing programs. It builds on the contents of the user manual, particularly the sections “Programming Language” and “Listener Buffers”.

Building Blocks

This section introduces the global functions and macros that will be used in the tutorial. Some global functions and macros are included for the sake of completeness and will not actually be used in the tutorial.

It is customary for a function or macro that tests a condition and returns a boolean to have a name ending with a question mark. This rule has some notable exceptions, though.

Data Type boolean

(not $\boolean$) ⇒ $\boolean$

The function returns #t if $\boolean$ is #f and #f if $\boolean$ is #t.

> (not #t)
#f

> (not #f)
#t

In the following two template macro calls, $\metavar{test-forms}$ matches any sequence of zero or more objects.

(and $\metavar{test-forms}$)

The macro returns #t if all its arguments are #t and #f otherwise. The exact behavior of the macro is as follows: The test forms are evaluated in sequence from left to right. If a test form evaluates to an object that is not a boolean, then the following test forms are not evaluated and the evaluation of the macro call completes abruptly for a reason of type error. If a test form evaluates to #f, then the following test forms are not evaluated and the macro call evaluates to #f. If all test forms evaluate to #t, then the macro call evaluates to #t. Note that the previous condition is automatically satisfied if there are no test forms.

> (and)
#t

> (and #t)
#t

> (and #f)
#f

> (and #t #t)
#t

> (and #t #f)
#f

> (and #f #t)
#f

> (and #f #f)
#f

(or $\metavar{test-forms}$)

The macro returns #f if all its arguments are #f and #t otherwise. The exact behavior of the macro is as follows: The test forms are evaluated in sequence from left to right. If a test form evaluates to an object that is not a boolean, then the following test forms are not evaluated and the evaluation of the macro call completes abruptly for a reason of type error. If a test form evaluates to #t, then the following test forms are not evaluated and the macro call evaluates to #t. If all test forms evaluate to #f, then the macro call evaluates to #f. Note that the previous condition is automatically satisfied if there are no test forms.

> (or)
#f

> (or #t)
#t

> (or #f)
#f

> (or #t #t)
#t

> (or #t #f)
#t

> (or #f #t)
#t

> (or #f #f)
#f

The macros and and or stop evaluating the test forms as soon as they can determine that the result of the macro call is definitively true or definitively false. This short-circuiting behavior is possible only because and and or are macros. When a function call is evaluated, all the operand forms are always evaluated (unless the evaluation of the operator form completes abruptly or does not complete, the primary value of the operator form is not a function, or the evaluation of one of the operand forms other than the last one completes abruptly or does not complete).

Here are two expansions illustrating the implementations of the macros and and or:

• (and $\metavar{test-form}_1$ $\metavar{test-form}_2$ $\metavar{test-form}_3$) expands into
  (if $\metavar{test-form}_1$ (if $\metavar{test-form}_2$ (if $\metavar{test-form}_3$ #t #f) #f) #f)
• (or $\metavar{test-form}_1$ $\metavar{test-form}_2$ $\metavar{test-form}_3$) expands into
  (if $\metavar{test-form}_1$ #t (if $\metavar{test-form}_2$ #t (if $\metavar{test-form}_3$ #t #f)))

The name of the function not and the names of the macros and and or do not end with a question mark because the function and the macros do not really test a condition. Instead, they combine booleans (they are boolean operators).

Data Type number

Arithmetic Operators

(+ $\number_1\ldots\number_n$) ⇒ $\number$

If the function is invoked on zero numbers, then the number 0 is returned. If the function is invoked on one number, then that number is returned. If the function is invoked on more than one number, then the result of adding those numbers from left to right is returned: the second number is added to the first number, then the third number is added to the partial result just computed, … The function + is a nonprimitive function built on top of the primitive function _+, which must be invoked on exactly two numbers.

> (+)
0

> (+ 1)
1

> (+ 1 2)
3

> (+ 1 2 3)
6

(- $\number_1\ldots\number_n$) ⇒ $\number$

If the function is invoked on zero numbers, then the invocation completes abruptly for a reason of type error. If the function is invoked on one number, then the opposite of that number is returned. If the function is invoked on more than one number, then the result of subtracting those numbers from left to right is returned: the second number is subtracted from the first number, then the third number is subtracted from the partial result just computed, … The function - is a nonprimitive function built on top of the primitive function _-, which must be invoked on exactly two numbers.

> (-)
EvaluatorError: program-error: Expecting at least one number.

> (- 1)
-1

> (- 0 1)
-1

> (- 0 1 2)
-3

> (- 0 1 2 3)
-6

(* $\number_1\ldots\number_n$) ⇒ $\number$

If the function is invoked on zero numbers, then the number 1 is returned. If the function is invoked on one number, then that number is returned. If the function is invoked on more than one number, then the result of multiplying those numbers from left to right is returned: the first number is multiplied by the second number, then the partial result just computed is multiplied by the third number, … The function * is a nonprimitive function built on top of the primitive function _*, which must be invoked on exactly two numbers.

> (*)
1

> (* 2)
2

> (* 2 4)
8

> (* 2 4 8)
64

(/ $\number_1\ldots\number_n$) ⇒ $\number$

If the function is invoked on zero numbers, then the invocation completes abruptly for a reason of type error. If the function is invoked on one number, then the inverse of that number is returned. If the function is invoked on more than one number, then the result of dividing those numbers from left to right is returned: the first number is divided by the second number, then the partial result just computed is divided by the third number, … The function / is a nonprimitive function built on top of the primitive function _/, which must be invoked on exactly two numbers.

> (/)
EvaluatorError: program-error: Expecting at least one number.

> (/ 2)
0.5

> (/ 1 2)
0.5

> (/ 1 2 4)
0.125

> (/ 1 2 4 8)
0.015625

Comparison Operators

(= $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ and $\number_2$ are numerically equal and #f otherwise.

(/= $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ and $\number_2$ are numerically different and #f otherwise.

(< $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ is numerically less than $\number_2$ and #f otherwise.

(<= $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ is numerically less than or equal to $\number_2$ and #f otherwise.

(> $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ is numerically greater than $\number_2$ and #f otherwise.

(>= $\number_1$ $\number_2$) ⇒ $\boolean$

The function returns #t if $\number_1$ is numerically greater than or equal to $\number_2$ and #f otherwise.

> (list (= -1 0) (= 0 0) (= 1 0))
(#f #t #f)

> (list (/= -1 0) (/= 0 0) (/= 1 0))
(#t #f #t)

> (list (< -1 0) (< 0 0) (< 1 0))
(#t #f #f)

> (list (<= -1 0) (<= 0 0) (<= 1 0))
(#t #t #f)

> (list (> -1 0) (> 0 0) (> 1 0))
(#f #f #t)

> (list (>= -1 0) (>= 0 0) (>= 1 0))
(#f #t #t)

The names of the comparison operators do not end with a question mark because they traditionally do not (in mathematics and other programming languages).

Data Type list

(list? $\object$) ⇒ $\boolean$

The function returns #t if $\object$ is of type list and #f otherwise.

> (list? '())
#t

> (list? '(1 2 3))
#t

(list $\object_1\ldots\object_n$) ⇒ $\list$

The function collects its arguments into a list: when invoked on the arguments $\object_1,\ldots,\object_n$, the function returns a list whose elements are $\object_1,\ldots,\object_n$.

> (list)
()

> (list 1 2 3)
(1 2 3)

Data Type empty-list

(empty-list? $\object$) ⇒ $\boolean$

The function returns #t if $\object$ is of type empty-list and #f otherwise.

> (empty-list? '())
#t

> (empty-list? '(1 2 3))
#f

Data Type cons

(cons? $\object$) ⇒ $\boolean$

The function returns #t if $\object$ is of type cons and #f otherwise.

> (cons? '())
#f

> (cons? '(1 2 3))
#t

(cons $\object_1$ $\object_2$) ⇒ $\cons$

The function returns a new cons whose first element is $\object_1$ and whose second element is $\object_2$.

> (cons 3 '())
(3)

> (cons 2 (cons 3 '()))
(2 3)

> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)

(car $\cons$) ⇒ $\object$

The function returns the first element of $\cons$.

(cdr $\cons$) ⇒ $\object$

The function returns the second element of $\cons$.

> (car '(1 2 3))
1

> (cdr '(1 2 3))
(2 3)

> (car (cdr '(1 2 3)))
2

> (cdr (cdr '(1 2 3)))
(3)

> (car (cdr (cdr '(1 2 3))))
3

> (cdr (cdr (cdr '(1 2 3))))
()

Equality Predicates

The purpose of an equality predicate is to test the sameness of two objects. An equality predicate returns #t if the two objects are the same and #f otherwise. Because there are multiple notions of sameness, there are multiple equality predicates. The three main equality predicates are eq?, eql?, and equal?.

(eq? $\object_1$ $\object_2$) ⇒ $\boolean$

The function returns #t if and only if the two objects are one and the same. In other words, the function returns #t if and only if the two objects have the same address in the heap.

(eql? $\object_1$ $\object_2$) ⇒ $\boolean$

If both objects are of type number, then the function returns #t if and only if the two objects represent the same mathematical number. Otherwise, if both objects are of type character, then the function returns #t if and only if the two objects represent the same Unicode character. Otherwise, if both objects are of type string, then the function returns #t if and only if the two objects represent the same indexed sequence of Unicode characters. Otherwise, the function returns #t if and only if the two objects are eq?.

(equal? $\object_1$ $\object_2$) ⇒ $\boolean$

If both objects are of type cons, then the function returns #t if and only if the cars of the two objects are equal? and the cdrs of the two objects are equal?. Otherwise, if both objects are of type vector, then the function returns #t if and only if the two objects have the same length and their corresponding elements are equal?. Otherwise, the function returns #t if and only if the two objects are eql?.

The three main equality predicates are related as follows:

• When testing the sameness of two objects of different leaf types, eq?, eql?, and equal? all return #f.
• When testing the sameness of two objects of type void, two objects of type boolean, two objects of type keyword, two objects of type variable, two objects of type empty-list, two objects of type primitive-function, or two objects of type closure, equality under eq? is equivalent to equality under eql? and equality under eql? is equivalent to equality under equal?.
• When testing the sameness of two objects of type number, two objects of type character, or two objects of type string, equality under eq? implies equality under eql? (but the converse is not true) and equality under eql? is equivalent to equality under equal?.
• When testing the sameness of two objects of type cons or two objects of type vector, equality under eq? is equivalent to equality under eql? and equality under eql? implies equality under equal? (but the converse is not true).

Of the three main equality predicates, eq? is the most discriminating and equal? is the least discriminating.

Because the three main equality predicates all return #f when testing the sameness of two objects of different leaf types, which one to use depends only on their behaviors when testing the sameness of two objects of the same leaf type.

By design, any two objects of type void are considered to be the same object. Because there exists in the heap exactly one object of type void, two objects of type void are necessarily one and the same. Therefore, the appropriate equality predicates to test the sameness of two objects of type void are eq? and the equivalent eql? and equal?.

When testing the sameness of two objects of type boolean, we want to test if the two objects represent the same truth value. Because there exists in the heap exactly one object of type boolean representing true and exactly one object of type boolean representing false, representing the same truth value is equivalent to being one and the same. Therefore, the appropriate equality predicates to test the sameness of two objects of type boolean are eq? and the equivalent eql? and equal?.

When testing the sameness of two objects of type number, we want to test if the two objects represent the same mathematical number. Because there can exist in the heap more than one object of type number representing the same mathematical number, representing the same mathematical number is not equivalent to being one and the same. Therefore, eq? is not an appropriate equality predicate to test the sameness of two objects of type number. The appropriate equality predicates are eql? and the equivalent equal?.

When testing the sameness of two objects of type character, we want to test if the two objects represent the same Unicode character. Because there can exist in the heap more than one object of type character representing the same Unicode character, representing the same Unicode character is not equivalent to being one and the same. Therefore, eq? is not an appropriate equality predicate to test the sameness of two objects of type character. The appropriate equality predicates are eql? and the equivalent equal?.

When testing the sameness of two objects of type string, we want to test if the two objects represent the same indexed sequence of Unicode characters. Because there can exist in the heap more than one object of type string representing the same indexed sequence of Unicode characters, representing the same indexed sequence of Unicode characters is not equivalent to being one and the same. Therefore, eq? is not an appropriate equality predicate to test the sameness of two objects of type string. The appropriate equality predicates are eql? and the equivalent equal?.

Using eq? to test the sameness of two objects of type number, two objects of type character, or two objects of type string is never safe because the evaluator is free to make copies of objects of those types at any time. Let us illustrate the point by considering the form ((_vlambda (x) (eq? x x)) 0). It is not guaranteed that the object of type number created by the reader, the value of the variable x, the first argument passed to the function eq?, and the second argument passed to the function eq? are one and the same. If the two objects passed to the function eq? happen to be one and the same, then the test evaluates to #t. If the two objects passed to the function eq? happen not to be one and the same, then the test evaluates to #f. Even in this seemingly straightforward case, the result of the test is unpredictable. The same goes for objects of type character and string.

By design, any two objects of type keyword/variable sharing the same name are considered to be the same object. Because there cannot exist in the heap more than one object of type keyword/variable with the same name, having the same name is equivalent to being one and the same. Therefore, the appropriate equality predicates to test the sameness of two objects of type keyword/variable are eq? and the equivalent eql? and equal?.

By design, any two objects of type empty-list are considered to be the same object. Because there exists in the heap exactly one object of type empty-list, two objects of type empty-list are necessarily one and the same. Therefore, the appropriate equality predicates to test the sameness of two objects of type empty-list are eq? and the equivalent eql? and equal?.

When testing the sameness of two objects of type cons or two objects of type vector, we can use eq? or the equivalent eql? to test if the two objects are one and the same or we can use equal? to test if the two objects have the same elements. Whether to use eq?/eql? or equal? is usually obvious from the purpose of the test.

When testing the sameness of two objects of type primitive-function or two objects of type closure, we would like to test if the two objects have the same behavior (same input/output mapping and same side effects). In practice, we can only test if the two objects are one and the same by using eq? or the equivalent eql? and equal?. For objects of type primitive-function, being one and the same is equivalent to having the same behavior. For objects of type closure, being one and the same implies having the same behavior but the converse is not true.

When testing the sameness of two objects that can each be of leaf type $type_1$, $type_2$, …, an equality predicate that is appropriate to test the sameness of two objects of type $type_1$, two objects of type $type_2$, … must be used.

As a matter of style, when more than one equality predicate is appropriate, the most discriminating one should be used. As a matter of style again, when testing the sameness of two objects that can only be of type number, the comparison operator = should be used instead of the equality predicate eql?.

Global Definitions

(vdef $\metavar{variable}$ $\metavar{value-form}$)

The macro defines a global variable by ensuring that the variable is bound in the value namespace of the global environment to the primary value of the value form. The macro call evaluates to the variable.

(fdef $\metavar{variable}$ $\metavar{parameter-list}$ $\metavar{body}$)

The macro defines a global function by ensuring that the variable is bound in the function namespace of the global environment to the closure resulting from the evaluation of the _vlambda form (_vlambda $\metavar{parameter-list}$ $\metavar{body}$). The macro call evaluates to the variable.

(mdef $\metavar{variable}$ $\metavar{parameter-list}$ $\metavar{body}$)

The macro defines a global macro by ensuring that the variable is bound in the function namespace of the global environment to the closure resulting from the evaluation of the _mlambda form (_mlambda $\metavar{parameter-list}$ $\metavar{body}$). The macro call evaluates to the variable.

Evaluation and Invocation Traces

An evaluation trace is a structured recording of some or all of the evaluations, invocations, and various steps performed by the evaluator to evaluate a form. Evaluation traces have the following format:

• An evaluation trace is a sequence of lines.
• Times flows from top to bottom.
• Each recorded evaluation contributes two lines to the trace: an eval-in line of the form “The form $\mlvar{form}$ is evaluated with respect to $\lexenv$ and $\dynenv$.” recording the start of the evaluation and a matching eval-out line recording the completion of the evaluation. The eval-out line can take the following forms:
  • “The form $\mlvar{form}$ evaluates to $\obj_1,\ldots,\obj_n$.”, which records the normal completion of the evaluation.
  • “The evaluation of the form $\mlvar{form}$ completes abruptly.”, which records the abrupt completion of the evaluation.
• Each recorded invocation contributes two lines to the trace: an invoke-in line of the form “The function $\mlvar{function}$ is invoked on $\obj_1,\ldots,\obj_n$.” recording the start of the invocation and a matching invoke-out line recording the completion of the invocation. The invoke-out line can take the following forms:
  • “The function $\mlvar{function}$ returns $\obj_1,\ldots,\obj_m$.”, which records the normal completion of the invocation.
  • “The invocation of the function $\mlvar{function}$ completes abruptly.”, which records the abrupt completion of the invocation.
• A step line is a free-form line recording a step other than an evaluation or invocation.
• A comment line is a free-form line in italic type containing a comment.
• Lexical and dynamic environments are represented as $[\mlvar{binding}_1,\ldots,\mlvar{binding}_n]$ where bindings in the value namespace are represented as $\var\vbind\obj$ and bindings in the function namespace are represented as $\var\fbind\obj$.

An evaluation trace is a tool used to illustrate a point. Any evaluation, invocation, or step that is not necessary to illustrate the point can be omitted from the evaluation trace. The only constraint is that if an evaluation or invocation is included in the evaluation trace, then both the in line and the matching out line must be included.

Let $X$ be an evaluation or invocation and $Y$ be another evaluation or invocation. A consequence of the evaluation rules is that $X$ and $Y$ cannot overlap. If we place $X$-in, $X$-out, $Y$-in, and $Y$-out on a line where time flows from left to right, there are four possible configurations and two impossible configurations:

• possible ($X$ precedes $Y$): — $X$-in — $X$-out — $Y$-in — $Y$-out —
• possible ($Y$ precedes $X$): — $Y$-in — $Y$-out — $X$-in — $X$-out —
• possible ($Y$ is nested inside $X$): — $X$-in — $Y$-in — $Y$-out — $X$-out —
• possible ($X$ is nested inside $Y$): — $Y$-in — $X$-in — $X$-out — $Y$-out —
• impossible ($X$ and $Y$ overlap): — $X$-in — $Y$-in — $X$-out — $Y$-out —
• impossible ($X$ and $Y$ overlap): — $Y$-in — $X$-in — $Y$-out — $X$-out —

To make nesting more obvious, the lines located between a pair of matching in and out lines are indented to the right with respect to the matching lines. To make the connection between an in line and the matching out line more obvious, nonadjacent matching lines are connected by a vertical line.

An invocation trace is an evaluation trace that only records invocations. Macro invocations are almost always omitted from an invocation trace.

Here is an evaluation trace of the evaluation of the top-level form (+ 1 2). It will be assumed, wrongly, that the definition of the global function + is (fdef + (x y) (_+ x y)):

Let us consider the following global macro, whose purpose is to evaluate the form with respect to the lexical environment extending the current lexical environment to bind, in the value namespace, the variable to the primary value of the value form:

> (mdef simple-vlet (variable value-form form)
    (list (list '_vlambda (list variable) form) value-form))
simple-vlet

> (simple-vlet x 1 (+ x 2))
3

> (simple-vlet x 1 (simple-vlet y 2 (+ x y)))
3

Here is an evaluation trace of the evaluation of the top-level form (simple-vlet x 1 (+ x 2)):

Here is an evaluation trace of the evaluation of the top-level form (simple-vlet x 1 (simple-vlet y 2 (+ x y))):

When debugging a macro, it is often useful to examine some expansions generated by the macro. The expansion of the macro call ($\metavar{macro-operator}$ $\metavar{macro-operand}_1\ldots\metavar{macro-operand}_n$) can easily be obtained by evaluating the plain function call ((fref $\metavar{macro-operator}$) $\code{'}\metavar{macro-operand}_1\ldots\code{'}\metavar{macro-operand}_n$):

> ((fref simple-vlet) 'x '1 '(+ x 2))
((_vlambda (x) (+ x 2)) 1)

> ((fref simple-vlet) 'x '1 '(simple-vlet y 2 (+ x y)))
((_vlambda (x) (simple-vlet y 2 (+ x y))) 1)

> ((fref simple-vlet) 'y '2 '(+ x y))
((_vlambda (y) (+ x y)) 2)

> ((fref simple-vlet) 'x '1 ((fref simple-vlet) 'y '2 '(+ x y)))
((_vlambda (x) ((_vlambda (y) (+ x y)) 2)) 1)

Let us consider the following global function, which returns the absolute value of its argument:

> (fdef abs (x)
    (if (>= x 0) x (- x)))
abs

> (abs 1)
1

> (abs -1)
1

Here is an evaluation trace of the evaluation of the top-level form (abs 1):

Here is an evaluation trace of the evaluation of the top-level form (abs -1):

Let us consider the following global functions:

> (fdef sum-of-squares (x y)
    (+ (square x) (square y)))
sum-of-squares

> (fdef square (x)
    (* x x))
square

> (sum-of-squares 3 4)
25

Here is an invocation trace of the evaluation of the form (sum-of-squares 3 4):

Recursive Functions

A recursive function is a function that invokes itself directly ($f\rightarrow f$) or indirectly ($f\rightarrow g\rightarrow\cdots\rightarrow f$).

A recursive function call is a function call through which a recursive function invokes itself directly or indirectly.

A form is said to be in tail position with respect to a lambda abstraction other than a _dlambda form if and only if one of the following conditions is satisfied:

• The form is the last serial form of the body of the lambda abstraction.
• The form is the last serial form of a progn form in tail position with respect to the lambda abstraction.
• The form is the then form or the else form of an if form in tail position with respect to the lambda abstraction.

A form $\mlvar{form}$ in tail position with respect to a lambda abstraction has the following property: If (1) a closure resulting from the evaluation of the lambda abstraction is invoked and (2) the form $\mlvar{form}$ happens to be evaluated during the invocation of the closure, then the result of the evaluation of the form $\mlvar{form}$ becomes the result of the invocation of the closure without any further processing. (The values of the form are returned as is and not used otherwise.)

Factorial Function

The factorial function is defined by the following recurrence relation, where $n$ is a nonnegative integer:

• $0!=1$
• $n!=n(n-1)!$ for $n\gt0$

It follows from the definition that the factorial of $n$ is equal to the product of the first $n$ strictly positive integers:

The equality still holds for $n=0$ because the product is then empty and an empty product is, by convention, equal to $1$.

Here are the values of the factorial function for $n$ varying from $0$ to $10$:

The values of the factorial function can be computed by the global function fact, which is a direct translation of the recurrence relation:

> (fdef fact (n)
    (if (= n 0) 1 (* n (fact (- n 1)))))
fact

> (fact 10)
3628800

The global function fact contains one recursive function call, which is not in tail position.

Here is an invocation trace of the evaluation of the form (fact 6):

There are two phases in the evaluation of the form (fact 6): (1) an expansion phase during which the number of active invocations of fact increases and (2) a contraction phase during which the number of active invocations of fact decreases. When the evaluator is processing the invocation of fact on the number 0, there are $7$ active invocations of fact:

1. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 6. That invocation is waiting for the value of the recursive invocation of fact on the number (- n 1) = 5. When that value is eventually available, it will be multiplied by the number n = 6 and the result of the multiplication will be returned as the value of the invocation.
2. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 5. That invocation is waiting…
3. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 4. That invocation is waiting…
4. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 3. That invocation is waiting…
5. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 2. That invocation is waiting…
6. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 1. That invocation is waiting for the value of the recursive invocation of fact on the number (- n 1) = 0. When that value is eventually available, it will be multiplied by the number n = 1 and the result of the multiplication will be returned as the value of the invocation.
7. One invocation evaluating the body of fact with respect to a lexical environment binding, in the value namespace, the variable n to the number 0. That invocation directly returns the number 1 as its value without any further recursive invocation of fact.

The factorial is computed during the contraction phase by adding factors to a running product. The running product is initialized to the number 1 by the innermost invocation and the whole product is equal to $6\times(5\times(4\times(3\times(2\times(1\times1)))))$.

The values of the factorial function can also be computed by the global function fact-iter:

> (fdef fact-iter (n)
    (fact-iter/internal n 1))
fact-iter

> (fdef fact-iter/internal (n acc)
    (if (= n 0) acc (fact-iter/internal (- n 1) (* n acc))))
fact-iter/internal

> (fact-iter 10)
3628800

The bulk of the work is done by the auxiliary global function fact-iter/internal, which contains one recursive function call. The call to fact-iter/internal in fact-iter and the recursive function call in fact-iter/internal are both in tail position.

Here is an invocation trace of the evaluation of the form (fact-iter 6):

There are two phases in the evaluation of the form (fact-iter 6): (1) an expansion phase during which the number of active invocations increases and (2) a contraction phase during which the number of active invocations decreases. When the evaluator is processing the invocation of fact-iter/internal on the numbers 0 and 720, there are $8$ active invocations ($1$ of fact-iter and $7$ of fact-iter/internal):

1. One invocation evaluating the body of fact-iter with respect to a lexical environment binding, in the value namespace, the variable n to the number 6. That invocation is waiting for the value of the invocation of fact-iter/internal on the numbers n = 6 and 1. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
2. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 6 and the variable acc to the number 1. That invocation is waiting for the value of the recursive invocation of fact-iter/internal on the numbers (- n 1) = 5 and (* n acc) = 6. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
3. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 5 and the variable acc to the number 6. That invocation is waiting…
4. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 4 and the variable acc to the number 30. That invocation is waiting…
5. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 3 and the variable acc to the number 120. That invocation is waiting…
6. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 2 and the variable acc to the number 360. That invocation is waiting…
7. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 1 and the variable acc to the number 720. That invocation is waiting for the value of the recursive invocation of fact-iter/internal on the numbers (- n 1) = 0 and (* n acc) = 720. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
8. One invocation evaluating the body of fact-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 0 and the variable acc to the number 720. That invocation directly returns the number acc = 720 as its value without any further recursive invocation of fact-iter/internal.

The factorial is computed during the expansion phase by adding factors to a running product. The running product, which is initialized to the number 1 by fact-iter, is propagated up the invocation chain through the variable acc. The whole product, which is equal to $1\times(2\times(3\times(4\times(5\times(6\times1)))))$, is propagated down the invocation chain without any further processing.

Fibonacci Sequence

The Fibonacci sequence is defined by the following recurrence relation, where $n$ is a nonnegative integer:

• $F_0=0$
• $F_1=1$
• $F_n=F_{n-1}+F_{n-2}$ for $n\gt1$

Here are the values of the Fibonacci sequence for $n$ varying from $0$ to $10$:

The values of the Fibonacci sequence can be computed by the global function fib, which is a direct translation of the recurrence relation:

> (fdef fib (n)
    (if (= n 0)
        0
      (if (= n 1)
          1
        (+ (fib (- n 1)) (fib (- n 2))))))
fib

> (fib 10)
55

The global function fib contains two recursive function calls, which are not in tail position.

Here is an invocation trace of the evaluation of the form (fib 6):

During the evaluation of the form (fib 6), the global function fib is invoked $1$ time on the number 6, $1$ time on the number 5, $2$ times on the number 4, $3$ times on the number 3, $5$ times on the number 2, $8$ times on the number 1, and $5$ times on the number 0.

When the evaluator is processing the first invocation of fib on the number 0 (that invocation has a gray background in the invocation trace), there are $6$ active invocations of fib:

1. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 6. That invocation is waiting for the value of the recursive invocation of fib on the number (- n 1) = 5. When that value is eventually available, it will be saved in a temporary location and fib will be invoked recursively on the number (- n 2) = 4. When the value of the second recursive invocation of fib is eventually available, it will be added to the saved value of the first recursive invocation of fib and the result of the addition will be returned as the value of the invocation.
2. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 5. That invocation is waiting…
3. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 4. That invocation is waiting…
4. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 3. That invocation is waiting for the value of the recursive invocation of fib on the number (- n 1) = 2. When that value is eventually available, it will be saved in a temporary location and fib will be invoked recursively on the number (- n 2) = 1. When the value of the second recursive invocation of fib is eventually available, it will be added to the saved value of the first recursive invocation of fib and the result of the addition will be returned as the value of the invocation.
5. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 2. That invocation has already saved in a temporary location the value of the recursive invocation of fib on the number (- n 1) = 1 and is waiting for the value of the recursive invocation of fib on the number (- n 2) = 0. When the value of the second recursive invocation of fib is eventually available, it will be added to the saved value of the first recursive invocation of fib and the result of the addition will be returned as the value of the invocation.
6. One invocation evaluating the body of fib with respect to a lexical environment binding, in the value namespace, the variable n to the number 0. That invocation directly returns the number 0 as its value without any further recursive invocation of fib.

The values of the Fibonacci sequence can also be computed by the global function fib-iter:

> (fdef fib-iter (n)
    (fib-iter/internal n 0 1))
fib-iter

> (fdef fib-iter/internal (n a b)
    (if (= n 0)
        a
      (if (= n 1)
          b
        (fib-iter/internal (- n 1) b (+ a b)))))
fib-iter/internal

> (fib-iter 10)
55

The bulk of the work is done by the auxiliary global function fib-iter/internal, which contains one recursive function call. The call to fib-iter/internal in fib-iter and the recursive function call in fib-iter/internal are both in tail position.

Whereas the global function fib computes the Fibonacci sequence top-down in a branching process that repeats the computation of some Fibonacci numbers, the global function fib-iter computes the Fibonacci sequence bottom-up in a linear process that does not repeat the computation of any Fibonacci numbers:

• $F_2$ is computed from $F_1$ and $F_0$
• $F_3$ is computed from $F_2$ and $F_1$
• …

Let $n_\textrm{init}$ be the the argument of fib-iter and $n$, $a$, and $b$ be the arguments of the invocation of fib-iter/internal under consideration. When processing the invocation of fib-iter/internal from fib-iter, $n=n_\textrm{init}$, $a=F_0$, and $b=F_1$. If $n_\textrm{init}=0$, then fib-iter/internal returns $a=F_0$. Otherwise, if $n_\textrm{init}=1$, then fib-iter/internal returns $b=F_1$. Otherwise, fib-iter/internal invokes itself recursively. On each recursive invocation of fib-iter/internal, $n$ is decremented by $1$, $a$ is replaced by the next Fibonacci number in the sequence $F_0,F_1,F_2,\ldots$, and $b$ is replaced by the next Fibonacci number in the sequence $F_1,F_2,F_3,\ldots$ When processing the $(n_\textrm{init}-1)$-th recursive invocation of fib-iter/internal, $n=n_\textrm{init}-(n_\textrm{init}-1)=1$, $a=F_{0+n_\textrm{init}-1}=F_{n_\textrm{init}-1}$, and $b=F_{1+n_\textrm{init}-1}=F_{n_\textrm{init}}$ and fib-iter/internal returns $b=F_{n_\textrm{init}}$.

Here is an invocation trace of the evaluation of the form (fib-iter 6):

When the evaluator is processing the invocation of fib-iter/internal on the numbers 1, 5, and 8, there are $7$ active invocations ($1$ of fib-iter and $6$ of fib-iter/internal):

1. One invocation evaluating the body of fib-iter with respect to a lexical environment binding, in the value namespace, the variable n to the number 6. That invocation is waiting for the value of the invocation of fib-iter/internal on the numbers n = 6, 0 and 1. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
2. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 6, the variable a to the number 0, and the variable b to the number 1. That invocation is waiting for the value of the recursive invocation of fib-iter/internal on the numbers (- n 1) = 5, b = 1, and (+ a b) = 1. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
3. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 5, the variable a to the number 1, and the variable b to the number 1. That invocation is waiting…
4. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 4, the variable a to the number 1, and the variable b to the number 2. That invocation is waiting…
5. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 3, the variable a to the number 2, and the variable b to the number 3. That invocation is waiting…
6. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 2, the variable a to the number 3, and the variable b to the number 5. That invocation is waiting for the value of the recursive invocation of fib-iter/internal on the numbers (- n 1) = 1, b = 5, and (+ a b) = 8. When that value is eventually available, it will be returned as the value of the invocation without any further processing.
7. One invocation evaluating the body of fib-iter/internal with respect to a lexical environment binding, in the value namespace, the variable n to the number 1, the variable a to the number 5, and the variable 8 to the number 5. That invocation directly returns the number b = 8 as its value without any further recursive invocation of fib-iter/internal.