関数の再帰的な定義に名前付けは必要か

lambda lang

結論から言うと, 名前を付けることなく再帰的な関数を定義することは可能. 特定のプログラミング言語でどうかというよりは抽象概念としての関数の再帰を名前なしに実現可能かどうかという話(名前なしに実現できるプログラミング言語は存在するかという話).

発端

id:naoyaさんがこういうツイートをしていた.

たとえば以下のように書いたときのlet fact =みたいな話.

let fact = n => n <= 1 ? 1 : n * fact(n-1)

ちなみに, 話は一見逸れるけど, こう書けると必然的に同じスコープ内の同一変数名の再定義で一つ前の定義を参照できないことを意味する(からそもそも同一スコープでの再定義を禁止していることも多い). 逆に, できるようにしている言語もあって, たとえばOCamlでは再帰的な定義をするときはlet rec 関数名 変数名 =と書かなければならないため, ふつうのlet~inでは同じ変数名・関数名を連続で使ってよい(右辺にその変数名を書いたら一つ前の定義が参照され、それ以降は古い方の定義はshadowされる). Scalaのforも再帰的な定義を書くことはないので同じ名前で古い値を参照できるようになっている.

(* OCaml *)
let x = 5 in
let x = x * x in
  x (* => 25 *)

// Scala
for {
  x <- Some(5)
  x <- Some(x * x)
} println(x) // => 25

言いたいこととしては, 「名前をつけられる」だけでなく「今つけようとしているその名前を, 名付けられる対象の中で使う」ことを明示的に許していないと(名前による)再帰的な定義は可能にならない*1.

自己言及するためのプリミティブ

たとえば, JavaScriptにはarguments.calleeというプリミティブがあり, これを使うと再帰呼び出しができる. これを使って以下のように階乗を求める無名関数が書ける(strict modeではダメだけど).

(function(n) { return n <= 1 ? 1 : n * arguments.callee(n-1) })

他の言語でも似たようなものはいろいろあるものの, 別のメジャーな方法としては, オブジェクト指向言語のthisも本質的には再帰的な処理を実現する方法と言える(自己言及だから). たとえばScalaでは以下のようにthisを使って階乗を求める無名関数が書ける.

new Function1[Int,Int] {
  def apply(n: Int): Int =
    if n <= 1
    then 1
    else n * this(n-1)
}

とはいえ, arguments.calleeやthis(およびapply)といった特別な名前を使っていて, なんだかこれはずるい感じがする.

不動点コンビネータによる無名再帰

言語機能としては関数のみを使い, 特別なプリミティブなしに関数の再帰を書けないものか. なんと, 書ける. 不動点コンビネータというものが(無数に)あって, これを使うと書ける. 不動点コンビネータの具体例は, たとえばYコンビネータやZコンビネータが有名で, ZコンビネータをJavaScriptで書くと以下のようになる.

let Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))

これを使うと階乗を計算する関数は以下のように書ける.

Z(f => (n => n <= 1 ? 1 : n * f(n-1)))

Z(f => (n => n <= 1 ? 1 : n * f(n-1)))(5)
// => 120

「Zって名前つけとるやないか」って? ではこう書こう.

(f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(f => (n => n <= 1 ? 1 : n * f(n-1)))

まぁ「この関数は再帰的になってます」と言われても「ほんまか?」って思ってしまうけど, なってる. 無名再帰できた. 「いやいや, 引数に名前つけまくっとるやないか」って? まぁ言いたいことはわかる.

引数にも名前をつけない

だんだん書くのが大変になってきたので, いったんラムダ計算の記法を混ぜて圧縮して書いておく. 条件分岐や四則演算はそのまま.

let Z = λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))
Z (λfn.n <= 1 ? 1 : n * (f (n - 1)))

引数を名前で表現するのをやめて, ぜんぶ#や##などと書くことにする. #の個数が「いくつ外側のλによる変数束縛か」を表すようにする.

