PPL212 -Assignment 3 -Solved

Part I: Theoretical Questions [35 points]
1.    Is let in L3 a special form? Justify your answer.

2.    In L3, what is the role of the function valueToLitExp?

3.    The valueToLitExp function is not needed in the normal evaluation strategy interpreter (L3-normal.ts). Why?

4.    The valueToLitExp function is not needed in the environment-model interpreter.

Why?

5.    What are the reasons that would justify switching from applicative order to normal order evaluation? Give an example.

6.    What are the reasons that would justify switching from normal order to applicative order evaluation? Give an example.

7.    In general, and as seen in class, substitution requires renaming. However, when the term that is substituted is "closed" (i.e., it does not contain free variables) then no renaming is required and naive substitution is correct.

a.    Prove it.

b.    Write evaluation rules for naive substitution

8.    Draw an environment diagram for the following computation. Make sure to include the lexical block markers, the control links and the returned values.

(define a 2) (define goo

(lambda (x)

(lambda (y)

(/ x y))))

(define foo (letrec

((f (goo a))

(g (lambda (x) (f x))))

(lambda (x)

(if (= x 0) x (g x)))))

(foo (foo 0))

Part II: Value Store [65 points]
In this part, you are given most of the implementation of the programming language L2.1. This language has almost the same syntax as the L2 language taught in class. The main difference is in the choice of evaluation model: it implements the Environment Model (L2 was implemented using the Substitution Model).

You are asked to change the implementation of the environment of L2.1 with two main features:

1.    Add a set! expression support

2.    Implement the mutation using a Value Store.

The Value Store
The value store plays the part of the heap in the execution: it is allocated dynamically during the execution and holds the actual value. The environment will now contain only the names of the variables and addresses of the value in the value store. The store is a partial function from these addresses to the values. Mutations occur only at the store. To do that, the value store will be implemented as an array of Box<Value> type.

Store API

Functions for managing the store need to be added: makeStore, extendStore, applyStore.

Allocating Memory
The store needs to be extended whenever memory needs to be allocated. You need to figure out where, during the evaluation, this should be done.

Applying Environment
Since the environment holds only pointers to the store, and the actual values reside in the store, the process of fetching the values needs to be changed.