| Sussman and Steele | December 22, 1975 | 6 | SCHEME Programming Examples |
Section 2: Some SCHEME Programming Examples
Traditional Recursion
Here is the good old familiar recursive definition of factorial, written in SCHEME.
(DEFINE FACT (LAMBDA (N) (IF (= N 0) 1 (* N (FACT (- N 1))))))
What About Iteration?
There are many other ways to compute factorial. One important way is through the use of iteration. Consider the following definition of FACT. Although it appears to be recursive, since it "calls itself", it captures the essence of our intuitive notion of iteration, because execution of this program will not produce internal structures (e.g. stacks or variable bindings) which increase in size with the number of iteration steps. This surprising fact will be explained in two ways.
- We will consider programming styles in terms of substitution semantics of the lambda calculus (Section 3).
- We will show how the SCHEME interpreter is implemented (Sections 4,5).
(DEFINE FACT (LAMBDA (N) (LABELS ((FACT1 (LAMBDA (M ANS) (IF (= M 0) ANS (FACT1 (- M 1) (* M ANS)))))) (FACT1 N 1))))
A common iterative construct is the DO loop. The most general form we have seen in any programming language is the MacLISP DO [Moon]. It permits the simultaneous initialization of any number of control variables and the simultaneous stepping of these variables by arbitrary functions at each iteration step. The loop is terminated by an arbitrary predicate, and an arbitrary value may be returned. The DO loop may have a body, a series of expressions executed for effect on each iteration.
The general form of a MacLISP DO is:
(DO ((<var1> <init1> <step1>) (<var2> <init2> <step2>) . . . (<varn> <initn> <stepn>)) (<pred> <value>) <body>)
