# 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)))))))

• 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 @ 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.)

• 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 @ 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)

• 100 ; [10 * (10+1-1)]
• 10! ; [the factorial of 10]
• 11! ; [since it’s 11109832]
• 10! * 10 ; [since it’s 10109832]
• 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 @ 2021-03-02 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 @ 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.)

• 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.