PLQ #7Done on:   Tuesday, November 2nd

Question 1 @ 2021-11-02 20:17

Which of the following are correct definitions of list-ref in Schlac with our church-encoded values?

---

• A
  (define list-ref
    (lambda (l n)
      (cdr (n car l))))
• B
  (define/rec list-ref
    (lambda (l n)
      (if (zero? n)
        (car l)
        (list-ref (cdr l) (sub1 n)))))
• C
  (define list-ref
    (lambda (l n)
      (car (n cdr l))))
• D
  (define list-ref
    (lambda (l n)
      (car (n car l))))

Question 2 @ 2021-11-02 20:20

Consider the following expression in plain Racket (#lang pl without the types, or just #lang racket):

How does Racket’s evaluation of this expression behave with each of the different let variants:

1. (let ([a 1] [b (lambda () (+ a c))] [c 2]) (b))
2. (let* ([a 1] [b (lambda () (+ a c))] [c 2]) (b))
3. (letrec ([a 1] [b (lambda () (+ a c))] [c 2]) (b))

The answers are listed in respective order for (1), (2), (3):

---

• A
  undefined a, undefined c, undefined c
• B
  undefined c, undefined c, undefined c
• C
  undefined a, undefined c, 3
• D
  undefined a, 3, 3
• E
  All are valid: 3, 3, 3
• F
  All are invalid: two undefineds, and letrec can only bind to lambda expressions

Question 3 @ 2021-11-02 20:23

Consider the the following Schlac expressions. There is exactly one expression that is different according to its semantics than all of the others. Which one is it?

---

• 1

  (lambda (f) ((lambda (x) (x x)) (lambda (x) (f (x x)))))

• 2

  (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (x x))))

• 3

  (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))

• 4

  (lambda (f) (let ([x (lambda (x) (f (x x)))]) (x x)))
  assuming a let extension, eg: (rewrite (let ([id expr]) body) => ((lambda (id) body) expr))

Question 4 @ 2021-11-02 20:25

One annoyance in auto-curried languages like Schlac is the lack of variable-arity functions. Can this be improved somehow?

For example, can we implement a Racket-like list function?

---

• 1

  We know that functions in these languages can receive any number of arguments, so there is no problem here.

• 2

  This is an inherent limitation in such languages, no way around it.

• 3

  If we’re in an untyped language like Schlac, and if we’re dealing with arguments that can be distinguished from some special value, we could implement this via a function that would repeatedly consume arguments (by returning a function), until it gets to some end-of-arguments marker.

• 4

  If we’re limiting ourselves to lazy languages, then we can use the laziness to check the arguments only when they’re needed, which gives us a way to implement variadic functions as deferred computations.