An introduction to TermiteNOTE: This post was written by Marc Feeley, the author of Gambit-C , following yesterday's MSLUG meeting where I gave a short introduction...
Javascriptで継続渡し - ヒビノキロク
id:nozom:20060317#1142577630の続き。世界で最も誤解された言語とも呼ばれるJavascriptを使って継続渡しを書いてみた。 なお、Javascriptの処理系としてRhino*1を使った。参考文献は『入門Javascript』(ISBN:4756138713)。 function fib(n) { if ((n == 1) || (n == 2)) return 1; else return fib(n - 1) + fib(n - 2); } function fib_cps(n, k) { if ((n == 1) || (n == 2)) return k(1); else return fib_cps(n - 1, function(v1) { return fib_cps(n - 2, function(v2) { return k(v1 + v2);
継続渡しとコンパイル - ヒビノキロク
実装はまだ先だが、継続渡しに変換してからコンパイルする方法がなんとなく分かった。 継続渡しへの変換 継続渡しへの変換は、簡単な例で示すと以下のようになる。 次の式を評価するためには、まず(g)を評価して、その戻り値を使って(f # x)を評価する。 (f (g) x)つまり以下の式と等価。 ((lambda (v) (f v x)) (g))ここで関数gの引数を一つ増やして、１引数の関数kを取れるようにしたg_cpsを考える。この関数g_cpsは、本来のgの計算を行った後で、戻り値を返す代わりに渡された関数を呼び出す（呼ばれた関数から戻ってこないので、呼び出すというよりジャンプすると言った方が正しい）。 (g_cps (lambda (v) (f v x)))このときの増えた引数が継続。 (擬似)バイトコードへのコンパイル 具体例で考える。 (define (fact n) (if (>
継続渡しとコンパイル(2)〜末尾再帰の場合 - ヒビノキロク
前のエントリでループの度にヒープにクロージャを生成しているのが無駄だと思う人がいるかもしれないが、それは例に挙げた関数が末尾再帰になっていないからだ。継続渡しは末尾再帰の時に最も真価を発揮する。 というわけで階乗計算の末尾再帰版。 (define (fact_tailrec n) (define (fact-aux n r) (if (> n 1) (fact-aux (1- n) (* n r)) r)) (fact-aux n 1))これを継続渡しスタイルにしたものがこれ。 (define (fact_tailrec_cps n k) (define (fact-aux n r k) (if (> n 1) (fact-aux (1- n) (* n r) k) (k r))) (fact-aux n 1 k))さらにこれを前のエントリと同様の規則で変換すると、 fact_tailre
末尾再帰と継続（メモ） - ヒビノキロク
レキシカルスコープと継続ができたので、あとSchemeに必要なものとしては末尾再帰の最適化がある。せっかくだからこれも実装したい。 どうやって実装すればいいか。最初はインタプリタではなくコンパイラを作らないといけないと思ったが、ひょっとすると継続を使えば自然に実装できるかもしれない。今は継続をバカ正直に毎回生成しているが、等しい継続(同じクラスで参照しているオブジェクトも同じ)は、振る舞いも同じはずなので、既に同値の継続オブジェクトが存在していたらそれを使うようにすると、繰り返しだろうが再帰だろうが有限の継続だけで済んでしまうような気がする。 ただ、もしそうなるとちょっとした問題があって、オブジェクトが循環参照するようになるので、最早オブジェクトの寿命をガベージコレクタに任せきりにはできないかもしれないということ。Javaのガベージコレクタってそこまで賢くなかったよなあ。となると自分で何と
続・継続 - ヒビノキロク
昨日の時点ではまだバグがあったが、そのバグも直った。たぶんこれで完成したと思う。最終的にはスタックですらなく、単に現在の継続を覚えておくだけで良くなった。これは継続自身に次に処理を渡すべき継続の参照を持たせることにしたためで、こうしないと継続を再利用した時に問題が出る。 昨日は結果しか書かなかったので、継続について少し解説を。 > (+ (call/cc (lambda (x) (x 1) 2)) 3) ==> 4この例では、xにcall/ccの外側への継続が束縛されているので、xを呼ぶと(call/cc ...)全体がその引数と置き換わり、全体としては(+ 1 3)を計算することになる。いわゆる大域脱出の例。 別の例： (define cont #f) ==> #f (+ (call/cc (lambda (x) (set! cont x) 1)) 2) ==> 3 (cont 5) =
ヒビノキロク
理由は id:nozom:20090202 を見てください。 はてな市民制度について はてな市民とは によると はてなキーワードを編集するためにははてな市民でなければならない はてな市民になるためにははてなダイアリーかはてなグループ日記を30日以上利用しなければならない 最後の利用から30日以上利用がない場合一時的にはてな市民ではなくなる ということで、移転先のはてなグループの方はほぼ週１更新なのではてな市民になるまであと約６ヶ月もかかるが、さすがにそれは待っていられないのではてなダイアリーの方を更新してみるテスト。 たぶん今後も何回か同じことがあると思います。 ユーザーページへのGoogle Analyticsの設置についてのアンケートで反対したことがいつの間にか*1導入されていたため、本日をもってこの日記の使用を中止します。 他のサービスに移ることも考えたのですが、当面の間 g:noz
Concurrent Programming in Erlang :: FreeTechBooks.com
Concurrent Programming in Erlang Posted: Wed Mar 07, 2007 8:17 am by ndaru Concurrent Programming in Erlang Authors : J. Armstrong, R. Virding, C. Wikström, M. Williams ISBN : 0-13-508301-X Pages : 358 Publisher : Prentice Hall Publication Date : 1996 Book Summary: Erlang is a concurrent, functional programming language designed for programming large industrial real time systems. The langua
絵を描いて学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記 (はてなBlog)
「JavaScriptで学ぶ・プログラマのためのラムダ計算」は、1回では述べ切らなくて、一段落付いたところで区切りました。これはかえって良かったですね、ブックマークやトラックバックでフィードバックが得られたので。 そのフィードバックなどをかんがみて、「残り＝次回の話題」として予告した内容とは食い違ってしまうのだけど、今回は、文章では伝わりにくい（前回うまく伝わらなかったと思える）ラムダ計算の大事なツボを、なんとか表現してみようと思います。 ［このエントリーの内容はだいぶ前にほぼ出来上がっていたのだけど、ココに書いてある事情で、“お絵描き”がなかなか出来なかったのです。］ ※印刷のときはサイドバーが消えます。 内容： 知っていて損はない 計算は身体的に理解しよう ラムダ項のツリー表示：準備 ラムダ項のツリー表示：描く！ β変換に対応するツリーの描き換え もっとβ変換をやってみよう 計算現象を
檜山正幸のキマイラ飼育記 - JavaScriptで学ぶ・プログラマのためのラムダ計算
「JavaScriptによるテンプレート・モナド、すっげー簡単!」にて： 紙と鉛筆でラムダ計算を実行できることは必要だな、やっぱり。 なんて強調したので、ラムダ計算の入門、いってみよう。 [追記]練習問題集を追加しました。説明を読みながら、あるいは読んだ後で是非やってみてください。→「JavaScriptで学ぶ・プログラマのためのラムダ計算 問題集」[/追記] ※印刷のときはサイドバーが消えます。 内容： JavaScriptの関数リテラル ラムダ式ってなんだ ラムダ計算の体系と適用操作 ラムダ式の例をいくつか β変換 -- ラムダ計算のキモ！ β変換を何度か実行してみる 中間まとめ、まだ続きがあるよ JavaScriptの関数リテラル 最初に、JavaScriptに関する知識を確認しておきましょう。なお、JavaScriptの対話的実行環境については「もっともお手軽な対話的JavaScr
魔法言語 リリカル☆Lisp
About ★「魔法言語 リリカル☆Lisp」はノベルゲーム風のLispチュートリアルです。 "アリサ"や"すずか"達と楽しくLispを学べます。 全１２話構成で各話の最後には練習問題が用意されています。 Lisp処理系にはNScripter上で動作するLispインタプリタであるNScLisperを使用。 別の処理系をインストールする必要はありません！！ Lispとは ★CやC++、Java、BASIC、Perl、Ruby、PHP、Python、ML、Haskellなどと同じプログラミング言語の一つです。 マサチューセッツ工科大学のJohn McCarthy教授を中心とする研究グループによって開発され、1962年に発表されました。 LispとはList Processorの略で名前通りリストの処理を得意とします。 このことから人工知能の開発に多く用いられています。 NScLisperとは
Scheme:使いたい人のための継続入門
使いたい人のための継続入門継続渡し形式call/ccは普通の関数call-with系関数call-with-procedurecall-with-continuation-procedurecall-with-current-continuation評価順序と継続call/ccパズルお手元マルチスレッド部分継続reset/pcとcall/pc環境破壊と部分継続部分継続の使用法PRINT-AND-NEXT-REPL議論質問お手元マルチスレッドのサンプルプログラムについて 使いたい人のための継続入門 とりあえず殴り書き。 くどかったり冗長な文章になってたり、重複してたり、間違ってたり、 おおいなる勘違いをしてたり、恥をカいてたりするかもしれないけどご愛敬。 藁をもつかみたい気持ちで継続を使えるようになりたい人は読んでみてください。 ただし所詮は藁です。(ｗ 継続渡し形式 例によって階乗fa
はてなブログ | 無料ブログを作成しよう
無名の遺跡15 建物が解体された土地を訪れると、時々、塀やコンクリートの基礎などが撤去されずに放置されているのを見かける。 このような過去の痕跡が残されている空き地を、本ブログでは"無名の遺跡"と呼んでいる。 無名の遺跡が生み出される原因の多くは、解体や撤去費用を抑え…
Factor programming language
Why Factor The Factor programming language is a concatenative, stack-based programming language with high-level features including dynamic types, extensible syntax, macros, and garbage collection. On a practical side, Factor has a full-featured library, supports many different platforms, and has been extensively documented. The implementation is fully compiled for performance, while still supporti
sumiiの日記 - call/ccが「副作用」である理由
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3acall%2fcc%e3%81%a8%e5%89%af%e4%bd%9c%e7%94%a8 (via http://d.hatena.ne.jp/flappphys/20061119#p2) おお、これは正確でわかりやすい議論ですね。call/ccが参照透明性を破壊する（ややトリッキーな）実例としては、前にちらっと書いた > (define x (call-with-current-continuation call-with-current-continuation)) > x #<system continuation> > (x 123) > x 123も、その筋ではよく知られているようです。元のcomp.lang.schemeの議論をちゃんと読んでいないので既出かもしれませ
Structure and Interpretation of Classical Mechanics
Looking for Scheme? The Scheme system, augmented with the Scmutils library, is free software. The system is provided, complete with documentation and source code, in a form that can be used with the GNU/Linux operating system, on the Internet at http://www-swiss.ai.mit.edu/~gjs/6946/linux-install.htm.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IBM Developer
azito.com
はてなブログ | 無料ブログを作成しよう
The Kawa language framework