Due date: 10/11 @ 5:00 pm

The goal of this problem set is to modify the interpreter for the kernel of our C-like language so that it can cope with procedures (functions).

Use the Pretty Big language and require the EoPL language. Use the functional subset plus exceptions.

---

Add procedure declarations to the small programming language of Problem Set 3:

 Block is: { Declarations* Statement+ }

 Declaration is one of: 
 -- (Type Variable = Expression) 
 -- (Type Variable (Parameter*) Block)

 Type is one of: 
 -- bool 
 -- int 

 Parameter is: (Type Variable)

 Variable is: alphanumeric sequence of characters 

 Expression is one of: 
 -- Variable 
 -- Number 
 -- (Expression + Expression) 
 -- (Expression > Expression) 
 -- (Variable Expression*)

 Statement is one of: 
 -- (Variable = Expression) 
 -- (if Expression Block else Block)
 -- (while Expression Block)
 -- (return Expression)
    Constraint: a return-statement may occur 
    only inside of a procedure body

The new form of declaration introduces a recursive call-by-value procedure (function); an assignment statement to its parameters has no visible effect outside of the extent of the procedure call. The procedures are visible following their declaration within their declared block; a procedure declaration does not shadow a variable declaration for the same name and vice versa. A procedure call -- the new kind of expression -- consists of the procedure name followed by as many expressions as the procedure has parameters. Finally, a procedure call must produce its result through the execution of a return statement. Conversely, a return statement stops the evaluation of a procedure. Thus,

 (int f () {
   (return 3)
   (return 5)
  })

always returns 3; the second return statement is ignored.

Here is one simple program (block) in this language:

  { (int x = 10)
    (int sum = 0)
    (int plus( (int x) (int y) ) {
      (int z = (x + y))
      (return z)
      })
    (while (x > 0) {
      (sum = (sum + x))
      (x = (plus x -1))
      })
    }

Problem 1:

Adapt your algebraic datatype representation from Problem Set 2(1) to the above grammar.

Develop a procedure for multiplying natural numbers (integers greater or equal to 0) in the language.

Problem 2:

Revise your definition for free and bound variables in this language. Assume block-structured, lexical scope.

Revise your environment datattype so that it maps symbols to locations and symbols to procedures. Why is this easy? If you had implemented these datatypes in your favorite programming language, would it have been as easy?

Design a store datatype, which is a finite function from Locations to Values. It has all the operations of the familiar environmental datatype plus one new function:

 
 
;; type Location = NaturalNumbers 

;; type Value 

;; type Store

;; store.mt : Store
;; the empty store 

;; store.update : Store Location Value -> Store
;; associate a new value with an existing location 

;; store.apply : Store Location -> Value 
;; look up the value at the given location 

;; Store Value ->* Location Store 
;; 1. determine a location L in S that is not in use 
;; (for example, one more than the current maximum)
;; 2. create a store that associates L with V
(define (store.next+allocate S V) ...)

;; store.plain : 
;;  Store -> (Listof (list Location Value))
;; present the given environment as an association 
;; list between symbols and plain Scheme values 
 

The notation ->* Value Store denotes a function that returns two values: a Value and a Store.

Problem 3:

Design an interpreter for this language. The interpreter consumes a program (as an AST if you weren't in the mood to design a parser). The program is closed (contains no free variables) and is type correct (whatever this exactly means). It produces a plain association list that associates all allocated locations with a Scheme value.
Requirements:

1. The interpreter continues to assume that types don't matter and that everything is correct (whatever that means).
2. The interpreters maintain an environment for procedures that is separate from the environment for denoted values.
3. In addition to two environments, the interpreters consumes a Store. The regular environment now maps variables to locations, which are allocated on declaration and on procedure application. The store maps these locations to values.
4. The interpreter returns Stores in addition to other results as needed.
5. Use Scheme's exceptions (see HelpDesk), i.e., raise and with-handlers, to implement the return statement. With this you may enforce that a procedure call is ended through a return statement at run-time.