ITEC 380 2008fall ibarland

home—info—lectures—exams—archive

hw06
Writing a Simple Interpreter

update:

1. If you turn in *all* of hw06 on Friday Dec.12, you'll get a 15% bonus to your score.
2. Otherwise, you can turn in part on Friday Dec.12, and the whole project on the last day of Finals, Dec.18 (Thu) 17:00.

   The part due Dec.12 is: all of L1 (parse, toString, eval), plus parse and toString for L2.

   To turn in For turning in during finals week, just slip it under my door. (I prefer *not* being emailed solutions, but if you must, then create a single readable file (plain-text or pdf) and send that to me [*not* a zip with many source files]. You don't need to print out any code which is was provided to you (e.g. UtilIan), if you didn't modify it.)

For this project, we'll implement a “tower” of languages (L0, L1, L2, L3, and L4), each language incorporating more features than the previous. L0 is provided for you.

• For each language, you must implement three methods:
  • parse, which turns source-code into an internal representation,
  • toString which turns internal representation back into source-code,
  and
  • eval, which actually interprets the program, returning a value (a number for L0-L2, and a number-or-function in L3).
  I recommend implementing and testing the methods in this order. See the provided test-cases, for examples. There might be other helper functions to implement as well.
• Your solution may be in Java or in Scheme (or see me, if you want to use a different language). See the comments in the provided files, for language-specific differences/nuances.
• You do not need to worry about error-checking -- we will only concern ourselves with syntactic L0 (etc.) programs.
  (As a matter of defensive programming, you might still want to add some assertions/sanity-checks in your code.)
• Use the WebCT discussion board for group questions and answers.
• This project is based on the first chapters of Programming Languages and Interpretation, by Shriram Krishnamurthi. As a result, this homework assignment is covered by the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. Although we're using a different dialect of scheme than that book, you might find it helpful to skim it.
• Turn-in instructions to be announced.

% L0 syntax:
% An Expr is one of:
Expr ::= Num | SumExpr | ProdExpr | IfZeroExpr 

SumExpr ::= {plus Expr Expr}
ProdExpr ::= {times Expr Expr}
IfZeroExpr ::= {ifZero Expr Expr Expr}

