笔记 The Little Schemer
杨贵福 2010-09-05
1赞
笔记 The Little Schemer
MIT Press - The Little Schemer - Daniel P. Friedman.pdf
The Little Schemer - 4th Edition.pdf
[2010-08-17 周二 00:40]-
[2010-09-05 周日 20:06]
* define atom?
pp.5 [2010-08-17 周二]
> (define atom?
(lambda (x)
(and (not (pair? x))(not (null? x)))))
> (atom? (quote ()))
#f
* cdr
pp.13 [2010-08-17 周二]
cdr is a list.
What is (cdr (cdr l))
where
l is ((b) (x y) ((c)))
(((c)))
类似的
What is the cdr of l
where
l is ( a b c)
(b c)
* cons
What is the cons of s and l
where s is (banana and)
and
l is (peanut butter and jelly)
((banana and ) peanut butter and jelly)
* cons
What is (cons s l)
where a is ((a b c))
and
l is b
No answer,
since the second argument l must be a list.
* null list
What is (null? (quote ()))
* eq
Is (eq? l1 l2) true or false
where l1 is ()
and
l2 is (strawberry)
No answer, () and (strawberry) are lists.
* eq
Is (eq? n1 n2) true or false
where n1 is 6
and
n2 is 7
No answer,
6 and 7 are numbers.
* eq
Is (eq? (cdr l) a) true or false
where
l is (soured milk)
and
a is milk
No answer,
See The laws of Eq? and Cdr.
Young says, (cdr l) is (milk), which is not an atom.
* lat
True or false: (lat? l)
where l is ()
True,
because it does not contain a list.
* recursion
InsertR
(cons old (cons new (cdr lat)))
* recursion
pp. 62
在定义multinnsertL中,
需要在递归中改变条件。
* recursion
pp.81
We recur with a first argument from which we subtract the second argument. When the function returns, we add 1 to the result.
=> division.
* recur with car
pp. 89
How are insertR* and rember* similar?
They both recur with the car, whenever the car is a list, as well as with the cdr.
* 递归代替迭代
pp.94 leftmose的递归调用方法，是用函数的递归调用代替了迭代。
* S-expression
What is an S-expression?
An S-expression is either an atom or a (possibly empty) list of S-expressions.
* lamda
pp.129
Now what is
(lambda (a)
(lambda (x)
(eq? x a)))
It is a function that, when passed an argument a, returns the function
(lambda (x)
(eq? x a))
where a is just that argument.
* lambda apply
pp.135
如何应用函数
(define multirember-f
(lambda (test?)
(lambda (a lat)
.....
)))
(multirember-f test?) a lat)
multirember-f是这样的函数，以test?作为参数，返回值是一个函数，
返回的函数以 a 和 lat 作为参数。
(multirember-f test?) a lat)
相当于
(foo a lat)
* lambda
应用一个过程
Applying a procedure of lamda
返回函数的函数 的应用语法
pp.130
Do we need to give a name to eq?-salad
No, we may just as well ask
((eq?-c x) y)
where
x is salad
and
y is tuna.
pp. 129
Now what is
(lamda (a)
(lamda (x)
(eq? x a)))
It is a function that, when passed an argument a, returns the function
(lambda (x)
(eq? x a))
where a is jsut that argument.
* closures
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显示变量，不够直观，只能显示应用求值，不能显示代换的过程。
** 手动
: (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))
'()
'()
)
* 图灵机停机
pp. 153
will-stop? 无法定义，因为有的函数不会停止。
* Y-combinator
[http://www.catonmat.net/blog/derivation-of-ycombinator]
解决在函数中应用匿名函数的问题。
1. 使用???替换函名函数，如果执行不到，这代码是可以执行的。
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (
:
: (lambda (list) ; the
: (cond ;
: ((null? list) 0) ; function
: (else ;
: (add1 (??? (cdr list)))))) ; itself
:
: (cdr list))))))
2. 以length为参数以后，下面这段代码需要修正后执行，否则报错 "reference to undefined identifier: ???"
: ((lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list)))))))
: ???)
??? 被改为 length 后可执行。
??? 被改为 '(???) 也可以被执行。
??? 被改为 '() 也可以被执行。
看起来，只要???是个可以被引用的东西就行，但是不能是未定义的。
事实上，lambda (length)的参数不管是什么，都会返回 (lambda (list) 这个函数。
如下实验：
: (((lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (willnot_run_here (cdr list)))))))
: 'place_holer) '() )
下面的代码
: ((lambda (f)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (f (cdr list)))))))
: ((lambda (g)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (g (cdr list)))))))
: ((lambda (h)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (h (cdr list)))))))
: ???)))
"ince the argument names f, g,h in (lambda (f) ...), (lambda (g) ...),
(lambda (h) ...) are independent, we can rename all of them to length,
to make it look more similar to the length function:"
以上并非可以替换名字的原因。
真正的原因是，lamda(f)中的参数f，是lamda(g);
lamda(g)中的参数g，是lambda(h);
而h只是占位符，对程序的求值没有任何作用。
以下代码是上面代码的变形，帮助理解。
: (((lambda (lambda_lambda_place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (lambda_lambda_place_holder (cdr list)))))))
: ((lambda (lambda_place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (lambda_place_holder (cdr list)))))))
: ((lambda (place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (willnot_run_here (cdr list)))))))
: 'place_holder))) '(a b))
下面的代码中，
把lambda(length)作为参数传给lambda (mk-length)
lambda (mk-length) 的执行是以参数作为函数，给这个函数的参数是占位符???；
这个参数此时是 lambda (length)。
lambda (length)的占位符参数没有被求值，函数就结束了。
所以，以下代码能求 '()
: ((lambda (mk-length)
: (mk-length ???))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
下面的代码中
lambda (mk-length)的执行是，
向mk-length传递参数 (mk-length ???)。
这一参数的解释上面已经提到，执行一次lambda (length)。
执行lambda (length)，最后返回的是 length (cdr list)。
即，以lambda (length)作为lambda (length)的参数。
一共执行两次。
: ((lambda (mk-length)
: (mk-length
: (mk-length ???)))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
既然???是占位符，不会被求值，所以可以
: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
所有的length改在mk-length。
传进来的参数确实是它。
代码略去。
然后，length (cdr list) 换成 (mk-length mk-length) (cdr list)。
这样，(mk-length mk-length) 递归地返回 原来的lambda (length) 应用在 (cdr list) 上
: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (mk-length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 ((mk-length mk-length) (cdr list))))))))
其实mk-lenth只执行了一次，然后mk-length参数就是占位符了。
但是，"The function works because it keeps adding recursive uses by passing
mk-length to itself, just as it is about to expire."
递归的跳出条件是(null? list)。
把(lambda (length)移出作为lambda (le)的参数，
(lambda (x)作为le的参数。
代码如下。
: ((lambda (le)
: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (mk-length)
: (le (lambda (x)
: ((mk-length mk-length) x))))))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
Y-combinator如下。
: (define Y
: (lambda (le)
: ((lambda (f) (f f))
: (lambda (f)
: (le (lambda (x) ((f f) x)))))))
匿名函数的应用如下。
: ((Y (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
: '(a b c d e f g h i j))
另一种Y-combinator的写法, [http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/]
and [http://www.stanford.edu/class/cs242/readings/vocabulary.html]
"When applied to a function, returns its fixed point."
: (define y
: (lambda (f)
: ((lambda (x) (f (x x)))
: (lambda (x) (f (x x))))))
参见TLS书(非pdf页码)pp.171，
如何把lambda (length)移出，从而形成了Y-combinatior的框架。
*关键：applying arguemnt lambda on precedure lambda, and eval the augument lambda in precedure lambda.*
另，参考[http://blog.vazexqi.com/2006/07/13/y-combinator]
原来看不懂的一个原因是，这本电子书有缺页。
[The Little Schemer - 4th Edition.pdf]是个更完整的版本。
* value
pp.185
What is (value e)
where
e is (quote nothing)
nothing.
What is (value e)
where
e is nothing.
nothing has no value.
* value
Where is (value e)
where
e is ((lambda (nothing)
(cons nothing (quote ())))
(quote
(from nothing comes something)))
((from nothing comes something))
以 '(from nothing comes something) 作为 lambda(nothing)的参数
实验，Pretty Big
>'(nothing)
(nothing)
> (cons '(nothing) '())
((nothing))
* interpreter
pp. 189
Have we used the table yet?
No, but we will in a moment.
Why do we need the table?
To remember the values of identifiers.
pp. 188
(define value
(lambda (e)
(meaning e (quote ()))))
(define meaning
(lambda (e table)
((expression-to-action e) e table)))
* What is the Value of All of This?
第10章，略读了。
这一部分应该是用 apply & eval 构造解释器。
准备细读《计算机程序的构造和解释》的相应部分。
* laws
** car
The primitive car is defined only for non-empty lists.
Young says: the result is a atom.
** cdr
The primitive cdr is defined only for non-empty lists.
The cdr of any non-empty list is always another list.
** cons
The primitive cons takes two arguments.
The second argument to cons must be a list. The result is a list.
** null?
The primitive null? is defined only for lists.
** eq?
The primitive eq? takes two arguments.
Each must be a non-numeric atom.
** lat
[http://objectmix.com/scheme/186190-newbie-problem-understanding-lat-atom-little-schemer.html]
I bet, they use lat as short for "List of-AToms".
** S-expression
[http://objectmix.com/scheme/186190-newbie-problem-understanding-lat-atom-little-schemer.html]
The S in S-expression stands for symbolic. The word S-expression is
older than Scheme.
** The First Commandment
When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.
When recurring on a number, n, ask two questions about it: (zero? n) and else.
When recurring on a list of S-expressions, l, ask thress question about it: (null? l), (atom? (car l)), and else.
[以下前面的版本]
Always ask null? as the first question in expression any function.
When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.
When recurring on a number, n, ask two questions about it: (zero? n) and else.
** The Second Commandment
Use cons to build lists.
** The Third Commandment
When building a list, describe the first typical element,
and then cons it cons onto the natural recursion.
** The Fourthe Commandment
Always change at least one argument while recurring.
When recurring on a list of atoms, lat, use (cdr lat).
When recurring on a number, n, use (sub1 n).
And when recurring on a list of S-expressions, l, use (car l) and (cdr l)
if neither (null? l) nor (atom? (car l)) are true.
If must be changed to be closer to termination. The changing argument
must be tested in the termination condition:
when useing cdr, test termination with null? and
when using sub1, test termination with zero?.
[以下前面的版本]
Always change at least one argument while recurring. It must be
changed to be closer to termination. The changing argument must be
tested in the termination condition:
when using cdr, test termination with null? and
when using sub1, test termination with zero?.
** The Fifth Commandment
When building a value with +, always use 0 for the value of the
terminating line, for adding 0 does not change the value of an
addition.
When building a vluae with X, alwyas use 1 for the value of the
termination line, for multiplying by 1 does not change the value of a
multiplication.
When building a vluae with cons, always consider () for the value of
the terminating line.
** The Sixth Commandment
Simplify only after the function is correct.
** The Seventh Commandment
Recur on the subparts that are of the same nature:
- On the sublists of a list.
- On the subexpressions of an arithmetic expression.
** The Eight Commandment
Use help functions to abstract from representations.
** The Ninth Commandment
Abstract common patterns with a new function.
** The Tenth Commandment
Build functions to collect more than one value at a time.
* 参考文献
[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]