Zenn
☯

Rubyのアロー演算子を用いたラムダ計算の基礎表現

2020/11/17に公開
Ruby
#
関数型プログラミング
#
ラムダ計算
#
yコンビネータ
tech

記事の主旨は 『ラムダ（λ）記法ではなくプログラミング言語の無名関数のみを用いたラムダ計算の解説』 です．ラムダ計算の概要についてはWikipeida等を参照．平たく言うと，関数型プログラミングの理論的背景として位置づけられている計算モデルです．

以前，別サイトにて『Pythonのlambda式を用いたラムダ計算の基礎表現』という記事を書いたのですが，同じ内容をRubyでやってみたら字面が面白かったので（おい）こちらで記事作成．例によって，ポエムに限りなく近い技術記事です．

Rubyのアロー演算子を用いた無名関数の基礎

関数f(x)=x（引数に与えた値がそのまま戻ってくる）を表現したい時，関数名fは特に必要なく，Rubyでは様々な記法を用いて，関数名（メソッド名）なしの『無名関数』を表現できます．これを，ラムダ計算では ラムダ抽象（lambda abstraction） と呼びます．この記事では，次のアロー演算子を用いた記法に統一します．

->x{x}

->の直後のxがf(x)のxに対応し，{x}のxがf(x)=xの右辺のxに対応します．

この無名関数を，RubyのREPLでxに実際に値を与えて実行したい場合は，次のように，その値を[]でくくって無名関数の直後に記述します．

>> ->x{x}[10]
=> 10

値を与えて関数を呼び出すことを，ラムダ計算では 関数適用（application） と呼びます．なお，引数なしの無名関数も定義できます．

>> ->{"Hello"}[]
=> "Hello"

引数として指定して実際に計算式で用いられている名前は 束縛変数（bound variable） と呼ばれ，同じ名前を用いなければなりません．逆に言えば，同じ名前であればどのようなものでもよく，次の通り，引数yを用いた無名関数も，f(x)=xと同じ関数と考えることができます．このような束縛変数の名前変更を，ラムダ計算では α変換（α-conversion） と呼びます．

>> ->y{y}[10]
=> 10

ラムダ計算では，関数の引数は原則としてひとつのみです．同様の表現をg(x,y)=x+yで行いたい場合は，処理本体である{}の中で更に無名関数を記述することで，関数定義自体を戻り値とします．関数適用したい時は，[]でくくった値を続けて記述します．

>> ->x{->y{x+y}}[10][20]
=> 30

複数の引数をもつ関数をひとつの引数の関数の組合せで表現することを カリー化（currying） と呼びます．カリー化された関数についてもα変換は有効であり，たとえば，上記の無名関数定義のうち，引数xの名前をzに変更しても，同じ関数処理として扱われます．

>> ->z{->y{z+y}}[10][20]
=> 30

ただし，zではなく，もう一方の引数として用いられているyと同じ名前にしてしまうと（当然ながら）計算式そのものが変化してしまうため，同じ関数処理とはなりません（α変換できない）．次の実行例では，ひとつ目の引数の値[10]は次の引数の値[20]に上書きされ，20+20=40が出力されています．

>> ->y{->y{y+y}}[10][20]
=> 40

関数の引数は，数値だけでなく，無名関数も指定できます．次の例では，引数fと引数xをとってf(x)*2の計算を行う無名関数に，引数fに[->y{y+1}]を，引数xに[10]を指定して関数適用しています．

>> ->f{->x{f[x]*2}}[->y{y+1}][10]
=> 22

上記は，fを->x{x+1}で書き換えた次の無名関数と同じ処理を行っています．

>> ->x{(x+1)*2}[10]
=> 22

束縛変数に引数の値を適用して書き換えることを，ラムダ計算では β簡約（β-reduction） と呼んでいます．

なお，関数を引数に指定する場合は，指定する関数定義を代入文で変数に代入してから渡すことも可能です．

>> inc = ->y{y+1}
=> #<Proc:0x00a51f50@(irb):19 (lambda)>
>> ->f{->x{f[x]*2}}[inc][10]
=> 22

また，関数の戻り値として無名関数定義を返すこともできます．これは，引数として受け取った関数定義を用いて構成した関数定義を返すことも含まれます．

>> inc_ret = ->{->y{y+1}}
=> #<Proc:0x00a4c9e8@(irb):21 (lambda)>
>> inc = inc_ret[]
=> #<Proc:0x00a4b518@(irb):21 (lambda)>
>> fnc_ret = ->f{->x{f[x]*2}}
=> #<Proc:0x00a48860@(irb):23 (lambda)>
>> fnc = fnc_ret[inc]
=> #<Proc:0x00a47018@(irb):23 (lambda)>
>> fnc[10]
=> 22

関数の引数や戻り値にできる関数定義は 第一級オブジェクト（first-class object） と呼ばれます．また，関数定義を引数や戻り値とする関数を 高階関数（higher-order function） と呼びます．

応用例

真理値

ラムダ計算によって， チャーチ真理値（Church booleans） と呼ばれる真偽表現が可能です．これは，引数をふたつとる無名関数をふたつ考え，真の無名関数では必ずひとつ目の引数を返し，偽の無名関数では必ずふたつ目の引数を返すというものです．

>> ->x{->y{x}}[10][20]    # 真
=> 10
>> ->x{->y{y}}[10][20]    # 偽
=> 20

ここで，true falseを返す比較演算子>の代わりに，上記の真偽の無名関数を返すGTを定義します．

>> def GT(a, b)
>>   if a > b then
?>     ->x{->y{x}}
>>   else
>>     ->x{->y{y}}
>>   end
>> end
=> :GT

このGTを用いて判断分岐を行っているのが次の実行例です．

>> GT(20,10)["True"]["False"]
=> "True"
>> GT(10,20)["True"]["False"]
=> "False"
>> a = 10
=> 10
>> b = 20
=> 20
>> GT(a, b)["a>b"]["a<=b"]
=> "a<=b"
>> GT(b, a)["a>b"]["a<=b"]
=> "a>b"

自然数と演算

ラムダ計算によって， チャーチ数（Church numerals） と呼ばれる自然数を表現できます．考え方としては，引数として指定した関数が，同じく引数として指定された初期値に何回適用されたかによって表します．

>>  zero = ->f{->x{x}}
=> #<Proc:0x01efeb80@(irb):107 (lambda)>
>>   one = ->f{->x{f[x]}}
=> #<Proc:0x01ef6120@(irb):108 (lambda)>
>>   two = ->f{->x{f[f[x]]}}
=> #<Proc:0x01e70f38@(irb):109 (lambda)>
>> three = ->f{->x{f[f[f[x]]]}}
=> #<Proc:0x01db7ce8@(irb):110 (lambda)>
>>  four = ->f{->x{f[f[f[f[x]]]]}}

次は，適用関数を->x{x+1}，初期値を0とすることで，チャーチ数を整数に変換するメソッドToINTを定義・実行している例です．

>> def ToINT(ch) ch[->x{x+1}][0] end
=> :ToINT
>> ToINT(zero)
=> 0
>> ToINT(one)
=> 1
>> ToINT(two)
=> 2
>> ToINT(three)
=> 3
>> ToINT(four)
=> 4

チャーチ数に+1する場合は，単純に，適用関数をもう一回適用する関数を返すことで定義できます．次の例では，+1する無名関数を定義してChINCに代入しています．

>> ChINC = ->ch{->f{->x{f[ch[f][x]]}}}
=> #<Proc:0x0118eb70@(irb):9 (lambda)>
>> ToINT(ChINC[two])
=> 3
>> ToINT(ChINC[one])
=> 2
>> ToINT(ChINC[three])
=> 4

+1する関数定義を用いて足し算が表現できます．

>> ChADD = ->ch{->ch1{ch1[ChINC][ch]}}
=> #<Proc:0x0117cae0@(irb):13 (lambda)>
>> ToINT(ChADD[one][three])    # 1 + 3 = 4
=> 4
>> ToINT(ChADD[four][zero])    # 4 + 0 = 4
=> 4
>> ToINT(ChADD[three][two])    # 3 + 2 = 5
=> 5

-1を行う関数は関数適用を減らす必要があるため煩雑で，1回関数適用した結果としての無名関数を返すよう定義することになります．

>> ChDEC = ->ch{->f{->x{ch[->g{->h{h[g[f]]}}][->u{x}][->u{u}]}}}
=> #<Proc:0x010e95b8@(irb):24 (lambda)>
>> ToINT(ChDEC[three])
=> 2
>> ToINT(ChDEC[one])
=> 0
>> ToINT(ChDEC[four])
=> 3

