Lisp Scheme Part22

1 名前：デフォルトの名無しさん mailto:sage [2008/05/21(水) 23:58:40 ] □過去スレ□ Part21: ttp://pc11.2ch.net/test/read.html/tech/1207300697/ Part20: ttp://pc11.2ch.net/test/read.cgi/tech/1205021786/ Part19: ttp://pc11.2ch.net/test/read.cgi/tech/1200237296/ Part18: ttp://pc11.2ch.net/test/read.cgi/tech/1186922295/ Part17: ttp://pc11.2ch.net/test/read.cgi/tech/1177065699/ Part16: ttp://pc11.2ch.net/test/read.cgi/tech/1172404795/ Part15: ttp://pc10.2ch.net/test/read.cgi/tech/1151025773/ Part14: ttp://pc8.2ch.net/test/read.cgi/tech/1132275726/ Part13: ttp://pc8.2ch.net/test/read.cgi/tech/1115901841/ Part12: ttp://pc8.2ch.net/test/read.cgi/tech/1100229366/ Part11: ttp://pc5.2ch.net/test/read.cgi/tech/1091456033/ Part10: ttp://pc5.2ch.net/test/read.cgi/tech/1075630259/ Part9: ttp://pc2.2ch.net/test/read.cgi/tech/1069594582/ Part8: ttp://pc5.2ch.net/tech/kako/1058/10582/1058263391.html Part7: ttp://pc5.2ch.net/tech/kako/1042/10421/1042167213.html Part6: ttp://pc3.2ch.net/tech/kako/1031/10315/1031560687.html Part5: ttp://pc3.2ch.net/tech/kako/1023/10230/1023091882.html Part4: ttp://pc.2ch.net/tech/kako/1016/10162/1016211619.html Part3: ttp://pc.2ch.net/tech/kako/1008/10082/1008220265.html Part2: ttp://pc.2ch.net/tech/kako/1002/10025/1002584344.html Part1: ttp://piza2.2ch.net/tech/kako/987/987169286.html 129 名前：デフォルトの名無しさん mailto:sage [2008/05/25(日) 22:39:31 ] Ｓ式を超える表現を思いついたらすげーな。 130 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 01:17:55 ] >>126 今でもマクロアセンブラレベルでしか書けないマシンもあるからあんまりいぢめんな メモリさえ許せばとりあえずlisp1.0系を導入して、強引に繋いだキーボードでテスト基盤を調査とかすることはよくあると思うんだけどどう？ 組み込みよりのちょっと大きめのプロダクト扱う会社だとテストでインタラクティブ環境作れるlispやもちっと小さいインタプリタを自前で持ってるよね？ 少なくともおいらのしってる会社で４件はあったよ（うち2件がlispだった) 131 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 01:38:56 ] 組み込み系はGCの移植・検証がめんどくさいな 132 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 01:41:26 ] そゆ用途ならForthじゃね？実績的に。 133 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 02:24:48 ] そういえば、BASICとassemblyしか知らなかった俺に、 美しいプログラミングの世界をかいま見せてくれたのがFORTHだった。 134 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 02:50:29 ] 130です >>132の言う通り残りの１件はforthでした、しかも、もっとメモリ制約の有った案件が１０件他にあってそれは全部forth系です。 ようするに若干メモリに余力無いと採用できないのは本当です 135 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 02:52:18 ] 補足 全部で1Kワードのメモリしか無いのが残りね。 最初の４件は３２Ｋワードあった 136 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 04:12:04 ] >>131 GCを極力使わない方法もある。 運用の仕方でGCレスも可能。 メモリも100KBもあれば余裕で動くんじゃないの。 組み込みつっても最近のは余裕あるでしょ。 137 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 09:28:07 ] >>135 それROMは別でしょ? 余裕でLisp動くじゃない。 138 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 09:29:11 ] Lispできついのはメモリ空間/ポインタの扱いじゃない? 組み込みだとアドレス空間の割り当てが、案件ごとに違うだろうし。 139 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 18:03:39 ] >>138 配列が使える状況であればどうとでもなる。 セグメントの話ならFORTHでも同じ事だし、 頻繁にreadするのでもない限りRAMもそれほど必要ない。 最終的に何かを制御するだけならGCも省ける場合がある。 どういうプロセッサできついのか具体的に 挙げてくれると判りやすいけど。 140 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 19:36:40 ] ポインタのサイズが16ビットだったり24ビットだったり そういえばdoubleは64ビットだから組み込み以外でも問題になるね 141 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 19:42:39 ] short型のコンスとlong型のコンスがあったりするの？ 142 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 19:43:07 ] ttp://www.forth.org/compilers.html 143 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 20:18:26 ] >>140 難しく考えすぎじゃないのか？ 組み込みでdoubleなんて使うのかね。 144 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 21:16:53 ] ニコスクリプトで pure lisp www.nicovideo.jp/watch/sm3452591 145 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 21:41:48 ] >>139 1KワードしかRAMがなければ、 組み込みシンボルオブジェクトの一部や組み込み関数の定義部は、 ROMに入れたくなるから、 > 配列が使える状況であればどうとでもなる。 は、そんな簡単にポータブルな実装にはならない。 「どうにでもなる」と言えば、どうにでもなるんだが。 146 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 21:45:09 ] ROMとRAMで空間が分かれてるタイプのプロセッサはちょっと使いにくいかもだな 147 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 21:53:50 ] >>145 お前口ばっかで全く作ったこともないだろ。 1ワードだから何だよ。それが仕事なら作るだろ。 むしろそんな環境でLispに出番があるのか疑問だが。 148 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 21:54:52 ] Kが抜けてたw まあそういう事。 149 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 22:12:36 ] 横ﾚｽｽﾏｿ。 1984年ごろのパソコンが128kぐらいだったのを考えると 最近の組み込みなんてメモリサイズが大きいという希ガス。 で、1kワードRAMって何に使うの？ 150 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 22:19:18 ] >>143 組み込み 以外 でも、と言ってる doubleのようにポインタのサイズより大きいオブジェクトは 間接参照やメモリ割り当てで遅くなるだろ？ 151 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 22:21:35 ] >>150 普通のLispの処理系一般に当てはまる問題だが、そういう一般的な話がしたいの？ 152 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 00:19:08 ] ところで、横槍を入れるときはそう言うべきなの？ 153 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 00:33:27 ] >>150 >>140の「そういえば」はどこに掛かるんだよ。酔っ払いか？ で？間接参照で遅くなるから何すか？ 154 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 05:10:09 ] >>152 特定の二人だけであまりに必死な会話を展開してるときは そう言いたくなることもある。たまに。 155 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 05:14:49 ] >>147がなんでかみついてるのかいまいち把握できん 元の書き込みも１Ｋワードのマシンじゃforthだって書いてるじゃん（っていうか他に選択肢あるのか1Kで） 156 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 07:22:55 ] だから、それが何なんですかね？forth大好きおじさん。 lispスレに何の御用ですか？ 157 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 07:48:17 ] 自分じゃ頭は良いけど性格が悪いキャラのつもりで 単に頭が悪いキャラなのは勘弁して欲しいなぁ 158 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 07:51:53 ] どちらかと言うと、気に入らない書き込みしてるのが1人に見えてしまう法則発動かと。 159 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 08:30:20 ] MindStormsで動く湯浅先生のLispってどう？ 使った人いる？ 160 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 12:07:40 ] GaucheでLittle Schemerにのってる以下の関数を実行すると、 メモリ以上に食って終わらなくなるのですが。 (define add1 　(lambda (n) 　　(+ n 1))) (define A 　(lambda (n m) 　　(cond 　　 ((zero? n) (add1 m)) 　　 ((zero? m) (A (sub1 n) 1)) 　　 (else (A (sub1 n) 　　　　　　 (A n (sub1 m))))))) 161 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 12:11:48 ] そうでしょうね 162 名前：163 mailto:sage [2008/05/27(火) 12:16:03 ] >>161 私、何か間違ってますでしょうか？ 163 名前：163 mailto:sage [2008/05/27(火) 12:34:36 ] 163 164 名前：へだま ◆7JLFh7E/wI mailto:sage [2008/05/27(火) 12:34:56 ] >>162 ttp://mathworld.wolfram.com/AckermannFunction.html このへんの記事が御参考になればよいのですが 165 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 12:42:26 ] すまそん、wikipedia.jp見てました。計算量が爆発する関数なんですね。 どうもです。 166 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 13:48:49 ] アッカーマン関数なんて懐かしいな 167 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 16:17:25 ] タイムボカンシリーズか。懐かしいよな。 168 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 17:46:00 ] >>140 Pointer(Address Reg)のサイズが 16bits って 8BitsMPU とかだよね？ メモリー空間が64Kの世界かぁ。うむむ。 169 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 18:35:29 ] >>168 たまには8086も思い出してください（個人的には嫌いだがw） 170 名前：デフォルトの名無しさん mailto:sage [2008/05/27(火) 19:02:48 ] あの変態的な「セグメントと称する物」は2度と見たくないw 171 名前：デフォルトの名無しさん [2008/05/28(水) 07:53:43 ] Windows環境でGaucheでCGIプログラミングをしようとしているのですが #!E:/Gauche/bin/gosh.exe (display "Content-Type: text/plain;\n\nHello, Gauche!\n") と書くとInternalServerErrorが出ます。 goshのパス自体はこれで正しいのですが、何かやり方を間違っている所があるでしょうか？ 初心者質問ですいません。 172 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 08:05:14 ] >>171 まずHTTPサーバのログを確認。 つぎにコマンドプロンプトで C:\foo> E:\Gauche\bin\gosh.exe bar.cgi とかやってみる。これで動くなら設定が悪い。 173 名前：デフォルトの名無しさん [2008/05/28(水) 10:41:42 ] サーバーのログ見たら Premature end of script headers: mb.cgi *** ERROR: cannot find file "./D:/ws/hp/scheme/mb.cgi" to load との事。 プログラムのあるフォルダで、コマンドプロンプトで動作させたときはきちんと動きますが gosh "プログラムの絶対パス" とすると同じエラーが返るのでこれが原因のようです。 もうちょっと頑張らないと… 174 名前：デフォルトの名無しさん [2008/05/28(水) 11:04:50 ] 解決いたしました goshの引数で「-l」付けたら行けました ご助言ありがとうございます。 #!E:/Gauche/bin/gosh.exe -l (display "Content-Type: text/plain;\n\nHello, Gauche!\n") 175 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 21:10:25 ] TI-Explorerって面白そう。他に情報ないかな？ ttp://cadr.g.hatena.ne.jp/g000001/?word=*%5BLisp%E3%83%9E%E3%82%B7%E3%83%B3%5D 176 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 21:16:53 ] こことか ttp://victor.se/bjorn/lispm.php 177 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 21:28:42 ] ttp://www.unlambda.com/cadr/index.html 178 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 21:32:51 ] マニュアル（PDF） ttp://www.bitsavers.org/pdf/ti/explorer/ 179 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 21:39:31 ] メモリ8Mで68020か。ハードはMacintosh II と同等ぐらいだな。時期的にもかぶってる。 180 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 00:27:16 ] MacIvoryとかELISとかって、手に入らないのかなぁ。 181 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 12:32:08 ] TAO/ELISのソースコードは公開できないのかねえ ICOTはKL1 UNIX版その他を公開したから、 まだ研究が続いているものもあるのにねえ www.icot.or.jp/ARCHIVE/Museum/IFS/about-IFS-J.html NTTは今や私企業だから難しいかね 182 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 18:39:36 ] ソースｸﾚ厨がうざくて・・ というか、正式に依頼するなり手順踏めば手に入るものだよ。 183 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 20:46:09 ] continuationについて教えてください．(下にコードを添付します) case-Aは常に同じ状態からのcontinuation再開となるのに対し， case-Bは前回の結果を反映したcontinuation再開となります． continuationが生成されたときの状態をそのまま保存したものであり continuationが呼び出されるとその状態が復元されて続きの評価が行われる という理解からするとcase-Bの結果が理解できません． 前回のcontinuation呼び出しの影響はどこに記録されるのでしょうか． 184 名前：183 mailto:sage [2008/05/29(木) 20:46:54 ] ;;;case-A (define continuation #f) (let loop ((counter 0)) 　(write counter) 　(if (< counter 3) 　　(begin 　　　(if (= counter 1) 　　　　(call-with-current-continuation 　　　　　(lambda (k) (set! continuation k)))) 　　　(loop (+ counter 1)))　　　　;;ここが違う 　　'finished))　;==> 0123finished (continuation #t)　;==> 23finished (continuation #t)　;==> 23finished (continuation #t)　;==> 23finished 185 名前：183 mailto:sage [2008/05/29(木) 20:47:30 ] ;;;case-B (define continuation #f) (let loop ((counter 0)) 　(write counter) 　(if (< counter 3) 　　(begin 　　　(if (= counter 1) 　　　　(call-with-current-continuation 　　　　　(lambda (k) (set! continuation k)))) 　　　(set! counter (+ counter 1))　;;ここが違う 　　　(loop counter))　　　　　　　 ;;ここが違う 　　'finished))　;==> 0123finished 186 名前：183 mailto:sage [2008/05/29(木) 20:49:13 ] [case-Bが途中で切れてしまいました．] [case-Bの続き] (continuation #t)　;==> 3finished (continuation #t)　;==> 4finished (continuation #t)　;==> 5finished 187 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 21:18:32 ] >>183 case-Bの場合で説明すると、continuationはcounterが記録されている位置だけを覚えていて、その値を覚えているわけではない。 なのでset!をすると次回は前回にセットされた値が読み出されるのでそのようになる。 って感じでいいのかな？ 188 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 21:23:58 ] 状態が「復元され」るわけじゃなく、とっておいたそれにスイッチするだけ。 MLをちょろっと勉強して、Schemeの破壊的に変更する変数は MLではセルになるんだと考えれば理解が早いと思う。 189 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 21:33:32 ] MLをちょろっと勉強しにいくのはいいんだけど・・・ ちゃんと帰ってきてくれよな！ ラムダの門が君を待ってるよ〜（w 190 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 21:35:21 ] これは意見が分かれるところで、 C言語を学んでスタックフレームを理解すれば早いという説もある。 191 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 21:56:00 ] 継続で保存した状態から再開したければクロージャを使うべきだと思うけど、その例では使ってない。 保存した状態（つまりクロージャ）をスタックしてバックトラックする例を勉強すればどこが違うか理解できるだろう。 非決定性とか論理プログラミングを探して読んでみると良いと思う。 192 名前：183 mailto:sage [2008/05/29(木) 22:27:39 ] 短時間の間に多くのご指導をいただきありがとうございます． なるほど．言葉の使いかたが間違っているかもしれませんが，まとめると， 「変数の束縛関係はどこかにあるsymbol-tableに記録されているが， 『continuationは，生成時のsymbol-tableをdeep-copyしたものを保持するわけではなく 単にそのsymbol-tableへの参照を保持するだけである』」 と考えてよろしいでしょうか． だからcontinuation生成後にそのsymbol-tableに変更が加えられると， continuation呼び出し時には変更分が反映されている，と． 193 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 22:31:22 ] >>192 symbol-tableって言い方は誤解を招くけど、大筋はそんなもんかな 194 名前：デフォルトの名無しさん [2008/05/29(木) 22:40:15 ] 文字列ポートってちゃんと閉じたほうがいいの？ 195 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 23:11:27 ] lispって本当に役に立つんだろうか 明日役に立つのはrubyやpythonだけど 数年後に役に立ってくれるんだろうか 196 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 23:19:58 ] ;;;case-A (define continuation #f) (let loop ((counter 1)) (if (< counter 2) (begin (if (= counter 1) (call-with-current-continuation (lambda (k) (set! continuation k)))) (write counter) (newline) (loop (+ counter 1)))　　　　 'finished))　;==> 1finished (continuation #t)　;==> 1finished (continuation #t)　;==> 1finished (continuation #t)　;==> 1finished 197 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 23:20:34 ] ;;;case-B (define continuation #f) (let loop ((counter 1)) (if (< counter 2) (begin (if (= counter 1) (call-with-current-continuation (lambda (k) (set! continuation k)))) (write counter) (newline)　 (set! counter (+ counter 1)) (loop counter)) 'finished))　;==> 1finished (continuation #t)　;==> 2finished (continuation #t)　;==> 3finished (continuation #t)　;==> 4finished 198 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 23:21:15 ] >>181 面白そうなのにもったいないよね。 199 名前：183 mailto:sage [2008/05/29(木) 23:22:21 ] >>187->>191, >>193 厳しいご指摘もないようですので>>192で考えてみます． どうもありがとうございました．またよろしくお願いします． 200 名前：デフォルトの名無しさん mailto:sage [2008/05/29(木) 23:23:34 ] call/ccに渡された継続って なぜ末尾コンテクストじゃなくても 末尾呼び出しされるんだろう。 普通の関数と同じ扱いにすれば 参照透明性も損なわれないような気がする。 深く考えてないけど。 201 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:05:48 ] >>199 symbol-table → binding 202 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:06:59 ] >>200 帰ってくるのかよ！ 203 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:11:35 ] >>200 帰還方法を（継続として）渡すような双方向継続フレームワークを作るのが良かろう 204 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:20:42 ] >201 「束縛関係(binding)を記録している所」なら「環境(environment)」なんじゃね？ 205 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:26:38 ] >>204 環境というとフラットな印象だなあ。（グローバルみたいな） スタック状に積み重なってるイメージは束縛のほうかな。 206 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:32:47 ] >>204-205 「環境(environment)」=「クロージャ」 207 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:50:22 ] >>206 おいおい、大事なものが抜けてないか〜 それじゃ仕事になんないよ（w 208 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 06:46:31 ] >>205 それは「環境」に対して持ってるイメージが狭すぎるよ。 SECDのEはenvironmentのEだぜ。 209 名前：183 mailto:sage [2008/05/30(金) 10:41:05 ] 昨日から考えていますが，まだ理解が不充分です．お教えください． 語弊があるかもしれませんが，変数の束縛関係が登録されている場所のことを「symbol-table」ということにします． symbol-table が何枚も重なって，scope 全体の階層構造を表現しているとします． 昨日お教えいただいた「continuation は，自分が生成されたときの symbol-table への『参照』を持っている」という理解だと， 今度は >>196 の挙動が理解できません． (>>183 の「symbol-tableの『deep-copy』を持っている」という私の最初の理解だと，>>197 の挙動が理解できませんでした．) ここで生成される continuation が参照しているのは，let がつくる「top-level よりも 1 レベル深い symbol-table」だと思います． >>196 の場合，末尾再帰の際に (+ counter 1) が評価されて，その結果の 2 が新たな counter の束縛値としてこの symbol-table に書き込まれ，その後に let の本体が評価されますよね？ そうすると，loop の引数として (+ counter 1) を渡す >>196 も，set! で直接 symbol-table に束縛関係を書き込む >>197 も， どちらも同じ >>197 のような結果を示すはずだと思うのです．なぜ >>196 が counter の最初の束縛値 1 を覚えているのでしょうか． >>196 と >>197 の違いはどこにあるのでしょう？まさにそれがこの 2 つのコードを書いてみた動機だったのですが… (多分 >>196 の評価過程をどこか間違えて理解しているのだと思います) 210 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 11:54:43 ] 関数呼び出しは、新しい「symbol-table」を作るだけで、元の symbol-table を書き換えたりしない。 この例だと、 (loop (+ counter 1)) を評価するたびに、 counter の値が違う symbol-table が作られる。 だから、継続に戻ると、元の symbol-table がそのまま残ってる。 211 名前：183 mailto:sage [2008/05/30(金) 12:18:01 ] >>210 実はそれも考えましたが，この場合そうあるべきではないと思うのです． loop を呼び出すたびに新たな symbol-table を作るとなると，末尾再帰呼び出しの回数が 大きくなるにつれて symbol-table の枚数が増え続けることになり，それを表現する stack がどんどん伸びてしまいませんか？ これは「末尾再帰処理」の「余計なメモリ消費を行わずに繰り返しを表現する」という掟に 反するように思うのですが… これが末尾再帰でなく通常の関数呼び出しなら >>210 さんのおっしゃる挙動で理解できます． 212 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 12:33:04 ] >>211 もしかしたら「末尾呼び出しはジャンプに最適化される」とあちこちに書いてあるから、loopの呼び出しがジャンプになるならcounterが上書きされると思ったのかもしれないけど・・・ schemeレベルからはそう見えることはないです。 ではどうやって末尾再帰呼び出しの保証をしているのかなのですが・・・時間が無いのでだれか書かない？ 213 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 12:59:06 ] 末尾再帰呼び出しだからといって（リソースの食いっぷり以外の）挙動が変わるわけではない。 普通に再帰呼び出ししてると考えたほうが判りやすいのではないかな。 214 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 13:08:16 ] 末尾コンテキストでの呼び出しは、実際にはスタックフレームに 積まれた引数を移動させるコストが発生する。 コンパイラがフロー解析していたり、単純な呼び出しならば 直接不要になった変数を破壊する書き換えが行われる場合がある。 それと、コンパイルされれば局所変数は相対位置で参照されるので 通常は名前なんかはスタック上に保持していない。 つまりsymbol-tableという言い方はおかしい。 215 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 15:20:37 ] スタックという言い方もおかしいかもしれないな。 スタックというと「ひとつしかない」「配列」を思い浮かべるかもしれないが、 概念的にはヒープ上のリストと同じように扱えるものと考えたほうがいい。 216 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 16:05:16 ] >>214 >>215 がいいこと言った！ というわけで、誘導しようと思ったらリンクが無かったわ＾＾； Three Implementation Models for Scheme ttp://www.cs.indiana.edu/~dyb/pubs/3imp.pdf 久しぶりにラムダの門磨いときますね（w 217 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 21:19:30 ] 識別子が式に束縛される（得る）OcamlやHaskellと違って Schemeの識別子はC言語などと一緒で 式ではなく記憶領域の場所に束縛される。 末尾再帰の最適化に関しては スタックフレームの参照で考えると A→B→C　;;普通の関数呼び出しのスタックフレームの参照連鎖 A→　→C　;;末尾呼び出しの場合はAとCを直接つないじゃえ、どうせCから値を直接返そうがBが値を返そうがプログラマから見れば同じだし 　　B A→C　;;Bはどのスタックフレームからも参照されてないのでGCに回収されました ってな感じで定数空間で末尾再帰されてると考えてもいいかも。 実際の処理系はもっと効率よくやってるはずだけど。 218 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 23:15:06 ] >>211 > それを表現する stack がどんどん伸びてしまいませんか？ 末尾再帰の場合はそうせずに済むってことだよ。 219 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 23:17:44 ] >>217 良い説明だと思う。 こういう風にきちんと考えないと、継続が絡んだときの挙動を説明できないんじゃないかな。 220 名前：183 mailto:sage [2008/05/30(金) 23:27:08 ] みなさまありがとうございます． 末尾再帰呼び出しについて >>217 さんのご説明が私のイメージにいちばん近くわかりやすいです． この例で，C の呼び出しは実際には A を呼び出しているわけで，>>214 さんのいわれるような 「末尾コンテキストでの呼び出し(C)は、実際には(Cの)スタックフレームに積まれた引数を(Aに)移動させる」 処理が起きるわけですよね． 問題は，この中に continuation が混在していることなのですが，この図に continuation の スタックフレームへの参照を追加するとどのような図になるのでしょうか． 再帰呼び出しの中で，どのようにすれば continuation が「正しい」scope を持ち続けることが できるのかということなのですが… 221 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 00:11:22 ] λ式中の束縛識別子はそのλ式がapplyされた時に動的に生成されるCで言えばauto変数。 だから再帰などで同じ手続きが呼ばれてもそれぞれの変数の束縛（アドレス）はユニーク。 λ式中の自由識別子はそのλ式がevalされ（て手続きが生成され）た時に可視な束縛（ポインタ）が参照される。 だから再帰などで同じ手続きがよばれても同一の場所（アドレス）を参照する。 call/ccが引数の手続きに渡す継続は case-Aの場合は(lambda (x) (write counter) (newline) (loop (+ counter 1))) case-Bの場合は(lambda (x) (write counter) (newline) (set! counter (+ counter 1)) (loop counter)) この中に現れている自由識別子（というか束縛識別子は参照されてないけど）は何度呼ばれても同一の場所を参照する。 case-Bの場合はset!でcounterが束縛されているメモリの値を書き換えてるから 書き換えられた値を参照している。 ここで(loop (+ counter 1))は手続き呼び出しだから(loop 3)等の値に評価されてから手続きに渡されている事に留意。 そして1回目のloopのcounterと2回目のloopのcounterは同一でない場所を参照してる。（スタックフレームの再利用などの最適化されていなければ） 222 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 00:15:27 ] 継続といっても呼び出され方が特別なだけで（末尾文脈でなくても末尾呼び出しされる） 手続きと実体は一緒だから同じように考えればOK 223 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 00:16:19 ] つ metacirclar interpreter 224 名前：204 mailto:sage [2008/05/31(土) 00:35:20 ] >183 末尾再帰や継続を勉強する前にせめてschemeの評価モデルの勉強をすべきだと思うんだ まず「環境フレームモデル」について勉強することをお勧めするよ 225 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 00:50:58 ] >>224 そういう意味じゃ>>183にとってGauche本は良書じゃなかろうか? 226 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 01:37:50 ] >>183 説明してみます。 C1はcounterが1の束縛、C2はcounterが2の束縛だとすると、 最初にnamed letに入ったときはスタックは C1 ここでcontinuationをセーブしている。 loopを呼び出すと C1->C2 の状態になる。 で、ifからfinishで抜けている。スタックは空。 "空" (continuation #t)を評価すると、スタックは先にセーブした C1 の状態になって(call/cc ...)の次の式から評価が開始される。 続く 227 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 01:38:23 ] そこからloopが再び呼び出されると C1->C2' の状態となる。ここで先のC2とC2'になる。 さてC1がどこに記録されているかだけど、これはcontinuationにぶら下がる形でヒープに保管するのが簡単な実装方法。 ところでloopは末尾再帰呼び出しなので、C1->C2やC1->C2'になるところでC1を潰してC2やC2'で上書きしてしまいそうなのだが、 これは実装がC1が破壊できないことを知っているので行われない。 これはC1がヒープに保管されているかどうかで判定するのが簡単な実装方法になる。 (continuation #t)の#tはどこにいくのか？ C1->C2'の途中に#tを持った束縛ができないか心配になるけど、この#tは(call/cc ...)の帰り値となって、スタックから取り去られることになる。 う〜ん、どうだろうか？ 228 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 01:42:53 ] typo御免 「の状態となる。ここで先のC2とC2'になる。」 は 「の状態となる。ここで先のC2とこのC2'は違う束縛になる。」 のつもり。m(_ _)m 229 名前：183 mailto:sage [2008/05/31(土) 01:52:17 ] みなさまありがとうございます． >>221 さんのご説明が具体的で核心をついた答そのものだと思います． さらに >>226 - >> 228 さんのご説明は >>217 さんの例に則していて わかりやすそうです． 少し時間がかかると思いますが処理をなぞって考えさせていただきます．

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef