lisp勉強８日目記号のパターンマッチング - c21coterie @ ウィキ

http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp22.html
今日の勉強はLispによる記号のパターンマッチングの解説ページの分析。
lispで理解しようとすると混乱したのでc++で同じコードを書くとどうなるかと考えて理解してみた。
束縛変数をstd::mapに入れて管理すると考えるとmatch-variableはmapのfind処理と同じである。

(defun variablep (pattern)
 (and (symbolp pattern);シンボルであるか
      (char= #\? (char (string pattern) 0))));束縛変数であるか
variablep
;
; 変数束縛に追加する
;
(defun add-binding (var value binding)
  (cons (cons var value) binding));束縛変数だけのリストvarは要素一個
add-binding
;
; パターンマッチング : datum に変数は無し
;
(step (defun match (pattern datum binding)
 (cond ((variablep pattern);patternをcarとcdrで分解した結果束縛変数のアトムが出てきたら
        (match-variable pattern datum binding));一度束縛変数に対応するvalueを呼び出してもう一度matchが呼ばれる
       ((and (atom pattern) (atom datum));アトム同士なら
        (match-atoms pattern datum binding));アトムが比較される、束縛変数は上の処理で一度valueに直される
       ((and (consp pattern) (consp datum))
        (match-pieces pattern datum binding));まだアトムが出てこないので与えられたpatternとdatumを分解してい
(t 'fail))))
match


;
; 変数とのマッチング
;
(defun match-variable (var datum binding);Ｃ++でいえば束縛変数をstd::mapに入れていくのと同じ
 (let ((value (assoc var binding)));mapのfindと同じ処理
   (if value
       ; 値を使ってもう一度チェック
       (match (cdr value) datum binding);束縛変数はもう出ているのでkeyに対するvalueを返し束縛変数をvalueにおきかえてmatchをもう一度呼ぶ
       ; 変数束縛に追加する
       (add-binding var datum binding))));束縛変数をkeyとＶalueを設定する
match-variable


;
; アトム同士のマッチング
;
(defun match-atoms (pattern datum binding)
  (if (equal pattern datum) binding 'fail));要素同士の比較、束縛変数なら一度std::mapから値が取り出されてからこの関数に移行する
match-atoms

  

;
; リスト同士のマッチング
;
(defun match-pieces (pattern datum binding)
  (let ((result (match (car pattern) (car datum) binding)));アトムが出てくるまで分解する
    (if (eq result 'fail)
        'fail
        (match (cdr pattern) (cdr datum) result))));アトムが出てきたので次へ進む