Midterm Solution

Hello World (8 points)

Write a Scheme function that appends two lists and convert it to CPS.

Solution:

(define append 
  (lambda (l1 l2)
     (if (null? l1) l2
       (cons (car l1) (append (cdr l1) l2)))))

(define append-cps
  (lambda (l1 l2 k)
    (if (null? l1) (k l2)
      (append-cps (cdr l1) l2 (lambda (v) (k (cons (car l1) v)))))))

Interpreters (25 points)

The abstract syntax of a while expression is:

public class WhileExp extends AST {
  private AST c, b;
  public WhileExp (AST condition, AST body) { c=condition; b=body; }
  public AST getCondition () { return c; }
  public AST getBody () { return b; }
}

The evaluation of the expression proceeds as expected, repeatedly testing the condition, and evaluating the body if the condition is true. Otherwise, the evaluation of the while expression terminates and returns 0. Write the part of the interpreter that evaluates a while expression. Make any reasonable assumptions about the rest of the interpreter but document them.

Solution:

Here is the code in Scheme :-)

      [while (condition body)
	(letrec ([loop (lambda ()
			 (let ([cv (eval condition env)])
			   (if (true? cv)
			       (begin (eval body env) (loop))
			       0)))])
	  (loop))]
      )))

Higher-Order Functions and Closures (25 points)

In a Scheme interpreter, the evaluation of a lambda-expression produces a closure that contains the formal parameters, the body of the function, and the lexical environment. Since the only thing one can do with a closure is to apply it, it could be represented as an object with one method called apply that takes the arguments and returns the result. Use this idea to complete the translation of the following Scheme program to Java.

Scheme code:

(define cons (lambda (a b) (lambda (s) (s a b))))
(define car (lambda (l) (l (lambda (a b) a))))
(define cdr (lambda (l) (l (lambda (a b) b))))

Solution:

class Primitives {
  static PairClosure cons (Object a, Object b) { return new PairClosure(a,b); }
  static Object car (PairClosure l) { return l.apply(new SelectFirst()); }
  static Object cdr (PairClosure l) { return l.apply(new SelectSecond()); }
}

class PairClosure {
  Object a, b;
  PairClosure (Object a, Object b) { this.a=a; this.b=b; }
  Object apply (Selector s) { return s.apply(a,b); }
}

abstract class Selector {
  abstract Object apply (Object a, Object b);
}

class SelectFirst extends Selector {
  Object apply (Object a, Object b) { return a; }
}

class SelectSecond extends Selector {
  Object apply (Object a, Object b) { return b; }
}

Continuation-Passing Style (30 points)

Convert the following collection of Scheme functions to continuation-passing style.

Solution:

(define zeroEncoding
  (lambda (f x) 
    x))

(define zeroEncodingCPS
  (lambda (f x k) 
    (k x)))

;;;

(define oneEncoding
  (lambda (f x)
    (f x)))

(define oneEncodingCPS
  (lambda (f x k)
    (f x k)))

;;;

(define twoEncoding
  (lambda (f x)
    (f (f x))))

(define twoEncodingCPS
  (lambda (f x k)
    (f x (lambda (v) (f v k)))))

;;;

(define succEncoding
  (lambda (m)
    (lambda (f x)
      (f (m f x)))))

(define succEncodingCPS
  (lambda (m k)
    (k (lambda (f x k)
	 (m f x (lambda (v) (f v k)))))))

;;;

(define addEncoding
  (lambda (m n)
    (lambda (f x)
      (m f (n f x)))))

(define addEncodingCPS
  (lambda (m n k)
    (k (lambda (f x k)
	 (n f x (lambda (v) (m f v k)))))))

;;;

(define test
  (lambda (nEncoding) 
    (let ((n (addEncoding (succEncoding twoEncoding) nEncoding)))
      (n add1 0))))

(define testCPS
  (lambda (nEncodingCPS k) 
    (succEncodingCPS twoEncodingCPS (lambda (v)
    (addEncodingCPS v nEncodingCPS (lambda (n) 
    (n (lambda (v k) (k (add1 v))) 0 k)))))))

Static vs Dynamic Typing (12 points)

Safe languages like Java and Scheme ensure the integrity of their data. For example, in both languages it is impossible to multiply two strings. Java has a static type checker that detects such situations at compile time. As the interpreter we developed in class illustrates, Scheme detects such situations at run time.

Solution:

Show with an example that Java's type checker rejects some expressions that would run in Scheme without any errors.
```
(if #t 3 #f)
```
Argue that Java must reject some expressions that would run in Scheme without any errors. In other words, it is impossible to statically determine, at compile time, if the evaluation of an expression will produce a type error.
```
Just mention the word "undecidable" in some coherent sentence.
```

Extra Credit (10 points)

The semantics of function application is explained using the beta-rule of the lambda-calculus:

((lambda (x) e) e') = e[x:=e']

where e[x:=e'] denotes the substitution of all occurrences of x in e by e'. For example:

	((lambda (x) (x + x)) 3) = (x+x)[x:=3] = 3+3 = 6

In a formal sense, the above definition is not quite right. But you should have an intuitive understanding of function application and that's what this problem is testing. Using the beta-rule, evaluate the following expressions:

Solution:

(((lambda (f) f) (lambda (x) x)) 3)
= (f[f:=(lambda (x) x)] 3)
= ((lambda (x) x) 3)
= x[x:=3]
= 3

((lambda (x) (x (lambda (x) (x + x)))) (lambda (f) (f 3)))
There is a name clash between the two declarations of x. For clarity
rename the inner x to y.
= ((lambda (x) (x (lambda (y) (y + y)))) (lambda (f) (f 3)))
= (x (lambda (y) (y + y)))[x:=(lambda (f) (f 3))] 
= ((lambda (f) (f 3)) (lambda (y) (y + y)))
= (f 3)[f:=(lambda (y) (y + y))]
= ((lambda (y) (y + y)) 3)
= (y+y)[y:=3]
= 3+3
= 6

((lambda (y) (((lambda (x) (lambda (y) (x + y))) y) 4)) 3)
Again there is a conflict between the two declarations of y. For clarity
rename the inner y to z.
= ((lambda (y) (((lambda (x) (lambda (z) (x + z))) y) 4)) 3)
= (((lambda (x) (lambda (z) (x + z))) y) 4)[y:=3]
= (((lambda (x) (lambda (z) (x + z))) 3) 4)
= ((lambda (z) (x + z))[x:=3] 4)
= ((lambda (z) (3 + z)) 4)
= (3+z)[z:=4]
= (3+4)
= 7

Page visited

times since November 18, 1996.

sabry@cs.uoregon.edu