PLQ #6

Question 1 @ 2025-02-18 18:31

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?

A Syntactic evaluator
B Meta evaluator
C Meta-circular evaluator
D Can go either way
E Bogus question, these terms are unrelated in this context

Question 2 @ 2025-02-18 18:33

We’ve talked about the difference between syntactic and meta evaluators. Which of the following features demonstrates a meta evaluator in our Flang language?

With With
Call Call
Fun Fun
Arith Arithmatic operations
None None

Question 3 @ 2025-02-18 18:35

What is the purpose of the Y-combinator?

(Choose the best answer)

A Allow recursive functions in lexically-scoped languages
B Allow recursive functions in dynamically-scoped languages
C Allow recursive functions regardless of scope
D Represent numbers using lambdas
E Often called fix because it can prevent infinite loops in code
F Provides seed capital for start-ups

Question 4 @ 2025-02-18 18:37

Reminder: the Y combinator definition that we used is

(rewrite (protect f) => (lambda (x) (f x)))

(define (make-recursive f)
((lambda (x) (x x)) (lambda (x) (f (protect (x x))))))

Why do we need this “protection”?

A Without it we get a free identifier instead of a recursive reference
B Avoids the problem of laziness
C Avoid infinite loop due to eager evaluation
D Without it we get a lazy Y, so using it will be much slower
E Enables substitution when using lexical scope
F The Y combinator does not need protection

Question 5 @ 2025-02-18 18:45

Reminder: the Y combinator definition that we used is

(rewrite (protect f) => (lambda (x) (f x)))

(define (make-recursive f)
((lambda (x) (x x)) (lambda (x) (f (protect (x x))))))

Why didn’t we use a simple definition for protect

(define (protect f) (lambda (x) (f x)))

A Bogus question: there is no need for this
B Simple definitions don’t work right in a lazy language
C It is wrong to have a function that returns a lambda
D This is in Racket, and there is no need for Y in Racket
E As we’ve seen later, protect is more for clarity, so it’s not needed
F Using a function defeats the purpose, much like defining an if-like function

Question 6 @ 2025-02-18 18:46

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