Question 1 @ 2025-02-25 18:56
We’ve seen that in Schlac, some seemingly unrelated values are actually the same. Which of the following pairs are such values?
Reminder of the relevant definitions:
(define null (lambda (s) #t))
(define #f (lambda (x y) y))
(define #t (lambda (x y) x))
(define 1 (lambda (f x) (f x))) ; orig: (add1 0)
(define id (lambda (x) x))
(define if (lambda (c t e) (c t e)))
(define 2 (lambda (f x) (f (f x)))) ; orig: (add1 1)
Q 1/5: 0 and null
Same, Different
Question 2 @ 2025-02-25 18:58
We’ve seen that in Schlac, some seemingly unrelated values are actually the same. Which of the following pairs are such values?
Reminder of the relevant definitions:
(define null (lambda (s) #t))
(define #f (lambda (x y) y))
(define #t (lambda (x y) x))
(define 1 (lambda (f x) (f x))) ; orig: (add1 0)
(define id (lambda (x) x))
(define if (lambda (c t e) (c t e)))
(define 2 (lambda (f x) (f (f x)))) ; orig: (add1 1)
Q 2/5: 0 and #f
Same, Different
Question 3 @ 2025-02-25 18:59
We’ve seen that in Schlac, some seemingly unrelated values are actually the same. Which of the following pairs are such values?
Reminder of the relevant definitions:
(define null (lambda (s) #t))
(define #f (lambda (x y) y))
(define #t (lambda (x y) x))
(define 1 (lambda (f x) (f x))) ; orig: (add1 0)
(define id (lambda (x) x))
(define if (lambda (c t e) (c t e)))
(define 2 (lambda (f x) (f (f x)))) ; orig: (add1 1)
Q 3/5: 1 and identity
Same, Different
Question 4 @ 2025-02-25 19:00
We’ve seen that in Schlac, some seemingly unrelated values are actually the same. Which of the following pairs are such values?
Reminder of the relevant definitions:
(define null (lambda (s) #t))
(define #f (lambda (x y) y))
(define #t (lambda (x y) x))
(define 1 (lambda (f x) (f x))) ; orig: (add1 0)
(define id (lambda (x) x))
(define if (lambda (c t e) (c t e)))
(define 2 (lambda (f x) (f (f x)))) ; orig: (add1 1)
Q 4+5/5: 1, 2, and if (as a multiple choice question)
1=2, 1=if, 2=if
Question 5 @ 2025-02-25 19:01
Remember that in Schlac we had only curried functions, which that all values are one-argument functions, with multiple arguments simulated via automatic currying.
| (lambda (<id> <id> ...) <SCHLAC-EXPR>)
| (<SCHLAC-EXPR> <SCHLAC-EXPR> <SCHLAC-EXPR> ...)
Note that one thing that we do NOT have here are no-argument (nullary) functions. An interesting question here is whether we lose anything as a result.
I’ll spoil it for you: we don’t lose anything.
This is because of several features of the language. Which ones are they?
(Hint: consider what such nullary functions are useful for in languages that you know.)
- Schlac is lazy
- Schlac is implemented in an eager language
- Schlac is Lisp-like in its S-expression syntax
- The Schlac computational model uses substitutions
- Schlac has no side effects (it is pure)
- Schlac is evaluated by rewrites, no traditional vector-based memory and no stack
Question 6 @ 2025-02-25 19:05
Reminder: here are some number-related definitions from our Schlac encodings:
(define add1 (lambda (n) (lambda (f x) (f (n f x)))))
(define zero? (lambda (n) (n (lambda (x) #f) #t)))
Let’s define a very big number (it’s around 1e+10k):
Converting a church numeral to a Racket natural number via ->nat
actually iterates through the functions one by one, making (->nat yooooje) impossible to run.
Remembering that it is a lazy language, how much time would it take to run the following test
in terms of n, the resulting number?
- O(1): Constant time
- O(1): but the constant is large
- O(n): Linear time
- O(log(n)): Log time
- O(nᵏ): Polynomial time
- O(2ⁿ): Exponential time
- Tricky question: it is practically undecidable (equivalent to the halting problem given the size of the number)
Question 7 @ 2025-02-25 19:10
We can summarize what we did last week as starting with a very small language and use encodings implement natural numbers, booleans, and lists.
Obviously, none of these are required, since they’re all implemented on top of Schlac, so we could use it just the same without the extra definitions. So all of that just makes it convenient to use it as a normal language.
Consider the prospect of keeping things convenient but implementing
less: skip the encoding of booleans (#t / #f) and use numbers
instead — 0 instead of #f and non-0 numbers instead of #t.
What can we say about this?
-
This wouldn’t work, since conditionals are required for any kind of code.
-
This cannot be done, since we need exactly two values for true/false, so “non-
0” numbers as “truthy” values will not work. -
Not only can this be done, but we won’t need to make any changes, since we already defined
0the same as#f. -
This could be done, but we will need to implement
ifin a different way, effectively making it do whatzero?did previously, so the result would be a similar implementation overall. -
This could be done, and not having to define boolean-related functionality would make the whole thing much shorter.
Question 8 @ 2025-02-25 19:12
In Schlac, we know that for any expression F, the following holds:
OTOH, this is not generally true in Racket. One reason is that it is
true as long as F evaluates to a single-argument function, which is
always true in Schlac, but that’s not the case in Racket.
The question is: other than that, is this true in Racket too?
(Hint: think about what we did two weeks ago.)
- Yes.
- Yes, because Racket is eager.
- Yes, because Racket is lazy.
- No.
- No, because Racket is eager.
- No, because Racket is lazy.