Rubyを使ったラムダ計算の詳しいシミュレーション方法

プリアンブル

最近、「計算の本質」という本を読んだのですが、主に計算の根底にある部分について書かれています。そして、今日、Y字結合器を使って再帰を実装できることを知り、私の世界観は基本的に崩壊しました。そこで、この機会に、計算の基本的な理解をまとめておこうと思い、記事を書きました。そうすることで、より良い学習ができるようになりました。また、Rubyの構文を使ってLambdaの話をいくつか説明する。

0.オフトピック

この前夜祭を祝して、LOLを早めに切り上げ、Emacsを開いて、以下のコードをたたき出した（ちなみにここではRubyのシングルピース・メソッドを宣伝している）。

{{コード

上記のコードの結果は

subject = "couple"
object = "dog"

def subject.do_something(who)
 "#{self} abuse #{who}"
end

if __FILE__ == $0
 p subject.do_something(object)
 p object.do_something(subject)
end

明らかに、夫婦は犬を「虐待」することができますが、犬は夫婦を「虐待」することができません。だから、2番目の実行文はエラーを報告することになる。上記のことはRubyのエレガントな部分でもあり、同じ種類の他のインスタンス（上記のインスタンスはすべて文字列）に影響を与えることなく、指定したインスタンスに直接メソッドを定義することができるんだ。

1. 機能に関するある程度の基本的な理解

オフトピック」ってなんだ？まあ、無駄なことですが、何か意味があるのでしょう。今日のトピックは、Rubyを使ってLambdaアルゴリズムをシミュレートすることで、Wikiでは以下のように説明されています。

ラムダアルゴリズムは、最小の汎用プログラミング言語と呼ぶことができる。変換規則（変数の代入）と関数の定義方法から構成されています。ラムダ演算の一般性は、計算可能なあらゆる関数がこの形式で表現・評価できることである。

命令型プログラミング言語を使う場合、主語にも目的語にもなる文字列や数値、ブール値などに注目しがちです。通常は、"off-topic "の "dog "や "couple "のように、変数という形で扱われる。しかし、この記事の焦点は「罵倒」という言葉、つまり私たちがよく述語と呼ぶものである。コンピュータでは、通常、メソッドとか関数と呼ぶことが多い。

Wikiには「ラムダは最小の汎用プログラミング言語」とも書かれているので、ラムダを使って数字や文字列、ブーリアンなどの一般的なデータ型をシミュレートすることは可能でしょうか。それは次でお話します。

1) Rubyの関数

Ruby では、関数は一級市民といえますが、Ruby の強力なオブジェクト指向機能（クラスやモジュールに注目させる）のために、その鋭さは影をひそめがちで、Ruby で関数を作るには、とても簡単な方法があるのです

"couple dog abuse"
dog.rb:11:in `<main>': undefined method `do_something' for "dog":String (NoMethodError)

これはProcオブジェクトを返します。このオブジェクトは、実は、私たちが普段操作している関数オブジェクトと似ています。しかし、ここでは関数に名前をつけていないので、無名関数であることが理解できる。では、この関数はどのように呼び出されるのでしょうか？この関数を呼び出すには非常にセマンティックな方法があり、変数で関数を受け入れる必要さえありません。

[1] pry(main)> -> x { x + 2 }
=> #<Proc:0x007fc171dc6010@(pry):1 (lambda)>

Rubyには引数検出機能があり、渡された引数が関数の定義に使われたものと一致しない場合、ArgumentError例外が投げられる。さらに、Ruby には構文解析があり、それを使って [2] pry(main)> -> x { x + 2 }.call(1000) => 1002 [3] pry(main)> -> x { x + 2 }.call(1000, 100000) ArgumentError: wrong number of arguments (given 2, expected 1) from (pry):3:in `block in __pry__' Procインスタンスを呼び出すための引数をラップしています。

は次のように使用します。

Proc#[]

2）コリドー化

Wikiでは以下のように説明されています。

コンピュータサイエンスにおいて、カリー化（英語：Currying）とは、carridizationまたはgarridizationとも訳され、複数の引数を受け付ける関数を、単一の引数（元の関数の第1引数）を受け付け、残りの引数を受け付ける新しい関数に変換して結果を返す手法のことである。
ここまでで、Rubyで無名関数を作る基本的な方法を説明しましたが、次はRubyでカーネル化のプロセスをシミュレートする方法を見てみましょう。

[4] pry(main)> ADD_THREE = -> x { x + 3 }
=> #<Proc:0x007fd8341ffc48@(pry):4 (lambda)>
[5] pry(main)> ADD_THREE[1000]
=> 1003

PS: 関数を定義するとき、認識しやすくするためにパラメータを括弧で囲みますが、実際には括弧は付けても付けなくてもよく、関数は -> x, y, z { x + y + z } のように書くこともできます。
上記の関数はどのように共焦点化されるのでしょうか？コロカライズの定義によると、複数引数の関数は、複数の単一引数の関数を返すネストした関数として書くことができます。読みやすいように、Rubyのスクリプトファイルにコードを書いてみます。

{{コード

実行結果

実際、この関数を呼び出すたびに引数が1つだけの関数が返され、返された関数は現在の関数が呼び出されたときに渡された引数を保持しており、これは通常クロージャと呼ばれるものである。実際に望ましい計算結果が得られるのは、最後の関数が呼び出されて返された後なのだ。

もちろん、Proc#[]を使ってもっと簡単に呼ぶこともできます（後半はこの方法で統一します、コード効率もいいですし）。

# currying.rb
ADD_THREE_NUMBER_NEW = -> (a) {
 -> (b) {
 -> (c) {
 a + b + c
 }
 }
}

if __FILE__ == $0
 p ADD_THREE_NUMBER_NEW.call(1).call(2).call(3)
end

2.ラムダ計算のシミュレーション

Lambda Lambdaは最小の汎用プログラミング言語なので、今度はRubyのProcという既製品のLambdaで何かを演じてみましょう。まだ難しいことは自分でもできないので、ここでは一番簡単なものをシミュレートしてみることにします。

1) 数値

まず、数字のモデル化をやってみよう。書籍「The Nature of Computing」では、より直感的なパラグラフが用意されており、私が概説した一般的な考え方は以下の通りである。

数字を直接使う方法がなく、述語（アクション）しかないとすると、数を特徴として記述するためには、数えるというアクションを繰り返すしかなく、数えるというアクションは、実は、以下のように書く必要があるLambda式なのです。

わかりやすいのは、0を表現したいときは0回カウントして0回メソッドを呼び、1を表現したいときは1回メソッドを呼び出すということです。

そうすると、0から2を表すには、単純に

6

少し混乱するかもしれませんが、実はどちらもLambdaを使っていて、関数p（アクションをカウントする）と基底値xを引数に取り、ZEROなら基底値xを直接返し、ONEなら基底値xを引数に関数pを一度呼び出すというものです。

ここでは、基底値xをうまく表現できないので、直感的にわかるように、Rubyの組み込み数値0を基底値として借用し、別途countアクションを定義する必要があります。

[1] pry(main)> require('. /currying')
=> true
[2] pry(main)> ADD_THREE_NUMBER_NEW[1][2][3]
=> 6

実は、数えるという動作は、元の基準値に1を足すことであり、結局、スクリプトを一律に書いてしまうのです

{コード

このスクリプトを解析環境に導入し、関連するステートメントをいくつか実行すると、期待通りの結果が得られます。

ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }

このシミュレーションは、すでに組み込みの数値型があるRubyでは全く実用的ではありませんが、Lambda演算を理解するための良いきっかけになるでしょう。

2) ブール演算

数値の話の後に、ブーリアン型について簡単に説明します。ブーリアン型も比較的基本的なデータ型です。そして、boolean型のシミュレーションはもっと簡単です。trueとfalseの2つの引数を取る関数を書けば、trueは第1引数を、falseは第2引数を直接返します。

CALCULATE = -> (n) { n + 1 }

検証として、もう一つ解析スクリプトを書いてみよう。C言語のようにブーリアン型がない言語では、falseは0、trueは1より大きい値を使うと記憶していますが、ここでは単純に0と1を基本値として、Lambdaの計算が正しいかどうか検証してみます。

# coding: utf-8

# number.rb
ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }

def to_integer(proc)
 calculate = -> (n) { n + 1 }
 # where 0 is the base value
 proc[calculate][0]
end

実行スクリプトを導入して試す

[1] pry(main)> require('. /number')
=> true
[2] pry(main)> to_integer(ZERO)
=> 0
[3] pry(main)> to_integer(ONE)
=> 1
[4] pry(main)> to_integer(TWO)
=> 2

予想通り、FALSE関数は0に、TRUE関数は1に分解され、我々のシミュレーションは正しいものとなりました。

上記の警告は、定数が重複しているためで、とりあえず無視してよい。

3）数字が0かどうかの単純な判定

最後に、先ほどシミュレーションしたnumeric型とboolean型を使って、入力されたパラメータが0かどうかを判定し（ZEROを定義するかどうか）、シミュレーションの結果としてboolean（TRUEまたはFALSE）を返すメソッドを定義して、簡単なシミュレーションをします。アルゴリズムは簡単です

TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}

これをLambdaでどう表現するか。前にも言ったように、ZERO関数は2つの引数を取ります。1つ目は関数、2つ目は基準値です。ZERO関数を渡すと、ZEROを呼び出したときに、第1引数に何を渡しても、呼び出しの結果は第2引数（つまりベース値）をそのまま返してくれます。

その後、我々は戻ってその第2パラメータとしてTRUE、第1パラメータとしてFALSEを返す関数は、その後、我々は新しい関数がZERO関数とそれを呼び出す受信した場合、直接TRUEを返すことはありません考える？また、ONE、TWOなどの他のメソッドは、→（x）{ FALSE }このプロセスを実行します。

というコードを書くことができます。

# boolean.rb
TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}

def to_boolean(proc)
 proc[1][0]
end

実行結果は

[1] pry(main)> require('. /boolean')
/Users/lan/Personal/Ruby/boolean.rb:1: warning: already initialized constant TRUE
/Users/lan/Personal/Ruby/boolean.rb:2: warning: already initialized constant FALSE
=> true
[2] pry(main)> to_boolean(FALSE)
=> 0
[3] pry(main)> to_boolean(TRUE)
=> 1

最初のZEROだけが期待した値で、最終的に1を返します（これは真です）。それ以外は、値0を表現するのに必要なラムダ式ではありません。

3. エピローグ

この記事は少し長くなりますが、Ruby内部のProcクラスを紹介し、関数の共起やLambda式についても最低限の説明をします。最後に、Lambda式を使って数値型と論理型をモデル化する例と、モデル化した型をベースにしてユーティリティメソッドIS_ZEROを定義しています。

この記事では、まだ吸収できないハイレベルなものが多いので、あまりハイレベルなものは取り上げず、吸収できたときに引き続き投稿していきたいと思います。お読みいただき、ありがとうございました。以上がこの記事の内容の全てです、この記事の内容があなたの勉強や仕事に少しでも役に立てれば幸いです、もし質問があればメッセージを残して交換することができます、BinaryDevelopを応援していただきありがとうございました。 {応援ありがとうございました。