PTT數位生活區 / Python

Re: [資訊] Guido 對 Tail Recursion Elimination …

看板Python作者 (..........)時間15年前 (2009/04/29 01:29), 編輯推噓11(11推 0噓 64→)
留言75則, 7人參與, 最新討論串1/3 (看更多)
※ 引述《yjc1 (..........)》之銘言： : http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html : 解釋了這麼多年來一直沒把 TRE / TCO(Tail Call Opimization) 加到 python 的原因 : 這些理由可以理解但不太能接受… 連 lua 都 support TCO 了… http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html 再次確認 TCO 無望，但後半段提到的 TCO 替代方案頗有趣 看起來還是可以硬幹，只是很醜…… 這些理由中唯一可以說服我的只有 guido 對 stack frame 不能被破壞的堅持， 但個人感覺 stack frame 也沒那麼神聖不可侵犯。 而且連放到 -O 才開的方式都冠以「破壞一致性」的大義…就死心了吧… -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.23.212
→
04/29 01:37, , 1F
「To iterate is human; to recurse, divine.」
04/29 01:37, 1F
→
04/29 01:39, , 2F
「遞迴只應天上有，凡人該當用迴圈」 - L. Peter Deutsch
04/29 01:39, 2F
推
04/29 12:11, , 3F
必要用 TCO 的案例，都可以很容易用 loop 寫吧，
04/29 12:11, 3F
→
04/29 12:12, , 4F
例如算階乘等，為什麼這種東西堅持要用遞迴寫？
04/29 12:12, 4F
→
04/29 18:09, , 5F
為了讓 Python 更向 functional programming 靠攏？
04/29 18:09, 5F
推
04/29 18:45, , 6F
以算階層來說，就算用 FP ，也不必用到遞迴
04/29 18:45, 6F
→
04/29 18:48, , 7F
reduce(lambda a, b: a+b, range(10))
04/29 18:48, 7F
→
04/29 18:53, , 8F
f=lambda x: reduce(lambda a, b: a*b, range(1,x+1))
04/29 18:53, 8F
→
04/29 18:54, , 9F
f(3)
04/29 18:54, 9F
→
04/29 18:54, , 10F
6
04/29 18:54, 10F
推
04/29 18:57, , 11F
我不反對遞迴，而是反對要動用 TCO 才跑得好的程式寫法
04/29 18:57, 11F
→
04/29 18:58, , 12F
這對數學家也許很有趣，但不符合工程美學
04/29 18:58, 12F
→
04/29 19:06, , 13F
Explicit is better than implicit.
04/29 19:06, 13F
→
04/29 19:06, , 14F
Simple is better than complex.
04/29 19:06, 14F
→
04/29 19:34, , 15F
你有考慮 reduce 是如何實做的嗎？應該是iterative作法
04/29 19:34, 15F
→
04/29 19:44, , 16F
loop 在 iteration 之間有額外的狀態必須正確維持住
04/29 19:44, 16F
→
04/29 20:01, , 17F
不過我認為你以reduce實做階層計算跟使用tail-recursion
04/29 20:01, 17F
→
04/29 20:02, , 18F
來實做的精神幾乎一樣了
04/29 20:02, 18F
推
04/29 21:02, , 19F
tail-recursion 是特定遞迴寫法照成的現象；
04/29 21:02, 19F
→
04/29 21:04, , 20F
reduce 的背後，基本上就是 iterative ，跟遞迴不相干
04/29 21:04, 20F
推
04/29 21:18, , 21F
這樣說好了，你手算階乘時是怎麼算的？有簡明的寫法，
04/29 21:18, 21F
→
04/29 21:19, , 22F
有簡單明瞭的寫法時，為甚麼要用遞迴來寫？
04/29 21:19, 22F
→
04/29 21:20, , 23F
我用遞迴的原則就是問：這樣寫有比較簡單嗎？
04/29 21:20, 23F
→
04/29 21:22, , 24F
Python 支援 TCO 的話，某種程度就是鼓勵人寫 TC
04/29 21:22, 24F
→
04/29 21:23, , 25F
而我看過的 TC 程式都比它的非 TC 版本來得晦暗；
04/29 21:23, 25F
→
04/29 21:23, , 26F
TC 的寫法把簡單的事情複雜化
04/29 21:23, 26F
→
04/29 21:24, , 27F
以上是我的觀點
04/29 21:24, 27F
推
04/29 21:25, , 28F
對不熟悉遞迴的人而言遞迴是不好懂；反之是很單純又直覺的
04/29 21:25, 28F
→
04/29 21:26, , 29F
There should be one
04/29 21:26, 29F
→
04/29 21:27, , 30F
-- and preferably only one --obvious way to do it.
04/29 21:27, 30F
→
04/29 21:34, , 31F
quicksort 以遞迴寫就比較簡明；乘階以遞迴寫比較晦暗
04/29 21:34, 31F
→
04/29 23:18, , 32F
我倒覺得用遞迴寫factorial一點都不晦暗...
04/29 23:18, 32F
→
04/30 00:00, , 33F
照 yk 的說法，那 list comprehension 與 lambda 也不應該加
04/30 00:00, 33F
→
04/30 00:00, , 34F
入 python 當中
04/30 00:00, 34F
→
04/30 00:02, , 35F
lambda 不夠直覺， list comprehension 不夠 explicit
04/30 00:02, 35F
→
04/30 00:04, , 36F
但這兩項暨沒有破壞 stack frame 也無破壞一致性的問題，所以
04/30 00:04, 36F
→
04/30 00:04, , 37F
我才說可以接受 guido 這樣的說法
04/30 00:04, 37F
→
04/30 00:10, , 38F
另外，遞迴只是種工具，有其適合的場合與不適用的場合
04/30 00:10, 38F
→
04/30 00:11, , 39F
總不能因為有人不熟 OOP 就叫他不要在c++/java裡用oop吧
04/30 00:11, 39F
推
04/30 00:29, , 40F
但是python 允許使用遞迴、只是限制在1000層的範圍內
04/30 00:29, 40F
→
04/30 00:32, , 41F
以工具使用上來用是足夠的
04/30 00:32, 41F
推
04/30 01:04, , 42F
factorial 以遞迴寫確實很明確，跟定義方式一樣 :)
04/30 01:04, 42F
→
04/30 01:05, , 43F
list comprehension 提出的原因就是它較 explicit
04/30 01:05, 43F
→
04/30 01:16, , 44F
有些場合用 lambda 很方便，雖然我覺得這個 term 很無俚頭
04/30 01:16, 44F
→
04/30 01:25, , 45F
function call 的 overhead 是不是變相不鼓勵遞迴解？
04/30 01:25, 45F
→
04/30 01:25, , 46F
就如 L 說的，Python 還是允許大家用遞迴，
04/30 01:25, 46F
→
04/30 01:27, , 47F
只要不要像 TC 類造成 recursion 災難就好...
04/30 01:27, 47F
→
04/30 01:32, , 48F
還有，就是值不值得，加了 TCO 壓縮到其他功能的開發資源
04/30 01:32, 48F
→
04/30 02:35, , 49F
lambda 是無俚頭的 term…… TCO壓縮到其他功能開發資源……
04/30 02:35, 49F
→
04/30 03:07, , 50F
我感受到一股Blob弔詭的味道...
04/30 03:07, 50F
→
04/30 03:22, , 51F
Blub sorry
04/30 03:22, 51F
→
04/30 10:22, , 52F
lambda 對知道典故的人當然不會無俚頭，
04/30 10:22, 52F
→
04/30 10:23, , 53F
只是覺得應該有更直覺的寫法才對，雖然我不知它該是什麼
04/30 10:23, 53F
推
04/30 15:04, , 54F
對於函數式程式語言的愛好者而言，lambda和遞迴都很直覺
04/30 15:04, 54F
→
04/30 15:05, , 55F
不過 Guido 說他不是函數式程式語言的愛好者 XD
04/30 15:05, 55F
推
05/04 12:17, , 56F
lambda 名稱是由 Lisp 來的，當初本來就是亂取個名字來用
05/04 12:17, 56F
→
05/04 12:17, , 57F
可以參考各種語言對相似語意的語法差異：
05/04 12:17, 57F
→
05/04 12:18, , 58F
Lisp: (lambda (arg) "hello world")
05/04 12:18, 58F
→
05/04 12:18, , 59F
Smalltalk: [arg| ^"hello world"]
05/04 12:18, 59F
→
05/04 12:19, , 60F
Ruby: 5.times {|x| puts x}
05/04 12:19, 60F
→
05/04 12:20, , 61F
大家不覺得 Smalltalk 或 Ruby 的用法比較簡潔有力嗎？
05/04 12:20, 61F
→
05/04 21:57, , 62F
lambda是從lambda calculus來的吧...
05/04 21:57, 62F
→
05/04 22:01, , 63F
不過前後關係我不知道，可能得請PLT那邊的來（倒
05/04 22:01, 63F
→
05/04 22:59, , 64F
05/04 22:59, 64F
→
05/04 23:00, , 65F
好歹先翻一下相關資料再討論吧.
05/04 23:00, 65F
推
05/05 00:19, , 66F
我喜歡 Haskell. \x -> x + 1. 另，ruby 用 lambda{ ... }
05/05 00:19, 66F
→
05/05 21:17, , 67F
我知道 lambda calculus 是 Church 提出來的，
05/05 21:17, 67F
→
05/05 21:18, , 68F
它跟 Lisp 的淵源是我記錯了；不過沒差，名字還是隨意取的
05/05 21:18, 68F
→
05/05 21:19, , 69F
新的 ruby 好像有新的語法糖衣，比 lambda term 簡便
05/05 21:19, 69F
→
05/05 22:45, , 70F
ruby 1.9 可以這樣用：->x{x+1} 這是學自 perl 6 的，但
05/05 22:45, 70F
→
05/05 22:46, , 71F
其實很多人反對這種用法，覺得 -> 一點都不像 lambda
05/05 22:46, 71F
→
05/05 22:46, , 72F
我自己試試的結果是，這樣寫長一點時，其實是真的不好看
05/05 22:46, 72F
→
05/05 23:05, , 73F
相較於 lambda calculus ，工程師應該對 Turing Machine
05/05 23:05, 73F
→
05/05 23:06, , 74F
感到較親切，雖然兩者的計算能力是等效的
05/05 23:06, 74F
→
05/05 23:06, , 75F
不過 Turing Machine 比較像 Machine :p
05/05 23:06, 75F
‣ 更多 yjc1 的文章
文章代碼(AID): #19zppyTM (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yjc1 的文章
文章代碼(AID): #19zppyTM (Python)