3-19-24.rkt

#lang racket
;; CIS352 -- 3/19/2024

;; Exam Solutions

;; Version A

;; (1a)
(define (count-n lst n)
  (match lst
    ['() 0]
    [`(,hd . ,tl) #:when (equal? hd n)
                  (+ 1 (count-n tl n))]
    [`(,hd . ,tl) (count-n tl n)]))

#;(define (count-n lst n)
  (cond
    [(empty? lst) 0]
    [(equal? n (first lst))
     (add1 (count-n (rest lst) n))]
    [else (count-n (rest lst) n)]))

;; (1b)
(define (zip l0 l1)
  (if (or (empty? l0) (empty? l1))
      '()
      (cons (cons (first l0) (first l1))
            (zip (rest l0) (rest l1)))))

;; Version B

;; (1a)
(define (count-even lst)
  (cond [(empty? lst) 0]
        [(even? (first lst)) (+ 1 (count-even (rest lst)))]
        [else (count-even (rest lst))]))

;; (1b)
(define (interleave l0 l1)
  (if (or (empty? l0) (empty? l1))
      '()
      (cons (first l0)
            (cons (first l1)
                  (interleave (rest l0)
                              (rest l1))))))

;; Version A

;; (2a)
(define (foo x y)
  (if (equal? x 1)
    ;;____________
      (+ 1 (foo y y)) ;; call to + should be circled
         ;;_________
      x))

;; (2b) False

;; (2c)

