関数型言語の勉強にSICPを読もう - (53) 4章 - 超言語的抽象(216ページ) C++でSchemeインタプリタを作ろう1

4章では Scheme の上に Scheme インタプリタを作る過程でいろいろなものを学んでいきます。
このように、被実装言語と実装言語が同じなことを metacircular というらしいのですが、読んでいるだけでドキドキしてきます。

実際4章を読み進めていくと、とても面白いのですが、所々で引っかかるところがあります。
どうも読んでいるだけでは解決しないモヤモヤがあって、それは被実装言語と実装言語の境界に関する問題のように思えてきました。
metacircularだと、どこまでが被実装言語の機能で、どこからが実装言語の機能なのか分からなくなってきてしまうのです。

こんな経緯もあり、4章で書かれているScheme インタプリタを「ほぼそのまま」C++で実装してみようという思いに至りました。
最近SICP日記を更新できなかったのはこのあたりに悩んでいたからです。
いろいろと困難あるでしょうが、試行錯誤してぜひ完成させたいです。

C++で実装する前提とか

現時点で分かっているだけでも、C++でScheme インタプリタを実装するのは、SchemeをScheme自身で実装するとだいぶ違います。

1.型の問題
C++ではSchemeに比べて、登場人物の型を強く意識しないといけません。
exp, env などがどういう型を持つか？あたりが実装の肝となりそうです。

2.S式の問題
入力されたS式を扱うことに関して、C++はSchemeに比べてかなり劣ります。
このあたりも自分で実装しないといけないでしょう。

3.primitive procedureの問題
primitive procedureの実装まで到達していませんが難しそうです。

Object型

評価される対象であるところの exp は全て Object クラスが基底クラスであるようなクラスにしました。
Objectをクラスで表現して継承をバリバリ使うか、構造体でごにょごにょするかに関してはかなり迷いましたが、経験がないのでとりあえず前者でいけるところまで行こうと思います。
なお、諸事情により RTTI は使わない方針でいきます。

Objectは以下の2つのメソッドを持ちます。

    virtual std::string toString() = 0;
    virtual int type() const       = 0;

toStringは、そのオブジェクトの文字列表現を返します。Schemeの display で使用することを想定しています。
typeは、型情報です。RTTIを使わないので type tag を自前で管理します。

eval

さてここからは、SICPのとおりに進んでいきます。
まずは eval です。
eval は ObjectとEnvironmentを引数として受け取りこれを評価し、Objectを返します。
たとえば自己評価式のカテゴリに属するObjectは、そのまま return されます。
if 文でだらだらと exp 判定をとしているのはSICPのとおりに書いただけです。

Object* eval(Object* exp, Environment* env)
{
    if (isSelfEvaluating(exp))
    {
        return exp;
    }

略

ここの実装は後からいろいろと変形する予感がしてなりません。

apply

もうひとつの肝である apply です。
procedure と arguments を引数として受け取って実行します。
primitive procedure の実装はまだ先なので compound procedure のみです。

Object* apply(Object* procedure, Objects* arguments)
{
    if (isCompoundProcedure(procedure))
    {
        Procedure* p = (Procedure*)procedure;
        p->env()->extend(p->parameters(), arguments); 
        evalSequence(p->body(), p->env());
    }

   // 略
}

procedure の仮パラメータとargumentsを組み合わせて、Environmentを拡張します。
そしてその環境の中で body を評価していきます。
楽しいですね。（まだ動いていないけど)

※「SICPを読もう」の目次はこちら