mrasu’s blog

読んだ物の内容など

算機プログラムの構造と解釈(4章)

「計算機プログラムの構造と解釈(SICP)」の4章です

解釈法を定義し、文字列を読み込み、実行できるようにします。
コンパイラDSLなどで行われる方法で、Lispで実行できるようにします。

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


4章 超言語的抽象[metalinguistic abstractionn]

4.1 超循環評価器

Lispを使った評価器で、Lispプログラムを評価する。
このように、評価対象の言語が評価する言語と同じである評価器は超循環[metacircular]であるという

4.1 評価器の中核

評価は2つの手続きの相互作用として記述できる

  1. eval
    式と環境を引数として、式を評価する
    式には種類がある
    1. 自己評価式
      数値のような自己評価式にはそれ自身を返す。変数の値は環境から得る
    2. クォート式
      クォートされていた式を返す
    3. 代入(定義)
      新しい値を取得するために再帰的にevalを呼び出し、その値で環境の変数の束縛を変更・作成する
    4. if
      述語の真偽により、帰結式・代替式を評価する
    5. lambda
      式で指定されたパラメタと本体を環境に合成した手続きへ変換する
    6. begin
      要素式を順に評価する
    7. cond
      ifの入れ子に変換し、評価する
    8. 組合せ
      演算子部分と非演算子部分を再帰的に評価したのち、評価する
  2. apply
    「手続き」と「引数のリスト」を引数にとり評価する
    基本演算と合成手続きの評価を行う

4.1.2 式の表現

評価器の言語構文は評価器の要素の取り出し方によってきまる(前置、中置など)

4.1.3 評価器のデータ構造

データ構造を定義する

4.1.4 評価器をプログラムとして走らせる

初期状態の環境とその環境への値追加を可能にすることにより評価できるようにする
評価器を走らせるため、読込→評価→出力をループさせる

4.1.5 プログラムとしてのデータ

Lispプログラムを入力としてLisp式を評価できるので作成した評価器は、万能機械といえる
評価器に対して、プログラム言語を入力すると、それをデータとして解釈する

4.1.6 内部定義

(define (f x)  
    (define (even? x)  
        (if (= x 0)  
            #t  
            (odd? (- x 1))  
        )  
    )  
    (define (odd? x)  
        (if (= x 0)  
            #f  
            (even? (- x 1))  
        )  
    )  
    (even? 3)  
)  

という定義をすると、even?とodd?は同じスコープにあり、実行時には両関数が定義されているので、動く。
しかし、実行時に両関数が定義されているのは偶然で、even?とodd?の間にeven?を実行されたらだめ。
これを回避するなら、lambda

4.1.7 構文解析と実行を分離する

同じ関数に対して呼ばれるたびに評価するのは無駄なので、キャッシュする

4.2 Schemeの変更 - 遅延評価

4.2.1 世紀順序と作用的順序

言語について

  • 世紀順序(遅延評価): 引数の値が必要になったときに評価する
  • 作用的順序: 関数の引数を内部実行前に評価する

手続きについて、同様の意味でノンストリクト(non-strict)、ストリクト(strict)という言葉をつかう。

4.2.2 遅延評価の解釈系

遅延評価用に今までの各種関数を変更する必要がある

4.2.3 遅延評価リストとしてのストリーム

cons をノンストリクトにすることにより、ストリームとリストを同一にする

4.3 Schemeの変形 - 非決定性計算

4.3.1 ambと探索

amb(候補の中から1つを適当に返す式)を導入する

2つのリストの要素を組み合わせて、要素の和が素数になる組み合わせを取ろうと思うと、

(prime-sum-pair '(1 2 3) '(20 35 110))  
(define (prime-sum-pair list1 list2)  
    (let ((a (an-element-of list1))  
            (b (an-element-of list2))  
        )  
        (require (prime? (+ a b)))  
        (list a b)  
    )  
)  
(define (require p)  
    (if (not p) (amb))  
)  
(define (an-element-of items)  
    (require (not (null? items)))  
    (amb (car items) (an-element-of (cdr items)))  
)  

無限の範囲から選択するには、

(define (an-integer-starting-from n)  
    (amb n (an-integer-starting-from (+ n 1)))  
)  

4.2.3 非決定性プログラムの例

ambの使用例

Baker, Cooper, Fletcher, Miller, Smithが1~5階に住んでいて、
Bakerは最上階ではない。Cooperは最下階ではない。Fletcherは最上階でも最下階でもない。MillerはCooperより上の階。SmithはFletcherの隣の階ではないFletcherはCooperは隣の階ではない。
という条件が与えられたとき、各人の階を求めることができる

4.4 論理型プログラミング

(define (append x y)  
    (if (null? x)  
        y  
        (cons (car x) (append (cdr x) y))  
    )  
)  

は、
(a b)と(c d)をappendすることができるが、逆はできない。
ので、逆もできるように「定義を定義して、解決を自動化する」

4.1 推論的情報検索

データベースにデータを入れて、取り出すことを考える。

(job (Bitdiddle Ben) (computer wizard))  
(job (Hacker Alyssa P) (computer programmer))  
(job (Cratchet Robert) (accounting scrivener))  

と、登録すると

(job ?x (computer . ?type))  

と検索することで

(job (Bitdiddle Ben) (computer wizard))  
(job (Hacker Alyssa P) (computer programmer))  

が得られる。
さらに、

  1. and/or/notによる質問の合成
  2. 変数化

ができるようにする

質問を抽象化したものを規則(rule)とすると、再帰が使える
すると、論理的推論が可能になる

例えば、

(rule (append-to-form () ?y ?y))  
(rule (append-to-form (?u . ? v) ?y (?u . ?z))  
    (append-to-form ?v ?y ?z)  
)  

という規則から

(append-to-form (a b) (c d) ?z)  

を満たすものは、(a b c d)であり、

(append-to-form (a b) ?y (a b c d))  

を満たす?yは (c d)であり、

(append-to-form ?x ?y (a b c d))  

を満たす?x/?y の組み合わせは全て導出される

4.4.2 質問システムはどう働くか

質問システムは、2つの演算からなる

  1. パターンマッチング
    (a b c) (x? y? z?) はそれぞれa,b,cでマッチし、(x? y?)に失敗する
  2. ユニフィケーション
    ( (a ?y c) (a b ?z))と(x? x?)では連立方程式のようにして、?x=(a b c)を導く

4.4.3 論理型プログラミングは数学的理論か

同一視できそうだが、論理型プログラミングは手続き的に解釈する制御構造があるがために、同一視するのは正しくない
以下の問題がある

  1. 無限ループ

    lisp (assert! (rule (married ?x ?y) (married ?y ?x) ) ) (married? Mickey ?x)

    とすると、
    (married? Mickey ?x)と (married? ?x Mickey)を交互に探し続ける

  2. notの問題

    lisp (and (supervisor ?x ?y) (not (job ?x (computer programmer))) ) (and (not (job ?x (computer programmer))) (supervisor ?X ?y) )

    は同じ結果が期待されるが、後者は(job ?x (computer programmer))を評価した結果にnotでフィルターするため結果は常に空になる