| Sussman and Steele | December 22, 1975 | 8 | SCHEME Programming Examples |
(DEFINE FACT (LAMBDA (N C) (IF (= N 0) (C 1) (FACT (- N 1) (LAMBDA (A) (C (* N A)))))))
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 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.
(DEFINE FRINGE (LAMBDA (TREE) (LABELS ((FRINGEN (LAMBDA (NODE ALT) (LAMBDA (GETTER) (IF (ATOM NODE) (GETTER NODE ALT) ((FRINGEN (CAR NODE) (LAMBDA (GETTER1) ((FRINGEN (CDR NODE) ALT) GETTER1))) GETTER)))))) (FRINGEN TREE (LAMBDA (GETTER) (GETTER '(EXHAUSTED) NIL))))))
