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
おとうさん、ぼくにも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 となります。λの引数部分を与えられた引数で置
コンビネータメモ - ボクノス
メモメモ。 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 が素晴らし過ぎて話が終わってしま
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のチュートリアルを読んだ方がずっと、コンビネータ論理を理解
flatline's Wiki for memo - Y in Practical Programs
大抵，Yコンビネータには型推論はできない． でも例えばStandard MLの再帰関数を定義する機能を使えば楽々定義できる． fun Y f x = f (Y f) x fun fact_ fact x = (* この fact_ を "seed" と呼ぶ *) if x = 0 then 1 else x * fact (x-1) val fact = Y fact_ "Seed" にラッパをかぶせれば機能を楽に付加できる． fun printerWrapper f_ f x = let val result = f_ f x val _ = printInt result in result end val factPrint = Y (printerWrapper fact_) このfactPrintは再帰の途中経過を印字する． Haskellのように副作用をモナドで分離しなければな
不動点演算子ふたたび - sumiiの日記
（追記：Ｙコンビネータって何に使うの？） Yコンビネータ（Curryの不動点演算子）を説明するのがプチブーム（死語）らしいので、ふたたび挑戦。 まず、ふつーに再帰関数factをSchemeで定義してみる。 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))この定義は、右辺にfact自身が出現するので、再帰的定義なのであった。ここから右辺にfactが出現しないようにするのが目標。とりあえず、factを関数の引数として外から受け取るようにしてみる。 (define make-fact (lambda (my-fact) (lambda (n) (if (= n 0) 1 (* n (my-fact (- n 1)))))))これは( (make-fact fact) 10)みたく使えるが、make-factを呼び出す際に
Y Combinator - LoveRubyNet
$Id: ycombinator.html,v 1.6 2002/06/27 23:37:39 aamine Exp $ [ruby-list:35058] に刺激を受けて Y combinator を解読してみた。 こんなもん読むくらいなら以下の参考ページを読んだほうがいい。 参考にした (というかほとんどそのままな) ページ (英語) http://www.ececs.uc.edu/~franco/C511/html/Scheme/ycomb.html 動機 再帰関数は再帰するときに自分自身を名前で呼ぶのが普通である。 これをなんとかして名前を使わず、関数そのものを呼ぶように させたい。 求めかた まず単純な fact (階乗) を以下に示す。言語は Scheme である。 (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ネタ記録庫/不動点コンビネータ - ocaml-nagoya
Y-Combinator
http://www.city5.org/AlligatorEggs.html