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.
素数判定 - あどけない話
要約：素数判定に使われるミラーラビン法を解説しながら、Haskell で実装してみる。 フェルマーテスト 大きな数を確実に素数だと判定するには、大変時間がかかるので、実用的には「ほぼ素数だ」と確率的に判定する。確率的な素数判定の代表格がフェルマーテストである。 フェルマーテストには、以下に示すフェルマーの小定理を利用する。 a^p ≡ a (mod p) a は任意の整数。p は素数である。法 p の下で a を p 乗したものは、a と合同であると言う意味だ。a には制限はないが、特に a を p より小さい整数、0 ≦ a ≦ p - 1 とすれば、a を p 乗して、p で割ると a に戻るとも解釈できる。 最初に見たときは、だからどうしたと思われるかもしれない。しかし、有名なフェルマーの大定理が実用上何の役にも立たないのに対し、フェルマーの小定理はいろんな場面で活躍する。 実際に計
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
おとうさん、ぼくにも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 となります。λの引数部分を与えられた引数で置
MapReduceの本質 - 中しまのメモ
また一つ、『計算機プログラムの構造と解釈』から面白いネタが飛び出してきた。 計算機プログラムの構造と解釈 一見なんでもないようなschemeの例題から、GoogleのIndex生成アルゴリズムとして名高いMapReduceの概要を理解するための機会を得た。 あの例題の本質は何だったのか？ きっかけは、先日の「プロセスの抽象化（シーケンスへの作用）」というエントリーに関して、会社の先輩から興味深い指摘をいただいたことだった。エントリーの内容は、抽象化によって「木構造の要素に対して作用する手続き」を改善するという話だが、その改善前後の手続きをもう一度掲載する。 【A】改善前の実装 (define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0))
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
なんでも継続
Shiro Kawai まだ下書き Schemeの特徴をあげるときに、「継続」や「call/cc」が出て来ないことはない。 でも、R5RSのcall/ccの項をいくら読んでも、どうもよくわからない。 call/ccを使えばC言語のbreakみたいなのとか、コルーチンとかいう スレッドもどきとかが書ける、というのはわかったけど、一体そういうのが書けて 何が嬉しいのか、そこんとこがピンと来ないんだ。 今、そこにある継続 プログラミングの世界の概念には、禅の公案のようなものがある。 それを説明する文章はほんの一文なのに、最初に目にする時、 その文は全く意味をなさない、暗号のように感じられる。 だがひとたびその概念を理解すると、 その概念の説明は確かにその一文で説明されているのがわかるのだ。 そんな、「分かれば分かる」という禅問答の中でも 「継続」は最も謎めいたものの一つと言えるだろう。 文献を
色々な言語でライフゲーム
Squeak Perl Scheme Ruby Prolog 色々な言語でライフゲームを作ってみました。 ライフゲームについてはライフゲーム保存会 が詳しいです。また、The Game of Life ですばらしい Java アプレットを遊ぶ事が出来ます。 まず手始めに、Squeak で原型を作りました。Squeak は オブジェクト指向の元祖である Smalltalk の直系の子孫です。最近の言語はどれもオブジェクト指向の 影響を受けているので、まず Squeak で作ったら他にも移植しやすいだろうと思ったのです。 作りながら決めた仕様は以下のとおり。 盤のサイズは 20 x 20 最初ランダムなパターンが現れる 0.2秒に一度世代交代 50 回世代交代をしたらまたランダムなパターンを生成 盤のクラス名は LifeMap ただ、Squeak 版以外は手を抜いてコマンドライン実行です。全部
OBB vs AABB - Radium Software Development
This domain may be for sale!
Scheme演習
成績について Schemeの成績はレポートのみ(出席は取らない) レポートは完全にできていなくても提出できた分をそれなりに評価する 課題について 提出は hara2001-scheme ＠ ui.is.s.u-tokyo.ac.jp へメールで送ってください 送信されたE-mailに対して自動的に返信メールが送られます 添付ファイルではなくメール本文に直接貼ってください (ただしどうしても文字化けしてしまう人はテキストファイルを添付してください) Subjectは "Report (課題番号) 学生証番号" で送ってください 例: Report (1) 123456 課題の本文の先頭に Scheme演習 第1回レポート 理科I類2年 123456 須木 異夢 という形式で名前等を書いてください 締め切りは次のScheme演習の前日 授業で出題する前に課題を提出してもかまいません (質問も受
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
Redirect
青木日記/T(2003-03-15)
児玉研究室（法政大学経営学部）のホームページは移転しました。