第十一章 迭代和塊結(jié)構(gòu)
11.1 導(dǎo)語
名詞“迭代”的意思就是重復(fù)昧互，或者說一遍又一遍的做一件事情。遞歸和函數(shù)式操作就是重復(fù)的伟桅，但是迭代（iteration）（也被稱作循環(huán)（looping））是一個最簡單的循環(huán)（repetitive）控制結(jié)構(gòu)敞掘。實際上，所有的編程語言都會包括一些寫迭代表達(dá)式的方法贿讹。
在lisp中的迭代比大部分其他語言要更加精妙一些渐逃。Lisp提供強大的迭代結(jié)構(gòu)，叫做do和do * 民褂。還有更簡化的版本叫做dotimes和dolist茄菊。
在本章我們也會學(xué)習(xí)塊結(jié)構(gòu)，一個從algol族語言（包括pascal赊堪，modula面殖，ada）中引申過來的概念，我們可以看到如何將表達(dá)式組織進(jìn)塊（blocks）中哭廉，如何給塊命名脊僚，以及為什么塊很有用。
11.2 dotimes和dolist
最簡單的迭代格式就是dotiimes和dolist遵绰，兩個都是宏函數(shù)辽幌，就是說他們不會對所有參數(shù)求值，他們有相同的語法椿访。
dotimes會發(fā)福對函數(shù)體內(nèi)的語句求值n次乌企，次數(shù)是由一個步進(jìn)的所因變量控制，從0一直到n-1成玫。然后就會返回結(jié)果語句的值加酵，如果忽略的話默認(rèn)就是nil。（結(jié)果語句是括起來的因為是可選的）下面是一個dotimes的例子哭当，從0數(shù)到3.索引變量被命名為I猪腕，請注意dotimes返回的結(jié)果是nil。
dolist和dotimes的語法是一樣的钦勘，只是把步進(jìn)的數(shù)字替換成了步進(jìn)的元素列表陋葡。在接下來的例子中，dolist返回的值是字符flowers彻采。
11.3 離開循環(huán)體
不想再繼續(xù)循環(huán)脖岛，想馬上離開循環(huán)提的時候朵栖，可以調(diào)用return函數(shù)，return函數(shù)接受一個輸入柴梆，返回的值就作為迭代語句的結(jié)果。當(dāng)return函數(shù)被用在強制結(jié)束迭代的時候终惑，迭代的結(jié)果語句表達(dá)式將會被忽略绍在。
一個叫做find-first-odd的函數(shù)返回的是列表的第一個奇數(shù)。它使用dolist來循環(huán)列表中的元素雹有，找到奇數(shù)的時候調(diào)用return來離開循環(huán)偿渡。如果列表不包括奇數(shù)，之后當(dāng)循環(huán)結(jié)束霸奕，dolist會返回nil溜宽。一個關(guān)于find-first-odd很有意思的點就是循環(huán)體中包括了兩個語句，而不是一個质帅。循環(huán)體可以包含任何數(shù)量的語句适揉。
dolist設(shè)定一個特定的返回值語句是十分有用的，如下例煤惩，函數(shù)check-all-odd使用dolist來檢查是不是所有元素都是odd嫉嘀，如果是，dolist就會在循環(huán)結(jié)束的時候返回字符T魄揉，如果有任何非奇數(shù)的數(shù)字存在剪侮，函數(shù)馬上從循環(huán)中返回，返回值是nil洛退。
11.4 遞歸搜索和迭代搜索的比較
用在搜索普通列表的時候瓣俯，迭代比遞歸用起來更加簡單兵怯。據(jù)不同的實現(xiàn)來說彩匕，也許也是更有效率的。比較兩個find-first-odd的版本摇零，這些代碼已經(jīng)將format語句簡化省略了推掸。
迭代版本有幾個小優(yōu)點。首先驻仅，這個終極的是語句是沒有疑問的谅畅，dolist一定會在列表的盡頭停止操作。而在遞歸版本中我們必須要特意加一個cond語句來含混的檢查這個邊界噪服。第二毡泻，在迭代版本中變量E是迭代中自帶的，不需要另外設(shè)置步進(jìn)變量粘优，這個很方便仇味。在遞歸版本中呻顽，我們不得不使用（rest x）來指向下一個操作對象，在每一個遞歸中含混的計算每一個（rest x）丹墨。
在其他情況下廊遍，遞歸可以比迭代更加簡潔而且自然。例如贩挣，你可以很方便的用car/cdr遞歸來搜索一個樹喉前，沒有相等同的方法來優(yōu)雅實現(xiàn)這樣的功能。當(dāng)然迭代的解決方法是存在的王财，但是以很丑陋的方式卵迂。
11.5 使用賦值構(gòu)建結(jié)果
在第八章，我們見到了使用不同的方式來建立一個結(jié)果绒净，比如通過遞歸調(diào)用構(gòu)建一個列表见咒。在迭代程序里，結(jié)果是通過反復(fù)賦值來構(gòu)建的挂疆，我們首先見到如何在dolist或者dotimes的函數(shù)體里通過setf的賦值來構(gòu)建結(jié)果改览。之后張潔麗你會看到如何使用do來賦值。
Let’s start by using DOTIMES to compute the factorial function. First we
create an auxiliary variable PROD with initial value one. We will repetitively
update this value in the body of the DOTIMES, and then return the final value
of PROD as the result of the DOTIMES. Since the index variable I varies
from zero to N-1 rather than from one to N, we must add one to I each time
we reference its value in the body. Thus, (IT-FACT 5) counts from zero up to
four, but it multiples PROD by the numbers one through five.
我們首先來看看使用dotimes計算階乘函數(shù)囱嫩，首先我們創(chuàng)建一個輔助變量prod恃疯，初始值是1，我們會在dotimes的函數(shù)體內(nèi)反復(fù)更新這個變量墨闲，然后最后返回prod的值今妄。因為索引變量時從0到n-1，而不是0到n鸳碧，我們要每一次都給I加1盾鳞。（it-face 5）是從0到4，但是prod的相乘數(shù)字是1到5瞻离。
下面是另一個使用賦值的例子腾仅，寫一個迭代的交集函數(shù)。變量elementE幣綁定在集合x的元素上套利，如果element是集合y的元素推励，會被壓入result-set，否則就不會肉迫。當(dāng)所有的x的元素被處理結(jié)束验辞，dolist返回result-set的值。
11.6 使用mapcar的迭代和遞歸的比較
mapcar是應(yīng)用一個函數(shù)到列表里每一個元素的最簡單方法喊衫〉欤考慮一下列表中的數(shù)字計算平方的問題，函數(shù)是版本是比遞歸版本要簡單得多的族购。
mapcar所做的事情不僅僅是處理輸入的列表壳贪，并在結(jié)尾處停止陵珍，而且還把結(jié)果組合成一個列表。素有這些操作在遞歸版本中都必須明確作出處理违施。如果哦我們使用dolist來寫一個迭代的版本的話互纯，終結(jié)街側(cè)竟會自動處理，但是我們?nèi)匀槐仨毷褂脧?fù)制來構(gòu)建結(jié)果醉拓。下面就是這樣一個嘗試伟姐。
The function’s result is faulty: It’s backwards. This is typical for an
iterative solution. Since the function proceeds through the input list from left
to right, and pushes each result onto the front of the result list, the result list
ends up backwards. The square of the first number in the input list is the last
number in the result list, and so on. We can fix this by writing (REVERSE
RESULT) as the result-form of the DOLIST.
函數(shù)的結(jié)果是個作物，看上去是反過來的亿卤。這是一個迭代方案的典型結(jié)果。因為函數(shù)是從左到右進(jìn)行處理的鹿霸，那么在壓棧的時候就會是倒過來的順序排吴。第一個數(shù)字的平方在結(jié)果列表中是最后一個，依次類推懦鼠。我們可以再最后加上一個reverse來修正結(jié)果钻哩。
如果你已經(jīng)閱讀過進(jìn)階話題章節(jié)的話，你會明白為什么有經(jīng)驗的lisp程序員在迭代函數(shù)的最后傾向于使用破壞性函數(shù)nreverse來替代reverse了肛冶。如果你跳過了那些章節(jié)街氢，也不必?fù)?dān)心。
11.7 do宏
do是lisp中最強大的迭代形式睦袖，他可以綁定任何數(shù)字到變量中珊肃，就像let一樣。也可以在多音變量里以你喜歡的方式步進(jìn)任何值馅笙，并且允許你定義你自己的測試來決定什么時候離開循環(huán)伦乔。因為他太過強大，所以do的語法是稍微有點復(fù)雜的董习。
首先每一個在do的變量列表里的變量都被賦予了一個初始值烈和，之后測試部分就會被求值，如果結(jié)果是true皿淋，do就會對終結(jié)操作求值然后返回最后一個的值招刹，否則do就會春旭求值函數(shù)體。函數(shù)體中可能會包括return語句啦強制返回窝趣。當(dāng)do到達(dá)整個函數(shù)體的最后的時候疯暑，就會開始下一個循環(huán)的迭代。首先高帖，變量列表里的每一個變量都會被更新表達(dá)式來更新值缰儿。（更新表達(dá)式也可以被忽略，變量就會維持原有的值）當(dāng)所有變量都被更新過后散址，終結(jié)測試就會再一次求值乖阵，如果返回true宣赔，do就會求值終結(jié)操作，否則就會再次求值函數(shù)體瞪浸。
下面叫做launch的函數(shù)是用do來寫的儒将，請注意他只是用了一個索引變量cnt，他會從n遞減到0对蒲。用dotimes來寫launch也是可以的钩蚊，但是會有一點難看，因為dotimes所因變量的步進(jìn)是在一個“錯誤“的方向蹈矮。
下面是一個使用do來定義的count-slices函數(shù)的實現(xiàn)砰逻，（count-slices在第八章介紹過）這個循環(huán)使用兩個索引變量。cnt是從0開始并備用在構(gòu)建結(jié)果泛鸟。Z的步進(jìn)是loaf的后續(xù)rest蝠咆。
這個Do函數(shù)的函數(shù)體是空的，所有的計算都在變量列表的表達(dá)式里面結(jié)束了北滥。假設(shè)我們求值（count-slices ‘（x x））刚操。當(dāng)我們進(jìn)入Do，cnt就初始化為0z就初始化為（x x）再芋。之后來到終結(jié)測試菊霜，z不是nil循環(huán)就不會終結(jié)，函數(shù)體是空的济赎，所以do就開始更新變量鉴逞，cnt被設(shè)置成為（+ cnt 1），也就是加上了1联喘，Z設(shè)置成為（rest z）华蜒，就是列表（x），之后do再一次計算終結(jié)測試的結(jié)果豁遭，z依然不是nil叭喜，所以再一次迭代，這一次cnt的值成了2蓖谢，z成了nil捂蕴，終結(jié)測試也變成了true，被求值的表達(dá)式和被返回的循環(huán)終結(jié)結(jié)果是cnt闪幽，所以返回值是2.
11.8 隱式賦值的好處
do相比dotimes和dolist有一些優(yōu)勢啥辨。你可以以你喜歡的方式來步進(jìn)變量，比如以遞減計數(shù)而不是遞增計數(shù)盯腌。do可以通知綁定多個變量溉知，這樣子在do中建立一個變量列表的結(jié)果就變得很容易。也就是說，沒有必要使用let加上顯式的setf來實現(xiàn)了级乍。下面是一個使用do來實現(xiàn)的階乘函數(shù)版本舌劳。
這個版本的fact使用遞減計數(shù)而不是遞增計數(shù)字，并且使用了do的平行綁定屬性玫荣，當(dāng)開始計算（fact 5）的時候甚淡，i被初始化為5，result初始化為1.更新變量的時候捅厂，表達(dá)式（- I 1）求值為4贯卦，（* result I）求值為5.只有在所有表達(dá)式都求值結(jié)束，變量自身才會被改變焙贷；I被設(shè)置成為4撵割，result被設(shè)置成為5。下一次精力循環(huán)辙芍，（- I 1）求值為3睁枕，等等以此類推，剩下的如下圖沸手；
count-slices和fact的函數(shù)體都是空的，這也是使用do最重要的理由注簿。在變量列表中的更新表達(dá)式里就可以完成所有的隱式賦值工作契吉，所以就不需要再寫一個setf或者push了。這樣風(fēng)格的函數(shù)被認(rèn)為是非常優(yōu)雅的诡渴。
有些時候最好不要把所有的工作都丟給更新表達(dá)式捐晶。特別是當(dāng)更新表達(dá)式中有條件式的時候⊥纾看看這個版本的it-intersection惑灵，沒有函數(shù)體。
由于do想要每一次都通過循環(huán)來更新result眼耀，但是我們想要的只是在在（first x）是y的一個元素的時候英支，值進(jìn)行改變。是一個更簡單的版本可以忽略在變量列表里的表達(dá)式哮伟，而是在函數(shù)體重設(shè)置一個條件push來實現(xiàn)干花。
如果你想做的事情就是迭代列表中的元素，那么dolist回事比do更精練的方法楞黄，但是do是更加一般化的方法池凄。例如，我們使用do來同事迭代多個列表鬼廓，函數(shù)會比較從兩個列表中的相對應(yīng)的元素肿仑，一直到有兩個相等的出現(xiàn)為止。例如下面的函數(shù)FIND-MATCHINGELEMENTS。
11.9 宏函數(shù) Do *
下面是一個用do來實現(xiàn)的find-first-odd函數(shù)尤慰，按照一般慣例馏锡，變量x作為輸入的rest的步進(jìn)變量。在函數(shù)體內(nèi)部割择，我們洗衣歌（frist x）來支出輸入的元素眷篇。
宏函數(shù)Do * 的語法和do是一樣的，但是區(qū)別在于do是逐個創(chuàng)建更新變量荔泳，就像let一樣蕉饼，而不是像let一樣一次性創(chuàng)建所有。在find-first-odd函數(shù)中使用do的一個好處就是玛歌，他允許我們?nèi)ザx第二個索引變量來保存列表的后續(xù)元素昧港，第一個所用變量保存的是后續(xù)元素的cdr。
請注意支子，索引變量E使用的初始值和更新表達(dá)式都是（first X）创肥，這樣做的原因是，如果更新值被省略的話值朋，E的值不會在每一次進(jìn)入循環(huán)的時候改變叹侄。在do的變量列表中，e出現(xiàn)在x之后是很重要的昨登，因為e的值仰賴與x的值趾代。
11.10 do無限循環(huán)
把nil作為終結(jié)測試的話，do循環(huán)就會永遠(yuǎn)進(jìn)行下去丰辣，對需要從鍵盤輸入內(nèi)容（比如數(shù)字）的函數(shù)來說撒强，這是一個很有用的特性。如果用戶鍵入除了數(shù)字之外的其他對象笙什，函數(shù)就會打印一個錯誤信息飘哨，然后再次等待輸入。如果用戶卻是輸入了一個數(shù)字琐凭，函數(shù)就會離開循環(huán)芽隆，使用return返回那個數(shù)字，下面是例子淘正。
11.11 隱式塊（implicit blocks）
在common lisp中函數(shù)體是被包括在隱式塊（implicit blocks）當(dāng)中的摆马，函數(shù)名字就是塊名（blocks name），一個塊就是一些表達(dá)式的序列鸿吆，在這個序列里囤采，可以使用return-form特殊函數(shù)來跳出這個塊。在接下來的例子中惩淳，find-first-odd的函數(shù)體就是一個叫做find-first-odd的塊蕉毯。return-form的參數(shù)是一個塊名和一個結(jié)果表達(dá)式乓搬，塊名是不被求值的，所以不必加引號代虾。
在這個例子中进肯，我們使用return-form來跳出find-first-odd的函數(shù)體，而不僅僅是dolist的函數(shù)體棉磨。return-form從特定名稱的最近的封閉函數(shù)體中返回江掩。循環(huán)形式，諸如乘瓤，dotimes环形，dolist，do和do*的函數(shù)體都是封閉的隱式塊衙傀，名字是nil抬吟。表達(dá)式（return x）實際上僅僅是（return-form nil x）的簡寫形式。所以在find-first-odd的函數(shù)體中统抬，return-form是嵌套在一個叫做nil的塊當(dāng)中火本，這個塊被包含在一個叫做find-first-odd的塊當(dāng)中。
下面的例子中并不包含迭代聪建，是需要return-form钙畔。函數(shù)square-list使用mapcar來對一個列表的數(shù)字進(jìn)行操作。但是金麸，如果列表中有元素不是數(shù)字的話刃鳄，square-list并不會報錯，而是返回字符nope钱骂。在lambda表達(dá)式內(nèi)部的return-form跳出的不僅僅是lambda表達(dá)式，還有mapcar挪鹏，還有square-list本身见秽。
除了包含函數(shù)體的隱式塊之外，塊也可能通過特殊函數(shù)block來進(jìn)行顯式定義讨盒。這個特性只在進(jìn)階應(yīng)用里有使用解取，所以這里我們就不展開了。
小結(jié)
dolist和dotimes都是最簡單的迭代形式返顺，do和do*的強大是因為可以同時步進(jìn)多個變量禀苦，以及使用任意的更新表達(dá)式和終結(jié)測試。但是對于最簡單的問題遂鹊，像搜索列表中的元素之類的振乏，dolist還是更精練些。
所有的迭代形式都會對他們的索引變量進(jìn)行隱式賦值秉扑。這是最最感性的賦值類型慧邮；你不會再需要去寫setf語句了调限，因為循環(huán)本身已經(jīng)做好了賦值。有些時候误澳，還是在循環(huán)體重使用顯式賦值來構(gòu)建結(jié)果更加好一些耻矮。特別是在像itinsection函數(shù)這種有條件式賦值的時候。
函數(shù)名也被用作隱式塊的名字忆谓，我們因此可以使用return-form在函數(shù)體的任何地方跳出函數(shù)裆装。
本章涉及函數(shù)
迭代宏函數(shù): DOTIMES, DOLIST, DO, DO*.
用于塊結(jié)構(gòu)的特殊函數(shù): BLOCK, RETURN-FROM.
對已有匿名塊使用的普通函數(shù): RETURN.
Lisp Toolkit: TIME
宏函數(shù)time告訴你需要多少時間來對表達(dá)式求值。也可能會告訴你在求值時候占用了多少內(nèi)存倡缠，或者其他有用的信息哨免。time具體提供什么以及用什么樣的形式展現(xiàn)，根據(jù)lisp實現(xiàn)的不同而不同毡琉。在評估程序的小籠包的時候time是很有用的铁瞒，例如，比較一個問題的兩個解決方案桅滋，那個更快一些慧耍，或者看看一個函數(shù)在接收到一個大型輸入的時候運行多慢。
第十一章進(jìn)階話題
11.12 PROG1, PROG2, 和PROGN
PROG1, PROG2, 和PROGN是三個非常簡單的函數(shù)丐谋，他們都接受任意數(shù)量的表達(dá)式作為輸入芍碧，然后一次性計算所有表達(dá)式。prog1返回的是第一個表達(dá)式的值号俐，prog2返回的是子二個表達(dá)式的值泌豆，progn返回的是最后一個表達(dá)式的值，
這些語句在今天已經(jīng)不是很常用了吏饿，他們在早期的lisp版本中是很重要的踪危，那時候，一個函數(shù)的函數(shù)體可以包含至多一個表達(dá)式猪落，一個cond語句最多包含一個序列贞远。
progn還有用的一個地方在于是在于一個if的真值部分和假值部分。如果你想要對一些真值部分或者假值部分的多個表達(dá)式求值笨忌，那么就必須用progn蓝仲，block或者let將他們組合在一起。
prog1和prog2的效果是很容易用let來實現(xiàn)的官疲，例如袱结，（pop x）就等同于下面兩個表達(dá)式谢床。
時至今日扎谎，第二種一般被認(rèn)為是更容易理解的形式晌杰。
11.13 可選參數(shù)（optional argument）
common lisp函數(shù)可以被定義成接受可選參數(shù)的形式稳衬，關(guān)鍵字參數(shù)或者任意數(shù)量的參數(shù)展箱，只要在參數(shù)列表中放置叫做lambda列表關(guān)鍵（lambda-list keyword）字的特殊字符炬转。例如属韧，在lambda列表字符串后面的變量就被稱作可選變量亮钦。下面的函數(shù)接受一個參數(shù)x和一個可選的參數(shù)y。如果一個可選變量沒有被提供的話噪漾，默認(rèn)就是nil硼砰。
可選參數(shù)沒有被提供的話，不是一定要用nil作為默認(rèn)值的欣硼。在lambda列表中题翰，使用這樣的形式（變量名 值），就可以用自己的定義替換默認(rèn)值诈胜。下面的函數(shù)divide-check豹障，divisor的默認(rèn)值是2。（rem焦匈，由divide-check調(diào)用血公，是一個內(nèi)建函數(shù)，返回一個數(shù)被另一個數(shù)除了之后額余數(shù)）缓熟。
11.14 REST參數(shù)
下面累魔，列表關(guān)鍵字&restlambda之后的參數(shù)將會被綁定在一個函數(shù)的參數(shù)的列表上。它允許函數(shù)接受無限數(shù)量的參數(shù)够滑，就像+和format那樣垦写。下面的函數(shù)接受無限數(shù)量的參數(shù)并返回他們的平均值。
在使用&rest參數(shù)的時候彰触，需要特別小心的地方是遞歸函數(shù)梯投。在首次調(diào)用的時候，函數(shù)的參數(shù)是會被收集聚合成一個列表的况毅，如果函數(shù)接下來遞歸調(diào)用自身分蓖，市容那個列表的cdr作為輸入，就會出現(xiàn)一個列表的列表尔许，而不是一個原始的列表咆疗，下面的例子，函數(shù)faulty-square-all就想要返回所有的參數(shù)的平方的列表母债。
我們可以使用apply來進(jìn)行遞歸調(diào)用以修正這個問題。使用apply尝抖，（cdr args）的值就會被看做參數(shù)的列表來調(diào)用毡们，而不是一個單獨的參數(shù)。
PROG1, PROG2, 和PROGN函數(shù)也可以使用&restlambda列表關(guān)鍵字來輕松定義昧辽。
內(nèi)建版本的PROG1, PROG2, 和PROGN函數(shù)杜宇穿件參數(shù)的列表沒有干擾衙熔，因為他們只是需要返回一個值罷了。
11.15 關(guān)鍵字參數(shù)
在之前章節(jié)的進(jìn)階話題中我們已經(jīng)見過一些函數(shù)是接受關(guān)鍵字參數(shù)的了搅荞。例如member和find-if红氯，例如框咙，當(dāng)你想要member使用equal作為等于斷言的時候，你會這樣寫：
關(guān)鍵字參數(shù)在一個函數(shù)接受大量的可選參數(shù)的時候是很有用的痢甘。通過使用關(guān)鍵字喇嘱，我們避免了去記憶那些可選參數(shù)的命令。我們要記住的只是他們的名字塞栅。你也可以通過用lambda列表關(guān)鍵字&key來創(chuàng)造你自己的接受關(guān)鍵字參數(shù)的函數(shù)者铜，比如&optional，就可以替換默認(rèn)值放椰。下面的函數(shù)make-sundae就接受超過6個關(guān)鍵字參數(shù)作烟。
像：cherries這種關(guān)鍵字都是求值為自身的，這也是為什么他們沒有引號砾医。請注意我們調(diào)用make-sundae的時候拿撩，使用關(guān)鍵字：cherries，但是在參數(shù)列表中還有makesundae的函數(shù)體中如蚜，我們只是使用了普通字符cherries压恒。這是一個很重要的區(qū)別。在makesundae內(nèi)部怖亭，cherries僅僅是另一個變量涎显。唯一一件特殊的事情是他得到這個值的方式。只有&rest變量會被特殊對待兴猩，用&key定義的變量都會用一個特別方式得到值期吓；當(dāng)調(diào)用make-sundae的時候，我們通過使用：cherries關(guān)鍵字接續(xù)上一個值來給cherries定義一個值倾芝。
11.16 輔助變量（auxiliary variables）
lambda列表關(guān)鍵字&aux被用于定義輔助本地變量讨勤。你可以僅僅定義一個變量名，初始值回事nil晨另，或者你可以使用一個列表的形式（變量 表達(dá)式）潭千。在后面的表達(dá)式會被求值，然后結(jié)果會作為變量的初始值借尿。下面例子中的輔助變量len就用來保存列表的長度刨晴。
關(guān)鍵字&aux完成的事情是和特殊函數(shù)let*相同的；都是使用逐個綁定來創(chuàng)造變量路翻。選擇使用哪個純粹是個人口味問題狈癞。
進(jìn)階話題涉及函數(shù)
PROG1, PROG2, PROGN
Lambda列表關(guān)鍵字: &OPTIONAL, &REST, &KEY, &AUX.
