SICP4.1にとりかかる前に足し算evalを作る

SICP4章ではschemeの評価器を作ります。
SICPの4.1を読んでそのまま実装するだけでクロージャを装備した簡易schemeが出来上がります。
しかしそれだけにハードルが高くなるためなかなか先に進めなくなってしまう場合も多いそうです。
そこで今回は足し算を実行できるevalの作成を目標として、そこまでの道程を小目標に分割し、
SICP4.1のハードルにとりかかる前にほんの少しステップを置いてみたいと思います。

ちなみに実装はlinux上のmit-schemeで行います。他の処理系を使う方は適宜読み替えてください。

以下が少目標のリストです。

1. 基本手続きreadで式を読む
2. readで入力した式をオウム返しにするevalを実装する
3. 連想配列を作る
4. 連想配列から値を取り出す関数を作る
5. 簡易schemeのグローバル環境を作る
6. readで入力したシンボルに束縛されている値を取り出すevalを実装する
7. readから文字列や数値などの値オブジェクトが得られたら、そのままその値を返すevalを実装する
8. ()でくくられた式が入力されたら、その式はオウム返しにするevalを実装する
9. ()でくくられた式が入力されたら演算子と被演算子に分ける
10. ()でくくられた式が入力されたら演算子と被演算子に分けて、演算子にevalを実行し、被演算子のリストにもevalを実行するevalを実装する
11. mit-schemeのapplyを使ってみる
12. グローバル環境にmit-schemeの'+'関数を設定し、シンボル'+'で取り出せるようにする
13. ()でくくられた式にapplyを適用するevalを実装する

基本手続きreadで式を読む

mit-schemeをインストールしたら、"scheme"と実行してみてください。mit-schemeの対話環境が起動します。
ここで以下のように"(read)"と入力し、エンターキーを押すとユーザーの入力待ち状態になります。
思いつく限りのS式を入力してみましょう。入力したS式がそのまま表示されます。

1 ]=> (read)
hello

;Value: hello

1 ]=> (read)
(+ 1 2 3)

;Value 13: (+ 1 2 3)

readで入力した式をオウム返しにするevalを実装する

早速evalを実装しましょう。中身は何もないです。
以下のプログラムをscheme.scmに保存してください。

; scheme.scm
(define (eval sexp)
  sexp)

これを以下のようにして実行します。

scheme -load scheme.scm

scheme.scmの内容がロードされて対話環境が起動します。
次に以下のように入力して、基本手続きreadからS式を受け取ってevalに渡してみましょう。
入力した式がそのまま帰ってきます。

1 ]=> (eval (read))
Hello 

;Value: hello

これから行っていくschemeの基本的な動作はこんな感じです。
ひたすら基本手続きreadを使ってS式を受け取り、evalに渡して結果を返すだけ。
evalは受け取った式を判別していろいろな処理を行って行きます。

連想配列を作る

evalをどんどん実装していく前に、evalが参照するデータベースを作りましょう。
このデータベースからはシンボルをキーにオブジェクトを取り出せるようにします。
このデータベースは連想配列で実装します。
連想配列はシンボルとオブジェクトのペアのリストです。
例えばシンボルxに1を、シンボルyに2を、シンボルzに3を束縛した連想配列は以下のようになります。

'((x . 1) (y . 2) (z . 3))

連想配列から値を取り出す関数を作る

連想配列から指定したキーのペアを取得する組み込み関数assocを使って、
オブジェクトをデータベースから取り出す関数lookup-variable-valueを作りましょう。
簡単に実装できますので、scheme.scmに追加しましょう。

; scheme.scm
(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp)
  sexp)

早速動かしてみましょう。
"scheme -load scheme.scm"と実行して対話環境を起動してください。
そうしたら以下のようにdbを作ってdbから値を取り出してみましょう。
意図した通りのオブジェクトが得られます。

