逆襲のSICP5.51 その後2

放置していたり、忘れていたわけではないのです。
なんかうまくいかなくてのたうちまわって苦しんでいただけなのです。

まあ色々ありましたが、レジスタ計算機のC言語版ですが、一応完成しました。
が、ひどいです、我ながらひどい。
ソースを読んでみようなどという気を起こしてはいけません。
本にあったscheme版をほぼそのまんま実装しただけのはずなんですが。

ダウンロード

フィボナッチを実行するようになってます。
実行すると入力待ちになるので、10といれてください、55と表示されると思います。
20以上の数を入力するのはやめましょう。無謀です。
schemeだと解析を先に済ませて効率化していますが、あまりにも面倒そうだったので毎回解析する方式に変えてます。

いやあ、実装はしてみたものの、よく考えたらprimitiveの手続きを準備しないといけないし、schemeマシンを動かせるのか自身がなくなってきました。
まあ、こっから先はのんびりやることにします。

逆襲のSICP5.51 その後1

えー、なんといいますか、前回それなりの勢いをもって、
スタックをなんとかするぞー、とか言ったような気がしますが。
その後色々考えまして、結局のところ、どうもならんような気がしてきました。
いや、実際にはどうにかなるんでしょうけど、どうすればいいのかまったく検討がつかないといいますか。

と、いうわけで、「なんとかする」に一番近い場所を目指し、
目標を「レジスタ計算機シミュレータ」をC言語でなんとかして、その上でシコシコ写経した積極制御評価器を動かす、に変更しようかと思います。
まあ、あれならなんかそのまんま実装するだけで動きそうなような気がしてこないでもなかったりするので、頑張れそうかな、と。
この辺ある程度気が済んだらなんかのソース読んでみるなりして本当のところはどうすればいいのかとか勉強してみようかと思います。

で、例のスタックですが、VisualStudioで動かしてたりしてたんですが、どうもデフォルトのスタックサイズが小さいみたいですね。
大富豪のようにスタックサイズを割り当ててやったら、それなりに動いた感のあるところまで普通に動くようになりました。
で、ついでにVMWare上のUbuntuでもコンパイルして実行してみたらSegmentationfaultでこけたりして、久々にひざがカックンしそうなバグを見つけてみたりするなど、色々おかしなところをなおしたので、ソースとか上げなおしときます。
多分、もういじらないだろうなー。
GCとかをなんとかしたくなったらまたいじるかも。でも、どうすればいいかわかんないしなー。

ダウンロード

逆襲のSICP5.51

何も考えずににCで実装したschemeは「あっ」と言うまもなくスタックオーバーフローになってしまい、そのせいで心がポッキリ折れたわけなんですが、良く考えたら、何もCのスタックをそのまんまつかって（要は再帰させて）やる必要って実はないんですよね。
つまり自前でスタックを用意してやって、必要な情報はそこにためこんでおき、evalはそのスタックから情報をもらってきてひたすらループするような形でやればよかったんではなかろうかと。
ってなことを電車の中でうつらうつらしているときにふと気づいたんですが、これって良く考えたら、5章のレジスタ計算機ですでに通った道なわけで。
なんかいろいろと遠回りをしたような気がしますが、ちょっとこの方向で修正してみようかなと思ってます。
まあ、今は別の本を読んでるんで、ある程度区切りがついたらですけど。

またしてもやられた件について（onLisp）

いろいろあってしばらくできなかったonLisp、久々にやったらいきなりハマりました。
第24章のPrologマクロ版です。
図24.10までのソースをシコシコ打ち込んで、さあためしに動かしてみよう、と思ったらエラーがでてうごかない。
どうも

(<_ (gaunt raoul))

の"raoul"が定義されていないとか、意味のわからないことをいっているもよう。
ソース打ち間違えかな、と思って見直してみてもどこもおかしなところが見つけられずへこみました。
ひょっとしたら前に打ち込んだソースが間違っているのかもしれませんが、さすがにそこまでさかのぼる気にもなれなかったので、サンプルソースを変更することにしました。
問題点はここです（以下は全てあくまでも私の環境での話です）。

