各種程式語言對尾遞歸的支援

• 2019 年 11 月 3 日
• 筆記

　　版權申明：本文為部落客窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須註明原文網址    　　http://www.cnblogs.com/Colin-Cai/p/11774213.html    　　作者：窗戶    　　QQ/微信：6679072    　　E-mail：[email protected]

　　尾遞歸

　　這篇文章，我們講尾遞歸。在遞歸中，如果該函數的遞歸形式表現在函數返回的時候，則稱之為尾遞歸。

　　舉個簡單的例子，用偽碼如下：

　　function Add(a, b)

　　if a = 0

　　　　return b

　　return Add(a-1, b+1)

　　end

　　上面這個函數實際上是兩個數的加法，簡單起見，只考慮非負整數，後面敘述具體語言總是會以這個函數為例子。所有的return部分都是不再依賴於遞歸，或者是返回Add函數，其參數的計算不再依賴於遞歸，典型的尾遞歸。

　　上述程式碼很容易用循環表示：

　　function Add(a, b)

　　while True

　　　　if a = 0

　　　　　　return b

　　　　end

　　　　a <= a-1

　　　　b <= b+1

　　end

　　end

　　所有的尾遞歸都可以用循環表示，只需要把傳入的參數當成是狀態，運算的過程當成是狀態的轉換。

　　比如Add(3,0)的計算就經過

　　3,0

　　2,1

　　1,2

　　0,3

　　這樣的狀態轉換。

　　函數的計算會維護一個棧，每當遇到函數調用會記錄當前運行的狀態，如此在函數返回的時候可以恢復上下文。

　　比如，對於Fibonacci數列，偽碼如下：

　　function fib(n)

　　if n < 3

　　　　return 1

　　end

　　return fib(n-1)+fib(n-2)

　　end

　　我們計算fib(4)，棧大致如下：

　　fib(4)

　　=>

　　fib(4)

　　fib(3)

　　=>

　　fib(4)

　　fib(3)

　　fib(2)

　　=>

　　fib(4)

　　fib(3)

　　fib(2) 1

　　=>

　　f(4)

　　f(3) 1+

　　=>

　　f(4)

　　f(3) 1+

　　f(1)

　　=>

　　f(4)

　　f(3) 1+

　　f(1) 1

　　=>

　　f(4)

　　f(3) 2

　　=>

　　f(4) 2+

　　=>

　　f(4) 2+

　　f(2)

　　=>

　　f(4) 2+

　　f(2) 1

　　=>

　　f(4) 3

　　=>

　　3

　　而作為尾遞歸，我們計算Add(3,0)，棧可能是如下過程：

　　Add(3,0)

　　=>

　　Add(3,0)

　　Add(2,1)

　　=>

　　Add(3,0)

　　Add(2,1)

　　Add(1,2)

　　=>

　　Add(3,0)

　　Add(2,1)

　　Add(1,2)

　　Add(0,3)

　　=>

　　Add(3,0)

　　Add(2,1)

　　Add(1,2)

　　Add(0,3) 3

　　=>

　　Add(3,0)

　　Add(2,1)

　　Add(1,2) 3

　　=>

　　Add(3,0)

　　Add(2,1) 3

　　=>

　　Add(3,0) 3

　　=>

　　3

　　對於Add函數，以上棧的長度與計算量成正比。如此，意味著計算量越大所需要的棧越大，甚至導致超過最大限制而無法運算。

　　同時我們發現，簡單的轉為循環表示的Add則沒有這個問題。

　　這裡，可以採用一個編譯技術，就是尾遞歸優化，其一般情況是，如果一個函數的計算中遇到了完全轉化成另一個函數調用的情況，那麼棧的當前函數部分的資訊可以完全抹去，而替換為新的函數。如此處理下，此情況棧不會增長。

　　Add(3,0)的棧的過程如下：

　　Add(3,0)

　　=>

　　Add(2,1)

　　=>

