こんにちは！健康のために1日1万歩の散歩を始めたら、雨に打たれて風邪をひいた@haruguchiです。
RubyKaigi 2024 が終わって早くも2カ月が経とうとしています。私にとってのKaigi Effectはなんだろうと考えると、言語処理系やコンピュータサイエンスといった別のレイヤに興味を持ったことだと思います。特に今年の@tompngさんの発表「Writing Weird Code」ではWeird Codeを書くということの楽しさを感じたり、テストの追加や言語仕様を深く理解するのに役立つことを実感しました。
弊社ではQuine部*1なるものが発足され、熱量十分の状態です。そこで私も業務ではまず書かない Weird Code を書いてみたので紹介します。
ラムダ計算でフィボナッチ数列を出力する
ラムダ計算は関数を主体とした計算モデルの一つでチューリング完全であることが知られています。 今回はフィボナッチ数列の第0項から第10項*2までの計算を、Rubyのlambda式を用いてシミュレートしていきます。
ここで、断っておくとラムダ計算自体は決してWeird Code ではなく計算の意味論だったり、型理論に使われたり、関数型プログラミングの論理的な土台となっていたりします。ラムダ式のみで書かれたコードが見た目上奇妙に見えるという意味で Weird Codeとして紹介します。
本体
コードの全容はこちらをご参照ください。 ラムダ計算でフィボナッチ数列を計算する · GitHub
本体だけ抜粋すると以下のようになります。
# 本体(50文字折り返し) proc = ->k{->f{->f{->x{f[->y{x[x][y]}]}[->x{f[->y{x[x][y] }]}]}[->f{->l{->x{->g{->b{b}[->p{p[->x{->y{x}}]}[l ]][x][->y{g[f[->l{->p{p[->x{->y{y}}]}[->p{p[->x{-> y{y}}]}[l]]}[l]][x][g]][->l{->p{p[->x{->y{x}}]}[-> p{p[->x{->y{y}}]}[l]]}[l]][y]}]}}}}][k][->x{->y{-> f{f[x][y]}}}[->x{->y{x}}][->x{->y{x}}]][->l{->x{-> l{->x{->x{->y{->f{f[x][y]}}}[->x{->y{y}}][->x{->y{ ->f{f[x][y]}}}[x][l]]}}[l][f[x]]}}]}}[->f{->x{f[-> y{x[x][y]}]}[->x{f[->y{x[x][y]}]}]}[->f{->m{->n{-> b{b}[->m{->n{->n{n[->x{->x{->y{y}}}][->x{->y{x}}]} [->m{->n{n[->n{->p{p[->x{->y{x}}]}[n[->p{->x{->y{- >f{f[x][y]}}}[->p{p[->x{->y{y}}]}[p]][->n{->s{->x{ s[n[s][x]]}}}[->p{p[->x{->y{y}}]}[p]]]}][->x{->y{- >f{f[x][y]}}}[->s{->x{x}}][->s{->x{x}}]]]}][m]}}[m ][n]]}}[m][n]][->x{->l{->x{->x{->y{->f{f[x][y]}}}[ ->x{->y{y}}][->x{->y{->f{f[x][y]}}}[x][l]]}}[f[->n {->s{->x{s[n[s][x]]}}}[m]][n]][m][x]}][->x{->y{->f {f[x][y]}}}[->x{->y{x}}][->x{->y{x}}]]}}}][->s{->x {x}}][->s{->x{s[s[s[s[s[s[s[s[s[s[x]]]]]]]]]]}}]][ ->n{->f{->x{f[->y{x[x][y]}]}[->x{f[->y{x[x][y]}]}] }[->f{->n{->b{b}[->n{n[->x{->x{->y{y}}}][->x{->y{x }}]}[n]][->x{->s{->x{x}}}][->b{b}[->n{->n{n[->x{-> x{->y{y}}}][->x{->y{x}}]}[->m{->n{n[->n{->p{p[->x{ ->y{x}}]}[n[->p{->x{->y{->f{f[x][y]}}}[->p{p[->x{- >y{y}}]}[p]][->n{->s{->x{s[n[s][x]]}}}[->p{p[->x{- >y{y}}]}[p]]]}][->x{->y{->f{f[x][y]}}}[->s{->x{x}} ][->s{->x{x}}]]]}][m]}}[n][->s{->x{s[x]}}]]}[n]][- >x{->s{->x{s[x]}}}][->x{->m{->n{n[->n{->s{->x{s[n[ s][x]]}}}][m]}}[f[->n{->p{p[->x{->y{x}}]}[n[->p{-> x{->y{->f{f[x][y]}}}[->p{p[->x{->y{y}}]}[p]][->n{- >s{->x{s[n[s][x]]}}}[->p{p[->x{->y{y}}]}[p]]]}][-> x{->y{->f{f[x][y]}}}[->s{->x{x}}][->s{->x{x}}]]]}[ n]]][f[->n{->p{p[->x{->y{x}}]}[n[->p{->x{->y{->f{f [x][y]}}}[->p{p[->x{->y{y}}]}[p]][->n{->s{->x{s[n[ s][x]]}}}[->p{p[->x{->y{y}}]}[p]]]}][->x{->y{->f{f [x][y]}}}[->s{->x{x}}][->s{->x{x}}]]]}[->n{->p{p[- >x{->y{x}}]}[n[->p{->x{->y{->f{f[x][y]}}}[->p{p[-> x{->y{y}}]}[p]][->n{->s{->x{s[n[s][x]]}}}[->p{p[-> x{->y{y}}]}[p]]]}][->x{->y{->f{f[x][y]}}}[->s{->x{ x}}][->s{->x{x}}]]]}[n]]]]}]][->s{->x{x}}]}}][n]}]
これは全てRubyのlambda記法によって表現されています。 このコードは奇妙さを演出するためにスペースを削除したり50文字で折り返して人間にとって読みにくいものになっています。なので、ラムダ式を意味のまとまりに区切り定数に代入してみます。すると以下のようになります。
# natural number(必要のない数も存在する) ZERO = -> s { -> x { x } } ONE = -> s { -> x { s[x] } } TWO = -> s { -> x { s[s[x]] } } THREE = -> s { -> x { s[s[s[x]]] } } FOUR = -> s { -> x { s[s[s[s[x]]]] } } FIVE = -> s { -> x { s[s[s[s[s[x]]]]] } } TEN = -> s { -> x { s[s[s[s[s[s[s[s[s[s[x]]]]]]]]]] } } FIFTEEN = -> s { -> x { s[s[s[s[s[s[s[s[s[s[s[s[s[s[s[x]]]]]]]]]]]]]]] } } # bool TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } } # if IF = -> b { b } IS_ZERO = -> n { n[-> x { FALSE }][TRUE] } IS_ONE = -> n { IS_ZERO[SUB[n][ONE]] } # pair PAIR = -> x { -> y { -> f { f[x][y] } } } LEFT = -> p { p[-> x { -> y { x } }] } RIGHT = -> p { p[-> x { -> y { y } }] } # operator SUCC = -> n { -> s { -> x { s[n[s][x]] } } } SLIDE = -> p { PAIR[RIGHT[p]][SUCC[RIGHT[p]]] } # ペア型を引数に取り、右の値と右の値+1したペア型のデータを返す PRED = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] } ADD = -> m { -> n { n[SUCC][m] } } # n + m SUB = -> m { -> n { n[PRED][m] } } # n - m # z-combinator Z = -> f { ->x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] } # list EMPTY = PAIR[TRUE][TRUE] UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } } IS_EMPTY = LEFT FIRST = -> l { LEFT[RIGHT[l]] } REST = -> l { RIGHT[RIGHT[l]] } # comparable IS_LESS_OR_EQUAL = -> m { -> n { IS_ZERO[SUB[m][n]] } } RANGE = Z[-> f { -> m { -> n { IF[IS_LESS_OR_EQUAL[m][n]][ -> x { UNSHIFT[f[SUCC[m]][n]][m][x] } ][ EMPTY ] } } }] # 畳み込み演算 FOLD = Z[-> f { -> l { -> x { -> g { IF[IS_EMPTY[l]][x][ -> y { g[f[REST[l]][x][g]][FIRST[l]][y] } ] } } } }] # map MAP = -> k { -> f { FOLD[k][EMPTY][-> l { -> x { UNSHIFT[l][f[x]] } }] } } def to_nat(nat) nat[-> n { n + 1 }][0] end def to_bool(bool) IF[bool][true][false] end def to_ary(proc) ary = [] until to_bool(IS_EMPTY[proc]) ary << FIRST[proc] proc = REST[proc] end ary end # フィボナッチ数列の漸化式 FIB = Z[-> f { -> n { IF[IS_ZERO[n]][ -> x { ZERO } ][IF[IS_ONE[n]][ -> x { ONE } ][ -> x { ADD[f[PRED[n]]][f[PRED[PRED[n]]]] } ]][ZERO] } }] proc = MAP[RANGE[ZERO][TEN]][-> n { FIB[n]} ] results = to_ary(proc).map { to_nat(_1) } p results #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
とても読みやすくなったのではないでしょうか。順を追ってみていきましょう。
自然数を表現する
今回作ったのはフィボナッチ数列の第0項から第10項までを計算するラムダ計算です。計算結果は自然数で表されますが、ラムダ計算では関数しか登場しないので関数を自然数(チャーチ数)に対応づける必要があります。
# natural number ZERO = -> s { -> x { x } } ONE = -> s { -> x { s[x] } } TWO = -> s { -> x { s[s[x]] } } TEN = -> s { -> x { s[s[s[s[s[s[s[s[s[s[x]]]]]]]]]] } }
引数sをxに何回適用するかを自然数に対応づけています。例えばs[x]であれば1回の関数適用があるので1を表し、s[s[s[x]]]であれば3回関数適用されているので3を表します。これで理論上100でも1000でも自然数を表すことができます。(大変ですが、、、)
これを私たちが普段扱っている数として視認できるように変換メソッドも併せて定義しておきます。
def to_nat(nat) nat[-> n { n + 1 }][0] end to_nat(ZERO) #=> 0 to_nat(TEN) #=> 10
条件式を表現する
ラムダ計算はチューリング完全なのでbool値や条件分岐IFも表すことができます。
bool値に関しては2つの引数をとり、前者を返すのをtrueと表し、後者を返す関数をfalseで表します。
# bool TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } } # if IF = -> b { b }
IFは非常にシンプルで引数であるbをそのまま返す恒等関数になっています。
それゆえ、IF[condition][consequnce][alternative]のような使い方ができます。
# 簡約の様子 IF[TRUE][ONE][THEREE] ↓ TRUE[ONE][THREE] ↓ ONE IF[FALSE][ONE][THREE] ↓ FALSE[ONE][THREE] ↓ THREE
IFはこのままではELSIF節を表せませんが、ELSIFを表すときにはIFを入れ子にして対応します。また、bool値においてもラムダ計算では関数で表されているので値(true, false)に変換するメソッドを作っておきます。
def to_bool(bool) IF[bool][true][false] end
ペア型のデータ構造を表す
データ構造も関数で表すことができます。ここでは2つの値の組みを表すペア型のでデータ構造を作っていきます。また、ペア型のデータの左の値と右の値を取り出す関数も実装します。
# pair PAIR = -> x { -> y { -> f { f[x][y] } } } LEFT = -> p { p[-> x { -> y { x } }] } RIGHT = -> p { p[-> x { -> y { y } }] }
算術演算を表す
フィボナッチ数列の任意の項を求める場合、2つの数(に対応付けられたラムダ式)の足し算をする必要があるためラムダ式の世界の算術演算を導入する必要があります。任意の自然数*3に対し、次の自然数を取得するSUCCと前の自然数を取得するPREDそして、足し算を表すADD、引き算を表すSUBを作ります。
掛け算や、割り算も同じように実装することができますが、フィボナッチ数列の計算では使わないので割愛します。
# operator SUCC = -> n { -> s { -> x { s[n[s][x]] } } } # ペア型を引数に取り、右の値と右の値+1したペア型のデータを返す SLIDE = -> p { PAIR[RIGHT[p]][SUCC[RIGHT[p]]] } PRED = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] } ADD = -> m { -> n { n[SUCC][m] } } # n + m SUB = -> m { -> n { n[PRED][m] } } # n - m
SUCCではs[...]と...の中のn[s][x]に分けると考えやすいです。s[]は関数適用1回分で、n[s][x]は関数sをxでn回呼び出すという意味になり合計n+1回の関数適用になります。よって次の値の自然数を表すことになります。
またここからn[●][○]という形式がよく出てきますが、●を○でn回適用すると読み替えると理解しやすいです。
引き算に関するラムダ式(PREDやSUB)は少し難しいです。n回関数適用したときにn-1を表すような関数を作るためにはペア型のデータ構造をうまく使います。SLIDEというペア型を引数に取り、ペア型の右の値とそれに+1した値のペア型を返す関数を用意します。
PREDのLEFT[n[SLIDE][PAIR[ZERO][ZERO]]]の部分を見るとSLIDEを引数PAIRでn回適用していることがわかるので例えば6という数に対してPREDを適用するとイメージとして以下のようになります。
# イメージ n = 6 n[SLIDE][PAIR[0][0]] 1[SLIDE][PAIR[0][0]] → (0, 0 + 1) → (0, 1) 2[SLIDE][PAIR[0][0]] → (1, 1 + 1) → (1, 2) ... 6[SLIDE][PAIR[0][0]] → (5, 5 + 1) → (5, 6) # ペア型の左の値を取り出す LEFT[6[SLIDE][PAIR[0][0]]] → 5
もちろん実際には数に対応付けられた関数を取り出すのであくまでイメージです。
1増やしたり、1減らしたりできるようになったら nを引くことは1減らすをn回適用するという感じでADDやSUBを作ることができます。
またここで <=のような比較演算子で必要最低限のものを実装しておきます。
# comparable IS_LESS_OR_EQUAL = -> m { -> n { IS_ZERO[SUB[m][n]] } }
今回扱っている数は自然数(0含む)のみなので引き算が負の数にならないことを利用し0かどうかを判定しています。
Z-コンビネーターを表す
Z-コンビネータとは不動点コンビネータの一種で
となるような性質を持ちます。
# z-combinator Z = -> f { ->x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }
これを用いることで無名再帰を実装することができます。 余談ですが、不動点コンビネータには Yコンビネータというものもありますが、Rubyの場合 Yコンビネータを用いることができないことに注意してください。Yコンビネータの場合無限ループに陥ります。 コンビネータについての詳しい解説はここでは割愛します。詳しくは、Jim Weirichの以下の動画をご参照ください。
リストを表現する
リストというデータ構造が必要になってくるのでここで用意します。 このコードでは、ペア型のデータ構造を用いて2つの値を組にしています。これを利用して、値と次の値へのポインタを格納した連結リストを構築します。この連結リストでは、各ノードが次のノードへの参照を持つことで、データの順序を保持しながらリスト全体を構成しています。
# list EMPTY = PAIR[TRUE][TRUE] UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } } IS_EMPTY = LEFT FIRST = -> l { LEFT[RIGHT[l]] } REST = -> l { RIGHT[RIGHT[l]] }
次のようにデータを構築します。
list = UNSHIFT[ UNSHIFT[ UNSHIFT[EMPTY][THREE] ][TWO] ][ONE] # イメージ # [ONE, TWO, THREE]
またこれを可視化するためにto_aryというメソッドを用意します。
def to_ary(proc) ary = [] until to_bool(IS_EMPTY[proc]) ary << FIRST[proc] proc = REST[proc] end ary end p to_ary(list).map { to_nat(_1) } #=> [1, 2, 3]
次に範囲を表すRANGEを実装します。
RANGE = Z[-> f { -> m { -> n { IF[IS_LESS_OR_EQUAL[m][n]][ -> x { UNSHIFT[f[SUCC[m]][n]][m][x] } ][ EMPTY ] } } }]
考え方としてはrange(a, b)の場合、aからbまでの全ての要素を再起的にリストに追加しています。また、終端まで繰り返すため先ほど作成したZコンビネータを使っています。
続いて、MAPを実装するための準備として畳み込み演算(FOLD)を実装しておきます。
# 畳み込み演算 FOLD = Z[-> f { -> l { -> x { -> g { IF[IS_EMPTY[l]][x][ -> y { g[f[REST[l]][x][g]][FIRST[l]][y] } ] } } } }]
リストが空だったら初期値xを返し、そうでない場合は関数gを再起的に呼び出します。
畳み込みを実装したのでMAPは簡単に記述することができます。
# map MAP = -> k { -> f { FOLD[k][EMPTY][-> l { -> x { UNSHIFT[l][f[x]] } }] } }
MAPは引数を2つ取ります。kが元のリストでFOLDを使って畳み込みを行っています。また2つ目の引数fは適用する関数を表しています。
フィボナッチ数列の計算を表す
以上で、フィボナッチ数列を計算するのに必要な役者が揃いました。 フィボナッチ数列は
という漸化式で表されます。これをもとに実装すると以下のようになります。
FIB = Z[-> f { -> n { IF[IS_ZERO[n]][ -> x { ZERO } ][IF[IS_ONE[n]][ -> x { ONE } ][ -> x { ADD[f[PRED[n]]][f[PRED[PRED[n]]]] } ]][ZERO] } }] proc = MAP[RANGE[ZERO][TEN]][-> n { FIB[n]} ]
FIBはフィボナッチ数列の任意の項の計算になっています。 条件分岐が3つ入っており、漸化式の通りの計算を行います。
procの部分はMAP関数を使って計算結果をリストに格納している処理です。
先ほど定義したラムダ式(関数)を数やデータ構造に変換するメソッドを群を適用すると結果が得られます。
result = to_ary(proc).map { p to_nat(_1) } p result #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
今回は第0項から第10項までのフィボナッチ数列を計算しましたが、任意の数をラムダ式で表しRANGE関数に渡すことで任意の項までの計算ができます。ただし、Rubyのプログラムで実行すると関数呼び出しが多くコールスタックがオーバーフローします。(RUBY_THREAD_VM_STACK_SIZEという環境変数でスタックサイズを変更できます)
まとめ
RubyKaigi 2024に参加した私のKaigi Effectとしてラムダ計算のみでフィボナッチ数列を計算するというWeird Codeに挑戦しました。本当はラムダ計算を使ってQuineを作れないか考えたのですが、うまくできそうになかったので個人的な宿題にしたいと思います。
永和システムマネジメントでは、Ruby とアジャイルソフトウェア開発を通じてコミュニティと成長したいエンジニアを絶賛募集しています。