1 ]=> (define db '((x . 1) (y . 2) (z . 3)))

;Value: db

1 ]=> (lookup-variable-value 'x db)

;Value: 1

1 ]=> (lookup-variable-value 'y db)

;Value: 2

1 ]=> (lookup-variable-value 'z db)

;Value: 3

簡易schemeのグローバル環境を作る

データベースを扱えるようになったので、evalが参照するグローバル変数を格納したデータベースを作成します。
とりあえずシンボルhelloと文字列"world"のペアだけが格納されたデータベースを以下のようにscheme.scmに定義しておきます。

(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp)
  sexp)

早速グローバル環境から値を取り出してみましょう。
"scheme -load scheme.scm"と実行して対話環境を起動し、以下のような結果が得られるか試してみてください。
evalはまだ使いません。

1 ]=> (lookup-variable-value 'hello global-env)

;Value 13: "world"

readで入力したシンボルに束縛されている値を取り出すevalを実装する

グローバル環境から値が取り出せるようになったので、基本手続きreadからシンボルを入力してグローバル環境から値を取り出すevalを実装しましょう。

まずevalがS式と一緒に環境を受け取るようにします。
そして受け取ったS式がシンボルなら環境からオブジェクトを取り出して返すようにします。

; scheme.scm
(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

上記のとおりにscheme.scmを実装したら"scheme -load scheme.scm"から対話環境を起動して、
以下のように入力してみてください。
シンボルhelloをキーにして文字列"world"が得られます。

1 ]=> (eval (read) global-env)
hello

;Value 13: "world"

readから文字列や数値などの値オブジェクトが得られたら、そのままその値を返すevalを実装する

続いてevalが数値や文字列を受け取ったら、そのまま数値や文字列を返すevalを実装してみましょう。
今のままではエラーになってしまいますから。

入力されたS式が数値であることを判断するのには組み込み関数number?を使います。
入力されたS式が文字列であることを判断するのには組み込み関数string?を使います。
これらの関数は以下のようにして使います。

1 ]=> (number? 1)

;Value: #t

1 ]=> (number? 'x)   

;Value: #f

1 ]=> (string? "hello")

;Value: #t

1 ]=> (string? '(world))

;Value: #f

これらの関数をevalに組み込んで、文字列と数値をそのまま返すように実装しましょう。

(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

これを実行して以下のような結果が得られことを確認してみてください。

1 ]=> (eval (read) global-env)
1

;Value: 1

1 ]=> (eval (read) global-env)
"hello"

;Value 13: "hello"

1 ]=> (eval (read) global-env)
hello

;Value 14: "world"

()でくくられた式が入力されたら、その式はオウム返しにするevalを実装する

次に()でくくられた式が入力されたら、その式をエラーにせずにそのまま返すようにevalを修正しておきます。

()でくくられた式かどうかは組み込み関数pair?を使って判定します。
pair?は以下のようにして使います。

1 ]=> (pair? '(1 . 2))

;Value: #t

1 ]=> (pair? "hello")

;Value: #f

それではpair?をscheme.scmのevalに組み込んでみましょう。

(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; ()でくくられた式だったらそのまま返す
    ((pair? sexp) sexp)
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

これを実行してみます。

1 ]=> (eval (read) global-env)
(1 2 3)

;Value 13: (1 2 3)

()でくくられた式が入力されてもエラーにならずにそのまま帰ってくるようになりました。

()でくくられた式が入力されたら演算子と被演算子に分ける

schemeでは以下のようにリストの先頭の要素を演算子、それ以外の要素を被演算子として扱います。

(演算子 被演算子 被演算子 ... )

作成中のevalでも、リストを受け取ったら演算子と被演算子に分けて扱えるようにしてみましょう。
ただ単にcarとcdrで分けるだけですので簡単です。
とりあえずリストを受け取ったら被演算子のリストを返すevalにしてみます。
こんな感じです。

(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; ()でくくられた式だったら ・・・
    ((pair? sexp) 
     ;; リストの先頭要素を演算子、それ以外を被演算子とする
     (let ((operator (car sexp))
           (operands (cdr sexp)))
       operands))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

これは以下のように実行できます。

1 ]=> (eval (read) global-env)
(scheme hello world)

