►Principles of Programming Languages
▼Assignments
•4 — Interpreting Functions
7.7.0.3
    ← prev  up  next → 

4 — Interpreting Functions

Due Tuesday, 04 February, 6am

The purpose of this assignment is to understand the interpretation of statically scoped functions and conditional expressions.

Delivery Deliver your solutions in a folder called 4 in your github repo with the following organization:

  • xinterpreter as specified in the testing task below.

  • ITests/ as specified in the testing task below.

  • Other/, which contains the solutions to the programming tasks.

Do read Make in case you need us to build your executables.

Programming Task

Step One Design a parser and an environment-based This is not a request to adapt your static-distance interpreter. interpreter for the language of FVExpr. You may wish to adapt existing code.

The JSON grammar for this language is as follows:

    An FVExpr is one of:

     - a Var

     - an Int

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

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

     - a JSON array of the shape [FDecl,...,FDecl,FVExpr]

       all variables declared in one sequence are pairwise distinct

     - a JSON array of the shape ["fun*",VarList,FVExpr]

     - a JSON array of the shape ["call",FVExpr,FVExpr,...,FVExpr]

       as in all mainstream languages, the first and required

       FVExpr is to evaluate to a function value

     - a JSON array of the shape ["if-0",FVExpr,FVExpr,FVExpr]

    

    An FDecl is

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

     - a JSON array of the shape ["let", Var, "=", ["fun*",  VarList, FVExpr]FVExpr]

    

    A VarList is a JSON array of the shape [Var, ...,Var]

       all variables declared in one sequence are pairwise distinct

Nothing else is a FVExpr.

Recall that "fun*", "call", and "if-0" are keywords.

The lexical scoping rules for these expressions are defined as follows:

The meaning of "fun*" and "if-0" expressions are as discussed in class. The first is a function of as many arguments as there are Vars. The second is the conditional expression that uses 0 as the only true value. The interpretation of all other expressions is adapted mutatis mutandis.

Stop! Does your chosen programming language have an "if-0"-like expression?

If the given program evaluates to a function value, the interpreter returns the String "closure"; otherwise a regular answer is a number and the interpreter returns it.

Step Two Having only two primitive operations is boring. Programming languages instead define a standard prelude, which is really just an initial environment. Then, instead of enumerating the operations in the grammar, we allow arbitrary Vars in binary positions:

    An FVExpr is one of:

     ...

     - a JSON array of the shape [FVExpr,Var,FVExpr]

       where the first FVExpr is not a keyword

     ...

The semantics of such a Var must be defined in the standard prelude.

For now, allow "+", "*", and "^" (for exponentiation with non-negative exponent argument). The standard prelude assigns an implementation-dependent data representation to the conventional meaning of these three operations.

Hint In functional languages you may use functions to represent such prelude functions. In object-oriented languages that don’t have anonymous function expressions, you may wish to use objects after looking up the command pattern (or recall it from OOD).

Step Three Ensure that your interpreter does not leak. In particular, it should explicitly catch all possible errors and it should evaluate the sub-expressions of a function application and binary operation strictly from right to left.

Here are the error messages your interpreter should issue:

  • "variable s undeclared" (for any String s)

  • "arithmetic error" (number expected)

  • "number of arguments does not match number of parameters"

  • "closure or primop expected" "function application (closure expected)"

These error messages are additional results that your interpreter may return.

Testing Task Write the test harness xinterpreter for your interpreter programs.

Create ten tests for xinterpreter. Place them in ITests/. A test consists of two files: N-in.json and N-out.json for N in [0 .. 9]. An input file in ITests contains a single FVExpr as modified and constrained in the programming task above. An output is an Answer, which is either a number or a JSON string.

Recall JSON: Simplicity and Complexity.

    ← prev  up  next →