midterm2-solns.rkt

#lang racket

;; Midterm 2 -- Practice Solution

(foldr + 5 '(1 2 3))
;; call the lambda f
;; call the initial value i

(+ 1 (+ 2 (+ 3 5)))

(foldl (lambda (x acc) (cons 1 (cons x acc)))
       '()
       '(2 3))

;; acc starts as being the empty list '()
;; then, inspect 2 and apply the lambda to '(2 ()) x = 2 acc = '()
;; acc = '(1 2)
;; '(1 3 1 2)
;; answer is '(1 3 1 2)

(define (concat l)
  ;; wrong
  (foldl (λ (x acc) (string-append acc x)) "" l))

'("x" "y" "z")
(string-append "x" (string-append "y" (string-append "z" "")))

;; (want to compute "xyz")

;; 2 (a):
;; first and third should be--second doesn't enough arguments to node
;; fourth has this invalid subtree (node 3 empty 4), as 4 is a number,
;; but not a tree?. This could be fixed by having 4 -> (node 4 empty empty)


(define (tree? t)
  (match t
    ['empty #t]
    [`(node ,e ,(? tree? t0) ,(? tree? t1)) #t]
    [_ #f]))

;; 2(b)
(define (tree-min t)
  (match t
    ['empty +inf.0]
    [`(node ,e ,t0 ,t1)
     (min e (tree-min t0) (tree-min t1))]))

;; Question 3: λ-calculus
;; 3(a)
;; ((λ (x) (λ (y) (λ (z) (y k)))) y)
;; -->α [y ↦ a]
;; ((λ (x) (λ (a) (λ (z) (a k)))) y)
;; second y doesn't change--as it is a free variable
;;
;; 3(b)
;; We could not rename y to k and perform the associated
;; α conversion, because doing so would capture the
;; otherwise-free variable k, and instead bind it as an
;; argument of the function.


;; ((λ(z)(z z)) ((λ(x)x) (λ(z)z)))
;; --> CBN β
;; (z z) [ z ↦ ((λ(x)x) (λ(z)z)) ]
;; = (((λ(x)x) (λ(z)z)) ((λ(x)x) (λ(z)z)))
;; ^^ this is the answer

;; Continue to reduce it to a final answer:
;; --> CBV β ((λ(z)z) ((λ(x)x) (λ(z)z)))
;; --> CBV β ((λ(z)z) (λ(z)z))
;; --> CBV β (λ(z)z)
;; Solution: (λ (x) x)


;; Question 4
(define (interp exp env)
  (match exp
    [(? string? s) s]
    [(? symbol? x) (hash-ref env x)]
    [`(+ ,s0 ,s1)
     ;; wrong
     #;(string-append s0 s1)
     ;; right
     (let ([v0 (interp s0 env)]
           [v1 (interp s1 env)])
       (string-append v0 v1))]
    [`(if-empty ,e ,e0 ,e1)
     ;; wrong!
     #;(if (equal? e "")
         (interp e0 env)
         (interp e1 env))
     ;; right
     (let ([v (interp e env)])
       (if (equal? v "")
           (interp e0 env)
           (interp e1 env)))]
    [`(let ([,x ,e]) ,exp)
     (let ([v (interp e env)])
       (interp exp (hash-set env x v)))]))

;; Question 5: Church Encoding

;; A church number for the natural number n is a function that
;; takes another function f, and "does f n times" to some argument x
;;
(λ (f) (λ (x) (f (f (f x))))) ;; Church numeral encoding of 3


;; two =~ (λ (f) (λ (x) (f (f x)))
;; (((λ(x)(x x))(λ(z)z))
;; two)
;;-->β
;;(((λ (z) z) (λ (z) z))
;; two)
;;-->β
;;((λ (z) z) two)
;;-->β
;;two

;; This term has *no* β-normal form
;;((λ (x) (x x)) (λ (x) (x x)))

;; This term has a some reduction sequences that end in a β normal form
;; and thus it is β reducible to a normal form. However, some other reduction
;; sequences run forever
;;((λ (x) y) ((λ (z) (z z)) (λ (z) (z z))))

;; call by name always performs the least amount of reduction



;; in Racket
;; (let ([x 0]
;;       [y 1])
;;   (+ x y))

;; After Church encoding
(((λ (x) (λ (y) ((plus x) y)))
  (λ (f) (λ (x) x)))
 (λ (f) (λ (x) (f x))))


(if Ω 0 1)
;; how do we encode this?

;; if you have
(if e-guard e-true e-false)
-- translate to -->
;; true is (λ (t f) (t)) -- expands to (λ (t) (λ (f) (t (λ (x) x))))
((e-guard-translation (λ (_) e-true))
 (λ (_) e-false))

((((λ (x) (x x)) (λ (x) (x x))) (λ (_) (λ (f) (λ (x) x))))
 (λ (_) (λ (f) (λ (x) (f x)))))
                               


;; (((λ (x) (x x)) (λ (z) z)) (λ (h) (λ (g) (h (h g)))))