+++ /dev/null
-Syntax
-------
-
-Insert all the implicit `( )`s and <code>λ</code>s into the following abbreviated expressions. Don't just insert them *freely*; rather, provide the official expression, without any notational shortcuts, that is syntactically identical to the form presented.
-
-*In response to your feedback and questions, we refined the explanation of the conventions governing the use of the `.` shorthand. Thanks!*
-
-1. `x x (x x x) x`
- <code><b>(((</b>x x<b>)</b> (<b>(</b>x x<b>)</b> x)<b>)</b> x<b>)</b></code>
-2. `v w (\x y. v x)`
- <code><b>((</b>v w<b>)</b> (\x <b>(\</b>y <b>(</b>v x<b>))</b>)<b>)</b></code>
-3. `(\x y. x) u v`
- <code><b>((</b>(\x <b>(\</b>y x<b>)</b>) u<b>)</b> v<b>)</b></code>
-4. `w (\x y z. x z (y z)) u v`
- <code><b>(((</b>w (\x <b>(\</b>y <b>(\</b>z <b>((</b>x z<b>)</b> (y z)<b>)))</b>)<b>)</b> u<b>)</b> v<b>)</b></code>
-
-Mark all occurrences of `(x y)` in the following terms:
-
-5. <code>(\x y. <u>x y</u>) x y</code>
-6. <code>(\x y. <u>x y</u>) (<u>x y</u>)</code>
-7. <code>\x y. <u>x y</u> (<u>x y</u>)</code>
-
-Reduction
----------
-
-Find "normal forms" for the following---that is, reduce them until no more reductions are possible. As mentioned in the notes, we'll write <code>λx</code> as `\x`. If we ever say "reduce" without qualifications, we mean just "beta-reduce" (as opposed to "(beta + eta)-reduce").
-
-8. `(\x \y. y x) z` ~~> `\y. y z`
-9. `(\x (x x)) z` ~~> `z z`
-10. `(\x (\x x)) z` ~~> `\x x`
-11. `(\x (\z x)) z` ~~> `\y z`, be sure to change `\z` to a different variable so as not to "capture" `z`
-12. `(\x (x (\y y))) (\z (z z))` ~~> `\y y`
-13. `(\x (x x)) (\x (x x))` umm..., reductions will forever be possible, they just don't "do" much
-14. `(\x (x x x)) (\x (x x x))` that's just mean
-
-
-
-Booleans
---------
-
-For these questions, and the ones on triples below, we're setting them up so as to encourage you to experiment with Racket and to formulate your answer in Scheme/Racket syntax. But you can answer in Lambda Calculus syntax if you prefer.
-
-Recall our definitions of true and false.
-
-> **true** is defined to be `\t f. t`
-> **false** is defined to be `\t f. f`
-
-In Racket, these functions can be defined like this:
-
- (define true (lambda (t) (lambda (f) t)))
- (define false (lambda (t) (lambda (f) f)))
-
-(Note that they are different from Racket's *primitive* boolean values `#t` and `#f`.)
-
-
-15. Define a `neg` operator that negates `true` and `false`.
-
- Expected behavior:
-
- (((neg true) 10) 20)
-
- evaluates to `20`, and
-
- (((neg false) 10) 20)
-
- evaluates to `10`.
-
- (define neg (lambda (p) ((p false) true)))
-
-16. Define an `or` operator.
-
- (define or (lambda (p) (lambda (q) ((p p) q))))
-
- or:
-
- (define or (lambda (p) (lambda (q) ((p true) q))))
-
-
-17. Define an `xor` operator. If you haven't seen this term before, here's a truth table:
-
- true xor true == false
- true xor false == true
- false xor true == true
- false xor false == false
-
- <!-- -->
-
- (define xor (lambda (p) (lambda (q) ((p (neg q)) q))))
-
-
-Triples
--------
-
-Recall our definitions of ordered triples.
-
-> the triple **(**a**, **b**, **c**)** is defined to be `\f. f a b c`
-
-To extract the first element of a triple `t`, you write:
-
- t (\fst snd trd. fst)
-
-Here are some definitions in Racket:
-
- (define make-triple (lambda (fst) (lambda (snd) (lambda (trd) (lambda (f) (((f fst) snd) trd))))))
- (define fst_of_three (lambda (fst) (lambda (snd) (lambda (trd) fst))))
- (define snd_of_three (lambda (fst) (lambda (snd) (lambda (trd) snd))))
-
-Now we can write:
-
- (define t (((make-triple 10) 20) 30))
- (t fst_of_three) ; will evaluate to 10
- (t snd_of_three) ; will evaluate to 20
-
-If you're puzzled by having the triple to the left and the function that
-operates on it come second, think about why it's being done this way: the triple
-is a package that takes a function for operating on its elements *as an
-argument*, and returns *the result of* operating on its elements with that
-function. In other words, the triple is a higher-order function.
-
-
-18. Define the `swap12` function that permutes the elements of a triple. Expected behavior:
-
- (define t (((make-triple 10) 20) 30))
- ((t swap12) fst_of_three) ; evaluates to 20
- ((t swap12) snd_of_three) ; evaluates to 10
-
- Write out the definition of `swap12` in Racket.
-
- (define swap12 (lambda (x) (lambda (y) (lambda (z)
- (lambda (f) (((f y) x) z))))))
-
-
-19. Define a `dup3` function that duplicates its argument to form a triple
-whose elements are the same. Expected behavior:
-
- ((dup3 10) fst_of_three) ; evaluates to 10
- ((dup3 10) snd_of_three) ; evaluates to 10
-
- <!-- -->
-
- (define dup3 (lambda (x)
- (lambda (f) (((f x) x) x))))
-
-20. Define a `dup27` function that makes
-twenty-seven copies of its argument (and stores them in a data structure of
-your choice).
-
- OK, then we will store them in a triply-nested triple:
-
- (define dup27 (lambda (x) (dup3 (dup3 (dup3 x)))))
-
-Folds and Lists
----------------
-
-21. Using Kapulet syntax, define `fold_left`.
-
- # fold_left (f, z) [a, b, c] == f (f (f z a) b) c
- letrec
- fold_left (f, z) xs = case xs of
- [] then z;
- x' & xs' then fold_left (f, f (z, x')) xs'
- end
- in fold_left
-
-
-22. Using Kapulet syntax, define `filter` (problem 7 in last week's homework) in terms of `fold_right` and other primitive syntax like `lambda`, `&`, and `[]`. Don't use `letrec`! All the `letrec`-ing that happens should come from the one inside the definition of `fold_right`.
-
- let
- filter (p, xs) = fold_right ((lambda (y, ys). if p y then y & ys else ys), []) xs
- in filter
-
-23. Using Kapulet syntax, define `&&` in terms of `fold_right`. (To avoid trickiness about the infix syntax, just call it `append`.) As with problem 22 (the previous problem), don't use `letrec`!
-
- let
- xs && ys = fold_right ((&), ys) xs
- # or append (xs, ys) = ...
- in (&&)
-
-24. Using Kapulet syntax, define `head` in terms of `fold_right`. When applied to a non-empty list, it should give us the first element of that list. When applied to an empty list, let's say it should give us `'err`. As with problem 22, don't use `letrec`!
-
- let
- head xs = fold_right ((lambda (y, _). y), 'err) xs
- in head
-
-25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? As with problem 22, don't use `letrec`!
-
- *Here is a boring, inefficient answer*
-
- let
- append (ys, zs) = fold_right ((&), zs) ys; # aka (&&)
- f (y, prev) = append (prev, [y]);
- reverse xs = fold_right (f, []) xs
- in reverse
-
- or (same basic idea, just written differently):
-
- let
- f (y, prev) = fold_right ((&), [y]) prev;
- reverse xs = fold_right (f, []) xs
- in reverse
-
- *Here is an elegant, efficient answer following the [[hint|assignment2 hint]]*
-
- Suppose the list we want to reverse is `[10, 20, 30]`. Applying `fold_right` to this will begin by computing `f (30, z)` for some `f` and `z` that we specify. If we made the result of that be something like `30 & blah`, or any larger structure that contained something of that form, it's not clear how we could, using just the resources of `fold_right`, reach down into that structure and replace the `blah` with some other element, as we'd evidently need to, since after the next step we should get `30 & (20 & blah)`. What we'd like instead is something like this:
-
- 30 & < >
-
- Where `< >` isn't some *value* but rather a *hole*. Then with the next step, we want to plug into that hole `20 & < >`, which contains its own hole. Getting:
-
- 30 & (20 & < >)
-
- And so on. That is the key to the solution. The questions you need to answer, to turn this into something executable, are:
-
- 1. What is a hole? How can we implement it?
-
- A hole is a bound variable. `30 & < >` is `lambda x. 30 & x`.
-
- 2. What should `f` be, so that the result of the second step, namely `f (20, 30 & < >)`, is `30 & (20 & < >)`?
-
- let
- f (y, prev) = lambda x. prev (y & x)
- in ...
-
- 3. Given that choice of `f`, what should `z` be, so that the result of the first step, namely `f (30, z)` is `30 & < >`?
-
- The identity function: `f (30, (lambda y. y))` will reduce to `lambda x. (lambda y. y) (30 & x)`, which will reduce to `lambda x. 30 & x`.
-
- 4. At the end of the `fold_right`, we're going to end with something like `30 & (20 & (10 & < >))`. But what we want is `[30, 20, 10]`. How can we turn what we've gotten into what we want?
-
- Supply it with `[]` as an argument.
-
- 5. So now put it all together, and explain how to express `reverse xs` using `fold_right` and primitive syntax like `lambda`, `&`, and `[]`?
-
- let
- f (y, prev) = lambda x. prev (y & x);
- id match lambda y. y;
- reverse xs = (fold_right (f, id) xs) []
- in reverse
-
-Numbers
--------
-
-26. Given that we've agreed to Church's encoding of the numbers:
-
- <code>0 ≡ \f z. z</code>
- <code>1 ≡ \f z. f z</code>
- <code>2 ≡ \f z. f (f z)</code>
- <code>3 ≡ \f z. f (f (f z))</code>
- <code>...</code>
-
- How would you express the `succ` function in the Lambda Calculus?
-
- let succ = \n. \f z. f (n f z) in ...
-
- Compare the definition of `cons`, which has an additional element:
-
- <code>let cons = \<u>d</u> ds. \f z. f <u>d</u> (ds f z) in ...</code>