### Chapter 2, Building Abstractions with Data

### Section - 2.1 - Introduction to Data Abstraction

#### Exercise 2.6

We are given these two procedures:

1
2
3
4

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

The procedure `zero`

accepts an argument `f`

and returns another procedure `(lambda (x) x)`

which returns whatever is passed to it.
Thus procedure `zero`

accepts an argument `f`

and returns an identity procedure.

Now lets find `one`

by expanding `(add-1 zero)`

using substitution:

1
2

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x)))))

It seems like we got stuck here but one more detailed look in last statement reveals that `zero f`

can also be expanded using
substitution. Thus the call `(zero f)`

can be expanded into `(lambda (x) x)`

which is clearly an identity function i.e. it returns
whatever is passed to it. It follows that the invocation `((zero f) x)`

returns `x`

. Thus substituting `x`

inplace of `((zero f) x)`

in the above statement, we get:

1

(lambda (f) (lambda (x) (f x))))

This procedure, similar to `zero`

, accepts an argument `f`

. But unlike `zero`

, it returns a procedure that accepts argument `x`

and applies `f`

to this
argument. In case of `zero`

the procedure returned does not apply `f`

to its argument.

It seems like that `zero`

means applying `f`

to argument, 0 times and `one`

means applying `f`

to argument, 1 times.

Now again we follow the same process to compute `two`

by expanding `(add-1 one)`

:

1
2

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x)))))

Lets expand this part `((one f) x)`

of the above statement. Clearly by the definition of `one`

, invocation: `(one f)`

returns a procedure that
accepts an argument, say a(to avoid conflict with above x), and applies `f`

to this argument and returns the result.
Thus `((one f) x)`

means applying `f`

to `x`

once i.e. `(f x)`

. Thus `((one f) x)`

can be substituted with `(f x)`

in the above
statement:

1

(lambda (f) (lambda (x) (f (f x)))))

It is exactly what we guessed i.e. the procedure `two`

accepts `f`

and returns another procedure that accepts an argument `x`

and returns
the result of applying `f`

**twice** to the argument `x`

.

We can take an example also to verify that procedure `zero`

means applying `f`

to `x`

times and similarly `one`

means
applying `f`

to `x`

times and so on:

1
2
3
4
5
6
7
8
9
10
11
12

> ((zero inc) 500)
500
> ((one inc) 500)
501
> ((two inc) 500)
502
> ((zero dec) 500)
500
> ((one dec) 500)
499
> ((two dec) 500)
498

After understanding this, we can try to make sense of the procedure `add-1`

:

1
2

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

Suppose that `n`

is a procedure that accepts an argument `f'`

and returns another procedure that accepts an argument `x'`

and returns
the result of applying `f'`

to `x'`

, number of times.

Now if we pass this procedure `n`

to `add-1`

, we get the procedure:

1

(lambda (f) (lambda (x) (f ((n f) x)))))

Now we can easily understand the invocation `((n f) x)`

in the above procedure. Clearly `(n f)`

returns a procedure that accepts an argument `x'`

and returns
the result of applying `f`

to `x'`

, number of times. Thus `((n f) x)`

will result in apllying `f`

to `x`

, number of times.

Now the result of `((n f) x)`

is again passed as an argument to `f`

. Thus we get applying `f`

to `x`

, total: number of times.

Thus effectively if procedure `n`

applies `f`

to `x`

, times then `add-1`

applies `f`

to `x`

, total: times.

Now we can easily code for procedure `+`

, which accepts procedures `m`

and `n`

and returns a procedure that takes argument `f`

and
returns another procedure that takes `x`

as argument and returns the result of applying `f`

to `x`

times, where
is the number of times `n`

applies `f`

to `x`

and is the number of times `m`

applies `f`

to `x`

.

1
2
3

(define (+ m n)
(lambda (f) (lambda (x) ((m f) ((n f) x))))
)

Lets say means the result of applying `f`

to `x`

times. Thus `((n f) x)`

returns . Now this result is passed
to `(m f)`

, thus `f`

is applied to `r_p`

times. Thus we get .

We can check our results:

1
2
3
4
5
6
7
8
9
10
11
12

> (define four (+ two two))
> ((four inc) 500)
504
> (define otherzero (+ zero zero))
> ((otherzero inc) 500)
500
> (define onepluszero (+ zero one))
> ((onepluszero inc) 500)
501
> (define eight (+ four four))
> ((eight inc) 500)
508