Homework Assignments

Since this problem doesn't involve writing any Scheme functions, use Scheme's multiline comments to comment out your entire file. 

For example:

#|
Part A
(car (cdr x)) = b

...

|#

Note: Some implementations of Scheme return the empty list i.e. () for false, but they should all understand #f.

Fill in the blanks in the following transcript: (In other words, fill in the values returned by each of these expressions.)

Work these problems first without using the interpreter. Be sure to check your answers afterwards using Scheme.  Please include both your initial guesses and the results of evaluating the expressions in scheme. If they are different, note the reasons why your initial guess was incorrect.

Part A - (15 minutes)

    > (define x '(a b ((3) c) d))
    > (car (cdr x))

    > (caddr x)

    > (cdaddr x)

Part B - (15 minutes)

    > (define x1 '(a b))

    > (define x2 '(a))

    > (define x3 (cons x1 x2))

    > x1

    > (eq? x3 (cons x1 x3))

    > (eq? (cdr x3) x2)

    > (eq? (car x1) (car x2))

    > (cons (cons 'a 'b) (cons 'c '()))

    > (cons 1 (cons 2 3))

Since this problem doesn't involve writing any Scheme functions, use Scheme's multiline comments to comment out your file.

This problem requires Lecture 4.

Part A
Consider the following definitions without entering them into an interpreter just yet.

(define f
  (lambda (x)
     (lambda (y)
       (y x))))

(define g (f (list 1 2 3 4 5)))

How would you describe f? What would you expect to be passed to it?

How would you describe g? What would you expect to be passed to it?

What would (g display) return? How about (g length)? (g 5)?

Verify your answers by typing this in and playing with the functions f and g.

Please don't cheat and plug the code into the interpreter since you'll get a great deal of understanding out of trying it out by yourself.

Part B
Consider two or three languages you know or for which you can find documentation. What restrictions, if any, are imposed on procedures that keep them from being first class? Is it possible to create anonymous procedures (ones without names bound to them)?

I consider questions like this to be at the heart of this course. You should ask yourself these kinds of questions as you read and study. Questions like this one will appear on the exams.

This problem requires Lecture 4 and Lecture 5.

Part A involves writing your first function that is autograded. Make sure it is not commented out. Parts B and C should be in block comments.

Part A
Write the following variable arity functions to handle either 2 or 3 arguments. If you use built-in functions (like +), you may only pass them 2 arguments at a time. Hint: try using if and/or cond.

• sum
  For example:

  > (sum 1 2)
  3
  
  > (sum 3 4 5)
  
  
  Notice:  Uninitialized string offset:  2 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 115
  
  12

• even-parity    (true if there are an even number of 1s passed to it, false if there are an odd number of 1s)
  For example:

  > (even-parity 1 0)
  #f
  
  > (even-parity 1 0 1)
  #t

YOU MUST NAME YOUR FUNCTIONS sum AND even-parity

Part B
Translate the following let expression into the equivalent application of a lambda expression to operands:

    (let ((a 3)
          (b (+ 2 3)))
      (+ a b))

Type both this let expression and your equivalent expression using lambda into the interpreter to verify that they work the same way.

Part C
Most languages have features that are just syntactic sugar. Pick a language you like to work with (C++, Java, etc.) and name as many features that you can think of that are syntactic sugar. What other features in the language are they equivalent to?

This problem requires Lecture 6 and book sections 1.1-1.2

Exercise 1.1, p.5 - (10 minutes)
Write a syntactic derivation that proves (-7 . (3 . (14 . ()))) is a list of numbers.

You should find syntactic derivations to be similar to those you might have done in CS 236 or CS 252.

Exercise 1.2, p.7 - (20 minutes)
Rewrite the <datum> grammar without using the Kleene star or plus.

You can use the following modified grammar for this exercise since the definition of list on page 6 is does not use the dot-paren notation:

   <list>         ::=  () | ( <datum> . <list> )   
   <dotted-datum> ::=  ( {<datum>}+ . <datum> )   
   <vector>       ::= #( {<datum>}* )   
   <datum>        ::=  <number> | <symbol> | <boolean> | <string>   
   |  <list> | <dotted-datum> | <vector>   
 

Hint: introduce new non-terminals for the Kleene-star parts if you need to. Please show the new derivation with your new BNF. The data type described here, <datum>, is the syntax of Scheme. This is a good example of how syntax and data type specifications are related.

Then indicate the changes to the following derivation that are required by this revised grammar.

<list>
=> (<datum><datum><datum>)
=> (<boolean><datum><datum>)
=> (#t <datum><datum>)
=> (#t <dotted-datum><datum>)
=> (#t ({<datum>}+ . <datum>) <datum>)
=> (#t (<symbol> . <datum>) <datum>)
=> (#t (foo . <datum>) <datum>)
=> (#t (foo . <list>) <datum>)
=> (#t (foo . ()) <datum>)
=> (#t (foo . ()) <number>)
=> (#t (foo . ()) 3)

Exercise 1.5, p.14 - (20 minutes)
This version of list-of-numbers? works properly only when its argument is a list. Extend the definition of list-of-numbers? so that it will work on an arbitrary Scheme <datum> and return #f on any argument that is not a list.

To save you some typing, here is the original version of the list-of-numbers? function, which you can copy and paste into your editor:

(define list-of-numbers?
(lambda (lst)
(if (null? lst)
#t
(and (number? (car lst))
(list-of-numbers? (cdr lst))))))

This problem requires Lecture 6 and book section 1.2.

Exercise 1.15, problems 1-5, p.24-25 - (60 minutes)
Here's a whole plate full of Scheme functions for you to define. You'll need lots of practice writing Scheme functions to get through this class. Here's a start. See Exercises 1.16 and 1.17 if you want more practice.

1. (duple n x) returns a list containing n copies of x.

	> (duple 2 3)
	(3 3)
	> (duple 4 '(ho ho))
	((ho ho) (ho ho) (ho ho) (ho ho))
	> (duple 0 '(blah))
	()

2. (invert lst), where lst is a list of 2-lists (lists of length two), returns a list with each 2-list reversed.

	>(invert '((a 1) (a 2) (b 1) (b 2)))
	((1 a) (2 a) (1 b) (2 b))

	> (filter-in number? '(a 2 (1 3) b 7))
	(2 7)
	> (filter-in symbol? '(a (b c) 17 foo))
	(a foo)

4. (every? pred lst) returns #f if any element of lst fails to satisfy pred, and returns #t otherwise.

	> (every? number? ' (a b c d 3 e))
	#f
	> (every? number? '(1 2 3 5 4))
	#t

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

5. (exists? pred lst) returns #t if any element of lst satisfies pred, and returns #f otherwise.

	> (exists? number? '(a b c 3 e))
	#t
	> (exists? number? '(a b c d e))
	#f

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

YOU MUST NAME YOUR FUNCTIONS WITH THE SAME NAMES THEY HAVE IN THE BOOK (i.e., duple, invert, filter-in, every?, and exists?).

Debugging Tip: DrScheme has a trace facility that will display when a function is called, what its parameters were, and what its return value was. The syntax for turning on tracing for a particular function is (trace <function>). So, for example, you could turn on debugging for your duple function by typing (trace duple). You have to explicitly turn on tracing for each function you want to trace. The (untrace <function>) operator will likewise turn tracing off for a particular function.

This problem requires Lecture 7 and book section 1.2.

Exercise 1.15, problems 6-9
Exercise 1.16, problem 2, p.25-26 - (60 minutes)

Define, test, and debug the following procedures. Assume that s is a symbol, n is a nonnegative integer, lst is a list, v is a vecotr, los is a list of symbols, vos is a vector of symbols, slist is an s-list, and x is any object, etc. Also assume that pred is a predicate, that is, a procedure that takes any Scheme object and returns either #t or #f. Make no other assumptions about the data unless further restrictions are given as part of a particular problem. For these exercises, there is no need to check that the input matches the description; ofr each procedure, assume that its input values are members of the specified set.

Exercise 1.15, problems 6-9
6.(vector-index pred v) returns the zero-based index of the first element of v that satifies the predicate pred, or #f if no element of v satisfies pred.

	> (vector-index (lambda (x) (eqv? x 'c)) '#(a b c d))
	2
	> (vector-ref '#(a b c)
		(vector-index (lambda (x) (eqv? x 'b)) '#(a b c)))
	b

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

7. (list-set lst n x) returns a list like lst, except that the n-th element, using zero-based indexing, is x.

	> (list-set '(a b c d) 2 '(1 2))
	(a b (1 2) d)
	> (list-ref (list-set '(a b c d) 3 '(1 5 10)) 3)
	(1 5 10)

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

8. (product los1 los2) returns a list of 2-lists that represents the Cartesian product of los1 and los2. The 2-lists may appear in any order.

	> (product '(a b c) '(x y))
	((a x) (a y) (b x) (b y) (c x) (c y))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

9. (down lst) wraps parentheses around each top-level element of lst.

	> (down '(1 2 3))
	((1)(2)(3))
	> (down '((a)(fine)(idea)))
	(((a))((fine))((idea)))
	> (down '(a (more (complicated)) object))
	((a)((more (complicated)))(object))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

Exercise 1.16, problem 2
2. (swapper s1 s2 slist) returns a list the same as s-list, but with all occurances of s1 replaced by s2 and all occurances of s2 replaced by s1.

	> (swapper 'a 'd '(a b c d))
	(d b c a)
	> (swapper 'a 'd '(a d () c d))
	(d a () c a)
	> (swapper 'x 'y '((x) y (z (x))))
	((y) x (z (y)))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

To test these procedures, at the very minimum try all of the given examples. Also use other examples to test these procedures, since the given examples are not adequate to reveal all possible errors.

If the operations involve lists, you must process them recursively as lists without converting them to vectors.

Hint: swapper is just a bidirectional version of subst, so structure it the same way.

YOU MUST NAME YOUR FUNCTIONS WITH THE SAME NAMES THEY HAVE IN THE BOOK (i.e., vector-index, list-set, product, down, and swapper).

This problem requires Lecture 8 and book section 1.2.

Part A - 'union' - (40 minutes)
This function will take two lists and returns a third list which is the union of the elements of the two lists. Be sure the final list has no duplicate elements. The elements in the final list may be in any order, so for the first example your function may return either (a b) or (b a).

> (union '() '(a b a))
  (a b)

> (union '(x y 7) '(7 z x w))
  (x y 7 z w)

Hint: You may find it useful to first define a function that removes duplicate elements from a list. Use that function it in the definition of union.

You may find the function member helpful.  The syntax is:(member x lst).  If x is in lst, member returns a list containing the first occurence of x and all the elements after it.  If x is not in lst, member returns #f.  (i.e.: (member 'a '(c b a b c a)) returns the list (a b c a))

These two problems together explore higher-order functions and the power of functional languages.

Part B - 'prod' - (10 minutes)
Write a function called prod that takes a list of numbers and returns their product. (This should be easy by now.) 

Part C - 'fold' - (20 minutes)
If we wanted to also define a function that summed a list of numbers, we could do that as well, but perhaps a higher-order function (an abstraction) would do the job in a more general way. Write a function called fold that generalizes prod. Your function should take an operator, a base number (what you return for an empty list-- the identity for the operator), and a list as arguments. For example, to sum a list of numbers with fold, you would make a call in scheme as:
(fold + 0 '(1 2 3 4 5))
For the product of a list of numbers, you would make a call in scheme as:
(fold * 1 '(1 2 3 4 5))

Try out your fold function by rewriting prod using it.

What does the following code do?
(fold + 0 (fold append '() '((3 1 2) (3 4 5) (3 5 6))))
Try to answer without running the code, then verify your answer.

YOU MUST NAME YOUR FUNCTIONS union, prod, fold.

This problem requires Lecture 9 and book section 1.3.

Exercise 1.19, p.31 - (50 minutes)
Write a procedure free-vars that takes a list structure representing an expression in the lambda calculus syntax given above and returns a set (a list without duplicates) of all the variables that occur free in the expression. Similarly, write a procedure bound-vars that returns a set of all the variables that occur bound in its argument.

See the help page. The concept of free and bound variables is an important one in programming languages. Use your union function to return a list without duplicates.

For instance, given

(define exp '(lambda (x)
               ((lambda (z) (x y))
                (lambda (y) y))))

your answers should be some permutation of the correct answer (i.e.: both '(x y) and '(y x) are valid)

    > (bound-vars exp)
    (x y)

    > (free-vars exp)
    (y)

YOU MUST NAME YOUR FUNCTIONS WITH THE SAME NAME THEY HAVE IN THE BOOK: free-vars, bound-vars.

Exercise 1.27, p.34 - (10 minutes)
In the following expressions connect each variable reference to its associated formal parameter declaration.

	(lambda (x)
		(lambda (y)
			((lambda (x)
				 (x y))
			x)))

	(lambda (z)
		((lambda (a b c)
			(a (lambda (a) (+ a c)) b))
		(lambda (f x)
			(f (z x)))))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

 

(lambda (x)
  (x (lambda (x) x)))

your answer should be

(lambda (x.1)
  (x.1 (lambda (x.2) x.2)))

This part will not be autograded, so please comment it out to avoid any errors with the submit script..

This problem requires Lecture 9 and book section 1.3.

Exercise 1.31, p.37 - (90 minutes)
see help page. The idea of lexical addresses is in interesting one. This problem requires that you use recursion and auxiliary variables to keep track of depth.

Consider the subset of Scheme specified by the BNF rules

<expression> ::= <identifier>
	     ::= (if <expression><expression><expression>)
	     ::= (lambda ({<identifier>}*) <expression>)
	     ::= ({<expression>}+)

Write a procedure lexical-address that takes any expression and returns the expression with every variable reference v replaced by a list (v :d p), as above. If the variable reference v is free, produce the list (v free) instead.

	> (lexical-address '(lambda (a b c)
		      	(if (eqv? b c)
		       	 ((lambda (c)
			   	(cons a c))
			 	a)
				b)))
		(lambda (a b c)
  			(if ((eqv? free) (b : 0 1) (c: 0 2))
    				((lambda (c)
        				((cons free) (a : 1 0) (c : 0 0)))
     					(a : 0 0))
   					 (b : 0 1)))

Get help early!

YOU MUST NAME YOUR FUNCTION lexical-address.

This problem requires Lecture 10, Lecture 11, and book section 2.2.

If you are using mzscheme, make sure to add the following line to your code:

(load "/users/ta/cs330ta/eopl.scm")

Part A - (20 minutes)
The implementation of bintree in Section 2.2.1 does not include empty trees. Extend the definition of bintree to support empty trees. Modify the leaf-sum function on page 46 as well to handle this new variant. Make sure to test your code by building your own test trees both with and without empty trees and testing your leaf-sum code on them.

(define-datatype bintree bintree?
	(leaf-node
		(datum number?))
	(interior-node
		(key symbol?)
		(left bintree?)
		(right bintree?)))

(define leaf-sum
	(lambda (tree)
		(cases bintree tree
			(leaf-node (datum) datum)
			(interior-node (key left right)
				(+ (leaf-sum left) (leaf-sum right))))))

Note: Remember that an empty tree has no fields: (define my-empty-tree (empty-tree))

MAKE SURE TO NAME YOUR VARIANTS: empty-tree, leaf-node, and interior-node
MAKE SURE TO NAME YOUR FUNCTION: leaf-sum

Part B - Exercise 2.6, p.50 - (10 minutes)
Draw the abstract syntax tree for the lambda caluculus expression:
((lambda (a) (a b)) c)

This exercise will help you better understand abstract syntax trees. Instead of drawing the tree, make your tree as a collection of abstract syntax records as described on page 48. For example, the tree for (lambda (x) x) would be

(define my-tree (lambda-exp 'x (var-exp 'x)))

You must use the following datatype which is defined on page 48 (i.e.: copy this into your homework file):

(define-datatype expression expression?
(var-exp (id symbol?))
(lambda-exp (id symbol?)(body expression?))
(app-exp (rator expression?)(rand expression?)))

YOU MUST STORE YOUR TREE IN A VARIABLE CALLED: my-tree

This problem requires lecture 11 and book section 2.2.2.

Exercise 2.8, p.52 - (60 minutes)

Rewrite the solution to exercise 1.19 using abstract syntax. Then compare this version to the original solution.

See HW11 for exercise 1.19.

Use the same logic you used for 1.19, but make sure to work from the parsed abstract syntax instead of directly from the concrete syntax.

You won't have to modify the definition of parse-expression for this problem. You may not use the occurs-free? function defined in the book, but you may model your code after it if you wish. Be sure to use a cases construct for both free-vars and bound-vars.

Use may use the following code to begin free-vars:

(define free-vars
  (lambda (exp)
    (free-vars-aux (parse-expression exp) '())))

(define free-vars-aux
  (lambda (ast bound)
    (cases expression ast
           ...
    )))

Do something similar for bound-vars.

This problem requires Lecture 13.

Mutable Data - (30 minutes)
Below is a definition of a function called next-symbol. When invoked, it generates the next symbol in the sequence g1, g2, etc.

(define next-symbol
  (let ((c 0))
    (lambda ()
      (set! c (+ c 1))
      (string->symbol (string-append "g" (number->string c)))
      )))

No, that's not a typo: the lambda expression is inside the let. Think about the order in which define, let, and lambda do things when evaluated.

What is displayed in the following transcript, and why?

(eq? (next-symbol) 'g1)

(eq? (next-symbol) 'g1)

(eq? (next-symbol) (next-symbol))

NOTE: when explaining why the expressions evaluate the way they do, do not just claim that the symbols are different, explain why they are different. Specifically, you should explain why the counter c does not get set to zero at each call to next-symbol and the role of the 'let c' statement and first class functions (i.e., what is next-symbol really bound to?).

This problem requires Lecture 15 and book sections 3.1-3.2.

Exercise 3.6, p.79 - (30 minutes)
Extend the language by adding a new primitive operator minus that take one argument, n and returns -n
--> minus(+(minus(5),9))
-4

This problem is a warm-up for working with the interpreter. The purpose of this problem is to get you used to working with the parser and eval-expression.

To complete this assignment, you will need to do the following:

1. Modify the grammar specification to include "minus".
2. Change the interpreter to handle this new primitive function.

Here is the code for the Lecture 15 interpreter to start with.

Homework 17 is the SLAT Parser

This problem requires Lecture 15 and book sections 3.1-3.2.

Exercise 3.7, p.79 - (45 minutes)
Add list processing primitives to the language, including cons, car, cdr, list, and a new variable, emptylist, which is bound to the empty list. Since there is no support for symbols, lists can contain only numbers and other lists. How does this change the epressed and denoted values of the language?
--> list(1,2,3)
(1 2 3)
--> car(cons(4,emptylist))
4

In this problem you add lists to the interpreter.

NOTE: In the initial environment, emptylist should be bound to ():

    > (run "emptylist")
    ()

    > (run "cons( 4, cons( 5, emptylist ) )")
    (4 5)

The process for adding the cons, list, car, and cdr primitive functions should be much like what you did in Homework 16.

Here is the code for the Lecture 15 interpreter to start with.

This problem requires Lecture 17 and book section 3.3.

This exercise is not from the book. The interpreter does not have logical operators. This exercise will help you explore adding them as regular primitives and as special forms.

Part A - variable arity 'or' - (30 minutes)
Add a variable arity primitive called "or" to the interpreter.  The function should return the boolean disjunction of its arguments (i.e. if any of the values are not zero, it should return 1).

Part B - short-cicuited 'sum' - (30 minutes)
Add a variable arity special form "sum" function to the interpreter that returns the boolean disjunction of its arguments, but performs "short-circuited evaluation" as we discussed in Lecture 5.  This means that "sum" should only evaluate expressions until it finds one that is true.

The parser should return a sum-exp node in the abstract syntax tree when given the string "sum(1,0,1,1)".  The abstract syntax for a sum-exp node is sum-exp(rands).  The process for adding this special form is just like the process in Lecture 17.

Note: this special form is called "sum" to distinguish it from the primitive function "or".  In logic, "or" is sometimes called the "disjunctive sum".

Part C - follow-up question - (10 minutes)
Why couldn't such short-circuited logic have been built into the primitive procedures?

Here is the code for the Lecture 17 interpreter to start with.

Here's a quick test you can use:
Suppose that the variable z is undefined. The expression or(1,z) should crash. The expression sum(1,z) should return 1.

Note: be very careful to keep straight ELL's logical values (zero and non-zero) and Scheme's logical values (#f and #t). Only ELL logical values should ever be visible to a programmer using the interpreter.

Homework 20 is the SLAT Translator

This problem requires and Lectures 17 and 18 and book sections 3.4-3.5.

Part A - Sequential 'let' - (60 minutes)
This exercise is not from the book. Modify the semantics of let given in Section 3.4 so that clauses in the let expression are executed sequentially and their binding takes affect in the next clause (like Scheme's let*). Thus:

    let x = 5 
        y = add1(x)
      in +(x,y)

would return 11 because the x in the second clause refers to the binding in the previous clause.

Part B - Exercise 3.20, p.89 - (30 minutes)
Modify the interpreter to signal an error if a closure is called with the wrong number of arguments.
The simple interpreter with if, let, proc, and app expressions.

This problem requires Lecture 18 and book section 3.5.

Syntax Expand - (120 minutes)
This exercise is not from your book. Remember from Lecture 5 that let expressions in Scheme are just syntactic sugar and can be replaced by an application of a lambda expression to operands:

    (let ((a 3)
          (b 4))
      (+ a b))

is equivalent to

    ((lambda (a b) (+ a b)) 3 4)

The same is true in ELL, although the syntax for the languages is different:

    let a = 3
        b = 4
      in +(a,b)

is equivalent to

    (proc(a,b) +(a,b) 3 4)

Write a function called syntax-expand that takes an ELL abstract syntax tree as input and replaces all occurrences of let-exp expressions with the equivalent app-exp expressions whose rators are proc-exp expressions.

I consider your doing and understanding this problem to be very important. 

Your eval-program function should have syntax-expand inserted to preprocess the syntax tree returned by the parser.

(define eval-program
  (lambda (pgm)
    (cases program pgm
           (a-program (body) (eval-expression (syntax-expand body) (init-env))))))

The simple interpreter with if, let, proc, and app expressions.

This problem requires Lecture 20 and book section 3.7.

Exercise 3.39, p.103 - (60 minutes)
Add the expression begin to the language.

A begin expression may contain one or more subexpressions separated by semi-colons. These are evaluated in order and the value of the last is returned. Implement this by modifying eval-expression.

   <expression> ::= begin <expression> { ; <expression> }* end   
 

The interpreter with variable assignment.

This problem requires Lecture 21 and book section 3.8.

Exercise 3.53, p.114 - (90 minutes)
In lanugages supporting call-by-reference it is usual for call-by value to be supported also, with a method for specifying wich is to be used for each formal parameter. Extend the inplementation of this section in this way.

Use the following syntax:

   <expression> ::= proc ( {<formal>}*(,) ) <expression>   
      
   <expression> ::= letrec {<identifier> ( {<formal>}*(,) ) = <expression>) }*   
                      in <expression>   
 

   <formal> ::= <identifier>   
              | var <identifier>   
 

Note that "<formal>*(,)" denotes a comma-separated list of <formal> nonterminals.

Using this syntax, the semantics for the assignment should be to have

    let a = 3
        p = proc (x) set x = 4
      in (p a)

pass a by value (a equals 3 when finished) and

    let a = 3
        p = proc (var x) set x = 4
      in (p a)

pass a by reference (a is changed to 4).

Here's a useful way to re-write eval-rands for this assignment:

    (define eval-rands
      (lambda (formals rands env)
        (map (lambda (form x) (eval-rand form x env)) formals rands)))

Notice that eval-rands now takes as a parameter the list of formal parameters for the function you are about to pass the operands to.  This lets you do the right kind of parameter passing (by value or by reference).  (Note the use of Scheme's map function here: it is used to map a two-parameter function onto two lists: one call to eval-rand with the first element in both lists, a second call with the second element from both lists, etc.)

The rest is up to you.  Make sure to think about

• how formals are now stored in a closure;
• what happens in eval-expression for the proc-exp, letrec-exp, and app-exp cases; and
• what eval-rand should do.

You may also want to incorporate your "begin" expression code into this new interpreter to make testing your code easier.  If not, you can use nested 'let's to emulate a "begin" like in the code below (which should return 11):

    let a = 4
        p1 = proc (var x) set x = 10
        p2 = proc (var x) set x = +(x, 1)
      in let tmp = (p1 a)
           in let tmp2 = (p2 a)
                in 

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 333

a

The interpreter with call-by-reference parameter passing.

This problem requires Lecture 23 and book section 3.8.

Exercise 3.58, p.118 - (30 minutes)
Add let to the call-by-need interpreter. Use a test program that demonstrates that this let is lazy.

If you use lazy evaluation for procedures, can't you use it for let expressions or other times you bind variables?

Try testing your results using expressions like this

    let x = 3
      in +(x,1)

and

    let x = +(z,1)
      in 

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 115

3

Why should the last one work with lazy evaluation?

The call by need interpreter.

This problem requires Lecture 25 and book section 3.9.

Exercise 3.64, p.122 - (30 minutes)
Extend the block statement to allow variables ot be initialized. In the solutions, does the scope of a variable include the initalizer for variable declared later in the same block statement?

The problem says "to allow variables to be initialized". For simplicity, make it so that all variables must have an initialization expression and be of the form <identifier> = <expression>. For example,

    var x = 1, y = *( 3, 4 );
    {
        print( x );
        print( y )
    }

Make sure to think about and answer the associated question in the book.

The interpreter with statements.

No homework due with Lecture 27.

Java procedure types
This problem is not from your textbook.

In Lecture 27, we talked about type signatures for functions. In some languages, certain functions might seem to have multiple signatures. Enumerate as many type signatures as you can for the binary "+" operator in Java. For example,

    (int * int) -> int
    (float * float) -> float

and so on. Think about all of the possible types that you can join by the "+" operator, including strings.

How many of these combinations do you think are implemented directly as special cases in the Java compiler? How might you be able to implement all of the other combinations?

This problem requires Lecture 28 and book section 4.2.

Exercise 4.8, p.142 - (180 minutes)
This problem will be spread over three assignments (HW 29-31). You don't have to submit anything until Homework 31 is due.

Some printed editions of the textbook show an error in the first rule:

    (type-of-expression «e₁» tenv) = t
    ...
    (type-of-expression «e_n» tenv) = t,    n > 0
  ___________________________________________________________
    (type-of-expression «listof (e₁,...,e_n)» tenv) = (listof t)

The red part of the above should not be in the book, so don't get confused by it. Use "list" as the keyword for an expression that makes a list from its arguments, and "listof" as the keyword for type-expressions.

This exercise requires that you complete the following:

• add the SIX new list-handling expressions to the grammar (follow the BNF given in the problem, plus do the car and cdr as described in the last paragraph of the problem in the text)
• add the new type-exp for lists to the grammar (follow the BNF given in the problem)
• add a new type for lists (change the define-datatype for type)
• change expand-type-expression to deal with the new list expression
• change type-to-external-form to return a printable form of the list type
• add new clauses to type-of-expression to handle the new list-handling expressions (follow the semantic rules in the problem)
• add new clauses to eval-expression to implement the new list-handling expressions

You may need to write some helper functions to assist with these.

Note that "null?" is a predicate that returns a boolean, and "emptylist [t]" is a constructor that returns an empty list.

The grammar in the book shows that emptylist requires a type parameter. In addition to answering the questions in the textbook, describe briefly how you might implement type-checking for emptylist without requiring a type parameter in the grammar.

IMPORTANT: To facilitate grading a type crash, we've added a variable arity function to the interpreter called type-crash.  You should call this function when the type error is detected.  The autograder is dependent on this type of crash, and will not award points otherwise.

Example Tests:

(run "list(1,2,3,4)") should return "(1 2 3 4)". This tests the evaluation part of the program.

(type-check "list(1,2,3,4)") should return "(listof int)". This tests the type-checking part of the program.

The type-checking interpreter.

Polymorphism - (20 minutes)
This problem is not from your textbook.

In Lecture 31, we talked about polymorphism.  Label each of the following C++ examples as using ad hoc or universal polymorphism (specify overloading, coercion, inclusion, or parametric) and explain your decision. If you're not sure exactly how C++ implements a particular form of polymorphism (whether it's overloaded or coerced, for example), take your best guess and explain it.

1. double sqrt( double );
   float  f = 1.0f;   //The 'f' in 1.0f means to interpret 1.0 as a float and not a double
   double d = 1.0;    //The 1.0 here will be interpreted as a double
   
   f += sqrt( f );
   d += sqrt( d );

   There are two uses of polymorphism in the above code.

2. class A { ...};
   class B: public A { ... };
   class C: public A { ... };
   
   A a;
   B b;
   C c;
   A array_of_A[10];
   
   array_of_A[0] = a;
   array_of_A[1] = b;
   array_of_A[2] = c;

3. #include <vector.h>
   ...
   vector<int>   v(10, 0);

4. char c  = 'A';
   int  i  = 10;
   int  *p = &i;
   
   (p++) + (i++) + (c++);

   There are also two polymorphic operators in this last example. (For this one, consider polymorphic operations in the last expression, not in the three declarations.)

   Be careful with this one--the last line evaluates to a pointer.

This problem requires Lecture 30 and book section 4.4.

Exercise 4.16, p.160 - (45 minutes)

Consider the following examples:

1. proc (f,g,p,x) if (p(f x)) then (g 1 x) else add1((f x))
2. proc (x,p,f) if (p x) then add1(x) else (f p x)
3. proc (x,p,f,g) if (p add1(x)) then add1((f x)) else (g f x)
4. let x = 3 f = proc (x) add1(x) in (f x)

First, insert ? in front of each formal parameter. Then, solve the resultant type equation. Treat add1 as if it were a procedure of type
(int -> int) and + as if it were a procedure of type (int * int -> int).

The book and the problem describe inference in terms of setting up "type equations" and then solving these equations, but these are just the type comparisons made at each step during the type-checking algorithm--we don't really set up systems of equations and then solve them, instead we just repeatedly traverse the AST until all of the type information is filled in. Just write down in order each type comparison that would take place.

The first one has been done for you. You would be wise to follow this model.

This problem is not from your textbook.

In this assignment, you will write short programs in C++ similar to the OOELL examples on pages 175 and 176 of your textbook to illustrate how C++ handles inheritance.

Part A - (20 minutes)
Write one program modeled after the example on page 175 to demonstrate that C++ uses static inheritance for variables.

Part B - (20 minutes)
Write a second program modeled after the example on page 176 to illustrate that C++ uses static inheritance for methods if you do not use the virtual keyword.

Part C - (20 minutes)
Write a third program, using the virtual keyword but otherwise identical to your second program, to demonstrate that C++ uses dynamic method inheritance for methods that are declared as virtual.

The OOELL examples store intermediate results and return them as a list since OOELL doesn't have print statements. You don't have to do this--just use normal C++ output as needed to print out what the different methods return.

In your submitted file, include the following for each of these three programs:

• Your C++ source code
• The output from running the program
• A brief explanation of how the program works

This problem requires Lecture 34 and book section 5.1-5.4.1.

Part A - Exercise 5.11, p.199 - (30 minutes)

The book omits the BNF:

   <expression> ::= instanceof <expression> <identifier>   
 

Part B - Exercise 5.20, p.200 - (30 minutes)

In our interpreters, the class object is a special case because it is not explicitly represented in the class environment. What procedures must be aware of this special case? Eliminate these special cases by placing a class whose name is object into the intial class environment. Give the class object an initialize method, so that it is possible to create an object of class object, and so that there is a default initialize method.

Implement both of these in the same interpreter and submit it as a single file.

Base your implementation on the simple implementation of an object-oriented interpreter.

Extra Credit (worth one full homework):
Please fill out the online course evaluation for this course.

To do this, go to the "Student Ratings" section on Route Y and follow the instructions there for completing the evaluation for this course. There is no need to otherwise submit anything--I receive a report of who has responded, but not what each person's reply is.