`(Hello ,world)

ツッコミ、添削大歓迎です。いろいろ教えてください。

2009-03-31

ドメイン取得したいんだけど

トップレベルドメインに .cc という、オーストラリア領ココス島地図)の国別コードがあるそうで。なのでcallという名前で取れば call.cc になる!これはいい!

けど残念ながら業者に確保されてるっぽい。ページのBuyというところから辿って行ったらどうやら$60くらいで買えるぽい。でも怖いからやらない。誰か試してみて!

  • call-with.ccもだめか…
  • call-with-.ccならいけるか!?

PAIP22章 Schemeインタプリタ

Paradigms of Artificial Intelligence Programming の22章にCommon LispでのSchemeインタプリタの実装がある。22.1章で最小限のスペシャルフォームだけのインタプリタを実装して、22.2章でマクロを追加。

22.3章で「いままでのは末尾呼び出し最適化をサポートしてないからSchemeと呼べない」といってGOを使うように変更するんだけど、これが辛い。それまでのinterpでもbegin以外は末尾でinterpを呼び出してるからいいと思うんだけど。traceするとネストが深くなるのは末尾呼び出し最適化されててもちゃんと表示するためじゃなかったっけ。

CLは仕様で末尾呼び出しの最適化を保証してるわけじゃないから念のためということかな。「『構造化プログラミング』ではgoto文は有害だ、というけどこのケースでは下位レベルを効率的に実装するために必要だ」といってるけど、それにしても辛い。

3impの実装だと代入が発生する変数はbox化されるからこういう書き方すると逆に遅くなると思うんだ。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090331

2009-03-29

beginをマクロから文法に変更

今までbeginは空のラムダ関数に変更するマクロ (begin a b c) => (lambda () a b c) で実装してたんだけど、lambda 式内の internal-define を実装するとbegin内部でdefineしたものが外部から見れなくなってしまうので、文法として追加するように変更。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090329

2009-03-25

1.9 ヒープ確保 (3) ベクター、文字列

  • vectorstringのテストも通るように関数追加
  • これで一応 Backend to Frontend の範囲は終了。続きは An Incremental Approach に進む

1.9 ヒープ確保 (2) ペア

  • 1.9のテストでbeginが使われている。これまでどおりemit-exprに追加してってもいいんだけど、煩雑になっていくのでdefine-special-formみたいのを追加しよう。と思って作業し始めたが、他の一般の関数を定義するdefine-primitiveでも評価された引数が渡されるわけじゃなくて元の字面が渡ってくるので、beginでもそのまま使える。
  • でそうすると末尾か末尾じゃないかで関数を2つ用意するのが煩雑になるので関数への引数として渡すように変更。
  • あと、beginは任意長の引数を受け取りたいのだけど、define-syntaxでrestパラメータを受け取るマクロの定義の仕方がわからなかったので、define-macroで書き換え。
  • letの本体に複文が使われているので、対応
  • ペア関係の関数(cons, car, cdr, set-car!, set-cdr!, pair?)は実装、ベクターと文字列は今後
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090325

2009-03-22

1.9 ヒープ確保

  • ペアやクロージャやシンボルや文字列はヒープに確保する
  • タグビットで区別
  • ペアの要素にアクセスする際に、pair-tag分引いた位置にアクセスすれば望みの要素が得られる
    • 目から鱗。ヒープを指す値のタグビットは0じゃないと面倒なことになると思い込んでいた。
  • テストでbeginを使ってる

1.8 末尾呼び出しの最適化による繰り返し

  • 末尾かどうか
    • プロシジャの本体は末尾
    • let式が末尾にあるなら、letの本体は末尾
    • 条件式(if test conseq altern)が末尾にあるなら、conseqとalternも末尾
    • 他の式は末尾じゃない
  • 末尾がプロシジャ呼び出しの場合、フレームを「シフト」させ、プロシジャをコールではなくジャンプにできる
    • 3impのVMで同じことをしていたけど、アセンブラレベルでこれをやってしまうとは目から鱗
    • この操作はC言語レベルではできないよな
    • gccが自動的にやってくれればいいんだけど、メモリコピーのペナルティと引換だからな
  • 後はテストを通せという、投げっぱなしジャーマン(先生ひどい…)
  • 二重再帰による偶奇判定5000000できた!末尾呼び出し最適化すごい!
  • Exercise 2 は、末尾呼び出し時にローカル変数領域の上の領域に引数を積んでいって後でシフトするんじゃなく、使われないローカル変数領域に直接書き込む、とかいうことかなぁ?難しいなぁ。

1.7 プロシジャ

  • letrec で関数定義して、呼び出せるようにする
  • testsがprocedureと関係ない、binary primitivesになっている
  • tests-1.8の後半#!eofの後にあるproceduresのテストを試してみる
  • 関数呼び出しが(app func args ...)の形じゃなくて(func args ...)
    • でもdeeply nested proceduresのテストの方はappがついてる
  • emit-lambda は、最後に"ret"を出力しないと関数呼び出しから戻れないんじゃ?
  • emit-app中のemit-argumentsで、引数の計算結果をsiに格納してない
  • emit-lambda中のsiが-wordsizeから始めているが、0からでいい?
    • どうやらsiの値が、次に使うスペースを指してるぽい(- wordsizeスタート)
  • $fxzero? -> fxzero?
  • $fxsub1 -> fxsub1
  • deeply nested procedures で Segmentation fault
    • 1.5 Binary Primitives でスタックを導入したときにスタックサイズを16Kx4しか取ってなかったのに、10000回とか5000000回とか再帰させてる
    • これは次の章の末尾呼び出しの最適化のチェック用か

関数が使えるようになったのでフィボナッチのテストができる:

[(letrec ((fib
           (lambda (n)
             (if (fx< n 2)
                 n
                 (fx+ (fib (fx- n 1))
                      (fib (fx- n 2)))))))
   (fib 35)) => "9227465\n"]
$ time ./stst.exe 
9227465

real	0m0.426s
user	0m0.424s
sys		0m0.000s

速い!

出力されたアセンブリコード:

    .text
    .global scheme_entry
    .type scheme_entry, @function
scheme_entry:
    movl %esp, %ecx
    movl 4(%esp), %esp
    call L_scheme_entry
    movl %ecx, %esp
    ret
    .text
    .global fib
    .type fib, @function
fib:
    movl -4(%esp), %eax
    cmpl $8, %eax
    jge L_0
    movl -4(%esp), %eax
    jmp L_1
L_0:
    movl -4(%esp), %eax
    subl $4, %eax
    movl %eax, -12(%esp)
    subl $4, %esp
    call fib
    addl $4, %esp
    movl %eax, -8(%esp)
    movl -4(%esp), %eax
    subl $8, %eax
    movl %eax, -16(%esp)
    subl $8, %esp
    call fib
    addl $8, %esp
    addl -8(%esp), %eax
L_1:
    ret
L_scheme_entry:
    movl $140, %eax
    movl %eax, -8(%esp)
    call fib
    ret

Cで書いてgcc -O2 --omit-frame-pointerで出したものが 0.233s なので約1.8倍。

1.6 ローカル変数

  • let式でローカル変数導入
  • 多重になっても大丈夫
  • let* はメンドイのでパス
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090322

2009-03-20

1.5 二項演算子

  • わざわざ自分でメモリ確保して、Cで使ってるスタックとは別領域を使うのか
  • espをいじらずにオフセットを自分で管理
  • fx+ の定義の中で、sc は si の間違い?
  • emit-expr で渡ってくるsiはスタックの底だから、自分が使うテンポラリ領域は(- si wordsize)で、左右の値に渡すsiはそれぞれ(- si wordsize)、(- si (* 2 wordsize))じゃないか?
(define-primitive (fx+ si arg1 arg2)
                  (emit-expr (- si wordsize) arg1)
                  (emit "    movl %eax, ~s(%esp)" (- si wordsize))
                  (emit-expr (- si (* 2 wordsize)) arg2)
                  (emit "    addl ~s(%esp), %eax" (- si wordsize)))
  • 数値のタグビットが00なので、そのまま加減算できるのは楽でいい
  • 以前$つきで出てきたfxlognotが、1.5のテストでは$なし…
  • 書き換えなきゃいけない箇所多すぎ…

1.4 条件式

  • ラベルを作って分岐
  • Exercise 2: and, orを追加しろ
    • よくあるLispマクロでifに展開する方式だと、andは素直に書けるけどorは値を2度評価しないようにするためにletで値を変数に入れる必要があるけど、アセンブラに落とす場合はレジスタに入ってるのでどちらも同じように書ける。便利。
  • Exercise 3: if の条件式に (fxzero? 0) とか使うといったん #t か #f を得た後にそれが #f か判定するのが無駄。なんとかしろ。
    • primitive関数の登録を、値を返す関数と述語を返す関数で分ける。述語を返す関数は真の判定までして、条件式として使う場合はフラグで直接分岐、値として取り出す場合はseteで#tか#fに戻すようにする。
    • 条件式にandやorを使った場合に対応できてない。値として使う場合と条件式として使う場合の2種類用意すればいけるけど、メンドイので後回し。

「Compilers: Backend to Frontend and Back to Front Again」を読んでみる

Compilers: Backend to Frontend and Back to Front Again

cranebirdさんのブログも参考にしつつ。cranebirdさんはllvm用に吐き出してるけど、オリジナルどおりx86で。

An Incremental Approach to Compiler Constructionも内容的にはほとんど同じ?どちらも入門用とかステップバイステップとかうたってるわりにはかなりハードな内容。Incremental~に比べるとこちらのほうがまだ読みやすい気がする。

tests-driver.scmを動かす
  • テスト用パッケージのtests-driver.scmGaucheで動かすのに躓く
    • ここは Scheme Compiler の勉強(0) - cranebirdの日記を見れば解決
    • それでも、tests-driver.scmには同じ関数の定義が2つあるもの(test-with-string-output, run-compile, execute, get-string)や、どこからも使われてない関数(runtime-file, input-filter, build-program, show-compiler-output)があって気持ち悪い
  • Cygwinユーザなので、実行ファイル名に勝手に「.exe」がついてしまうのでそれ用の対応
1.1 整数
  • 論文中のソースを写経
    • とかいって本当にそのまま写してしまうと(error ---)とかあるので、そういうところは適宜いいように変更していかないとだめ
  • アセンブラとの名前のルールが違うのか、「scheme_entry」だとC側から呼べないので、前にアンダーバーをつけて「_scheme_entry」に変更する
  • 宣言が違うのか、.typeは「.def _scheme_entry; .scl 2; .type 32; .endef」にする
1.2 即値
  • tests-driver.scm でランタイム用に使うCのソースファイル名がruntime.c決め打ちになっているが、それだと1.1のものとは共用できない。なのでtests-driver.scmを修正してtest-allにランタイムのCソースファイル名を与えるように変更
  • immediate-repの中身がfixnum?しか書いてなくてあとは自分で補えという。かなりストイックだな。ランタイムのほうもprint_ptrがほとんど書いてない
1.3 単項プリミティブ
  • Gaucheにputprop, getpropがない。ハッシュテーブルで代用
  • define-primitive の define-syntax はそのままで動いた
  • 論文中に出てくるのは「fxadd1」だけど、テストで使われてる関数名は「$fxadd1」とか、統一されてない
  • ほとんどの関数が省略されていてヒントすら書かれてない。x86のアセンブラもよく知らないもんだから、かなり辛い。わからないものはCでテストコードを書いて、「gcc -S --omit-frame-pointer test.c」でアセンブリコードを吐き出して参考にすべし
  • 実行時にエラーを出す方法がわかってないので、$fxlognot(整数のビット反転)で整数かどうか判定してない

成果物はhttp://svn.coderepos.org/share/lang/scheme/backend-to-frontendへ。かなりハードな内容だけど、x86アセンブラとかやったことなくてもこんなに簡単に生成できるんだー、というのが結構楽しい。

cranebirdcranebird2009/03/21 00:02こんにちは。Abdulaziz Ghuloum さんの文書の楽しさ(と不満と)を共有できてとても嬉しいです。2つの文書はほとんど同じですが、どちらもいろいろ不足(既に mokehehe さんが指摘されている、不整合やらtypoやら‥)してて、かなり補完が必要です。runtime.c の正解版を探しまわって見つからず苦労したので、mokehehe さんが coderepos に残されているのはとても良いと思います。
ネイティブコンパイラを少しずつ作るというアイディアはとても楽しいのに、細かいところが不足しているのが惜しいですよねぇ。

mokehehemokehehe2009/03/21 11:14cranebirdさん、ありがとうございます!論文のわからないところを参考にさせてもらってます。
内容は非常にハードですが、テストコードがついていて正しいかどうかチェックがちゃんとできるのがよいですね!

mokehehemokehehe2009/03/21 15:18Linuxだと論文のとおり、エントリのラベルは「scheme_entry」、.defは「.type scheme_entry, @function」でいけた。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090320

2009-03-18

実行時の命令書き換えを試してみる

3impのVMでフィボナッチを動かすと、そのほとんどがグローバル環境に定義されている関数を呼び出す時に行われるハッシュテーブルの参照に費やされてることがわかる。C言語とかのコンパイラで実行ファイルにした場合はリンク時にアドレスが解決されてるので関数呼び出しのコストは純粋にスタック操作の分だけだろうけど、スクリプト言語・VMではそうはいかないということをあらためて認識した。

で実行時にグローバル変数の参照の命令が現れたら初回は普通にハッシュテーブルから検索して場所を特定して、以降はコードを書き換えて直接、ではないんだけどハッシュ検索は省くようにしてみた。そうしたらかなり速くなった!

すると今度は関数呼び出し時に引数の数をチェックしてるのが目立つようになった。これも毎回行う必要はないので同じように書き換えて初回だけ引数のチェックをして以降はチェックしないようにしてみた。これもまあまあ速くなった。ただこれをすると、後から関数を書き換えて引数の数を変更してもチェックされないのでエラーが出ない罠。

Inspiron mini 9(Atom 1.6GHz)、Linuxでfib(35)を測った結果:

命令書き換えなし20.194s
GLOC12.106s
GLOC+PAPPLY10.225s
Gauche7.964s
Ypsilon5.673s
Mosh0.0.813.144s
gcc -O30.204s
Ruby1.9.027.251s
Perl5.8.81m32.834s
Python2.5.225.857s
Lua5.1.412.177s
Squirrel2.2.222.010s
Xtal0.9.9.016.143s

Windows、Core2で動かした時とはだいぶ結果が違うなぁ。gcc -O3を見るとスクリプトがバカらしくなってくるな…。Common Lispでも試したいんだけど、処理系の使い方がまだわからない。

フィボナッチ以外のベンチもしてみないとね。

2009-03-17

合成命令を試してみる

3impの最適化のテストなんぞ。コンパイルした結果を見ると、+などのグローバルの関数参照→APPLYで呼び出し、とか定数宣言→引数としてスタックに積む、みたいなパターンが多いのでその辺をまとめたらステップ数も減るし効果あるのかどうか試してみる。

コンパイルして吐き出されたS式をGauchematchを使ってこれこれのパターンだったらこれこれに置き換える、という単純なもの。命令を置き換えるときに新しいリストに置き換えてしまうと循環参照などが保てなくなってしまうので破壊的操作で。

(use util.match) 

(define-macro (replace-rule code . ls)
  `(match ,code
          ,@(map (lambda (e)
                   `((,@(car e) . %rest) (values ,(caddr e) %rest)))
                 ls)
          (else (values #f code))))


;;;; 置き換えルール
(define (get-replace-rule code)
  (replace-rule code
                (('GREF f 'APPLY n) => `(GREF-APPLY ,f ,n))
                (('GREF f 'SHIFT m 'APPLY n) => `(GREF-SHIFT-APPLY ,f ,n))
                (('SHIFT m 'APPLY n) => `(SHIFT-APPLY ,n))
                (('CONST obj 'ARG) => `(CONST-ARG ,obj))
                ))


(define optbl
  '((HALT ())
    (LREF (n . $x))
    (FREF (n . $x))
    (GREF (sym . $x))
    (UNBOX $x)
    (CONST (obj . $x))
    (CLOSE (argnum n $body . $x))
    (BOX (n . $x))
    (TEST ($then . $else))
    (LSET (n . $x))
    (FSET (n . $x))
    (GSET (sym . $x))
    (CONTI (tail$ . $x))
    (NUATE (stack . $x))
    (FRAME ($x . $ret))
    (ARG $x)
    (SHIFT (n . $x))
    (APPLY (argnum))
    (RET ())
    (EXPAND (argnum . $x))
    (SHRINK (n . $x))
    ))

(define *h* (make-hash-table))

(dolist (e optbl)
  (let ((sym (car e))
        (args (cadr e)))
    (hash-table-put! *h* sym args)))

(define (next-ops code)
  (define (op? sym)
    (eq? (string-ref (symbol->string sym) 0)
         #\$))
  (define (check sym x f)
    (if (op? sym)
        (f x)
      (f #f)))
  (define (scons x xs)
    (if x (cons x xs) xs))
  
  (let* ((op (car code))
         (e (and (hash-table-exists? *h* op)
                 (hash-table-get *h* op))))
    (if e
        (reverse!
         (let loop ((p e)
                    (q (cdr code))
                    (acc '()))
           (cond ((pair? p)
                  (check (car p) (car q)
                         (lambda (x) (loop (cdr p) (cdr q) (scons x acc)))))
                 ((null? p) acc)
                 (else
                  (check p q
                         (lambda (x) (scons x acc)))))))
      '())))

(define (replace pair newpair)
  (set-car! pair (car newpair))
  (set-cdr! pair (cdr newpair)))

(define (optimize! code)
  (when (not (null? code))
    (receive (rep rest) (get-replace-rule code)
             (if rep
                 (replace code (append rep (optimize! rest)))
               (begin
                 (dolist (x (next-ops code))
                   (optimize! x))))))
  code)

(define (main args)
  (until (read) eof-object? => code
    (optimize! code)
    (write/ss code)
    (newline)))

で試した結果…あまり効果なかったので(1分30秒→1分28秒とか)、こういう最適化はまだ後回しでいいかな、という感じ。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090317

2009-03-15

R5RSと6のライブラリが全然違う

Gaucheで動くソースをYpsilonでも動くかどうか試してみよう、と思ったらいろいろひっかかる。まず use とか require とか load がない。まあシステム寄りのものだからそうなのかな、とあきらめもつく。

でそのへんは無視して、肝心要のmake-hash-tableがない。これには非常に困った。それがR5RSで標準だったのかどうかは知らないのだけど、Gaucheではuseとかせずに使える(Gauche Users’ Reference: Top)。SRFI-69にも書いてある(SRFI 69: Basic hash tables)。

R6RSでハッシュを使うにはどうしたらいいのかR6RSのドキュメントを見るとの標準ライブラリ編の13章に書いてあった。いわくmake-hashtable(ハイフンがないのと、引数が必要)とかmake-eq-hashtable(内容的にはR5RSのmake-hash-tableと同じ?)とかになるらしい。

内容対して変わらないんだからそういうとこわざわざ変えるなよ、と絶望的な気持ちになった。SRFIはR5RSと6では別物なんだろうか。

俺の中でSchemeはうさんくさいものという認識が急速に高まっている。

yharayhara2009/03/19 17:18R5RSにはハッシュテーブルはありません。
というか、R5RSにはライブラリがほとんどありませんでした。数値とリストとvectorくらいで。
だから、R5RSと6の「ライブラリが違う」のは仕方ないことかな、と思います。
(ただSRFIのものから名前が変わった理由は分かりませんが。)

mokehehemokehehe2009/03/19 22:11せめて同じ名前にして欲しかったですね。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090315

2009-03-10

テストを書く

3imp処理系の修正をすると一見うまく動いているようだけどあるケースでは動かない、とかかなり起こってて困るのでテストを書く。Gaucheからプロセスを起動させて3impの処理系に渡した文字列を評価した結果の出力と、Gauche上でevalした時の値が等しいかどうかを確認する。テストの出力は404 Blog Not Found:「同じコード」の同じって何さ - TAPのススメで紹介されてたTAPとあわせてみた。proveの利点はまだわかってないんだけど。

(use gauche.process)
(use srfi-1)  ; for partition

(define (exec-3imp sexp)
  (let ((proc (run-process `("gosh" "3imp.scm" "-e" (write ,sexp)) :output :pipe :error :pipe)))
    (guard (exc
            (else (process-kill proc) exc))
      (if (process-wait proc #f #t)
          (read (process-output proc))
        #f))))

(define (test-suite title cases)
  (define (check subtitle sexp)
    (let ((res (exec-3imp sexp))
          (ans (eval sexp (interaction-environment))))
      (if (equal? res ans)
          `(#t ,subtitle ,res)
        `(#f ,subtitle ,res ,ans))))

  (let ((n (length cases)))
    (print #`"1..,n")
    (let ((results (map (lambda (c i)
                          (let ((subtitle (car c))
                                (sexp (cadr c)))
                            (let ((res (check subtitle sexp)))
                              (if (car res)
                                  (print #`"ok ,subtitle # ,i")
                                (begin
                                  (print #`"not ok ,subtitle # ,i")
                                  (print #`"# got:      ,(caddr res)")
                                  (print #`"# expected: ,(cadddr res)")))
                              res)))
                        cases
                        (iota n 1))))
      (receive (oks ngs) (partition car results)
               (null? ngs)))))

使うのは適当に

(test-suite 'CHECK-ALL
 '((simple-primitive-function-application
    (+ 1 2))
   (direct-lambda-application
    ((lambda (x) x) 123))
   ...))
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090310

2009-03-09

caseマクロが動かなかったのを修正

BOX

元は

(index-set! s n (box (index s n)))

とs相対でアクセスしてるけど、DIRECT-INVOKEを追加したのでCLOSE直後に呼ばれるとは限らなくなりsとfがずれてる可能性があるので、f相対に変更。

lambdaのコンパイル

元の論文だとlambda式のコンパイル時に内部で使われるフリー変数の列挙が

      (let ((free (set-intersect (find-frees bodies proper-vars)
                                 (set-union (car e)
                                            (cdr e))))

という順になってるけど、これだと列挙される並び順がlambdaの入れ子ごとに逆順になってしまう。DIRECT-INVOKE時にはフリー変数をキャプチャしなおさないので同じ並びになってないとまずい。ので

      (let ((free (set-intersect (set-union (car e)                 ; 入れ替え
                                            (cdr e))
                                 (find-frees bodies proper-vars)))  ; 入れ替え

という並び順に変更。

デバッグ大変だお。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090309

2009-03-08

生駒3imp読書会に参加

生駒読書会#3 参加者:orken, naoya_t, yuki_neko_nyan, momo_dev, 私, sano(敬称略、登録順)

なんか結構まったりとして不思議な会だった。集まるけど各自思い思いのことをするという感じで、自分としてはみんなで本を輪講するよりは全然よかった。輪講するとどうしても時間がかかってしまうので。

私は事前に4章まで一通り写経は終わってて4.7.2のDirect Function Invocation時に親フレームがあるかないかを実行時に判定するのは事実上無理なのでトップにフレームを作るようして必ずフレームが存在するように変更したのが朝までの時点。読書会ではそのスタック操作のバグを修正して一応動くようになった。それが原因ではなかったみたいだけどcall/ccを使った非決定性のプログラムも動くようになった。

で次の改善に手を出そうと思って4.7.3末尾再帰最適化は難しそうだから4.7.4クロージャのヒープ割り当て回避ができるかどうか考えた。たとえば(map (lambda (x) ...) ls)とかのラムダ式をスタック上に取りたいよなぁとか考えてたらそれまでの実装がmapが実装側言語であるGaucheのmapを呼び出していたことが判明した。applyも。mapやapplyに渡る関数は被実装側のクロージャなので確実に動かないはずなんだけどどうなってたんだろう?これらを被実装言語側で定義するよう修正。

改善は手軽に手を出せそうになかったので、ここまでの実装でメタサーキュラーができるかどうかやってみた。するとcompile関数で真っ先に必要になるrecord-case内で使われるcaseマクロで使われる名前つきletがうまく動いてないことが判明。原因を調べてたけどわからず。

そんな具合で読書会は終了。なかなか有意義な一日でした。みなさまありがとうございました。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090308

2009-03-06

3impのcall/ccでやっぱりエラーが出る

3impの4.6スタックベース最終版でcall/ccを使うとちゃんと動かない場合がある。誰か同じ現象にあってないかな、、、と思ってググると過去に自分で書いていた。さすが俺!ていうかなんでやったこと忘れてまた同じことしてるのか…。

これでよしと思ったんだけど、The 90 Minute Scheme to C compilerに出てくる非決定性のプログラム

(define fail
  (lambda () (error "no solution")))

(define in-range
  (lambda (a b)
    (call/cc
     (lambda (cont)
       (enumerate a b cont)))))

(define enumerate
  (lambda (a b cont)
    (if (> a b)
        (fail)
      (let ((save fail))
        (set! fail
              (lambda ()
                (set! fail save)
                (enumerate (+ a 1) b cont)))
        (cont a)))))

(print
 (let ((x (in-range 2 9))
       (y (in-range 2 9))
       (z (in-range 2 9)))
   (if (= (* x x)
          (+ (* y y) (* z z)))
       (list x y z)
     (fail))))

を動かそうとするとちゃんと動かない。NUATE時にスタックが壊れてるっぽいんだけどまだちゃんと確認できてない。

定数の畳み込み

S式レベルで行う奴。四則演算以外に、ifとstring-appendもやってみた。なんかこう、まどろっこしいな…。

(use srfi-1)  ; for partition, span

(define (constant-folding s)
  (if (pair? s)
      (let ((ss (map constant-folding s)))
        (case (car ss)
          ((+) (constant-folding+* + ss))
          ((*) (constant-folding* ss))
          ((-) (constant-folding-/ - + 0 ss))
          ((/) (constant-folding-/ / * 1 ss))
          ((if) (constant-folding-if ss))
          ((string-append) (constant-folding-string-append ss))
          (else ss)))
    s))

(define (constant-folding+* op s)
  (receive (consts left) (partition number? (cdr s))
    (let ((const (apply op consts)))
      (cond ((null? left) const)    ; 定数項のみ
            ((= const (op))         ; 定数が基本ケース:無視できる
             (if (single? left)
                 (car left)
               `(,(car s) ,@left)))
            (else
             `(,(car s) ,const ,@left))))))

(define (constant-folding* s)
  (let ((ss (constant-folding+* * s)))
    (cond ((and (pair? ss)
                (= (cadr ss) 0))  ; 係数が0
           0)
          (else ss))))

(define (constant-folding-/ op op2 base s)
  (receive (consts left) (partition number? (cddr s))
    (let ((const (apply op2 consts)))
      (if (number? (cadr s))
          (if (null? left)
              (op (cadr s) const)  ; 定数のみ
            `(,(car s) ,(op (cadr s) const) ,@left))
        (if (= const base)
            (if (null? left)
                (cadr s)
              `(,(car s) ,(cadr s) ,@left))
          `(,(car s) ,(cadr s) ,const ,@left))))))

(define (constant-folding-if s)
  (let ((c (cadr s))
        (th (caddr s))
        (el (cdddr s)))
    (if (or (number? c) (string? c) (boolean? c))
        (if c
            th
          `(begin ,@el))
      s)))

(define (constant-folding-string-append s)
  (let ((res
         (let loop ((s (cdr s)))
           (if (null? s)
               '()
             (receive (consts temp) (span string? s)
               (receive (noconsts left) (span (compose not string?) temp)
                 (cond ((null? consts)
                        `(,@noconst ,(loop left)))
                       ((null? noconsts)
                        (list (apply string-append consts)))
                       (else
                        `(,(apply string-append consts) ,@noconsts ,@(loop left))))))))))
    (if (single? res)
        (car res)
      `(string-append ,@res))))

(define (single? ls)
  (and (pair? ls)
       (not (null? ls))
       (null? (cdr ls))))
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090306

2009-03-04

3impの処理系にラムダ関数の直接呼出しを追加

3impの4章のスタックベースの処理系で、4.7「できそうな改善」の 2.「関数直接呼出し」を実装した。

コンパイル時:関数適用の関数がソース上で直接のlambda式だった場合*1に、まず普通の関数呼び出しと同じように引数をARGUMENTでスタックに積んでいくコードを生成。関数は普通の CLOSE→APPLY で無駄なクロージャを作って呼び出す代わりに新規に追加した DIRECT-INVOKE→lambdaの本体埋め込みというバイトコードを生成。関数本体はひとつ上の環境のローカル変数を自身の仮引数で拡張してコンパイル。本体の最後では通常 RETURN のところをこれまた新規に追加した RETURN-DIRECT というオペコードで戻るようにした。

実行時:DIRECT-INVOKE で直接呼出し用の引数をフレームのローカル変数と同様に扱えるように結合。普通のフレームと同じ形になるようにする、これによって末尾呼び出しだった場合は RETURN で普通に戻れる。RETURN-DIRECT ではスタックを操作して一時的に追加したローカル変数を取り除く。

これで let とかある程度気兼ねなく使えますわ。

  • ToDo: コンパイル時に引数の数のチェックをする、restパラメータがあった場合の処理

*1: ((lambda (params...) body...) args...) のような形

g000001g0000012009/03/05 12:173impで思い出したのですが、今週の日曜日に3impを読む「生駒読書会」があるようです。
http://www.slideshare.net/naoya_t/shibuyalisp-tt2-opening?type=presentation
の「おまけ」参照
http://atnd.org/events/350
自分は参加しませんが、mokeheheさんにぴったりかなと思いました(*'-')

mokehehemokehehe2009/03/05 21:08おお、それはすごい会ですね!参加してみようかしら。

naoya_tnaoya_t2009/03/08 00:12こんばんは、生駒読書会主催のnaoya_tです。明日はちょうどその辺りをやります。
slimy hackathon中のg000000001さん勧誘活動どうもありがとうございます。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090304

2009-03-01

shibuya.lisp#2動画とmoshのビルドと

もうニコニコ動画にアップされてる!「Shibuya.lispテクニカルトーク#2」 nkoguro さんの公開マイリスト - ニコニコ動画

その中でもhigeponさんの話は面白かった。流暢でプレゼンうまいなぁと思う。

Toy to practical interpreter Mosh internals - ニコニコ動画

速くなったというmoshを試してみたい…以前はWindowsだったから失敗したに違いない、今回はUbuntuで試してみるぜ!と思ってGoogle Code Archive - Long-term storage for Google Code Project Hosting.からsvnで最新版を落としてやってみる。./configureはできたんだけどmakeするとエラーに引っかかる。

> make
make  all-recursive
make[1]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only' に入ります
Making all in ./gc-7.1alpha3
make[2]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only/gc-7.1alpha3' に入ります
make[3]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only/gc-7.1alpha3' に入ります
depbase=`echo allchblk.lo | sed 's|[^/]*$|.deps/&|;s|\.lo$||'`;\
	/bin/bash ./libtool --tag=CC   --mode=compile gcc -DPACKAGE_NAME=\"gc\" -DPACKAGE_TARNAME=\"gc\" -DPACKAGE_VERSION=\"7.1alpha3\" -DPACKAGE_STRING=\"gc\ 7.1alpha3\" -DPACKAGE_BUGREPORT=\"Hans.Boehm@hp.com\" -DPACKAGE=\"gc\" -DVERSION=\"7.1alpha3\" -DDONT_ADD_BYTE_AT_END=1 -DLARGE_CONFIG=1 -DNO_CLOCK=1 -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DHAVE_DLFCN_H=1 -DLT_OBJDIR=\".libs/\" -DNO_EXECUTE_PERMISSION=1 -DALL_INTERIOR_POINTERS=1 -DATOMIC_UNCOLLECTABLE=1  -I./include   -fexceptions -I libatomic_ops/src -O2 -fomit-frame-pointer -DUSE_I686_PREFETCH -MT allchblk.lo -MD -MP -MF $depbase.Tpo -c -o allchblk.lo allchblk.c &&\
	mv -f $depbase.Tpo $depbase.Plo
libtool: Version mismatch error.  This is libtool 2.2.6, but the
libtool: definition of this LT_INIT comes from libtool 2.2.4.
libtool: You should recreate aclocal.m4 with macros from libtool 2.2.6
libtool: and run autoconf again.
make[3]: *** [allchblk.lo] エラー 63
make[3]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only/gc-7.1alpha3' から出ます
make[2]: *** [all-recursive] エラー 1
make[2]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only/gc-7.1alpha3' から出ます
make[1]: *** [all-recursive] エラー 1
make[1]: ディレクトリ `/home/foo/repos/mosh-scheme-read-only' から出ます
make: *** [all] エラー 2

gc-7.1alpha3で./configureしなおしてもダメだった。完全初心者になにかアドバイスを…。

YasuyukiMiuraYasuyukiMiura2009/03/02 20:57ちょうど最新版が良くない状態だったせいだと思います。
svn upしてやりなおせばきっとmakeとおります。

mokehehemokehehe2009/03/02 22:49アドバイスありがとうございます!最新版を取り直したところmake check, installも通りました。
しかし、REPLは動いてフィボナッチも計算できたんですが、スクリプトとしての動かし方が分かりません。空のファイルを食わせても
> mosh empty.scm
Condition components:
1. &assertion
2. &who: expander
3. &message: "top-level program is missing an (import ---) clause"
4. &irritants: ()

Exception:
error in raise: returned from non-continuable exception

Stack trace:
1. throw: <subr>
2. (raise c): compiler-with-library.scm:889
3. assertion-violation: <subr>
4. apply: <subr>
...
となってしまいます。

lequeleque2009/03/03 06:49R6RS Scheme ではトップレベルプログラムの先頭には import 節がないといけないからですね(R6RS Chapter 8)。
ファイルの先頭に (import (rnrs)) を追加すると動くと思います。

mokehehemokehehe2009/03/03 08:25ありがとうございます!(import (rnrs))を追加したところ動くようになりました!
R6RS...難しいものですね。

トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090301