# Scheme: An Interpreter for Extended Lambda Calculus/Section 2
## Section 2: Some SCHEME Programming ExamplesSection 2: Some SCHEME Programming Examples
### Traditional RecursionTraditional Recursion

Here is the good old familiar recursive definition of factorial, written in SCHEME.

### What About Iteration?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).
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:
The semantics of this are that the variables are bound and initialized to the values of the <initi> expressions, which must all be evaluated in the environment outside the DO; then the predicate <pred> is evaluated in the new environment, and if TRUE, the <value> is evaluated and returned. Otherwise the body is evaluated, then each of the steppers <stepi> is evaluated in the current environment, all the variables made to have the results as their values, and the predicate evaluated again, and so on.
For example, the following MacLISP function:
computes the reverse of a list. In SCHEME, we could write the same function, in the same iterative style, as follows:
From this we can infer a general way to express iterations in SCHEME in a manner isomorphic to the MacLISP DO:
This is in fact what the supplied DO AMACRO expands into. Note that there are no side effects in the steppings of the iteration variables.

### Another Way To Do RecursionAnother Way To Do Recursion

Now consider the following alternative definition of FACT. It has an extra argument, the continuation [Reynolds], which is a function to call with the answer, when we have it, rather than return a value; that is, rather than ultimately reducing to the desired value, it reduces to a combination which is the application of the continuation to the desired value. ​
Note that we can call this like an ordinary function if we supply (LAMBDA (X) X) as the second argument. For example, (FACT 3 (LAMBDA (X) X)) returns 6.

### Apparently "Hairy" Control StructureApparently "Hairy" Control Structure

A classic problem difficult to solve in most programming languages, including standard (stack-oriented) LISP, is the samefringe problem [Smith and Hewitt]. The problem is to determine whether the fringes of two trees are the same, even if the internal structures of the trees are not. This problem is easy to solve if one merely computes the fringe of each tree separately as a list, and then compares the two lists. We would like to solve the problem so that the fringes are generated and compared incrementally. This is important if the fringes of the trees are very large, but differ, say, in the first position.
Consider the following obscure solution to samefringe, which is in fact isomorphic to the one written by Shrobe and presented by Smith and Hewitt. Note that SCHEME does not have the packagers of PLASMA, and so we were forced to use continuations; rather than using packages and a next operator, we pass a fringe a continuation (called the "getter") which will get the next and the rest of the fringe as its two arguments.
Now let us consider an alternative solution to the samefringe problem. We believe that this solution is clearer for two reasons:
* the implementation of SAMEFRINGE is more clearly iterative;
* rather than returning an object which will return both the first and the rest of a fringe to a given continuation, FRINGE returns an object which will deliver up a component in response to a request for that component.
A much simpler and more probable problem is that of building a pattern matcher with backtracking for segment matches. The matcher presented below is intended for matching single-level list structure patterns against lists of atoms. A pattern is a list containing three types of elements: ​
* constant atoms, which match themselves only.
* (THV x), which matches any single element in the expression consistently. We may abbreviate this as ?x by means of a LISP reader macro character.
* (THV* x), which matches any segment of zero or more elements in the expression consistently. We may abbreviate this as !x.
The matcher returns either NIL, meaning no match is possible, or a list of two items, an alist specifying the bindings of the match variables, and a continuation to call, if you don't like this particular set of bindings, which will attempt to find another match. Thus, for example, the invocation
would return the result
where calling <continuation1> as a function of no arguments would produce the result
where calling <continuation2> would produce NIL.
The MATCH function makes use of two auxiliary functions called NFIRST and NREST. The former returns a list of the first n elements of a given list, while the latter returns the tail of the given list after the first n elements.
The main MATCH function also uses a subfunction called MATCH1 which takes four arguments: the tail of the pattern yet to be matched; the tail of the expression yet to be matched; the alist of match bindings made so far; and a continuation to call if the match fails at this point. A subfunction of MATCH, called MATCH*, handles the matching of segments of the expression against THV* match variables. It is in the matching of segments that the ​potential need for backtracking enters, for segments of various lengths may have to be tried. After MATCH* matches a segment, it calls MATCH1 to continue the match, giving it a failure continuation which will back up and try to match a longer segment if possible. A failure can occur if a constant fails to match, or if one or the other of pattern and expression runs out before the other one does. ​

### A Useless Multiprocessing ExampleA Useless Multiprocessing Example

One thing we might want to use multiprocessing for is to try two things in parallel, and terminate as soon as one succeeds. We can do this with the following function.
TRY!TWO!THINGS!IN!PARALLEL takes two functions of no arguments (in order to pass an unevaluated expression and its environment in for later use, so as to avoid variable conflicts). It creates two processes to run them, and returns the value of whichever completes first.
As an example of how to misuse TRY!TWO!THINGS!IN!PARALLEL, here is a function which determines the sign of an integer using only ADD1, SUB1, and EQUAL.