;Value 13: (hello world)

()でくくられた式が入力されたら演算子と被演算子に分けて、演算子にevalを実行し、被演算子のリストにもevalを実行するevalを実装する

演算子と被演算子に分けたら、それぞれにevalを実行してオブジェクトとオブジェクトのリストに変換します。
何も難しいことはありません。ただ単にoperatorとoperandsにevalを実行するだけです。
ただoperandsはリストなのでmapを使うことにしましょう。
実装は次の通りになります。

(define global-env '((hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; ()でくくられた式だったら ・・・
    ((pair? sexp)
     ;; リストの先頭要素をevalで評価し、
     (let ((operator (eval (car sexp) env))
           ;; 被演算子のリストのそれぞれの値もevalで評価する
           (operands (map (lambda (s) (eval s env)) (cdr sexp))))
       operands))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

これも以下のように実行出来ます。

1 ]=> (eval (read) global-env)
(1 hello hello)

;Value 13: ("world" "world")

mit-schemeのapplyを使ってみる

演算子と被演算子のリストは基本手続きapplyを使って実行する事ができます。
ここでは足し算'+'をapplyを使って実行してみましょう。
mit-schemeの対話環境を起動して以下のように実行します。
1 + 1の計算結果が表示されます。

(apply + '(1 1))

applyは以下のようなインタフェースを持ち、それらを評価して値を返してくれます。

(apply 演算子のオブジェクト 被演算子のオブジェクトのリスト)

作成したevalでは既に演算子と被演算子を分けられるようになったので、
あとはapplyを使えるようにするだけです。

グローバル環境にmit-schemeの'+'関数を設定し、シンボル'+'で取り出せるようにする

まだグローバル環境に足し算を追加していませんでした。
scheme.scmに足し算を追加しておきましょう。
scheme.scmのglobal-envの定義を以下のように書き換えてください。

(define global-env `((+ . ,+) (hello . "world")))(define global-env `((+ . ,+) (hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; ()でくくられた式だったら ・・・
    ((pair? sexp)
     ;; リストの先頭要素をevalで評価し、
     (let ((operator (eval (car sexp) env))
           ;; 被演算子のリストのそれぞれの値もevalで評価する
           (operands (map (lambda (s) (eval s env)) (cdr sexp))))
       operands))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp))))

クォートがバッククォートに変わり、シンボル+のペアに指定しているのが,+になっているのがポイントです。
これはscheme固有の書き方です。
バッククォートとクォートはどちらもリストを作るマクロですが、バッククォートを指定した場合には,の箇所だけ評価してリストを作ることが出来ます。
したがって新しいglobal-envにはシンボル+とmit-schemeの組み込み関数+に束縛されていた関数オブジェクトのペアを追加したことになります。

()でくくられた式にapplyを適用するevalを実装する

それではevalにapplyを追加してみましょう。

(define global-env `((+ . ,+) (hello . "world")))

(define (lookup-variable-value var env)
  (cdr (assoc var env)))

(define (eval sexp env)
  (cond
    ;; 数値か文字列だったらそのまま返す
    ((or (number? sexp) (string? sexp)) sexp)
    ;; シンボルだったら環境から値を取り出して返す
    ((symbol? sexp) (lookup-variable-value sexp env))
    ;; ()でくくられた式だったら ・・・
    ((pair? sexp)
     ;; リストの先頭要素をevalで評価し、
     (let ((operator (eval (car sexp) env))
           ;; 被演算子のリストのそれぞれの値もevalで評価する
           (operands (map (lambda (s) (eval s env)) (cdr sexp))))
       (apply operator operands)))
    ;; 上記以外の式だったらエラーにする
    (else (error "eval error: "sexp)))

これで以下のようにして足し算が出来るようになりました。

1 ]=> (eval (read) global-env)
(+ 1 2)

;Value: 3

1 ]=> (eval (read) global-env)
(+ (+ (+ (+ 1 2) 3) 4) 5)

;Value: 15