Question

these questions are about LISP

please explain the reason

In the following Fun language example, which expressions can we get by some series of reductions? Assume that we can reduce the built-in function + in the usual way that addition works.

Definitions:

f(x, y) = x+y

g(x) = x+1

h(x) = 7

Example:

f(g(h(4)), h(g(5)))

1.Select all that apply:

a. g(h(4)) + h(g(5))

b. f(g(7), h(g(5)))

c. f(8, 7)

d. 15

e. f(g(h(4)) + h(g(5)))

f. f(5, h(g(5)))

g. f(h(g(4)), g(h(5)))

h. 42

2.In ((lambda (x) (x 2)) (lambda (z) (+ z 1))) we can choose both orders of reduction: reduce lambda (x)... first, or lambda (z)... first T or F

3. Assume that a sequence of reductions leads to a normal form. Then none of the intermediate expressions before the last reduction was in normal form T or F

Answer 1

1. Options a, b, c, d, g are all correct answers.

Explanation:

(Observation: f(x,y) is a sum function,

Given expression: f( g(h(4)), h(g(5)) )

From definitions, let's simplify the innermost expressions first:

h(4) = 7, g(5) = 5 + 1 = 6

Substituting these in the expression:

f( g(7), h(6) ) ... [1]

From definition: g(7) = 7 + 1 = 8, h(6) = 7, and substituting these again in [1]

f ( 8, 7) = 8 + 7 = 15 ... [2]

From [2] it is immediately obvious that the options c and d are correct.

Let's try simplifying the remaining options:

a. g(h(4)) + h(g(5)) = g(7) + h(6) = 8 + 7 = 15; (correct)

b. f( g(7), h(g(5)) ) = f( 8, h(6) ) = f( 8, 7 ) = 8 + 7 = 15; (correct)

e. f( g(h(4)) + h(g(5)) ) -> function takes 2 parameters but just 1 parameter is supplied here; (incorrect)

f. f( 5, h(g(5)) ) = f( 5, h(6) ) = f( 5, 7 ) = 5 + 7 = 12; (incorrect)

g. f( h(g(4)), g(h(5)) ) = f( h(5), g(7) ) = f( 7, 8 ) = 7 + 8 = 15; (correct)

h. 42; (incorrect)

2. T (true). Explanation: From the Church Rosser theorem, it does not matter what reduction strategy is used initially. Either reduction will converge to the same final expression.

3. T (true). Explanation: When an expression cannot be further beta reduced, it is in normal form. So reaching normal form is the final state of the reduction.