初めての人のためのLISP[増補改訂版]のメモです。
最初:初めての人のためのLISP (第1講-第5講) - もうカツ丼でいいよな
M式
遠い昔にはそんなものもあった。
M-expression - Wikipedia
Lispを解剖するには少し見た目の違うものが良いだろうということで使う人もいたが、同じ見た目のLispでも自分自身を解剖するのに十分だったので今では使われない。
S式の評価
- S式は評価によりS式を返す
- 同じS式が同じ値を返すとは限らない
- 単独のシンボルは変数である、(a b c)なら最初の要素は関数である等々
- 評価値に影響を与える源を環境(environment)と呼ぶ
- 環境によらない不変の評価規則を言語核、または核と呼ぶ
Lispの核
- nil、数、文字列は評価すると自身を返す
- シンボルの評価値はその時点での環境による
- nilでないリスト(後述の2つを例外とする)は第0要素を関数、残りの要素を引数とみなし、引数を左から順に評価したのち関数に渡して評価値を求める
- 第0要素が次のものであるリストの評価値の求め方は第0要素に依存する
quote cond setq prog progn prog1 prog2 go let let* if do do* defun defmacro function
- リストの第0要素がマクロの場合、まず第1要素以下が未評価のままマクロに渡される。マクロ本体が値を返してきたら、それを最初の場所で改めて評価する。
evalの定義
特殊形式の一覧などは...で省略している
(defun eval (form) (cond ; nil、数、文字列なら自身を返す ((or (null form) (numberp form) (stringp form)) form) ; シンボルなら変数と解釈し値を返す ((symbolp form) (variable-value form)) ; 以上はアトム。これより先へ進むのはセルだけ。 ; carが特殊形式の一覧にある要素なら特殊形式の処理へ ((member (car form) '(quote cond setq prog ...)) (eval-special-form form)) ; 関数呼び出し ; ラムダ式のとき ((and (consp (car form)) ; carがコンスセルで (eq (caar form) 'lambda)) ; caarがlambdaならラムダ式 ; 評価した引数をラムダ式にapply (apply (car form) (evlis (cdr form)))) ; 関数シンボルのとき ((function-symbol-p (car form)) ; 関数シンボル判定 (apply (symbol-function (car form)) ; 関数実体を取り出して (evlis (cdr form)))) ; 評価した引数をapply ; マクロ呼び出しのとき ((macro-symbol-p (car form)) ; マクロシンボル判定 (eval (apply (macro-function (car form)) (cdr form))) ) (t (error 'cannot-evaluate form)))) ;; 引数を順次評価してリストにして返す(実際はスタックに積むだけ) (defun evlis (args) (cond ((null args) nil) (t (cons (eval (car args)) (evlis (cdr args)))))) ;; 特殊形式の評価 (defun eval-special-form (form) (cond ((eq (car form) 'quote) (cadr form)) ((eq (car form) 'cond) (evcon (cdr form))) ... )) ;; cond節の評価 (defun evcon (clauses) (cond ((null clauses) nil) ((eval (caar clauses)) ; 述語が真 (evprogn (cdar clauses))) ; 暗黙のprogn (t (evcon (cdr clauses))))) ;; prognの評価 (defun evprogn (forms) (cond ((null forms) nil) ((null (cdr forms)) ; 最後のS式まで来た (eval (car forms))); 最後のS式の値を返す (t (eval (car forms)) (evprogn (cdr forms)))))
環境
- 各種の辞書やメモの寄せ集め
- 以下の2つに大別できる
- 変数の値を調べるための辞書(alistのリスト)
- シンボルが関数かマクロかを調べる辞書(シンボルの集合)
シンボルの内部構造をのぞく
(setq x '(1 2 3)) ;; シンボルの大域値 (symbol-value 'x) ; => (1 2 3) ;; シンボルの大域値変更 (set 'x "abc") ;; シンボルの大域値消去 (makunbound 'x)
関数実体についても同様に次のような関数が用意されているとする
(defun f (x) (* x x)) (symbol-function 'f) ; => (lambda (x) (* x x)) (set-symbol-function 'f '(lambda (x) (+ x x))) (fmakunbound 'f)
関数実体がマクロだったとき、lambdaの代わりにmacroと書かれたリストが返るものとする。
function-symbol-p macro-symbol-p macro-function
シンボルの内部構造が上記関数でのぞけるとすると、次の関数が定義できる。
(defun function-symbol-p (s) (let ((fb (and (symbolp s) ; andは真なら最後の評価値を返すので (symbol-function s)))) ; 関数実体がセットされる ; 関数実体が非nilでcarがlambdaならtが返る (and fb (eq (car fb) 'lambda)) )) (defun macro-symbol-p (s) ; function-symbol-pとほぼ同じ (let ((fb (and (symbolp s) (symbol-function s)))) (and fb (eq (car fb) 'macro)) )) (defun macro-function (s) (and (macro-symbol-p s) ; マクロシンボルのときだけ (symbol-function s))) ; symbol-functionを実行
defun defmacro
eval-special-form中cond節
((eq (car form) 'defun) (set-symbol-function ; 関数実体をセット (cadr form) ; setされるシンボル名 `(lambda ,(caddr form) ,@(cdddr form)))) ; 引数からラムダ式組み立て
defmacroもほぼ同じ。
変数のメモ
変数に値が束縛されるとき、alistによって変数と値が対応づけられると考える。たとえば
x = (1 2 3) y = nil
のとき
((x . (1 2 3)) (y . nil))
このalistはenvというリストに格納されており、新たに値が束縛されたときはenvの前の方にalistが追加されると考える。
シンボルの値を見つける
(局所的な)変数と値の対応付けをalistとして考えると、シンボルの値を見つける関数local-valueは次のように定義できる。
(defun local-value (s) (let ((sv (loc-val2 s env))) ; svにはシンボルと値のドット対が入る (cond (sv (cdr sv)) ; svが非nilならcdr(シンボルの値) (t 'no-value)))) ; svがnilのときは対応する値がない (defun loc-val2 (s e) (cond ((null e) nil) ; envが空ならnil ((assoc s (car e)) ; carのalistを探す(cond節は帰結部を省略すると述語の値を返す (t loc-val2 s (cdr e)))))) ; 次のalistを探す
variable-value apply
(defun variable-value (s) (let (localv globalv) ; 初期値を省略するとnilで初期化される (setq localv (loc-val2 s env)) ; 局所変数として探す (cond (localv (cdr localv)) ; 局所変数があるならそれを返す (t (setq globalv (symbol-value s)) ; 大域値を探す (cond ((neq globalv 'no-value) globalv) ; 値があった (t (error 'unbound-variable s)) ))))) ; 値が束縛(定義)されていない (defun loc-val2 (s e) (cond ((null e) nil) ((assoc s (cdar e))) ; envには変数を束縛している関数がタイトルとして入っているのでこれを取り除く (t (loc-val2 s (cdr e))) )) (defun apply (fn args) (cond ((function-symbol-p fn) ; fnが関数シンボル (eval-body-in-new-environment fn (symbol-function fn) args)) ;関数名 関数実体 引数 ((lambda-expression-p fn) ; fnがラムダ式のとき (eval-body-in-new-environment nil fn args)) ;関数名をnilに (t (error 'illegal-function fn)) )) ; マクロなどはapplyできない (defun eval-body-in-new-environment (title lambda args) (prog2 ; 二つ目のS式の値を返すprogn ; envに仮引数と実引数を対応付けるalistを足す (push (cons title (pairlis (cadr lambda) args)) env) (evprogn (cddr lambda)) ; 新しいenv(環境)中での関数本体の評価 (pop env) )) ; 評価が終わったら環境は元に戻す (defun pairlis (x y) ; xとyの各々の要素を対応付けたalistを返す (cond ((and x y) ; xもyも残っている (cons (cons (car x) (car y)) ; xとyのcar同士のドット対 (pairlis (cdr x) (cdr y)) ))))
setq
eval-special-form中のcond節
((eq (car form) 'setq) (let (localv) ; nil (setq localv (loc-val2 (cadr form) env)) ; 局所変数を探す (cond (localv ; 局所変数があった (rplacd localv (eval (caddr form))) ; 局所変数の値を書き換える (t (set-symbol-value ; 局所変数がなければ大域値 (cadr form) (eval (caddr form)) ))))))
