author Jim Sun, 8 Feb 2015 00:30:38 +0000 (19:30 -0500) committer Jim Sun, 8 Feb 2015 00:30:38 +0000 (19:30 -0500)
 topics/_assignment2.mdwn [new file with mode: 0644] patch | blob

diff --git a/topics/_assignment2.mdwn b/topics/_assignment2.mdwn
new file mode 100644 (file)
index 0000000..2ca8ede
--- /dev/null
@@ -0,0 +1,109 @@
+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>&lambda;x</code> as `\x`. If we ever say "reduce" without qualifications, we mean just "beta-reduce" (as opposed to "(beta + eta)-reduce").
+
+1. `(\x \y. y x) z`
+2. `(\x (x x)) z`
+3. `(\x (\x x)) z`
+4. `(\x (\z x)) z`
+5. `(\x (x (\y y))) (\z (z z))`
+6. `(\x (x x)) (\x (x x))`
+7. `(\x (x x x)) (\x (x x x))`
+
+
+Booleans
+--------
+
+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`.)
+
+<OL start=8>
+<LI>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.
+
+<LI>Define an `or` operator.
+
+<LI>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
+
+</OL>
+
+
+
+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 pair
+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.
+
+
+<OL start=13>
+<LI>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.
+
+
+<LI>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
+
+<LI>Define a `dup27` function that makes
+twenty-seven copies of its argument (and stores them in a data structure of
+your choice).
+
+</OL>
+
+