Y Combinator
このファイルで、我々は、再帰手続き理論の重要な成果の一つであるYコンビ ネータを導出する。手続きに名前を与える必要がない場合があることが知られ ている。たとえば、 ((lambda (x) (+ x 1)) 6) は、それを行なう手続きを名付けることなく1を6に加える。しかし、再帰手続 きはどうだろうか? たとえば、 (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) は数nの階乗を計算するが、手続きの最終行で自身に再帰できるようにするた めに名前"fact"が必要であるように思える。しかし、我々はそれは必要でない ことを理解し、そのプロセスにおいて、Schemeを使うことに関する多くの勘を やしなうだろう。我々は一ステップずつ進み、各ステップで"fact"をわずかに 変更する。 Step 1. 最初のアイディア
F#入門
コンビネータ ラムダ計算の親戚みたいな理論として、コンビネータ理論がありますが このページの趣旨は、理論的なことはさておき コンビネータを使って遊んでみようというものです。 例えばコンビネータを使うと 「引数の順序を入れ替えたり、入れ替えて適用する」 といったことができます。 なお、ここではλ式について少し知識があることを仮定しています。 最初にコンビネータとは何かというと 「自由変数を含まないλ式」、と定義されています。 自由変数とはλ式において束縛されていない変数のことで letによる関数定義をλ式の定義とみなすと 引数が束縛変数、 既に定義されてる識別子が自由変数 になります。 コンビネータに関する本として スマリヤンの本「To mock a mocking bird」 (邦題：数学パズル ものまね鳥をまねる―愉快なパズルと結合子論理の夢の鳥物語) は有名です。 この本の楽しいところ
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.
コンビネータでVM実装:old
編集中。 尚、内容の正しさは全く保証できません。 「○○は△△です」と言い切りの形で書いてあっても、鵜呑みにしない方が安全です。 概要目的ルール予習復習基礎コンビネータの準備ユーティリティマクロの用意他のコンビネータ条件分岐自然数その一(失敗)演算その一(失敗)自然数その二(チャーチ数)演算その二ToDo参考リンク 概要 http://hw001.gate01.com/eggplant/tcf/unlambda/ 「全てのオブジェクトは関数である」という理念の極北とも言うべきunlambda。 そのunlambdaの基本となるS, Kコンビネータだけを用いて、論理的に正しく動作するVMを実装します。 尚、速度や実行コスト等は度外視します。 unlambdaには「難読化」というポリシーも含まれている為、VMの実装にはunlambdaそのものではなく、S式を利用します。具体的にはscheme。
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
賢人鳥 - あどけない話
分かった！ 分かった！ 分かった！ 自己言及 ものまね鳥(M)は、自己言及する鳥なんだ！ Haskell では、型推論がジャマして、ものまね鳥を実現できない。 -- Mx = xx m x = x x -- エラーになる ヒバリ(L)も実現できない！ -- Lxy = x(yy) l x y = x (y y) -- エラーになる 当然の帰結として、Haskell では再帰を使わないと賢人鳥(Y)を実現できない！ 賢人鳥1 wikipediaの Y コンビネーターに書かれている最初の賢人鳥はこう。 (define Y (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))) これは SLL だ！ ;; Sxyz = xz(yz) (define S (lam
Rubyのある風景 - Y+Combinator+2
以前取り上げたY Combinatorですが、何故"Y"なのかと思って調べてみたところ、どうやら"To Mock a Mockkingbird" がもとになっているようです。 この本では色々な鳥の名前を各ラムダ式に割り当てて、組み合わせ理論(Combinatory Logic)を解説しています。 ちなみにYは"Why Bird (aka Sage Bird)"だそうで。 さて、組み合わせ理論の有名な話として、 K = λxy.x S = λxyz.xz(yz) の二つを用いることで、チューリングマシンと等価な計算能力が得られるということが知られています(ということは、この二つさえあれば、今一般に使われているプログラムは全て記述できるわけですね)。 例えば、恒等写像I(λx.x)は SKK = (λxyz.xz(yz))(λxy.x)(λxy.x) = (λyz.(λxy.x)z(yz))(
おとうさん、ぼくにも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 となります。λの引数部分を与えられた引数で置
combinator - Nobuhisa's diary
コンビネータとは自由変数を含まないλ項のことをいいますが、Yコンビネータ以外あまり取り上げられていない気がするのですが、これも100年に1度の金融危機の影響かとか、WBC楽しみですねだとか、そういえば今年雪祭り行けなかったんですよとか、最近携帯変えましたとか色々あるのですが、自分の練習もかねて、そんなコンビネータ達と戯れたいと思います。 沢山ある！ Y以外にも広く知られている（？）コンビネータはいっぱいあるようですが、その中からいくつか。 I ≡ λx.x K ≡ (λx.(λy.x)) //以下、簡単に λx y.x と書きます F ≡ λx y.y M ≡ λx.xx S ≡ λx y z.xz(yz) B ≡ λx y z.x(yz) C ≡ λx y z.xzy L ≡ λx y.x(yy) Y ≡ (λx.xx)(λx.xx) (SLL) （当てるアルファベットが違うのはたまに見
Yコンビネータ - Mae向きなブログ
相変わらず，Yコンビネータについては理解できていないのですが，昨日に引き続き，Rubyの学習もかねて，Schemeで書かれたYコンビネータをRubyで書くことに挑戦しました。 http://d.hatena.ne.jp/kazu-yamamoto/20080402/1207127522 でYコンビネータは，以下のように紹介されています。 (lambda (le) ((lambda (f) (f f)) (lambda (g) (le (lambda (x) ((g g) x)))))) 昨日は，たくさん出てくるlambdaをRubyでどう書けば良いのか分からなかったのですが，今日はなんとかYコンビネータをRubyで書くことができました。 y = lambda { |le| lambda { |f| f.call(f) }.call( lambda { |g| le.call(lambda
コンビネータメモ - ボクノス
メモメモ。 Z Yをη変換するとZ Y f = f (Y f) Z f = f (λy.Z f y)η変換ってなんだかよくわからんけど、λを一個追加(削除?)することらしい。 とりあえずη変換してみよう。 (lambda (x) x) ; ↓ η変換 (lambda (y) ((lambda (x) x) y)) 一回lambdaで囲んでも意味は変わらない。 η変換すると、理論上での計算の意味合いは全く一緒だけど、計算機上では評価順序が変わるのがポイントらしい。 不動点オペレータ - ボクノスコレネ。 これが純粋なYコンビネータ。 Y = λf.(λx.f (x x)) (λx.f (x x))外側は意味が無いので、一番内側の(x x)をaでη変換すると、(λa.(x x) a)。 代入する。 Z = λf.(λx.f (λa.(x x) a)) (λx.f (λa.(x x) a))おぉ
Y コンビネータって何？ - IT戦記
このエントリの 親友へ。ブログを書こう。 - IT戦記 y がブログを始めたみたいなので、読んでみた。 で、最新のエントリを読んでみたら、 Y コンビネータというものについて書いてあったので、 Y Combinatorが凄すぎる！ - yuji1982の日記 Y コンビネータって何ってところから、自分でもいろいろ考えてみた。 結局なんなのかさっぱり分からなかったんですが、自分が考えたことをまとめておく まず、フィボナッチ数を求める fib を定義する var fib = function(n){ return (n <= 2) ? 1 : (arguments.callee(n-1) + arguments.callee(n-2)); }; fib(10); おお！ JS すげー！名前は n しか使ってねーよ！ めでたし、めでたし。。。。じゃなくて！ JS が素晴らし過ぎて話が終わってしま
不動点オペレータについて
不動点オペレータY 階乗関数は、 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) のように、再帰的に定義できる。 再帰的定義を行なう場合はdefineやletrecを使うけど、 代わりにletを使うと再帰的定義はできない。 defineやletrecをどうしても使いたくないなら、多少工夫がいる。 例えば、factの引数を増やすという方法がある。 (let ((fact (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))) (fact fact 10)) ⇒ 3628800 (中略) 不動点オペレータYを使うと次のように書ける。 (let* ((Y (lambda (g) ((lambda (s) (g (lambda (x) ((s s) x))
羊堂本舗 脳ざらし紀行 (2003-10-22)
_ [ネット] Fの不動点 ラムダ式fを受けとったら、ラムダ式を返す次のようなプロシージャFを定義します。 (define F (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) とりあえず簡単な例で計算してみましょう。Fに常に5を返すラムダ式を渡して、返ってきたラムダ式に3を渡してみましょう。 ((F (lambda (n) 5)) 3) いくらになるでしょうか。 ;; => (* 3 (f (- 3 1))) => 15 15になりました。そして、次のようなプロシージャ fを考えます。 (define f (lambda (s) (F (lambda (x) ((s s) x))))) fはラムダ式を受けとるようなラムダ式sを受けとって、ラムダ式を生成した後、それをFに渡します。 さて、次のような単純なプロシージャhを
Unlambda
Your Functional Programming Language Nightmares Come True. 関数型言語の悪夢がやってくる Unlambdaについて 公式サイト: http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/ Unlambdaは、obfuscated programming languages (混乱させるプログラム言語、といったところでしょうか) の一種として開発された言語です。 しかしただそれだけではなく、純粋関数型言語というもう一つの特徴も持っています。 そのためオブジェクトは関数しかなく、数値や文字列などというものは(組み込みでは)存在しません。 しかしこの極限的な状況でのプログラムには、実に楽しいものがあります。 このページでは、そんなUnlambdaのプログラミングの解説を行い
翻訳:コンビネータ論理チュートリアル
このページは、Combinatory Logic Tutorialの翻訳です。 http://homepages.nyu.edu/~cb125/Lambda/ski.html 基本的に超訳です。 訳の正しさは全く保証されません。 訳のおかしい部分は多数あります。 翻訳元サイトの許可を取ったりはしていません。 無認可です。 訳者による前書きと感想コンビネータ論理チュートリアル 訳者による前書きと感想 訳してみたものの、ちょっと、たったこれだけの説明では、はじめてコンビネータ論理を知った人が読んで充分に理解できるとは思えない。 どうも、この文書は、原文の上位ディレクトリにあるLambda tutorialを読んだ後に読むべきものっぽいようだ。 しかし、流石にこっちまで訳す気力は無い。 そういう訳で、これだけを読むよりは、Unlambdaのチュートリアルを読んだ方がずっと、コンビネータ論理を理解
コンビネータでVM実装
翻訳:プログラミング言語Lazy_Kを訳したら、大体、コンビネータVMがどんなものになるのか分かって、満足してしまったので、当分は続行する予定無し。 古いものはこっちに移動しました。新しい文章が書け次第、削除する予定。 コンビネータでVM実装:old 尚、内容の正しさは全く保証できません。 「○○は△△です」と言い切りの形で書いてあっても、鵜呑みにしない方が安全です。 概要ロードマップ 概要 あとで。 ロードマップ 仮のロードマップ。おそらく、あとで変更しまくる。 コンビネータ等の、前提知識の説明や説明サイト/ページへのリンク 簡単な概要説明 事前にschemeで定義用の手続きやマクロを用意する プリミティブな要素から順に実装していく SとK その他の基礎コンビネータ unlambdaの「v」もここで実装 ブール値 cons cellと空リスト 数値(チャーチ数ではなく、ものまね鳥に出てき
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ネタ記録庫/不動点コンビネータ - ocaml-nagoya
k16's note