While this section is a brief one, and merely an introduction to the ideas of streams and delayed procedures, there is something important missing. It’s not possible to fully test our answers without an element of the Scheme language that the book never really reveals. While we can get through these exercises by just thinking through the process, it’s always nicer if we can add to our understanding by seeing our work in action, and knowing whether our expectations were correct. This post will cover that missing element, which will not only be useful for running this section, but something that will come in handy in most of the remaining chapters as well.

There’s a footnote in the book that explains that delay and cons-stream must be ‘special forms’ that allow for expressions in them to be treated a certain way. Both of these need to avoid evaluating the expressions given to them (i.e. their ‘arguments’), so they cannot be ordinary procedures. We have been given no way to create special forms, so these two would have to be part of the language already (in many implementations, delay is in fact present). Later on in the book we will learn to create our own custom evaluator. Now within that system, we’ll be able to make as many special forms as we want, but we’re not there yet. What the book never explains, though, is that Scheme actually does have its own way of defining new special forms.

Making custom special forms means that we’re actually modifying the language itself. It’s a potentially dangerous thing to do, so we’ll avoid it in our own work when possible. We do want it in this section to let us tinker with the delay form, and if we need it in the future it’ll be there as a possibility. It turns out to be fairly straightforward, at least for minor tweaks like this. In fact, the majority of the time that we want a special form will be when we simply want to avoid evaluating an expression immediately, and these sorts of special forms are pretty similar to just writing an ordinary procedure.

The most basic way to define a new special form in Scheme is to use a define-syntax statement. The define-syntax statement will provide a pattern, or template body of the special form. While it might look similar to a procedure, the difference is that the new syntax expression is not interpreted immediately. Instead, each time the special form is encountered, it is essentially replaced with the text of that pattern, using appropriate substitution for the ‘arguments’ of the special form. There’s a good primer of how this statement works in Scheme on this page if you desire a better understanding.

To illustrate, here is one of the special forms we’ll be using, namely the cons-stream statement:

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b))
             )
    )
  )

The syntax pattern or template is the list that is the second argument Not technically procedure ‘arguments’ to syntax-rules (the first argument here is an empty list, and means there are no special keywords). That pattern starts with the actual name of the special form, with the underscore being a shortcut for the label we have given to the special form (if your implementation does not support this shortcut, just replace the underscore with the special form’s label, e.g. cons-stream here). The remainder of that list is the names of what look like arguments in a procedure definition. However, they will not be evaluated, but textually replaced in the body. After this initial list, the remainder is the body, the actual code that should be used for a cons-stream statement. So if the interpreter encounters the statement (cons-stream 5 (+ 1 x)) it will directly replace it with (cons 5 (delay (+ 1 x))), and then evaluate that. It does not immediately evaluate the 5 or the (+ 1 x), which is what would happen if this were a regular procedure with arguments.

Being able to define our own special forms lets us extend and experiment with the language. While there are other ways to work with define-syntax and its pattern replacement methods, most of our needed special forms will look like this, and that will suffice for most if not all of our needs. It’s almost exactly like defining a procedure, and from external appearances functions nearly the same way, just without evaluating the arguments.

The procedures for working with streams, as well as the possible special forms needed for the delay statement, are provided in a separate file. That file also includes a few procedures for testing and creating streams from lists, so we can check the results programatically. Note that although MIT/GNU Scheme does have some of these stream procedures already implemented, they do not use memoization, and therefore will still require the included definitions (along with the special form for delay).

(Library file) streambasic.scm

Exercises 3.5.1.