1. (20pts) L1 is just like L0, but with two additional types of expressions:

   Expr ::= … | ModExpr | IfNegExpr ModExpr ::= {mod Expr Expr} IfNegExpr ::= {ifNeg Expr Expr Expr}

   Update parse, toString (a.k.a. expr->string), and eval appropriately.

   The only method which cares what these new expressions mean (their semantics) is eval: {ifNeg Expr₀ Expr₁ Expr₂} first evaluates just Expr₀; if that value is negative, then it evaluates Expr₁ and returns its value; otherwise it evalutaes Expr₂ and returns its value. (Note how you are making sure that ifNeg short-circuits.)

   {mod a b} evaluates to³ a mod b, where the result is always between 0 (inclusive) and b (exclusive); in particular, the result is never positive if b<0. Notice that this is slightly different behavior than either Java's built-in % (which behaves differently on negative numbers), and from Scheme's built-in modulo (which only accepts integers). In Java, you can use a%b (if b>0 or a%b=0) and a%b+b (otherwise). In scheme or Java, you can use b*(a/b-floor(a/b))

   Hint: Most all the code for this problem is virtually identical to existing code. The only exception (and it's a mild one) is the eval for ModExprs, since the formula is a bit more involved.

   hw06-L1-test.ss

2. (40pts) L2 adds identifiers to L1:

   Expr ::= … | Id | WithExpr WithExpr ::= {with Id Expr Expr}

   where Id can be any series of letters and digits which isn't interpretable as a number⁴.

   Update your three methods parse, toString (a.k.a. expr->string), eval. We now need to define the semantics of {with Id E₀ E₁}:

   • Evaluate E₀, naming the result v₀.
   • Then, substitute v₀ for all free occurrences of Id inside E₁; name the result⁶ E′
   • Evaluate E′, and return that result.
   The code to make a substitution in an Expr parse-tree is reminiscent of hw03's subst-in-tree (except that a list had only two cond-branches, while Expr has around ten (most of which are similar)). For example: {with x 5 {plus x 3}} ⇒ {plus 5 3} ⇒ 8⁷.

   However, there is one wrinkle: What if E₁ contains some non-free (“bound”) occurrences of Id?
   That is, wat if E₁ contains a (nested) “{with x … …}”? In that case the inner one should shadow the outer one:
   {with x 3 {with x 5 {plus x 3}}} ⇒ {with x 5 {plus x 3}} ⇒ {plus 5 3} ⇒ 8
   Thus, when substituting, only substitute “free occurrences” of an Id in E₁, not any “bound occurrences”⁸. Think through exactly what you need to substitute, in the following examples:
   {with y 3 {with x 5 {plus x y}}} ⇒                  ⇒                  ⇒ 8
   {with y 3 {with x y {plus x y}}} ⇒                  ⇒                  ⇒ 6
   {with x 5 {with y 3 {plus {with x y {plus x y}} x}}} ⇒                                          ⇒                                ⇒                ⇒                  ⇒ 11
   (You might find it helpful to draw the parse tree, rather than staring at the flat string, especially for this last example.)

   Observe that when evaluating a (legal) L2 program, eval will never actually encounter an Id -- that Id will have been substituted out before we ever recur down to it.

   hw06-L2-test.ss

3. (40pts) L3 adds functions and function-application to our language:

   Expr ::= … | FuncExpr | FuncApplyExpr FuncExpr ::= {fun Id Expr} FuncApplyExpr ::= {Expr Expr}

   We restrict ourselves to unary functions (functions of one argument). (To think about: if we wanted to 'fake' functions of 2 arguments in L3, how could we do it?

   Just like numbers are self-evaluating, so are FuncExprs. If evaluating (an internal representation of) a FuncExpr, just return that same (internal representation of) function. We won't actually evaluate the body until the function is applied.

   In FuncApplyExpr, the first Expr had better evaluate to a function. (That is, it's either a FuncExpr, or it's an Id which gets substitued to a function value.) For example, here is a function for computing absolute value:

   {fun x {ifNeg x {times -1 x} x}}

   A funcApplyExpr represents calling a function. Here are two examples, both computing the absolute value of -5:

   {{fun x {ifNeg x {times -1 x} x}} -5} {with abs {fun x {ifNeg x {times -1 x} x}} {abs -5}}

   To evaluate a function-application {Expr₀ Expr₁}:
   • Evaluate Expr₀; call the result f. (f had better be a function-value!)
   • Evaluate Expr₁; call the result arg.
   • Substitute f's parameter with arg in f's body; call this new expression E′.
   • Evaluate E′ and return that value.
   Hey, those semantics are practically the same as with!

   Observe that our programs can now evaluate to either of two types: numbers or functions. In Java, we'll need to have a class which can represent either, as the return type for our eval.

   hw06-L3-test.ss

4. (35pts extra credit: This problem and the next are really the crux of the assignment, but due to the impending end-of-semester, it will be extra credit.)
   Deferred evaluation: L4 doesn't add any new syntax, but it is a different evaluation model which will give us more expressive semantics. Use a new file/project for L4, separate from L0-L3.

   There are two problems⁹ with the substitution approach used above: we can't make recursive functions, and it doesn't generalize to assigning to variables. We solve these problems with deferred evaluation:

   • When interpreting a program, eval will take two arguments: the program to interpret, and a list of bindings (Ids and their associated values).
   • Upon encountering an Id, we just look up its value in our list of bindings. (Recall that in L3, eval never actually reached an Id; in L4 it does.)
   • In this approach, function-application and with each introduce (exactly one) binding; in these cases we'll just add the binding to our list¹⁰ and proceed recursively.
   • For full extra credit, make sure that you can evaluate recursive functions. (This means our ‘with’ must have letrec-like semantics.)

   Note that this gives us dynamic scoping.

5. (35pts) Extra credit: static scope. Extend functions so that they include one extra piece of information: the bindings in effect when the function was declared. Be sure to make a careful suite of test-cases, to test for various ways of capturing bindings in different closures. (For example, consider the midterm's problem for testing scope.)
6. Further extra-credit options (of varying difficult, hence points):
   • Add comments to the grammar. (Make sure they nest.) (An easier version would require that even within comments, any parentheses are balanced, to leverage scheme's reader.) It's up to you whether or not you store comments in the internal representation, or discared them entirely.
   • Re-write the code for evaluating with so that it simply creates a function-application and evaluates that.
   • Generalize functions to multiple arity; generalize with so that it takes any number of id/value pairs (call it with*).
   • If you want, modify the with syntax: instead of {with Id Expr Expr}, you can use {Id = Expr ; Expr}. (Note that this still represent declaring a new variable, not mutating an existing one.)
   • Add mutation (i.e. assigning to Ids).

  eval(parse("{with x 5 {plus x 3}}"))
= eval(parse("{plus 5 3}"))
= 8

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Dec.10 (Wed)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu