Scheme

継続を伴った引数つきgoto

タイトルの実装方法が分からずに、ずっと止まってる。処理系のソースを読めば分かると思うけど、なんか悔しいので、自分で試行錯誤して作りたい。 まず「継続を伴った」に関して。継続渡し形式なんてものを以前に考えたことがある。それは「次に何をすべきか…

環境と継続

現在のsacallopでは、関数適用を次のような(うさん臭い)方法・手順で評価している。 先頭要素のlambda式の評価でクロージャを生成する時、不完全な環境フレーム(名前だけで、値がまだ対応付けられていない)を作って、クロージャに保持させる*1。 引数を…

VMだった

昨晩、Gaucheのソースを読み始めてすぐ挫折したけど、それでもすぐ分かったことがある。スタックが溢れちゃうことについて。要はスタックごとこしらえれば良いってこと。僕はド素人なので、スタックは与えられるものだという先入観があった。スタックが溢れ…

chibi-scheme

アドバイスいただいた。 @yagiey_tw まずは chibi-scheme あたりの小さい処理系を参考にする方が良いかも http://twitter.com/SaitoAtsushi/statuses/16518986703310849 GitHub - ashinn/chibi-scheme: Official chibi-scheme repositoryからソースダウンロ…

ひらメソッド

Schemeプログラミングもろくにできないくせに、Schemeを作りたくて仕方がない。ってことでGaucheのソースコードをダウンロードして読み始めたけど、すぐ途方に暮れた。そんなことをツイートしてたらこんな返信を頂いた。 @yagiey_tw おせっかいします。http:…

環境

環境をどう実装したらいいのか考えていたら、(R5RSでは)各実装に任せられているそうな。 R5RSのevalは、第二引数に「環境指定子(environment specifier)」を取ると定義されている。 (eval form environment-specifier) しかし、環境指定子の具体的な実装は…

動的スコープ

ふと思いついたので、仕事中にメモメモ。 emacs lispで、 動的スコープである (equal (lambda (n) n) (quote (lambda (n) n))) の評価結果がtになる はとても関係があるように思える。 lambda式を評価したら単なるリスト → 環境フレームを作らない → 環境フ…

末尾呼び出しの最適化

末尾呼び出しの最適化に関して全然理解できてない。 「手続き呼び出しをジャンプに最適化」って言われるけど、Schemeではもともと「手続き呼び出しは継続を伴った引数付きgoto」(Gauche本6ページ)なので、最適化というか当たり前のことをやってるだけのよ…

2の1000乗

28日にあった第二回YMPAミーティングで、2の1000乗の計算について話しが出た。長整数でもオーバーフローしてしまうので求められなかったという声が聞こえたので、Gaucheでやってみようと思った。 (define pow (lambda (x n) (if (= n 0) 1 (* x (pow x (- n …

演習問題

25ページで止まっとる。全然読めてないな。今のところプログラムの勉強というか英語の長文読解のような感じ。とりあえず、演習問題の回答でも書いとこう。 Exercise 1.1 次の式を順にインタプリタで評価する場合、評価結果がどうなるかしらべなさい。 gosh> …

コルーチン3(コルーチンから脱出)

プログラミングGaucheのpp298-303。前回のコルーチンによるREPLは(exit)を与えてGaucheのインタプリタを終わらせるまで無限に繰り返していたけど、今回はコルーチンから脱出してGaucheのREPLのトップレベルに戻ってくるように修正するらしい。そのために定義…

コルーチン2(call/ccでREPL)

プログラミングGaucheのpp296-298。今回はコルーチンでREPLを実装する。もちろんread、eval、printの各処理はGaucheに丸投げだけどな!それは実装とは言わないッ! 実行結果がこんな感じになるように、3つのコルーチンreader、evaluator、printerを作成する…

call/ccとdefine

前回書いたコルーチン定義用マクロdefine-coroutineの中に、以下のようなコードがあった。 (define routine (lambda () (call/cc (lambda (return) (define yield (lambda () (call/cc (lambda (cont) (enqueue! *tasks* cont) (return))))) body ...)) ((de…

コルーチン

プログラミングGaucheのpp.294-296の「コルーチン」の前半。 call/ccでコルーチンまで実現できるらしい。ってことで、コルーチンを実現するための構文define-coroutineの定義を写経。 ;; キューの機能を使うから (use util.queue) ;; コルーチン再開するとき…

簡易な例外機構

プログラミングGaucheのpp.292-293。他の主要な言語でいうところの例外みたいな仕組みすらcall/ccで実現可能らしい。 そういえば組込みのguardもcall/ccで実装されていると聞いたことがあるな。 call/ccどんだけー。 目標とするクライアントコードは次のとお…

break/next名前付きfor-each

他の主要な手続き型言語でいうところのbreakやcontinueの仕組みを、Schemeの組込みのfor-eachに追加してやろう、ということらしい。 つまり、次のようなことができるようにしたい。 gosh> (for-each-ext return next (lambda (x) (cond ((odd? x) (next #t))…

大域脱出

call/ccを利用した大域脱出の例。今までcall/ccでウダウダ考えていたのでさすがに挙動の理解は簡単。 ただし、継続と絡めて説明しろと言われても無理。そういう意味ではcall/ccは全く理解できていない。指定したラベルを含むS式から脱出するマクロblockを定…

call/cc使ってみる4

前回(id:yagiey:20100424:1272115876)の続きっぽいけど... まず、コメントを受けて、 (and (begin (display 'a) 10) (call/cc (lambda (c) (begin (set! cont c) 10)))) の構文andはifへ展開できるので (if (begin (display 'a) 10) (call/cc (lambda (c) …

よくわからん

call/ccの中で継続を実行すれば、returnみたいな使い方ができるのは分かった。 ただ、捕捉した継続をcall/ccの外に持ち出して後で実行する場合の挙動が理解できない。 もういいや、いい加減プログラミングGauche再開するか。

call/cc使ってみる3

call/cc 入門 (Coroutine with call/cc) - MAYAHの前半を読んでみた。 演習問題みたいなのがあったので、やってみた。 gosh> (define cont #f) cont gosh> (and (call/cc (lambda (c) (begin (set! cont c) 10))) (begin (display 'a) 10)) a10 gosh> (cont …

call/cc使ってみる2

前回はcall/ccの引数の引数(つまり継続)でfを束縛して、そのあとfを実行してみた。 実行した結果を一見すると、fは(lambda (a) (inc a))のような手続きに思えるけど、mapを使ったときにちょっと違った。 今回はfで束縛せずにcall/ccの中で継続を実行してみ…

call/cc使ってみる

call/ccを実行すると、その時点での継続を捕まえられるらしい。 (call/cc (lambda (cont) body)) ってすると、継続がcontを束縛するらしい。 call/ccの戻り値はbodyだけど、bodyの中でcontが実行された場合はcontの引数がそのまま戻り値になるらしい。 cont…

call/cc理解不能

19.4のcall/cc、全くわからん。何もかもが分からん。 「call/ccで継続を取得できるよ」って言ってるだけのような気がして、 なぜあのコードでfind-foldが正しく動くのか call/ccで取得した継続って具体的に何なのか なぜあそこでcall/ccするのか などなど、…

さらに継続を渡して

find-foldからfind-fold2にすることで、procを継続渡し方式に変更できた。 だけど、find-fold2自身は(null? lis)が真となるときに、依然として「seed(=戻り値)を返却する」というCall-Return方式になっている。 これを継続渡し方式に修正してみよう、との…

継続渡し形式

find-foldからfind-fold2への書き換えでいきなりつまずいてたけど、やっと理解できてきたかも。 指定した条件を満たす要素だけfoldするfind-foldは、素直に書くと以下のようになる。 (define find-fold (lambda (pred? proc seed lis) (cond ((null? lis) se…

継続渡しで実行を制御する

find-foldで済むものを、なぜ手間をかけてfind-fold2にするのか。 それは外から与えられるproc/contを少しいじるだけで、find-fold2の実行を制御できるからだ、と。 ということで、コード例をば。次のようなnextとbreakとadd/breakを定義して、 (define next…

マクロ展開に対する先入観

プログラマがコード中に書いたマクロ マクロ展開によって出現するマクロ すべてが展開された後に評価されるもんだという先入観があった。 だけど、id:yagiey:20100223:1266942998あたりからその先入観が疑わしく感じ始めた。 例えば次のような場合 gosh> (de…

新たな変数名の作成

id:yagiey:20100305:1267761841にトラバもらった。id:trotr:20100308:1268043643 引数を加工することが必要っぽいので、objectを書き直してみた。 今度はちゃんとget-○○○って名前にした。 (define-macro (object args . methods) `(lambda ,args (lambda (mn…

使い捨てのシンボル

適当なシンボルを生成したいときは、シンボルを生成してくれる手続きgensymを使えばいい。 gosh> (gensym) #:G1 とまあ、こんな感じ。 このgensymと伝統的なマクロを使って、id:yagiey:20100127:1264595558で定義したmy-orを書き直してみると (define-macro …

objectマクロを非R5RSマクロで

今回は勝手にシンボルをでっちあげて、新しい名前を作ってみる。 271ページの 例えば構造体を定義するマクロdefine-structを定義することを考えます。fileという構造体を定義し、それがnameというスロットを持つ場合、自動的にfile-nameというスロットアクセ…