III.1 (((1.(2.(3.nil))).(1.(2.nil))).nil) = ((1 2 3).(1 2)) ((1.2).(2.3)) ((1 2 (3.nil).(4 5 6))) = ((1 2 (3).(4 5 6))) III.2 (1 2 3) ==> ----------- ----------- ----------- ------- |N| | -|-->|N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ----------- ------- | | | v v v ------- ------- ------- |T| 1 | |T| 2 | |T| 3 | ------- ------- ------- (1.(2.3)) ----------- ----------- ------- |N| | -|-->|N| | -|-->|T| 3 | ----------- ----------- ------- | | v v ------- ------- |T| 1 | |T| 2 | ------- ------- ((1.2).3) ----------- ------- |N| | -|-->|T| 3 | ----------- ------- | v ----------- ------- |N| | -|-->|T| 2 | ----------- ------- | v ------- |T| 1 | ------- ((1.2) 3) ----------- ----------- ------- |N| | -|------------>|N| | -|-->|T|nil| ----------- ----------- ------- | | v v ----------- ------- ------- |N| | -|-->|T| 2 | |T| 3 | ----------- ------- ------- | v ------- |T| 1 | ------- ((1 2) 3) ----------- ----------- ------- |N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ------- | | | v | ------- | |T| 3 | | ------- v ----------- ----------- ------- |N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ------- | | v v ------- ------- |T| 1 | |T| 2 | ------- ------- (1 (2.3)) ----------- ----------- ------- |N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ------- | | v v ------- ----------- ------- |T| 1 | |N| | -|-->|T| 3 | ------- ----------- ------- | v ------- |T| 2 | ------- (1 2 3 nil) ----------- ----------- ----------- ----------- ------- |N| | -|-->|N| | -|-->|N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ----------- ----------- ------- | | | | v v v v ------- ------- ------- ------- |T| 1 | |T| 2 | |T| 3 | |T|nil| ------- ------- ------- ------- (1 2 (3.nil)) ----------- ----------- ----------- ------- |N| | -|-->|N| | -|-->|N| | -|-->|T|nil| ----------- ----------- ----------- ------- | | | v v v ------- ------- ----------- ------- |T| 1 | |T| 2 | |N| | -|-->|T|nil| ------- ------- ----------- ------- | v ------- |T| 3 | ------- III.3 ((1 2)(3 4)(5 6)) --------- --------- --------- | | -|-------------->| | -|-------------->| |nil| --------- --------- --------- | | | v v v --------- --------- --------- --------- --------- --------- | 1 | -|-->| 2 |nil| | 3 | -|-->| 4 |nil| | 5 | -|-->| 6 |nil| --------- --------- --------- --------- --------- --------- ((1.2)(3.4)(5.6)) --------- --------- --------- | | -|-->| | -|-->| |nil| --------- --------- --------- | | | v v v --------- --------- --------- | 1 | 2 | | 3 | 4 | | 5 | 6 | --------- --------- --------- (((1.2).(3.4))(5.6)) --------- --------- | | -|-------------->| |nil| --------- --------- | | v v --------- --------- --------- | | -|-->| 3 | 4 | | 5 | 6 | --------- --------- --------- | v --------- | 1 | 2 | --------- (((1.2).(3.4)).(5.6)) --------- --------- | | -|-------------->| 5 | 6 | --------- --------- | v --------- --------- | | -|-->| 3 | 4 | --------- --------- | v --------- | 1 | 2 | --------- ((1.2).((3.4).(5.6))) --------- --------- --------- | | -|-->| | -|-->| 5 | 6 | --------- --------- --------- | | v v --------- --------- | 1 | 2 | | 3 | 4 | --------- --------- ((1 2).((3 4).(5 6))) --------- --------- --------- --------- | | -|-------------->| | -|-------------->| 5 | -|-->| 6 |nil| --------- --------- --------- --------- | | v v --------- --------- --------- --------- | 1 | -|-->| 2 |nil| | 3 | -|-->| 4 |nil| --------- --------- --------- --------- (()()().(()())) = (()()()()()) --------- --------- --------- --------- --------- |nil| -|-->|nil| -|-->|nil| -|-->|nil| -|-->|nil|nil| --------- --------- --------- --------- --------- III.9 Fibonacchi(n) = fib(n,1,1) whererec fib(n,i,k) = if n == 0 then k else fib(n-1,i+k,i) III.10 evaluate(e) = create-number(eval(e)) whererec eval(e) = if is-a-number(e) then get-value(e) else if is-paren(e) then eval(get-body(e)) else if is-if-expr(e) then if eval(get-if(e)) then eval(get-then(e)) else eval(get-else(e)) else let f = get-operator(e) and a = eval(get-left(e)) and b = eval(get-right(e)) in if is-a-*(f) then a*b else if is-a-/(f) then a/b else if is-a-+(f) then a+b else if is-a--(f) then a-b else if is-a-<(f) then a(f) then a>b else if is-a-<=(f) then a<=b else if is-a->=(f) then a>=b New predicate functions: is-if-expr(e) -- true if e has syntax of if-expression, where test expression is a comparison (<,=,>,<=,>=) between two integers is-a-<(e) -- true if e is the < operator is-a-=(e) -- true if e is the = operator is-a->(e) -- true if e is the > operator is-a-<=(e) -- true if e is the <= operator is-a->=(e) -- true if e is the >= operator New selector functions: get-if(e) -- returns test expression get-then(e) -- returns then expression get-else(e) -- returns else expression Modified function: get-operator(e) -- returns outermost <,=,>,<=,>=,*,/,+,- None of these functions is recursive, but eval(). Here, I did more then was asked in the problem. This expanded code not only handles if-then-else expression, but it also can handle comparison expessions and treats their result as integer. IV.1 ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) xqz // this one is given in the book ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => (((lambda z|((lambda q|q)z))h)i) => (((lambda z|(z))h)i) => (hi) xzq ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => (((lambda z|((lambda q|q)z))h)i) => ((lambda q|q)h)i) => (hi) qxz ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => ((lambda x|(xi))((lambda z|(z))h)) => (((lambda z|(z))h)i) => (hi) qzx ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => ((lambda x|(xi))((lambda z|(z))h)) => ((lambda x|(xi))(h)) => (hi) zxq ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => ((lambda x|(xi))(((lambda q|q)h))) => ((lambda q|q)h)i) => (hi) zqx ((lambda x|(xi))((lambda z|((lambda q|q)z))h)) => ((lambda x|(xi))(((lambda q|q)h))) => ((lambda x|(xi))(h)) => (hi) IV.2 a. _ | v ((lambda y|yxx)y x) ** * * y occurs free and boud x occurs free b. _________________________ | _____________ | | | _ | | | | | v v v ((lambda x|(lambda x|(lambda x|x)x)x)x) * x occurs free and bound c. ________________ ___ | | ___|__________________________|__ | | | | || __ | | || | v | vv | vv | vv (lambda x|(xy(lambda y|((xy)(lambda x|wxyz))(lambda z|wyz)))) * * * * x occurs bound y occurs free and bound z occurs free and bound w occurs free d. ____________ ______________ | x | | | _ | | | v | v | vv (lambda x|y(lambda y|x(lambda x|xz(lambda y|yx)))) * * x occurs bound y occurs free and bound z occurs free IV.3 ________ | v v (lambda f|+(f 3)(f 4))(lambda x|* x x) -> | ________________ |_____________________| (+((lambda x|* x x) 3)((lambda x|* x x) 4)) -> (+(* 3 3)(* 4 4)) -> + 9 16 -> 25 IV.4 T = (lambda x y|x) F = (lambda x y|y) not = (lambda w|w F T) not T = T F T = F not F = F F T = T and = (lambda w z|w z F) and F F = F F F = F and F T = F T F = F and T F = T F F = F and T T = T T F = T or = (lambda w z|w T z) or F F = F T F = F or F T = F T T = T or T F = T T F = T or T T = T T T = T IV.5 xor = (lambda w z|w (not z) z) = (lambda w z|w (z F T) z) xor F F = F (F F T) F = F T F = F xor F T = F (T F T) T = F F T = T xor T F = T (F F T) F = T T F = T xor T T = T (T F T) T = T F T = F IV.7 add 2 3 = (lambda w z y x|w y (z y x)) (lambda y z|y(y z)) (lambda y z|y(y(y z))) = (lambda y x|(lambda y z|y(y z)) y ((lambda y z|y(y(y z))) y x)) = (lambda y x|(lambda y z|y(y z)) y (y(y(y x)))) = (lambda y x|y(y(y(y(y x))))) = 5 IV.10 Ackerman function: Ack(i,j) = if i = 0 then j + 1 else if j = 0 then Ack(i-1,1) else Ack(i-1,Ack(i,j-1)) Lambda calculus: ack(i,j) = Y(lambda f i j|zero i (+ j 1) (zero j (f (- i 1) 1) (f (- i 1) (f i (- j 1)))) IV.12 1, n = 0,1 Fib(n) = Fib(n-1) + Fib(n-2), n > 1. Abstract syntax: fib(n) = if (zero(n) or zero(n-1)) then 1 else fib(n-1) + fib(n-2) Lambda calculus syntax: fib(n) = Y(lambda f n|(or (zero (- n 1)) (zero (- n 2))) 1 (+ (f (- n 1)) (f (- n 2))) ) Assume: Y = (lambda y|((lambda x|y(x x))(lambda x|y(x x)))) R = (lambda f n|(or (zero (- n 1)) (zero (- n 2))) 1 (+ (f (- n 1)) (f (- n 2))) ) Then: fib(3) = Y R 3 --> R (Y R) 3 --> (lambda n|(or (zero (- n 1)) (zero (- n 2))) 1 (+ ((Y R)(- n 1)) ((Y R)(- n 2))) ) 3 --> (or (zero (- 3 1)) (zero (- 3 2))) 1 (+ ((Y R)(- 3 1)) ((Y R)(- 3 2))) --> (or (zero 2) (zero 1)) 1 (+ ((Y R) 2) ((Y R) 1)) --> (or F F) 1 (+ ((Y R) 2) ((Y R) 1)) --> F 1 (+ ((Y R) 2) ((Y R) 1)) --> (+ ((Y R) 2) ((Y R) 1)) --> (+ (R (Y R) 2) (R (Y R) 1)) --> (+ ((lambda n|(or (zero (- n 1)) (zero (- n 2))) 1 (+ ((Y R)(- n 1)) ((Y R)(- n 2))) ) 2) ((lambda n|(or (zero (- n 1)) (zero (- n 2))) 1 (+ ((Y R)(- n 1)) ((Y R)(- n 2))) ) 1)) --> (+ ((or (zero (- 2 1)) (zero (- 2 2))) 1 (+ ((Y R)(- 2 1)) ((Y R)(- 2 2)))) ((or (zero (- 1 1)) (zero (- 1 2))) 1 (+ ((Y R)(- 1 1)) ((Y R)(- 1 2))))) --> (+ ((or (zero 1) (zero 0)) 1 (+ ((Y R) 1) ((Y R) 0))) ((or (zero 0) (zero (- 1 2))) 1 (+ ((Y R)(- 1 1)) ((Y R)(- 1 2))))) --> (+ ((or F T) 1 (+ ((Y R) 1) ((Y R) 0))) ((or T (zero (- 1 2))) 1 (+ ((Y R)(- 1 1)) ((Y R)(- 1 2))))) --> (+ (T 1 (+ ((Y R) 1) ((Y R) 0))) (T 1 (+ ((Y R)(- 1 1)) ((Y R)(- 1 2))))) --> (+ 1 1) --> 2 fib(3) = 2