## Reduction

Find "normal forms" for the following---that is, reduce them until no more reductions are possible. We'll write `λx`

as `\x`

.

`(\x \y. y x) z`

`(\x (x x)) z`

`(\x (\x x)) z`

`(\x (\z x)) z`

`(\x (x (\y y))) (\z (z z))`

`(\x (x x)) (\x (x x))`

`(\x (x x x)) (\x (x x x))`

## Booleans

Recall our definitions of true and false.

trueis defined to be`\t \f. t`

falseis defined to be`\t \f. f`

In Racket, these can be defined like this:

```
(define true (lambda (t) (lambda (f) t)))
(define false (lambda (t) (lambda (f) f)))
```

- 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 an
`and`

operator. - 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`

- 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.) - 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)`

.)

- 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. - 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`

- Define a
`sixteen`

function that makes sixteen copies of its argument (and stores them in a data structure of your choice). - 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. - 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))))`