読者です 読者をやめる 読者になる 読者になる

kb84tkhrのブログ

何を書こうか考え中です

Scheme手習い(20) eval、またはvalue、またはmeaning

ついに最終章、ラスボス2です
小さいschemeの核にあたるもの、いわゆる?evalを作ります
でもこの本ではvalueっていう名前になってます
でもvalueは空っぽの環境を作るだけで実際の仕事の中心はmeaningという関数がやってます

ラスボス2と言っても、Yコンビネータみたいに何がなんだかわからないようなものではなく
ひとつひとつの関数はとてもシンプルで難しくはありません
そのかわり、たくさんの関数があるのでそれらの関連を理解する必要があります
あと、環境と呼ばれるデータ構造も

この本ではこれまでクロージャとか関数の評価方法とか説明が省かれていた部分がありますが
この章を理解すればあそこはそういうことだったのか、と納得できます
「この本では形式的な定義はしない」ので代わりにソース見ろということですね
「この本を2回以下で読み切ろうとしないこと」というのは
この章をクリアしたら2周目に突入してもう1回読め、ということを言っているのではないかと

いつもどおりなんの説明もなく始まります

エントリ(entry)とはリストのペアであり、その第1のリストが集合であるものです。

これがインタプリタの作り始めだと誰が思うでしょうかいや思いません
(知ってる人は別として)

エントリを扱うための関数を定義します

(define new-entry build)
(define lookup-in-entry
  (lambda (name entry entry-f)
    (lookup-in-entry-help name (first entry) (second entry) entry-f)))
(define lookup-in-entry-help
  (lambda (name names values entry-f)
    (cond ((null? names) (entry-f name))
          ((eq? (car names) name) (car values))
          (else (lookup-in-entry-help name (cdr names) (cdr values) entry-f)))))

buildは名前の集合と値のリストからエントリを作る関数、
lookup-in-entryはエントリ内で名前に対応する値を得る関数です
entry-fは名前を引数に取る関数で、名前が見つからない場合に呼ばれます
こういうのも継続っていうんでしょうか
違う気がしますけど何が違うかというとわかりません
やっぱり継続かもしれません

名前と値の対応をつけるなら、名前と値のペアを作ってそれをリストにするほうが
自然な気がしますが理由はあとでわかります
そもそもまだ何を作っているのかわかってませんし

テーブル(table、環境ともいう)とはエントリのリストだとします。

テーブルを扱うための関数を定義します

(define extend-table cons)
(define lookup-in-table
  (lambda (name table table-f)
    (cond ((null? table) (table-f name))
          (else (lookup-in-entry 
                 name (car table) 
                 (lambda (name) 
                   (lookup-in-table name (cdr table) table-f)))))))

extend-tableはテーブルにエントリを追加する関数、
lookup-in-tableはテーブルから名前に対応する値を得る関数です

extend-tableのシンプルさには度肝を抜かれる思いです
本気で言語書くときはもっといろいろくっつくのかな
エラー処理とか

table-fはやはり名前を引数に取る関数で、名前が見つからない場合に呼ばれます
entry-fはここで、テーブル内の次のエントリから名前を探すために使われています
そうやって使うのかー

知らないで「テーブルから値を探す関数を書け」と言われたら
そこをパラメータにしようとは考えず直接書いてしまいそうですけど

(define lookup-in-table2
  (lambda (name table)
    (cond ((null? table) #f)
          ((lookup-in-entry2 name (car table)))
          (else (lookup-in-table2 name (cdr table))))))
(define lookup-in-entry2
  (lambda (name entry)
    (lookup-in-entry-help2 name (first entry) (second entry))))
(define lookup-in-entry-help2
  (lambda (name names values)
    (cond ((null? names) #f)
          ((eq? (car names) name) (car values))
          (else (lookup-in-entry-help2 name (cdr names) (cdr values))))))

実は大きなごまかしをしてて、失敗すると#fを返すんですが、
ということは値が#fの場合と区別がつかなくなっています
見つかった値と成功/失敗と両方返せるとか、
例外があるとかならちゃんとしたものにできるんですけど

そういう方法がないから仕方なく失敗したときに呼ぶ関数を渡してます、ってことでしょうか?
それだけではなくて、何かもっといいことがあるような気がするんですが
パラメータにしておくと柔軟ではありそうですが柔軟性が役に立っているかな?

しばらくの間、ゴシック体で書いてあるところはプログラムそっくりだけど
valueという関数が扱うデータだよっていう話
ゲーデルの証明みたい

続いて、式のタイプを考えます。

  • 定数 *const ※組み込みの関数も含まれます
  • quote *quote
  • 識別子 *identifier
  • ラムダ式 *lambda
  • cond *cond
  • 関数適用 *application

式のタイプを返すexpression-to-actionを作ります
単にcondが並んでいるだけで難しくはありません
consとかcarとかの組み込み関数が*constとして扱われるのがちょっと意外でした
関数というくくりで見れば*lambdaにも近いような気がするんですが
関数へのポインタみたいなものと思えば確かに定数

タイプはそのタイプの式を評価する関数を兼ねていますので
式をexpression-to-actionに渡せば評価できます
(quote ())というのは環境です
最初はまだ覚えておくべき変数がないので環境はからっぽです

(define value
  (lambda (e) (meaning e (quote ()))))
(define meaning
  (lambda (e table)
    ((expression-to-action e) e table)))

環境を扱う関数を定義して、
タイプを判別する関数を定義して、
式を評価する関数を定義するというトップダウンともボトムアップともとれない
不思議な順番には何か意味があるんでしょうか
わかりません

とりあえずガワができたので、少しずつ作っては動かすことができます
定義してない関数があっても、呼び出すまではエラーになりません
こういうときはありがたいです

(define *const
  (lambda (e table)
    (cond ((number? e) e)
          ((eq? e #t) #t)
          ((eq? e #f) #f)
          (else (build (quote primitive) e)))))

さっき気になった組み込み関数はここで(primitive hoge)という形になって
ちょっと別扱いになります
じゃあ*primitiveみたいなタイプ作ってもいいんじゃないかと

さて

> (value 1)
1
> (value #t)
#t
> (value 'cons)
(primitive cons)

やったー!
・・・という感じはまだしませんけどとりあえずインタプリタ動きました

(define *quote
  (lambda (e table)
    (text-of e)))
(define text-of second)

eを見てほげほげすればいいんだな、ということがちょっと見えてきました

> (value '(quote abc))
abc

本文だとこの後*identifier*lambdaを定義してから*condなんですが
*identifier*lambdaだけあってもつまらないので先に*condやります

これまでより複雑ですが、ただリストをいじってるだけです

(define else?
  (lambda (x)
    (cond ((atom? x) (eq? x (quote else)))
          (else #f))))
(define question-of first)
(define answer-of second)
(define evcon
  (lambda (lines table)
    (cond
      ((else? (question-of (car lines)))
       (meaning (answer-of (car lines)) table))
      ((meaning (question-of (car lines)) table)
       (meaning (answer-of (car lines)) table))
      (else (evcon (cdr lines) table)))))
(define cond-lines-of cdr)
(define *cond
  (lambda (e table)
    (evcon (cond-lines-of e) table)))

(else #f)あたりにちょっと不自然さを感じます
(and (atom? x) (eq? x (quote else)))で済むはずですが
セルフで実行できるようにってことかな
(ここで定義するインタプリタandを実装していないことからして)

> (value '(cond (#t 1)))
1
> (value '(cond (#f 1) (#t 2)))
2
> (value '(cond (#f 1) (else 2)))
2

動いてます
変数も関数もないのでかなり不自然なcondですが