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
$0$ times and similarly one
means
applying f
to x
$1$ 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'
, $p$ 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'
, $p$ number of times. Thus ((n f) x)
will result in apllying f
to x
, $p$ 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: $p + 1$ number of times.
Thus effectively if procedure n
applies f
to x
, $p$ times then add-1
applies f
to x
, total: $p + 1$ 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
$q + p$ times, where $p$
is the number of times n
applies f
to x
and $q$ 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 $r_i$ means the result of applying f
to x
$i$ times. Thus ((n f) x)
returns $r_p$. Now this result is passed
to (m f)
, thus f
is applied to r_p
$q$ times. Thus we get $r_{p+q}$.
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