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