« Return to index

HOP WPO 6

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

Section 0: Understanding The Metacircular Scheme evaluator

Download the metacircular implementation and open this file in DrRacket. In contrast to previous exercises that required you to make use of a file, you will need to make direct changes to this file. So be sure to keep a copy of the original file in case you wish to revert your changes.

If you have not set up DrRacket correctly, you might have to redo the instructions from the first lab session (be sure to uncheck “Disallow redefinition of initial bindings”). Also check the updated instructions in case you are using a command line interface![1]

The foundations

The metacircular implementation can be difficult to understand, since multiple components are inherently dependent on each other. The figure below showcases the four important components.

metacircular.png

The eval procedure




		

This procedure dispatches over the different types of expressions. After an expression has been entered in the REPL, it will be sent to this procedure for further evaluation. There are multiple branches here, and every branch represents one type of expression.

If you want to add new special forms (syntax), you have to add them to this condtional.

The apply procedure




		

This procedure is executed when the expression in eval is an application (it is a list). eval already evaluated both the operator expression and the argument expressions, therefore apply receives the procedure object (or something that is not a procedure: and therefore should raise an error) and a list of argument values.

Ignoring the error case, there are two options. Either a primitive procedure needs to be applied (a procedure that is given by the language implementation itself), or a user-defined (compound) procedure that is implemented by the user of the metacircular evaluator.

In the latter case, the body of the procedure is evaluated in the lexical scope that is created by extending the environment of the procedure object with the bindings that bind the formal parameters to the actual values.

The duality of eval and apply

sicp.jpg

The two most important componenets of the metacircular evaluator are eval and apply. We also need primitives and environments as part of a working language, but the heart of the implementation can be found in only eval and apply. The difference between eval and apply is…

Primitives

Primitive procedures are the foundation blocks on which new programs can be build. A Scheme evaluator by default comes with many primitives. For simplicity, only the most important ones are supplied in our metacircular implementation.




		

The variable primitive-procedures contains a list of all built in procedures. Each element of this list is a list of size 2, where the first element is the name (as a symbol) of the procedure: this is how it will be available in the global environment. The second element is the procedure object itself. In this metacircular Scheme evaluator the built-in procedure itself is made available.

Next to primitive operations there are special forms. Remember that the eval procedure dispatched over the different types of expressions. The main difference between procedures and special forms in the metacircular evaluator is that special forms work on expressions, and procedures work on evaluated expressions (i.e., values).

During the exercises we will delve in both procedures and special forms.

Environments

The last important component of the metacircular Scheme evaluator are environments. An environment can be seen as pair containing a frame, and a base environment. A frame is the combination of two lists: a list of variable names and a list of values that represents the bindings.




		

Every environment has an enclosing environment, except for the global environment which is the empty environment. Check the implementation of lookup-variable-value, set-variable-value!, and define-variable! for how special forms like define and set! operate, and how variables are resolved to their values.

Section 1: Primitive Procedures

In these exercises we are going to work on the metacircular implementation of Scheme in the Scheme implementation Racket. Remember that an evaluator is just a procedure (i.e. lambda) that when applied to an expression, performs the required actions to evaluate that expression. In other words, an evaluator is just another program. If we implement an evaluator in the same programming language for which we write an eval- uator, we call this a metacircular evaluator. Since a Scheme expression is actually just a list, a Scheme evaluator is nothing more than a list processing program.

Exercise 1: Adding Support for Vectors

Currently the metacircular evaluator only has support for pairs (via cons, car and cdr). Add support for vectors in the metacircular evaluator by extending the list of primitive operations. Verify whether the following program works in the metacircular evaluator.




		

Exercise 2: Division by Zero

Currently, the / procedure in the metacircular evaluator will make use of the / procedure from the host environment. Since that procedure raises an error when the divisor is equal to the number zero, the metacircular evaluator will stop working due to this error.

Instead of catching errors from the host environment in the metacircular evaluator, you will modify the / procedure in the metacircular evaluator such that it returns the number zero instead[2]. Therefore, you get the following behaviour in your modified metacircular evaluator.




		

Section 2: Syntactic Sugar

Before delving in how special forms can be implemented we will explore how new syntactic constructs can be created by using syntactic sugar: by expanding a Scheme expression from one form, into another.

Exercise 3: Implementing when

Currently, when you want to execute multiple expressions when a condition is true, you have to wrap all expressions in a begin, even when there is no “alternative” branch.




		

Wouldn’t it be better if this program could be written as follows.




		

Hint! Just as before, it can help to create accessor procedures that make it easier to retrieve values stored in the when expression: the condition, and the expression sequence stored within. Remember that code is data!

Expand (eval exp env) with a case that when it encounters a when, it will transform this expression to the corresponding program using only if and begin, and then apply eval on this transformed program.

Hint! Check how cond is supported in the current implementation for an example.

Hint! If you wish to check a part of your implementation, without starting the metacircular REPL you can uncomment (driver-loop) at the bottom of the file!

Exercise 4: Implementing let

Do the same thing for adding support for the let syntax: remember that for each well-formed let expression, an equivalent expression using lambda can be written (refer to earlier exercises that used this property). Make use of the same technique as in the previous exercise.

Hint! Just as before, it can help to create accessor procedures that make it easier to retrieve values stored in the let expression.

  1. Create the accessor procedures: (let-body, let-clauses, let-clause-name, let-clause-expression).
  2. Create a lambda expression where the formal parameters are the let-clause-names of the clauses, and the body is the let-body
  3. Create an application expression where the procedure is the one created in the previous step, and the arguments are the let-clause-expressions of the clauses.

Section 3: Special Forms

After adding new syntactical constructs to our Scheme evalu by transforming one expression into another, we will look at how they can be implemented directly without transforming their program text to an equivalent program text using lower constructs (such as lambda, instead of let).

Exercise 5: Implementing when

Repeat exercise 3, this time by implementing the behaviour of when manually.

It should…

Hint! Start by looking at the evaluation of if, and adapt. The value returned by when when the conditional expression returned false is unspecified.

Exercise 6: Imlementing let

Repeat the same for adding support for let.

It should…

Hint! You can reuse the syntactical accessors from exercise 4.

Section 4: Lazy Evaluator

Download the metacircular Scheme evaluator using call-by-need semantics for this section.

Exercise 7: Repetition

Bonus Exercises

Bonus Exercise 1: Adding support for let* (syntactic sugar)

Recommended after exercise 4.

Repeat exercise 4 in order to add support for let*. You can reuse the same accessor procedures, as let and let* have an similar syntax.

Bonus Exercise 2 : Adding support for let* (special form)

Recommended after exercise 6.

Repeat exercise 6 in order to add support for let*.

Bonus Exercise 3: Adding support for let* (lazy)

Recommended after exercise 7.

Repeat bonus exercise 2 for the lazy evaluator.


  1. In the implementation of the metacircular evaluator we redefine apply, which is not allowed by default in the R5RS implementation bundled with Racket. ↩︎

  2. This is not a correct as it should return NaN (not a number). However, this value is not available in Scheme. Therefore, if you want to be correct, you can also choose to return 'nan (as a symbol) instead, or +inf.0 or -inf.0 to represent an infinite value (depending on the sign of the dividend). ↩︎