C311 Assignment 5 -- More Interpreters

Due Monday, February 12, at 9 AM

Submit via email

In this assignment, like the previous one, you are asked to build a series of interpreters. Each part of the assignment should be done cumulatively, building on the interpreter in the previous part. The input to the interpreter is an expression in Scheme syntax (see the examples) so you need to extend your parser for expressions in Scheme syntax. In the end you should have just one interpreter, which is equipped to handle the test inputs from all parts of this assignment.

EOPL Exercise 5.4.1
Use the Scheme syntax for inputs to your interpreter.

> (run '((lambda (x) x) 1))
1
> (run '((lambda (x) (x 1)) (lambda (x) x)))
1
> (run '(((lambda (x) (lambda (y) (+ x y))) 1) 2))
3

EOPL Exercise 5.4.4

> (run '(let ((a 1)) (+ a 1)))
2
> (run '(let ((a 1)) (let ((b 2) (a 4)) (+ a b))))
6

EOPL Exercise 5.5.4
In addition to adding a begin form, you should also support ``multiple-bodied lambdas.'' That is, when a lambda with multiple bodies is expanded, the multiple bodies should be encapsulated within a begin form:
(lambda (v ...) e0 e1 ...)
-->
(lambda (v ...) (begin e0 e1 ...))
```
> (run '(begin 10))
10
> (run '(begin (+ 3 4) 10))
10
> (run '(begin (+ 3 4) (+ 4 5) 10))
10
> (run '((lambda () (+ 3 4) 10)))
10
```
EOPL Exercise 5.5.1
You don't have to alter the ``let'' clause, since the handling for let has been subsumed by the syntax expander: In fact, there shouldn't even be a let clause in your interpreter at this point. You may choose whatever ``unspecified'' value you like for the return value of a set! expression: In the examples below, set! returns the symbol unspecified.
```
> (run '(let ((a 1)) (set! a 5)))
unspecified
> (run '(let ((a 1)) (begin (set! a 10) (+ a 10))))
20
> (run '(let ((x 3))
           (let ((f (lambda () (set! x (add1 x)) 9)))
              (begin (f) (f) x))))
5
```

EOPL Exercise 5.5.5

> (run '(define x 3))
unspecified
> (run '(+ x 1))
4
> (run '(define x 5))
unspecified
> (run 'x)
5
> (run '(begin (set! x 6) x))
6
> (run '(define even 
           (lambda (n) 
              (if (zero n) 
                  1 
                  (odd (sub1 n))))))
unspecified
> (run '(define odd 
           (lambda (n) 
              (if (zero n) 
                  0 
                  (even (sub1 n))))))
unspecified
> (run '(even 6))
1

EOPL Exercise 5.5.2
Convert the representation of your environments into a ``ribcage'' representation if you haven't already. Then implement this exercise.

Submission

Write your answers to the exercises in a file (with comments, following the proper indentation rules), and send that file to

c311@lakshmi.cs.indiana.edu

with the subject line

5

Assuming you've saved your homework in the file ``asgn.ss'' in the current directory, one way to submit is with the command:

Mail -s "5" c311@lakshmi.cs.indiana.edu < asgn.ss

If you use the define-record stuff, include the expression

(load "record.ss")

in your submission.

Back to the c311 page

ehilsdal@cs.indiana.edu