我試圖更好地掌握類型如何在lambda微積分中發揮作用。無可否認,很多類型理論的東西都在我的頭上。 Lisp是一種動態類型語言,它大致對應於無類型的lambda演算?還是有某種我不知道的「動態類型lambda微積分」?Lisp鬆散地是什麼類型的lambda演算?
回答
Lisp是一種動態類型語言,它大致對應於無類型lambda微積分嗎?
是的,但只是粗略的。在「純」的無類型lambda演算中,所有內容都被編碼爲函數。 (你可以在谷歌搜索受歡迎的「教會編碼」和不太受歡迎的「斯科特編碼」)。Lisp具有非功能性數據,如原子和數字等,因此這可以被視爲「無類型的lambda微積分擴展常量」。
另一個重要的區別是評估順序。減少lambda-演算術語的規則是非常不確定的。 (有一個定理,即教會 - 羅塞爾定理,它鬆散地指出,只要事情終止,評估順序就不重要。)實際上,使用最左邊最外層的「正常順序」縮減來減少lambda項,因爲如果任何減少策略終止,那一個。 這與Lisp總是在進行beta縮減之前將參數評估爲正常形式非常不同。此評估訂單被稱爲「按價值調用」。
綜上所述,Lisp對應於的一種無類型的按值調用的lambda演算,其常量爲。
John McCarthy在his April, 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"中介紹了LISP。以下段落來自第6頁:
e。函數和形式。在數學邏輯之外的數學中通常不精確地使用「功能」一詞並將其應用於形式 ,例如y + x。因爲我們稍後將用函數的表達式進行計算,所以我們需要函數和形式之間的區別以及用於表示這種區別的符號。這種區別和描述它的符號,我們偏離平凡的 由Church [3]給出。
...
3. A. CHURCH,Lambda轉換的結石(普林斯頓大學 出版社,Princeton,N.J。,1941)。
該Wikipedia article on lambda-calculus有教會的出版物的歷史。麥卡錫引用的1941年的論文似乎是關於型的 lambda演算,這與維基百科文章的介紹相矛盾。
Lisp中的lambda
關鍵字可以理解爲僅通過類比來指代lambda-演算。 Lisp lambda表達式是一種anonymous function。
這就是我的想法,但我被訓練認爲無類型!=動態類型。 :-) – 2010-05-01 15:24:12
@Heath:但是,引用明確指出,從論文中得出的結論是「功能和形式之間的區別以及表達這種區別的意見」,而不是實施本文所述的系統。 – outis 2010-05-01 15:51:40
Lisp不是'lambda微積分',我不知道'lambda微積分'是什麼。
如果你想通過那裏鍵入系統來識別lambda結石,那麼當然Lisp是它自己的。 Scheme之前的任何lisp中的'lambda'關鍵字肯定是自命不凡的,在Scheme之後還有空間可以說。只要使用'func'會更加謙虛。 Lisp主要是列表處理器,而不是'lambda微積分'
我也寫了一篇相當廣泛的文章,一次試圖說明爲什麼A:術語'函數式編程'是無意義的,B:爲什麼說'一個演算,而不是‘一類的制度’也是如此:
http://blog.nihilarchitect.net/archives/289/on-functional-programming/
另外,請記住,在Lisp中,所有功能都有效單個參數只能是有名單作爲他們的論據。
您的帳戶已被暫停!因此鏈接實際上已經死亡 – 2016-07-20 13:24:49
- 1. 爲什麼大多數腳本語言是鬆散類型的?
- 2. 鬆散XAML的侷限性是什麼?
- 3. 什麼是鬆散耦合的代碼?
- 4. 是否可以在無類型的lambda演算中有效地實現`max`?
- 5. 什麼是lambda函數的類型?
- 6. 質疑LAMBDA演算
- 7. 什麼讓耦合「鬆散」,是否更好地編寫我的代碼鬆散耦合?
- 8. 什麼樣的算法描述鬆散吊線物理?
- 9. *(++ ptr)是什麼類型的運算符?
- 10. 假設數據類型的鬆散類型數據集
- 11. DDD:你有什麼理由鬆散地結合實體?
- 12. 「嚴格」和「鬆散」行爲之間的區別是什麼?
- 13. 在Babeljs中「鬆散」的意思是什麼?
- 14. Git GUI引用的「鬆散對象」是什麼?
- 15. 什麼是「分散唯一性算法」?
- 16. decltype(rvalue expr)的類型演繹規則是什麼?
- 17. 這個lambda表達式的返回類型應該是什麼?
- 18. Php找出什麼類型的散列是一個字符串
- 19. PostgreSQL - 自動演算的類型?
- 20. lambda演算的圖靈完備性?
- 21. 鬆散的QProcess
- 22. 用於分類鬆散可比數據的算法?
- 23. .Net - 什麼是「放鬆」?
- 24. 什麼是鬆耦合?
- 25. 什麼是類型和什麼是類型構造函數scala
- 26. LetterP的類型是什麼?
- 27. 什麼是MouseEventArgs.X的類型?
- 28. T的類型是什麼?
- 29. 什麼是setContentView()的類型
- 30. 什麼是等效的lambda?
如果我們談論的是Lisp,不應該是(lambda(微積分));-) – 2010-05-01 15:06:53
只要你不是在談論Clojure。那麼它就是'(fn [微積分])':-) – 2010-05-01 15:10:20
這個問題的問題是沒有一個獨特的Lisp語言,他們有一個完整的家族。你指的是哪個Lisp? – outis 2010-05-01 15:48:58