1
false)))
This is pretty much exactly what you would have been tempted to write by hand. In fact, read it and it’s
obvious that it implements a simple conditional matcher over symbols. Furthermore, it has a very convenient
interface: a matcher is a first-class function value suitable for application in several contexts, being passed to
other procedures, etc. The macro produced this by recursively generating lots of functions, but a smart choice
of compiler “primitive”—((lambda · · ·) · · ·), in this case—that was sensitive to the needs of macros reduced
the result to taut code. Indeed, it now leaves the code in a state where the compiler can potentially apply
further optimizations (e.g., for large numbers of comparisons, it can convert the cascade of comparisons into
direct branches driven by hashing on the symbol being compared).
37.3
Example: Automata
Next, we examine another optimization that is crucial for capturing the intended behavior of many programs.
As an example, suppose we want to define automata manually. Ideally, we should be able to specify the
automata once and have different interpretations for the same specification; we also want the automata to
be as easy as possible to write (here, we stick to textual notations). In addition, we want the automata to
execute fairly quickly, and to integrate well with the rest of the code (so they can, for instance, be written
in-line in programs).
Concretely, suppose we want to write a simple automaton that accepts only patterns of the form (01)∗.
We might want to write this textually as
342
CHAPTER 37. MACROS AND THEIR IMPACT ON LANGUAGE DESIGN
automaton see0
see0 : 0 -> see1
see1 : 1 -> see0
where the state named after the keyword automaton identifies the initial state.
Consider a slightly more complex automaton, one that recognizes the Lisp identifier family car, cdr,
cadr, cddr, cddar and so on. To simplify the example, let’s say it should recognize the regular language
c(ad)∗r. The corresponding automaton might look like
automaton init
init : c -> more
more : a -> more
d -> more
r -> end
end
:
We leave defining a more formal semantics for the automaton language as an exercise for the reader.
It is easy to see that some representation of the textual description suffices for treating the automata
statically. How do we implement them as programs with dynamic behavior? We request you, dear reader,
to pause now and sketch the details of an implementation before proceeding further.
A natural implementation of this language is to create a vector or other random-access data structure to
represent the states. Each state has an association indicating the actions—implemented as an association list,
associative hash table, or other appropriate data structure. The association binds inputs to next states, which
are references or indices into the data structure representing states. Given an actual input stream, a program
would walk this structure based on the input. If the stream ends, it would accept the input; if no next state
is found, it would reject the input; otherwise, it would proceed as per the contents of the data structure. (Of
course, other implementations of acceptance and rejection are possible.)
One Scheme implementation of this program would look like this. First we represent the automaton as
a data structure:
(define machine
’((init (c more))
(more (a more)
(d more)
(r end))
(end)))
The following program is parameterized over machines and inputs:
(define (run machine init-state stream)
(define (walker state stream)
(or (empty? stream)
;; if empty, return true, otherwise . . .
(let ([transitions (cdr (assv state machine))]
[in (first stream)])
(let ([new-state (assv in transitions)])
37.3. EXAMPLE: AUTOMATA
343
(if new-state
(walker (cadr new-state) (rest stream))
false)))))
(walker init-state stream))
Here are two instances of running this:
> (run machine ’init ’(c a d a d d r))
true
> (run machine ’init ’(c a d a d d r r))
false
This is not the most efficient implementation we could construct in Scheme, but it is representative of
the general idea.
While this is a correct implementation of the semantics, it takes quite a lot of effort to get right. It’s easy
to make mistakes while querying the data structure, and we have to make several data structure decisions in
the implementation (which we have done only poorly above). Can we do better?
To answer this question affirmatively, let’s ignore the details of data structures and understand the
essence of these implementations.
1. Per state, we need fast conditional dispatch to determine the next state.
2. Each state should be quickly accessible.
3. State transition should have low overhead.
Let’s examine these criteria more closely to see whether we can recast them slightly:
fast conditional dispatch This could just be a conditional statement in a programming language. Compiler
writers have developed numerous techniques for optimizing properly exposed conditionals.
rapid state access Pointers of any sort, including pointers to functions, would offer this.
quick state transition If only function calls were implemented as gotos . . .
In other words, the init state could be represented by
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(c) (more (rest stream)) ]
[else false])))
That is, if the stream is empty, the procedure halts returning a true value; otherwise it dispatches on the first
stream element. Note that the boxed expression is invoking the code corresponding to the more state. The
code for the more state would similarly be
(lambda (stream)
(or (empty? stream)
344
CHAPTER 37. MACROS AND THEIR IMPACT ON LANGUAGE DESIGN
(case (first stream)
[(a) (more (rest stream))]
[(d) (more (rest stream))]
[(r) (end (rest stream))]
[else false])))
Each underlined name is a reference to a state: there are two self-references and one to the code for the end
state. Finally, the code for the end state fails to accept the input if there are any characters in it at all. While
there are many ways of writing this, to remain consistent with the code for the other states, we write it as
(lambda (stream)
(or (empty? stream)
(case (first stream)
;; no matching clauses, so always false
[else false])))
The full program is shown in Figure 37.2. This entire definition corresponds to the machine; the definition of machine is bound to init, which is the function corresponding to the init state, so the resulting value
needs only be applied to the input stream. For instance:
> (machine ’(c a d a d d r))
true
> (machine ’(c a d a d d r r))
false
What we have done is actually somewhat subtle. We can view the first implementation as an interpreter
for the language of automata. This moniker is justified because that implementation has these properties:
1. Its output is an answer (whether or not the automaton recognizes the input), not another program.
2. It has to traverse the program’s source as a data structure (in this case, the description of the automa-
ton) repeatedly across inputs.
3. It consumes both the program and a specific input.
It is, in fact, a very classical interpreter. Modifying it to convert the automaton data structure into some
intermediate representation would eliminate the second overhead in the second clause, but would still leave
open the other criteria.
In contrast, the second implementation given above is the result of compilation, i.e., it is what a compiler
from the automaton language to Scheme might produce. Not only is the result a program, rather than an
answer for a certain input, it also completes the process of transforming the original representation into one
that does not need repeated processing.
While this compiled representation certainly satisfies the automaton language’s semantics, it leaves two
major issues unresolved: efficiency and conciseness. The first owes to the overhead of the function appli-
cations. The second is evident because our description has become much longer; the interpreted solution
required the user to provide only a concise description of the automaton, and reused a generic interpreter
to manipulate that description. What is missing here is the actual compiler that can generate the compiled
version.
37.3. EXAMPLE: AUTOMATA
345
(define machine
(letrec ([init
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(c) (more (rest stream))]
[else false])))]
[more
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(a) (more (rest stream))]
[(d) (more (rest stream))]
[(r) (end (rest stream))]
[else false])))]
[end
(lambda (stream)
(or (empty? stream)
(case (first stream)
[else false])))])
init))
Figure 37.2: Alternate Implementation of an Automaton
37.3.1
Concision
First, let us slightly alter the form of the input. We assume that automata are written using the following
syntax (presented informally):
(automaton init
(init : (c → more))
(more : (a → more)
(d → more)
(r → end))
(end : ))
The general transformation we want to implement is quite clear from the result of compilation, above:
(state : (label → target) · · ·)
⇒
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(label) (target (rest stream))]
· · ·
[else false])))
346
CHAPTER 37. MACROS AND THEIR IMPACT ON LANGUAGE DESIGN
(define-syntax automaton
(syntax-rules (: →)
;; match ‘:’ and ‘→’ literally, not as pattern variables
[(automaton init-state
(state : (label → target) · · ·)
· · ·)
(letrec ([state
(lambda (stream)
(or (empty? stream)
(case (first stream)
[(label) (target (rest stream))]
· · ·
[else false])))]
· · ·)
init-state)]))
Figure 37.3: A Macro for Executable Automata
Having handled individual rules, we must make the automaton macro wrap all these procedures into a
collection of mutually-recursive procedures. The result is the macro shown in Figure 37.3. To use the
automata that result from instances of this macro, we simply apply them to the input:
> (define m (automaton init
[init : (c → more)]
[more : (a → more)
(d → more)
(r → end)]
[end : ]))
> (m ’(c a d a d d r))
true
> (m ’(c a d a d d r r))
false
By defining this as a macro, we have made it possible to truly embed automata into Scheme programs.
This is true purely at a syntactic level—since the Scheme macro system respects the lexical structure of
Scheme, it does not face problems that an external syntactic preprocessor might face. In addition, an au-
tomaton is just another applicable Scheme value. By virtue of being first-class, it becomes just another
linguistic element in Scheme, and can participate in all sorts of programming patterns.
In other words, the macro system provides a convenient way of writing compilers from “Scheme+” to
Scheme. More powerful Scheme macro systems allow the programmer to embed languages that are truly
different from Scheme, not merely extensions of it, into Scheme. A useful slogan (due to Matthew Flatt and
quite possibly others) for Scheme’s macro system is that it’s a lightweight compiler API.
37.3. EXAMPLE: AUTOMATA
347
37.3.2
Efficiency
The remaining complaint against this implementation is that the cost of a function call adds so much over-
head to the implementation that it negates any benefits the automaton macro might conceivably manifest.
In fact, that’s not what happens here at all, and this section examines why not.
Tony Hoare once famously said, “Pointers are like jumps”4. What we are seeking here is the reverse of
this phenomenon: what is the goto-like construct that corresponds to a dereference in a data structure? The
answer was given by Guy Steele: the tail call.
Armed with this insight, we can now reexamine the code. Studying the output of compilation, or the
macro, we notice that the conditional dispatcher invokes the function corresponding to the next state on the
rest of the stream—but does not touch the return value. This is no accident: the macro has been carefully
written to only make tail calls.5
In other words, the state transition is hardly more complicated than finding the next state (which is
statically determinate, since the compiler knows the location of all the local functions) and executing the
code that resides there. Indeed, the code generated from this Scheme source looks an awful lot like the
automaton representation we discussed at the beginning of section 37.3: random access for the procedures,
references for state transformation, and some appropriately efficient implementation of the conditional.
The moral of this story is that we get the same representation we would have had to carefully craft by
hand virtually for free from the compiler. In other words, languages represent the ultimate form of reuse,
because we get to reuse everything from the mathematical (semantics) to the practical (libraries), as well as
decades of research and toil in compiler construction.
Tail Calls versus Tail Recursion
This example should help demonstrate the often-confused difference between tail calls and tail recursion.
Many books discuss tail recursion, which is a special case where a function makes tail calls to itself. They
point out that, because implementations must optimize these calls, using recursion to encode a loop results
in an implementation that is really no less efficient than using a looping construct. They use this to justify,
in terms of efficiency, the use of recursion for looping.
These descriptions unfortunately tell only half the story. While their comments on using recursion for
looping are true, they obscure the subtlety and importance of optimizing all tail calls, which permit a family
of functions to invoke one another without experiencing penalty. This leaves programmers free to write read-
able programs without paying a performance penalty—a rare “sweet spot” in the readability-performance
trade-off. Traditional languages that offer only looping constructs and no tail calls force programmers to
artificially combine procedures, or pay via performance.
The functions generated by the automaton macro are a good illustration of this. If the implementation
did not perform tail-call optimization but the programmer needed that level of performance, the macro would
be forced to somehow combine all the three functions into a single one that could then employ a looping
4The context for the quote is pejorative: “Pointers are like jumps, leading wildly from one part of the data structure to another.
Their introduction into high-level languages has been a step backwards from which we may never recover.”
5Even if the code did need to perform some operation with the result, it is often easy in practice to convert the calls to tail-calls
using accumulators. In general, as we have seen, the conversion to continuation-passing style converts all calls to tail calls.
348
CHAPTER 37. MACROS AND THEIR IMPACT ON LANGUAGE DESIGN
construct. This leads to an unnatural mangling of code, making the macro much harder to develop and
maintain.
37.4
Other Uses
Scheme macros can do many more things. datum→syntax-object can be used to manufacture identifiers
from syntax supplied to the macro. Macros can also define other macros! You will find such examples
as you begin to employ macros in your work. Books such as Kent Dybvig’s The Scheme Programming
Language and Paul Graham’s On Lisp elaborate on these programming styles.
37.5
Perspective
We have now seen several examples of Scheme’s macro system at work. In the process, we have seen how
features that would otherwise seem orthogonal, such as macros, first-class procedures and tail-calls, are in
fact intimately wedded together; in particular, the absence of the latter two would greatly complicate use of
the former. In this sense, the language’s design represents a particularly subtle, maximal point in the design
space of languages: removing any feature would greatly compromise what’s left, while what is present is an
especially good notation for describing algorithms.
Part XIII
What’s Next?
349
Chapter 38
Programming Interactive Systems
Consider writing a program that solves a graph algorithm such as finding a minimum spanning tree. Your
implementation of the algorithm may suffer from several problems: even if the program runs to completion,
the output it produces may not be minimal, it may not span, and it may not even be a tree! While debugging
such a program by manual inspection of intermediate data structures can be onerous, often (especially if
the bug is in one of the latter two cases) it is easy to spot the problem visually. Suppose, however, you
were writing a library that was meant to be used in textual applications. It would not make sense to add
graph-drawing code to your library program. But how can you instrument your program from the “outside”
to add this functionality?
In principle, adding this graph-drawing instrumentation is something a debugger should support well. It
is, however, a very domain-specific instrumentation; it doesn’t make sense for a general-purpose debugger
to offer the ability to add graph-drawing code, because this is a property many applications don’t require. In
general, a debugger offers only a general, domain-independent view of a program’s data, while we would
often like to specialize this view to a domain-specific one. Ideally, that is, we would like to make the
debugger scriptable, so each application can install its own programs that run atop a library of debugging
primitives.
In most programming languages, programs expect to be in control of their execution. That is, the
beginning of the program initiates a process of execution, and the end of the program terminates it. The
program may invoke external agents (such as functions in libraries, procedures written in other languages
through a foreign-function interface, or even a method residing on a remote host through a remote procedure
call mechanism), but expect at some point (either synchronously or asynchronously) to get a response that
resumes the computation.
In a debugger scripting language, in contrast, the script is most certainly not in control of the computa-
tion. Two other programs—the target program being debugged, and the debugger itself—control the flow
of computation. The script should have the ability to install an event generator that triggers whenever some
event of interest—such as a method invocation, a variable mutation, a thread spawn, and so forth—happens
in the target program. The script only runs in response to these events. Furthermore, the script does not
return any answers to the target program (which is essentially unaware of the script’s existence) or to the
debugger (which, being general-purpose, may not know what to do with it), but rather preserves information
for its own (possible) subsequent execution.
351
352
CHAPTER 38. PROGRAMMING INTERACTIVE SYSTEMS
In fact, most modern applications share this characteristic: the application must lay dormant waiting for
some behavior from an external source of events. We have already seen this property in the case of Web
applications; programmers needed to invert the structure of their source to expose the points of resumption,
and manually represent the rest of the computation at each point. To remedy this problem, we devised
the send/suspend primitive, and showed that better language support makes Web applications far easier to
construct and maintain.
The Web is a simple interactive medium in the sense that there is only one kind of behavior available
to a user, namely clicking on a link or on a button. Other user actions are masked by the browser and not
conveyed to the Web application. In contrast, a modern GUI application—such as that Web browser itself—
must respond to multiple kinds of behavior, including keystrokes, mouse button pushes and mouse clicks.
Applications may also need to be sensitive to the receipt of network packets or the ticking of the system
clock.
Confronted with the challenge of building complex interactive systems, most programming languages
have taken a rather weak route. Traditional programming languages offer the callback as the primary method
of registering code that will respond to events. A callback is essentially a procedure that consumes arguments
corresponding to the event information—such as which key was pressed—and returns. . . nothing.
Why does a callback not return anything? A callback is a piece of application code that is “installed”
in the underlying system layer, to be invoked when that layer receives an event that the application must
process. That is, the system code invokes the callback. But it is the application that must process the event,
so there is no meaningful information that the callback can return to the system. This explains the return
type.
What do we know about procedures that do not return a value? To be of any use at all, they must
accomplish their action by using side-effects (such as mutation). This explains why side-effects, especially
mutation, are so prevalent in GUI applications. But side-effects, and procedures that don’t return any value,
are difficult to compose, and make it harder to reason about a program’s behavior. Is it surprising that GUIs
are difficult to develop correctly and to test for the absence of errors?
Many programmers see the current design of GUI libraries, with their plethora of callbacks, as a fixture
in the design space. We should know better. The callback-based solution should be especially familiar to us
from our Web programming experience: the continuation generated by CPS a procedure that does not return
any meaningful value (in fact, it doesn’t return at all), and represents the rest of the computation. As such,
it is a special kind of callback. If through better language design we were able to improve the state of Web
programming, perhaps better language design can improve GUI programming (and debugger scripting, and
. . . ) also?
This is precisely the kind of challenge that leads to research in programming languages. For instance,
the FrTime1 language in DrScheme is designed to make developing interactive applications, from debugging
scripts to GUIs, more direct. Though FrTime programs superficially look like Scheme programs, they eval-
uate under a very different semantics: certain expressions are known to yield sequences of events, and any
computation that depends on it in turn gets recomputed every time a new event occurs. Thus, for instance,
the expression
(make-circle mouse-pos 10 ”blue”)
1Pronounced “father time”.
353
automatically draws a blue circle of radius ten pixels wherever the mouse is currently centered, because
mouse-pos is a value in the language that updates whenever the mouse moves. Because it updates, every
expression that depends on it must also update to remain fresh. There is, therefore, no need for a loop to
ensure the circle is re-drawn: the “loop” is built into the language semantics! Note, of course, that there is
no need for a callback either.
This is just a miniscule example of how a deeper analysis of a problem can lead to better linguistic tools,
which can in turn make a problem much simpler than it was initially. Look up FrTime in DrScheme for
more on this fascinating language.
354
CHAPTER 38. PROGRAMMING INTERACTIVE SYSTEMS
Chapter 39
What Else is Next
At this point, it may be humbling to consider all the