I have a compiling matcher I've written that takes a pattern and
returns a LAMBDA expression which performs the actual match.
Here is an example: (MCL2 prompts with a "?")
;;; Match a pattern and datum using the interpretive matcher
? (Match '(a ?x c) '(a b c))
((?X . B))
;;; It matches with one variable binding.
;;; Now compile the pattern into a LAMBDA using compiling matcher
? (Compile-Match '(a ?x c))
(LAMBDA (DATUM ...) [...a bunch of code deleted...] )
? (SETF *p* *) ; save pattern code in a variable
? (SETF *d* '(a b c)) ; set datum variable
Now that I've got the LAMBDA in the variable *p*, how can I do
anything with it? I can't FUNCALL or APPLY it. But I can
use a really ugly EVAL as follows:
? (EVAL `(,*p* ',*d*))
((?X . B))
This works okay, but yucko!
Anybody got any better ideas?
Thanks.
Danny Brewer
·····@farallon.com
In article <··················@danny.farallon.com> ·····@farallon.com (Danny Brewer) writes:
;;; Now compile the pattern into a LAMBDA using compiling matcher
? (Compile-Match '(a ?x c))
(LAMBDA (DATUM ...) [...a bunch of code deleted...] )
? (SETF *p* *) ; save pattern code in a variable
? (SETF *d* '(a b c)) ; set datum variable
Now that I've got the LAMBDA in the variable *p*, how can I do
anything with it? I can't FUNCALL or APPLY it. But I can
use a really ugly EVAL as follows:
? (EVAL `(,*p* ',*d*))
((?X . B))
This works okay, but yucko!
(eval `#',*p*) will return a function. In cltl2 lisps, you can coerce
the lambda expression returned by compile-match to a function:
(coerce *p* 'function)
These solutions use eval explicitly or implicitly, but that's OK. eval
was made for this sort of thing. If you are translating little
languages to lisp code, the prohibition against using eval breaks
down.
You could compile the lambda expression:
(compile nil *p*)
Alternatively, you could think about defining your patterns in a
declarative manner so that the lambda expressions will be dealt with
at compile or load time:
(defmacro defpattern (pattern)
`(eval-when (:compile-toplevel :execute)
(add-pattern-to-db ,pattern #',(compile-match pattern))))
--
Tim Moore ·····@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Wind in my hair - Shifting and drifting - Mechanical music - Adrenaline surge"
- Rush
Thanks to everyone who responded with postings or email.
The solution I liked best was (COMPILE NIL *p*) to produce a
function that can be FUNCALLed.
I could see from several emails that I should have been more
clear in my original posting about the fact that I cannot
simply put #' in front of a LAMBDA in the pattern compiler
and return a closure. There is no LAMBDA embedded within
the compiler that is returned. The returned LAMBDA list
is actually "computed" from the pattern and can vary
greatly due to the fact that the matchers support nested
patterns, anonymous variables, segment matching and pattern
directives.
Since I got such a satisfying solution to my first ugly EVAL,
here's another place I've used EVAL and wonder if there is
an alternative. (Note all of the following discussion applies
to the interpretive matcher, the compiling matcher simply compiles
function names or LAMBDAs into the resulting LAMBDA expression.
The interpretive matcher EVAL's them.)
The pattern directives can contain predicates. For example:
(Match '(a (?:* ?x) (?:? ?n NUMBERP) (?:* ?y) (?:+ ?z SUBSETP '(a b c)))
'(a b c d 5 e f g a b a c b))
which results in the bindings:
((?Z A B A C B) (?Y E F G) (?N . 5) (?X B C D))
The pattern means:
Match an 'a
followed by zero or more items,
followed by a number,
followed by zero or more items,
followed by one or more items, all of which must be SUBSETP of '(a b c)
Other pattern directive examples would be:
(?:? ?x > 5)
(··@ ?_ CONSP)
(?:? ?str STRINGP)
(?:? ?n = *PRINT-BASE*)
(?:* ?items (LAMBDA (items) (SUBSETP (INTERSECTION items *x*) *y*)))
The last example would match some items which when intersected with
the special variable *x* are a subset of special variable *y*.
Basically, the third item can be the name of a function (or LAMBDA),
and additional arguments can be given, such as the > function being
given the argument 5 to test if ?x > 5 in the first example.
I use the following function to see if the pattern directive can
match a potential value...
(DEFUN Call-Predicate (patternDirective potentialValue)
"Call the predicate of the pattern directive to see if the value is
okay."
(COND
;; Is there a predicate to test?
((PatDir-Predicate? patternDirective)
(EVAL `(,(PatDir-Predicate patternDirective)
',potentialValue
,@(PatDir-Params patternDirective))))
;; If no predicate to call, then return T
(T)
))
(DEFUN PatDir-Predicate (pattern-directive)
(THIRD pattern-directive))
(DEFUN PatDir-Params (pattern-directive)
(CDDDR pattern-directive))
In the interpreter it is probably not wise to spend the time compiling
the predicate function (or LAMBDA) and then applying it to the
potential value and other params. Is there any better solution than
using this ugly backquoted EVAL?
If I were going to match the pattern more than once I would use the
pattern compiler. When the pattern interpreter is being used, the
pattern is probably being matched one time only.
BTW, I plan on posting these matchers to the cambridge.apple.com ftp
site sometime in the future.
Danny Brewer
·····@farallon.com
In article <··················@danny.farallon.com> ·····@farallon.com (Danny Brewer) writes:
>Other pattern directive examples would be:
...
> (?:* ?items (LAMBDA (items) (SUBSETP (INTERSECTION items *x*) *y*)))
>
>The last example would match some items which when intersected with
>the special variable *x* are a subset of special variable *y*.
I suggest that you require the user to supply the actual function object in
that case. He can do this by using backquote to construct the pattern that
he supplies to MATCH:
(match `((?:* ?items ,#'(lambda (items) (subsetp intersection items *x*) *y*)))
data)
Besides solving your problem of having to use EVAL or COMPILE to execute
it, it also allows the user to supply a local function (i.e. one defined
using FLET or LABELS), an expression that evaluates to a function, or a
lexical closure, e.g.
(defun example (data predicate)
(flet ((local-predicate (items) (every #'numberp items)))
(match `((?:* ?x ,predicate) (?:* ?y ,#'local-predicate)
(?:* ?z ,#'(lambda (items) (member (car (last items)) '(a b c)))))
data)))
In all these cases, you can use FUNCTIONP to detect that the third element
of the list is a function (note, however, that CLtL1 specified that
FUNCTIONP is true for all symbols, even if they don't have function
bindings, so you should check this case after most others).
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <··················@danny.farallon.com> ·····@farallon.com
(Danny Brewer) writes:
? (Compile-Match '(a ?x c))
(LAMBDA (DATUM ...) [...a bunch of code deleted...] )
? (SETF *p* *) ; save pattern code in a variable
? (SETF *d* '(a b c)) ; set datum variable
Now that I've got the LAMBDA in the variable *p*, how can I do
anything with it? I can't FUNCALL or APPLY it.
You can funcall the lambda expression by coercing it to FUNCTION first
(this is only necessary in ANSIfied Common Lisps):
(funcall (coerce *p* 'function) *d*)
...but this is really very equivalent to using EVAL.
Or you can force compilation of the code using COMPILE:
(funcall (compile nil *p*) *d*)
In this case you would probably save the result of the COMPILE
somewhere because compilation makes most sense when you reuse the
compiled matcher for many operations.
--
Simon.