　　Add(1,2)

　　=>

　　Add(0,3)

　　=>

　　3

　　尾遞歸優化給了我們一種迭代的方式，之所以研究它，在於函數式編程會用到它。

　　註：遞歸論區分遞歸和迭代(迭置)，和電腦上定義有一點區別，在此不深入。

C/C++

　　我們從底層的語言開始，首先還是上面的加法實現。為了讓範圍更大一點，便於觀察，我們使用unsigned long long類型。

/*add.c*/  unsigned long long add(unsigned long long a, unsigned long long b)  {          if(a==0ULL)                  return b;          return add(a-1ULL,b+1ULL);  }

　　再寫一個main來測試它，用命令行參數去獲得傳入add的兩個參數

#include <stdio.h>  unsigned long long add(unsigned long long a, unsigned long long b);  int main(int argc, char **argv)  {      unsigned long long a, b;      sscanf(argv[1], "%llu", &a);      sscanf(argv[2], "%llu", &b);      printf("%llun", add(a,b));      return 0;  }

　　用gcc編譯，

　　gcc add.c main.c -o a.out

　　運行一下，

　　./a.out 10000000 100000000

　　馬上發生短錯誤，直接崩潰。看來C語言作為底層語言沒必要支援這個啊？

　　於是我們開啟優化，

　　gcc -O2 add.c main.c -o a.out

　　然後運行一下

　　./a.out 10000000000000000 10000000000000000

　　立即得到我們想要的值而沒有發生崩棧

　　20000000000000000

　　看來……不對，1億億次迭代瞬間完成？

　　objdump反彙編一把，

00000000004006b0 <add>:    4006b0:       48 8d 04 37             lea    (%rdi,%rsi,1),%rax    4006b4:       c3                      retq   

　　……原來全被優化了，gcc現在還真強大，直接猜出語義，clang測一把也是如此。

　　這個並非我們想要的，我們得用其他手段去驗證(其實我們可以抽出部分優化選項來，但此處講的是驗證思路)。

　　此處藉助我在《相互遞歸》中講的奇偶判斷，分三個函數，實現如下，

/*sub1.c*/  unsigned long long sub1(unsigned long long x)  {          return x - 1ULL;  }

/*is_odd.c*/  unsigned long long sub1(unsigned long long x);  int is_even(unsigned long long x);  int is_odd(unsigned long long x)  {          if(x == 0ULL)                  return 0;          return is_even(sub1(x));  }

/*is_even.c*/  unsigned long long sub1(unsigned long long x);  int is_odd(unsigned long long x);  int is_even(unsigned long long x)  {          if(x == 0ULL)                  return 1;          return is_odd(sub1(x));  }

　　上述函數是單獨編寫，甚至，減1的操作也單獨用一個文件來實現。如此測試的原因，就在於，我們要排除掉整體優化的可能。

　　還需要寫一個main函數來驗證，

/*main.c*/  #include <stdio.h>  int is_odd(unsigned long long x);  int main(int argc, char **argv)  {      unsigned long long x;      sscanf(argv[1], "%llu", &x);      printf("%llu is %sn", x, is_odd(x)?"odd":"even");      return 0;  }

　　以上四個文件單獨編譯，開啟-O2優化選項(當然，其實main無所謂)

　　for i in sub1.c is_odd.c is_even.c main.c; do gcc -O2 -c $i; done

　　然後鏈接，

　　gcc sub1.o is_odd.o is_even.o main.o -o a.out

　　然後我們對一個很大的數來進行測試，

　　./a.out 10000000000

　　一會兒之後，程式列印出

　　10000000000 is even

　　以上可以證明，gcc/clang對於尾遞歸優化支援的挺好。實際上，很早之前大部分C語言編譯器就支援了這點，因為從技術上來看，並不是很複雜的事情。而C++也同理。

Python

　　Python實現add如下

def add(a, b):      if a==0:          return b      return add(a-1, b+1)

