Church numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足
Church Numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足 後半は佐藤雅彦先生に教えてもらいました. SICP Exercise 2.4 〜 Exercise 2.6 誤解を恐れずに大雑把にいうと, λ計算では名前つきのシンボル (名前付きの手続き) による再帰呼出しや special form が使えないところが Scheme と違うところです. そのため, λ計算を Scheme で行うためにはいろいろな工夫が必要となります. そのポイントは closure (閉包) と呼ばれる構造です. 自然数 n の Church numeral を c(n) とすると, c(n) f x = (f ... (f x)), ただし, f は n 回出現. となることを利用します. まず, c0 と successor を定義します. (SICP Ex.
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
イプシロン計算ってなんですかぁ？ こんなもんですよぉ - 檜山正幸のキマイラ飼育記 (はてなBlog)
ラムダ計算は、計算モデルとしてだけでなく、手計算の実際的手段としても役立ちます。しかし、通常使われる各種変換（アルファ、ベータ、イータ、デルタ）ではうまく計算が進まないときがあります。例えば、gがfの逆関数のとき、f(g(y)) は y に簡約されるのだけど、f(g(y)) ⇒ y って簡約規則は通常のラムダ計算ではうまく定式化できません（いや、できるかもしれませんが、僕にはうまい方法が思いつきません）。 そこで、ラムダ計算に加えてイプシロン計算も使うとよさそうです。でも、イプシロン計算は、ラムダ計算ほどにポピュラーではないですね。簡単な例でイプシロン計算を紹介しましょう。 内容： イプシロン記号とイプシロン項 イプシロン項の意味 イプシロン項が定義する関数 例題：gがfの断面（セクション）であること イプシロン記号とイプシロン項 負の数-1とか、無理数√2とかを導入するとき、次のような定
Lambda Animator : animated reduction of the lambda calculus
mode with Java Web Start or in an Applet Usage Screenshots Feedback Acknowledgements Related work Lambda Animator is a tool for demonstrating and experimenting with alternative reduction strategies in the lambda calculus. Eager languages reduce arguments before function application. Lazy languages reduce arguments, if needed, after function application. Reductions can also be performed within func
ラムダ計算ＡＢＣ
仙台ロジック倶楽部 ラムダ計算ＡＢＣ 数学セミナー９２年８月号より Ａ. ラムダ計算とは 今から６０年程前、プリンストン大学の若手論理学者Ａ．チャーチが、関数の新しい表記法を提案しました。ラムダ記法と呼ばれるその表記法では、例えば二乗を計算する関数は λx.x^2 と表します。従来の"f(x)"という書き方は、それが関数を表すのか、関数のxにおける値を表すのかが曖昧なので、ラムダ記法では、関数fのxにおける値をfxで示し、xにおける値がf(x)となる関数fをλx.f(x)と表すのです。 "f(x)"という表記法の欠陥は、高校の数学までではほとんど表面化しませんが、大学に入ってから定義域や値域が関数の集合になるような高階関数（オペレータとか作用素とも呼びます）を扱いだすとすぐわかります。作用素などというとひどく特殊なもののようですが、関数f(x)にその導関数f'(x)を対応させる微分演算子Ｄ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
