ECL爲什麼可以計算階乘（1000）？

-2

ECL可以計算fac（1000）真是太棒了！ ECL如何做到這一點？ECL爲什麼可以計算階乘（1000）？

>(defun fac (n) (if (= n 1) 1 (* n (fac (- n 1))))) 
>(disassemble #'fac) 
#(FAC N = - * #<bytecompiled-function FAC> SI:FSET) 
Name:   FAC                 
    0 POP  REQ 
    1 BIND N 
    3 NOMORE 
    4 PUSHV 0 
    6 PUSH 1 
    8 CALLG 2,= 
    11 JNIL 18 
    13 QUOTE 1 
    15 SET  VALUES(0),REG0 
    16 JMP  35 
    18 PUSHV 0 
    20 PUSHV 0 
    22 PUSH 1 
    24 CALLG 2,- 
    27 PUSH VALUES(0) 
    28 CALLG 1,FAC 
    31 PUSH VALUES(0) 
    32 CALLG 2,* 
    35 EXIT

我對ECL字節碼知之甚少。似乎沒有尾遞歸優化。任何專家都可以解釋嗎？

真誠！

來源

2012-09-19 z_axis

這是字節碼，但可能解釋器可以做優化？ 1000級別的堆棧並不是一個真正的問題 - 解釋器實現應該已經處理了這個事件（如果它確實對這種情況進行遞歸）。 – nhahtdh

1000確實不是問題。 '（defun fac（n）（reduce＃'*（從1到n的循環收集i）））'甚至計算（fac 30000）或更多。精彩（E）CL，謝謝！ –

如果解釋器確實保留了一個堆棧，它將被實現爲數據結構來像堆棧一樣工作，因此它可以任意堆疊多層（不確定內部實現，但它可能會施加一個限制，或者限制是系統的限制）。 – nhahtdh

我對ECL一無所知，但從編譯的源代碼中看到，然後在拆卸後，編譯器正常工作。該函數被定義爲對其自身的遞歸調用。我在解體中看到了同樣的結果。因此，調用此函數時可能出現的唯一問題是堆棧溢出和算術溢出。

來源

2012-09-19 01:22:21 Serge

溢出發生使用newlisp來計算fac（30），所以我真正想知道的是如何（E）CL可以做到沒有溢出。 –

順便說一句，它是否打印出結果的所有2568位數？ – Serge

@z_axis自動從fixnum升級到bignum，因爲reult會溢出fixnum的大小。原則上相對簡單（但要使數學運算速度快可能會有點棘手）。 – Vatine

ECL的解釋器目前不會進行尾部呼叫優化。它可以很容易地實現，但我沒有時間這樣做：基本上，它相當於向字節碼編譯器添加一個標誌來發信號通知尾部調用。無論如何，正如這裏所指出的那樣，ECL解釋器使用動態分配的堆棧以及用於解釋器遞歸的C堆棧。這意味着您將獲得大約1000 C的堆棧幀（小）和一些consed列表來跟蹤環境。目前已經足夠，沒關係。然而，在C方面，ECL檢測自我尾巴呼叫並且可以優化其中的許多，而在其他情況下，GCC優化相互尾巴呼叫（呼叫尾部位置的其他功能）。

來源

2012-09-25 14:17:49 Juanjo

ECL爲什麼可以計算階乘（1000）？

回答

相關問題