ppa-en solution

solution.md

Test 1 - Introduction to λ calculus and Lisp

(1) Reduce the following expression to normal form:

    (λx. (λy. (x y))) ((λu. (u y)) (ay))
α=> (λx. (λt. (x t))) ((λu. (u y)) (ay))
β=> (λt. (((λu. (u y)) (ay)) t))
β=> (λt. (((ay) y) t)

(2) Reduce the following expression using normal evaluation order:

   (λx. (λy. (λx. x (x y))(λa. * x a))(- x 5)) 7
=> (λy. (λx. x (x y))(λa. * 7 a))(- 7 5)
=> (λx. x (x (-7 5)))(λa. * 7 a))
=> (λa. * 7 a)((λa. * 7 a) ( - 7 5)) 
=> * 7 ((λa. * 7 a) ( - 7 5)) 
=> * 7 * 7 - 7 5
=> 98

(3) Reduce the same expression using applicative order:

   (λx. (λy. (λx. x (x y))(λa. * x a))(- x 5)) 7
=> (λy. (λx. x (x y))(λa. * 7 a))(- 7 5)
=> (λy. (λx. x (x y))(λa. * 7 a)) 2
=> (λx. x (x 2))(λa. * 7 a))
=> (λa. * 7 a)((λa. * 7 a) 2)
=> (λa. * 7 a)(* 7 2)
=> (λa. * 7 a) 14
=> * 7 14
=> 98

(4) Reduce the following expression using the definitions for logical functions:

   and false true
=> (xy. x y F) F T
=> F T F
=> (λtf. f) (λtf. t) (λtf. f)
=> (λtf. f)
=> F

(5) Describe a λ function in normal form for expression x+x for an integer number x represented as a lambda function. Apply it to x = 3 = (λsz. s(s(sz))):

x + y = (λxysz. x s (y s z))
x + x = (λxsz. x s (x s z))

   (λxszz. x s (x s z)) (λsz. sssz)
=> (λsz. (λsz. sssz) s ((λsz. sssz) s z))
=> (λsz. (λz. sssz) ((λsz. sssz) s z))
=> (λsz. sss ((λsz.sssz) s z))
=> (λsz. ssssssz)
=> 6

(6) Write λ function for a recurrent equation f(n) = 3f(n -1), f(0) = 2:

(λf. (λn. zero n 
               2
               (* 3 (f (-n 1)))
     )
)

(7) For the function from the previous example, show the reduction for f(1). What would be the initial expression?

The initial expression is: YR1 where R is the recursive function from (6).

   Y R 1 
=> R (YR) 1
=> (λfn. zero n 2 (* 3 (f (-n 1)))) (YR) 1
=> zero 1 2 (* 3 ( (YR) (-1 1)))
=> (* 3 ( (YR) (-1 1)))
=> (* 3 ( R (YR) (-1 1)))
=> (* 3 ( (λfn. zero n 2 (* 3 (f (-n 1)))) (YR) (-1 1)))
=> (* 3 ( zero (-1 1) 2 (* 3 ( (YR) (- (-1 1) 1)))))
=> (* 3 ( zero 0 2 (* 3 ( (YR) (- (-1 1) 1)))))
=> (* 3 (2))
=> (* 3 2)
=> 6

(8) Define function diffMinMax(s) which for a given list s returns the difference between its smallest and largest numbers:

(defun diffMinMax(s)
    (if (eq s nil)
        nil
        (diffMinMax2 (cdr s) (car s) (car s))
    )
)

(defun diffMinMax2 (s min max)
    (if (eq s nil)
        (- max min)
        (diffMinMax2 (cdr s) (minF min (car s)) (maxF max (car s)))
    )
)

(defun minF (x y)
    (if (< x y)
        x
        y
    )
)

(defun maxF (x y)
    (if (> x y)
        x
        y
    )
)

There are of course multiple ways to deal with this problem, any solution that will work will be accepted as long as it stays within reasonable performance bounds.