前言
上個月月末的時(shí)候外构，看了《The Little Schemer》的第九章，第九章就是在講停機(jī)問題和Y組合子播掷。感覺很有意思审编，Y組合子真的是一個很神奇又有趣的東西，以至于MIT數(shù)學(xué)系的系徽就用的是Y組合子歧匈。Y組合子的發(fā)現(xiàn)者Haskell B.Curry把Y組合子紋在手臂上垒酬，他覺得自己撿了個大便宜。什么件炉？你不知道這個人勘究？我也不知道，但是學(xué)編程的Haskell這個單詞應(yīng)該很眼熟吧斟冕，沒錯就是用這個人的名字命名的Haskell語言口糕。可見此人必定是大魔法師啊磕蛇，魔法師景描，你懂得。手臂上封印Y組合子秀撇，手中莫名的多了汽油和火把超棺。
其實(shí)我也是魔法師這個高貴職業(yè)中得一員，Lv.22即將升到Lv.23呵燕。
停機(jī)問題
首先是停機(jī)問題棠绘，我們來思考這樣一個問題：是否會有這樣一個程序告訴我們一個函數(shù)對于它的每一個輸入都能夠返回一個值？什么意思？看我們的題目弄唧，停機(jī)問題啊适肠，一個程序返回了那就是停機(jī)了，如果一直運(yùn)行下去候引，那就是不停機(jī)侯养。什么沒見過一直運(yùn)行下去的程序？去寫個函數(shù)澄干，無參逛揩，自己調(diào)自己你看它能返回不？好麸俘，現(xiàn)在停機(jī)的概念已經(jīng)清楚了辩稽，那么我們問題是什么？就是說會不會有這么一個程序从媚，我們傳入另一個程序逞泄，它返回true或false，如果是true拜效，那就是說這個程序停機(jī)喷众，如果是false那就是說這個程序不停機(jī)，問題清楚了吧紧憾。所以有還是沒有呢到千？好，我知道你們都會說沒有赴穗，但是我還是要剛一波憔四，我就說有。假如有應(yīng)該是這個樣子般眉，參數(shù)是一個函數(shù)f了赵，返回值應(yīng)該是true或者false。我們用Scheme來定義一下這個充滿魔法自帶火把的函數(shù)：
(define will-stop?
(lambda (f)
...))
在這里簡單的說一下Scheme的語法：
define就是起個名甸赃，函數(shù)的定義：很簡單柿汛，lambda關(guān)鍵字，括號里面是參數(shù)表辑奈，然后是函數(shù)體，就是下面的樣子已烤。
(define add
(lambda (x y)
(+ x y)))
(define <fun-name>
(lambda (<args>)
<body>))
函數(shù)的調(diào)用：就是先寫操作符鸠窗，然后寫實(shí)參，實(shí)際上就是前綴表達(dá)式胯究。寫法就像下面的樣子：
(+ 1 2)
((lambda (x y)
(+ x y)) 1 2)
(<op> <args>)
這里必須吹一波Scheme語法稍计，簡潔到令人感動。Lisp語言誕生于1958年裕循，至今還很活躍臣嚣，如運(yùn)行在JVM上的Clojure，我感覺語法有很大的功勞。那些號稱語法簡潔的語言如某Go蚕涤，看了看噪裕，感覺也就那樣。
吹B結(jié)束怎虫，回到我們之前的問題暑认，現(xiàn)在我們這個will-stop?函數(shù)已經(jīng)寫好了。好我們寫兩個函數(shù)驗(yàn)驗(yàn)貨大审，先寫一個可以停機(jī)的吧蘸际。
(define length
(lambda (l)
(cond
((null? l) 0)
(else
(+ 1 (length (cdr l)))))))
這個函數(shù)接受一個list作為參數(shù)，就是數(shù)據(jù)結(jié)構(gòu)中的鏈表徒扶。然后呢如果是空鏈表就返回0粮彤，否則的話返回(+ 1 (length (cdr l)))，cdr就是除去鏈表第一個元素形成的新的鏈表姜骡。所以這個函數(shù)是對的吧导坟，傳入一個list，返回它的元素個數(shù)也就是節(jié)點(diǎn)的個數(shù)溶浴，這個值就是list的長度乍迄。就像Java中List的size方法一樣。顯然對于一個合法的參數(shù)士败，length函數(shù)是可以停機(jī)的闯两。什么你說無窮流？我認(rèn)為它不合法:）×陆現(xiàn)在我們將length傳給will-stop?漾狼，它就會返回true。現(xiàn)在再來想一個不會停機(jī)的函數(shù)饥臂，這個簡單逊躁，遞歸啊隅熙！看下面的函數(shù)稽煤，以x為參數(shù)，然后函數(shù)中再用自己去調(diào)用x囚戚，這樣它就會一直的運(yùn)行下去酵熙。所以(will-stop? eternity)會返回false。好驰坊，現(xiàn)在我們充滿魔法的的will-stop匾二？函數(shù)已經(jīng)可以工作了。說了這么多，其實(shí)就是假設(shè)我們有這樣的程序察藐，反證法么皮璧，上學(xué)的時(shí)候證明題做不出來就反證啊分飞！
(define eternity
(lambda (x)
(eternity x)))
現(xiàn)在我們利用現(xiàn)有的will-stop?函數(shù)來寫另一個函數(shù)：
(define last-try
(lambda ()
(and (will-stop? last-try)
(eternity '())))
這里說一下Scheme中的and悴务，如果第一個表達(dá)式返回false，就返回false浸须。如果前面的的表達(dá)式都返回的true惨寿，就返回最后一個表達(dá)式。所以看一下last-try這個函數(shù)删窒，無參數(shù)裂垦，函數(shù)體的意思是，如果last-try停機(jī)我就調(diào)用eternity函數(shù)肌索，如果last-try不停機(jī)我就返回false蕉拢。
沒錯吧？是這個意思吧诚亚，好記自位弧！
有沒有發(fā)現(xiàn)哪里不對站宗？我們調(diào)用一下(will-stop? last-try)闸准，完了，崩了梢灭！我們充滿魔法的will-stop?總會給我們一個答案夷家，如果是true，那么我們認(rèn)為last-try是可以停機(jī)的敏释。但是我們上面有說過库快，last-try函數(shù)如果停機(jī)，就會調(diào)用eternity函數(shù)钥顽，就不會停機(jī)义屏。如果是不可停機(jī)的，即(will-stop? last-try)返回的是false蜂大，也就是說充滿魔法的程序告訴我們last-try是不會停機(jī)的闽铐。但是我們就看last-try的函數(shù)體，如果last-try不停機(jī)奶浦，就直接返回false兄墅，停機(jī)了。财喳。察迟。
Ok！矛盾了耳高，所以說不存在這樣一個程序扎瓶。原來寫不出來是因?yàn)椴淮嬖冢皇俏覀儾粔蚺１泼谇梗睦镞@就好受多了概荷，感謝圖靈和哥德爾，66666碌燕！
好误证，停機(jī)問題到此結(jié)束，先用這個簡單的問題來醒醒腦修壕。
下集預(yù)告
第二篇文章會用Scheme語言一步一步的推倒出Y Combinator愈捅，敬請期待:）。
還得說一嘴慈鸠，網(wǎng)上總有人說一下午看完了Dan的《The Little Schemer》蓝谨，這幫人真的挺low的。這書雖然寫的像個小人書一樣青团，而且也就兩百來頁譬巫，但是進(jìn)入第八章之后，瞬間高能督笆！一下午都不見得看得完一章芦昔，你要說你一下午看完了《Thinking in Java》，那我信:）娃肿。人越缺少什么就越愛炫耀什么咕缎，骨子里還是自卑的。所以總是向別人炫耀自己多么聰明的咸作，對吧:）锨阿。
