## Question 1 @ 2023-02-21 18:53

You’re running into a situation where a language that you need to implement is very different from the language you’re implementing it in.

What kind of evaluator would you likely implement for this language?

• Syntactic evaluator
• Meta evaluator
• Meta-circular evaluator
• Can go either way
• None of the above

## Question 2 @ 2023-02-21 18:59

We’ve seen how the core of the Y combinator leads to an inifinte nesting of calls to F:

((lambda (x) (x x))
(lambda (x) (F (x x))))
=>
(F (F (F ...)))

What would we get if we’d change it to:

((lambda (x) (G (x x)))
(lambda (x) (F (x x))))
=>
???

• `(G (F (G (F ...))))`
• `(F (G (F (G ...))))`
• `(G (F (F (F ...))))`
• `(F (G (G (G ...))))`
• It’s an infinite loop anyway, so it doesn’t matter

## Question 3 @ 2023-02-21 19:02

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 4 @ 2023-02-21 19:05

Why do we need “protection” when writing our Y combinator?

• Without it we get a free identifier instead of a recursive reference.
• Avoids the problem of laziness.
• Infinite loops due to eager evaluation.
• Enables substitution when using lexical scope.
• The Y combinator does not need protection.
• Avoids losing recursive references when switching from dynamic to lexical scope.

## Question 5 @ 2023-02-21 19:07

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))))`
• All of the above are combinators.
• None of the above are combinators.