關於程式設計,最重要的是什麼呢?實務層面上,當然是能實現功能,然而如何實現?另一方面,想要的功能都能實現嗎?心智層面上,存在著「最重要的其實是運算思維」這樣的說法,那麼,運算是什麼?運算思維又是什麼?

語言與運算

現代有許多程式語言,從最初接觸的第一門語言開始,開發者努力閱讀文件、上課、練習,不斷從錯誤中吸收經驗,學著如何使用語言來表達想法,然後,交給電腦去運算,某些程度上,駕馭語言的能力,似乎就主宰了開發者能否實現運算,而掌握語法成了程式開發的要點。

於是,新的語言不斷出現,新的語法也不斷產生,一切都是為了能讓開發者擁有更多實現運算的能力。

然而,程式語言是怎麼產生的?那些語法為什麼又會與運算產生關係?

若將思考順序反過來,想想什麼是運算,或許會有點啟發,在(1 + 2)這個式子中,有1、2這樣的數值,而加法操作針對左運算元與右運算元進行運算,那麼如果是(1 + 2) + (3 + 4)呢?對最中間的加法來說,可以看看左、右運算元是否可化簡,對運算元中的加法也是如此,加法遇到運算元不能化簡時,才直接相加。

以這樣的想法出發,就可以定義布林值,也可以定義減、乘、除等操作,或者將一組數值與操作組成運算式,而運算式遵循著相同的化簡規則,進一步地,可以建立if(cond, a, b)操作,若持續化簡cond最後結果成立,進一步化簡a運算式,否則,化簡b運算式。那麼,陳述句呢?像是x = 1這樣的指定,搭配一個環境(Context)記錄化簡後的狀態,就能遵循相同的化簡規則,要定義while等陳述句,也就不是問題了。

喔!發現了嗎?從數值出發,思考操作的基本規則是什麼,然後在基礎規則上,逐一增加運算的複雜度。

這些操作組成的集合,似乎開始有了程式語言的樣貌,不過,還是跟語言有段差距,數值、操作、運算式、陳述句等,必須依一定的規則組成特定結構,也就是一個抽象語法樹,整個運算才能進行。然而,遵循某語言語法而撰寫的程式碼,可以透過解析器來建立對應的抽象語法樹,然後,依規則開始進行運算,而這個過程是可以自動化的。

運算的機器

持續化簡並不是運算唯一的方式,也可以是其他規則,然而,無論採用哪種規則,僅靠人力來執行一堆規則,其實是沒有效率的,如果有機器,可以自動化執行規則就好了,那麼,這臺機器該是什麼樣貌呢?

就方才談到的,每個化簡會得到化簡後的狀態,也就是說,無論採用哪種規則,採用「規則」後就會有個「狀態」,這就成了運算機器最基本的要求,當然,還必須能「輸入」資料,那就試著設計只有兩個狀態的機器開始吧!

一開始,機器在狀態一,狀態一讀取a後,會進入狀態二,狀態二讀到a,再回到狀態一。這機器最終目的,是想看看讀取一串字元後,是否處於狀態二,顯然地,只有奇數個a的字串,才會有可能,而狀態二稱為接受狀態,若真的能設計出機器,那就不用人力,即可進行「字串是否為奇數個a組成」這樣的運算啦!

而上述的這類型機器,稱為決定論有限狀態機(Deterministic finite automation, DFA)。決定論是指某輸入只會有一個可套用規則,這就造成了機器運算能力的限制,如果想判斷字串倒數第3個字元是否為b,方才的設計方式就不行了,如果讀到的b為倒數第3個字元時,「湊巧」選擇可轉移到狀態二的規則,後續狀態轉移設計就簡單了,只是真的能設計出這麼湊巧就轉移狀態的機器嗎?

關於這樣「湊巧」的機器,稱為非決定論有限狀態機(Nondeterministic finite automation,NFA)。然而,湊巧是不可能的,實作層面上,還是要找出各種可能的狀態,但這樣的機器過於複雜且沒有效率,那麼可以試著用DFA來模擬嗎?

若DFA每次轉移,只能有一個狀態,那是做不到的!然而,如果每次的轉移,可以處於一個「狀態集合」(也是一種狀態),裏頭包含了多種狀態,在讀取完字串之後,只要看看狀態集合中,是否包含著接受狀態,此時,就可以回答「字串倒數第3個字元是否為b」這類的問題了,雖然代價是更多、更複雜的規則與狀態集合,然而,NFA轉DFA是絕對可行的,也就是說NFA能做的運算,也能採用DFA來運行!

不過,DFA/NFA沒辦法記得看過哪些輸入,因而遇到必須根據過往資訊才能解決的問題時,DFA/NFA就沒輒了。此時,試著為加上個可儲存資料的機制,就可以增加機器可解決的問題,像是加入個堆疊,或者是隨機存取裝置,後者就是圖靈機了。先前專欄〈令人腦殘的程式語言〉中談過圖靈機,也談過Brainfuck這種無腦的語言為何能進行運算,有興趣可以進一步察看。

lambda演算

縱使只有8個符號,Brainfuck確實是門語言,它告訴我們程式語言是一組符號,圖靈機讀取這組符號撰寫的程式,依規則進行狀態轉移與讀寫,有比Brainfuck更簡單的語言嗎?Wolfram的2,3圖靈機!3表示使用三個符號,2表示有兩個狀態,為了令2,3圖靈機可以運作,它必須有六條規則。

談到規則,若曾經接觸過Lisp,應該會令其S表達式(s-expression)印象深刻,如先前專欄〈可程式的程式語言〉中談過的,想要理解Lisp,就只要掌握S表達式簡單的幾條規則,就可以了,Lisp是基於lambda演算(lambda calculus),lambda演算中的lambda表達式,只有三條規則,基於此三條規則,可以發展出描述各種運算的表達式。

對於函數式程式設計有概念的開發者,其實或多或少都接觸過lambda演算,如果更深入一點,可以試著寫個Y Combinator,使用ES6實作的話會是f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))),這是個完全使用lambda表達式的實例。

對於尋常的程式開發來說,Y Combinator或許沒啥實用性,不過,如果想要用lambda演算來表達運算,像是表達[1, 2, 3].map(elem => elem - 2),Y Combinator會是重要的元素之一,在實現Y Combinator之後,可以進一步看看《深入理解運算原理》,然後試著將各個元素都使用lambda表達式來表示,就連數值也必須使用lambda表達式,不得有例外。

持續思考

思考、思考,不斷地思考,就連「運算思維是什麼?」也必須持續思考,或許在不同的時間點上,被問到這問題時,必須暫時給個答案,然而在不同的時間點上,因為持續不斷地思考,答案也會一再地變動。

在運算的世界中,真理並不存在,有著直接面對卻無法解決的問題,然而,持續思考然是必要的,這並不是為了逼近真理,而是為了能以不同的方式來解決問題。像是轉移後只能有一個狀態的DFA,雖然無法解決NFA的問題,然而,試著轉移後能處於狀態集合,DFA就能解決NFA的問題。

思考會形成一種慣性,未曾有過這種慣性的開發者,多半會認為lambda演算、圖靈機或其他的運算系統,過於抽象、不重要而無實用性,然而,思考一旦形成慣性,相關的概念會無形注入日常的開發工作之中,從而影響對語言的看法、程式碼風格的展現、程式庫或工具等的採用,甚至是開發流程的決定等各個層面!

作者簡介


Advertisement

更多 iThome相關內容