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). 

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

• これは別にどってことなかった。 rescue以下に見知らぬ方々がいるのかと思ってた。
  問題は日本語環境構築。結局土日ではまるで足らず、第一回目の対局は敗戦。
• リベンジ成功！ kterm上での日本語入力にて若干まだヘンテコなところがある。
  • .Xresources の中の FontList 属性と -fn 引数のサイズが違ってて 文字サイズ(pitchとか)を誤って取得したんだろう。 カーソルの動きと表示がずれてて苦しんだが無事回避できた。 いよいよ pthread 付で Gauche の make に挑戦かな。 cut-sea:2004/12/22 02:35:06 PST
  • むぅ。GC からして support が必要な感じ。

• おぉ、以前書いてた pmap が 2.0 から組み込まれてる。

  HISTORY
       The pmap utility appeared in NetBSD 2.0.
  

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))))))))

• teranishi: 細かいけど、(_ (fn arg) body ...)と(_ (fn arg ...) body ...)の パターンは必要ないですね。
  • 修正しました。どうもパターンが把握出来てないっす。(+_+; cut-sea:2004/12/02 06:05:05 PST

高速フィボナッチ

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

• teranishi: ggc の trace で、苦し紛れ版の fib-dash をトレースしてみます。

  gosh> (fib-hi 6)
  0:(fib-dash 0 1 6)
  1:  (fib-dash 1 1 5)
  2:    (fib-dash 1 2 4)
  3:      (fib-dash 2 3 3)
  4:        (fib-dash 3 5 2)
  5:          (fib-dash 5 8 1)
              ->8
            ->8
          ->8
        ->8
      ->8
    ->8
  ; trace: fib-dash has been called 6 times.
  8
  

  fib-dash の引数を見てみると、一度も同じ値が現れません。 つまり、一回の実行では、cache が全く使われない事になります。
  そもそも、fib-hi は、自前で fib の値を cache することで高速化しています。 (fib-dash の引数を見れば分かると思います) そのため、memoize しても、その分の負荷が増えるだけなのです。
• fib-super とかも試してみたんだけど難しくてよく分かんないっす。(++;;
  とりあえず、他の引数を累積変数みたいに使ってるのかなぁと感じる。
  cache として使っているというより、同じ引数パターンにならないように 避けている(？)様にすら感じるんですよね。cut-sea:2004/11/29 05:44:01 PST
• teranishi: 私も fib-super に関しては何をやっているのか分かりませんが、 少なくとも、一回の実行で cache が効かない事だけははっきりしています。 なぜなら、再帰の時に自分自身を一度しか呼んでいないからです。 この場合、もし一回の実行で同じ引数パターンが現れたとすると、 同じ計算が再び行われる事となり、無限ループになってしまうからです。
  • 何かいろいろいじると黄金比を使った一般項が求められるわけですけど， その中間の結果なんですかね? ちょっと面白いけどどういう計算なんだかまでは読めないな．
  • teranishi: trace 結果とか m^n の O(log n) 計算方法とかを参考にして、 適当な説明をでっち上げました。

    fib(n) = fib(n-1) + fib(n-2)
           = 2 * fib(n-2) + fib(n-3)
           = 3 * fib(n-3) + 2 * fib(n-4)
           = 5 * fib(n-4) + 3 * fib(n-5)
    
    これを一般化すると、以下のようになる
    fib(n) = fib(k+1) * fib(n-k) + fib(k) * fib(n-k-1) ・・・(1)
    (0 <= k <= n-1)
    
    (1)に n = 2^(m+1), k = 2^m-1 を代入
    fib(2^(m+1)) = fib(2^m) * fib(2^m+1) + fib(2^m-1) * fib(2^m)
                 = fib(2^m) * (fib(2^m) + fib(2^m-1)) + fib(2^m-1) * fib(2^m)
                 = fib(2^m) * fib(2^m) + 2 * fib(2^m) * fib(2^m-1)
    (1)に n = 2^(m+1)-1, k = 2^m-1 を代入
    fib(2^(m+1)-1) = fib(2^m) * fib(2^m) + fib(2^m-1) * fib(2^m-1)
    
    p(m) = fib(2^m-1), q(m) = fib(2^m) とすると
    p(0) = 0, q(0) = 1
    q(m+1) = q(m) * q(m) + 2 * q(m) * p(m)
    p(m+1) = q(m) * q(m) + p(m) * p(m)
    これで、fib(2^m) (=q(m)) が求められる
    
    (1)に n = 2^m+l, k = l を代入
    fib(2^m+l) = fib(l+1) * fib(2^m) + fib(l) * fib(2^m-1)
    (1)に n = 2^m+l+1, k = l+1 を代入
    fib(2^m+l+1) = fib(l+2) * fib(2^m) + fib(l+1) * fib(2^m-1)
                 = (fib(l+1) + fib(l)) * fib(2^m) + fib(l+1) * fib(2^m-1)
                 = fib(l+1) * fib(2^m) + fib(l) * fib(2^m) + fib(l+1) * fib(2^m-1)
    
    a' = fib(2^m+l+1), b' = fib(2^m+l), a = fib(l+1), b = fib(l) とすると
    b' = a * q(m) + b * p(m)
    a' = a * q(m) + b * q(m) + a * p(m)
    これは、l を 2^m+l に更新する、つまり、fib の引数に 2^m を足すことに相当
    
    あとは、a = fib(1), b = fib(0) に初期化しておいて、
    2^m が出てくるたびに a, b を上の式で更新すればOK
    

• まず、fib-hi の方は素直な計算ロジックですね。

   i          0   1   2   3   4   5   6   7   8   9   10  ...
  ------------------------------------------------------------
  fib         0   1   1   2   3   5   8  13  21  34   55  ...
  ============================================================
  fib(a,b,5)  a   b
  fib(a,b,4)      a   b
  fib(a,b,3)          a   b
  fib(a,b,2)              a   b
  fib(a,b,1)                  a   b
  fib(a,b,0)                      a   b
  
  逆にレジスタの値で見ると
  
         a    b   counter
      =====================
         0    1      5
         1    1      4
         1    2      3
         2    3      2
         3    5      1
         5    8      0
  

  fib-dash の引数は順に a レジスタの値、b レジスタの値、counter になってる。 counter = 5 の時には 5,4,3,2,1 と順にカウントダウンして、反復動作させてる。 その回数分 a レジスタには b を b レジスタには a+b を MOV してるだけか。 再帰形と反復形って訳ね。fib-super の方はやっぱダメ。 こういう式展開自体拒絶反応が。
  

  gosh> (fib-dash 1 0 0 1 2)
  2:    (fib-dash 2 1 1 1 0)
  fib(2) => 1
  
  gosh> (fib-dash 1 0 0 1 3)
  3:      (fib-dash 3 2 1 1 0)
  fib(3) => 2
  
  gosh> (fib-dash 1 0 0 1 4)
  3:      (fib-dash 5 3 2 3 0)
  fib(4) => 3
  
  gosh> (fib-dash 1 0 0 1 5)
  4:        (fib-dash 8 5 2 3 0)
  fib(5) => 5
  
  gosh> (fib-dash 1 0 0 1 6)
  4:        (fib-dash 13 8 2 3 0)
  fib(6) => 8
  
  gosh> (fib-dash 1 0 0 1 7)
  5:          (fib-dash 21 13 2 3 0)
  fib(7) => 13
  
  gosh> (fib-dash 1 0 0 1 8)
  4:        (fib-dash 34 21 13 21 0)
  fib(8) => 21
  
  gosh> (fib-dash 1 0 0 1 9)
  5:          (fib-dash 55 34 13 21 0)
  fib(9) => 34
  
  gosh> (fib-dash 1 0 0 1 10)
  5:          (fib-dash 89 55 13 21 0)
  fib(10) => 55
  

  でも、fib-dash/fib-super を trace で順次走らせて、解が求まる時の a b p q を 見ているといずれもフィボナッチ数列に出現する値ばかり。 理屈は依然として理解できんけど、いずれも累積変数臭いなぁ。cut-sea
  • teranishi: trace するなら、まず引数 q に注目してください。 fib(1)->fib(2)->fib(4)->fib(8)->... というふうに変化しているのがわかると思います。
    次に、引数 b に注目してください。たとえば、fib(13) (=fib(1+4+8)) を trace すると fib(0)->fib(0+1)->fib(0+1+4)->fib(0+1+4+8)というふうに変化しています。
    要するに、引数 q で fib(2^n) を計算して、それを引数 b に足しこんでいるのです。

• teranishi: 今更ですが、内部 define の評価順の問題で 動かなかったコードは、二番目の define を set! に変えると 動くようになります。 ただ、実行するたびに cache が作り直されますが。

今ごろ気付いたのでした

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

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

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

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

会場爆笑だったのに、５ヵ月遅れとは・・・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

• 今見たら野田さんの邦訳も一通り完了した様ですね。 どっかの出版社さんとか出してくれないかなぁ。 とりあえず今からちまちま印刷してみようかしらん。cut-sea:2004/11/06 19:45:25 PST

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 ((x (cons (block-tree in) tree))) (loop x (read-line in))) とやるかな、skimu
• そうですね。ただ、引数が増えてくると入れ子が増えてくる。 結果としてインデントが深くなる。 で、どんな処理系でも左から評価されることが保証された名前付letって 欲しくならないのだろうかと思ったりするのです。（多分マクロか？）
  let で束縛を作るときに同じスコープで束縛するもの達と 内側のスコープで束縛するもの達って、どっかで区別してませんかね。
  レイヤーとでも言えばいいのかどうか分かりませんけど、 たいていは外側の束縛の方が低位の概念で。cut-sea
  • 余談ですが、カーリーブレースって正規表現中でまんま使えたんですね。 確認してませんでした。 最近 {3,7} みたいな繰り返しもアリな正規表現があったりするので NG ワードかと思ってました。cut-sea:2004/09/05 22:57:04 PDT
  • あー、emacs でC-[ C-\でインデント揃えようとしたらbeepする〜 escape しないと括弧の仲間と思われ取るんだろか(T^T)
    
• 関数の引数をどの順番で評価すべきかは、関数を定義するときではなく、関数を呼び出すときに決まるのではないでしょうか。
  そう考えると、名前付let*を作るよりは、loopの呼び出しの時に引数の評価順を指定するようにすべきでしょう。
  評価順の指定は、skimuさんのように明示的にやってもいいし、引数を左から右に評価するマクロを組んでもいいでしょう。teranishi
• んーと、先に断っておくと私はこの点について、どうしたいとかこうあるべき といったあまり積極的な主張が無いままです。すみません。
  ただ、teranishiさんのおっしゃる評価順の指定は呼び出し時に決まるというのは 私にはr5rsの仕様がそうだから、結局そうなるよね？ という風にしか解釈できないです。(誤解だったらごめんなさい)
  逆に仕様が ((lambda (a b c ...) (body ...)) a-val b-val c-val ...)の評価において λ式が評価、 a-val b-val c-val と左から順に評価して、最後に apply するよと 決まっていればどうなるでしょうか？
  この場合にはおそらく let の入れ子に相当する環境フレームの積み重ねとか不要に なるのではないかなぁ？と思うわけです。 (あくまでプログラマがそれを理解して引数順を決定していれば)
  一方で、順序が制約される様にも思えるので、本当にそんな制約か付いて困らない？ って考えたりもします。(自分で自分に反論してますけど・・・)
  しょもないところかもしれませんが、(subst new old tree) とかって関数を考えると substitute new for all old in tree で自然な順序 (「初めての人のためのLISP」から引用)というか、要は可読性とかの面で、 この順番にしたい！ってケースもあります。
  もし私が上で言うような評価順があったとして、評価順序は(この場合にはないけど) old tree new の順に評価させたい場合には、読みにくいけど、 あえて(subst old tree new) にする、といったばかげたことはしなくても 済むわけだし。
  支離滅裂ですけど、ふとそんな風なことが色々浮かんだわけです。 うーん、俺ってつまらん所で妙に拘ったりするんです。cut-sea:2004/09/06 03:17:18 PDT
• 誤解を招くような書き方をしてすみません。
  要するに、コードを書く時に、(loop (cons (block-tree in) tree) (read-line in)))と 書き終って初めて、 引数を順番に評価しなければならないと気づくのであって、 名前つきletを書く時点では、引数の評価順は分からないだろうという事です。
  名前つきlet*という言い方をされていたので、上のプログラムのletをlet*に変えると、 loopだけ引数を左から右へ評価するという動作になることを期待しているのではないかと 思ったわけです。
  それだと、名前つきletを書く→(loop ...)を書く→評価順を決める必要が出てきてletを let*に書き換える、という流れになるので、ソースを戻らなければならず不自然だ、 というだけの意味です。teranishi
  • こちらこそ妙な書き方して失礼しました。m(__)m
    冗長に書くくせにどうも要点が・・・(^^;)cut-sea:2004/09/06 04:37:04 PDT

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

• 評価順て左からっていう仕様では？と思ってR5RS読んでみたら、『評価の順序は規定しない (4.1.3.プロシージャ呼び出し)』ってはっきり書いてあったんですね。知りませんでした。なんかCみたい。hira:2004/09/05 20:11:05 PDT

CGIのお勉強２

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を手に取った。
Ｃにおけるメモリ管理関係の記事が出ており、ちょいと立ち読みさせてもらった。

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

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

• なんだ。最近のって書いてあったから諦めてたのに 今見たら会社の古いSunOS 5.6 とかでもちゃんとあるじゃん。 私が知らなかっただけか(^^;
  そういや自宅のNetBSDは/procをマウントしているけど使ってないや。 /proc/#/map とかがそうなんだろうけど。

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

• Shiro: syntax-rulesは、anaphoric macroのような変数捕捉が 間違っても起きないように作られているため、そのままではaifとかは 作れません。健全性を保ったまま必要な箇所にだけ変数捕捉を 許すには、syntax-rulesの持つコンパイル時環境にアクセスする 低レベルの仕組みが必要です。統一規格はまだ無いのですが、 syntax-caseという仕組みはわりとたくさんの処理系にポートされて います。Gaucheでもいつかはサポートしたいと思っています。 なお、syntax-rulesだけで変数捕捉を行う裏技みたいな方法も 実はあります。(が、マクロ機構を限界まで駆使する方法で、Gaucheの 実装はヤワなので実行できないのですが)。Oleg Kiselyovさんの Schemeのページにあったはず。(2004/08/16 04:51:06 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

• このへんも→Gauche:SXMLとSXPath

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

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

しかし２番目以降の非終端についてはなんでじゃろ？
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 など数個しかサポートしてない様に見える)

• Shiro: SXMLはXMLのパーザ構築キットで、ssax:xml->sxmlはそのうち 生のXMLに特化したものだと考えれば良いんじゃないでしょうか。 終端のないタグはHTMLの話であって、生のXMLじゃないですから。 こういう場合はssax:make-parserなどでカスタマイズしたパーザを 作るってことになるんじゃないかと思います。ただ、終端無しのタグを '<foo />' で書いてないHTMLはXMLのサブセットにはならないので、ssaxで パーズできるかどうかわかりません。(sxml:non-terminated-html-tag? は HTML生成に使われてるだけで、パーズには使われてないと思います)。 それと、&nbsp; なんかは該当するDTDを読ませてやれば良いと思うんですが、 どうやるかは定かではありません。HTMLをパーズするなら、 HtmlPragというのもあります。

sitcom

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

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

出力

いまさらですが。

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

どう使い分ける？

• hira: 初稿ではformatしか使わないですね。で、スピードに不満が出たらdisplayとwriteにバラすと。printは最近使ってません。
• そうか。私も format で書くことが多いんですけど、あまり自信がないんですよね。
  っていうのも format って port に #f を指定する使い方があるせいで、 なんとなく、 format = 形式変換の関数？って最近思い始めたからなんです。
  でも出力の関数としてマニュアルに載ってるし、どうもこの #f/#t のオプションって CommonLisp から来ているのかもしれないですけど、違和感を感じます。 文字列形式の変換のみの機能にした方が美しかったんじゃないか？と。cut-sea:2004/07/18 10:43:25 PDT
• Shiro: 伝統的には、portにちゃんとポートを渡す(CLではstream)のが 由緒正しい使いかた、なのではないかと思います。#f/#t のオプションは元祖が どこだかはわかりませんが、まあCLからの輸入ですね。一方、「formattingと 出力は別」という主張はそれなりに筋が通っていて、srfi-28なんかは その方向です。なお、直接portに出力するformatでは、中間文字列をビルドしないので 若干オーバヘッドが少ない、という現実的な理由もあります。 (Gaucheでは呼ばれる度にformat文字列をパーズしているので相殺されてしまうかも。 Common Lispの実装によってはformat文字列がリテラルの場合、formatの呼び出し 自体をあらかじめ変換してしまって、format文字列のパーズを行わないように することができます。入出力がヘヴィな処理では結構差が出ます。 Gaucheもcompiler macroみたいなしくみをいずれは入れたいと思ってます)。

今日本屋にいって 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 ってなってる。

• 通りすがり: http://ntb.utmc.or.jp/c55/UTMCPressC55.pdf
  これと同じものかと。
  • あ、これ！
    余談ながら、同じく探しものとして「Cプログラムブック〜Lisp処理系の作成〜」 って本を探してるんですが、この本についてもUTMCの人が見ると 笑えるとかなんとか書いてあるのを見たことがあるんですが、 このLisp処理系ってのもUTMCが関わってるのかな。cut-sea:2004/07/19 00:47:26 PDT

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

• ん〜、上の zip (from share/gauche/lib/srfi-1/zipper.scm)ですが。

  (define (zip . args) (apply map list args))
  

  これでも OK ですよね？
  

  (zip '(1 2 3) '(4 5 6))
   => ((1 4) (2 5) (3 6))
  (zip '(1 2 3) '(4 5 6) '(7 8 9))
   => ((1 4 7) (2 5 8) (3 6 9))
  (zip '(1 2 3))
   => ((1) (2) (3))
  

  ってなるし。(0.7.4.2 on cygwin/windows 98)
  引数与えなかった時にはどうせ同じようにエラー発生する。（理由は違うかしんないが）
  おそらく一つは必須の引数であることを明示する意味で上のようになってるのだろうか。cut-sea:2004/05/10 01:31:29 PDT

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

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

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

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

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

• "Y combinator" でぐぐってみませう。

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

コンビネータ

自由変数を含まないλ項

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

• Shiro: あれ。style-sheetの部分は与えられた文字列をそのまま HTMLに入れてるだけだと思うんですが。wilikiはそのファイルの存在さえ チェックしてないですよ。出力されるHTML中のスタイルファイル指定は どうなっていますか?

• 失礼。エラーを吐いているのは httpd の方です。 ただ、 wiliki.cgi 中の設定と css の置き場所が矛盾無く用意できない状況です。

↓がブラウザで見たときのページソースです。
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 の探すパスが一致しない。

• apacheの設定がどうなっているのかわかりませんが，~cut-sea/public_html/以下にwiliki2.cssをおいて，:style-sheetに"/~cut-sea/wiliki2.css"じゃダメですかねぇ．あるいは，/usr/pkg/share/httpd/htdocs/以下にwiliki2.cssをおいて，:style-sheetに"/wiliki2.css"とか． - kou

• ありがとうございます。
  指示された後者の設定 /usr/pkg/share/httpd/htdocs の下に wiliki2.css を置き、 :style-sheet "/wiliki2.css" でスタイルが変わりました。
  ちなみに apache の方の設定は

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 のライブラリがどうなってんのかなと調べたら ライブラリじゃなくて組み込みで実装してる模様。（ああ、やはり）

• Shiro: そんなことないっすよ＞あとから取り込み。 もちろん、拡張されたアクセサに対するセッターは人手で追加してやる 必要がありますが、要はアクセサからセッターへのマッピングをどっかで 持っていればいいだけで。後付けするならグローバルなテーブルかなんかを 持っといて、setterはそれを見に行けばいいわけです。 Gaucheで組み込みにしているのは、その方が速いってだけです。

• 実は私が Lisp の setf についても誤解してたみたいなんですが、 後から定義したものは定義しただけでは汎変数の位置に使えないですよね。 つまりShiroさんのおっしゃる「人手で追加してやる必要がある」わけですよね。

>(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

• Shiro: 「set!されるもの」の箇所に来るのは、一般的に言えば 左辺値でなければなりません。左辺値としての評価と右辺値としての評価は 意味が異なります。Cで

  a[i] = b[i];
  

  と書いたとき、a[i]とb[i]は同じ形の式に見えますが、評価の意味が 違うわけです。 上記のmynthの例で言われているように、自動的に一般化されたセッターを 得たいならば、evalの他にeval-as-lvalueみたいな別の評価器が必要になります。 さらに、「左辺値として評価」という動作をユーザに見せるとなると、 「左辺値への参照」を一級の値として扱う必要も出てきます。 やってやれなくはないですが、evalのセマンティクスを簡単に説明できる というLispの利点を失ってまで導入するメリットは無いというのが Lisp陣営の一般的な見解でしょう。 (普通の言語では、左辺値として使える式を制限し、かつ左辺値を 陽に扱わないことでセマンティクスの混乱を避けています。 (C++の参照は微妙ですが))
• 別の見方をすれば、mynthが「アクセサ (= set!可能な場所が保持する現在の値を返す関数)」であるか「普通の関数」であるかっていうのは、 コード上で判断するのは不可能で、それを書いた人間にしかわからないことなので、 セッターも人間が設定してやるしか無いとも言えます。
  • この見方を逆転すれば、(setter foo) が設定されているfooが 「アクセサ」である、とも言えるわけです。上記の foo-with-generic-setの例では、意味上、accessorに渡せる関数は どんな関数でも良いわけでなく「アクセサ」でなければならないわけですから、 (setter accessor)が定義されている関数なら渡せる、ということになります。 これはこれで、整合性のあるセマンティクスだと思うのですが。
  • ありがとうございました。後半の方は理解できました。
    前半の方の「左辺値への参照」を一級の値として扱う必要・・・のくだりが、 私にはまだ消化不良な状態な感じです。 ちょっと頭を冷やしてから考え直してみることにします。cut-sea:2004/03/22 07:27:52 PST

• ようやく分かりました。

    (set! left-value right-value)
  

  の文脈において left-value のところに場所を指定するアクセサが来る様にする ってのは一般化参照 set! を使用するプログラマの責任ですよね。
  ただ、ここで (setter accessor) が定義されている必要があるって所に まだ疑問があったんです。
  私の（ぼんやりですが）頭の中では (setter accessor) が直接定義されているのではなく left-value を評価して行ったときに最終的に (setter primitive) が定義されている ものにたどり着ければいいのでは？と思ってました。

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

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

• リストの最後でrestメンバーを引きずり出すなら、次のような手も使えます。

    `(a . ,b)
  

  実装者にとってはこれは若干trickyです。というのも、(a . ,b) は ドット対の定義上 (a unquote b) と読まれますから。

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

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

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

• したがって、,@ が「どうしても」必要なのは、 あくまでリストの中間にspliceしたい場合ですね。 でも、私は結構そういうケースに出会います。--Shiro

• なるほど。中間にしたい場合って意味がようやくわかりました。 ってことで結局のところ一般的には、やはり必要な存在になるんですよね。 rest 引数がマクロ展開形の中のリストの末尾に来るようなのはあくまで特殊解ですし。

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

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 とかのような進行状況のメッセージもそうだし、 テレビでたま〜にあるしばらくお待ち下さいもそうだ。

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

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

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

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

イラストロジック開始

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

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

• Shiro: ども。一応Schemeの応用ってことで、 Scheme: プレフィックスを付けた名前に変更しておきます。(2004/03/06 23:20:53 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

• Shiro(2004/02/08 17:46:36 PST): 問題の本質は、make-lotがトップレベル定義に 展開されることを意図しているマクロであるってことですよね。 だから、lambdaの中では本来呼び出せないものであると。 最終的に「評価」される形がトップレベル定義にならなければいけないので、 繰り返しを行うのもマクロを使う必要があります。

  (define-macro (make-lots names)
    `(begin ,@(map (lambda (l) `(make-lot ,l)) names)))
  
  (make-lots (keyX keyY keyZ))  ;;quote不要
  

• ただし、トップレベル定義を導入するマクロの場合、それが普通の関数の ように使われると混乱を引き起こします。そこで、それとはっきりわかるように 名前を付けておくと良いでしょう。例えば、make-lotではなくdefine-lot とすれば、あんまりmapの中で使う気にならないんじゃないですか? 同様に、上の例のmake-lotsも、define-lotsの方が良いでしょう。 でないと、なんでquoteが不要なのか悩まなくちゃならない。 (マクロの悪い面が出てしまいます)

• ありがとうございます。結構この手の混乱が私自身コード書いてて多いんですよね。 確かに名前の付け方とか気を付けるだけでも違いますね。

• あと、私はどうもことあるごとに感じるのですが、 トップレベルと言うのがどういった所で効いてくるのかが はっきりイメージできてない感じです。2004/02/08 21:45:59 PST

ああ勘違い

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

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

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

• それって、Instructor's Manual じゃないですか？ 私はハードカバーの原著を持っていますが、ちゃんと絵はありますよ hidenao 2004/02/01 03:11:38 PST
  • ナイスツッコミです。(^^;
    今酒入ってるからかしばらく自分で笑いが止まらなかった。 Instructor's Manual とありますね。 あんだけ図が違ったらさぞかし文章も大きく違うだろうと 不思議には思ってたんですけどオオボケですね〜(^ワ^)cut-sea:2004/02/01 05:18:31 PST

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

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

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

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

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

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

循環小数？？？

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

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

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

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

みたいな感じ。

新たなデータオブジェクトとかクラスっぽくするわけではない。 読み込みは１０進以外の基数をカバーしたとしても同じこと。 (あ、小数になる時点で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式で解説されているわけじゃないですよね・・・。(しまったマズイ)

• Shiro(2004/01/20 07:13:02 PST): いえ、Lispに特化された内容です。 というかCommonLispべったり。前半はオブジェクトシステムが無い Lispシステムの上にCLOSのサブセットを実装することでMOPの原理と 実装が説明され、後半はCLOSのMOPの規格書になっています。 一応、前半は順を追って説明されています。 私は既にMOPがなんとなくわかった時点で読んでたので、どっちかというと 前半はざっと眺めただけで、規格書の方をリファレンス的に使っていますが。 でも、エッセンスはTinyCLOSに含まれていると思いますよ。
• そうなんですか。 私はてっきり特定の言語にあまり依存してないオブジェクト指向の実装モデル のようなもんだと思ってました。 CLOSとMOPの関係もあんまり良く分ってないんで全く漠然とした思い込みでしたが。
• 私にとっては前半がなかなか楽しみな内容になりそうで期待大ですね。

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

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

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

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

• Shiro: Schemeの数値リテラルは効率良く書こうと思うと面倒ですね。 文法的にはregular grammerの範囲に収まるので決して難しくはないのですが、 サボろうとすると落し穴にはまったりします。 →Scheme:数値リテラル

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> 

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

• あ、 procedure もまだ実装してなかった。しまったすっかり忘却。

まずは目の前の課題で有理数ってか分数をどうしたろかってことで、 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

• Shiro: 素因数分解はいらないでしょう。gcdがわかればよいので。 大抵はmodulo数回ってところじゃないですか。2004/01/08 13:30:48 PST

• あーそでした、互除で済むんだ。何をトボケてんだろ。cut-sea:2004/01/08 14:13:43 PST

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

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

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

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

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

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

• Shiro (2003/10/31 22:46:37 PST): 私はTAOCPをちゃんと「読み通す」根性は無くて、 リファレンス的に使っています。あと、適当に開いたところに出てきた 面白そうなアルゴリズムをコーディングして確かめたりとか。

• う〜む、単にパラパラってめくってこの辺にこんなことが書かれてるってのが 即断出来ないんで・・・cut-sea:2003/11/01 03:56:49 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

• Shiro: それは管理用の秘密ページです。「最近の更新」の情報を 保持しています。名前としては" %recent-changes"と 先頭にスペースが入っているので、wikiのページとしては 参照することができない…はずなんですが、見えちゃいます?
• Shiro: うわぁぁほんとだ。確認しました。 こりゃバグです。手元でチェックしてた時に一覧ページを見なかったんだ… 面目ない。WiLiKi:Bugsの方にパッチを上げました。 （WiLiKiのバグではなく、Gaucheのバグですが…）

• ちなみにこの patch で WiLiKi を立ち上げて最初にトップページをつつくと ちゃんと検索結果が出て来るようになりました。 WiLiKi の最初の状態を知らなかったので、 Error がでるのが普通なのかと思っちゃってました。 patch をあてる前は、とりあえずトップページにトップページへの参照を含む コンテンツを作ると検索結果を表示しだすので、そういうもんかと。 これも合わせて直ってますね。cut-sea:2003/10/25 18:34:34 PDT

言語の機能とOSの機能

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

• shelarcy: 既に来年発売の新版(Vol.1 to 7)の予約を受け付けているようですので、できるだけ不要な在庫を持たないようにするために既に海外にしか置いていないのかもしれませんね。
  • えっ。。。。もしかしてまた半端な時期に買ってしまったのだろうか。(+_+)...cut-sea:2003/10/17 22:10:55 PDT

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

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

• Shiro(2003/10/17 15:23:41 PDT): 普通のunixプログラムと同じです。termios(3)参照。 Gaucheからは、gauche.termiosモジュールを通して使えます。
  • あっと、ありがとうございます。 普通の unix プログラムと一緒ってのがちょっと分からないのですが、C ならば確かに termios ですかね。

いくつかの(全部かどうかは知らないですが)スクリプト言語では 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

• Shiro (2003/10/17 20:52:05 PDT): まず端末モードの操作はOSが提供するもので、 基本的には言語の機能ではないですよね。 UnixではOS機能のコールがCのAPIで指定されているので、 Cからだとたまたま直接使えますが、C言語の機能というわけではなく、 他の言語でもそのAPIへのバインディングを通して 使うというのが正当な方法だと思います。 Gaucheではバインディングライブラリを提供していますが、多くのCommonLispや いくつかのSchemeではFFIが使えるでしょう。 systemは手軽ですが、共通仕様を定めるのは難しいです。 POSIXでは戻り値も実装依存になっているので、 コマンドが成功したか失敗したかさえ、ポータブルな方法では知ることができません。 Schemeは特に、そういうプラットフォーム依存な部分は言語仕様には入れない ようにしているのだと思います。

• なるほど、OS の機能なのであたりのくだりはなんとなく、色々思いをめぐらして予想し始めていたので納得です。 おそらく RnRS に入って来るということも考えにくいですね。 FFI という term を頂けたので、そちらをきっかけに調べてみるとします。cut-sea:2003/10/17 22:08:42 PDT

• 最初 FFI で引っかけたときファイナルファンタジーばっか出て来たときは汗が出た。(^ワ^;)ハハハ

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

魅惑のλTシャツ

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

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

• Shiro: bignumの基本はとても古典的な問題です。 (8bit CPUの頃に苦労して複数ワード演算をやっていたのが思い出されます)。 私は、あのThe Art of Computer Programmingをずいぶん参考にしました。 2巻(4章)のMulti-precision arithmeticのところ。 なお、速いアルゴリズムはどんどん出てきていますが、SCMのAubrey Jafferは 「実用上、ほとんどのbignum演算は数ワード以内のものである」という統計を 出しています。

• だいぶ以前に現物を見掛けたときに買おうかどうしようか悩んだんですよね。 たしか就職前に実家に一旦帰った春休みのことだったかな。 今回の件もそうだけど、なんだかんだ言って結局いずれは必要になりそうなんで 今日会社帰りに書店に寄って注文してきちゃいました。 とりあえず、Vol1-3 までのセットパックになってたやつを会社から amazonで検索して見付けたんで。 国内になければ2〜3ヵ月かかるっていわれましたけど。。。cut-sea:2003/09/17 05:08:39 PDT

継続についての文書(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 に渡す。

今、我々はこのような手続きをどう呼び出せば良いのだろうか ?
(継続形式の使用が、このプロジェクトの２番目の部分になる評価器を、
その内部に覆い隠すかどうかには無関係であることに注意せよ)
そう、我々は 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

• これは、ふつうに int を malloc すると4バイト境界になるような。 つまり、下位２ビットは必ず 00 ということでは -- nobsun
  • あ、そうか。。。cut-sea:2003/06/21 21:39:48 PDT

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

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

6.18.6 手続き的ポート

手続き的ポートの潜在的な機能は非常に柔軟だが、後述の各１つづつを除いて今のところは 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 を伴って呼び出される。

• こんなんだろうか？う〜ん、どうも手続き的ポートってやつの特徴がわからない。
  • (高階)手続としてのポ−トてな感じでしょうか -- nobsun

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

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

で、試してみる。 ⇒Ｃコード及び実行確認は削除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

• Shiro: 向こうにも書きましたが、メモリアロケータはアロケート時のサイズ をもとにメモリを管理しているので、その心配はないです。

週末だし、ちょいと酒飲んでますけど、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

• ScmObjは単なるポインタなので、共用体にするとしたらそのポイントする先ですね。 Gaucheではキャストで対応しています。 共用体で宣言する方が行儀が良いのでしょうが、後から追加されるユーザ定義の オブジェクトなんかはキャストで対応するしかないので、 それなら最初から共用体なんていらないかなと。 SCMやGuileのように、ユーザ定義オブジェクトは一段間接参照することにすれば 共用体でいけるんですが、それはやりたくなかったのです。--Shiro
• あ〜なるほど、ポインタならどんな構造体でもサイズは int だからキャストがきくし、 しかも新しいデータ型の追加に対して ScmObj については変えなくてすむか。（このメリットが思い浮かばなかったです。。。） SICP でもデータ抽象のところで同様の話がありましたね。 だから各データ型を Class として作っておいて、全部キャストで (ScmObj *) にはめ込んでる（というか指させている）のか。 各クラスのメンバへのアクセスは ScmObj の klass が期待しているデータ型のクラスがさされているか（割りつけられているか）を 確認してから、そのクラスのメンバへアクセスするような関数マクロがバシバシと書かれていると。cut-sea

• 以降もし追記する場合には GHG の Basic Types の ScmClass のところへ移行。許可頂き同文転記した。 cut-sea:2003/06/06 17:30:37 PDT

• むむむ、分かったつもりで簡単に書いたけど、実装するとなるとやっぱり複雑。 ただ、方向は見えたからそのつもりで読めばいいんだろうけど。cut-sea
• ⇒後日Ｃコードで試したもの（実行例含む）は削除2004/01/20 23:20:18 PST

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