ITEC 380 2011fall ibarland

home—lectures—exams—hws—breeze (snow day)

hw09
Interpreting N
project

Due Dec.09 (Fri) 23:59

Over the course of several homeworks, we'll implement a “tower” of languages (N0, N1, …, N6) each language incorporating more features than the previous. N0 is provided for you. You may write your interpreter in either in Java or in scheme (besides N1, which you must implement in both scheme and Java).

• 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 N0-N2, and a number-or-function in N3).
  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 Racket (or see me, if you want to use a different language). (The exception is N1, which you must implement in both Racket and Java.)
• You do not need to worry about error-checking -- we will only concern ourselves with syntactic N0 (etc.) programs.
  (As a matter of defensive programming, you might still want to add some assertions/sanity-checks in your code.)
• Use the Desire2Learn 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.

1. (35 pts: This problem and the next are really the crux of the assignment.)
   Deferred evaluation: N5 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 N5, separate from N0-N4. Turn in a full set of files on-line; for hardcopy only turn in parts of code that changed from your last turnin or posted solution (namely, eval and new test cases, but not parse or toString).

   There are two problems¹ with the substitution approach used in N2-N4: we can't make recursive functions, and it doesn't generalize to assigning to variables. We solve these problems with deferred substitution:

   • When interpreting a program, eval will take two arguments: the program to interpret, and a set of bindings. A binding is just an Id and its associated value; a set of bindings (an environment) might be implemented with an association list or a java.util.Map<IdExpr,ValExpr>.
   • In this approach, function-application and let no longer do any substitution — instead, each introduce (exactly one) new binding and proceed recursively².
   • Upon encountering an Id, we just look up its value in our list of bindings. (Recall that in N2, eval never actually reached an Id; in N4 it does.)
   • For full credit, make sure that you can evaluate recursive functions.
   • You should not need to be doing any parse-tree-substitutions any more (though you can if you want, to temporarily address the note below). Note that in N6, no substitutions will be allowed.

   Your test cases should include a recursive function, as well as the example below. Also, since eval now takes an extra argument, that suggests three to four check-expects with various environments (lists of bindings):

   • an empty environment;
   • an environment with no necessary bindings;
   • an environment where some of the bindings are needed;
   • an environemnt where some of the bindings will be shadowed in the expression.

   A step sideways: This algorithm as described lets us add recursive functions, but it also doesn't handle some expressions that N4 did! For example, let make-adder = func(m, func(n, (n plus m)) ) in <<make-adder(3)>4>; gives an error "unbound identifier: m" if no substitution has been done, however <func(m, <func(n, (n plus m))(3)>)(4)> does still work just fine(!). The problem will be fixed in N6: in the first example, <make-adder(3)> returns a function whose body involves m and n, but not the binding of m to 3. We'd need return the function and its bindings.

   Note that this gives us dynamic scoping (which we'll mention in class):

   let m = 100 in let addM = func(x, (x plus m)) in ((let m = 5 in <addM(3)>;) plus (let m = 4 in <addM(3)>;)) ; ;

   evaluates to 15, not 206.

2. (Extra credit: 30pts) N6: Implement static scope.
   • You'll want to modify your function-structures 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 lecture on ways of using let* to effectively implement objects, classes, and inheritance.)
   • When evaluating a function-application, use the bindings in effect back when that function was declared, for its free variables.
   • You should not be doing any substitution.
   • For extra credit, make sure recursive functions work. This is a bit tricky, since their environment (closure) needs to include themselves, but when you're evaling a func-expr you don't yet have its associated name, hmmm. Just after the func-expr is created then you'll want to go in and set³ its environment to include itself.
   • To think about: Hmm, when we first parse our expression, we'll create function-expressions, but (since we're not eval'ing) we don't have any bindings right then. Only later, when we eval a function, will we actually know about any bindings (since that call to eval was given a list of bindings)….
   Be sure to make a copy of your N5 project files before starting N6.
3. Further extra-credit options (of varying difficulty):
   • Add comments to the grammar and parser. Make sure they nest. It's up to you whether or not you store comments in the internal representation, or discard them entirely⁴.
   • Re-write the code for evaluating let so that it simply transforms it into a function-application, and evaluates that.
   • Generalize functions to multiple arity, and/or generalize let so that it takes any number of id/value pairs. (Really this would be like scheme's letrec, since N4 allows recursion.)
   • If you want, modify the let syntax: instead of let id = Expr in Expr;, you can use Id = Expr ; Expr ; . (Note that this still represent declaring a new variable, not mutating an existing one.) Your programs now look like procedural programs.
   • Add mutation (i.e. assigning to Ids): Id ← Expr;. (If you want to use mutation in your underlying scheme implementation, you can use set-first! and set-struct-field!⁵. You can also think about how you might try implementing mutation in N6 without actually using mutation in your underlying program.)
   • Once we have assignment, add the equivalent of scheme's begin. (You might use “{” and “}” to delimit such a “block” of statements; you now have implemented all the procedural concepts of a Java or Python interpreter, including first-class functions! And as seen in lecture, you also could write superficial transformations to get most of an object system as well.)

home—lectures—exams—hws—breeze (snow day)

©2011, Ian Barland, Radford University Last modified 2011.Dec.07 (Wed)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu