X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment1.mdwn;h=b65cc177f76ebe872a1897d574068ce013b72def;hp=dd1fa12cd0b3c4f29c3d9fa92ed087d85a8870f2;hb=7958db26a9129e5264f05f835090ae894b4f828b;hpb=7e98785584b3e6bef8f331c032e2b41b0c92deea diff --git a/assignment1.mdwn b/assignment1.mdwn index dd1fa12c..b65cc177 100644 --- a/assignment1.mdwn +++ b/assignment1.mdwn @@ -1,4 +1,5 @@ -**Reduction** +Reduction +--------- Find "normal forms" for the following (that is, reduce them as far as it's possible to reduce them): @@ -12,7 +13,8 @@ them): 7. (\x (x x x)) (\x (x x x)) -**Booleans** +Booleans +-------- Recall our definitions of true and false. @@ -24,30 +26,34 @@ In Racket, these can be defined like this: (define true (lambda (t) (lambda (f) t))) (define false (lambda (t) (lambda (f) f))) -* 8. Define a "neg" operator that negates "true" and "false". +* Define a "neg" operator that negates "true" and "false". + Expected behavior: - (((neg true) 10) 20) + (((neg true) 10) 20) evaluates to 20, and - (((neg false) 10) 20) + (((neg false) 10) 20) evaluates to 10. -* 9. Define an "and" operator. +* Define an "and" operator. + +* Define an "xor" operator. -* 10. Define an "xor" operator. (If you haven't seen this term before, here's a truth table: +(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 + true xor true = false + true xor false = true + false xor true = true + false xor false = false ) -* 11. Inspired by our definition of boolean values, propose a data structure -capable of representing one of the two values "black" or "white". If we have +* Inspired by our definition of boolean values, propose a data structure +capable of representing one of the two values "black" or "white". +If we have one of those values, call it a black-or-white-value, we should be able to write: @@ -58,7 +64,7 @@ if-white, depending on which of the black-or-white values we started with. Give a definition for each of "black" and "white". (Do it in both lambda calculus and also in Racket.) -12. Now propose a data structure capable of representing one of the three values +* Now propose a data structure capable of representing one of the three values "red" "green" or "blue," based on the same model. (Do it in both lambda calculus and also in Racket.)