-1を行う関数定義を用いて引き算が表現できます．ここで想定されるチャーチ数は自然数であるため，結果は0以上であり，したがって，第一引数＞第二引数でなければなりません．

>> ChSUB = ->ch{->ch1{ch1[ChDEC][ch]}}
=> #<Proc:0x01296750@(irb):30 (lambda)>
>> ToINT(ChSUB[three][one])    # 3 - 1 = 2
=> 2
>> ToINT(ChSUB[four][one])     # 4 - 1 = 3
=> 3
>> ToINT(ChSUB[four][three])   # 4 - 3 = 1
=> 1

掛け算とべき乗は，-1や引き算はもちろん，+1や足し算よりも単純に表現できます．これは，チャーチ数が関数の適用回数で表現されており，その性質をそのまま利用すれば良いためです．

>> ChMUL = ->ch{->ch1{->f{ch1[ch[f]]}}}
=> #<Proc:0x0128aeb8@(irb):35 (lambda)>
>> ToINT(ChMUL[two][three])    # 2 * 3 = 6
=> 6
>> ToINT(ChMUL[four][three])   # 4 * 3 = 12
=> 12
>> ChPOW = ->ch{->ch1{ch1[ch]}}
=> #<Proc:0x01280928@(irb):39 (lambda)>
>> ToINT(ChPOW[two][three])    # 2^3 = 8
=> 8
>> ToINT(ChPOW[two][four])     # 2^4 = 16
=> 16
>> ToINT(ChPOW[one][four])     # 1^4 = 1
=> 1

再帰関数

プログラミング言語で再帰関数を定義するには，通常，自分自身を呼び出すための関数名が必要になります．ですが，ラムダ計算では基本的に，関数定義を関数名なしの無名関数として表現します．ここでは，g(f)=f(g(f))と循環的に成り立つ関数gである 不動点コンビネータ のひとつで，無名関数のままで定義可能なYコンビネータ（Zコンビネータ）を用いて，再帰関数の定義を行います．

まず，次の無名関数定義を考えます．

->x{x[x]}[->x{x[x]}]

この関数定義をβ簡約，すなわち，左側の無名関数本体のx[x]のxそれぞれに，値としての->x{x[x]}を適用すると，元の関数定義と同じものが導かれます．

->x{x[x]}[->x{x[x]}]
↓
x → ->x{x[x]}
[x] → [->x{x{x]}]
↓
->x{x[x]}[->x{x[x]}]

この無名関数をRubyで実行すると，いつまでも自己適用することになり，無限ループが発生します．

>> ->x{x[x]}[->x{x[x]}]
Traceback (most recent call last):
       16: from (irb):1:in `block in irb_binding'
       15: from (irb):1:in `block in irb_binding'
       14: from (irb):1:in `block in irb_binding'
       13: from (irb):1:in `block in irb_binding'
       12: from (irb):1:in `block in irb_binding'
       11: from (irb):1:in `block in irb_binding'
       10: from (irb):1:in `block in irb_binding'
        9: from (irb):1:in `block in irb_binding'
        8: from (irb):1:in `block in irb_binding'
        7: from (irb):1:in `block in irb_binding'
        6: from (irb):1:in `block in irb_binding'
        5: from (irb):1:in `block in irb_binding'
        4: from (irb):1:in `block in irb_binding'
        3: from (irb):1:in `block in irb_binding'
        2: from (irb):1:in `block in irb_binding'
        1: from (irb):1:in `block in irb_binding'
SystemStackError (stack level too deep)

このループする無名関数定義のx[x]それぞれを引数にとる関数fを引数としてとる無名関数定義を考えます．

->f{->x{f[x[x]]}[->x{f[x[x]]}]}

ここで，引数としての関数fがもつ引数の名前をgとするとf[g]⇔f[x[x]]であり，gにはx[x]が適用されます．つまり，関数fの処理内部で引数gが関数名として呼び出されると，x[x]が呼び出されることになります．したがって，fおよび自己適用パターンx[x]を含む同じ無名関数定義が繰り返し適用されることになり，fについて再帰的な適用を行うことが可能となります．

