「lisp勉強８日目記号のパターンマッチング」の編集履歴（バックアップ）一覧に戻る

lisp勉強８日目記号のパターンマッチング - (2012/08/10 (金) 18:00:41) のソース

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))));アトムが出てきたので次へ進む