►Principles of Programming Languages
▼Assignments
•5 — Simple Mutable Objects
7.7.0.3
    ← prev  up  next → 

5 — Simple Mutable Objects

Due Tuesday, 11 February, 6am

The purpose of this homework problem is to understand simplistic but mutable objects, as commonly found statements in a modern language, via a store-passing.

Delivery Deliver your solutions in a folder called 5 in your github repo:

  • 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.

Maintenance Task Before you get to your programming task, make sure that the prelude is realized as the first and basic part of the general environment. What this means in general is that every function can be used as an infix primitive operation and every primitive operation can be used as a function.

Programming language researchers refer to this idea as uniformity. Uniformity greatly simplifies implementations. Whether programmers like uniformity is an open question.

Programming Task Step One Design a parser and an interpreter for the language SFVExpr. The JSON grammar is a revision of the grammar for FVExpr in the following parts:

  • the primitive operation form which may now take a potentially empty sequence of argument expressions to the right of the operator position:

        - a JSON array of the shape [SFVExpr,Var,SFVExpr, ..., SFVExpr] where the

          first SFVExpr is not a keyword

    The arity of the pure arithmetic operators remains 2; a violation causes a failure. Your interpreter must still signal a "number of arguments" error.

  • the declaration block, which once again permits arbitrary expressions on the right side:

         - a JSON array of the shape [SFVDecl,...,SFVDecl,SFVExpr],

           all variables declared in one sequence are pairwise distinct

        

        A SFVDecl is ["let", Var, "=", SFVExpr].

        

The lexical scoping rules for these expressions are same as for FVExpr.

Your interpreter must use store-passing style to determine the meaning of all expressions; it must not use imperative assignments. The values of all variables—declared ones or function parameters—must be allocated in the store. Furthermore, the interpreter must accept an optional argument that permits client code to receive either the answer value of the given program or the store.

The interpretation of SFVDecl sequences starts with allocating locations for all variables, initialized to 0, and extending the environment with these newly allocated locations. Then the interpreter determines the value of each right-hand side expression, in the given order, and, when evaluated, stores the value at the corresponding location. Finally, the interpreter evaluates the body of the declaration block.

Step Two Once you have a store-passing interpreter and it passes the existing test suite, you must adjust the interpretation of primitive operations from the prelude—"+", "*", and "^"—and add three new ones. Specifically, all primitive operations must accept the store and must produce both the value they compute and the potentially modified store.

When you have adjusted the operations in the existing prelude to work with stores, add the following three new operations:

  • @, which consumes one argument value, allocates a cell store location, sticks the given value into the store at this location this cell, and returns a cell. A cell value is distinct from both Ints and function values. Its only useful content is the newly allocated location.

  • !, which consumes one argument value—a cell—and retrieves the current value in the location specified by this cell.

  • =, which consumes two argument values—a cell and an arbitrary value—sticks this second value into the location specified by this cell, and returns the value that used to be at this location.

You may wish to think of @ as an object constructor, ! as a getter, and = as a setter.

Use natural numbers to represent store cells locations..

Your store-passing interpreter will use the four kinds of pre-existing error messages, but we reformulate the one for arithmetic error to "primop domain error", which is more appropriate given the new cell values and operations. You may also wish to experiment with a division operation in the prelude.

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

Create fifteen tests for xinterpreter. Place them in ITests/. A test consists of two files: N-in.json and N-out.json for N in [0 .. 14].

An input file in ITests contains a single JSON array of the shape

  -- ["value", SFVExpr]

     demand the resulting value

  -- ["store", SFVExpr]

     demand the resulting store

An output file contains a single JSON array of one of the following shapes:

  -- ["value",SAnswer]

     a value or an error string rendered as an answer

  -- ["store",[SAnswer,...,SAnswer]]

     a store--without prelude--rendered as an array

where SAnswer is a rendering of a stored value:

  • an Int is rendered as itself;

  • a primop value is rendered as the JSON string "primop";

  • a function value is rendered as the JSON string "closure";

  • a cell containing location l is rendered as ["cell", l].

The embedded store lists the values in the store at location N+1, N+2, etc. if the prelude occupies locations 0 thru N.

Recall JSON: Simplicity and Complexity.

    ← prev  up  next →