SICP 4 Metalinguistic Abstraction - プログラミング再入門

どうも普通の言語（と言うかLisp）では実現されていない、更にそこからはみ出たアイデアについて。
Lispで書くLisp インタープリタは『Scheme手習い』で経験済み。

ノート

Metalinguistic abstraction -- establishing new languages --

超言語抽象=新しい言語を定義する事

The evaluator, which determines the meaning of expressions in a programming language, is just another program.

プログラミング言語の式の意味を決める評価器自身もただのプログラムである。

殆どのプログラムは『ある言語』で書かれたプログラムの評価器と捉える事が出来る。
そもそも細部を部品として抽象化してあるとき、最上位部分のプログラムは何らかの言語と捉える事も出来る。内部DSL的な話。更にはリストで数式を表現したシステム、電子回路シミュレータ、（なんちゃって）制約プログラミングシステムは
外部DSL的な話。

Schemeをベースの言語に、まずは基本的なLispシステムを構築。
次にapplicative-order eveluationのSchemeに変わって、normal-order evaluationの（多分Lisp）を実装。
次にnondeterministic＝非決定論的なコンピューティングの実装。値とはいくつかの取り得る値で表現されて、制約を満たす値を探して行く。
最後に論理プログラミング。

4.1 The Metacircular Evaluator

『超循環評価器』と言う訳語が充てられている。
評価するプログラムと同じ言語で書かれた評価器をmetacircularと呼ぶ。

（スペシャルフォームではない）式を評価するとき、入れ子になった式を評価した後、最初の項を手続きとして残りの引数に適用する。
手続きを引数に適用する時には手続きの本体を新しい環境下で評価する。そこでは手続きの環境部分を拡張して、仮引数が実引数に拘束されている。

4.1.1 The Core of the Evaluator

Eval

Evalは式とそれを評価する環境を引数に取る。
式のタイプを判定して、タイプに応じて対応する。
本物のEvalはdata drivenに書いてあり新しいタイプを追加してもコードを変更する必要は無いが、ここでの例ではコードを変更しないと新しいタイプは追加出来ない。

Apply

Applyは手続きと引数を引数として受け取る。プリミティブな手続きであればそのまま実行。定義されたプロシージャであれば、その中の式を一つ一つ評価して行く。

Procedure arguments

List-of-valuesは与えられた環境下で引数を全て評価して結果をリストにする。

Conditionals

ifは条件部のみを評価して、真の時のブロック、偽の時のブロックは条件部の結果が決まるまで評価しないので専用の評価ルーチンが必要。
述語部分は必ずしも真・偽を返さないので、インタープリタを実装している言語の判断をそのままは使えない。なので仲介をするtrue?が必要。

Sequences

式のリストを評価する。手続きの本体かbeginのブロック。

Assignments and definitions

代入と定義は最初の引数は名前を参照しているだけで、評価はしないのでこれも専用の評価ルーチンが必要。

Exercise 4.1

テキストのlist-of-valuesの定義ではconsの二つの引数が評価される順番はインタープリタを実装している言語に依存してしまっている。これを強制する為にはどちらかを先に評価してしまって、あとからconsで繋ぐ必要がある。
呼ばれた時にdisplayする関数を呼ぶラムダを二つ引数に見立てて評価させる。その他色々とスタブを作って、Racketの解釈に任せる、左から順に評価、右から順に評価を作成。

#lang racket
(define no-operands? null?)
(define (eval exp env)
  (exp))
(define first-operand car)
(define rest-operands cdr)

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

(define (list-of-values-left-to-right exps env)
  (if (no-operands? exps)
      '()
      (let ((first-value (eval (first-operand exps) env)))
        (cons first-value
              (list-of-values (rest-operands exps) env)))))

(define (list-of-values-right-to-left exps env)
  (if (no-operands? exps)
      '()
      (let ((rest-of-values (list-of-values (rest-operands exps) env)))
      (cons (eval (first-operand exps) env)
            rest-of-values))))

(define (a)
  (display "a")(newline) 1)

(define (b)
  (display "b")(newline) 2)

動作確認

> (list-of-values (list (lambda () (a)) (lambda () (b))) null)
a
b
'(1 2)
> (list-of-values-left-to-right (list (lambda () (a)) (lambda () (b))) null)
a
b
'(1 2)
> (list-of-values-right-to-left (list (lambda () (a)) (lambda () (b))) null)
b
a
'(1 2)
>