let Z = λ (λ ## (λ ## ## #)) (λ ## (λ ## ## #))
Z (λλ # <= 1 ? 1 : # * (## (# - 1)))

Zも名前をつけるのをやめる.

(λ (λ ## (λ ## ## #)) (λ ## (λ ## ## #))) (λλ # <= 1 ? 1 : # * (## (# - 1)))

やったー! 名前がいっさいなくなった!

この表現の仕方はDe Bruijn indexと呼ばれている.

De Bruijn indexは名前ではないのか?

今回は(数値も登場して紛らわしいので)#の個数でDe Bruijn indexを表現したけど, ふつうは単に数字を使う. その場合, 数字は名前ではないのか? 名前はおそらく自然数と1対1に対応がつけられる(自然数と同型)だろうから, 数字で表現することと名前をつけることはイコールではないのか?

De Bruijn indexを名前だと思うと少しおかしなところがあって, それは式が評価されると名前がどんどん変わってしまう点. たとえば

λ (λλ ## #) #

という式の1段内側の関数適用を簡約すると

λλ ## #

となり, #だったものが##に変わってしまう. こんなコロコロ変わってしまうものを名前と言っていいのか?? 名前とはなんなのだ???

逆に名前ではないとしたら, いやもしかしたら名前なのかもしれないが名前かどうかという話はいったん忘れて, このDe Bruijn indexとはなんなのかと言うと, λ項をグラフで表現したときの束縛関係を表す辺になっている.

graph TD
    Lx((λ)) --- Ly((λ))
    Ly --- Lz((λ))
    Lz --- y(( ))
    y -.->|##| Ly
    Lz --- z(( ))
    z -.->|#| Lz
    Lx --- x(( ))
    x:::red -.->|#| Lx

    classDef red fill:#ff3366, stroke:#993366;

graph TD
    Lx((λ)) --- Lz((λ))
    Lz --- y(( ))
    y:::red -.->|##| Lx
    Lz --- z(( ))
    z -.->|#| Lz

    classDef red fill:#ff3366, stroke:#993366;

「名前」と言うとノードそのものにラベルが付いていてほしい感じがするが, ノードそのものではなく他のノードとの関係についたラベルだから, あまり名前っぽくはない. まぁ変数名でないというだけで関係を表す名前なのだと強弁されたら, そうかもしれないけど.

名前をいっさいつけないプログラミング言語

ではもう名前はいっさいやめてしまおう. コンビネータ計算に従って作られたLazy Kのような言語では, 言語のプリミティブは基本的にSやKといったコンビネータのみで, 変数名という概念がない. この言語で書く人が何かを名付けるということはない.

コンビネータ計算はチューリング完全なので, 再帰的に計算する関数であっても表現できる. あるいは不動点コンビネータそのものも以下のようにコンビネータの式で書き表せる(Iは(S K K)の略).

Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
不動点コンビネータ - Wikipedia

これを直に書き下すにはヒルベルト脳*2になる必要があって頭の体操どころではないけど, 幸いなことに任意のλ項はコンビネータの式に機械的に変換できる. そういう変換を使って階乗を計算するプログラムをLazy Kで書いている人もいる.

こういったプログラミング言語が存在する以上, 「関数の再帰的な定義を実現するのに名前付けは必要か?」と問われればNoと言わざるを得ない.

そもそもどういう話だったのか

もともとは, おそらく『記号と再帰』という書籍からの引用で, 再帰を記号論的に捉えるとどうなるかという話だと思う.

『記号と再帰』は読んでいないので「三項」というのがなんのことなのかちょっとよくわからないけど, こういう話だろうか??

記号論（セミオティクス）は、チャールズ・サンダース・パースによる、「表現、内容、指示対象」の三項に基づく記号学である。

記号学 - Wikipedia

だとすると, De Bruijn indexで無名化したところくらいまでは, 無名ではあるものの「指示対象」みたいな話は健在で, わからないではない. ただこれは再帰かどうかはあまり関係なく, 「変数束縛」という概念のあるラムダ計算では避けて通れない(から再帰が書けない単純型付ラムダ計算でも「指示対象」みたいなものは本質的に存在していることになるはず).

けれどコンビネータ計算までいくとなんだかよくわからなくなってくる. たぶんヒルベルト流の論理体系の記号論的解釈みたいなものをちゃんと考えないと, ぜんぜん自明ではない気がする.

記号論についてはぜんぜんよく知らないので頓珍漢なことを言っているかもしれない. 「名前を付けることで, 不動点コンビネータみたいな大変なものを持ち出さずとも, 再帰を自然に表現できるね」くらいの話であれば「そうだね」と思う.

追記 2022-08-18T11:20:27+09:00

追記 2022-08-18T12:05:27+09:00

追記 2022-08-18T13:30:12+09:00

id:mandel59さんのブックマークコメント:

関数の再帰的な定義に名前付けは必要か - 貳佰伍拾陸夜日記

そもそも『記号と再帰』に不動点関数の話が出てきて、最終的に「三次性は不動点関数であることが示唆された」(7.6) って書いてるんだよな

2022/08/18 13:07

あー, 話の流れの向きはそっち向きなんですね. 記号論における3次性(っていうのは三項の「3」のことと解釈してます)は, 不動点関数(に起因する?)と思うことができるかもしれない, って話なわけですよね? (その主張が正しいかはともかく)それなら言いたいことはわかるし, ぜんぶコンビネータで書いた場合はあまり関連性がなくなって見えるけどとくに問題はないですね. 逆の, プログラミングにおける再帰(や不動点関数)の性質は記号論の三項関係に帰着されるという話かと思っていたから「そうでもない場合がありそう」と思ってしまっていたのでした. つまり再帰を記号論的に解釈しているのではなく, 記号論を再帰や不動点を使って説明している, と.

*1:言語処理系を書いてみるとわかりやすくて, 変数の定義を処理しようとしたら, 具体的な定義はまだわからない段階で変数名とそれが指す定義(が後で入るはずの入れ物)をいったん環境に積む必要がある

*2:普通の論理ではなくヒルベルト流の論理体系で考えること

#ラムダ計算 #再帰

tarao 読者になる

広告を非表示にする
コメントを書く