Hi there.
I am somewhat new to scheme and lisp-style languages in general, and am
attempting to teach myself scheme via SICP using Gambit Scheme. I was hoping
some of you kind people could offer some enlightenment as to what is going on
in a couple of exercises in SICP. (No, I am not an undergraduate looking for
some help with homework :-) I simply never picked up lisp/scheme in my
degree, and am now trying to fill this void). There are two main problems I
am having difficulty with (to this point).
1. Church Numerals
I am currently struggling with exactly what is happening in Exercise 2.5,
concerning the construction of Church numerals.
The exercise as given is
In case representing pairs as procedures wasn't mind-boggling enough,
consider that in a language that can manipulate procedures, we can get
by without numbers (at least so far as integers are concerned) by
implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x)))
(define (1+ n)
(lambda (f) (lambda (x) (f ((n f) x)))))
This representation is known as Church numerals, after its inventor
Alonzo Church, the logician who invented the lambda calculus.
Define one and two directly (not in terms of zero and 1+).
(Hint: Use substitution to evaluate (1+ zero)). Give a direct definition
of the addition operator + (without introducing any auxiliary procedures).
I am reasonably happy that I understand what the intent of the definitions
of zero and 1+ is, ie, representing a number by the repeated application
of a function, but it is not clear to me exactly what is going on in a
computational sense.
My thumbnail description of zero is:
zero takes a procedure f as a parameter, and returns as a value
a procedure that is equivalent to applying f zero times - that is,
the value of (zero f) is the identity procedure.
Substituting the definitions of 1+ and zero in the expression (1+ zero)
I get
(lambda (f) (lambda (x) (f x)))
or descriptively
(1+ zero) takes a procedure f as parameter, and returns as a value
a procedure that is equivalent to applying f to whatever argument
(1+ zero) is applied to - that is, the effect of applying (1+ f)
to value a say, is the value of applying f to a, (f a).
Similarly, the result of (1+ n) is a procedure which, when applied to a
procedure f, returns a procedure equivalent to applying f n+1 times.
The difficulty I have in this process, is that while I can see that this
is what is happening, I have no idea what is happening in lisp/scheme
terms. From what I can see, the value of ((1+ zero) f) is in some sense
equivalent to f, but it will have a different machine representation. To
better understand what was going on, I asked my scheme interpreter to
pretty-print the value of (1+ zero). What I got was
(lambda (f.2) (lambda (x.3) (f.2 ((n.1 f.2) x.3))))
Similarly, I asked it to pretty print the value of (1+ (1+ zero)) and got
(lambda (f.2) (lambda (x.3) (f.2 ((n.1 f.2) x.3))))
In other words, exactly the same.
One thing in particular that is puzzling me is the appearance of the term
n.1 in these expressions. This seems to be an anonymous variable (not
present in the top-level environment) and not passed in as a parameter to
the procedures. However, for the number of times of f is applied by each
resultant procedure to be correct, this must have a particular value stored
somewhere. I really am not sure what is happening in this case.
Can somebody enlighten me as to what is going on in this situation ?
2. Change counting
I also had difficulty with Exercise 1.9, developing an iterative solution
for the change-counting problem.
I seemed to make some progress with this by attempting to write a recursive
solution in terms of reducing the number of types of coin at each step, but
I always seemed to come to a point at which I had code something like
(define (cc amount n-denominations)
(define (iter-cc amount n-denominations n acc)
(cond ((= 0 n-denominations) acc)
((< amount 0) 0)
(else (+ (iter-cc (- amount (top-denom n-denominations))
(div amount (top-denom n-denominations))
0)
(iter-cc amount (- n-denominations 1)
(div amount (top-denom (- n-denominations 1)))
acc)))))
(iter-cc amount n-denominations
(div amount (top-denom n-denominations)) 0))
This exercise seems like such a natural for homework that I am sure someone
out there must have solved it.
The problem I have is that as far as I can see, for the process to be
iterative, and for the accumulator method of carrying pending additions
forward to work, I need the else clause above to have only one call to
iter-cc in it. Of course, I could be wrong. Anyone able to help?
Anyway, thanks for reading this far. I have to say three things have struck
me in my work/play with scheme so far -
- that lisp/scheme is so much more expressive than the languages I have
used in the past (Algol/Pascal/C) that it takes some getting used to
- that SICP is a remarkably clear book so far
- that Marc Feeley deserves my great thanks for such a nice (freeware)
scheme interpreter (Ken Dickins for the port to the Amiga too!)
Anyone interested in becoming email tutor while I (slowly) work my way
through SICP ?
Thanks for your time
Phil Ware
Metal Trades Industry Association
--
-------------------------------------------------------------------------------
Phil Ware ยทยทยท@mtiame.mtia.oz.au
Metal Trades Industry Association of Australia + 61 3 280 0141