(define (reverse lst)
  (define (h lst acc) (if (empty? lst)
                          acc
                          (h (rest lst)
                             (cons (first lst) acc))))
  (h lst '()))


(define (filter lst f)
  (define (h lst acc)
    (cond [(empty? lst) (reverse acc)]
          [(f (first lst))
           (h (rest lst) (cons (first lst) acc))]
          [else
           (h (rest lst) acc)]))
  (h lst '()))

;; Version B

;; (2a)
#;(define (foo x y)
  (if (equal? x 1)
    ;;____________
      (foo 5 (+ y y)) ;; call to foo circled
           ;;_______
      x))

;; (2b) False

;; (2c) Same as (2c) on Version A

;; Version A

;; Problem 3

;; (3a)
;; acc0 = ""
;; acc1 = ",world"
;; acc2 = ",world,hello" << ANSWER

;; (3b)
(define (mul-by-k lst k)
  (foldr (λ (x acc) (cons (* k x) acc)) '() lst))

;; Version B

;; (3a) 
;; acc0 = ""
;; acc1 = ",world"
;; acc2 = ",world,hello"

;; (3b)
(define (add-k-to-lst lst k)
  (foldr (λ (x acc) (cons (+ k x) acc)) '() lst))

;; Problem 4

;; Version A
((λ (x) ((λ (x) x) x)) (λ (z) z))
;; there are *two* redexes
;; - the whole expression is a reducible expression
;; - the subordinate application ((λ (x) x) x)

;; for the whole expression
;; ((λ (x) x) x) [ x ↦ (λ (z) z)]
;; ((λ (x) x) (λ (z) z))

;; for the second one, we reduce ((λ (x) x) x)) ⟶β x
;; within the context of ((λ (x) ·) (λ (z) z))
;; so the answer is ((λ (x) x) (λ (z) z))

;; (4c)
;; ((λ (x) (λ (z) z)) Ω)
;; if I repeatedly try to β reduce Ω...
;; ⟶ ((λ (x) (λ (z) z)) Ω) ⟶ ((λ (x) (λ (z) z)) Ω) ...
;; If I do the outer application (λ (z) z)

;; Version B
;; (4a) 

;; I have two reducible expressions here...
((λ (z) ((λ (y) y) z)) (λ (k) k))
;; the whole thing is a redex
;; the inner application of ((λ (y) y) z)

;; (4b)

;; doing the outer application
((λ (y) y) (λ (k) k))

;; doing the inner application
((λ (z) z) (λ (k) k))

;; (4c)
;; Yes, it can reduce to k, even though there's another
;; occurrence of Ω, you can always do the outer
;; application and make progress.


;; In general, a term of size O(n) can have O(n) β redexes...
((λ (x) ((λ (x) (λ (x) x) (λ (x) x)) (λ (x) (λ (x) x) (λ (x) x))))
 (λ (x) ((λ (x) (λ (x) x) (λ (x) x)) (λ (x) (λ (x) x) (λ (x) x)))))

;; The free variables of a term are variables which don't have a
;; definition (binder)
(define (fv exp)
  (match exp
    [(? symbol? x) (set x)]
    [`(λ (,x) ,e-b)
     (set-remove (fv e-b) x)]
    [`(,e-f ,e-a)
     (set-union (fv e-f) (fv e-a))]))

    
     
    
  

3-21-24.rkt

;; CIS352 -- Mar 21, 2024
#lang racket

;; Reduction Strategies

;; Consider the term
;; ((λ (x) k) ((λ (x) (x x)) (λ (x) (x x))))

;; There are two β redexes

;; one β redex says you can reduce the term to itself
;; ((λ (x) k) ((λ (x) (x x)) (λ (x) (x x))))

;; another says you can reduce the term to just k
;; k 

;; In the λ calculus, the only way to introduce a variable
;; is to bind it via a λ

;; In Racket
(let ([x (λ (y) y)])
  (x x))

;; The λ calculus doesn't have let...

;; We can translate lets as "left-left" lambdas
;; Here is an equivalent expression

((λ (x) (x x)) (λ (y) y))

;; α conversion says I can change (λ (x) e)
;; to (λ (y) e [ x ↦ y ]) *provided* that
;; e doesn't contain any free instances of y

;; Why is this important? Because I shouldn't be able to change
;; the meaning of the term by doing the conversion 

;; Everything in the λ calculus is a function. And functions
;; f and g are equal when their extensions are equal
;; i.e., they agree on all points of their domain

;; In math, f ≡ g (f and g functions) whenever ∀x. f(x) = g(x)
;; In λ-calculus, terms e and e+ are equal whenever
;; they behave the same way for all arguments (i.e., I can
;; compute the same set of reductions from them).
(λ (x) (add1 x)) ;; can be α converted to
(λ (y) (add1 y))

;; But NOT to
#;((λ (add1) (add1 add1)) 5) ;; breaks! 
;; but this if fine
;; ((λ (y) (add1 y)) 5)

;; In general, I need to be very careful not to change the
;; meaning of the terms (during reductions) by capturing
;; otherwise-free variables. If I do, I'm forbidding the
;; user from later substituting those free variables
;; for the value they intend, because I've captured
;; (i.e., redefined) those variables.

;; Capture-avoiding substitution
;; The role of capture-avoiding substitution
;; is to formalize our thought process for substitution
;; being thoughtful about the fact that λs create new
;; bindings. We need to be careful not to change the
;; meaning of term by substituting.

;; Ω = ((λ (x) (x x)) (λ (x) (x x)))

;; ((λ (x) (λ (x) x)) Ω)
;; (λ (x) x) [ x ↦ Ω ] 
;; ≡ (λ (x) x) ;; by the fourth case in capture-avoiding substitution

;; Reduction strategies
;; At any point in time, there may be a number of potential
;; β redexes. How do we pick which one to do?

;; Racket is call by value:
;; - Before a function body is entered, the arguments to that
;; function *must* be reduced to values. *Even* when those
;; arguments are never used, dropped on the ground, etc...

;; This will *never* terminate in Racket
;; ((λ (x) (λ (y) y)) ((λ (x) (x x)) (λ (x) (x x))))

;; Because Racket uses call-by-value, i.e., applicative
;; order.

;; η-reduction and expansion observe that λ calculus
;; terms are equal when they produce equal behavior
;; on all of their arguments
;; (λ (x) (e x)) ⟶η e ;; provided x ∉ FV(e)
;; e ⟶η (λ (x) (e x)) ;; provided x ∉ FV(e)

;; In our languages, we never reduce under a λ
;; because we don't want the body of functions
;; to run, until those functions are *actually called*

;; So I can write (λ (x) ....) and it doesn't matter
;; how bad (i.e., what the consequences of) the body
;; is, until I actually execute it.

(define div-0 (λ (x) (/ 1 0)))

;; You *never* want to execute a function's body
;; until you *call* that function.

;; In terms of the λ calculus: we never want to
;; do reduction (α, β, or η) until we get to
;; the function *call*.

;; Weak Head Normal Form (WHNF):
;;
;; Once you get to a λ, you *stop* until that
;; λ is actually applied.
;;
;; A λ-calculus term is in WHNF whenever it
;; is a λ.

;; Exercise:

;; Use call-by-name (i.e., normal order, but under λs)
;; reduction to reduce the following to WHNF
((λ (x) (λ (y) y)) ((λ (x) (x x)) (λ (x) (x x))))

;; Call by *name* immediately terminates, because it "lazily"
;; reduces the expression, skipping β reduction of arguments
;; until they're truly needed.

;; CBN β ⟶ (λ (y) y)

;; CBV β ⟶ ((λ (x) (λ (y) y)) ((λ (x) (x x)) (λ (x) (x x))))
;; CBV β ⟶ ((λ (x) (λ (y) y)) ((λ (x) (x x)) (λ (x) (x x))))
;; CBV β ⟶ ((λ (x) (λ (y) y)) ((λ (x) (x x)) (λ (x) (x x))))
;;  ... and so on...

;; Use CBN and CBV to reduce the following to WHNF
;; ((lambda (x) x) ((lambda (y) y) (lambda (y) y)))
;; ⟶CBN β
;; ((lambda (y) y) (lambda (y) y))
;; ⟶CBN β 
;; (lambda (y) y) <<- in WHNF

;; ((lambda (x) x) ((lambda (y) y) (lambda (y) y)))
;; ⟶CBV β
;; ((lambda (x) x) (lambda (y) y))
;; ⟶CBV β
;; (lambda (y) y) <<- in WHNF
;; and the Church Rosser theorem tells me that these
;; must be the same, up to α equivalence.