27/ 為什么 Lisp 沒有指針 (Why Lisp Has No Pointers)

一個理解 Lisp 的秘密之一是意識到變量是有值的棉胀，就像列表有元素一樣夕冲。如同Cons對象有指針指向他們的元素弄砍，變量有指針指向他們的值究反。

;;可以把變量當成一個容器，可以裝不同的東西舟奠。

28/ 函數(shù)copy-list接受一個列表，然后返回此列表的復(fù)本房维。新的列表會有同樣的元素，但是裝在新的Cons對象里：每個cons對象裝在不同的容器中抬纸。

>(setf x '(a b c);;;定義變量x并賦值

y (copy-list x) );;;把容器x中得值咙俩，拷貝一份到容器y

(ABC);結(jié)果，返回最后運算值湿故，此處為y的值

測驗：

* (eql x y)

NIL
* (equal x y)

T

29/ 函數(shù)append返回任何數(shù)目的列表串接 (concatenation)：它復(fù)制所有的參數(shù)阿趁，除了最后一個

* (append '(a b) '(c d) '(t y u) '(y i) '(5 6)? '(c d) 'e) ;;最后一個不為列表形式，其余為列表

(A B C D T Y U Y I 5 6 C D . E)
* (append '(a b) '(c d) '(t y u) '(y i) '(5 6)? '(c d) 'f);;;復(fù)制所有的參數(shù)坛猪，除了最后一個,若末位實參非列表脖阵，則?

(A B C D T Y U Y I 5 6 C D . F)

* (append '(a b) '(c d) );;;;復(fù)制所有列表內(nèi)的參數(shù)，組成新列表.

(A B C D)

30 游程編碼(run-length encoding)

* (defun n-elts (elt n);;;定義函數(shù)名及形參墅茉，此處elt為數(shù)據(jù)列表命黔，非函數(shù)elt
? (if (> n 1);;;;若n大于1，真就斤，否則悍募，假
????? (list n elt);;真，返回n 與elt組成新列表
????? elt));;假洋机，返回elt數(shù)據(jù)列表

作用：判斷n值是否大于1坠宴，若真，則返回n與原列表作為實參組成的新列表绷旗；若假則返回原列表喜鼓。N-ELTS舉例如下

* (n-elts '(4 5 6) 9)

(9 (4 5 6))

* (defun compr (elt n lst) ;;定義函數(shù)名及形參，此處elt 為數(shù)據(jù)列表衔肢，n為計數(shù)器庄岖，初始值不應(yīng)大于1
? (if (null lst) ;;判斷列表是否為空，空則真膀懈，不空則假
????? (list (n-elts elt n));;;真顿锰，繼續(xù)執(zhí)行n-elts 程序，返回新列表(n elt)启搂，n≤1硼控，則（elt）
????? (let ((next (car lst)));;假，定義變量next并賦lst列表的首值
??????? (if (eql next elt);;;判斷變量值與數(shù)據(jù)列表值是否為相同對象胳赌，相同牢撼，真；不同疑苫，假;(實質(zhì)是判斷l(xiāng)st列表中相鄰兩值是否相同）
??????????? (compr elt (+ n 1) (cdr lst));;真熏版，循環(huán)執(zhí)行compr纷责，取n值+1，列表為首值后的新列表撼短。
??????????? (cons (n-elts elt n) ;;假再膳，執(zhí)行n-elts 程序，返回新列表(n elt)曲横；n≤1喂柒，則（elt），確定出cons新組列表返回的第一個值
????????????????? (compr next 1 (cdr lst))))))) ;;;lst首值作為next禾嫉，從第一個開始判斷灾杰，首值后元素組成新列表作為lst，循環(huán)執(zhí)行開始程序

compr舉例：

*? (compr '( 3 5 7) 9 nil);;;;lst為空情況
((9 (3 5 7)));;返回elt與n組成的新列表(n不大于1則返回elt列表值）

* (compr 4 2 nil)

((2 4))

*? (compr 4 1 '(3 4 4 4 3 4 5))

(4 3 (3 4) 3 4 5)

*? (compr 4 0 '(3 4 4 4 3 4 5))

(4 3 (3 4) 3 4 5)

*? (compr 4 2 '(3 4 4 4 3 4 5))

((2 4) 3 (3 4) 3 4 5)

*? (compr 3 1 '(4 4 4 3 4 5))

* (defun compress (x) ;;定義函數(shù)名及形參
? (if (consp x);;;判斷實參是否為列表熙参，是艳吠，真；否孽椰，假
????? (compr (car x) 1 (cdr x));;;;真昭娩，比較列表相鄰兩值是否相等，并統(tǒng)計出連續(xù)相同值得個數(shù)弄屡。取(car x)值到elt题禀，n為1，（cdr x）到lst
????? x));;;假膀捷，直接返回x值

COMPRESS函數(shù)舉例：

* (compress '(1 1 1 0 1 0 0 0 0 人 人 人))

((3 1) 0 1 (4 0) (3 人))

* (compress '(1 1 1 0 1 0 0 0 0 1))

((3 1) 0 1 (4 0) 1)

過程分析：

(compress '(1 1 1 0 1 0 0 0 0 1));;x為 '(1 1 1 0 1 0 0 0 0 1)

執(zhí)行：(if (consp x);;; (1 1 1 0 1 0 0 0 0 1)非空列表迈嘹，真

執(zhí)行：(compr (car x) 1 (cdr x)) 即(compr 1 1 (1 1 0 1 0 0 0 0 1));;compr (elt n lst)注意位置對應(yīng)的變量名。elt存儲了x列表第一個值全庸，n賦值為1秀仲，lst存儲了新列表(cdr x)

執(zhí)行：(if (null lst)即(if (null (1 1 0 1 0 0 0 0 1)) ;;不空，假

不執(zhí)行：(list (n-elts elt n));;;真

執(zhí)行：(let ((next (car lst)))即(let ((next (car (1 1 0 1 0 0 0 0 1))));;假壶笼，壬窠（x列表第二個值）lst列表首值存儲到變量next

執(zhí)行：(if (eql next elt)即(if (eql 1 1);;;比較變量中對象是否相同，elt中存儲x列表第一個值(car x)覆劈，next存儲了lst列表第一個值(car lst)（即x列表第二個值）保礼。實質(zhì)是判斷l(xiāng)st列表中，從第一個位置開始责语，相鄰兩值是否相同）炮障，相同，真坤候；不同胁赢，假

執(zhí)行：(compr elt (+ n 1) (cdr lst))即(compr 1 2 (1 0 1 0 0 0 0 1));;真，elt變量中存儲的值仍為（x列表第一個值）1白筹，n存儲器中值增加1為(+ n 1)=2智末，lst列表更新為(cdr lst)為(1 0 1 0 0 0 0 1)新lst列表橄杨。

2執(zhí)行：(if (null lst)即(if (null (1 0 1 0 0 0 0 1)) ;;不空劫侧，假

2不執(zhí)行：(list (n-elts elt n));;;真

2執(zhí)行：(let ((next (car lst)))即(let ((next (car (1 0 1 0 0 0 0 1))));;假，妊龉凇（x列表第三個值）新lst列表首值存儲到變量next

2執(zhí)行：(if (eql next elt)即(if (eql 1 1);;;比較變量中對象是否相同板熊，elt中存儲列表第一個值(car x)哈恰，next存儲了新lst列表第一個值(car lst)（即x列表第三個值）海诲。實質(zhì)是判斷l(xiāng)st列表中第一個值和第三個值是否相同）洛勉，相同，真纵穿；不同，假

2執(zhí)行：(compr elt (+ n 1) (cdr lst))即(compr 1 3 (0 1 0 0 0 0 1));;真奢人，elt變量中存儲的值仍為（x列表第一個值）1谓媒，n存儲器中值增加1為(+ n 1)=3，新lst列表更新為(cdr lst)為(0 1 0 0 0 0 1) 新lst列表2何乎。

3執(zhí)行：(if (null lst)即(if (null (0 1 0 0 0 0 1)) ;;不空句惯，假

3不執(zhí)行：(list (n-elts elt n));;;真

3執(zhí)行：(let ((next (car lst)))即(let ((next (car (0 1 0 0 0 0 1))));;假，戎Ь取（x列表第四個值）新lst列表2首值存儲到變量next

3執(zhí)行：(if (eql next elt)即(if (eql 0 1);;;比較變量中對象是否相同抢野，elt中存儲列表第一個值(car x)，next存儲了新lst列表2第一個值(car lst)（即x列表第四個值）0各墨。實質(zhì)是判斷l(xiāng)st列表中第一個值和第四個值是否相同）指孤，相同，真贬堵；不同恃轩，假

3不執(zhí)行：(compr elt (+ n 1) (cdr lst));;真

3執(zhí)行：(cons (n-elts elt n) 即(cons (n-elts 1 3) ;;假，執(zhí)行n-elts 程序黎做，返回新列表(n elt)叉跛；n≤1，則（elt）蒸殿。返回列表（3 1）并暫存到cons函數(shù)容器中筷厘，等待最終合成

3執(zhí)行：(compr next 1 (cdr lst))))))) ;;;繼續(xù)執(zhí)行(compr 0 1 (cdr lst))，next（即x列表第四個值）中的0值做為新的elt宏所，n賦值1酥艳，新lst列表2更新為(cdr lst)為(1 0 0 0 0 1) 新lst列表3。

4執(zhí)行：(if (null lst)即(if (null (1 0 0 0 0 1)) ;;判斷新lst列表3楣铁，不空玖雁，假

4不執(zhí)行：(list (n-elts elt n));;;真

4執(zhí)行：(let ((next (car lst)))即(let ((next (car (1 0 0 0 0 1))));;假，雀峭蟆（x列表第五個值）新lst列表3首值存儲到變量next

4執(zhí)行：(if (eql next elt)即(if (eql 1 0);;;比較變量中對象是否相同赫冬，elt中存儲了列表第四個值0浓镜，next存儲了新lst列表3第一個值(car lst)（即x列表第五個值）1。實質(zhì)是判斷l(xiāng)st列表中第四個值和第五個值是否相同）劲厌，相同膛薛，真；不同补鼻，假

4不執(zhí)行：(compr elt (+ n 1) (cdr lst));;真

4執(zhí)行：(cons (n-elts elt n) 即(cons (n-elts 0 1) ;;假哄啄，執(zhí)行n-elts 程序，返回新列表(n elt)风范；n≤1咨跌，則（elt）。返回列表（0）并暫存到cons函數(shù)容器中硼婿，等待最終合成

4執(zhí)行：(compr next 1 (cdr lst))))))) ;;;繼續(xù)執(zhí)行(compr 1 1 (cdr lst))锌半，next（即x列表第五個值）中的1值做為新的elt，n賦值1寇漫，新lst列表3更新為(cdr lst)為(0 0 0 0 1) 新lst列表4刊殉。

5執(zhí)行：(if (null lst)即(if (null (0 0 0 0 1)) ;;新lst列表4不空，假

5不執(zhí)行：(list (n-elts elt n));;;真

5執(zhí)行：(let ((next (car lst)))即(let ((next (car (0 0 0 0 1))));;假州胳，燃呛浮（x列表第六個值）新lst列表4首值存儲到變量next

5執(zhí)行：(if (eql next elt)即(if (eql 0 1);;;比較變量中對象是否相同，elt中存儲x列表第五個值1栓撞，next存儲了新lst列表4第一個值(carlst)（即x列表第六個值）0遍膜。實質(zhì)是判斷l(xiāng)st列表中第五個值和第六個值是否相同），相同腐缤，真捌归；不同，假

5不執(zhí)行：(compr elt (+ n 1) (cdr lst));;真

5執(zhí)行：(cons (n-elts elt n) 即(cons (n-elts 1 1) ;;假岭粤，執(zhí)行n-elts 程序惜索，返回新列表(n elt)；n≤1剃浇，則（elt）巾兆。返回列表（1）并暫存到cons函數(shù)容器中，等待最終合成

5執(zhí)行：(compr next 1 (cdr lst))))))) ;;;繼續(xù)執(zhí)行(compr 0 1 (cdr lst))虎囚，next（即x列表第六個值）中的0值做為新的elt角塑，n賦值1，新lst列表4更新為(cdr lst)為( 0 0 0 1) 新lst列表5淘讥。

6執(zhí)行：(if (null lst)即(if (null (0 0 0 1)) ;;新lst列表5不空圃伶，假

6不執(zhí)行：(list (n-elts elt n));;;真

6執(zhí)行：(let ((next (car lst)))即(let ((next (car (0 0 0 1))));;假，取（x列表第七個值）新lst列表5首值存儲到變量next

6執(zhí)行：(if (eql next elt)即(if (eql 0 0);;;比較變量中對象是否相同窒朋，elt中存儲x列表第六個值0搀罢，next存儲了新lst列表5第一個值(car lst)（即x列表第七個值）0。實質(zhì)是判斷l(xiāng)st列表中第六個值和第七個值是否相同）侥猩，相同榔至，真；不同欺劳，假

6執(zhí)行：(compr elt (+ n 1) (cdr lst));;真.;繼續(xù)執(zhí)行(compr 0 2 (cdr lst))唧取，elt變量中存儲的值為0（x列表第六個值），n存儲器中值增加1為(+ n 1)=2划提，新lst列表5更新為(cdr lst)為( 0 0 1) 新lst列表6枫弟。

7執(zhí)行：(if (null lst)即(if (null (0 0 1)) ;;新lst列表6不空，假

7不執(zhí)行：(list (n-elts elt n));;;真

7執(zhí)行：(let ((next (car lst)))即(let ((next (car (0 0 1))));;假鹏往，让角（x列表第八個值）新lst列表6首值0存儲到變量next

7執(zhí)行：(if (eql next elt)即(if (eql 0 0);;;比較變量中對象是否相同，elt中存儲x列表第六個值0掸犬，next存儲了新lst列表6第一個值(car lst)（即x列表第八個值）0。實質(zhì)是判斷l(xiāng)st列表中第六個值和第八個值是否相同）绪爸，相同湾碎，真；不同奠货，假

7執(zhí)行：(compr elt (+ n 1) (cdr lst));;真.;繼續(xù)執(zhí)行(compr 0 3 (cdr lst))介褥，elt變量中存儲的值為0（x列表第六個值），n存儲器中值增加1為(+ n 1)=3递惋，新lst列表6更新為(cdr lst)為( 0 1) 新lst列表7柔滔。

8執(zhí)行：(if (null lst)即(if (null (0 1)) ;;新lst列表7不空，假

8不執(zhí)行：(list (n-elts elt n));;;真

8執(zhí)行：(let ((next (car lst)))即(let ((next (car (0 1))));;假萍虽，染取（x列表第九個值）新lst列表7首值0存儲到變量next

8執(zhí)行：(if (eql next elt)即(if (eql 0 0);;;比較變量中對象是否相同，elt中存儲x列表第六個值0杉编，next存儲了新lst列表7第一個值(car lst)（即x列表第九個值）0超全。實質(zhì)是判斷l(xiāng)st列表中第六個值和第九個值是否相同），相同邓馒，真嘶朱；不同，假

8執(zhí)行：(compr elt (+ n 1) (cdr lst));;真.;繼續(xù)執(zhí)行(compr 0 4 (cdr lst))光酣，elt變量中存儲的值為0（x列表第六個值）疏遏，n存儲器中值增加1為(+ n 1)=4，新lst列表7更新為(cdr lst)為(1) 新lst列表8。

9執(zhí)行：(if (null lst)即(if (null (1)) ;;新lst列表8不空财异，假

9不執(zhí)行：(list (n-elts elt n));;;真

9執(zhí)行：(let ((next (car lst)))即(let ((next (car (1))));;假倘零，取（x列表第十個值）新lst列表8首值1存儲到變量next

9執(zhí)行：(if (eql next elt)即(if (eql 1 0);;;比較變量中對象是否相同宝当，elt中存儲x列表第六個值0视事，next存儲了新lst列表8第一個值(car lst)（即x列表第十個值）1。實質(zhì)是判斷l(xiāng)st列表中第六個值和第十個值是否相同）庆揩，相同俐东，真；不同订晌，假

9不執(zhí)行：(compr elt (+ n 1) (cdr lst));;真

9執(zhí)行：(cons (n-elts elt n) 即(cons (n-elts 0 4) ;;假虏辫，執(zhí)行n-elts 程序，返回新列表(n elt)锈拨；n≤1砌庄，則（elt）。返回列表（4 1）并暫存到cons函數(shù)容器中奕枢，等待最終合成

9執(zhí)行：(compr next 1 (cdr lst))))))) ;;;繼續(xù)執(zhí)行(compr 1 1 (cdr lst))娄昆，next（即x列表第十個值）中的1值做為新的elt，n賦值1缝彬，新lst列表8更新為(cdr lst)為(nil) 新lst列表9萌焰。

10執(zhí)行：(if (null lst)即(if (null (nil)) ;;新lst列表9空，真

10執(zhí)行：(list (n-elts elt n))即(list (n-elts 1 1));;;真谷浅，執(zhí)行n-elts 程序扒俯，返回新列表(n elt)；n≤1一疯，則（elt）撼玄。返回列表（1），并暫存到cons函數(shù)容器中墩邀，等待最終合成掌猛。

;;;返回(1)到9

10不執(zhí)行：(let ((next (car lst)));;

10不執(zhí)行：(if (eql next elt);;

10不執(zhí)行：(compr elt (+ n 1) (cdr lst));;真

10不執(zhí)行：(cons (n-elts elt n)? (compr next 1 (cdr lst))))))) ;;;

9執(zhí)行：(cons '(4 0) '(1)) ;;;返回8

( (4 0) 1)

6-8不執(zhí)行：(cons (n-elts elt n)? (compr next 1 (cdr lst))))))) ;;返回到上層

5執(zhí)行：(cons '(1) (cons '(4 0) '(1)) ) ;;;返回開始4

((1) (4 0) 1)

4執(zhí)行：(cons '(0)?(cons '(1) (cons '(4 0) '(1) )) ) ;;;返回開始3

( (0) (1) (4 0) 1)

3執(zhí)行：(cons? '(3 1) (cons '(0)?(cons '(1) (cons '(4 0) '(1) )) )) ;;;返回開始2

((3 1) (0) (1) (4 0) 1)

2不執(zhí)行：(cons (n-elts elt n)? (compr next 1 (cdr lst))))))) ;;返回開始

不執(zhí)行：(cons (n-elts elt n)? (compr next 1 (cdr lst))))))) ;;返回終值

總結(jié)：遞歸原理即確定解決問題的規(guī)則，每一層級按此規(guī)則解決問題（看做末端眉睹，得出返回值即認為此層程序執(zhí)行完畢）留潦，并把每層計算的數(shù)值或nil或t返回，代入到上一層級辣往，最終在頂層輸出程序段的最終語句所指定的表達式值兔院。（層層向下分拆邏輯關(guān)系，層層向上歸納返回值站削。

31/ elt函數(shù)坊萝，返回列表某個位置的值(elt? lst n),列表起始位置為0，依次往后累加

? (elt '(1 2 35 7 8 ) 4);;;返回列表第4位置的值

8;;結(jié)果