Teach yourself scheme in fixnum days

1 Enter Scheme

The canonical first program is the one that says «Hello, World!»» on the console. Using your favorite editor, create a file called hello.scm with the following contents:

The first line is a comment. When Scheme sees a semicolon, it ignores it and all the following text on the line.

To run this program, first start your Scheme. This is usually done by typing the name of your Scheme executable at the operating-system command line. E.g., in the case of MzScheme [9], you type

at the operating-system prompt.

Since you have such an eager listener, you need not always write your programs in a file and load them. Sometimes, it is easier, especially when you are in an exploring mood, to simply type expressions directly at the listener prompt and see what happens. For example, typing the form

at the Scheme prompt produces

Actually, you could simply have typed the form «Hello, World!»» at the listener, and you would have obtained as result the string

Other than the fact that the second approach produces a result with double-quotes around it, there is one other significant difference between the last two programs. The first (i.e., the one with the begin ) does not evaluate to anything — the Hello, World! it emits is a side-effect produced by the display and newline procedures writing to the standard output. In the second program, the form «Hello, World!»» evaluates to the result, which in this case is the same string as the form.

Henceforth, we will use the notation => to denote evaluation. Thus

(i.e., nothing or void), although it has the side-effect of writing

to the standard output. On the other hand,

In either case, we are still at the listener. To exit, type

and this will land you back at the operating-system command-line (which, as we’ve seen, is also a kind of listener).

The listener is convenient for interactive testing of programs and program fragments. However it is by no means necessary. You may certainly stick to the tradition of creating programs in their entirety in files, and having Scheme execute them without any explicit “listening”. In MzScheme, for instance, you could say (at the operating-system prompt)

and this will produce the greeting without making you deal with the listener. After the greeting, mzscheme will return you to the operating-system prompt. This is almost as if you said

Teach Yourself Scheme in Fixnum Days

This is an introduction to the Scheme programming language. It is intended as a quick-start guide, something a novice can use to get a non-trivial working knowledge of the language, before moving on to more comprehensive and in-depth texts.

The text describes an approach to writing a crisp and utilitarian Scheme. Although we will not cover Scheme from abs to zero?, we will This is an introduction to the Scheme programming language. It is intended as a quick-start guide, something a novice can use to get a non-trivial working knowledge of the language, before moving on to more comprehensive and in-depth texts.

The text describes an approach to writing a crisp and utilitarian Scheme. Although we will not cover Scheme from abs to zero?, we will not shy away from those aspects of the language that are difficult, messy, nonstandard, or unusual, but nevertheless useful and usable. Such aspects include call‑with‑current‑continuation, system interface, and dialect diversity. Our discussions will be informed by our focus on problem-solving, not by a quest for metalinguistic insight. I have therefore left out many of the staples of traditional Scheme tutorials. There will be no in-depth pedagogy; no dwelling on the semantic appeal of Scheme; no metacircular interpreters; no discussion of the underlying implementation; and no evangelizing about Scheme’s virtues. This is not to suggest that these things are unimportant. However, they are arguably not immediately relevant to someone seeking a quick introduction.

6 Recursion

A procedure body can contain calls to other procedures, not least itself:

Mutually recursive procedures are also possible. The following predicates for evenness and oddness use each other:

6.1 letrec

If we wanted the above procedures as local variables, we could try to use a let form:

This won’t quite work, because the occurrences of local‑even? and local‑odd? in the initializations don’t refer to the lexical variables themselves. Changing the let to a let* won’t work either, for while the local‑even? inside local‑odd? ’s body refers to the correct procedure value, the local‑odd? in local‑even? ’s body still points elsewhere.

To solve problems like this, Scheme provides the form letrec :

6.2 Named let

A recursive procedure defined using letrec can describe loops. Let’s say we want to display a countdown from 10 :

Scheme allows a variant of let called named let to write this kind of loop more compactly:

6.3 Iteration

countdown defined above is really a recursive procedure. Scheme can define loops only through recursion. There are no special looping or iteration constructs.

Nevertheless, the loop as defined above is a genuine loop, in exactly the same way that other languages bill their loops. I.e., Scheme takes special care to ensure that recursion of the type used above will not generate the procedure call/return overhead.

Scheme does this by a process called tail-call elimination. If you look closely at the countdown procedure, you will note that when the recursive call occurs in countdown ’s body, it is the tail call, or the very last thing done — each invocation of countdown either does not call itself, or when it does, it does so as its very last act. To a Scheme implementation, this makes the recursion indistinguishable from iteration. So go ahead, use recursion to write loops. It’s safe.

Here’s another example of a useful tail-recursive procedure:

