<div>Hi</div><div><br></div><div>I wrote a matching pattern (recursive) function and would like to share it;</div><div>it is still work in progress (some bugs are expected to show up anytime)</div><div> </div>
<div>I started with the destruc function found in onLisp book by Paul Graham. </div><div> </div>
<div>The following is a draft of a poor doc and some examples of usage:</div><div><br></div><div>; variables: untyped :x, typed (:var x (integer 0 9)) </div>
<div> </div><div>keywords :var :all :lone, :some, :not, :or, :and, :type, :match, this </div>
<div> </div><div>pattern == _ | (:all pattern) | (:lone pattern) | (:not pattern) </div>
<div> | (:some pattern pattern) | (:var var pattern) | keyword </div><div> | (:or pattern pattern) | (:type primitive-pattern) </div>
<div> | literal | ( pattern* ) | this | (:match pattern) </div><div> where _ matches anything (any lisp element) </div>
<div> this is a recursive reference to the current matching pattern </div><div> :match starts a new matching pattern for the current element </div>
<div> keyword is a variable (ie. :x is equivalent to (:var x _)) </div><div> primitive-pattern == lisp types (eg. integer, number, consp, ...) </div>
<div> literal == lisp atoms (number, string, symbol, ...) </div><div> </div>
<div> :x == (:var x _) </div><div> _ == (:type t) </div>
<div> (pattern1 (:lone pattern2) pattern3) == (:or (pattern1 pattern2 pattern3) (pattern1 pattern3)) </div><div> (:some pattern (:type null)) == (:all pattern) </div>
<div> (match '(1 2 3 . 4) ((:all (:type integer)) 'ok)) -> NIL fails because of the dotted list </div><div> :all matches a sequence (:some can match any list as shown below) </div>
<div> (match '(1 2 3 . 4) ((:some (:type integer) (:var x (:type integer))) x)) -> 4 </div><div> (match '(1 2 A . 4) ((:some (:type integer) (:var x _)) x)) -> (X . 4) </div>
<div> (match '(a b c) (('a (:lone 'b) 'c) 'ok)) -> OK </div><div> (match '(a c) (('a (:lone 'b) 'c) 'ok)) -> OK </div>
<div> (match 3 ((:not (:type integer)) 'ok)) ; match a non integer </div><div> -> NIL </div>
<div><div> (:not (_ . _)) == (:not (:type consp)) ; match an atom </div><div> (match '(1 2 3 4) ((:all (:type integer)) 'ok)) -> OK </div>
<div> (match '((a 1) (b foo) (c ok)) ((:all (:var val ((:var key (:type symbol)) _))) (list val key))) </div><div> -> ((C OK) C) </div>
<div> (match '((a 1) (b 2) (c 3)) ((:all ((:var x (:type symbol)) (:var y (:type integer)))) (list x y))) </div><div> -> (C 3) </div>
<div> ? (match '(1 (2 2 2) 3) ((:x (:var y (:match (:or (:type null) (2 . this)))) :z) (values x y z))) </div><div>1 </div>
<div>(2 2 2) </div><div>3 </div>
<div>**** (:some _) is problematic (implement rollback?) </div><div> currently we have (:some _) == (:all _) </div>
<div> *** in general in ((:some p1) p2), p1 and p2 must be incompatible </div><div> that is if x is matched by p2 then x must not be matched by p1 </div>
<div> </div><div>? (defun member? (x e) (match e ((:or (:var r (x . _)) (_ . this)) r))) </div>
<div>MEMBER? </div><div>? (member? 'x '(a b x c)) </div>
<div>(X C) </div></div><div><div>? (member? 'x '(a b c)) </div>
<div>NIL </div><div>? (member? '(1 2) '(a (1 2) b))</div><div>((1 2) B)</div><div> </div>
<div>20120729: TODO convert a regular expression to a pattern </div><div> "a*" -> (:lone ((:all #\a))) </div>
<div> "a*b" -> ((:lone (:some #\a)) #\b) </div><div> many difficulties are to expect (eg. ".*H" -> ((:some _) #\H) </div>
<div> some consumes all characters and the match fail because of end of inputs and we still have #\H to read </div></div><div><br></div><div><br></div><div>I am currently using the match macro to implement a simple lambda calculs interpreter (normal order, lazy, untyped)</div>
<div><br></div><div>For example the full beta reduction is as follows:</div><div><br></div><div><div>(defun fv? (e u)</div><div> "(member u (fv e))"</div><div> (match e</div><div> ((:var v (:type atom))</div>
<div> (eq u v))</div><div> (('fn :v :e0)</div><div> (and (not (eq u v)) (fv? e0 u)))</div><div> ((:e0 :e1)</div><div> (or (fv? e0 u) (fv? e1 u)))</div><div> (_ (error "fv?: invalid syntax"))))</div>
<div><br></div><div>(defun br (eb v ea &optional (i 0))</div><div> "beta-reduction (in-place version)"</div><div> (format t "~Abr: ~S ~S ~S~%" (%cars i) eb v ea)</div><div> (let ((r</div><div> (match eb</div>
<div> (v ea)</div><div> ((:or (:type atom) ('fn v _)) eb)</div><div> (('fn :u :e0)</div><div> (if (not (and (fv? ea u) (fv? eb v)))</div><div> (progn</div><div> (setf (third eb) (br e0 v ea (1+ i)))</div>
<div> eb)</div><div> (let ((w (gensym)))</div><div> (setf (third eb) (br (br e0 u w (1+ i)) v ea (1+ i)))</div><div> (setf (second eb) w)</div><div> eb)))</div>
<div> ((:e0 :e1)</div><div> (setf (first eb) (br e0 v ea (1+ i)))</div><div> (setf (second eb) (br e1 v ea (1+ i)))</div><div> eb)</div><div> (_ (error "br: invalid syntax")))))</div>
<div> (format t "~Arbr r:~A~%" (%cars i) r)</div><div> r))</div></div><div><br></div><div><br></div><div>Kind regards</div><div>Taoufik</div><div><br></div><div><br></div>