SICP series - Interpretation
So far in this series we have seen that abstractions allow to hide details and create modules to model complex systems. Abstraction can be obtained by building procedures which capture patterns of computation and data structures made out of simpler components. Although they tackle complementary issues, the distinction between both kinds of abstraction are blurred and share a common structure. In the previous post we have drawn a comparison between the functional approach and a state-based one characterized by side effects. We have then formulated the environment model as model of evaluation to take into account mutation. Building on this last concept, we are going to delve into the central topic of the book: meta-linguistic abstractions. This topic deals both with the definition of a new language and with the process of evaluation of a program. This is the ultimate step in the process of abstraction, as it allows not only to combine and abstract over the primitive elements of a language, but to define new languages which introduce different primitives and consequently new ways of combination and abstraction tailor-suited to different kinds of problems.
Interpreter
In order to deduce the meaning associated to the expressions in a language, we need to define a set of procedures which compose what we call an interpreter or evaluator. An interpreter is then a program which is able to unwind the means of abstraction in a language and reduce them into means of combination or primitives of the language. It specifies what it means to evaluate expressions in this language, so it defines what is legal syntax or legal semantics.
Structure of an interpreter
An interpreter is composed of a series of components.
-
Lexical analyzer: maps a string of characters to a sequence of words (tokens). -
Parser: parses the sequence of words into a defined structure useful for the subsequent phase. An example of representation is a tree structure made up of pairs. -
Evaluator: works hand-in-hand with an environment, a sort of dictionary associating names to values. The evaluator employs a set of rules to reduce complex expressions to simpler elements until a simple value is returned. -
Printer: converts the returned value in the appropriate form (e.g. a string) and displays it to the user.
It is possible to exploit Scheme to take care of some of the steps of the interpretation process to avoid to build them from scratch. So we will focus only on the evaluator, the core of the evaluation process. This means that we will need to build a language resembling Scheme in that it should have a tree structure as the output of the parser and a set of rules for manipulating that tree structure.
Eval-Apply
The evaluator is composed of several functions to evaluate different elements of the language, and a function to apply procedures on the evaluated arguments. It is the interplay of this eval-apply cycle that makes up the core of the process of evaluation:
The evaluation of an expression with respect to an environment reduces to an application of a procedure to a set of arguments. This in turn reduces to the evaluation of a simpler expression, the body of the procedure, with respect to a new environment (one in which the formal parameters of the procedure have been bound to the arguments passed in). The loop continues unwinding expressions until it reaches the application of a primitive procedure to primitive values or the evaluation of a primitive data object.
Note that it is important to exploit data abstraction to define the elements on which the evaluation procedures work in order to separate the syntax of the language from its semantics. This is useful as it allows to change the syntax of the language without having to change the evaluator, i.e. the semantics. So for example to implement the syntactic change to function calls it is necessary to just change the procedures dealing with the syntax, i.e. those walking the tree structure and pulling out the pieces.
Metacircular Evaluator
We have talked so far how it is possible to create languages within Scheme by defining an evaluator which defines some procedures to implement the eval-apply cycle. For example, it is possible to define a language for processing arithmetic expressions which resembles Scheme. However, this is not all. In fact, it is actually possible to write the actual Scheme evaluator with Scheme itself! This is what has been named by the authors of the book as metacircular evaluator, since writing the interpreter in a language is equivalent to defining the language itself.
To build a complete evaluator of Scheme, it is necessary to define the procedures to implement the following elements of the language:
-
semantics - the core evaluator composed of the eval-apply procedures
-
syntax - procedures detailling how to write legal expressions in the language
-
environment manipulation - procedures that implement the Environment Model defined in the previous post
-
primitive procedures and initial global environment
-
read-eval-print loop (REPL) to interact with the evaluator
I close this post by including this funny clip taken from the lecture given by Prof. Gerald Sussman.