Here’s yet another tail-recursive procedure, one that reverses its argument list “in place”, i.e., by mutating the contents of the existing list, and without allocating a new one:

( reverse! is a useful enough procedure that it is provided primitively in many Scheme dialects, e.g., MzScheme and Guile.)

In the last chapter, we defined two procedures throw‑one‑die and throw‑two‑dice that returned the result of a single experiment, i.e., a single throw of one or two dice. What if we want to find the expected result, and we don’t want to do the calculations? One way, the so-called Monte Carlo method, is to use iteration to run the experiment many (e.g., 10000) times, and average the results.

The expected values should be close to 3.5 and 7 respectively.

For some numerical-calculus examples of recursion (including iteration), see appendix C.

6.4 Mapping a procedure across a list

The map procedure applies a given procedure to every element of a given list, and returns the list of the results. E.g.,

The for‑each procedure also applies a procedure to each element in a list, but returns void. The procedure application is done purely for any side-effects it may cause. E.g.,

has the side-effect of displaying the strings (in the order they appear) on the console.

8 Macros

Users can create their own special forms by defining macros. A macro is a symbol that has a transformer procedure associated with it. When Scheme encounters a macro-expression — i.e., a form whose head is a macro —, it applies the macro’s transformer to the subforms in the macro-expression, and evaluates the result of the transformation.

Ideally, a macro specifies a purely textual transformation from code text to other code text. This kind of transformation is useful for abbreviating an involved and perhaps frequently occurring textual pattern.

The transformation yields the list

Scheme will then evaluate this expression, as it would any other.

As an additional example, here is the macro-definition for when ’s counterpart unless :

Alternatively, we could invoke when inside unless ’s definition:

Macro expansions can refer to other macros.

8.1 Specifying the expansion as a template

A macro transformer takes some s-expressions and produces an s-expression that will be used as a form. Typically this output is a list. In our when example, the output list is created using

where test is bound to the macro’s first subform, i.e.,

and branch to the rest of the macro’s subforms, i.e.,

Output lists can be quite complicated. It is easy to see that a more ambitious macro than when could lead to quite an elaborate construction process for the output list. In such cases, it is more convenient to specify the macro’s output form as a template, with the macro arguments inserted at appropriate places to fill out the template for each particular use of the macro. Scheme provides the backquote syntax to specify such templates. Thus the expression

is more conveniently written as

We can refashion the when macro-definition as:

The comma and the comma-splice are used to insert the macro arguments into the template. The comma inserts the result of evaluating its following expression. The comma-splice inserts the result of evaluating its following expression after splicing it, i.e., it removes the outermost set of parentheses. (This implies that an expression introduced by comma-splice must be a list.)

In our example, given the values that test and branch are bound to, it is easy to see that the template will expand to the required

8.2 Avoiding variable capture inside macros

