Question 1 @ 20210302 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)))))))
 Yes.
 Yes, only if we’re using an eager language.
 Yes, only if we’re using an lazy language.
 They’re equivalent, but wrong.
 They’re equivalent, but wrong: both will loop infinitely.
Question 2 @ 20210302 18:30
Bob finished implementing the Y combinator in a language with
Racketlike 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.)
 Yes. We just moved the
(lambda (n) ((x x) n))
to a new
function and otherwise keept the same functionality.
 Yes. In
newY
, (x x)
does not get evaluated before passed
into protect
as an input, so the behavior is the same.
 Yes. In
newY
, (x x)
is evaluated before passed into
protect
as an input so the behavior is the same.
 No. In
newY
, (x x)
is evaluated before passed into
protect
as an input, and so we will be stuck in an infinite loop.
 It depends.
newY
will work the same way if the language is
eager.
 It depends.
newY
will work the same way if the language is
lazy.
Question 3 @ 20210302 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)
 100 ; [10 * (10+11)]
 10! ; [the factorial of 10]
 11! ; [since it’s 111098 … 32]
 10! * 10 ; [since it’s 101098 … 32]
 10¹⁰ ; [10^10]
 No answer: it will get stuck in an infinite loop.
 It will run out of memory.
 It will fail with an error.
Question 4 @ 20210302 18:39
Which of these is NOT a combinator?
 (lambda (x) (x x))
 (lambda (x) (lambda (y) (x x)))
 (lambda (x) (lambda (y) ((x x) y)))
 (Y (lambda (x) (lambda (y) ((x x) y))))
 of the above are combinators.
 of the above are combinators.
Question 5 @ 20210302 18:44
What do we get if we run the following code:
(define fibstep
(lambda (fib)
(lambda (n) (if (<= n 2) 1 (+ (fib ( n 1)) (fib ( n 2)))))))
(define fib
((lambda (x) (x x))
(lambda (x) (fibstep (x x)))))
(fib 1)
(Choose the best answer.)

We get a result of 1.

We get a result of 1 only if the language is eager.

We get a result of 1 only if the language is lazy.

We get a result of 2.

We get a result of 2 only if the language is eager.

We get a result of 2 only if the language is lazy.

We get an error.

We get an error only if the language is eager.

We get an error only if the language is lazy.