Shozo TAKEOKA's page (JQ3KLL)
(一社)組込みシステム技術協会 (JASA)の 理事/技術本部本部長/OSS活用WG リーダを勤めています OSSコンソーシアムの 副会長と理事を勤めています。 ( Linuxコンソーシアムは、解散し、改めて、OSSコンソーシアムとして発足しました。) PCクラスタ コンソーシアムの 理事を勤めています DEOS協会の 理事/事務局長を勤めています BSD Researchの 理事を勤めています ( NPO法人 日本エンベデッド・リナックス・コンソーシアム (Emblix)の 理事と事務局長を勤めていましたが、解散。資産は、JASA OSS活用委員会で生かしています。) 表紙モデルもやった ・ facebook: takeoka ・ twitter ID: @takeoka ・ メモを記したBlog(アメブロ) ・ 公開ブックマーク(hatena) オレの特許(豊田通商/ネクスティ社とOS
schemeで矢印let - val it : α → α = fun
ふと LispUser.net のむかしの記事を見ていたところ、S式の限界と題して、 let と cond の記法拡張の話があった。端的に言うと、矢印が使えるようになるというもの。 で、最初に見たときは「あーまあそうだよね」という感じであり、まあサンプルとしては良いな、と思っていたわけだ。でまあそれだけだったんだけど、なんというか、わりと最近になってようやく自分でも define-syntax / syntax-rules で書くのに抵抗がなくなったというか、「こうすればできるじゃん」のイメージが掴めるようになったので、例題がてらにちょっとやってみた。 いい機会なので、 pyvnc2swf で撮影したムービーも公開します。というか、ムービー作成をちょっとやってみたかった、というのもある(笑)。 矢印let矢印cond 裏をあかすと矢印letの方はやってみたらすぐ出来てしまい、それは撮影して
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
魔法言語 リリカル☆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 建物が解体された土地を訪れると、時々、塀やコンクリートの基礎などが撤去されずに放置されているのを見かける。 このような過去の痕跡が残されている空き地を、本ブログでは"無名の遺跡"と呼んでいる。 無名の遺跡が生み出される原因の多くは、解体や撤去費用を抑え…
CodeZine：JavaScriptでつくるSchemeインタプリタの基礎の基礎（lisp）
はじめに 現存するプログラミング言語の中で2番目に古いのがLispです。生まれは古くても、いまだに使われ続け、また、Rubyなどの新しい言語にも影響を与えています。そのLispの派生であり、シンプルさが売りなのがSchemeです。 ここではSchemeの簡単なインタプリタをJavaScriptで作ってみます。対象読者 本稿はLispやSchemeは少し触ったことはあるけど、インタプリタは書いたことがないという方を読者対象としています。また、JavaScriptの文法や、簡単なデータ構造についての知識を前提とし、説明は省きます。必要な環境 テキストエディタと、JavaScriptが動くWebブラウザがあれば十分です。他に特に用意するものはありません。概要作成するインタプリタについて インタプリタのコードはJavaScriptで書き、HTMLのフォームを使って、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.
Super Technique 講座〜再帰関数の技
Ｃ言語初心者が戸惑うものとして、「再帰」に関する技法がある。まあ、今時の言語で「再帰関数」を書けないのは、COBOL と FORTRAN, 古典的BASIC くらいのものだが、一般的な言語解説書での説明は大変おざなりなものである。だから、これは意識して憶えないことには、やはり身に着かない。 そこで「Super Technique 講座」では、再帰の技法を、再帰という発想の親玉である Lisp(Scheme) を利用して理解する、という無謀な企てをしてみることにする。「ある言語を理解するのに、何で別な言語を勉強するの？」という当然の疑問が湧くことだろう。しかし、しかし、「それがハッカーというものである」。筆者は MS-DOS の時代に、UNIXのテキストツールの使い方を理解するために、それらを自分で実装した。一見「無駄」に見える技術投資は、ことプログラマにとっては決して「無駄」ではない。Li
Practical Scheme
Shiro Kawai 7/3/2000初出、3/29/2002更新 まあとりあえずカッコは我慢しよう。ラムダとやらも、関数ポインタ＋環境データ ということで納得しよう。しかし、Schemeのループ構文(do)は許せないなあ。 ごちゃごちゃしてるし、途中で脱出できないし。 CやPerlのforやwhileの方がずっと使いやすいね。 え? doなんて使わない? じゃあどうやってループを書くんだ? 消えるループ 簡単だけど、よくありそうな例として、こんなのを考えてみよう。 入力テキストの行数を数える関数count_linesを書きたい。 Cで書くとすれば、こんな感じだ。 /* 例1 */ int count_lines(void) { int count = 0, c; for (c=getchar(); c!=EOF; c=getchar()) { if (c == '\n') count+
Practical Scheme
Shiro Kawai 11/20/2000初出、3/29/2002更新 Cに慣れたプログラマがSchemeのコードを見て面食らうことのひとつは、 無名の関数やローカル関数の多用だろう。 特に実行効率に敏感なプログラマにとっては「関数呼出しは高価」 という感覚が染み着いているため、 至るところに散りばめられたlambdaに眉をひそめてしまうようだ。 しかしSchemeにおいては、 コード上に関数が書いてあるからといって 実行時にスタックフレームの生成やレジスタの退避などのオーバヘッドが起こるとは限らない。 例えば関数の最後に別の関数を呼び出す末尾呼び出し(tail call) はただのjumpインストラクションに置き換え可能だ。 ここでは、Cプログラマを対象に、 lambdaで生成される関数群が実際にどのように実行され得るのかを書いてみたい。 (なお、Schemeの規格ではlambdaフォ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://oss.timedia.co.jp/show/column/%BA%A3%C6%FC%A4%CE%B0%EC%B9%D4/%A3%B2%A3%B0%A3%B0%A3%B5%C7%AF%A3%B1%A3%B2%B7%EE
An introduction to Termite
The Kawa language framework
Ｐ２Ｐな自作ソフトとＬＩＳＰ言語 メインページ
