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)))))))
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))] )))
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; } }
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)))))))
Solution:
(if #t 3 #f)
Just mention the word "undecidable" in some coherent sentence.
((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 = 6In 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
sabry@cs.uoregon.edu