PLQ #6Done on:   Tuesday, March 2nd

Question 1 @ 2021-03-02 18:25

Warmup question:

Are the following two definitions of Y valid and equivalent?

(define Y1
  (lambda (f)
    ((lambda (x) (f (lambda (n) ((x x) n))))
    (lambda (x) (f (lambda (n) ((x x) n)))))))

(define Y2
  (lambda (f)
    ((lambda (x) (x x))
    (lambda (x) (f (lambda (n) ((x x) n)))))))

Question 2 @ 2021-03-02 18:30

Bob finished implementing the Y combinator in a language with Racket-like syntax.

(define (Y f)
  ((lambda (x) (x x))
  (lambda (x) (f (lambda (n) ((x x) n))))))

Bob now wants to move part of the Y combinator into a helper function because he is a good Fundies 1 student who uses helper functions.

(define (protect anything)
  (lambda (n) (anything n)))
(define (newY f)
  ((lambda (x) (x x))
  (lambda (x) (f (protect (x x))))))

Will this newY combinator work in the same way as the first?

(Choose the best answer.)


Question 3 @ 2021-03-02 18:35

What will the following code produce when run?

#lang pl broken

(define (Y f)
  ((lambda (x) (f (lambda (n) ((x x) n))))
  (lambda (x) (f (lambda (n) ((x x) n))))))

(define add1 (lambda (x) (+ x 1)))

(define fact
  (Y (lambda (add1)
      (lambda (x) (if (zero? x) 1 (* x (add1 (- x 1))))))))

(fact 10)

Question 4 @ 2021-03-02 18:39

Which of these is NOT a combinator?


Question 5 @ 2021-03-02 18:44

What do we get if we run the following code:

(define fib-step
  (lambda (fib)
    (lambda (n) (if (<= n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
(define fib
  ((lambda (x) (x x))
  (lambda (x) (fib-step (x x)))))

(fib 1)

(Choose the best answer.)