忙しい人のためのScheme処理系（課題92）

まえがき

このページの目標は、課題92のScheme処理系を書くという課題を、課題のページの実行例が動く＋提出時のテストが通るレベルに作ろうというものです。 Optional課題93の、自己を読み込めるScheme処理系に関しては触れませんのであしからず。 （というか、書いてる人がプログラミング始めて3か月とかなので、難しいこと聞かれても答えられる自身がありません。というか、たぶん無理です(笑)）

※私はWin7Pro＋Gaucheで作って、テストは通りました。ローカルな環境での設定等については皆さんで対応ください。 ※答えは載せていません。さすがにそこまですると、カンニングとかに限りなく近づいちゃうでしょうから。まぁ、結構踏み込んだところまでは説明を書くので許してください。

はじめに

まず、講義のページのPDFから、以下の関数をコピペしておきます。掲載順序はPDF掲載順です。（カッコ内はPDFでのページ数です）

数が多いですが、頑張ってください。（検索で"define"で検索して探したりすると多少は楽です。）

備考

やること

学生側がやるように強いられている内容は、簡単にまとめると以下の4つです。

make-top-env内の書き足し
組み込み関数を追加します。具体的には、-,*,<,cons,car,cdrを実装します。（テストで必要かどうかは知りませんが、せっかくなので、>も実装するといいと思います。）
if-evalの定義
自作Scheme内でifを使えるように実装します。
quote-evalの定義
自作Scheme内でquote（もしくは'）を使えるように実装します。
base-apply内の書き足し
関数適用時に関数がユーザー定義関数（λ閉包）だった時の振る舞いを定義します。

これから、それぞれについて説明を書こうと思います。

make-top-env内の書き足し

これは、例として挙げてあるものをコピペして、ちょこちょこ書き換えてあげれば終わりです。特に注意すべき点はないと思いますが、あくまで、（環境.計算結果）のペアを返すことを忘れないようにしてください。

また、make-primitiveの直後の数字は引数の数を表しているため、当然ながらcar,cdrでは1となります。コピペの後、2を1に変えるのを忘れないでください。（まぁ、実行すると、「引数の数が違うんだよ！」と怒られるので気付くとは思いますが。）

argsとして渡される物は、引数を入れたリスト（ペア）です。具体例を挙げると、

(+ 1 2)→argsは(1 . (2 . ()))
(cons 1 2)→args(1 . (2 . ()))
(car (1 . 2))→args((1 . (2 . ())) . ())

となります。計算結果を求めるときのcarなりcdrなりの数合わせの参考にしてください。

if-evalの定義

これは、IS2011の先輩のページを参考にするのがいいと思います。

…とまぁ、きちんと理解することが前提なら、この先輩のページの中でexpの該当部分と書いてある部分は自力で埋めるべきなのでしょうが、「そんなの面倒だ！」という方はhttp://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/material/6/6.mtd.dist.htmlをご覧ください。（URLから見るに、12年前の講義の資料ですね。萩谷先生は現在の基礎実験の担当の先生なので、ある種公式の資料です(笑)）

しかし、わざとなのか、タイプミスなのか（はたまた、他の原因なのか）はわかりませんが、12年前の講義資料のほうは、一か所間違いがあります。ここからif-eval（資料中ではeval-if）をコピペすると、「常に#tのほうの式を評価する」というバグが発生します。 （まぁ、他の関数を見ればわかるとおり、12年前は関数の引数やら、返値やらが現在私たちが使っている関数とは少し異なるので、そのせいでしょうけど。ちなみに、IS2011の先輩の資料のほうも、同様の間違い（仕様変更の影響？）があります。）

デバッグのヒントは、

「base-evalの返り値は、ペア（環境.値）」である

ということです。

quote-evalの定義

これも、またしてもIS2011の先輩のページを参考にするのがいいと思います。もしくは、先ほど示した、12年前の資料を見ても同じことが書いてあります。 まぁ、さっきグダグダ書いたとおり、仕様変更の影響を受けてか、これらも少しおかしな動作をしてしまいます。

デバッグのヒントは、さっきと同じで、

「base-evalの返り値は、ペア（環境.値）」である

ということです。

base-apply内の書き足し

先輩のページにもあるとおり、これが課題の真打ちです。私が作った時もこいつに手間取りました。まず、λ閉包の評価の方法について、これ::http://hagi.is.s.u-tokyo.ac.jp/kisojikken/scheme.pdfやここ::http://hagi.is.s.u-tokyo.ac.jp/kisojikken/sicp1.htmlの下のほうで動作を把握します。

把握とか怠いんだよ！という方はすぐ下へどうぞ。

要するに、λ閉包を評価するときは、

（2の例）

(define f (lambda (x) (+ x 1)))
(f 1)

と実行した際に、(f 1)を処理するときには、xに1を対応付けるということ。

という流れを行うことになります。 Schemeは関数型言語なので、これらの作業を1つの式にまとめるか、もしくは、別に関数を作って、適宜呼び出しつつ式まとめるという作業を行えばきちんと動くようになります。

注意点は以下のようになります。

ここで、変数の束縛が少し面倒（argsのリストと、funのparamsを連想リストに登録していかねばならない）ですが、これを行わないと、複数の変数を扱うような関数に対応できません。変数束縛をさぼって、「使用できる変数は1つのみ」という処理系を書き上げた場合、課題のページの動作例は動かない（letの所でエラーを吐く）ものの、提出時のテストは通ってしまいます(笑)。まぁ、そんな、あとからコメント付きで指摘されかねない危ない橋は渡らず、きちんと複数変数に対応する方が無難だと思います。

おわりに

まず、ここまで読んでくれてる人いたら、どうもありがとうございます。ほんっとうに駄文ですみません。ある程度は説明しつつ、核心を逸らして書いてるので、なかなか読みにくい＋わかりにくい文章になってると思います。

後書き

参考サイトまとめ

ReadingCategory KisoJikkenClassCategory

taka/忙しい人のためのScheme課題入門 (最終更新日時 2013-04-27 15:13:34 更新者 grafi)