In this section, we'll use Scheme to implement an interpreter for a tiny subset of Scheme--just simple arithemetic expressions. The interpreter we'll show is simple, but it's a real interpreter--it works on the same principles as many real Scheme systems. In the next chapter, we'll show how a slightly more complicated interpreter which implements most of Scheme's important features, and the skeleton of a compiler for Scheme.
The interpreter is a good example for learning Scheme programming, because it makes heavy use of recursion--the processes of reading and evaluation are naturally recursive. As you'll see, the code is also an example of mostly-functional programming (with very few side effects); using recursion in the natural way avoids the need for side effects, because data structures are generally created at the right times, rather than being created too early and having to be updated later.
Our interpreter will use Scheme's built-in
to accept input in the form of s-expressions, i.e.,
expressions represented as standard Scheme data structures such
as symbols, numbers, and possibly nested lists of those constituents.
[Recall that...] S-expressions can be simple, as in the case of
symbols, or complex, as in the case of nested lists.