(defun rule-fn (ant con)
  (with-gensyms (val win fact binds)
    `(=lambda (,fact ,binds)
       (with-gensyms ,(vars-in (list ant con) #'simple?)
         (multiple-value-bind
           (,val ,win)
           (match ,fact
                  (list ',(car con)
                        ,@(mapcar #'form (cdr con)))　←ココ
                  ,binds)
           (if ,win
             ,(gen-query ant val)
             (fail)))))))

どうも、ruleをmatchに渡すときに、最初の単語だけクォートされて、残りはクォートされていないので、変数だと思って勝手に展開しに行っているようなエラーがでていたようです。
と、いうわけで全部クォートすりゃいいじゃん、と思ったのですが、?xとかの変数についてはすぐ上のwith-gensymsで定義されているので、これはクォートしてはいけません。
てなわけで、formを変更してみました。

(defun form (pat)
  (if (simple? pat)
    (if (and (not (var? pat)) (atom pat))　　←　ここから
      `',pat
      pat)　　　　　　　　　　　　　　　　　　　　←　ここまで
    `(cons ,(form (car pat)) ,(form (cdr pat)))))

?がついてるやつはクォートせず、それ以外は一律クォートしてみました。

（12/23　クォートした文字をいれると悲しいことになったので修正しました）

一応動きましたが、いまだに私がどこで間違ってしまったのかは不明のままです。
なんか気持ち悪いですね。

続きを読む "またしてもやられた件について（onLisp）"

久しぶりにハマった件について

カテゴリーSICPですが、onLispの話です。

継続ですよ、継続、継続でやられましたよ、というか実際にはスコープにハメられたわけですが。
実はよく知らなかったんですが、defvarするとダイナミックスコープになるそうです。で、まあonLispの方はそこを承知で、defvarせずにsetqしてレキシカルスコープのグローバル変数を作る、ってやってたんですが、ここが落とし穴。
私の使ってた処理系だと、親切にもdefvarしてない変数にsetqすると勝手にdefvarしてくれる（スペシャル変数というそうな）、というありがた迷惑（迷惑でもないが）な機能がついてまして、で、継続のサンプルコードはグローバル変数がレキシカルスコープであることを前提にしていたので想定通りの動きにならず、久々にうめきながらデバッグする羽目になりました。
でてきた、エラーメッセージわかりにくかったこともあり結構時間かかりましたね。
で、まあ問題点がスペシャル変数にあることが判明してからはおなじみGoogle先生にご登場願ってなんとか解決しました。
同じところでズバリはまってる人も結構いたみたいですね。
一応、たどりついたサンプルコードを張っておきます。こんな感じにすればレキシカルスコープになるそうです。実際サンプルコードも動いたので間違いありません。

(defmacro lexdefvar (name value)
  (let ((symbol (gensym)))
    `(progn
       (defparameter ,symbol ,value)
       (define-symbol-macro ,name ,symbol))))