　　計算add(1000,0)就崩棧了，顯然Python的發行是不支援尾遞歸優化的。

　　不過這裡棧似乎小了點，可以用sys.setrlimit來修改棧的大小，這實際上是UNIX-like的系統調用。

　　有人用捕捉異常的方式讓其強行支援尾遞歸，效率當然是損失很多的，不過這個想法倒是很好。想起以前RISC大多不支援奇邊界存取值，比如ARM，於是在內核中用中斷處理強行支援奇邊界錯誤，雖然效率低了很多，但邏輯上是通過的。異曲同工，的確也是一條路，不過我還是更加期望Python在未來支援尾遞歸優化吧。　　

JavaScript

　　依然是用add測試，編寫以下網頁

<input type="text" id="in1" />  <input type="text" id="in2" />  <input type="button" id="bt1" onclick="test()" value="測試"/>  <script type="text/javascript">  function add(a, b)  {      if (a==0) {          return b;      }      return add(a-1, b+1);  }    function test()  {      a = parseInt(document.getElementById("in1").value);      b = parseInt(document.getElementById("in2").value);      try {          alert(add(a,b));      }      catch(err) {          alert('Error');      }  }  </script>

　　就用1000000和0來測試，沒看到哪個瀏覽器不跳出Error的……據說v8引擎做好了，可是人家就不給你用……

Scheme

　　然後我們來看Scheme，按照Scheme的標準一向強行規定Scheme支援尾遞歸優化。

　　我們實現add函數如下

(define (add a b)   (if (zero? a) b (add (- a 1) (+ b 1))))

　　實現更為複雜的奇偶判斷

(define (is-odd x)      (if (zero? x) #f (is_even (- x 1))))  (define (is-even x)      (if (zero? x) #t (is_odd (- x 1))))

　　使用Chez Scheme、Racket、guile測試，使用很大的數來運算，

　　然後使用top來觀測程式的記憶體使用情況，我們發現，雖然CPU佔用率可能是100%，但記憶體的使用並不增加。就連guile這樣的一個小的實現都是如此，從而它們都是符合標準而對尾遞歸進行優化的。

Common Lisp

　　測完Scheme，再來測Scheme的本家兄弟，另外一種Lisp——Common Lisp

　　先用Common Lisp實現add，因為Common Lisp將數據和過程用不同的命名空間，導致程式碼有點奇怪(似乎很不數學)

(defun add(a b)   (if (zerop a) b (funcall #'add (- a 1) (+ b 1))))

　　使用clisp來運行

　　(add 10000 10000)

　　結果就

*** – Program stack overflow. RESET

　　因為沒有尾遞歸優化的規定，所以對於那種無限循環，Common Lisp只能選擇迭代才能保證不崩棧，比如使用do。使用do重新實現add如下

(defun add(a b)   (do    ((x a (- x 1))     (y b (+ y 1)))    ((zerop x)  y)))

　　如此，終於不崩棧了。但是似乎也改變了Lisp的味道，do顯然此處只能在設計編譯器、解釋器的時候就得單獨實現，雖然按理Lisp下這些都應該是宏，但是無論用宏如何將函數式編程映射為顯示的迭代，因為尾clisp遞歸優化不支援，則無法和系統提供的do一樣。

　　sbcl是Common Lisp的另外一個實現，在這個實現中，我們使用第一個add函數的版本，沒有發生崩棧。我們再來實現一下奇偶判斷

(defun is-odd(x)   (if (zerop x) '() (funcall #'is-even (- x 1))))  (defun is-even(x)   (if (zerop x)  t (funcall #'is-odd (- x 1))))

　　計算

　（is-even 1000000000)

　　過了幾秒，返回了結果t，證明了sbcl對尾遞歸做了優化。也終於給了我們一個更為靠譜的Common Lisp的實現。

AWK

　　選擇一種腳本語言來測試這個問題，使用GNU awk來實現add

awk '  function add(a,b)  {     if(a==0)         return b      return add(a-1, b+1)  }  {print add($1, $2)}'

　　運行後，用top來觀測記憶體佔用

　　輸入

　　100000000 1

　　讓其做加法

　　記憶體使用瞬間爆發，直到進程被系統KO。

　　話說，awk沒有對尾遞歸優化也屬正常，而且對於記憶體的使用還真不節制，超過了我的想像。不過這也與語言的目的有關，awk本就沒打算做這類事情。

Haskell

　　直接上如下Haskell程式來描述奇偶判斷

is_even x = if x==0 then True else is_odd (x-1)  is_odd x = if x==0 then False else is_even (x-1)  main = print (is_even 1000000000)

　　用ghc編譯運行，輸出True，用時33秒。

　　Haskell不虧是號稱純函數式編程，尾遞歸優化無條件支援。

Prolog

　　本不想測prolog，因為首先它並沒有所謂的函數，靠的是謂詞演化來計算，推理上的優化是其基本需求。尾遞歸本不屬於Prolog的支援範疇，當然可以構造類似尾遞歸的東西，而且Prolog當然可以完成，不會有懸念。

　　比如我們實現奇偶判斷如下：

is_even(0, 1).  is_even(X, T) :- M is X-1, is_odd(M, T).  is_odd(0, 0).  is_odd(X, T) :- M is X-1, is_even(M, T).

　　查詢

　　?- is_even(100000000,S),write(S),!.

　　得到

　　1

Erlang

　　先寫一個model包含add/even/odd三個函數，

-module(mytest).  -export([add/2,even/1,odd/1]).  add(A,B)->if A==0->B;true->add(A-1,B+1) end.  even(X)->if X==0->true;true->odd(X-1) end.  odd(X)->if X==0->false;true->even(X-1) end.

　　載入模板，並測試如下

1> c(mytest).
{ok,mytest}
2> mytest:add(1000000000,1000000000).
2000000000
3> mytest:even(1000000000).          
true
4> mytest:odd(1000000000).
false

　　顯然，Erlang對尾遞歸支援很好。

golang

　　編寫add的實現如下

package main  import "fmt"  func add(a int, b int) int {      if (a==0) {          return b;      }      return add(a-1,b+1);  }    func main() {      fmt.Println(add(100000000, 0))  }

　　運行

　　go run add.go

　　馬上崩潰

Lua

　　Lua的作者和JS的作者一樣是Lisp的粉絲，Lua的後期設計(從Lua4)據說參考了Scheme。

function odd(x)      if (x==0) then          return false      end      return even(x-1)  end  function even(x)      if (x==0) then          return true      end      return odd(x-1)  end  print(odd(io.read()))

　　運行

　　echo 1000000000 | lua5.3 x.lua

　　過程中，觀察記憶體沒有明顯變化，之後列印出了false。

　　看來，至少參考了Scheme的尾遞歸優化。

Ruby

　　Ruby的作者松本行弘也是Lisp的粉絲，當然，我想大多數程式語言的作者都會是Lisp的粉絲，因為它會給人很多啟發。

　　實現奇偶判斷如下：

#!/usr/bin/ruby    def odd(x)      if x == 0          return 0      end      return even(x-1)  end    def even(x)      if x == 0          return 1      end      return odd(x-1)  end    puts even gets.to_i

　　然而，數字大一點點，就崩棧了。Ruby並不支援尾遞歸優化。

尾聲

　　測了這些語言以及相應的工具，其實還是在於函數式編程里，尾遞歸實現的迭代是我們經常使用的手段，編譯器/解釋器的支援就會顯得很重要了。再深一步，我們會去想想，編譯器/解釋器此處該如何做，是否可以對現有的設計進行修改呢？或者，對該語言/工具的未來懷著什麼樣的期待呢？再或者，如果我們自己也設計一種程式語言，會如何設計這種程式語言呢？……