Overview

The goal of this project is to write an interpreter for a simple functional language called PLAN. The interpreter itself should be written in Scheme. A PLAN program is a list and defined by the following grammar:

(P γОJγa茄)    ::= ( planProg (Eα夕γ) )

(Eα夕γ)    ::= (Id)

l (CОng≠)

l ( planIf (Eα夕γ) (Eα夕γ) (Eα夕γ))

l ( planAdd (Eα夕γ) (Eα夕γ) )

l ( planMul (Eα夕γ) (Eα夕γ) )

l ( planSub (Eα夕γ) (Eα夕γ) )

l ( planLet (Id) (Eα夕γ) (Eα夕γ) )

l ( planLet (Id) ( planFunction (Id) (Eα夕γ) ) (Eα夕γ) )

l ( (Id) (Eα夕γ) )

(Id)    ::= a l b l . . . l z

(CОng≠)    ::= integer constant

As examples, here are five valid PLAN programs

1.  (planProg 5)

2.  (planProg (planAdd (planAdd 7 (planIf (planMul 4 5) 0 10)) (planMul 2 5)))

3.  (planProg (planLet z (planAdd 4 5) (planMul z 2)))

4.  (planProg (planLet a 66 (planAdd (planLet b (planMul 2 4) (planAdd 2 b)) (planMul 2 a))))

5.  (planProg (planLet x 66 (planAdd (planLet x (planMul 2 4) (planAdd 2 x)) (planMul 2 x))))

Each PLAN program and expression evaluates to an integer value. The semantics of a program are defined as follows:

1.  The entire program (prog (Eα夕γ)) evaluates to whatever (Eα夕γ) evaluates to.

2.  (planIf (Eα夕γ)  (Eα夕γ)  (Eα夕γ)) evaluates the first expression.  If this is > 0 then the planIf returns the result of the second expression, otherwise it returns the result of the the third expression.

3.  (planAdd (Eα夕γ) (Eα夕γ)) evaluates to the sum of the values the two expressions evaluate to.

4.  (planMul (Eα夕γ) (Eα夕γ)) evaluates to the product of the values the two expressions evaluate to.

5.  (planSub (Eα夕γ) (Eα夕γ)) evaluates to the difference of the values the two expression evaluate to.

6.  (planLet  (Id)  (Eα夕γ) 1   (Eα夕γ) 2 ) has the following semantics.  First,  (Eα夕γ) 1  is evaluated. The resulting integer value is bound to the identifier (Id) .  Then (Eα夕γ) 2  is evaluated, and the result of that evaluation serves as the value of the entire planLet expression. The binding between the id and the integer value is active only while (Eα夕γ) 2  is being evaluated.

7.  (Id) evaluates to the value the identifier has been bound by a planLet expression. PLAN will use dynamic scoping, i.e. if there are multiple bindings for the identifier the most recently executed active binding is used.

8.  (CОng≠) evaluates to the value of the integer constant.

9.  The semantics of (planLet (Id)  (planFunction (Id)  (Eα夕γ)) (Eα夕γ)) and ((Id)  (Eα夕γ)) are more complicated and are discussed in their own section below.

Based on these rules, the five programs from above evaluate to:

1.  5

2.  17

3.  18

4.  142

5.  142

Function Semantics

When a planLet expression contains a planFunction expression like

(planLet (Id) 1  (planFunction (Id) 2  (Eα夕γ) 1 ) (Eα夕γ) 2 )

is evaluated, the planFunction expression is evaluated by binding the body of the function (Eα夕γ) 1 to (Id) 1 . This binding is only active while (Eα夕γ) 2  is being evaluated.

Then,  if an expression  ((Id) 1   (Eα夕γ)) is encountered while evaluating  (Eα夕γ) 2   and a new binding for (Id) 1 has not been introduced, then the value of (Eα夕γ) is bound to (Id) 2  and (Eα夕γ) 1 is evaluated (once this finishes, the binding of the value of (Eα夕γ) and (Id) 2 is removed). The value from evaluating (Eα夕γ) 1  is the value of ((Id) 1  (Eα夕γ)).

So for example,

1.  (planProg (planLet a (planFunction b (planAdd b b)) (a 5))) evaluates to 10

2.  (planProg (planLet a (planFunction b (planAdd b b)) (planLet a 1 (planMul a a)))) evaluates to 1

Implementation

Write a Scheme function called myinterpreter that takes as input a single PLAN program and

outputs the result of evaluating that program. For example, an invocation

( m y i n t e r p r e t e r      ’ ( pla nProg   5 ) )

should produce the output 5.

Your code must work on the scheme48 interpreter. There can be a great deal of variation in how scheme interpreters work, so please make sure you only use scheme48.

The following instructions that limit what you can do. Please ask on piazza if any of this is at all unclear:

1.  The only built-in Scheme functions you are allowed to use are

❼ define, equal?, car, cdr, cons, list, append, cond, if, and, or, not, quote, ’, +, -, *, null?,

list?, symbol?, integer?, pair?

❼ car/cdr variants, like cadr, caar, cddr, and so on

❼ let and lambda, but I do not recommend these unless you are interested in extending

the project beyond what is required

You should not use any other built-in functions.

2.  Make sure your code is purely functional; here you need to give up on trying to assign to variables.

The following instructions and suggestions are intended to help you and/or simplify your interpreter’s implementation:

1. Name your file ”myfns.ss” and have a function named “myinterpreter” so your code interacts nicely with my scripts.

2. You do not need to write a scanner or a parser, the scheme interpreter automatically handles that for us and we will use the binary tree representation of the input as our parse tree.

3.  Create many functions that each have a simple, clear purpose.  You do not have the ability to do sequencing, everything will have to be recursive.

4.  Do not use the PLAN keywords as names your functions, i.e. instead of “(define (planAdd ...” use names like “(define (evalPlanAdd ...” . This will prevent you from making a common mistake I have seen in past semesters, and should help you avoid confusion.

5. You are guaranteed that the input given to the interpreter will not be empty, and will contain a valid PLAN program.   The program will be valid both syntactically and semantically. Syntactically, you can assume that any program given is valid with respect to the grammar from above.  Semantically, you can assume that any evaluation of an identifier has at least one existing binding for that identifier. Your implementation does not have to contain error-handling code. Do not worry about arithmetic issues such as underflow or overflow.

6. First write code to handle Plan programs with just constants (test cases 1-5). Then add the code for handling binding ids to values (test cases 6-10).  Then add the code for binding ids to functions and calling functions (test cases 11-14).

7. In order to maintain the set of bindings, consider using a list where each element of the list is a specific binding. A binding is just a pair: the symbol and the bound value or expression. You cannot define global variables in scheme, so you will need to pass this list as an additional parameter.

8. Using (load “FILENAME”) or ,load FILENAME inside the scheme48 interpreter allows you to load a file named FILENAME with your implementation of myinterpreter and any other helper functions.