Programming Languages (CS 328) Homework 2 Computer Science and Engineering Out: 2000-03-17 Indian Institute of Technology Bombay Due: 2000-04-20

Note: Some of the experimental work in this homework will be needed in the next homework.

1. Here is the abstract syntax of FL!

E ::= L | I | (unary U E) | (binary B E_{1} E_{2})
       | (if E_{0} E_{1} E_{2}) | (vlambda I E) | (call E_{1} E_{2})
       | (ref E) | (^E) | (:= E_{1} E_{2})

(a) Completely specify the semantic domains for writing standard semantics.

(b) Complete the design of the store and its accessors and write down standard semantics for the following productions: (ref E), (^E), and (:= E_{1} E_{2}).

2. Here are the abstract syntax for FLCPS and FLC:

 C ::= A | (C A) | (if I C_{1} C_{2})
 A ::= I | L | (λ I C) | (prim P I^{∗})

                                       E ::= I | L | (unary U E) | (binary B E_{1} E_{2})

                                          | (if E_{0} E_{1} E_{2}) | (lambda (I) E) | (E_{1} E_{2})

Show by structural induction that the CPS transformation described in class leads to an expression that adheres to the abstract syntax of FLCPS.

3. Write in Scheme a front-end for FLC. Assume that literals are integers and booleans, U are the unary operators not and unary minus, and B is chosen from +, -, *, /, and, and or. Your program should read a source file, construct an abstract syntax tree in memory, and print it out to a file in a suitable structured format. (See the Friedman, Wand and Haynes book for help on writing such front-ends usign tagged records in Scheme.)

4. An interpreter for FLCPS can be written as a typical recursive eval function having a case statement for each syntactic production rule of FLCPS. Let the ‘handler’ function for the application (C A) be called eval-apply. (See the Friedman, Wand and Haynes book for examples of such interpreters.)

Consider an execution of eval with an arbitrary FLCPS program as input, such that the execution terminates. At any point of time during this execution, eval may call eval-apply which in turn may call eval. Other ‘handlers’ will also be called in general.

Show that the number of eval-applys ever to appear on the “call-stack” of eval at any given time will be bounded by a function of the size of the abstract syntax tree of the input code. The smaller your function the better.