(lexdefvar =cont= #'values)

と、いうか明らかに勉強する順番間違えた気がする。
こういうときに困るんですよね。

SICP問題5.51 途中経過その3 factorialが動いた

タイトルどおりです。
昨日予想したとおり、全然駄目駄目な部分はのこっていましたが、なんとか修正して、factorialが動くようになりました。
まあ、まだまだおかしいところはいっぱい残ってそうですが、もう段々これでいいや、という気になってきました。
超循環評価器とか大変そうだしな～
というわけで、今後どうするかはまだ決めてません。
個人的には大分満足しました。

ダウンロード

SICP問題5.51 途中経過その2 readをなんとかした

readをなんとかしました。
むか～し買ってちょびっと読んでみたもののわかわかめになったので死蔵していたいわゆるドラゴンブックをひっぱりだしてみたりして、あーでもないこーでもないしているうちになんとか動くようになりました。
readの本当の仕様というのはよくわからなかったので本に書いてあったこんな感じで返るみたいな記述を参考に、複雑なことは一切しない方向で、割り切った実装となっています。
当然変な文をいれたりするとろくなことにはなりません。

はまったところといえば、教科書のいうところのオブアレイというやつにlambdaやらdefineやらtagged_list?で比較するリテラルを片っ端から突っ込んでおかないとなんでもかんでも全部変数にされてしまったりするところでしょうか。オブアレイなどやるつもりなかったので、後からヒーヒー実装する羽目になりました。

それと何気に面倒なのが、

(+ (+ 1 (+ 2 3)) 4)

みたいなのをきっちりリスト（上の記述そのままのリスト）にして返さないといけないところで、ちょっと憂鬱でしたが、今までの演習で散々やった再帰使う方向でなんとなくまとまりました。
そこだけ書くとこんな感じです。

scheme_type_t scheme_read()
{
    scheme_type_t token= next_token();

    if( token.type == TYPE_PTR ) {

        return scheme_read_list( scheme_null() );

    } else if( token.type == TYPE_EMPTY ) {

        error( "Illgal input -- READ", token );
        return scheme_null();

    } else {

        return cons( token, scheme_null() );

    }
}

scheme_type_t scheme_read_list( scheme_type_t list )
{
    scheme_type_t token;

    while( 1 ) {

        token = next_token();

        if( token.type == TYPE_EMPTY ) {

            break;

        } else if( token.type == TYPE_PTR ) {

            list = append( list, cons( scheme_read_list( scheme_null() ), scheme_null() ) );

        } else {

            token = cons( token, scheme_null() );
            list = append( list, token );

        }

    }

    return list;
}

なんにせよ、上の奴が動くことは確認しました。
ちなみにfactorialとかはまだ試してないです、多分バグっているでしょうが、とりあえずreadが動いたのがうれしくて書いてしまいました。

ダウンロード

SICP問題5.51 途中経過

しばらく何も書いてませんでしたが、一応ちょこちょこ進めてました。
問題文にはさりげなく書いてある実装時支援とかで結構苦戦しましたが、一応第一歩は踏み出せたかな、と思うところまで来ましたので、一旦あげてみます。

readとか未実装ですし、手続きもまだどうなるかわからない状態なんですが、コンパイルして実行すると、(+ 49 81)の結果が出てくると思います。
変更したいときはmain関数で実行する文を一生懸命リスト化しているところがあるのでそこをちょこっと変更してください。
VisualStudio2005で作りましたが、中身はまるっきりC言語のはずです。

一応exeもいれてありますが、動かなかったらごめんなさい。
それとなにかファイルの中身を使用することで何かおきても責任はとれませんので、ご了承の上ご使用ください。

ダウンロード

本当はfactorialくらい動かしてみたいんですが、リストを手作りするのは面倒この上ないので、まずはreadをなんとかしたいなあと思ってます。
それと余裕があったらGCの方にも手を出すかも。
まあ先は長いですね。

SICP問題5.51の目標

C言語（じゃなくてもいいんだけど）で4章の超循環評価器を作って見ましょうという話なんですが、問題文は2行なのに書いてあることは結構きつそうです。
超循環評価器自体は本文に詳細に書かれているので、まあできなくもないかなという感じなんですが、基本手続きとして何気なくつかっていたあれやこれやを自分で実装する必要があります。
具体的には多分

(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
        (list 'square (lambda (x) (* x x)))
        (list '= =)
        (list '< <)
        (list '<= <=)
        (list '> >)
        (list '>= >=)
        (list '+ +)
        (list '- -)
        (list '* *)
        (list '/ /)
        (list 'apply apply)
;        (list 'map map)
        (list 'let let)
        (list 'pair? pair?)
        (list 'eq? eq?)
        (list 'length length)
        (list 'set-car! set-car!)
        (list 'set-cdr! set-cdr!)
        (list 'display display)
        (list 'newline newline)
        (list 'read read)
        (list 'number? number?)
        (list 'string? string?)
        (list 'symbol? symbol?)
        (list 'caddr caddr)
        (list 'cdadr cdadr)
        (list 'cddr cddr)
        (list 'cadr cadr)
        (list 'cdddr cdddr)
        (list 'cadddr cadddr)
        (list 'caadr caadr)
        (list 'cadadr cadadr)
        (list 'not not)
        (list 'append append)
        (list 'list list)))

これだけいると思われます。
で、何気にcarとかcdrとかlistとかやろうとすると途中でさらっとでてきた記憶領域管理の話（gcとか）やらないといけないし、いままでありがたく何も考えずにつかってきたreadもなんとかしないといけないんですよね。
だんだん暗い気分になってきました。
まあとりあえずはcarとかcdrとかをどうするかあたりから考えて見ます。

SICP私的解答パック

SICPの練習問題も残すところあと2問となりましたが、我ながら終わる気がしません。
まあここはノンビリやろうかなあと思ってます。

と、いうわけでここがちょうど良い区切りだと思われますので、私がちまちま解いてきた練習問題の解答をまとめてあげとくことにします。
当然のことながらあっている保障はどこにもありません。
注意点は中のREADMEを読んでください。

ちなみに、3章くらいまでならググれば私のよりもずっと質の高い解答がバンバンひっかかりますので、あまり使い道は無いような気がします。4章以降になると情報量がガクッとへるので、ひょっとしたら役に立つこともあるかもしれません。
配布のことでなにか問題等々お気づきの点ありましたら、こそっとコメントいただければと思います。

ダウンロード