f[g][->x{f[x[x]]}]
f[x[x]][->x{f[x[x]]}]       # gの呼び出し1回目
f[->x{f[x[x]]}[->x{f[x[x]]}]
f[f[g]][->x{f[x[x]]}]
f[f[x[x]]][->x{f[x[x]]}]    # gの呼び出し2回目
f[f[->x{f[x[x]]}][->x{f[x[x]]}]
f[f[f[g]]][->x{f[x[x]]}]
f[f[f[x[x]]]][->x{f[x[x]]}] # gの呼び出し3回目
...

この式は Yコンビネータ（Y combinator） と呼ばれ，無名関数定義に対して，その関数定義の引数の名前を用いて自分自身を呼び出す機能を提供します．

しかし，Rubyを含む多くのプログラミング言語では，関数処理よりも先に，その関数に指定された引数の方が先に実行されてしまいます．上記の例でいえば，fそれぞれの処理よりも先にgの呼び出しが次々と行われ，先と同じく自己適用を繰り返して無限ループとなります．次は，Yコンビネータに階乗計算を行う無名関数を適用して実行『しようとした』例です．

>> ->f{->x{f[x[x]]}[->x{f[x[x]]}]}[->g{->n{n==0?1:n*g[n-1]}}][5]
Traceback (most recent call last):
       16: from (irb):5:in `block (2 levels) in irb_binding'
       15: from (irb):5:in `block (2 levels) in irb_binding'
       14: from (irb):5:in `block (2 levels) in irb_binding'
       13: from (irb):5:in `block (2 levels) in irb_binding'
       12: from (irb):5:in `block (2 levels) in irb_binding'
       11: from (irb):5:in `block (2 levels) in irb_binding'
       10: from (irb):5:in `block (2 levels) in irb_binding'
        9: from (irb):5:in `block (2 levels) in irb_binding'
        8: from (irb):5:in `block (2 levels) in irb_binding'
        7: from (irb):5:in `block (2 levels) in irb_binding'
        6: from (irb):5:in `block (2 levels) in irb_binding'
        5: from (irb):5:in `block (2 levels) in irb_binding'
        4: from (irb):5:in `block (2 levels) in irb_binding'
        3: from (irb):5:in `block (2 levels) in irb_binding'
        2: from (irb):5:in `block (2 levels) in irb_binding'
        1: from (irb):5:in `block (2 levels) in irb_binding'
SystemStackError (stack level too deep)

そこで，自己適用の先行実行を避けるため，x[x]を本体とした無名関数を新しく定義し，実際に実行が必要になるまで，すなわち，上記でいうgが関数として呼び出されるまで自己適用を据え置くようにします．ラムダ計算としては，η簡約（η-reduction）と呼ばれる書き換えの逆である η展開（η-expansion） を行い，x[x]に余分な変数（ラムダ計算では 自由変数 と呼ばれる）yを導入して->y{x[x]}[y]に書き換えます．

->f{->x{f[->y{x[x][y]}]}[->x{f[->y{x[x][y]}]}]}

この記述によって，引数gに適用されるのはx[x]ではなく->y{x[x][y]}となり，gが引数の値と共に呼び出された時に初めて，xのそれぞれに->x{f[->y{x[x][y]}]}が適用されると共に，gの引数の値がyに適用されることでfが実行されます．Yコンビネータをこのように修正した無名関数を Zコンビネータ（Z combinator） と呼びます．

次は，Zコンビネータに階乗計算を行う無名関数を適用して実行『した』例です．fが先に実行されn==0の判定が優先されることから，無限ループに陥らず処理が収束して終了しています．

>> ->f{->x{f[->y{x[x][y]}]}[->x{f[->y{x[x][y]}]}]}[->g{->n{n==0?1:n*g[n-1]}}][5]
=> 120

なお，次のように，関数処理本体に自己適用パターン（下記ではx[x]のα簡約であるg[g]）を埋め込むことで無名の再帰関数を実現することも可能です．この場合は，自己適用パターンが引数ではなく関数処理本体の一部であるため先行実行されず，無限ループとなりません．

>> ->g{g[g]}[->g{->n{n==0?1:n*g[g][n-1]}}][5]
=> 120

備考

更新履歴

  • 2020-11-18：記事に関する冒頭の説明を整理
  • 2020-11-17：初版公開

Discussion