Chapter 18. Summary

In this book we've watched the evolution of a programming language from humble beginnings to a powerful if somewhat incomplete implementation.

Starting from a global environment model in Chapter 3 with basic arithmetic and conditional evaluation, in Chapter 4 we introduced an environment passing model which made possible the implementation of local variables and much else besides. We also reasoned that trees are a much better structure for combining environment frames than stacks are, especially in Chapter 5 where we introduced function definition and closure.

We then went on to introduce recursive functions in Chapter 6, and showed that a different kind of binding is necessary to get recursive functions to work. Moving on, in Chapter 7, we introduced another type of binding which is performed sequentially. In the next chapter we looked at adding list processing to the language, allowing it to manipulate directly the structures that the language is composed of. Then in posession of that new set of functions, in Chapter 9 we added a macro facility that allowed the program to generate parts of its own structure.

Before adding other desirable features to the language we paused to describe the benefits of a language without such features, and noted that such a pure functional language was amenable to parallel evaluation. Brushing aside those concerns we moved on to add side effects, (both definition and assignment,) sequences and global definition.

Chapter 12 described a simple object-oriented extension to the language, using our existing environment implementation to model objects.

In Chapter 13 we re-wrote the entire interpreter in Continuation Passing Style, giving the language direct access to those continuations via call/cc (call-with-current-continuation) and showed how powerful a control tool continuations are.

In the short but sweet Chapter 14 we showed how trivial a threaded interpreter is once continuations are available, and in the equally short Chapter 15 we added built-in error handling and error recovery.

Chapter 16 took continuations even further, making a radical departure63 from a standard Scheme implementation to add the amb operator and backtracking. By showing that it is possible for an interpreter to pass both a normal (success) continuation and a failure continuation, backtracking was easily included into the PScheme core.

Chapter 17 discussed pattern matching and unification, added unification and other support routines as extensions to the interpreter. Then it used amb alongside those extentions to implement a simple but complete logic programming application in the PScheme language, demonstrating the essence of logic programming languages.

That's all for now.

Last updated Sun Mar 14 10:43:08 2010 UST
63

Why are departures always radical?