Adways Advent Calendar 14日目の記事です。
http://blog.engineer.adways.net/entry/advent_calendar/archive
今は昔でもなくつい最近、とある西新宿の新宿グランドタワー38階に正直な40代のシステムエンジニアがいました。←僕のことです。菊池です。
ある晴れたリリース前の忙しい日のことでした、いつものように僕が「自分をプログラミングしろ！」タタタターン！と勢いよくプログラミングしていたところ、うっかりキーボードを滑らせて、いつも使っている大事なプログラミング言語（ Ruby ）を /dev/null の池に落としてしまいました。
さて、困りました。これでは仕事になりません。
ターミナル越しに /dev/null の池を覗き込むと、目の前に女神が現れてこう言いました
「あなたの落としたプログラミング言語はこれですか？」
似た話では金の斧が返ってきたようなので、これはきっと「金のプログラミング言語（ gold-lang ）」ということですね。
金のプログラミング言語文法
# gold-lang の使い方 foo = λ { |引数ひとつ| 関数の本体 } # 定義 foo.β(引数ひとつ) # 実行
以下、説明の都合上、文字列や == など Ruby から拝借しているものがありますので、あらかじめご了承下さい。
ということで、唐突ですが今回は僕が手に入れたこの「金のプログラミング言語（ gold-lang ）」について、軽くじっくり紹介したいと思います。
※さっそくこの言語を irb で試してみよう！以下のコードを入力するとこの言語を試せるよ！
def λ # 引数をひとつに制限 -> (x) { yield x } end class Proc alias :β :call end
実行例
irb(main):001:0> def λ irb(main):002:1> -> (x) { yield x } irb(main):003:1> end irb(main):004:0> irb(main):005:0* class Proc irb(main):006:1> alias :β :call irb(main):007:1> end # 定義 irb(main):009:0> a = λ { |s| "Hello, #{s}!" } # 実行 irb(main):010:0> a.β('World') => "Hello, World!" # 定義して実行 irb(main):011:0> λ { |s| "Hello, #{s}!" }.β('World') => "Hello, World!" # 定義して実行入れ子パターン irb(main):012:0> λ { |a| λ { |b| "#{a}, #{b}!" } }.β('Hello').β('World') => "Hello, World!"
たったこれだけでどこまでやれるものなのか、やり始めたら意外といろいろ出来るんですよ。それでは、ひとつひとつ見てみましょう。
その１：引数をそのまま返す
Id = λ { |x| x }
試しにさっきの irb で実行してみよう！
irb(main):11:0> Id.β('こんにちは') => "こんにちは"
この Id はあまりに単純なんですが、これは案外便利なもので、これから紹介するコードの中にちょいちょい出てきます。探してみて下さいね。
その２：論理演算
いったい、この言語でプログラミングの基本となる論理演算が出来るのでしょうか！？どうやって！？無理じゃないの？と思ってしまいますが、こんな風にして出来るんです。
# # 真偽値 # True = λ { |x| λ { |y| x }} # y は捨てちゃう False = λ { |x| λ { |y| y }} # x は捨てちゃう # # 論理演算 # Not = λ { |p| p.β(False ).β(True ) } And = λ { |p| λ { |q| p.β(q ).β(False) }} Or = λ { |p| λ { |q| p.β(True ).β(q ) }} Xor = λ { |p| λ { |q| p.β(Not.β(q)).β(q ) }}
試しにさっきの irb で実行してみよう！
irb(main):011:0> True.β('真').β('偽') => "真" irb(main):012:0> False.β('真').β('偽') => "偽"
True, False は λ の中に λ があるので、β すると λ が返ってくるので、そこに β すると値が確定します。
僕は「違う、違う。そうじゃない」と否定ばかりする人が苦手なのですが、これをプログラミングしてみましょう。
irb(main):016:0> Not.β(Not.β(True)).β('はい').β('いいえ') => "はい"
ということで「違う、違う。そうだ」ということになりますね。そうなんです。
試しに以下のコードを実行して true になることを確認してみよう！論理演算が動くよ！
Not.β(True ) == False Not.β(False) == True And.β(True ).β(True ) == True And.β(False).β(True ) == False And.β(True ).β(False) == False And.β(False).β(False) == False Or.β(True ).β(True ) == True Or.β(False).β(True ) == True Or.β(True ).β(False) == True Or.β(False).β(False) == False Xor.β(True ).β(True ) == False Xor.β(True ).β(False) == True Xor.β(False).β(True ) == True Xor.β(False).β(False) == False
どうでしょう。この言語で論理演算できるようになったと思います。間違いなくこの言語のスキルがレベルアップしましたね！
その３：ゼロを含む自然数の演算
とはいえ「数字もないこんな世の中じゃ」となるので、レベルアップが計算できるようにゼロを含む自然数を導入しましょう。
# # ゼロを含む自然数 # # Zero = λ { |f| λ { |x| x }} # False と同じ。第一引数の f が第二引数の x に適用されない # One = λ { |f| λ { |x| f.β(x) }} # 第一引数の f が第二引数の x に１回適用される # Two = λ { |f| λ { |x| f.β(f.β(x)) }} # 第一引数の f が第二引数の x に２回適用される # Three = λ { |f| λ { |x| f.β(f.β(f.β(x))) }} # Four = λ { |f| λ { |x| f.β(f.β(f.β(f.β(x)))) }} # Five = λ { |f| λ { |x| f.β(f.β(f.β(f.β(f.β(x))))) }} Zero = False IsZero = λ { |f| f.β(λ { |x| False }).β(True) } # Zero の時 True を返す Succ = λ { |n| λ { |f| λ { |x| f.β(n.β(f).β(x)) }}} # ひとつ増やす Pred = λ { |n| λ { |f| λ { |x| n.β(λ { |g| λ { |h| h.β(g.β(f)) }}).β(λ{ |u| x }).β(Id) }}} # ひとつ減らす Plus = λ { |m| λ { |n| λ { |f| λ { |x| m.β(f).β(n.β(f).β(x)) }}}} # 足し算 Sub = λ { |m| λ { |n| n.β(Pred).β(m) }} # 引き算 Mult = λ { |m| λ { |n| λ { |f| m.β(n.β(f)) }}} # 掛け算 Gte = λ { |m| λ { |n| IsZero.β(Sub.β(n).β(m)) }} # 等しいか大きいとき True Eq = λ { |m| λ { |n| And.β(Gte.β(m).β(n)).β(Gte.β(n).β(m)) }} # 同じ数のとき True
コメントの所に書きましたが、この言語では第一引数が第二引数に何回適用されるかで数字を表現します。ちなみに Zero は False と同じ形なので False の別名になっています。 それと、負の数は表現できないので Zero から Pred や Sub しても Zero となります。なのでここでは 5 - 7 = 0 になります。
試しに実行してみよう！
# Zero は第一引数が適用されない irb(main):062:0> Zero.β(λ { |x| '★' + x }).β('！') => "！" # Zero + 1 = 1 なので、第一引数が一回適用される irb(main):063:0> Succ.β(Zero).β(λ { |x| '★' + x }).β('！') => "★！" # Zero + 1 + 1 = 2 なので、第一引数が二回適用される irb(main):064:0> Succ.β(Succ.β(Zero)).β(λ { |x| '★' + x }).β('！') => "★★！" # 2 + 3 = 5 irb(main):065:0> Two = Succ.β(Succ.β(Zero)) irb(main):066:0> Three = Succ.β(Two) irb(main):067:0> Plus.β(Two).β(Three).β(λ { |x| '★' + x }).β('！') => "★★★★★！"
残念ながらページの余白が少ないので全ての演算について実行例は載せられませんが、みなさんお手元でお試しください。
その４：ペア（タプル）
論理演算もゼロを含む自然数の演算も出来ることがわかりました。しかしながら、データ構造はどうでしょう。基本のペア（タプル）は表現できるのでしょうか？見てみましょう。いったいどうなっているのか！？
# # ペア # Pair = λ { |s| λ { |b| λ { |f| f.β(s).β(b) } } } First = λ { |p| p.β(True ) } Second = λ { |p| p.β(False) } Nil = False IsNil = λ { |p| p.β(λ { |s| λ { |b| λ { |f| False } } }).β(True) }
Pair, First, Second じゃなくて Cons, Car, Cdr の方がいいじゃないか！と思った人もいるかもしれません。そうですよねそっちの方がカッコ（括弧）いい！分かります。そのとおり。実はこの記事、最初はそっちで書いていました。
それはさておき、よーく見てみると First, Second は True と False を使って実装されています。こんな使い方が出来るんですね。
それではさっそくペアを使ってみましょう！
# ペア作成 irb(main):047:0> a = Pair.β('りんご').β('みかん') # ペアの最初の要素取得 irb(main):048:0> First.β(a) => "りんご" # ペアの二番目の要素取得 irb(main):049:0> Second.β(a) => "みかん"
その５：リスト
さっきのペアは二つの値をひとまとめにするデータ構造。とても単純なものですが、これがあるとリストを作ることができます。 さっそくペアを使ってリストを作ってみましょう！
# リスト作成 irb(main):053:0> fruits = Pair.β('アップル').β(Pair.β('オレンジ').β(Pair.β('レモン').β(Nil))) # リストの要素取得 irb(main):054:0> First.β(fruits) => "アップル" # リストの要素取得 irb(main):055:0> First.β(Second.β(fruits)) => "オレンジ" # リストの要素取得 irb(main):056:0> First.β(Second.β(Second.β(fruits))) => "レモン"
ペアの一番目の要素が値になっていて、二番目の要素が次のペアになっていますね。一番最後のお尻（二番目の要素）は Nil で終端してます。
さて、みなさん。我々の手元には「ゼロを含む自然数」と「リスト」があります。これを使えば、リストの n 番目の要素を取得するプログラムが簡単に書けるんじゃないでしょうか！？それと、リストの全ての要素に対して何か処理したくなったことでしょう。なりましたよね！
その６：不動点コンビネータ
この環境では Y コンビネータだと永久ループしてしまうので、Z を使います。なんのこっちゃ！？ちなみに、再帰呼び出しが無いのでこれを使ってループ処理します。
# # 不動点コンビネータ # # Y = λ { |f| λ { |x| f.β( x.β(x) ) }.β(λ { |x| f.β( x.β(x) ) }) } Z = λ { |f| λ { |x| f.β(λ { |y| x.β(x).β(y) }) }.β(λ { |x| f.β( λ { |y| x.β(x).β(y) }) }) }
この言語に興味をもったあなたはきっと不動点コンビネータについて調べたくなったことでしょう。フフフ... 僕の布教活動の成果がそろそろ現れたでしょうか。「Y？Z？なにが違うの？」 そんなあなたの楽しみのために説明しないで次に進みます（笑）
その７：リスト処理
リストの n 番目の要素を取得したり、リストとリストを繋げたりといったことが出来ますよ。
# # リスト処理 # # NthSecond = λ { |n| λ { |p| n.β(Second).β(p) } } # Nth = λ { |n| λ { |p| First.β(NthSecond.β(n).β(p)) }} NthSecond = λ { |n| λ { |p| n.β(λ { |q| IsNil.β(q).β(Id).β(λ { |r| Second.β(r) }).β(q) }) .β(p) } } # p のリストから n 番目の Second を返す Nth = λ { |n| λ { |p| λ { |q| IsNil.β(q).β(Id).β(λ { |r| First.β(r) }).β(q) }.β(NthSecond.β(n).β(p)) } } # p のリストから n 番目の値（ First ）を返す # 二つのリストを繋げる Concat = Z.β( λ { |g| λ { |a| λ { |b| IsNil .β(a) .β(Id) .β( λ { |c| Pair .β( First.β(a)) .β(g.β(Second.β(a)).β(c)) } ) .β(b) } } } ) # リストの要素に f を適用する Map = Z.β( λ { |g| λ { |f| λ { |p| IsNil .β(p) .β(Id) .β( λ { |q| Pair .β( f .β(First.β(q))) .β(g.β(f).β(Second.β(q))) } ) .β(p) } } } )
僕も書いててわけがわからなくなったので（笑）改行入れてます。
ちなみにリストから n 番目の要素を取得するには、リストに対して Second を n 回繰り返して First すれば良いってことですよね。それぞれ NthSecond と Nth として実装してあります。ここでは n にリストのサイズ以上の値を指定した場合、Nil を返すようにした（つもり）です。
それではさっそく実行してみましょう！
# いろいろ面倒なので数字を用意しておきます irb(main):111:0> One = Succ.β(Zero) irb(main):112:0> Two = Succ.β(One) irb(main):113:0> Three = Succ.β(Two) irb(main):114:0> Four = Succ.β(Three) # リスト作成 irb(main):115:0> fruits = Pair.β('アップル').β(Pair.β('オレンジ').β(Pair.β('レモン').β(Nil))) # リストの n 要素をさっき作ったゼロを含む自然数を使って取得 irb(main):124:0> Nth.β(Zero).β(fruits) => "アップル" irb(main):125:0> Nth.β(One).β(fruits) => "オレンジ" irb(main):126:0> Nth.β(Two).β(fruits) => "レモン" irb(main):127:0> Nth.β(Three).β(fruits) == Nil => true irb(main):128:0> Nth.β(Four).β(fruits) == Nil => true
その８：PPAP
ここまでをまとめると、こういうこともできますね！
irb(main):129:0> pen = Pair.β('ペン').β(Nil) irb(main):130:0> apple = Pair.β('アップル').β(Nil) irb(main):131:0> pineapple = Pair.β('パイナップル').β(Nil) irb(main):132:0> applePen = Concat.β(apple).β(pen) irb(main):133:0> pinapplePen = Concat.β(pen).β(pineapple) irb(main):134:0> ppap = Concat.β(pinapplePen).β(applePen) irb(main):135:0> Map.β(λ { |x| p x }).β(ppap) "ペン" "パイナップル" "アップル" "ペン"
ペンパイナポーアポペーン♫
さいごに
今回は、最近色々な言語に導入されてきた Lambda （ラムダ）を使って、いろいろなことができることを紹介しました。ただの無名関数かと思いきや、論理演算やゼロを含む自然数、ペア（タプル）、そしてリスト処理まで出来ることが分かってもらえたと思います。
単純なことの組み合わせでいろいろ表現できる、そんな面白さが伝われば幸いです。実はもっともっと奥深いラムダ計算ですが、今回は紙面の都合上ここまでの紹介とさせて頂きます。時間があったら SKI など調べてみて下さい。さらに楽しめると思いますよ！
おまけ
# # gold-lang.rb # # Created by Jun Kikuchi <kikuchi.jun@adways.net> # Copyright (c) 2016 Jun Kikuchi. All rights reserved. # def λ ->(x) { yield x } end class Proc alias :β :call end # a = λ { |s| "Hello, #{s}!" } # a.β('World') # p λ { |s| "Hi, #{s}!" }.β('Foobar') # p λ { |a| λ { |b| a + b } }.β('foo').β('bar') Id = λ { |x| x } # # Boolean # # If = λ { |p| λ { |x| λ { |y| p.β(x).β(y) }}} True = λ { |x| λ { |y| x }} # y は捨てちゃう False = λ { |x| λ { |y| y }} # x は捨てちゃう Not = λ { |p| p.β(False ).β(True ) } And = λ { |p| λ { |q| p.β(q ).β(False) }} Or = λ { |p| λ { |q| p.β(True ).β(q ) }} Xor = λ { |p| λ { |q| p.β(Not.β(q)).β(q ) }} # # Natural Number # # Zero = λ { |f| λ { |x| x }} # False と同じ # One = λ { |f| λ { |x| f.β(x) }} # Two = λ { |f| λ { |x| f.β(f.β(x)) }} # Three = λ { |f| λ { |x| f.β(f.β(f.β(x))) }} # Four = λ { |f| λ { |x| f.β(f.β(f.β(f.β(x)))) }} # Five = λ { |f| λ { |x| f.β(f.β(f.β(f.β(f.β(x))))) }} Zero = False IsZero = λ { |f| f.β(λ { |x| False }).β(True) } Succ = λ { |n| λ { |f| λ { |x| f.β(n.β(f).β(x)) }}} Pred = λ { |n| λ { |f| λ { |x| n.β(λ { |g| λ { |h| h.β(g.β(f)) }}).β(λ{ |u| x }).β(Id) }}} Plus = λ { |m| λ { |n| λ { |f| λ { |x| m.β(f).β(n.β(f).β(x)) }}}} Sub = λ { |m| λ { |n| n.β(Pred).β(m) }} Mult = λ { |m| λ { |n| λ { |f| m.β(n.β(f)) }}} Gte = λ { |m| λ { |n| IsZero.β(Sub.β(n).β(m)) }} Eq = λ { |m| λ { |n| And.β(Gte.β(m).β(n)).β(Gte.β(n).β(m)) }} One = Succ.β(Zero ) Two = Succ.β(One ) Three = Succ.β(Two ) Four = Succ.β(Three) Five = Succ.β(Four ) # # Pair # Pair = λ { |s| λ { |b| λ { |f| f.β(s).β(b) } } } First = λ { |p| p.β(True ) } Second = λ { |p| p.β(False) } Nil = False IsNil = λ { |p| p.β(λ { |s| λ { |b| λ { |f| False } } }).β(True) } # # Combinator # # Y = λ { |f| λ { |x| f.β( x.β(x) ) }.β(λ { |x| f.β( x.β(x) ) }) } Z = λ { |f| λ { |x| f.β(λ { |y| x.β(x).β(y) }) }.β(λ { |x| f.β( λ { |y| x.β(x).β(y) }) }) } # # List # # NthSecond = λ { |n| λ { |p| n.β(Second).β(p) } } # Nth = λ { |n| λ { |p| First.β(NthSecond.β(n).β(p)) }} NthSecond = λ { |n| λ { |p| n.β(λ { |q| IsNil.β(q).β(Id).β(λ { |r| Second.β(r) }).β(q) }) .β(p) } } Nth = λ { |n| λ { |p| λ { |q| IsNil.β(q).β(Id).β(λ { |r| First.β(r) }).β(q) }.β(NthSecond.β(n).β(p)) } } Concat = Z.β( λ { |g| λ { |a| λ { |b| IsNil .β(a) .β(Id) .β( λ { |c| Pair .β( First.β(a)) .β(g.β(Second.β(a)).β(c)) } ) .β(b) } } } ) Map = Z.β( λ { |g| λ { |f| λ { |p| IsNil .β(p) .β(Id) .β( λ { |q| Pair .β( f .β(First.β(q))) .β(g.β(f).β(Second.β(q))) } ) .β(p) } } } )
次は須藤さんの記事です。
