Match.lsp
Original Version
CAAR = (car (car lst)) = (first (first lst))
CADAR = (car (cdr (car lst))) = (first (rest (first lst)))

;Match

; MATCH.LSP -- a recursive pattern-matching function
;	for use in production-systems programming.
(DEFUN MATCH
 (P S)
  (COND
  ((NULL P)(NULL S))                  ;case with both P and S null
                                      ;from here on we can
                                      ; assume P is not null.


  ((ATOM (CAR P))                     ;case when CAR P is an atom
   (AND S                             ;S must not be null.
		(EQUAL (CAR P) (CAR S))
		(MATCH (CDR P) (CDR S)) ) )
                                      ;from here on CAR of P is non atomic.

  ((AND                               ;case when P starts with ? form.
    S                                 ;S must not be null.
		(EQ (CAAR P) '?) )
   (COND  ((MATCH (CDR P)(CDR S))     ;rest much match, too.
		 (SET (CADAR P) (CAR S)) 
		 T)
		(T NIL) ) )

  ((EQ (CAAR P) '*)                   ;case when P starts with * form.
	 (COND
    ((AND S (MATCH (CDR P)(CDR S)))   ;subcase 1
		 (SET (CADAR P) (LIST (CAR S))) T)

    ((MATCH (CDR P) S)                ;subcase 2
		 (SET (CADAR P) NIL) T)

    ((AND S (MATCH P (CDR S)))        ;subcase 3
		 (SET (CADAR P) (CONS (CAR S)(EVAL (CADAR P)))) T)

		(T NIL) ) )

  ((AND                               ;case when P starts with predicate form.
    S                                 ;S must not be null.
		(APPLY (CAAR P) (LIST (CAR S)))
		(MATCH (CDR P) (CDR S)) )
	 (SET (CADAR P)(CAR S)) T)

	(T NIL)
 ) )