## Syntax

Insert all the implicit `( )`

s and `λ`

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!*

`x x (x x x) x`

**(((**x x**)**(**(**x x**)**x)**)**x**)**`v w (\x y. v x)`

**((**v w**)**(\x**(\**y**(**v x**))**)**)**`(\x y. x) u v`

**((**(\x**(\**y x**)**) u**)**v**)**`w (\x y z. x z (y z)) u v`

**(((**w (\x**(\**y**(\**z**((**x z**)**(y z)**)))**)**)**u**)**v**)**

Mark all occurrences of `(x y)`

in the following terms:

`(\x y.`

__x y__) x y`(\x y.`

__x y__) (__x y__)`\x y.`

__x y__(__x y__)

## 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 `λx`

as `\x`

. If we ever say "reduce" without qualifications, we mean just "beta-reduce" (as opposed to "(beta + eta)-reduce").

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

~~>`\y. y z`

`(\x (x x)) z`

~~>`z z`

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

~~>`\x x`

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

~~>`\y z`

, be sure to change`\z`

to a different variable so as not to "capture"`z`

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

~~>`\y y`

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

umm..., reductions will forever be possible, they just don't "do" much`(\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.

trueis defined to be`\t f. t`

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

.)

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

Define an

`or`

operator.`(define or (lambda (p) (lambda (q) ((p p) q))))`

or:

`(define or (lambda (p) (lambda (q) ((p true) q))))`

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.

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

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

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

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`

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`

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 (&&)`

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`

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*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:

What is a hole? How can we implement it?

A hole is a bound variable.

`30 & < >`

is`lambda x. 30 & x`

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

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`

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

The ideas here are explored further in Chapter 8 of

*The Little Schemer*. There they first introduce the idea of passing function as arguments to other functions, and having functions be the return values from functions. Then the`multirember&co`

function discussed on pp. 137--140 (and the other`...&co`

functions discussed in that chapter) are more complex examples of the kind of strategy used here to define`reverse`

. We will be returning to these ideas and considering them more carefully later in the term.

## Numbers

Given that we've agreed to Church's encoding of the numbers:

`0 ≡ \f z. z`

`1 ≡ \f z. f z`

`2 ≡ \f z. f (f z)`

`3 ≡ \f z. f (f (f z))`

`...`

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:`let cons = \`

__d__ds. \f z. f__d__(ds f z) in ...