談談程式與 backtracking

https://github.com/YauHsien/work/blob/master/src/vertical_arithmetics.prolog

如以上網址內容,前陣子為了一個小小的 AB x C = DE, DE + FG = HI 的直式算式,求將 1 到 9 之間的數字填入。寫了這個小小的 Prolog 程式。

以前曾經聽過有一位仁兄說過: “Prolog function always return boolean value." 沒錯,如果是用普通的語言思維來想事情, Prolog 的確是只傳回真偽值。正因為一句可能會有 False 結果,所以可以建構出 backtracking 機制。

又像這篇 http://feed.wordcorp.net/blog/post/how-language-you-speak-changes-your-view-world ,標題為「【語言的祕密】你所使用的語言,直接塑造了你看待世界的方式」,我覺得:

以通用程式語言,如 Java ,來談: Java 程式也有能讓每一句有機會執行失敗的機制,然而,絕大部分的錯誤處理動作,是只讓一句程式的錯向上浮,通過它所在的呼叫點,通過它所經過的每一個類別,回到最開端的執行位置– main 方法而印出,而跟著程式一起結束。

可是, Prolog 包容了失敗,凡是發生失敗的句子,就是它程式邏輯上的證偽。而證偽是有意義的。

試想,我們採用 Erlang 來實現 Prolog 的例子:例如呼叫 add(AB, C) 來證成 add(AB, C) =:= DE 。那麼,我認為,在 Erlang 這 add(AB, C) =:= DE 會被認為寫成 Guard 或 Case ,是適當的辦法。至於無法證成 add(AB, C) =:= DE,則是由 try-catch 式子來將失敗的 add(AB, C) =:= DE 轉換為真偽值,然後向上提醒上游及早放棄掉此判斷,而如此則可以實現 backtracking 機制。

也就是說,以 Java 程式,也有 try-catch 。善用 try-catch 及錯誤處理,搭配著原有的迴圈及判斷邏輯,是可以搭出很自然的 backtracking 機制。(不過,另外是 Java 系統的重點通常是在於類別之間或物件之間的關聯。把視野放在程式行之間的邏輯理路,可能是放錯重點。)

至於,改想想用 C 語言寫 backtracking ,那與使用 Java 或 Prolog 的差別是:前者是要動手寫才有 backtracking ,後者是要動手「不寫」才有 backtracking 。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Uncategorized。將永久鏈結加入書籤。