Meta Circular Evaluators

This page is completely based on the 4th chapter of the famous "Abelsson and Sussman" course (book: Abelson & Sussman: Structure and Interpretation of Computer Programs - SICP).

Meta Circularity

According to SICP, an evaluator that is written in the same language that it evaluates is said to be meta circular.

Studying meta circular evaluators for any language L is a very useful activity because:

• By studying this volume of L code, you get to know L much better than by merely studying small code excerpts and standard algorithms.
• By studying the code, we get a a precise definition of the semantics of L. In fact, the code for the evaluator is the only precise definition of the semantics. The only drawback of a metacircular definition is that it cannot be used in practice because the resulting evaluator is too slow.
• Although the evaluator studied is written specifically for L, it contains the essential structure of an evaluator for any computer language. By studying and experimenting with one metacircular evaluator, students are acquainted to the entire discipline of interpreter building is a very accessible way.
• The essence of meta circularity is that one has to understand precisely one program written in L in order to understand all programs written in L!

Structure of the Meta Circular Evaluator

• Read When the user types in a program, this program is just a text, a meaningless sequence of characters. Before the core of the evaluator can do something reasonable with it, it has to check whether that sequence of characters indeed constitutes a valid program. This because many texts can be rejected as being wrong programs (e.g. because parentheses don't match). Instead of detecting this during the execution of the wrong program, it is better to detect it before beginning any execution. This checking phase is called the reading phase of the REPL. The reader takes a piece of text that is expected to meet the rules of the syntax of the language. If the text does not meet the definition of the syntax, an error is generated. Otherwise, the reader transforms the text meeting the concrete syntax into a tree data structure, the so-called parse tree. This tree represents the structure of the program and no longer contains surface syntax like parentheses. The reader for pico consists of two files representing the scanner (or lexical analyzer) and the parser (or structural analyzer). The scanner transformes the program text into a stream of 'tokens' such that all irrelevant information such as whitespaces and carriage returns have been removed. The parser consumes these tokens and tries to find the structure linking the tokens in order to build up the parse tree.
• Eval After reading a string, we obtain a parse tree which is of course much easier to process than the original string (after all, that's the reason why we parse in the first place). Therefore, evaluating the program boils down to performing a tree recursive process on the parse tree. Hence, the evaluator is a tree recursive process that consumes a parse tree and returns a Pico value. Each step in this recursive process takes one node in the parse tree, dispatches over the kind of node (is it a definition, an assignment,...) and undertakes the appropriate steps to process that particular kind of node. In many cases, this will require recursive calls to the evaluator. The result of the recursive evaluation procedure is called a Pico value.
• Print After calling the evaluator, the printer is called. The printer can be considered the inverse of the reader. It takes a Pico value (a tree) and prints the value on the screen in a form that makes sense to the Pico programmer.