∀x. (F x or ∀x (not (F x)))
+
 Scheme (functional part) OCaml (functional part) C, Java, Python +Scheme (imperative part) +OCaml (imperative part) untyped lambda calculus +combinatorial logic --------------------------------------------------- Turing complete --------------------------------------------------- + more advanced type systems, such as polymorphic types + + + simply-typed lambda calculus (what linguists mostly use) + +
 Scheme (functional part) OCaml (functional part) C, Java, Python +Scheme (imperative part) +OCaml (imperative part) untyped lambda calculus +combinatorial logic --------------------------------------------------- Turing complete --------------------------------------------------- + more advanced type systems, such as polymorphic types + + + simply-typed lambda calculus (what linguists mostly use) + +
+
1. 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. + +
2. Define an `and` operator. + +
3. 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 + + +
4. 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: + + the-value if-black if-white + +(where `if-black` and `if-white` are anything), and get back one of `if-black` or +`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.) + +
5. 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.) +
+ + + +Pairs +----- + +Recall our definitions of ordered pairs. + +> the pair **(**x**,**y**)** is defined to be `\f. f x y` + +To extract the first element of a pair p, you write: + + p (\fst \snd. fst) + +Here are some definitions in Racket: + + (define make-pair (lambda (fst) (lambda (snd) (lambda (f) ((f fst) snd))))) + (define get-first (lambda (fst) (lambda (snd) fst))) + (define get-second (lambda (fst) (lambda (snd) snd))) + +Now we can write: + + (define p ((make-pair 10) 20)) + (p get-first) ; will evaluate to 10 + (p get-second) ; will evaluate to 20 + +If you're puzzled by having the pair 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 pair is a higher-order function. (Consider the similarities between this definition of a pair and a generalized quantifier.) + +If you like, you can disguise what's going on like this: + + (define lifted-get-first (lambda (p) (p get-first))) + (define lifted-get-second (lambda (p) (p get-second))) + +Now you can write: + + (lifted-get-first p) + +instead of: + + (p get-first) + +However, the latter is still what's going on under the hood. (Remark: `(lifted-f ((make-pair 10) 20))` stands to `(((make-pair 10) 20) f)` as `(((make-pair 10) 20) f)` stands to `((f 10) 20)`.) + + +
+
1. Define a `swap` function that reverses the elements of a pair. Expected behavior: + + (define p ((make-pair 10) 20)) + ((p swap) get-first) ; evaluates to 20 + ((p swap) get-second) ; evaluates to 10 + +Write out the definition of `swap` in Racket. + + +
2. Define a `dup` function that duplicates its argument to form a pair +whose elements are the same. +Expected behavior: + + ((dup 10) get-first) ; evaluates to 10 + ((dup 10) get-second) ; evaluates to 10 + +
3. Define a `sixteen` function that makes +sixteen copies of its argument (and stores them in a data structure of +your choice). + +
4. Inspired by our definition of ordered pairs, propose a data structure capable of representing ordered triples. That is, + + (((make-triple M) N) P) + +should return an object that behaves in a reasonable way to serve as a triple. In addition to defining the `make-triple` function, you have to show how to extract elements of your triple. Write a `get-first-of-triple` function, that does for triples what `get-first` does for pairs. Also write `get-second-of-triple` and `get-third-of-triple` functions. + +
5. Write a function `second-plus-third` that when given to your triple, returns the result of adding the second and third members of the triple. + +You can help yourself to the following definition: + + (define add (lambda (x) (lambda (y) (+ x y)))) + + + +