my‑or takes two arguments and returns the value of the first of them that is true (i.e., non- #f ). In particular, the second argument is evaluated only if the first turns out to be false.

displays «doing first argument»» twice.

This is almost OK, except in the case where the second argument happens to contain the same identifier temp as used in the macro definition. E.g.,

Surely it should be 3! The fiasco happens because the macro uses a local variable temp to store the value of the first argument ( #f ) and the variable temp in the second argument got captured by the temp introduced by the macro.

To avoid this, we need to be careful in choosing local variables inside macro definitions. We could choose outlandish names for such variables and hope fervently that nobody else comes up with them. E.g.,

This will work given the tacit understanding that +temp will not be used by code outside the macro. This is of course an understanding waiting to be disillusioned.

A more reliable, if verbose, approach is to use generated symbols that are guaranteed not to be obtainable by other means. The procedure gensym generates unique symbols each time it is called. Here is a safe definition for my‑or using gensym :

8.3 fluid‑let

Here is a definition of a rather more complicated macro, fluid‑let (section 5.2). fluid‑let specifies temporary bindings for a set of already existing lexical variables. Given a fluid‑let expression such as

we want the expansion to be

Here is how we go about fashioning a fluid‑let macro that implements what we want:

The output list is created by the macro for our given example looks like

13 Jumps

13.1 call‑with‑current‑continuation

The current continuation at any point in the execution of a program is an abstraction of the rest of the program. Thus in the program

In other words, this continuation is a program that will add 1 to whatever is used to fill its hole.

This is what the argument of call/cc is called with. Remember that the argument of call/cc is the procedure

The program now running is simply

Note that r will abandon its own continuation, which is better illustrated by embedding the call to r inside some context:

The continuations provided by call/cc are thus abortive continuations.

13.2 Escaping continuations

Escaping continuations are the simplest use of call/cc and are very useful for programming procedure or loop exits. Consider a procedure list‑product that takes a list of numbers and multiplies them. A straightforward recursive definition for list‑product is:

13.3 Tree matching

A more involved example of continuation usage is the problem of determining if two trees (arbitrarily nested dotted pairs) have the same fringe, i.e., the same elements (or leaves) in the same sequence. E.g.,

The purely functional approach is to flatten both trees and check if the results match.

However, this traverses the trees completely to flatten them, and then again till it finds non-matching elements. Furthermore, even the best flattening algorithms will require cons es equal to the total number of leaves. (Destructively modifying the input trees is not an option.)

We can use call/cc to solve the problem without needless traversal and without any cons ing. Each tree is mapped to a generator, a procedure with internal state that successively produces the leaves of the tree in the left-to-right order that they occur in the tree.

The procedure same‑fringe? maps each of its tree arguments to a generator, and then calls these two generators alternately. It announces failure as soon as two non-matching leaves are found:

It is easy to see that the trees are traversed at most once, and in case of mismatch, the traversals extend only upto the leftmost mismatch. cons is not used.

13.4 Coroutines

The generators used above are interesting generalizations of the procedure concept. Each time the generator is called, it resumes its computation, and when it has a result for its caller returns it, but only after storing its continuation in an internal variable so the generator can be resumed again. We can generalize generators further, so that they can mutually resume each other, sending results back and forth amongst themselves. Such procedures are called coroutines [18].

We will view a coroutine as a unary procedure, whose body can contain resume calls. resume is a two-argument procedure used by a coroutine to resume another coroutine with a transfer value. The macro coroutine defines such a coroutine procedure, given a variable name for the coroutine’s initial argument, and the body of the coroutine.

13.4.1 Tree-matching with coroutines

Tree-matching is further simplified using coroutines. The matching process is coded as a coroutine that depends on two other coroutines to supply the leaves of the respective trees:

The leaf-generator coroutines remember who to send their leaves to:

The same‑fringe? procedure can now almost be written as

13.4.2 Getting wet

In the same‑fringe? program, the coroutines for the two trees report back to one managing coroutine, which takes care to call them alternately, as many times as needed. The two tree coroutines don’t interact with each other. Let’s now explore a scenario where all the managed coroutines can resume each other: i.e., the managing coroutine is hands-off and doesn’t micromanage the dispatching at all, simply reporting the final result when the work is done.

To prepare for this, Prof F decides to keep an umbrella at both home and office. Unfortunately, the smart prof is also absent-minded, so if the weather is clear, he invariably neglects to take an umbrella along, so there is a possibility that when it does rain, both his umbrellas are at the other place and he is stranded. How many walks can he hope to make before being stranded?

We can model each location (home, office) as a coroutine that keeps track of the number of umbrellas it has. Each walk is simulated by one location resuming the other. The resumption’s arguments include whether Prof F is carrying an umbrella (i.e., it is raining) and the number of walks so far (including the current one). When Prof F gets stranded, one of the location coroutines resumes the manager coroutine with the number of walks achieved.

The two location coroutines are just two instances of the same kind, and as such can be generated by a single procedure. We will have this procedure take the other location and the walk-manager as parameters.

(There is another, not very probable, possibility: The walks‑so‑far have reached the maximum, in which case, the location in question resumes the manager with that number. We need this to avoid an experiment that takes forever.)

The managing coroutine starts off one of the location coroutines, say the home. Since it refers to the home coroutine, we’ll use a coroutine-genertor procedure for it too, taking the home coroutine as paramter:

All it does is start off the professor at his home, and waits until one of the locations resumes it when the prof has stranded himself.

To start off the process, we need to actually generate the three coroutines, and link them together.

Note that we use lambda-wrapping, so the argument coroutines have a chance to be created before being used.

The body of the letrec then runs the manager

This should give the number of walks the prof manages before getting stranded. We’d like to run this simulation multiple times, plus we’d like to vary the rain probability. 2 Let’s wrap the letrec inside a procedure that takes these parameters and returns a thunk that can be run as one trial.

We can now call, say

and this will output the number of walks before strandedness.

To estimate the expected value of the achieved walks, we can use the monte‑carlo procedure we’ve already defined in chapter 6:

You will find that Prof F gets stranded in a matter of mere days, way before the 5-year goal he set himself. What do you think the result will be if the probability of rain is 0 or 1? What if it is a little more than 0 or a little less than 1? Well, you don’t have to puzzle over it. Just call monte‑carlo on umbrella‑trial with the appropriate argument!

1 If your Scheme does not already have this abbreviation, include ( define call/cc call‑with‑current‑continuation ) in your initialization code and protect yourself from RSI.