2.2 How the Interpreter Works

Interpretation

The interpretation of a Lisp code is done in three steps:

• Black Opus: segmentation or decomposition
• White Opus: the creation of the execution tree
• Red Opus: execution of the code

Black Opus

The segmentation or decomposition of a code is an operation that consists in isolating the different elements of the code, namely:

• The operators
• The key words of the language
• Strings of characters
• Numbers
• Lists
• Dictionaries

In the case of our interpreter, this segmentation is performed using the method LispE::segmenting (in lispe.cxx).

This method is in fact very simple. It consists in detecting the characters whose interpretation is specific to the language.

segmenting detects:

• ': the simple apostrophe.
• / % + * - ^ << >> < > <= >= : the basic operators of LispE.
• "..." : the strings.
• atoms: the tokens. Note that LispE manipulates Unicode strings.
• (..): the opening and closing parentheses that define a list.
• {..}: the opening and closing braces that define a dictionary.
• 0..9: _numbers including decimal and hexadecimal numbers.

At each detection, segmenting records in a Tokenizer object, not only the code of each of these characters but also their position in the code.

Each character or sequence of characters identified by segmenting receives a particular identifier, the list of which is as follows:

typedef enum {e_token, e_opening_parenthesis, e_closing_parenthesis,
    e_operator, e_quote, e_chain, e_emptystring, e_digits, e_cadr,
    e_opening brace, e_closing brace, e_colon, e_character
} e_type;

White Opus: Execution Tree

Once the code has been segmented into clearly identified tokens, the second step is to produce the execution tree using the method: abstractSyntaxTree.

• Note that the Abstract Syntax Tree in Lisp has the particularity of being indistinguishable from the execution tree. We can directly produce this execution tree without having to go through an intermediate step as in most programming languages.

To do so, you just have to browse the list of segments in the Segmentation object, to query the type of these segments and to deduce the associated object.

The method abstractSyntaxTree takes in particular a List object as argument, in which all new objects are systematically stored. When an opening parenthesis is found, a new List is created and abstractSyntaxTree is called recursively with this new List as argument.

The presence of a closing parenthesis allows to exit this recursion. In this way, the execution tree builds itself naturally at each new iteration.

Thus the instruction:

Lisp (cons 'a ())

will be transformed into the following Element vector: 

Lisp
[Atom(cons), [Atom(quote) Atom(a)], []]

[...] corresponds to the content of the std::vector stored in the class List...

To evaluate this structure, we only need to interpret the first element of each List recursively.

eval([Atom(cons), [Atom(quote) Atom(a)], []])

Atom(cons) 
      eval([Atome(quote) Atome(a)]
           Atom(quote)
      eval([])

LispE::compile

This method allows to combine a call to segmenting followed by a call to abstractSyntaxTree.

It returns a List object that can be evaluated now.

Note that the code given to compile is first encapsulated in a (block code) instruction. In this way, one can analyze a simple expression as well as a complex program with a long list of instructions.

Red Opus: execution

The execution consists in calling the eval method on the object returned by compile. This object is by default a list whose evaluation method is implemented in the eval.cxx file: List::eval.

Each instruction is associated with a method from List in the evals array in Delegation.

For instance, quote is associated with List::evall_quote.

Element* List::evall_quote(LispE* lisp) {
   return liste[1];
}

//eq compares two elements together
Element* List::evall_eq(LispE* lisp) {
    Element* e1 = null_;
    Element* e2 = null_;
   try {
      // We evaluate each element
      e1 = liste[1]->eval(lisp);
      e2 = liste[2]->eval(lisp);
      //we compare the elements together (each type hosts its own equal method)
      Element* test = e1->equal(e2);
      //we do not need these elements anymore
      //we release them if their status is 0
      e1->release();
      e2->release();
      //we return the test value
      return test;
   }
   catch(Error* err) {
     //there was an error
     //we clean the memory
     e1->release();
     e2->release();
     //we propagate the error to the next call
     throw err;
   }