读 The Little Schemer
* pp. 137开始。递归太复杂。
** [http://www.michaelharrison.ws/weblog/?p=34]
:
: (define multirember&co
: (lambda (a lat col)
: (cond
: ((null? lat)
: (col '() '()))
: ((eq? (car lat) a)
: (multirember&co a
: (cdr lat)
: (lambda (newlat seen)
: (col newlat
: (cons (car lat) seen)))))
: (else
: (multirember&co a
: (cdr lat)
: (lambda (newlat seen)
: (col (cons (car lat) newlat)
: seen)))))))
基于closures的解释，参见文献[1]。
** 文献[2]提到，可以用Dr.Scheme 语言Pretty Big的debug观察。
实验。定义multirember&co以后。Dr.Scheme, Pretty Big.
: >(define foo
: (lambda (x y)
: (length x)))
:
: > (multirember&co 'tuna '(tuna aa bb cc) foo)
: 3
** 尝试用drscheme"展开"闭包，不支持；求助刘典，用display显示变量，不够直观，只能显示应用求值，不能显示代换的过程。
** QUOTE 手动
: (define multirember&co
: (lambda (a lat col)
: (cond
: ((null? lat)
: (col '() '()))
: ((eq? (car lat) a)
: (multirember&co a
: (cdr lat)
: (lambda (newlat seen)
: (col newlat
: (cons (car lat) seen)))))
: (else
: (multirember&co a
: (cdr lat)
: (lambda (newlat seen)
: (col (cons (car lat) newlat)
: seen)))))))
: (define foo
: (lambda (x y)
: (length x)))
:
: ultirember&co 'tuna '(tuna aa bb cc) foo)
substitute:
The arguments of calling multirember&co:
| calling | current lat | col | col, substituted a and lat
| col, substituted lambda |
| multirember&co | | |
| |
|----------------+-----------------+-----+----------------------------+-------------------------|
| 1st round | (tuna aa bb cc) | col | /
| lambda (x y)(length x) |
The arguments of calling multirember&co:
| calling | current lat | col, before substitution
| col, substituted a and lat
| col, substituted lambda
|
| multirember&co | |
|
|
|
|----------------+-----------------+---------------------------------------------------------+----------------------------------------------------------------------+-------------------------------------------------------------------------------------------|
| 2nd round | (tuna aa bb cc) | lambda (newlat seen) (col newlat
(cons (car lat) seen)) | lambda (newlat seen) (col newlat (cons (car
'(tuna aa bb cc)) seen)) | lambda (newlat seen) ((lambda (x y)(length
x)) newlat (cons (car '(tuna aa bb cc)) seen)) |
Note:
In the expression
: lambda (newlat seen) (col newlat (cons (car lat) seen))
lat is (tuna aa bb cc), insetead of (aa bb cc).
The substitution happens before multirember&co is called,
so the lat is the original one without cdr applying.
Sic passim.
End of the note.
The col
lambda (newlat seen) ((lambda (x y)(length x)) newlat (cons (car
'(tuna aa bb cc)) seen))
is from:
lambda (newlat seen)
((lambda (x y)(length x))
newlat
(cons (car '(tuna aa bb cc)) seen))
The arguments of calling multirember&co:
| calling | current lat | col, before substitution
| col, substituted a and lat
| col, substituted lambda
|
| multirember&co | |
|
|
|
|----------------+-------------+---------------------------------------------------------+-----------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------|
| 3rd round | (aa bb cc) | lambda (newlat seen) (col (cons (car
lat) newlat) seen) | lambda (newlat seen) (col (cons (car '(aa bb cc))
newlat) seen) | lambda (newlat seen) ((lambda (newlat seen) ((lambda
(x y)(length x)) newlat (cons (car '(tuna aa bb cc)) seen))) (cons
(car '(aa bb cc)) newlat) seen) |
The col
lambda (newlat seen) ((lambda (newlat seen) ((lambda (x y)(length x))
newlat (cons (car '(aa bb cc)) seen))) (cons (car '(bb cc)) newlat)
seen)
is from:
lambda (newlat seen)
((lambda (newlat seen) ((lambda (x y)(length x)) newlat (cons (car
'(aa bb cc)) seen)))
(cons (car '(aa bb cc)) newlat)
seen)
The arguments of calling multirember&co:
| calling | current lat | col, before substitution
| col, substituted a and lat
| col, substituted lambda
|
| multirember&co | |
|
|
|
|----------------+-------------+---------------------------------------------------------+--------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 4th round | (bb cc) | lambda (newlat seen) (col (cons (car
lat) newlat) seen) | lambda (newlat seen) (col (cons (car '(bb cc))
newlat) seen) | lambda (newlat seen) ((lambda (newlat seen) ((lambda
(newlat seen) ((lambda (x y)(length x)) newlat (cons (car '(tuna aa bb
cc)) seen))) (cons (car '(aa bb cc)) newlat) seen)) (cons (car '(bb
cc)) newlat) seen) |
The col
lambda (newlat seen) ((lambda (newlat seen) ((lambda (newlat seen)
((lambda (x y)(length x)) newlat (cons (car '(tuna aa bb cc)) seen)))
(cons (car '(aa bb cc)) newlat) seen)) (cons (car '(bb cc)) newlat)
seen)
is from:
lambda (newlat seen)
((lambda (newlat seen) ((lambda (newlat seen) ((lambda (x y)(length
x)) newlat (cons (car '(tuna aa bb cc)) seen))) (cons (car '(aa bb
cc)) newlat) seen))
(cons (car '(bb cc)) newlat)
seen)
The arguments of calling multirember&co:
| calling | lat | col, before substitution
| col, substituted a and lat
| col, substituted lambda |
| multirember&co | for multirember&co |
|
| |
|----------------+---------------------+---------------------------------------------------------+-----------------------------------------------------------+-------------------------|
| 5th round | (cc) | lambda (newlat seen) (col
(cons (car lat) newlat) seen) | lambda (newlat seen) (col (cons (car
'(cc)) newlat) seen) | |
The col
lambda (newlat seen) ((lambda (newlat seen) ((lambda (newlat seen)
((lambda (newlat seen) ((lambda (x y)(length x)) newlat (cons (car
'(tuna aa bb cc)) seen))) (cons (car '(aa bb cc)) newlat) seen)) (cons
(car '(bb cc)) newlat) seen)) (cons (car '(cc)) newlat) seen)
is from:
lambda (newlat seen)
((lambda (newlat seen) ((lambda (newlat seen) ((lambda (newlat seen)
((lambda (x y)(length x)) newlat (cons (car '(tuna aa bb cc)) seen)))
(cons (car '(aa bb cc)) newlat) seen)) (cons (car '(bb cc)) newlat)
seen))
(cons (car '(cc)) newlat)
seen)
There is no 6th round of calling multirember&co, because of cond fullfilled.
: ((null? lat)
: (col '() '()))
Current lat is (cdr '(cc)), as '().
The procedure col has been subsitituted in the previous steps to be
: lambda (newlat seen) ((lambda (newlat seen) ((lambda (newlat seen)
((lambda (newlat seen) ((lambda (x y)(length x)) newlat (cons (car
'(tuna aa bb cc)) seen))) (cons (car '(aa bb cc)) newlat) seen)) (cons
(car '(bb cc)) newlat) seen)) (cons (car '(cc)) newlat) seen)
Eval (applying '() '() as arguements on col);
(col '() '())
=>
((lambda (newlat seen) ((lambda (newlat seen) ((lambda (newlat seen)
((lambda (newlat seen) ((lambda (x y)(length x)) newlat (cons (car
'(tuna aa bb cc)) seen))) (cons (car '(aa bb cc)) newlat) seen)) (cons
(car '(bb cc)) newlat) seen)) (cons (car '(cc)) newlat) seen))
'()
'()
)
* 参考文献
[1] [http://www.michaelharrison.ws/weblog/?p=34]
Unpacking multirember&co from TLS The purpose of The Little Schemer,
its authors profess, is to teach you to think recursively, and to do
so without presenting too much math or too many computer science
concepts. The book is a ball to read. However, from the perspective of
this reader, who is fairly new to functional programming and totally
new to Scheme, the book gets almost asymptotically more difficult and
complicated towards the end of chapter 8, when we hit the function
multirember&co. Looking around on the web, I noticed quite a few
people had also hit this speed bump and were scratching their heads
about how to go on. I think I can offer some assistance. So, as
threatened yesterday, I now unveil my initial contribution to the wild
world of Lisp, my explication of multirember&co and the concept of
currying. Here's hoping I don't embarrass myself too much.
The Little Schemer, (hereafter "TLS") is the latest iteration of The
Little LISPer, and is presented as a dialogue between teacher and
student. If you take the roll of the student, and try to answer the
teacher's questions, especially those of the form "define this
function whose behavior we've been describing," you can really flex
your neurons. Each chapter is a little more complicated than the
previous, and within each chapter the questions get slightly harder as
you go. It's like walking up a steadily graded hill. Until you get to
page 137 and they hit you with a long function definition, for a
function you've never seen before, and they ask, "What does this do?"
Yikes!
Here is the code for the function. (Thank you, Geoffrey King, for
transcribing it in your post.)
(define multirember&co
(lambda (a lat col)
(cond
((null? lat)
(col '() '()))
((eq? (car lat) a)
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col newlat
(cons (car lat) seen)))))
(else
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col (cons (car lat) newlat)
seen)))))))
The first clue to dealing with this function is its context. The
previous pages of TLS deal with currying, in which you define a
function like (lambda (x) (lambda(y) (eq? x y) )) — it takes one
argument, parameter x, and then returns the inner function, which also
takes one argument, parameter y. The value you pass as x acts to
customize the inner function by binding the occurance of variable x in
the inner function to the value you passed in. So chapter 8 is about
the practice of wrapping functions in this way.
The chapter is also about passing functions as arguments. The first
line of multirember&co, (lambda (a lat col) defines three
parameters. The variables 'a' and 'lat' are by convention used for an
atom and a list of atoms. But 'col' is a function–you have to pass
multirember&co a function that it uses inside its own definition.
TLS admits that multirember&co is complicated. "That looks really
complicated!" says the student. But it seeks to simplify the function
by defining functions to stand in for a) the function that will be
passed as 'col'; b) the first inner function defined in the cond
branch (eq? (car lat) a); and c) the inner function defined in the
cond else branch. To try to make you feel better about being up to
your eyelids in deep water, the TLS authors give their functions
friendly names, like "a-friend" and "next-friend." But I prefer names
that tell me what roll the functions play, so here are my renamed
functions:
a) the function that will be passed initially as 'col' (and will be
executed last):
(define last-function
(lambda(x y) (length x)))
b) the function called when a matches (car lat):
(define when-match
(lambda (newlat seen) (col newlat (cons (car lat) seen)))
c) the function called when the cond else branch executes:
(define when-differ
(lambda (newlat seen) (col (cons (car lat) newlat) seen))
TLS walks you through an execution of multirember&co, and so will
I. To further simplify things, and reduce the amount of typing I have
to do, I'll change the example in the book. Instead of a four-word lat
with some longer words, let's use (berries tuna fish) for our list,
and we'll keep tuna as our atom argument.
Here's multirember&co, with the two inner functions replaced by the
pre-defined helper functions:
(define multirember&co
(lambda (a lat col)
(cond
((null? lat)
(col '() '()))
((eq? (car lat) a)
(multirember&co a
(cdr lat)
(when-match)))
(else
(multirember&co a
(cdr lat)
(when-differ))))))
When the function is called the first time, a is tuna, lat is (berries
tuna fish), and col is last-function. (car lat) is berries, which does
NOT eq tuna, so the else branch executes: multirember&co is called
with tuna as a, (tuna fish) as lat because we pass (cdr lat) and so we
lose the berries atom at the front of the list, and when-differ as
col.
But wait. Actually, we're not just passing the when-differ function we
defined above. Here is that definition:
(lambda (newlat seen) (col (cons (car lat) newlat) seen))
This definition contains a variable, lat, that has a value at the time
multirember&co is called recursively: (berries tuna fish). So (car
lat) is (quote berries). What we've got here is a version, or an
instance, of when-differ that has a value bound to one of its
variables.
This is like currying, this binding of values to the variable of a
function and then using this altered function to do something. I think
that currying, however, refers to wrapping functions so that only one
variable at a time is given a value. What this apparent creation of a
specific instance of the function when-differ DOES have in common with
currying is this: both use closures to encapsulate the instance of the
function with bound variables, or, to be precise, to make a copy of
the function with its own scope that will persist so long as there are
references to the closure. I didn't realize this on my own, of
course. I owe this insight to Richard P. Gabriel's essay The Why of Y,
which you can read in this Dr. Dobb's article or download as a PDF.
There's something else in when-differ that will bind to a value:
col. The function passed, remember, is last-function. So we can (and
should) substitute that in for col.
Let's give a unique name to the instance (technically the closure) of
the function when-differ that has these two values bound to it:
when-differ-1. Let's write it out, and set it aside for later use:
(define when-differ-1
(lambda (newlat seen) (last-function (cons (quote berries) newlat) seen))
)
Now, on to iteration two, which we can summarize like this:
(multirember&co (quote tuna) (tuna fish) when-differ-1)
OK, so this time, (eq? (car lat) a) yields true, and the other branch
of the condexecutes: multirember&co is called with tuna as a, (fish)
as lat, and when-match as col. Once again, thanks to currying, the
definition of when-match contains expressions to which values are
bound:(car lat), which becomes (quote tuna) , and col, which becomes
when-differ-1. Remember, we just recurred by calling multirember&co
with when-differ-1 as the function argument for the parameter col. So
now let's define the resulting instance of when-match as when-match-1:
(define when-match-1
(lambda (newlat seen) (when-differ-1 newlat (cons (quote tuna) seen)))
)
On on to iteration three–we're nearly there–which we can summarize
like this:
(multirember&co (quote tuna) (fish) when-match-1)
This time, tuna and fish don't match, which means we're going to recur
with another version of when-differ, when-differ-2:
(define when-differ-2
(lambda (newlat seen) (when-match-1 (cons (quote fish) newlat) seen))
)
Finally, iteration four:
(multirember&co (quote tuna) () when-differ-2)
This time lat is an empty list, which means (null? lat) is true, and
the terminating line (col (quote()) (quote())) is executed. Yay! We're
done!
Except…
The result of the completed execution (col (quote()) (quote())) has to
be evaluated. Here's where everything turns inside out, or rightside
out if you like.
First of all, the value of col in the final iteration was
when-differ-2. So we'll start there.
(when-differ-2 (quote()) (quote()))
Now, look back up and get the definition of when-differ-2 and
substitute it.
((lambda (newlat seen) (when-match-1 (cons (quote
fish) newlat) seen)) (quote()) (quote()))
OK, so the parameters newlat and seen both get assigned the value of
an empty list:
(when-match-1 (cons (quote fish) (quote())) (quote()))
We can simplify this by consing fish onto the empty list:
(when-match-1 (fish) (quote()))
We have a definition for when-match-1 too. Let's substitute that in now.
((lambda (newlat seen) (when-differ-1 newlat (cons (quote tuna)
seen))) (fish) (quote())) )
And again assign values, this time (fish) and () to newlat and seen:
(when-differ-1 (fish) (tuna))
We're getting somewhere now. Do you see how at each step we're consing
a value onto either seen or newlat? seen has gotten the instance of
tuna, which was the atom we passed to multirember&co at the start,
whereas newlat has gotten the other atom, fish. Guess where berries is
going to go when we get to it.
Now, let's substitute our definition of when-differ-1:
((lambda (newlat seen) (last-function (cons (quote berries) newlat)
seen)) (fish) (tuna))
Which becomes….
(last-function (berries fish) (tuna) )
And now we're back where we started, with last-function.
( (lambda(x y) (length x)) (berries fish) (tuna) )
(length (berries fish) )
2
So that's how multirember&co works. What does it accomplish? It seems
to separate occurrences of the atom a in the list of atoms lat from
the other atoms in lat, and then it executes last-function using the
list of occurrences and the list of other atoms.
In an imperative language like C or Java, you would probably define
two variables, one for each list, and then loop through the list of
atoms, testing each element in the list for equality with a, and then
pushing the element onto either of the two lists. Finally, you would
call the final function with the two lists you built.
Consider the differences in this approach. Throughout the loop, you
have several variables remaining in scope, which means you have an
opportunity to munge one of them accidentally. Also, how modular is
this hypothetical code? In C, you could pass the last-function
function as an argument to a procedure that encapsulates the loop, but
try it in Java. No sir, in Java you'd have to call a method to get the
two lists (which would have to come back wrapped into one object,
probably a String[] array) and then call last-function with returnval[
0 ] and returnval[ 1 ]. Not terrible, but not elegant either.
That's just scratching the surface, I'm sure. If the example were more
complicated, other implications of the recursive approach might become
clear, at least to smarter people than me. But there is one other
thing to point out.
As TLS points out, the function you supply for use with the two lists
is assigned to a parameter names col because "col" stands for
"collector" by convention. What is this function collecting? The two
lists, of course. But more than that each use of col, as it changes
from when-differ to when-match, is persisting the values of the lists
from one step to the next. And that's important because as of page
136, there has been no mention in TLS of an assignment operator. So
even if we wanted to define variables to reference while looping
through the list, we could not. Not yet. After all, such code would
produce what functional programmers refer to, with a sniff, as side
effects.
[2] [http://www.rhinocerus.net/forum/lang-scheme/100568-how-why-did-they-do.html]
