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).


 

The evaluator, which determines the meaning of expressions in a programming language, is just another program.

 

Meta Circularity

A meta circular evaluator for Pico is an interpreter for Pico that is written in Pico itself. How is this possible? In order to explain this, we just realize that in fact there are 2 Pico's: the first Pico is the 'real' Pico (whose interpreter was written in C, but that's not essential at all) and the 'meta circular Pico' (whose interpreter was written in 'real' Pico). The 'real' Pico is called the meta level and the 'false' Pico is called the base level Pico. Notice that 'false' is not really a well chosen word here as that evaluator is a real as the first one: it runs Pico programs. We will sometimes also talk about the implementing Pico (i.e. the 'real' Pico) and the implemented Pico (i.e. the 'other' Pico).

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:

Structure of the Meta Circular Evaluator

The structure of a meta circular evaluator is no different from the structure of any other evaluator. The only thing special about it is that it is written in the same language it evaluates. The evaluator consists of a so called 'Read-Eval-Print'-Loop (or REPL). This is a loop that is started and terminated by the programming environment. As you might expect, the REPL consists of three parts:


Back to the beginning !
This page was made (with lots of hard work!) by Wolfgang De Meuter