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

まえがき

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

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

はじめに

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

• scheme (P.6)
• empty-frame (P.7)
• update (P.7)
• lookup (P.7)
• make-env (P.7)
• extend-env (P.7)
• define-var (P.7)
• lookup-war (P.7)
• make-closure (P.8)
• data-closure? (P.8)
• closure-env (P.8)
• closure-params (P.8)
• closure-body (P.8)
• make-primitive (P.9)
• data-primitive? (P.9)
• primitive-arity (P.9)
• primitive-fun (P.9)
• print-data (P.9)
• base-eval (P.9)
• constant? (P.10)
• eval-error (P.10)
• let-eval (P.10)
• let->app (P.10)
• def-eval (P.11)
• var-eval (P.11)
• lambda-eval (P.11)
• repeat-base-eval (P.12)
• begin-eval (P.12)
• app-eval (P.12)
• base-apply (P.12)
• make-top-env (P.13)
• define-var! (P.15)

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

備考

• define-var!はdefine-varの上位互換（？）であるため、特に理由がない限りはdefine-var!だけをコピペして、define-varはコピペする必要はありません。

  このときは、def-eval、make-top-envのなかで呼び出されているdefine-varをdefine-var!に書き換えることを忘れないでください。まぁ、実行して、エラー吐いて、「define-varが無いんだよ！」って怒られて気づくとは思いますが。

• この中で、一部、未完成な関数などがありますが、ひとまず、この後の作業のために全部コピペしてください。

  「mapはコピペしなくていいの？repeat-base-evalとlet->appで呼び出してるけど？」と思う方もいるかとは思いますが、これは、本来のSchemeのmapを流用するため、わざわざ定義する必要はありません。課題93で自己を読み込ませるときには定義しなくてはいけないと思いますが。

  また、letrec-evalも未定義ですが、まぁ、実行例では使っていませんし、テストも通ります。（これも、自己を読み込むときにでも使うんでしょうかね？）

• PDFの関数schemeをコピペすると、（PDFタイトル同様、）俺妹ネタを引きずって、入力待ちプロンプトが"sister>"となりますが、まぁ、大して意味は無いんじゃないですか(笑)

やること

学生側がやるように強いられている内容は、簡単にまとめると以下の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年前の資料を見ても同じことが書いてあります。 まぁ、さっきグダグダ書いたとおり、仕様変更の影響を受けてか、これらも少しおかしな動作をしてしまいます。

デバッグのヒントは、さっきと同じで、 CENTER:''「base-evalの返り値は、ペア（環境.値）」である'' RIGHT:ということです。

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つの式にまとめるか、もしくは、別に関数を作って、適宜呼び出しつつ式まとめるという作業を行えばきちんと動くようになります。

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

• 引数funは関数を指す（fとか）
• 引数argsは値のリストを指す（(f 1)とかいう場合は、argsは(1 . ())です）
• 引数envは関数が呼ばれたときの環境を指す（要するに、λ閉包の評価にあたっては、一切関係ないです。ただ、λ閉包以降の演算を行うためには必要なので、きちんと返値として返してあげましょう）
• base-applyの返り値は、ペア（環境.評価結果）である（λ閉包に限って説明すると、ペア（λ閉包評価前の環境.λ閉包の評価結果）ということになります）
• (closure-env fun)で「λ閉包が作られたときの環境」が得られる
• (extend-env env)で「envを空のフレームで拡張した環境」が得られる（最も内側に空のフレームを付け加えた環境）
• (closure-params fun)で「λ閉包で変数として宣言されているもののリスト」が得られる
• (define-var! env param arg)で、「envの最も内側のフレームに、"param = arg"という情報を加えた環境」が得られる

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

おわりに

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

• 誤字脱字は気づいた人が修正してくださるとありがたいです。
• 他にも説明の改善等は、やる気のある方がいらっしゃったらどうぞ。
• 「この説明の意味が分からない」等ありましたら、下のコメント欄にどうぞ。できる限り改善したいと思います。
• まぁ、私なんかに聞くよりも、TAさんあてにメールした方が確実だと思いますよ？私も1通送ってお世話になりましたし。
• 来年以降の人もSchemeさせられるのかな？そうだとしたら、このページ、流用されればうれしいです(笑)。

後書き

• 初版（2013/1/11）
  • PDF等の確認は1/11に行いました。

参考サイトまとめ

• 情報科学基礎実験
• Scheme演習 第６回
• SICP４章を読んでscheme処理系書いてみた - mmitouの日記
• M.Hiroi's Home Page / お気楽 Scheme プログラミング入門
• Naoaki Iwakiri/Scheme課題memo - IS2011 Wiki