Chapter 03

ラムダ式を用いた再帰

TAKIZAWA Yozo
TAKIZAWA Yozo
2021.12.19に更新

ループ式による関数適用

プログラミング言語には通常,繰り返し,または,既に行った処理の時点に巻き戻るための構文や命令があります.同じ処理を繰り返すための仕組みをプログラミングによって実現できることは,コンピュータの基本的な機能であり,必須であるとも言えます.

ところが,関数型パラダイムには,この繰り返しを直接表現する方法がありません.というのも,そもそも数学の関数に繰り返しの考え方がないからです.あえてあるとするなら,和と積を繰り返し適用する\Sigma\prodが相当するかもしれませんが,あくまで足し算,掛け算に限定されます.

そこで,繰り返しと同じ効果の,別の表現が関数型パラダイムで実現できないかを検討してみます.さしあたりfpLISPで,値0から始めて,1ずつ増やしながら+を5回繰り返し適用する処理を表現します.

fpLISP
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))
15

このような処理を行う関数名を仮にsumとすると,次のような関係が成り立ちます.

(sum 5) は (+ 5 (sum 4)) に等しい
(sum 4) は (+ 4 (sum 3)) に等しい
(sum 3) は (+ 3 (sum 2)) に等しい
(sum 2) は (+ 2 (sum 1)) に等しい
(sum 1) は (+ 1 (sum 0)) に等しい
(sum 0) は 0 に等しい

この関係を言葉にすると,『x0の時の(sum x)0,それ以外の(sum x)(+ x (sum (- x 1))』となります(xが負の時は想定していません).ここから,次のラムダ式が導かれます.

fpLISP
(lambda (x)
  (if (eq x 0) 0
      (+ x (sum (- x 1)))))

残念ながら,このラムダ式はうまく評価できません.なぜなら,このラムダ式自身を呼び出すための関数名であるsumが定義できないためです[1].自己の関数規則を自己の中で呼び出せるようにするには,更に工夫が必要となります.[2]

次は,無限ループを発生させるラムダ式です.この式自体は,何も評価結果を出力しないまま,自己と同じ関数規則の適用を永遠に繰り返します[3]

fpLISP
((lambda (u) (u u)) (lambda (u) (u u)))


このループ式をよく見ると,値として渡される右側のラムダ式のうち,(u u)が何度も適用を繰り返す部分となっています.そこで,前節の最後に登場したラムダ式

fpLISP
(lambda (x)
  (if (eq x 0) 0
      (+ x (sum (- x 1)))))

におけるsum(u u)に置き換えます.

fpLISP
(lambda (x)
  (if (eq x 0) 0
      (+ x ((u u) (- x 1)))))

そして,uを引数とするラムダ式として呼び出せるようにします.

fpLISP
(lambda (u)
  (lambda (x)
    (if (eq x 0) 0
        (+ x ((u u) (- x 1))))))

これを,最初に自己適用するためのラムダ式(lambda (u) (u u))に値として渡します.

fpLISP
((lambda (u) (u u))
 (lambda (u)
   (lambda (x)
     (if (eq x 0) 0
         (+ x ((u u) (- x 1)))))))

このようにすることで,ラムダ式の中の(lambda (x) ...)が,(u u)の引数(- x 1)によって次々と呼び出される,すなわち,自己の関数規則が自己の中で次々と呼び出されることになります.このラムダ式全体に,引数として値5を渡して評価してみましょう.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x)
      (if (eq x 0) 0
          (+ x ((u u) (- x 1)))))))
 5)
15

このような,自己の関数規則を自己の中で呼び出す関数を再帰関数と呼びます.関数型プログラミングにおいて,何かを繰り返し行わせたい場合は,この再帰関数で表現することになります[4]

末尾再帰による繰り返し

上記の+を繰り返し適用する関数規則ですが,引数をふたつに増やして,次のように定義することもできます.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x r)
      (if (eq x 0) r
          ((u u) (- x 1) (+ r x))))))
 5 0)
15

この場合,(u u)の引数(- x 1)および(+ r x)は,次のように変化していきます.

((u u) (- 5 1) (+ 0 5))
((u u) (- 4 1) (+ 5 4))
((u u) (- 3 1) (+ 9 3))
((u u) (- 2 1) (+ 12 2))
((u u) (- 1 1) (+ 14 1))
⇒ x = (- 1 1) = 0となるので,r = (+ 14 1) = 15が評価結果となる.

これはちょうど,変数xrに計算結果を次々と代入しているように見えます.ですが,実際には自己の関数規則を次々と呼び出していく中で,引数xrの値を評価結果に置き換えているだけに過ぎません.このことは,代入の仕組みを利用する計算手順(アルゴリズム)の多くを,再帰関数としてそのまま表現できることを意味します.このようなスタイルの再帰処理を末尾再帰と呼びます.

次は,n番目のフィボナッチ数0番目は01番目は1,それ以降のn番目はn-1番目の値+n-2番目の値)を求める末尾再帰関数の例です.fibという名前を付け,21番目のフィボナッチ数を求めています.

fpLISP
((lambda (fib) (fib 21 0 1))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (n a b)
      (if (eq n 0) a
          ((u u) (- n 1) b (+ a b)))))))
10946

この関数の規則本体は引数nabをもち,次のように,評価を繰り返しながら引数の値を置き換えています.

n → n - 1
a → b
b → a + b

練習問題

次は,10の階乗を求める末尾再帰のつもりで作成したラムダ式ですが,うまく動きません.どこを修正すれば良いか考え,解答して下さい.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x r)
      (if (eq x 0) r
          ((u u) (- x 1) (* r x))))))
 10 0)
0
脚注
  1. 前章で扱った,もうひとつのラムダ式を用いた名前付けは,そのもうひとつのラムダ式の関数規則の中でのみ有効です.このような名前参照の範囲は,レキシカルスコープと呼ばれています. ↩︎

  2. どこからでも参照できる変数を用いた代入の仕組みがあれば,変数sumにこのラムダ式を格納することで,自己と同じ式を呼び出せるようになりますが,本書では,そのような代入の仕組みも想定していません. ↩︎

  3. LISP処理系によっては,同様の式によってコンピュータ本体に高負荷がかかる処理となることがありますので注意して下さい ↩︎

  4. 今回,再帰を実現しているラムダ式の組み合わせは,不動点コンビネータと呼ばれるもののうち,無名関数であるラムダ式のみで実現できる表現のひとつであるUコンビネータと呼ばれるものです. ↩︎