cut-sea:log

cut-sea:log

cut-seaより移動(2004/12/25 20:13:58 PST)


あ、ようやく出た。 今週末の楽しみがでけたわい。cut-sea:2004/12/09 22:10:47 PST

The system is now fully dynamically linked (including /bin and /sbin). 
                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~
System recovery tools are provided in /rescue. These are space-optimized 
statically linked versions of various tools required to repair a system 
(including /rescue/init and /rescue/sh). 

うーん、この辺がなんか気になる。


memoize

こんなんもありかなぁ。 (define foo ... で定義しておいて、あとからメモ化したいなぁって関数だけ memoize-define に差し替えるとか。cut-sea:2004/12/02 03:49:57 PST

(define-syntax memoize-define
  (syntax-rules ()
    ((_ (fn . arg) body ...)
     (memoize-define fn (lambda arg body ...)))
    ((_ fn lambda-body)
     (define fn (let ((cache (make-hash-table 'equal?))
                      (rawfn lambda-body))
                  (lambda args
                    (if (hash-table-exists? cache args)
                        (hash-table-get cache args)
                        (let ((val (apply rawfn args)))
                          (hash-table-put! cache args val)
                          val))))))))

高速フィボナッチ

OSSの今日の一行 に出てた高速フィボナッチの計算を Gauche でやってみた。

(define (fib n)
  (if (< n 2) n
      (+ (fib (- n 1)) (fib (- n 2)))))

(define (fib-hi n)
  (define (fib-dash a b n)
    (case n
      ((0) a)
      ((1) b)
      (else (fib-dash b (+ a b) (- n 1)))))
  (fib-dash 0 1 n))

(define (fib-super n)
  (define (fib-dash a b p q c)
    (cond ((= c 0) b)
          ((even? c)
           (fib-dash a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ c 2)))
          (else
           (fib-dash (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- c 1)))))
  (fib-dash 1 0 0 1 n))

さて、ここで fib が最も低速なやつ、 fib-hi が高速なやつ、 fib-super が最高速のやつなんだけど。。。 fib についてはメモワイズしたら高速になる。(fib 50) や (fib 100) くらい どってこと無くなる。 メモワイズは Scheme:OnLispのメモワイズ を use して使った。

gosh> (time (fib 35))
;(time (fib 35))
; real   6.889
; user   6.800
; sys    0.000
9227465
gosh> (define fib (memoize fib))
fib
gosh> (time (fib 35))
;(time (fib 35))
; real   0.000
; user   0.000
; sys    0.000
9227465
gosh> (time (fib 1000))
;(time (fib 1000))
; real   0.022
; user   0.030
; sys    0.000
43466...

さて、 fib-hi や fib-super についても memoize をかまして超高速にしたいが、 単に fib-hi/fib-super に memoize しても無駄だろう。 一番最初に通過するだけだから。だけど、

(define (fib-hi n)
  (define (fib-dash a b n)
    (case n
      ((0) a)
      ((1) b)
      (else (fib-dash b (+ a b) (- n 1)))))
  (define fib-dash (memoize fib-dash))
  (fib-dash 0 1 n))

としてもダメ。内部 define の評価順て保証されない。

gosh> (fib-hi 100)
*** ERROR: invalid application: (#<undef> 0 1 100)
Stack Trace:
_______________________________________
  0  (apply fn args)
        At line 29 of "/home/cut-sea/lib/Gauche/onlisp.scm"

こんな感じになって #<undef> になってる。 じゃあ、というわけで。

(define (fib-hi n)
  (define (fib-dash a b n)
    (case n
      ((0) a)
      ((1) b)
      (else (fib-dash b (+ a b) (- n 1)))))
  (let ((fib-dash (memoize fib-dash)))
    (fib-dash 0 1 n)))

こうやって fib-dash の内部定義が見えるようにしてやると、 動作はするが高速になってない気がする。 いやむしろ遅くなった。(fib-hi 100000) が 5-6sec のものが 8sec 位まで。 let で環境積み上げたりしちゃったからか?
気乗りはしなかったが、とりあえず高速になるかどうか確認したかったので

(define (fib-dash a b n)
  (case n
    ((0) a)
    ((1) b)
    (else (fib-dash b (+ a b) (- n 1)))))
(define fib-dash (memoize fib-dash))
(define (fib-hi n)
  (fib-dash 0 1 n))

と苦し紛れにこうやると。

gosh> (time (fib-hi 100000))
GC Warning: Out of Memory!  Returning NIL!
out of memory (3924).  aborting...

Process scheme exited abnormally with code 1

念のため、もっかい確認。

gosh> (time (fib-dash 0 1 100000))
GC Warning: Out of Memory!  Returning NIL!
out of memory (4040).  aborting...

Process scheme exited abnormally with code 1

がぁん!返り打ち!

落ち着いて 10000 位で再計測すると 0.9sec が 1.5 位まで落ちてた。 もちろん、二回目回からはほぼ 0sec になるんだけど。 つまりメモワイズの効果は一発勝負だと fib-hi や fib-super による アルゴリズムの方が勝ってるってことかな。 勘だけどメモワイズって引数のパターンで答えを記憶するから fib-hi や fib-super みたいに引数が多くて色んなパターンを通過するほど cache されたデータが再利用されてなくてメモにばっか負荷かかってんのかなぁ。cut-sea:2004/11/28 16:50:49 PST


今ごろ気付いたのでした

出張で東京に行って来まして、帰りにちょいと秋葉に寄りました。

本屋でサイエンス社の「初めての人のためのXウィンドウシステム入門」を入手。 古本かと見紛うばかりに汚かったけど、分かりやすそうだったので。 で、確かに分かりやすかったです。一気に飲み干しました。 さらに「OpenGLプログラミングガイド」いわゆる赤本(?)もゲット。

そこで、ふと思い返して LL Weekend で久井さんがやった 三次元図形言語のLT を走らせた。 そこで、またまた自分の愚鈍な側面が露出しました。

あー!三倍速いこの赤いヤツは!!遅い方の緑のヤツは!!!
第一次ガン○ム世代失格でした。切腹。

会場爆笑だったのに、5ヵ月遅れとは・・・cut-sea:2004/11/26 05:41:33 PST

On Lisp

野田さんの邦訳をちょろちょろ読み始めてます。 これ制覇したら立派な魔法(マクロ)使いになれるかしらん。

てなわけでちょいやらせてもらいます。 -> Scheme:OnLisp


本屋でぷらぷらしてたらマイコン関係の書棚のところで見付けました。その名も

「ハードウェアハッキング大作戦」 オライリー・ジャパン ISBN4-87311-211-7

興味が惹かれて衝動買い。 寒くなって来たし(?)、半田鏝使いたくなって来た。 帰ってから google で探ったら、何のことは無いわ。 しばらく前に /.J でも話題になってたらしい。cut-sea:2004/10/30 03:02:37 PDT


使いこなせる様になりたいものの最右翼

ここ見てる人は大抵知ってると思うけど、 野田さんのサイトで以前から on Lisp の邦訳が公開されてる。 最近再び活発に進みはじめた模様で全 25 章の内、 24 章まで来たらしい。
もう少ししたら完了しますね。 私はってーと、読むだけのくせに遅々として進まない。

未だ自信の無いものにオブジェクトシステム、モジュールシステムそしてマクロが あるんだけど、その内、マクロはやっぱり特別。 どんなに Lisp だの Scheme だのを語ったところで、 マクロを使いこなせる自信が無いってのが弱いトコです。

しかしポール・グレアムの文章ってすごいその気にさせるよなぁ。cut-sea:2004/09/30 06:17:05 PDT


cal 1752

…………知らなんだ(もろお国言葉)
cut-sea:2004/09/06 16:08:00 PDT


引数の評価順の問題か?

Gauche:CGI:MiniWiKiを書いててふと気になったのが、

(define (block-tree in)
  (let loop ((tree '())
             (line (read-line in)))
    (if (eof-object? line)
        (html:blockquote (reverse tree))
        (cond ((#/^>>>$/ line) (html:blockquote (reverse tree)))
              ((#/^<<<$/ line) (loop (cons (block-tree in) tree)
                                     (read-line in)))
              ((#/^{{{$/ line) (loop (cons (pre-tree in) tree)
                                     (read-line in)))
              (else (loop (cons (line->html line) tree)
                          (read-line in)))))))

例えばこのコードの名前付letの引数の順序だ。 (loop ... ...) の引数のうち、第二引数はもろに read-line を含んでいるけど、 第一引数に含まれる block-tree も内部で read-line するので 順序としては左から評価ってのを仮定して組んでいる(ことになりますよね)。
let も所詮 ((lambda (tree line) ...) (cons ...) (read-line in)) の 構文糖衣だから、処理系によっては第二引数から評価ってのもありえると思う。
こういう場合って処理系依存をなくそうとしたら、どんな方法が考えられるだろう?

私が今思ったのはlet*なら引数は最初のものから一個ずつ環境を積み重ねるから 左から評価ってのを処理系依存なく前提にできそう。(に考えた)
でもlet*はそういうものだから、以前r5rsとにらめっこしながら、 そもそも名前付let*にはできなそうな気がした。cut-sea:2004/09/05 19:47:50 PDT


CGIのお勉強2

Gauche:CGI:スケジュール予定表:Shiro版を見て、 いろいろ勉強になるところがあった。 まぁces-convertとかいまだに単なる模倣でやっているところがあるけど、 ちっちゃなwikiを作ってみました。2004/09/03 07:11:46 PDT

こっちね->Gauche:CGI:MiniWiKi


1/1スコープドック

かっこいい! 尊敬しちゃう。「なんでも作るよ」というこのノリがいい感じ。
何がかっこいいかというと、 チンクタンクにせよ、 デスクトップマシンにせよ 頭ん中で一瞬は考える事はあっても、作るという行動を起こさないだろう ということをいとも簡単に(そう見えるんだが)やっちゃうところ。 しかもチカラワザ。
見習いたい。プログラムでもそう。 考えてもなかなか歯が立たなかったり、 ボスキャラレベルと思ったら戦わずにすぐ逃げる私とは正反対だ。

CGIのお勉強

LL Weekend で刺激を受けた。 やっぱり web アプリ書けるとデキルって感じがする。
でも CGI とかそもそも http とかどうやって動いてんのかすら知らない。 というわけで巣に戻ってから勉強始めました。

とりあえず、LL Weekend での最後の御題のスケジュール予定表ができました。 けど、制限時間4時間どころの騒ぎじゃなかったです。 一応完動を確認したが、さすがの私も今すぐはアップするのにためらわれる程 コードがごちゃごちゃしてます。 土日でリファクタリングできて、普段程度の汚さに昇格したらあげさせてもらおうと。 でも (use www.cgi) しておきながらまともに使ってないです。 text.html-lite と text.tree でほとんど生成してて どの辺がどう違って来るのかがよく理解できてません。 ちなみに現時点で 226 行あって長いです。 <date>型を使いこなせず、自前で色々カレンダー計算のためのコードも用意したし。cut-sea:2004/08/27 10:05:18 PDT

こっちへ->Gauche:CGI:スケジュール予定表
さらここが参考になりそう->URLエンコード
やっぱり日本語訳に逃げる私->RFC2616日本語訳 URIのエスケープ・解除->RFC2396日本語訳


先日久々にUNIX MAGAZINEを手に取った。
Cにおけるメモリ管理関係の記事が出ており、ちょいと立ち読みさせてもらった。

最近の Solaris には pmap とかいうプロセスのメモリマップを 表示してくれるツールがあるらしい。なんか便利そう。
実はこういったの見れるといーなーとか思ってた。

記事は pmap とか ps を使ってCでmallocしたり、auto/staticなどで定義した 変数のアドレスを表示させてメモリマップのここだよんとかって示してる だけなんだけど、こういう記事って好きだな。
そういうのって多分みんなも一度はやったことあるんだと思うけど、 pmap で生きてるプロセスのメモリマップを見れるってのが面白かった。 ^Dを入力したらmallocして、もっかい^D入れたらfree、さらに同じサイズを mallocしたり大きいサイズをmallocするってのを対話的にやりながら、 一方で pmap でheapが増加する様を見せて解説してあるの。cut-sea:2004/08/22 19:43:52 PDT


anaphoric macro

LL Weekend から直接帰省してきました。
休み中のお供は on Lisp の日本語訳。

anaphoric macro を見てほほうと感心。 忘れかけてたけど、今日ふと思い出して書いてみた。

(define-macro (aif test . args)
  (cond ((null? args) `(let ((it ,test))
                         (if it it #f)))
        ((= (length args) 1) `(let ((it ,test))
                                (if it ,(car args) #f)))
        ((= (length args) 2) `(let ((it ,test))
                                (if it ,(car args) ,(cadr args))))
        (else (error "extra arguments exist. -- AIF --"))))

(define-macro (aand test . args)
  (cond ((null? args) `(aif ,test))
        (else `(aif ,test
                    (aand ,@args)))))

gosh> (aif (sys-getenv "HOME") (string-append "HOME = " it))
"HOME = /home/cut-sea"
gosh> (aand (sys-getenv "HOME") (string-append "HOME = " it) (string-append "MY " it))
"MY HOME = /home/cut-sea"

けど、最初は hygienic macro っていうのかな、 syntax-rules を使ってやろうと思ったのです。 ところが it が保護されてしまうっていうかマクロのユーザの視野から見えないっす。 んで、やっぱり苦し紛れに define-macro を使ったのです。くやしい。 どうやれば良かったんでしょう?cut-sea:2004/08/16 04:20:18 PDT


websteal

websteal 作ってみました。 まだ全然不完全ですが一応 SICP の本家からは問題なく引っ張れます。cut-sea:2004/07/25 04:52:32 PDT


gauche で XML

昨日大した作業じゃない(と思った)のにやり方が分からず 作業を細切れにして sed/awk/scheme でリレーしながら、 最後は力技で押し切ってすませたんだけど。 あるんじゃねーかなーと思ってた。。。

http://namazu.org/~satoru/diary/20040325.html

ふむ、こりゃ便利そう。cut-sea:2004/07/22 20:18:02 PDT

使ってみたら結構エラーばっかでちゃいますね。ムツカシイ(^^;
とりあえず、 http://mitpress.mit.edu/sicp/full-text/book/book.html に対して ssax:xml->sxmlを掛けてやると、以下4点book.htmlを修正しないと ちゃんとtreeを構築してくれない。

  1. &nbsp; が含まれているとダメ
  2. <meta ...> に対して terminate </meta> が必要になるみたい
  3. <link ...> に対して terminate </link> が必要になるみたい
  4. <img ...> に対して terminate </img> が必要になるみたい

しかし2番目以降の非終端についてはなんでじゃろ?
share/gauche/0.8/lib/sxml/tools.scm には

(define (sxml:non-terminated-html-tag? tag) (memq tag '(area base basefont br col frame hr img input
 isindex link meta param)))

ってのがあるのでいずれも非終端でもおっけーな中に入ってるような気がする。 どこがどうなってエラーが出るのだろう。

*** ERROR: "./book.html":line 5: (END . head) while expecting ENDmeta

Stack Trace:
_______________________________________
  0  (ssax:assert-token term-token 'END start-tag-head (lambda (token e ...
        [unknown location]
  1  (handle-start-tag (xml-token-head term-token) port entities namesp ...
        [unknown location]
  2  (handle-start-tag (xml-token-head term-token) port entities namesp ...
        [unknown location]
  3  (handle-start-tag (xml-token-head term-token) port entities namesp ...
        [unknown location]
  4  ((ssax:make-parser NEW-LEVEL-SEED (lambda (elem-gi attributes name ...
        At line 99 of "/usr/local/share/gauche/0.8/lib/sxml/ssax.scm"
  5  (proc port)
        At line 60 of "/usr/local/share/gauche/0.8/lib/gauche/with.scm"
  6  (call-with-input-file xml (lambda (in) (ssax:xml->sxml in '())))
        At line 19 of "././websteel.scm"

こんな感じです。ENDmetaを期待してるところで云々と言っておられる。
tools.scm はPDSなsxml-tools.scmのコードからgenerateされてるっぽいんだけど、 &nbsp;なんかもサポートしてなさげ。 (というか gt/lt/amp など数個しかサポートしてない様に見える)


sitcom

まるで余談だけどNHKとかで放映されるアメリカさんの シチュエーションコメディが好きだ。
学生時代にずいぶんハマったアルフなんかビデオにとったものだ。 東京の安アパートでゴーストでまくり状態に泣いたが、今でも残っている。 ふと思って google で検索かけたら こことか他にも仲間がいる。
ああ、そうだよね。

個人的にはここ数年の日本のお笑いってどうも下品なだけになって もちろん面白いんだけど癒されはしない。
小馬鹿にしたり、ハメたり、ひたすらふざけるだけなんじゃなくてさ。
笑い疲れるんじゃなくて、元気になれる様な癒しのあるユーモア ってやつが最近無性に欲しかったりするよ。cut-sea:2004/07/21 05:04:04 PDT


出力

いまさらですが。

  1. write
  2. display
  3. format
  4. print

どう使い分ける?


今日本屋にいって BSD Magazine No.20 を買って来た。 んで、NetBSD開発者へのインタビュー記事を見たら、 いきなり「NetBSDの開発言語を変える?」ってのがあった。
Cはやっぱり扱いやすいとは言えないからってことで、 Sampson氏がちょびっと語っているんだけど、 氏が考えるCに変わる第一候補はSchemeらしい。
C++,Javaはありえない。可能性として考えられるのはscheme。 質の良いコードを吐くものもあるからkernel部分の多くを移行できるんじゃないか。 ただ、あくまで現時点では夢の段階だけどねと。 ちょっとワクワクする話。cut-sea:2004/06/19 03:08:49 PDT


プログラミング言語 日本語。。。cut-sea:2004/06/01 07:15:15 PDT

昨夜上記のサイトを見てから、妙に思い出して気になってたんだけど、 ``//blackstar.benefit-online.co.jp/~saw/'' ってところに 2003/1/10 時点で「世界における宗教」ってタイトルの web page があった。 今はなくなってるみたいなんだけど、結構おもしろかったんだよね。
今手元には印刷したものがあるんだけど、言語を各宗教に見たてて解説しているの。 リスプ教ももちろんある。
アセンブラ教、フォートラン教、パスカル教、シー教、リスプ教、フォース教、 コボル教、モジュラ教、スモールトーク教、ベーシック教の解説。 さらにリスプ教とプロローグ教について別の補説みたいのもある。 いったいどこにいったんだろう。
著 W.E.Mec 訳 E.Minami ってなってる。


apply ショック

今ようやく apply の凄さを感じた。

Scheme:イラストロジックの中で転置行列っぽいもの を生成する transpose(旧trans-row-col)ってのがあるんだけど、 「関数プログラミング」を読んでたら zip ってのがある。

ん〜?コレっていかにもありそうじゃん? そう思って調べると srfi-1 に含まれるのを知った。
ただ transpose とは引数の取り方が違うんだけどね。

じゃあさ、 zip はどう実装されてんの?とみたら

(define (zip list1 . more-list) (apply map list list1 more-list))

これだけなんだよね。少しショッキングだった。 私は apply をちゃんと理解してなかったよ。これって凄い!
結構他にも再帰的にコード組んでるものが同様に apply 一発で できるかも知れないゾと興奮気味。

apply の最後の引数が正規のリストじゃないとだめだよって 仕様に詠ってるわけだけど、これまで私は単なる制約としか思ってなかった。 しかも「最後だけかよっ、なんかいびつ〜」とか思っちゃってました。 (すんません)違うよ、コレッ!

うまく言えないけど map と併用すると再帰的なロジックを簡単に組めるんだ。
rest 引数の扱いが簡単になってることと、 そのまま map に渡せるってのが強力な表現力を生んでるんだ。 なんか嬉しくなって泣けて来た。cut-sea:2004/05/08 20:50:57 PDT


昨日から東京へ遊びにいってきた。 今回はテロとかありそうとか思って、ちょい気にしてたんだけど無事かえってきた。

本屋さんをぷらぷらしていたら 「Lightweight Language MAGAZINE」てのがあるのを発見した。 先日 ML とかでも今年もやるよ〜と告知のあったやつで、 昨年のネタで MOOK になったもののようだ。
おれたちだってLLだ!の中にやましたさんの Haskell の記事もある。
あと、アンケートにて使える言語のところに scheme(Gauche) を発見。

「お題プログラム」なんて企画があったんですね。 土日の予定らしいし今年は行ってみようかな。


MIT Schemeの top page のロゴ にあるこの式って何なんだろう。

  (Y F) = (F (Y F))

英語で解説しているサイト
日本語で解説しているサイト

コンビネータ

自由変数を含まないλ項

ということらしい。 上記サイトでも再帰関数を書くのに「自分自身を呼ぶために 自分自身の名前という自由変数を使わないで書く」ということを 目指すというアプローチで解説している(みたいだ)。
私も無名関数を使ってても再帰な関数の場合には"あ〜無理っ"と思って諦めて 名前付けて書くわけだけど、やっぱりとことん考える人はいるんだなぁ。
でもはっきし言って今の私には難解。
しかも相互再帰のコンビネータなんてのも考える方々がいるやらいないやら、、、 なぜにそう難解なコードをかけちゃうのかまったくもって不思議。cut-sea:2004/04/12 22:02:41 PDT


wiliki で css ファイルが

実は前からよく分からなかったんですが、教えてやってください。
wilikiで wiliki-sample.css を stylesheet として使いたいのですが、 wiliki.cgi をアクセスすると httpd のエラーログに

[Sat Apr  3 15:34:43 2004] [error] [client 127.0.0.1] file permissions deny server execution: ?
/usr/pkg/libexec/cgi-bin/wiliki-sample.css

こんな感じのエラーがでちゃいます。(一行が長いので改行入れてます) apache 1.3.29 を使用してるんですけど、 wiliki-sample.css 自体は wiliki.cgi と同じ cgi-bin ディレクトリに入れてて 上記エラーを吐くものの wiliki は使えてます。
しかしスタイルは真っ白で実にタンパクなページになり、とてもさみしい。 yahoo にて httpd & permission deny & css とかで探すと、 別の wiki サイト関係で似たようなエラーが出たって報告があったんですが、 解決したっていうような内容は見あたらず。

apache のML検索したら、 cgi-bin の下は cgi だと思って実行しようとするので css を別ディレクトリにおいてねという様な回答がありました。
ところが困ったことに wiliki.cgi の style-sheet は path 指定しても cgi-bin の下のディレクトリと見なしてアクセスするみたいで ファイルが存在しないよって叱られちゃいます。 どうしたもんなんでしょう。2004/04/03 00:31:53 PST

↓がブラウザで見たときのページソースです。
HTML中のスタイルファイルの指定ってこれですよね?

><base href="http://jini/cgi-bin/wiliki.cgi" /><link rel="stylesheet" 
href="/home/cut-sea/data/css/wiliki2.css" type="text/css" /></head

なお、 wiliki.cgi はこうなってます。

(define (main args)
  (wiliki-main
   (make <wiliki>
     :db-path "/home/cut-sea/data/wikidir"
     :log-file "wiki.log"
     :top-page "Silk"
     :title "Silk"
     :description "cut-sea's Wiliki Site"
     :style-sheet "/home/cut-sea/data/css/wiliki2.css"  ;;; こんな風にしてみた。
     :language 'jp
     :charsets '((jp . euc-jp) (en . euc-jp))
     :db-type <ndbm>
     :debug-level 0
     )))

error_log が

[Sat Apr  3 17:45:03 2004] [error] [client 127.0.0.1] File does not exist: ?
/usr/pkg/share/httpd/htdocs/home/cut-sea/data/css/wiliki2.css

で、アクセス先が変になってしまう。(cgi-bin の下でもなかったですね。すみません。) かといって css ファイルは cgi-bin の下にも置けないみたいだし。

  1. :style-sheet "wiliki2.css" なら httpd はファイルを探せるが cgi-bin の下なのでエラーを発生させる。
  2. :style-sheet "/home.../wiliki2.css" なら 生成されるページの style-sheet のパスと httpd の探すパスが一致しない。
cut-sea@jini> diff httpd.conf httpd.conf.org 
274c274
< ServerAdmin cut-sea@master.email.ne.jp
---
> ServerAdmin you@your.address
292c292
< ServerName jini
---
> #ServerName www.example.com

だけしかいじってませんでした。2004/04/03 01:52:34 PST

やさしい Lisp 入門

ISBN4-87783-102-9

本屋にいったら「やさしい Lisp 入門」て本が出てたのを発見。 Lisp/scheme 関係って本が異常に少ないのでなんでもいいから 買ってしまえってわけで読みもせずに購入した。
なんか500p弱あるんだけど、その割に内容が極めて希薄な感じ。

二色刷りで、なんかメジャーな言語にありがちな やさしいシリーズとかよくわかるシリーズの様なイデタチ。


一般化参照

Lisp でいうところの setf 。
強力なのはいうまでもない。なんせそういう思考を使うことがよくあり、 そのまんま書けちゃうんだから。

強力とは 思考したまま書けることと 見つけたり

強力とは 思考したまま書けるように出来ちゃうことと 見つけたり

問題は scheme でも使いたいとなった時に、多分通常はマクロを使うんだろうけど その実装は処理系によっては結構めんどくさいかなってところ。

あんだけ便利なんだし、 これはあるだろうってことで調べたら SRFI-17 がそうらしい(一般化参照)。
gauche もサポートしてくれている。。。

on Lispを読んでて思ったのは、一般化参照は各scheme(Lisp処理系)が プリミティブに提供している各セレクタに対応するインバージョンなるものを マクロ定義中に全部飲み込んでやる必要がありそうだってこと。

つまり

 > (define x (list 1 2 3)
 x
 > (set! (car x) 29)
 #<undef>
 > x
 (29 2 3)

では汎変数の位置が (car x) だから set! 式全体が (set-car! x 29) になるように 変換する展開形になるし、cdr なら set-cdr! などの対応するインバージョンに 個別に変換する式を書いてやる必要があるわけだ。 SRFI-17 の実装例では簡単なマクロと setter なる関数に分れていて、 setter 中にそれぞれのインバージョンを定義してるのかなぁって感じ。 (真面目に読んじゃいないけど)

・・・ということはR5RSからデータ型(とそのアクセサ)を拡張している処理系では あとから一般化参照を取りこむのは結構大変なんじゃないか?
特に処理系の上でさらに新たなクラス定義と、 そのセレクタが定義できちゃうような実装では・・・と思い、 gauche の srfi-17 のライブラリがどうなってんのかなと調べたら ライブラリじゃなくて組み込みで実装してる模様。(ああ、やはり)

>(defun mynth (n lst)
     (if (= n 0)
         (car lst)
         (mynth (- n 1) (cdr lst))))

>(setq x (list 1 2 3 4 5))

>(setf (mynth 3 x) 10)  ;; ERROR!!

とかしても Lisp でもエラーが出ます。(上記確認は clisp/cygwin/win32)
実は私はこれも一般化参照可能だと思ってました。
それで scheme で毎回 mynth などの関数を定義するたびに合わせて 対応する setter を登録してやるのってどうなんだ?と思ったわけです。

しかし、誤解だったわけですがそれでも以下の様にも思います。
上記の例で mynth の呼び出しの評価はいずれ car に行き着くはずなので car にぶつかった時点で対応するセッターに置換されてもよさそうな気がするんです。 そうでなければ、一般化参照って汎変数のところに気を使わないとダメ (つまり組み込み関数か人手でセッターとのマップを追加したもののみが使用可能) ってことになる。
やはり、その scheme 実装の組み込み関数のアクセサに対するセッターのみを srfi-17 に対応するマクロ中に用意しておいてやれば、 それだけで一般化参照がユーザ定義関数についてさえも ばっちり動いて良さそうな気がするのにどうもそうじゃない。 ってところが腑に落ちなかったりします。

もし、そりゃ無理だなぁとなると、 このことは一般化参照を使うコードを組む場合には結構な足かせにはなるまいか?
例えば次の様な例は?

(define (foo-with-generic-set x y accesser ...)
  (bar  ...
     (set! (accesser moo) (hugaga ...))
       ... )))

恐らくこの手の使用は一般的な手法としては使えないって事になりそうな気がします。う〜む。。。cut-sea

実はかなりむちゃくちゃなんだけど漠然と思ってたことなので勘弁

  1. 第二引数 right-value を評価
  2. set! の第一引数 left-value を評価(っていうか展開になるのか・・・)
  3. left-value を評価(じゃなくて展開だなぁやっぱり)してアクセサを定義しているプリミティブに行き着けばインバージョン置換

あぁ、やっぱり第一引数を評価したのではダメで 単に (car x) した評価値が出てきちゃうだけになる。 これを、評価値を取るんじゃなくて場所を指定する式、 例えば (car x) となったところまでで寸止めするってことが評価器にできるとか、 そういう評価器を準備する必要があるんだよと。
逆に式の評価を寸止めすることは出来ない (というかどこまで評価してどの段階で止めたいかは プログラマの気持ちに過ぎないので判断不能ですね)から、 場所を指定するっていう値をファーストクラスとして 扱えるようにしないとこの時点で返すってことは出来ないんですね。2004/03/22 16:10:29 PST


,@ ナットク

どうにも以前から ,@ っていう入力マクロの存在についてイマイチよく分らないでいた。 位置付けというか必要性というかそういう点に確信が持てなかったわけだ。 確かに使う場面もあったが、無くてもいいんでないかい?とか思ってたし、 なんとなく一段上のリスト構造に埋めこむってのが不自然に感じていた。 以前 lisp を自作した時にも、 defmacro の実装時に "," は自然にできたのに ",@" がどうにもうまくなかった。 まぁあくまであれは自作の評価器がずぶずぶだったのが原因だったわけだけど、 なんとなく不自然さを感じずにはいられなかった。

最近 ANSI COMMON LISP と on Lisp を読んでてようやくナットク。 なるほど rest 引数が残りの引数を一手に引き取って リストにパッケージングされてしまうってところから、 逆に rest 引数のメンバを引きずり出して ベタ貼りする必要があるってのに対応してたのか。

分ってしまえば何てことないなぁ。cut-sea:2004/03/18 15:54:45 PST

  (a . b)
      +---+---+
  =>  | a | b |
      +---+---+
  ,b
      +---+---+    +---+---+
  =>  | , |  ----->| b | / |
      +---+---+    +---+---+

  ∴
  (a . ,b)  => (a . (unquote b)) => (a unquote b) ;; 確かに tricky だ
      +---+---+    +---+---+     +---+---+
   => | a |  ----->| , |  ------>| b | / |
      +---+---+    +---+---+     +---+---+

ですね。なんか(a unquote b)って示されたのが 直感と違ったんで帰ったら自分の実装を確認しないと。 (自然な解釈なんでいけてるはずだけど)


ウィンドウマネージャはなざかり

NetBSD1.6.2 にして一からpackageをmakeしまくっているが、 gnome の操作が分り難くなってる上に死ぬほど遅い。
KDEに宗旨替えしようかとインストールするが、 こっちもテーマが気に入らず弄くると動作がおかしくなる。
この辺はもう少しがちがちに安定するまではやめとくか。

日本語が使えて軽くて、それなりの look&feel なのを web 検索してたら・・・ 少し前の BSD Magagine でもやってたけどウィンドウマネージャが 爆発的に増えているぞ。。。 なにがこの現象を引き起こしたのか、 gtk とか qt とかか?

gosh で書けるかなぁ?

私が目を奪われたのは python で書かれたウィンドウマネージャと perl で書かれたウィンドウマネージャ。
perl にいたっては570行程度と宣伝されている。
もちろん見た目はぐずぐずだけどすごいわこりゃ。

そんなら gosh でも書けないかしらんとか思ってみる。

ウィンドウマネージャを書くのにどんな機能がいるのかなぁと 積んでた X-Window Ver.11 プログラミング【第二版】を読んで勉強しよう。
これがまた用語から一つずつやさしく書いてくれてて分りやすい感触。

しかし、まだどのウィンドウマネージャと仲良くなろうか決められないでいる。2004/03/11 20:05:35 PST


人へのメッセージを考える

イラストロジックをデバッグしてて思ったわけだ。

ありがちな話なんだけど、時間のかかる計算をする時、 やっぱり人に向けて何かのメッセージを出したほうがいいんだよなぁ。 ftp とかのような進行状況のメッセージもそうだし、 テレビでたま〜にあるしばらくお待ち下さいもそうだ。

たったこれだけでなぜか体感速度が変わるようなことがある。 何も出ないでまたされると46億年くらいまたされた気がする。

逆に昨年職場のシステムをH/W入れ替えした時、 早くなりすぎて以前は読めたメッセージが一瞬で消えるので なんて書いてあったんだろうってしばらく悩んでしまったりして、 このままやっちゃっていいのか?って立ち止まってしまう場合もある。 もちろん確認を促すでもなく消えてしまったのだから、 お待ち下さい系のメッセージだったのだろうと推測は立つのだが、 そんなもんは設計次第なので確約はできない。

そう、両面あるわけなんだ。

世のソフトウェアって当たり前のようにポータビリティは上がっていく。 configure の出現から autoconf/automake などのツールの出現で ますますそれを促している。 コードは移植性を求められ、いろんな環境で動くように皆がんばってサポートしている。 だが、H/W性能に依存している人へのメッセージ出力って 移植性の最難関なのかもとかなんとか思ってみたり。cut-sea:2004/03/08 16:05:53 PST


イラストロジック開始

Scheme:イラストロジックの最初の version。 とりあえずScheme:イラストロジックに最初のコードをアップさせてもらいます。 あと実行した感じはScheme:イラストロジック:デモです。

ちなみにまだ論理思考しか作れてなくて、途中から推論モードが必要な場合(一般には複数解存在し得るタイプ)はまだやれてない。2004/03/06 22:39:51 PST


セミナーから

一日遅れですけど、Kahuaセミナー楽しかったです。
ご苦労さまでした。
懇親会行きたかったのですがどうにもはずせなかったということで。無念。。。 コメントはSeminar:Kahuaへ移動


マクロの定義名

実はちょっとしたシミュレーションのようなことをしたくて次のようなマクロを書いてみた。(実際のものはもっと色々内部定義を含んでいるけど)

(define-macro (make-lot keyno)
  `(define ,keyno
     (lambda (m)
       (cond ((eq? m 'key) ',keyno)
             (else
              (error "Unknown message type --MAKE-LOT" m))))))

SICPでもよく紹介されたメッセージパッシングスタイルのオブジェクト。 ロットというものを関数で表現している。 マクロは引数にロットのキー名称を与えて呼び出す。

マクロじゃなくて関数にして、

gosh> (define keyname1 (make-lot keyname1))

とするのは避けたかった。(最初はそうしてたんだけど) 必ずkeyname1がシンボル名とオブジェクトの保持する名前と一致する様に 制限したかったからだ。

で、マクロにしてみたんだが。。。

gosh>  (make-lot key1)
key1
gosh> (key1 'key)
key1
gosh> (make-lot key2)
key2
gosh> (key2 'key)
key2
gosh> (key2 'key)
key2
gosh> (map (lambda (l) (make-lot l)) '(keyX keyY keyZ))
(l l l)
gosh> l
#<closure 0x8122e60(m)>
gosh> keyX
*** ERROR: unbound variable: keyX
Stack Trace:
_______________________________________
gosh> keyY
*** ERROR: unbound variable: keyY
Stack Trace:
_______________________________________
gosh> keyZ
*** ERROR: unbound variable: keyZ
Stack Trace:
_______________________________________

このようにマクロにした場合に for-each や map で複数のロットを作りたいと 思っても思うようにならない。
こういう場合の繰り返しを実行する場合の常套手段ってどんな感じに書くんでしょう。2004/02/08 17:25:01 PST


ああ勘違い

実は水曜あたりに The Art of Metaobject Protocol 入着してて、 ちょろっとだけ見たところです。 まだ最初の方を2〜3ページ読んだだけだけど、 TAOCPより難しく感じるのは私だけだろうか。

ちなみに同時にSICPの原書も購入してみたんだけど、 あれれ?なんだこりゃ?って意外でした。 えらく薄くてちっちゃいの。

中身を見てたら、あると思ってた絵がほとんど無いし、 あれってほとんど和田先生が追加したものだったのでしょうか? まぁ、こちらの原書は気が向いたらってことで。2004/01/30 15:44:48 PST


数値データオブジェクトの実装(続)

数値データの読みこみについてはなんとか一段落しました。 みなさんに要所要所勉強する方向をお導き頂き、 その結果TAOCPなんかも読んだりしつつたどりついた。

正確性に基づいて小数や分数に変換するロジックは結局多倍長整数の演算ロジックを 要するのでまだちゃんとしてないけど、とにかく読んで全部分数表記で処理している。 (極座標表記の複素数もそのままで直交座標系に変換していない。)

字句解析の最中で表記がマズイことが判明したものは全部アラームを発生させるものの (とりあえず現時点では)シンボルに落としこんでいる。 この部分も今のとこ全部 goto になってるので不満だらけ。 このテのチェックはじっくり考えて必要最小限に削ったけどなんか多い気がしてうっとおしいし。 (コードの方はリーダ/ライタが全体的に揃ったら一旦整理した方がいいかな〜と思っている。)

数値データの読み込みロジックに侵入している段階で R5RS的にはシンボル名に使えない文字を捕捉しているので("+"や"-"もそうですね) 全部エラーにしてしまった方が良いのかなぁと思ったり、判断は先送り。

で、数値データのリーダ部分を作ってる最中にちょっと思ったのでメモっておきます。

循環小数???

実は実装途中で循環小数なんかもサポートしてみようかと考えた。

test> #e.[123]        ; こいつは簡単だろう
41/333    ;;; 123/999

test> #i.[123]        ; これが実際には難しい、
0.[123]               ; 内部で一旦分数にしたものが
                      ; 循環小数であることを捕捉するのが難。

test> #i-41/333       ; こういうのもアリというか、
-0.[123]              ; 上の例の難しい部分の根本はコレ

みたいな感じ。

新たなデータオブジェクトとかクラスっぽくするわけではない。 読み込みは10進以外の基数をカバーしたとしても同じこと。 (あ、小数になる時点でR5RSのスペック外ですね。) 別に難しくないだろうし、効率もさして悪くはならないはず。

上の様に正確性に応じて分数にしたり循環小数表記(新設)したりできれば 結構面白いかもと思ったわけだ。 (多分データオブジェクトの正確性は読み込んだ時点なら確定的な数値になるのだろうか)

読みこみ自体の計算オーダーもほぼ一定になるだろう。 (教わったのは高校だったかな、等比級数の総和に帰着するだけなので公式を埋め込みゃ一発だ) 混合循環小数になる場合も分数もしくは小数の加算が一回余分に入るだけ。 (循環するまでの部分がオフセットになる)

ただ、ライタ(表示)側というか循環小数になることを検出したり

循環桁数を算出するためには素因数分解がいる(らしい)ということで試行停止した。 この辺の情報もwebをあさると結構転がっていて、これはこれで面白い。 桁数の算出も素因数分解が前提だがアルゴリズムが存在するってか研究済みなんだね。 (やっぱり皆も算出できないかと考えるんだなぁ、と感心したり。)

ライタの方は循環表記なしね!ってのもありだけど、 なんか中途半端でヤダし、R5RSにも書き出したものを読み出したら全く同じ データにならないといけないみたいな記述が確かあったような。。。 (循環小数用に書式を改造した時点でスペック外なんだけどさ)

あとは特殊な文字を一つでも増やすと結構コードをいじらないと(特に書式チェック) いけないんで、ライタ側の目処が立たない限りは見送りだなぁと思った次第。cut-sea:2004/01/22 16:39:34 PST


TinyCLOS

TinyCLOSをweb検索するとなかなか本家(?)と思われる所が見付からず難儀した。 いろんな所で見付かるんだけど、どれも古い上にまともにloadできない。 結構バージョンにも差があるし、大元のサイトからじゃないと信用できない。

で、かなり巡り歩いた結果、1〜2Hr位でなんとかそれらしい所をみつけた (連絡先のメールアドレスがGregor/Xeroxなやつだったんで)。

しかし喜んだのも束の間で、これまたナカナカloadできない。 手持ちの処理系で唯一そのままload出来たscmですら、 実際にここ でチュートリアルを読みながら入力してみたけど、ん〜なんか変だ。

ソースコードを読もうと思ったが、結構難しい。 試しながら確認できれば一番いいんだけどねぇ。

しかし、たったこれだけのコードでできるなんてTinyCLOSってのが小さいのか? それでも実現していることを考えると色んな意味で凄いなあと感心。

いずれ要りそうな気がしたんで、 たった今amazonで『The Art of Metaobject Protocol』を購入することにした。2004/01/20 06:23:23 PST

買うことにしてから聞くのもなんだけど、この本は読みやすさはどんなもんでしょう。 よく考えたらLispに特化した内容じゃないから、 S式で解説されているわけじゃないですよね・・・。(しまったマズイ)


数値データオブジェクトの実装(続)

自分なりにschemeを実装しようとしてて、 現在数値データのリーダ/ライタをコーディングしているわけだけど、 どうにも数値データの取り込みがうまく無い。;-<

字句解析がごちゃごちゃしちゃって長ったらしく汚くなるので、 なんどもなんども色々工夫しながら書き換えていき、 ようやくそれっぽい形に持っていけそうな感触だけど、 めちゃめちゃパワーを取られてる。

数値データの読み込みって大変。。。cut-sea:2004/01/12 18:16:49 PST


Gauche:組み込み関数の再定義:2004/01/09 14:33:39 PST


数値データオブジェクトの実装(続)

昨夜虫取りして整数値についてはおっけーな感じ。

これから実数や複素数の実装をやってみる。 この辺は情報処理系の学科を出たような人達にはあったりまえなレベルなんだろうなぁ。 いまようやく整数だけって感じで、しかもまだまだこれからだもんね。

いちおうリーダ/ライターのみを作ってて、 今のところこんな感じだったりします。

test> #e#x812376237626834
581588196859734068
test> #o7671521375
1055302397
test> #b00011111010101011
16043
test> (#x-123 hoge 'foo bar)
(-291 hoge (quote foo) bar)
test> "Hello, World!"
"Hello, World!"
test> #?な 
#?な
test> #o#e-7654321
-2054353
test> #(1 #(3 4 5 7) #?ふ #x987654321987654321)
#(1 #(3 4 5 7) #?ふ 2812431594283598168865)
test> '(1 #()    "HeyHeyHey"    +  -    'scheme   .  end)
(quote (1 #() "HeyHeyHey" + - (quote scheme) . end))
test> (define-macro hoge ()   
         `(huga ,poo ,@puu))
(define-macro hoge () (quasiquote (huga (unquote poo) (unquote-splicing puu))))
test> ^D
cut-sea@jini> 

数値データを作り込んで、早く評価器の実装に移行したいっす。

まずは目の前の課題で有理数ってか分数をどうしたろかってことで、 Gaucheだけでなく色んなScheme処理系の数値データの処理を見てるけど結構差があったりして・・・

この部分に関しては個人的にはscheme48のものがいいかなぁと思っているんだけど。

> 123/43
123/43
> 4312/34
2156/17
> #x123434/43
1193012/67
> #x123434
1193012
> #x43
67

この辺の動作が好みなんだけど、これって既約分数にするってことだから、 巨大数とか与えると素因数分解とかでパフォーマンスが落ちまくりそう。2004/01/08 06:30:55 PST


数値データオブジェクトの実装

オリンピックイヤーですねぇ。 みなさま、あけましておめでとう。

えーと、年末年始を兵庫の実家でのんびりしてきました。

帰省中全く計算機をいじらなかったのって久々だ。 その間ずっと多倍長整数の基数変換について考えてた。 ノートだけは持ちかえってた。(ペーパーの方)

昨夜、考えた通りに基数変換をコーディングしてみたらなんとなく動いてるくさいのだが、 たとえば#x123456789abcdefのような数を試してみると、最後の一桁は1だけ多く計算しちゃう。 いろいろなケースで正しそうな値を示すものの結構バグバグしてる。

Cにおけるdoubleとunsigned long間の変換などの絡んでいるからか 完全動作までは確認できず。 似たようなことが昔あったんだけどなぁ。

遅かったので寝ちゃったけど、 まぁあとはprintf攻撃で突破できるだろうと楽観している。2004/01/05 19:16:36 PST


名前付letに関する恥ずかしい勘違い

ものすごく初歩的なことを勘違いしていた。 ずっと末尾呼び出ししかしてこなかったからだな。(としておこう)

gosh> (let loop ((a 10) (b 1))
        (if (> a b)
            (begin
              (set! a (- a 1))
              (set! b (+ b 1))
              (loop a b)))
        (print "hello a: " a " b: " b))
hello a: 5 b: 6
hello a: 5 b: 6
hello a: 6 b: 5
hello a: 7 b: 4
hello a: 8 b: 3
hello a: 9 b: 2
#<undef>

この動作だ。

私はずっと最後に

hello a: 5 b: 6

とだけ表示されるものと思ってた。 再帰だから巻き戻しが発生するのね。 Scheme:call/ccパズルの動作が全然理解できなかったのもこの辺の理解不足か?cut-sea:2003/12/06 19:40:03 PST


TAOCP読み込み(続)

TAOCPのコーディングを試させてもらいましょう。 WiLiKiでもGaucheでもないけど許されて。。。cut-sea:2003/11/28 21:31:06 PST


TAOCP読み込み(続)

TAOCP読んでると、やっぱMIXのコードを読めた方がいいかな〜ってことで、 Vol.1のMIXの解説を読んでみる。 自宅のWiLiKiにメモりながら、ちびちびやってるんだけどどうも難しいな。 めちゃめちゃ計算しにくい気がする。。。 本当にこれでいいのか? D.E.K.!!cut-sea:2003/11/13 06:05:09 PST


TAOCP読み込み(続)

The Art of ... 最初どうなるかと思ったけど浮動小数点数の所に入って結構読める。 それなりに予測がつくと意外に読みやすかったりする。 はっきり言って学生時代から英語は苦手な方なんだけど。cut-sea:2003/11/01 09:33:44 PST


TAOCP読み込み

The Art of ... を読み始めた。 基数が負の数とか虚数とか・・・考えたこともなかった。

とにかくちょっとしたメモを取りたくなるだろうということで、自宅で立ち上げたWiLiKiを使用してみる。cut-sea:2003/10/31 17:11:41 PST


本日 The Art of ... 入着連絡ありました。 早速定時で会社を引けて来てもらって来ました。 依頼したのが 9/17 だから約 6week か〜取り寄せだったのかな〜微妙だな。cut-sea:2003/10/28 02:01:48 PST


WiLiKi を導入してはみたものの・・・

とりあえず、 WiLiKi を入れてみた。

Ver.0.4 で、結局以前 gdbm のところでつまってたんだけど、fsdbm でもって設定し、 とにかく動かしてみてみた。

で、FAQ とかにもないんで、もしかしたら私だけ?ってのが。 fsdb に関係したgaucheのバグでした ⇒WiLiKi:Bugs:done


言語の機能とOSの機能

やはり The Art of... は海外からの取り寄せになるのか連絡がまだ無い。

ちょっと時間が空いてしまったので UNIX コマンドのクローン作成なんぞをしてみながら scheme の勉強をしています。

そこで一つ疑問が。。。 raw モードでキー入力を受け取りたいのだが、 scheme ( や他の Lisp) ではどうするのでしょう? 今はまだフィルタ系コマンドをちょろっと始めたとこですが、次なに作ろうかと探していたら more なんぞが気になったもので。cut-sea:2003/10/16 06:57:20 PDT

いくつかの(全部かどうかは知らないですが)スクリプト言語では system 関数があって、 そいつを経由して shell に仕事させてってのが汎用的な口になると思うのですが(違ってたりして)。

gauche では sys-system 、 guile や scm や STk だと system がやはり準備されてますよね。 基本的には全部同じ機能と思ってますが、これが汎用でシステムとやりとりできる方法でいいんですよね? この辺を使うのかなと思ってたんです。 分からないけど stty ... を使ってうまくやれるのかな〜とか。

ところが r5rs を見ても、それ以前に system っぽいのが見当たらないんで、 scheme ではどうやるのが普通なんだろうと思いました。 確かに gauche ではやれるんだけど、じゃぁ他の処理系は?とか。

私自身独学だけでやってて周囲に詳しい人がいないので、 常識的なところが結構欠けていてトンチンカンな質問かも知れないですが。

gauche.termios のコードをみりゃいいんだと思って、share/gauche/0.7.2/lib/gauche/termios.scm を見たら、dynamic-load ... てことはC で作成された共有ライブラリの動的ロードだから、ちょっと期待してたのと違うんですよね。cut-sea:2003/10/17 19:01:10 PDT

Foreign Function Interface = 外部関数インターフェースってやつですね。名前もまさにそのままって感じですね。cut-sea:2003/10/17 22:58:46 PDT


魅惑のλTシャツ

bignum の実装に関して調べてました。 日本語の情報で実装について書かれているところとかが見当たらず。。。 英語苦手だけど救いを求めて comp.lang.scheme を漁ってたらλTシャツなんてのが出ててすぐ道草。(^^)

しかし、 Baby Doll T シャツなんてのもあって、こんなん着てる女がいたら引くぞっ!! ただ、キャップやらカップやら持ちたいかも〜。


継続についての文書(6.001)

ん〜 6.001LectureNotes にて取得した continuation.pdf を訳してみたんですけど、はっきり言って they/them なんかの指しているものの訳がかなり怪しい。。。 訳文もかなり意味分からんってのが何箇所もあるし。 とりあえず、だしてみるので興味ある人修正しまくったってくださいな。。。cut-sea:2003/09/10 08:02:54 PDT

継続

このノートはプロセスの中で計算フローを制御する際に使う継続についての補足的な背景を提示するものである。
継続のアプローチは通常の Scheme のコードとは違ったフロー制御をする。
呼び出し元に値を返す手続きを書くのではなくて、継続と呼ばれる引数(手続き)を受け取り、
返り値をその継続手続きに与えて呼び出すような形式で手続きを書く。
例えば、

(define (add-to-3 x)
  (+ 3 x))

を

(define (add-to-3 x cont)
  (cont (+ 3 x)))

として書き換える。

この add-to-three の新しい定義は直接にはいかなる値も返さない。
その代わりに、呼び出し元が cont として提供するものにその値を渡す。

なぜ継続なのか

なぜ継続渡し形式を使うのだろうか ?
継続はあなたのプログラムの制御フローを上回る、より優れた制御を与える。
例えば、あなたは手続きに複数の継続を渡すことが出来るのだ。

(define (divide a b success fail)
  (if (= b 0)
      (fail "divide-by-zero")
      (success (/ a b))))

継続を使わなければ、 (divide 17 0) の評価は計算を終了させて、
デバッガを起動させるかどうかを聞いて来るだろう。
継続を使えば、エラーメッセージを印字する fail という手続きを渡し、
計算を再開できるだろう。
継続のもう一つの別の側面とは、手続きの返り値に起こり得る全ての未来の計算を表現することである。
それらの継続は変数として渡されるので、それらを蓄えたり、他の手続きに渡したり、

さらには違う値で複数回呼び出すという様な気の利いた事が出来てしまうのだ。
この評価例では、継続はエラー処理の有用な手段を提供する。
もし、いくつかのエラー条件に出食わすならば、現在の継続を覚えておくことが出来て、
ユーザにそのエラーを修正するか処理するかを問い合わせ、それから保存しておいた継続を呼び出して
計算を再開することが出来る。

継続を用いた実例

これまでの手続きはかなり簡単なものである。
継続を使った、より面白い手続きをいくつか書いてみよう。

(define (factorial n c)
  (if (= n 0)
      (c 1)
      (factorial (- n 1) (lambda (x) (c (* n x))))))

これは旧友である階乗だ。
基底条件に注目しよう。
もし n が零なら、継続に 1 を渡して呼び出すだけである。
(つまり、もしかしたら返り値となったであろう値を継続に渡して呼び出したのである)
再帰条件の場合には (- n 1) を伴って factorial を呼び出しつつ新しい継続を渡す。
その新しい継続は (n-1)! (これは継続にとっては下請けであることを覚えておこう;
継続はその手続きの返り値を伴って呼ばれる)の値を伴って呼ばれる。
つまり、我々の (lambda (x) ...) は (n-1)! を伴って呼ばれる。
それに n を掛けた値を元々の継続である c に渡す。

今、我々はこのような手続きをどう呼び出せば良いのだろうか ?
(継続形式の使用が、このプロジェクトの2番目の部分になる評価器を、
その内部に覆い隠すかどうかには無関係であることに注意せよ)
そう、我々は n と、そしてその結果を使って何をするかを我々に伝える手続きを
その手続きに渡して呼び出す必要があるだけなのだ。
例えば

(factorial 10 (lambda (x) x))
;Value: 3628800

これはただ最終的な値を返すという (継続を渡してやる) だけだ。
しかし、代わりに我々が結果をどう印字するかに手を加える事が出来る。

(factorial 10
           (lambda (x)
             (newline)
             (display "Factorial result is: ")
             (display x)))

はモニタ上に次に示すように結果を表示する。

Factorial result is: 362880
;Value: #[unspecified-return-value]

次は継続を使用した版の sum-interval(これは a から b に含まれる数値を合計する)である。

(define (sum-interval a b c)
  (if (= a b)
      (c a)
      (sum-interval (+ a 1)
                    b
                    (lambda (x) (c (+ a x))))))

この式の再帰条件では、我々は a+1 から b までの区間の sum-interval を呼び出す。
新しい継続は a+1 から b までの区間に渡る合計に a を足して、呼び出し元の継続にその値を渡す手続きである。

GHG 最近読めてなかったけど、 私自身は少し再開。。。 でも例によって Shiro さんに手取り足取りで教えてもらうばっかり。 ^^;; vm 周辺が理解できれば、かなり嬉しいんだけど。

一方 Common LISP 2nd edition ははっきり言って難解なので (まぁ仕様書なんだからこまかい説明や事例はねぇ) しばらく前に秋葉に出たときに ANSI Common Lisp の邦訳を購入した。 これにもCLOSの解説があるので少し時間を作って読んでみたり。2003/09/02 03:44:15 PDT


CLOSについての勉強

どうやら gauche のソースを読む上である程度の CLOS の知識が必要になるようだ。 GHG の各所で Shiro さんがポイントしてくれる時にも CLOS の用語だとのコメントが出て来ることがよくある。

というわけで、部屋に積んでた Common LISP 2nd edition の CLOS の所をつまみ読みすることに。 そういや買ってたんだな〜。

とりあえずメモっておく。

CLOS における基本的なオブジェクトはクラス、インスタンス、 総称関数(これがジェネリックファンクション)、およびメソッド。

「総称関数は与えられた引数のクラスまたは引数の一致に依存した振舞をする関数」とある。 「メソッドは総称関数にクラス特有の振舞と操作を定義する。したがってメソッドは総称関数を特定化(スペシャライズ)する」というらしい。 また、「総称関数が呼び出されると、与えられた引数のクラスに基づいて、その総称関数に属するメソッドの部分集合を実行する」という説明になる。

ここまでの説明からすると多相性を有する関数という感じかな。

 (+ 3 4) => 7
 (+ "Hello," "World!") => "Hello,World!"

みたいに引数がどんなデータ型かで振舞をかえられるものと言うわけだ。

次にメソッド。。。と思ったけど概念の説明を読む限り全然何者なのかすぐには分からない。 メソッド結合機能だの引数特定子だのいろいろ不明用語が連発されている。 今後、少しずつ読み進めるとしよう。2003/07/18 06:09:25 PDT


ん〜、やはり GHG を読んでて Shiro さんがポインタを示してくれたNumericTower だけど、 そこで出て来る実装継承/インターフェース継承って用語をはじめて聞いたのでまだ理解できないでいる。

web で検索してみると一般に使われている用語のようだけどイマイチ意味と用語が繋がらない。 どうも、両方ともクラスの再利用の方法らしいんだけどね。 いわゆる継承=実装継承、クラスネスト=インターフェース継承?ってことになるのかな??

私自身は委譲とかクラスネストとか違いが良く分からないし。。。 昨日ちょろっと立ち読みした本では長々と C++ のコードが示されてて こんな風に微妙に違うんだよ〜って書いてたけど、 C++ 読めない。。。

今のところそれが分からないので、 Shiro さんが今の実装の何が気に入ってないのかも実はよく分かってない(-_-;; cut-sea:2003/07/08 15:15:25 PDT


Brainfuck

brainfuck ってのが結構面白そうだったのでちょっと作ってみる。 なんかループさせるところで手順にまよったけど、なんとか hello.b echo.b quine2.b あたりが動くとこまで。 でも普通の動作させてるだけで最適化とかもしてないから quine2.b なんか結構遅いってかトロすぎ。。。 やっぱり、あの程度の言語でこういう作り込み方って無駄が大きいのかな。

作ってみて思うのは、skimu さんが作ってるコードの parse/bfi 辺りって、 すごいシンプルで?#[ ?#] の扱いがうまいな。 ?#[ と ?#] の間を再帰的に扱ってて、よく答えを見るとあ〜なんだ〜ってのがあるけど、あの感じ。 すんなりこういったコードが書けるようになれたらな〜。 最初見たとき何やってんだか分からなかったけど、 自分でメカニカルに組んだら面倒くさいとこだっただけに どうやって実現してるのか見えたときにはちょい感動。cut-sea:2003/06/28 11:35:37 PDT

⇒コードはScheme:Brainfuck:別解へ移動2004/01/21 01:26:15 PST

実行例は削除2004/01/20 23:20:18 PST


例によってGHG。。。 少し前に戻ってBasicTypes を読んでたんですけど、今更〜な質問があるんですけどお願いします (^^;

gauche.h の 123 行目あたりにポインタってありますよね。 32bit の下2桁が 00 のタグ付きのもの。 SCM_PTRP(obj) なんかが述語的に使われている。 ところでこれ、どこでどんな風に作られているんでしょうか? そもそもポインタをビットシフトして。。。とか加工するってことは低位のシステム からメモリをもらって、そのアドレスを加工してる? じゃあ参照するときにも毎回逆に演算が必要になっちゃう? ポインタだから、も〜うんざりするくらい出て来るだろうと、 あのときは思ったんだと思うけど、その後さっぱり見掛けないし、 src の下で SCM_PTRP で grep してもそんなにマッチしないし 当然のことながら判定して条件分岐するような使われ方でしかないようだし。 すみませんけど、教えてやってください。今ごろ異常に気になってしまって。

ちなみにあっちに書かなかったのは

  1. 時期を逸したんで見付けてもらえなそうな気がした
  2. 説明聞いたらなんとなくお試しコードを書く気になりそうな予感がした

ってことで。cut-sea:2003/06/21 19:33:07 PDT


手続き的ポート(gauche)に関して

GHG:gauche.h:Port に書き込みしてて、ポートの所が普通の代物より難しそうなのでリファレンスマニュアルをみてたんだけど、手続き的ポートって英語のままなんだよね〜まだ。とりあえず訳してみる。 ⇒原文はコメントにして隠した。2004/01/20 23:20:18 PST

6.18.6 手続き的ポート

手続き的ポートの潜在的な機能は非常に柔軟だが、後述の各1つづつを除いて今のところは scheme のインターフェースを用意していない。

これらの手続きはより汎用の手続き API により価値が無くなり、いずれ置き換えられるだろう。

これらの手続きはバッファードポートへの Scheme インターフェースとなるものだ。

open-input-bufferd-port は関連づけられたバッファのサイズ buffer-size を伴う入力ポートを作成して返す。 データはバッファから読み出される。 ポートが読まれて、そのバッファが空だった場合、読みだし要求されたデータのサイズを一引数として取る手続き filler が呼び出される。 filler は(完全でも不完全でもよいが)サイズの確定した文字列を返す。 要求されたサイズに十分なデータが用意出来ない場合、filler はそのサイズより短い文字列を返すことが許されている。 filler がその要求されたサイズより大きな文字列を返すならば、その場合の振るまいは未定義である。 注意してもらいたいのは、文字列の長さではなく、サイズが問題なのである。 もし filler がそのデータソースから EOF を検出したら、 EOF を返す。 サイズがゼロの文字列を返すことは EOF を返すことと同じ効果を持つ。 最初はバッファは空だから filler はいつもポートからの最初の読みだしとして呼ばれることになる。

open-output-bufferd-port は関連づけられたバッファのサイズ bufferd-size を伴う出力ポートを作成し返す。 ポートへの出力データはそのバッファ内に蓄えられる。 バッファが一杯になったり、あるいはポートに対して flush が呼び出された場合、手続き flusher が不完全文字列をフラッシュするために呼ばれる。 flusher はフラッシュしたバイト数を返すべきであり、それは通過した文字列のサイズに等しいはずである。 その文字列が buffer-size より短くてもかまわない。 ポートがクローズされていた場合、 flusher はバッファに残った任意のデータについて呼ばれる。それから再度 flusher はポートがクローズされていることを示す #f を伴って呼び出される。


Cのmallocに関する常識でした

やっぱ GHG で読んでてなんだけど、ベクタのところ。 ScmVectorRec の要素 elements[1] なんだけど、 なんで 1 ?って思って、 make_vector するとこ見たら、 え〜、こんなサイズの取り方して普通にアクセスできるんだべか?

で、試してみる。 ⇒Cコード及び実行確認は削除2004/01/20 23:20:18 PST

ん〜よーわからんが、いずれにせよこの手法は構造体のメンバの最後のものについてのみ使えるんだな〜ってのを確認して少しほっとした。

ただ、これって C の常套手段臭いな、雰囲気が。 ただの恥さらしかもしれん。 cut-sea:2003/06/11 07:24:44 PDT

いやいや!問題はそんなこっちゃないぞ! free はどうするんだ? free(v) としたら elements[1] 分を含む構造体のメモリ空間しか free すまい? よーわからんが、なんとなく・・・メモリリークしやしないか? cut-sea:2003/06/11 08:59:30 PDT


週末だし、ちょいと酒飲んでますけど、GHG にて gauche.h の Class の読み込みに 入ったので目を通してる。 オブジェクト指向言語の用語にあまり慣れてないので、とまどいがあるけどねcut-sea:2003/06/06 08:44:33 PDT


ScmObjの実装について

これまであんまり Scheme の実装とか詳しく見たことないんだけど、 Gauche でいうところの ScmObj に位置する構造体って中身では各基本データ型の共用体になってるものと思いこんでた。 (で、 ScmObj の最初のメンバにはデータ型の型タグがあって〜みたいな感じ。)

昔少しだけのぞいた GCL なんかはそんな風に出来てたような記憶がある。

gauche.h を見てるとなんか違いますねぇ。どうやってつながるんだろうか?2003/06/04 16:55:59 PDT


とりあえず、継続が分からん。。。2003/05/29 20:02:30 PDT

More ...