"ilya" <············@example.com> wrote in message ···························@lnews.actcom.co.il...
>
> (defun matcher (pat expr)
> (defun kern (pat expr dict)
===> (labels ((kern (pat expr dict)
Internal functions should use FLET or LABELS, DEFUN
puts the function in the global enviroment. LABELS
allows for recursion.
> (cond
> ((eq dict 'fail) dict)
> ((and (null pat) (null expr)) dict)
> ((and (atom (car pat)) (atom (car expr)))
> (when (equal (car pat) (car expr))
> (kern (cdr pat) (cdr expr) dict)))
> ((eq (caar pat) ':match-var)
===> ((eq (caar pat) :match-var)
Keywords are self-evaluating, the quote isn't necessary.
> (kern
> (cdr pat)
> (cdr expr)
> (extend-dict dict (cadar pat) (car expr))))
> ((eq (caar pat) ':match-rest)
> (extend-dict dict (cadar pat) expr))
> ((eq (caar pat) ':match-any)
> (kern (cdr pat) (cdr expr) dict))
> (t (kern
> (cdr pat)
> (cdr expr)
> (kern (car pat) (car expr) dict)))))
> (kern pat expr (empty-dict)))
I think you have a bit of work left ...
: (matcher '(a b c) '(a b c))
NIL ; OK
: (matcher '(a b c) '(a b d))
NIL ; FAIL?
: (matcher '((:match-var a)) '(b c))
NIL ; FAIL?
: (matcher '((:match-var a)(:match-var b)) '(c))
((B NIL) (A C)) ; FAIL?
..................
You might consider abstracting a bit more as you've
already done with the dictionary, you can change the
representation of pattern variables without changing
the pattern matcher.
For example, using
((match-var-p pat)
instead of
((eq (caar pat) :match-var)
and
(match-var-name pat)
instead of
(cadar pat)
where
(defun match-var-p(pat)
(and (listp pat) (listp (car pat)) ; just in case
(eq (caar pat) :match-var))
(defun match-var-name(pat) (cadar pat))
..................
If you recurse just a bit more you could cut CAAR and CADAR down
to CAR and CADR and eliminate :match-rest with a little trick, e.g.
(matcher '(:match-var a) '(b c)) ==> ((A (B C)))
(matcher '((:match-var a) :match-var b) '(c d e)) ==> ((B (D E)) (A C))
--
Geoff
"Geoffrey Summerhayes" <·······@NhOoStPmAaMil.com> wrote in message ····························@news20.bellglobal.com...
>
> You might consider abstracting a bit more as you've
> already done with the dictionary, you can change the
> representation of pattern variables without changing
> the pattern matcher.
> For example, using
> ((match-var-p pat)
> instead of
> ((eq (caar pat) :match-var)
> and
> (match-var-name pat)
> instead of
> (cadar pat)
> where
>
> (defun match-var-p(pat)
> (and (listp pat) (listp (car pat)) ; just in case
> (eq (caar pat) :match-var))
>
> (defun match-var-name(pat) (cadar pat))
>
Sorry, too tired when I wrote this, should be
((match-var-p (car pat))...
(match-var-name (car pat))
(defun match-var-p(pat)
(and (listp pat)) ; just in case
(eq (car pat) :match-var))
(defun match-var-name(pat) (cadr pat))
The CAR is definitely part of the way the matcher works,
not the variable.
--
Geoff
Hi.
Forgot to tell you about the "keys" issue.
I've got your point ( :xx = ':xx ) but i use VIM that have
syntax highlighting, ':xx is green and :xx is black ...
I dont want to mess with vim's sytax files for now
so i'll keep the ':xx notation.
ilya <············@example.com> wrote in message news:<······················@lnews.actcom.co.il>...
> Hi.
> Forgot to tell you about the "keys" issue.
> I've got your point ( :xx = ':xx ) but i use VIM that have
> syntax highlighting, ':xx is green and :xx is black ...
> I dont want to mess with vim's sytax files for now
> so i'll keep the ':xx notation.
I think this is a fine thing to do. I use unquoted keywords when they
are the keywords of keyword arguments, but quoted ones when they are
in a `normal evaluation' position. Yes, I know that the keywords of KW
args are just evaluated the ordinary way, but I can't think of a
better way to express what I mean. I guess an example:
(defun foo (&key (selector ':default))
(ecase selector
((:explode) "bang")
((:vomit) "puke")
((:default) "what?")))
(foo :selector ':vomit)
I do similar things for NIL and '() - NIL being false, '() being the
empty list.
Some people hate this, I know, and they probably also hate the quoted
keyword thing.
"Tim Bradshaw" <··········@tfeb.org> wrote in message
·································@posting.google.com...
>
> (foo :selector ':vomit)
>
> I do similar things for NIL and '() - NIL being false, '() being the
> empty list.
> Some people hate this, I know, and they probably also hate the quoted
> keyword thing.
I don't mind '(), though slightly prefer just () but I do hate ':keyword and
despise anyone who has ever done that.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
(ok, maybe that is a *little* too extreme ;)
"Coby Beck" <·····@mercury.bc.ca> wrote in message news:<·············@otis.netspace.net.au>...
> I don't mind '(), though slightly prefer just () but I do hate ':keyword and
> despise anyone who has ever done that.
Assassins have been dispatched...
--tim
"ilya" <············@example.com> wrote in message ···························@lnews.actcom.co.il...
> Hi.
> Forgot to tell you about the "keys" issue.
> I've got your point ( :xx = ':xx ) but i use VIM that have
> syntax highlighting, ':xx is green and :xx is black ...
> I dont want to mess with vim's sytax files for now
> so i'll keep the ':xx notation.
>
No problem, just wanted to make sure you were aware of it.
Part of the first version, part of the second, part mine :-(
;;;; variable handling
; (:match-any a) replaced by (:match-var) no variable name
(defun anonymous-var-p (var)
(= 1 (length var)))
(defun match-var-p (pat-item)
(and (listp pat-item)
(eq :match-var (car pat-item))))
(defun var-name(var)
(cadr var))
;;;; dictionary handling
; replaced dict as list-of-lists with list of cons/pairs
; save 1 cons cell per entry
(defun entry-var-name (x) (car x))
(defun entry-value (x) (cdr x))
(defconstant +empty-dict+ '())
(defconstant +failed-dict+ 'failed)
(defun failed-dict-p (dict)
(eq dict +failed-dict+))
(defun assoc-pat-var (var dict)
(assoc (var-name var) dict))
(defun add-to-dict (var var-value dict)
(cons (cons (var-name var) var-value) dict))
;;;; The matcher
(defun extend-dict (dict var var-value)
(if (anonymous-var-p var)
dict
(let ((m (assoc-pat-var var dict)))
(if m
(if (equal (entry-value m) var-value)
dict
+failed-dict+)
(add-to-dict var var-value dict)))))
; eliminated kern by making dict optional argument
; gives option to pass in a partial dict
(defun matcher (pat expr &optional (dict +empty-dict+))
;(format t "~&MATCHER: pat=~a expr=~a dict=~a~%" pat expr dict)
(cond
((failed-dict-p dict) dict)
((equal pat expr) dict)
((match-var-p pat)
(extend-dict dict pat expr))
((and (consp pat) (consp expr)); don't recurse when either is nil
(matcher
(car pat)
(car expr)
(matcher (cdr pat) (cdr expr) dict)))
(t +failed-dict+)))
--------------- Test run ----------------
const var any rest
(matcher '(1 (:match-var b) (:match-var) :match-var d) '(1 2 3 4 5 6))
MATCHER: pat=(1 (MATCH-VAR B) (MATCH-VAR) MATCH-VAR D) expr=(1 2 3 4 5 6) dict=NIL
MATCHER: pat=((MATCH-VAR B) (MATCH-VAR) MATCH-VAR D) expr=(2 3 4 5 6) dict=NIL
MATCHER: pat=((MATCH-VAR) MATCH-VAR D) expr=(3 4 5 6) dict=NIL
MATCHER: pat=(MATCH-VAR D) expr=(4 5 6) dict=NIL
MATCHER: pat=(MATCH-VAR) expr=3 dict=((D 4 5 6))
MATCHER: pat=(MATCH-VAR B) expr=2 dict=((D 4 5 6))
MATCHER: pat=1 expr=1 dict=((B . 2) (D 4 5 6))
((B . 2) (D 4 5 6))
--
Geoff
As far as LISP pattern matchers go, you may try the one I wrote,
as available on
http://tunes.org/cgi-bin/cvsweb/fare/fare/lisp/matcher.lisp
It can trivially express ML and Erlang type pattern matching,
AND it feels like a Lisp2 and is extensible in a typical Lisp way:
(defun my-length (x)
(ematch x
((cons _ tail) (1+ (my-length tail)))
('() 0)))
Notice how cons, being in head position, behaves like a match constructor,
whereas tail, being in rest position, behaves like a symbol to bind.
Quoting nil was not necessary, unless you specially define nil as
a symbol-matcher-macro (which I originally did, meaning failure,
whereas T was success, but recanted and used _ for success, and didn't
provide a standard syntax for the failure case, for who wants to build
a pattern that always fail? -- noone unless matcher-macros are used
to a considerable extent, and my matcher-macro infrastructure is primitive).
Here is a test battery for the pattern matcher:
(TTEST*
((my-length '(1 2 3)) :result 3)
((ifmatch (cons _ (cons x y)) '(1 (2 3) 4) (list x y)) :result '((2 3) (4)))
((ifmatch (like-when (cons x y) (eql x y)) '(2 . 2) x) :result 2)
((ifmatch (and (cons x y) (when (eql x y))) '(2 . 2) x) :result 2)
((ifmatch (and (cons a 1) (cons 2 b)) '(2 . 1) (list a b)) :result '(2 1))
((ifmatch (list a b) '(1 2) (list b a)) :result '(2 1))
((ifmatch (list* a b c) '(1 2 3 4) (list a b c)) :result '(1 2 (3 4)))
((ifmatch (and x (cons (of-type integer) _)) '(2) x) :result '(2))
((let ((res 2))
(ifmatch (cons 'reply (cons (value (+ 1 res)) (cons msg 'nil)))
'(reply 3 foo) (list res msg)))
:result '(2 FOO))
((let ((res 2))
(ifmatch (list 'reply (value (+ 1 res)) msg) '(reply 3 foo)
(list res msg)))
:result '(2 FOO)))
Note how you can build patterns that match dynamically-computed values.
Together with my quasiquote reimplementation, you can easily match patterns
that mix constants and litterals, like
(ifmatch
`(send ,msg ,@args)
'(send foo bar baz)
(list msg args))
==> (foo (bar baz))
I find it very practical to write rewrite rules.
[ Fran�ois-Ren� �VB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]
"Don't worry about people stealing your ideas. If your ideas are any good,
you'll have to ram them down people's throats." -- Howard Aiken
Francois-Rene Rideau wrote:
> As far as LISP pattern matchers go, you may try the one I wrote,
> as available on
> http://tunes.org/cgi-bin/cvsweb/fare/fare/lisp/matcher.lisp
Sorry, to complicated for beginner that doesn't have much time ...
>
> It can trivially express ML and Erlang type pattern matching,
> AND it feels like a Lisp2 and is extensible in a typical Lisp way:
> (defun my-length (x)
> (ematch x
> ((cons _ tail) (1+ (my-length tail)))
> ('() 0)))
>
> Notice how cons, being in head position, behaves like a match constructor,
> whereas tail, being in rest position, behaves like a symbol to bind.
> Quoting nil was not necessary, unless you specially define nil as
> a symbol-matcher-macro (which I originally did, meaning failure,
> whereas T was success, but recanted and used _ for success, and didn't
> provide a standard syntax for the failure case, for who wants to build
> a pattern that always fail? -- noone unless matcher-macros are used
> to a considerable extent, and my matcher-macro infrastructure is primitive).
>
> Here is a test battery for the pattern matcher:
> (TTEST*
> ((my-length '(1 2 3)) :result 3)
> ((ifmatch (cons _ (cons x y)) '(1 (2 3) 4) (list x y)) :result '((2 3) (4)))
> ((ifmatch (like-when (cons x y) (eql x y)) '(2 . 2) x) :result 2)
> ((ifmatch (and (cons x y) (when (eql x y))) '(2 . 2) x) :result 2)
> ((ifmatch (and (cons a 1) (cons 2 b)) '(2 . 1) (list a b)) :result '(2 1))
> ((ifmatch (list a b) '(1 2) (list b a)) :result '(2 1))
> ((ifmatch (list* a b c) '(1 2 3 4) (list a b c)) :result '(1 2 (3 4)))
> ((ifmatch (and x (cons (of-type integer) _)) '(2) x) :result '(2))
> ((let ((res 2))
> (ifmatch (cons 'reply (cons (value (+ 1 res)) (cons msg 'nil)))
> '(reply 3 foo) (list res msg)))
> :result '(2 FOO))
> ((let ((res 2))
> (ifmatch (list 'reply (value (+ 1 res)) msg) '(reply 3 foo)
> (list res msg)))
> :result '(2 FOO)))
>
> Note how you can build patterns that match dynamically-computed values.
>
> Together with my quasiquote reimplementation, you can easily match patterns
> that mix constants and litterals, like
> (ifmatch
> `(send ,msg ,@args)
> '(send foo bar baz)
> (list msg args))
> ==> (foo (bar baz))
>
> I find it very practical to write rewrite rules.
>
> [ Fran�ois-Ren� �VB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
> [ TUNES project for a Free Reflective Computing System | http://tunes.org ]
> "Don't worry about people stealing your ideas. If your ideas are any good,
> you'll have to ram them down people's throats." -- Howard Aiken
Thanks.
I'll get to it back later, after i learn macros :)
"ilya" <············@example.com> wrote in message ···························@lnews.actcom.co.il...
*random-snippage*
| Geoffrey Summerhayes wrote:
| [snip]
| >
| > Part of the first version, part of the second, part mine :-(
| >
| > ;;;; variable handling
| >
| > ; (:match-any a) replaced by (:match-var) no variable name
| >
| > (defun anonymous-var-p (var)
| > (= 1 (length var)))
| Alternative (good?):
| :match-any,anonymous-var-p can be excluded
| the (match-any-p pat) check in kern too
| and the dictionary handling changed to something like:
:MATCH-ANY isn't necessary in any case, all you have to
do is replace it with a named variable that is only used once
and ignored otherwise, although it would then pad the dict.
| (extend-dict (dict var-name var-value)
| (if var-name
| (let ((m (assoc var-name (cdr dict))))
| (if m
| (if (equal (cadr m) var-value)
| dict
| (make-failed-dict-from-normal dict))
| (cons t (cons (list var-name var-value) (cdr dict)))))
| dict))
It still mixes levels, I'd be more inclined to eliminate calling
#'VAR-NAME from the entire set of functions and adding :TEST #'EQUAL
to the ASSOC for reasons that follow. Writing EXTEND-DICT so it is
independent of what a variable or a dictionary looks like:
(defun extend-dict (dict var value)
(if (anonymous-var-p var)
dict
(let ((entry (assoc-pat-var var dict)))
(if entry
(if (equal (entry-value entry) value)
dict
(make-failed-dict))
(add-to-dict var value dict)))))
Examples for the helpers which do know:
;; dict as list
(defun assoc-pat-var (var dict)
(find var dict :key #'entry-var :test #'equal))
(defun add-to-dict (var value dict)
(cons (make-entry var value) dict))
;; dict as hash-table
(defun assoc-pat-var (var dict)
(make-entry var (gethash var dict)))
(defun add-to-dict (var value dict)
(setf (gethash var dict) value))
Note they are independant of what an entry looks like, they
just know the dict. This is probably overkill, it depends
a lot on how much you are willing to rewrite if you change
representations.
| >
| > ; replaced dict as list-of-lists with list of cons/pairs
| > ; save 1 cons cell per entry
| That would definitely save memory but i don't like dots :)
Better get used to them anyway, they're useful.
Watch this.
(matcher '(1 (:match-var b) (:match-var) :match-var d) '(1 2 3 4 5 6))
is the same as
(matcher '(1 (:match-var b) (:match-var) . (:match-var d)) '(1 2 3 4 5 6))
So we could do
(defun var-name (var) var) ; was it ever really required?
(defun match-var-p (pat-item)
(and (symbolp pat-item)
(char= #\? (char (symbol-name pat-item) 0))))
(defun anonymous-var-p (var)
(eq var '?_))
Now we can do
(matcher '(1 ?b ?_ . ?d) '(1 2 3 4 5 6))
which, IMO, is more readable. EXTEND-DICT works for either
representation without changes.
| >
| > ;;;; The matcher
| >
| > (defun extend-dict (dict var var-value)
| > (if (anonymous-var-p var)
| > dict
| > (let ((m (assoc-pat-var var dict)))
| > (if m
| > (if (equal (entry-value m) var-value)
| > dict
| > +failed-dict+)
| Hei, that was your idea to return partially matched dicts
| even if the whole match fails ...
| As i understand this variant wouldn't.
Not my idea, a failed match is a failed match, AFAIC.
Your original code did return dicts for patterns that
I would have considered a failed match though.
| > (add-to-dict var var-value dict)))))
| >
| > ; eliminated kern by making dict optional argument
| > ; gives option to pass in a partial dict
| That can be useful, i suppose.
|
| > (defun matcher (pat expr &optional (dict +empty-dict+))
The main point was just to avoid the extra nesting. The
additional capability was a side-effect. Its usefulness
is probably limited to anaphors.
<daydream>
PARSER> multiply 3 4 and 5
(* 3 4 5)
PARSER> add 6
(+ 6 (* 3 4 5))
PARSER> what do you get?
66
PARSER> I have a ball.
You have a ball.
PARSER> It is red.
You have a red ball.
</daydream>
--
Geoff
Even better:
On Thu, Jan 30, 2003 at 04:07:08PM -0500, Geoffrey Summerhayes wrote:
> <daydream>
> PARSER> I have a ball.
Have a ball.
> </daydream>
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
"Matthew Danish" <·······@andrew.cmu.edu> wrote in message ··························@lain.cheme.cmu.edu...
> Even better:
>
> On Thu, Jan 30, 2003 at 04:07:08PM -0500, Geoffrey Summerhayes wrote:
> > <daydream>
> > PARSER> I have a ball.
> Have a ball.
> > </daydream>
>
One-upmanship, eh?
PARSER> I have Lisp.
Have a ball.
--
Geoff