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.
Lambda Gate -- various LISPs
λ門 Updated $Date: 2008/01/19 08:38:39 $ 様々な LISP LISPs in research TUPLE (Toyohashi University Parallel Lisp Environment) は、 Common Lisp に超並列計算機の機能を付加したもの とのことです。 NUE (New Unified Environment) の TAO は、LISP 専用機 ELIS の核言語です。 Thomas Mahler 氏の pLISPは an experimental Implementation of parallel functional Programming. It is based on massive parallel graph-reduction machine だとのことです。 Gregory J. Chaitin 氏は
「クロージャの定義」 - hidemonのブログ
Java7のクロージャの提案者の一人，Neal Gafterのブログが大変参考になるので，ちょっと野良翻訳してみよう． クロージャの定義 Java 言語にクロージャを追加しようという我々の提案に関して混乱があるようだ．そもそも，Javaにはすでに無名インナークラスという形で，クロージャがあるのではないか? すでにあるものをなぜまた追加しようというのか? 一部の人々には，我々の提案には，クロージャとは関係ないものが含まれているように思われているようだ．例えば，control invocation 構文，null型，Unreachable, 型パラメータ付きthrows，関数インターフェイス型，「非ローカル」な returnなどがそうだ．Javapolisでの講演で，なぜこれらの機能が提案に含まれているのかを，これまで不可能だったことを可能にするための実用的な観点から説明したつもりだ．しかし，
2008-02-01
id:poco_ryun の似顔絵を想像しながら書いてみた。 節子それ似顔絵やない、ただの妄想や。 ポイント 大きくてクリクリした目 長いまつげ マスカラでおめかし アイラインのなんとか セクシーな唇 どうですか > テスト期間だし、なんか作っとかないとね。 ということで、最近話題のYコンビネータとかそこらへんの話に絡めて、ラムダ計算のインタプリタ作ってYコンビネータ動かそうぜ、っていう。前に書いたラムダ計算インタプリタは、データの形式を入力形式そのままで引き回していたので、割とカオスなことになったので、今回はパーサ、構文木、など適当に部品化してみた。 記法 λxyz. xz(yz) <==> '(λ (x y z) x z (y z)) Gaucheは全角文字がシンボルとして使えるのでスバラシイですね！ β簡約 Pでラムダ式をパースして、BBでいけるところまでベータ簡約しつづける（発散す
2008-02-01
Haskell のリストはシンタックスシュガーだらけ a = [] b = [1] c = [1,2] d = [1..10] e = [1..] f = [1,3..] g = [ x * x | x <- f ] 逆に分かりにくいので書き直す a = [] b = (:) 1 [] c = (:) 1 ((:) 2 []) d = ff 10 where ff 0 = [] ff i = (:) 1 (map (+1) (ff ((-) i 1))) e = (:) 1 (map (+1) e) f = (:) 1 (map ((+) ((-) 3 1) f) g = map (\x->x*x) f うん、なるほど ついでに map と同じ事をする関数 mymap を作ってみる mymap f [] = [] mymap f ((:) x xs) = (:) (f x) (mymap
Schemeでラムダ計算
Schemeとか関数型言語を使う人は、ラムダ計算が好きだったりする。 実際にラムダ計算をするのは別に好きではないと思うけど。 日本にも、 ラムダ算法騎士団の 総本山 があったりする。 Schemeのlambdaでも実際のlambda計算みたいな事ができる。 ; *** car、cdr、cons *** ; car、cdr、consが、lambdaだけで書ける事は、わりと有名。 ; (car、cdr、consが書けるというのは、 ; (eq? x (car (cons x y))) ; (eq? y (cdr (cons x y))) ; が成立するという事。) ; 次のようになる。 (define _cons (lambda (x y) (lambda (z) (z x y)))) (define _car (lambda (z) (z (lambda (x y) x)))) (defin
不動点オペレータについて
不動点オペレータ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))
Practical Scheme
Shiro Kawai 11/20/2000初出、3/29/2002更新 Cに慣れたプログラマがSchemeのコードを見て面食らうことのひとつは、 無名の関数やローカル関数の多用だろう。 特に実行効率に敏感なプログラマにとっては「関数呼出しは高価」 という感覚が染み着いているため、 至るところに散りばめられたlambdaに眉をひそめてしまうようだ。 しかしSchemeにおいては、 コード上に関数が書いてあるからといって 実行時にスタックフレームの生成やレジスタの退避などのオーバヘッドが起こるとは限らない。 例えば関数の最後に別の関数を呼び出す末尾呼び出し(tail call) はただのjumpインストラクションに置き換え可能だ。 ここでは、Cプログラマを対象に、 lambdaで生成される関数群が実際にどのように実行され得るのかを書いてみたい。 (なお、Schemeの規格ではlambdaフォ
Life with Cygwin
沖ソフトウェア株式会社は、沖通信システム株式会社および株式会社沖インフォテックと平成22年10月1日をもって合併いたしました。新会社名は、株式会社OKIソフトウェアとなります。3社が行っております事業は新会社にて従来通り継続いたします。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ラムダ算法
Lua/組み込み - assari
http://kaiunix.cs.shinshu-u.ac.jp/Lesson/ProgLangT/2007/LambdaCaluculus.html
Y-Combinator
The Kawa language framework