►Principles of Programming Languages
▼Assignments
•2 — Static Distance, Simple Interpretation
7.7.0.3
    ← prev  up  next → 

2 — Static Distance, Simple Interpretation

Due Tuesday, 21 January, 6:00pm Wednesday, 22 January

The purpose of this assignment is to enhance your understanding of the principles of parsing, lexcial scope, and interpretation with a simple example.

Delivery Deliver your solutions in a folder called 2 with the following organization:

Programming Task Here is a specification of the language of variable expressions:Variable expression is the name used in pre-college algebra text books, and you’re essentially implementing a homework-solving machine for 7th and 8th graders.

    An VExpr is one of:

     - a Var

     - an Int

     - a JSON array of the shape [VExpr,"+",VExpr]

     - a JSON array of the shape [VExpr,"*",VExpr]

     - a JSON array of the shape [Decl1,...,Decln,VExpr] for n >= 0

    

    A Decl is

     - a JSON array of the shape ["let", Var, "=", VExpr]

    

    An Int is a Integer.

    

    A Var is a String.

Nothing else is a VExpr.

The let expressions are inspired by Rust and JavaScript’s variable declarations. In a sequence of Decls, every let variable definition is visible in all VExpr expressions to its right in the same JSON array. For example,

    [["let","x","=",5],

     ["let","y","=",["x","+",1]],

     ["x","*","y"]]

is a meaningful VExpr. It declares and initializes two variables, "x" and "y", and then multiplies the two. Due to the scoping rule for variable declarations, the initialization of "y" may use "x" and both variables may be used in the expression following the two variable declarations.

Your programming tasks are:

  • Develop a data representation for VExprs.

    Design the program parse, which consumes a JSON (representation of) a VExpr and produces an internal data representation.

  • Design sd. The program consumes (the data representation of) a VExpr and replaces every variable reference with a pair of integers. The first integer counts how far away the variable’s declaration is in terms of surrounding Decl JSON arrays, the second one how far from the left the declaration is within this array. Both counts start at 0. A variable without declaration is replaced by itself.

    Design the program unparse, which consumes the result of sd and produces a JSON (representation of) a VExpr with lists of natural numbers in places of variable references.

  • Design the program interpreter, which consumes a VExpr and produces its value, an integer via a substitution/replacement process (see 3 — Scope, Compilation).

    A variable reference in VExpr stands for its definition. As with ordinary definitions, this means that you may replace every occurrence of a variable with its definition. An interpreter will replace every variable with its value.

    Hence, if the interpreter encounters a variable, say "x", we know that there is no declaration for the variable. Why? In this case, the interpreter signals an error by producing a JSON string of the form "variable x undeclared".

    Hint 1 A substitution interpreter employs generative recursion. Whenever a variable is replaced, the interpreter recurs on an expression that is not a structural component of the given one.

    Hint 2 Due to let arrays, your interpreter has to substitute several variables simultaneously.

    Hint 3 Also due to sequences of variable declarations, your program may have to substitute variables with themselves, not just with integers.

Testing Task Write the test harnesses xsd and xinterpreter for your sd and interpreter programs, respectively.

Create three tests for xsd and xinterpreter each. Place them in SDTests/ and ITests/, respectively. A test consists of two files: N-in.json and N-out.json for N in {1, 2, 3}. An input file consists of a single VExpr. An output file for xsd is like a VExpr with all Var references replaced by a JSON array of two natural numbers. An output file for xinterpreter is a JSON integer.

Recall JSON: Simplicity and Complexity.

    ← prev  up  next →