Standard lisp/scheme convention is to use #\? (the question mark) to
denote logic variables when pattern matching sexps [1] [2] [3] [4].
So
FOO
is a symbol
?FOO
is a logic variable and
?
denotes the "wildcard" that matches anything (sometimes ?? is used).
I usually use #\$ (the dollar sign) instead, to make them visually
stand out against scheme-
style predicates (ie USER? instead of USERP).
So:
$FOO
is a logic variable
$
is the wildcard.
I've also seen the practice of using quoted symbols to denote symbols
and non-quoted symbols to denote variables [5]:
'FOO
is a symbol and
FOO
is a variable
I recently packaged a pattern matcher I made for another project into
it's own system [6] and at the last second I changed the default log
var behavior from #\$ to #\? to #\_ (the underscore) to make it look
more like erlang/prolog/haskell. So:
_FOO
is a variable and
_
is the wildcard.
but I think was a mistake now because it looks bad. Personally I'm
still using #\$ but I'm wondering if I should change the default back
to #\?.
Nick
[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%25_idx_5116
[2] http://norvig.com/paip/patmatch.lisp
[3] http://www.bookshelf.jp//texi/onlisp/onlisp_20.html#SEC122
[4] http://franz.com/support/documentation/8.0/doc/prolog.html
[5] http://toute.ca/termite.pdf
[6] http://common-lisp.net/project/bpm/
On Nov 4, 8:36 pm, ········@gmail.com wrote:
> but I think was a mistake now because it looks bad. Personally I'm
> still using #\$ but I'm wondering if I should change the default back
> to #\?.
In Prolog etc. an underscore at the beginning of the name of the
variable indicates an anonymous variable---you may want to have a
named anonymous variable (yeah, I know it sounds stupid) for
readability's sake. Because of that, using an underscore as a logical
variable indicator is a BAD idea.
'?' is quite a common symbol, and may bring unwanted associations. I
would opt for $.
Finally, right now your notation is inconsistent, because most logical
variables begin with the magic prefix, except the anonymous one.
To sum it up: logical variables should star with $, make the anonymous
variable look like $_ (this also continues the great tradition of Perl
of associating magical meaning to that string). $_foo should also be
an anonymous variable.
Cheers,
-- Richard
> To sum it up: logical variables should star with $, make the anonymous
> variable look like $_ (this also continues the great tradition of Perl
> of associating magical meaning to that string). $_foo should also be
> an anonymous variable.
yes, I like this. AND SO IT SHALL BE ;-)
Nick
Hi
Both the #\? and the #\$ have been used as "logical variable
indicators" in several Lisp-based logic manipulation programs.
Therefore either will work. You do not want to use the QUOTE operator
for this sort of things as you may end up conflating semantic issues,
but then again YMMV.
In CL-UNIFICATION (shameless plug: http://common-lisp.net/project/cl-unification/:
it's missing from your list! :) ) I use #\? as a prefix (not even as a
macro-character) and the symbol _ as the "any" variable. The
alternative/complement is to keep a set of declared symbols (or
expressions if you really want to be fancy) to recognize as logical
variables; at that point you may as well get the universal and
existential operators back in the picture, otherwise, you *have* to go
the Prolog way and use some special syntax to denote logical
variables.
Cheers
Marco
On Nov 4, 9:36 pm, ········@gmail.com wrote:
> Standard lisp/scheme convention is to use #\? (the question mark) to
> denote logic variables when pattern matching sexps [1] [2] [3] [4].
>
> So
>
> FOO
>
> is a symbol
>
> ?FOO
>
> is a logic variable and
>
> ?
>
> denotes the "wildcard" that matches anything (sometimes ?? is used).
>
> I usually use #\$ (the dollar sign) instead, to make them visually
> stand out against scheme-
> style predicates (ie USER? instead of USERP).
>
> So:
>
> $FOO
>
> is a logic variable
>
> $
>
> is the wildcard.
>
> I've also seen the practice of using quoted symbols to denote symbols
> and non-quoted symbols to denote variables [5]:
>
> 'FOO
>
> is a symbol and
>
> FOO
>
> is a variable
>
> I recently packaged a pattern matcher I made for another project into
> it's own system [6] and at the last second I changed the default log
> var behavior from #\$ to #\? to #\_ (the underscore) to make it look
> more like erlang/prolog/haskell. So:
>
> _FOO
>
> is a variable and
>
> _
>
> is the wildcard.
>
> but I think was a mistake now because it looks bad. Personally I'm
> still using #\$ but I'm wondering if I should change the default back
> to #\?.
>
> Nick
>
> [1]http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%25_idx_...
> [2]http://norvig.com/paip/patmatch.lisp
> [3]http://www.bookshelf.jp//texi/onlisp/onlisp_20.html#SEC122
> [4]http://franz.com/support/documentation/8.0/doc/prolog.html
> [5]http://toute.ca/termite.pdf
> [6]http://common-lisp.net/project/bpm/
> In CL-UNIFICATION (shameless plug:http://common-lisp.net/project/cl-unification/:
> it's missing from your list! :) )
ah yes, how cold I have forgotten? I took a look at cl-unification
before writing my own matcher, it wasn't exactly what I was looking
for. it is cool though :-)
On Nov 5, 11:36 pm, ········@gmail.com wrote:
> > In CL-UNIFICATION (shameless plug:http://common-lisp.net/project/cl-unification/:
> > it's missing from your list! :) )
>
> ah yes, how cold I have forgotten? I took a look at cl-unification
> before writing my own matcher, it wasn't exactly what I was looking
> for. it is cool though :-)
Well, thanks. But CL-UNIFICATION does all the patterns of BPM and
many, many more, e.g. CLOS and DEFSTRUCT instances (plus, of course,
full blown unification).
What you added is the "compiler" for a pattern. It could be easily
added to CL-UNIFICATION as well.
Cheers
--
Marco
········@gmail.com writes:
> Standard lisp/scheme convention is to use #\? (the question mark) to
> denote logic variables when pattern matching sexps [1] [2] [3] [4].
>
> So
>
> FOO
>
> is a symbol
>
> ?FOO
>
> is a logic variable
I worry about quoting issues. Suppose I wish to process data
containing symbols such as ?FOO. I might want to use my
pattern matcher to distinguish bewteen (?x 3) and (?y 4). So
I write (?x ?x) ;pick out tentative x-coordinate. Whoops I
need some way of quoting the first ?x to say that it is a
literal.
The idea that I have been playing with assumes that one
usually has several patterns, and that it is therefore a
small overhead to list the logic variables separately. So a
crude simplifier might look like
(pattern-case form (x)
(+ x 0) => x
(* x 0) => 0
(* x 1) => x)
Suppose that the imp of the perverse has struck one a fatal
blow:forcing one to use `x' as times, instead of `*'. How is
(pattern-case form (x)
(+ x 0) => x
(x x 0) => 0
(x x 1) => x)
to be rescued?
Since you must decide the literal elements of the pattern
when you are writing the code, you can always change the
variable names to miss them
(pattern-case form (n)
(+ n 0) => n
(x n 0) => 0
(x n 1) => 1)
Sometimes you want a logic variable to be restricted so that
it will only match a datum of a particular type. Embedding
the type restriction in the pattern knocks the pattern out
of shape. Attach it to the name-declaration instead.
(pattern-case form ((n number)(m number) y z)
(+ n m y) => `(+ ,(+ n m) y)
(+ n y m) => `(+ ,(+ n m) y)
(+ y n z) => (+ n y z))
There are other notations beyound type restrictions that
could usefully go in the name-declaration, such as a
predicate that matched data must satisfy, or the equality
test to be used when duplication of a variable is used to
indicate that a datum must be duplicated in a pattern.
These are interesting ideas, but perhaps a bit of a
distraction if one has code to write.
Alan Crowe
Edinburgh
Scotland
>
> I worry about quoting issues. Suppose I wish to process data
> containing symbols such as ?FOO. I might want to use my
> pattern matcher to distinguish bewteen (?x 3) and (?y 4). So
> I write (?x ?x) ;pick out tentative x-coordinate. Whoops I
> need some way of quoting the first ?x to say that it is a
> literal.
yeah, for the general pattern matcher (bpm) it's a matter of assigning
or binding *LOGIC-VAR-PREFIX-CHAR*, *LOGIC-VAR-PRED*, or *LOGIC-VAR-
WILDCARD-PRED* before compiling your code. for the actual code walking
stuff there's a different syntax that lends itself more towards
changing this stuff on the fly.
>
> The idea that I have been playing with assumes that one
> usually has several patterns, and that it is therefore a
> small overhead to list the logic variables separately. So a
> crude simplifier might look like
>
> (pattern-case form (x)
> (+ x 0) => x
> (* x 0) => 0
> (* x 1) => x)
>
> Suppose that the imp of the perverse has struck one a fatal
> blow:forcing one to use `x' as times, instead of `*'. How is
>
> (pattern-case form (x)
> (+ x 0) => x
> (x x 0) => 0
> (x x 1) => x)
>
> to be rescued?
>
> Since you must decide the literal elements of the pattern
> when you are writing the code, you can always change the
> variable names to miss them
>
> (pattern-case form (n)
> (+ n 0) => n
> (x n 0) => 0
> (x n 1) => 1)
>
> Sometimes you want a logic variable to be restricted so that
> it will only match a datum of a particular type. Embedding
> the type restriction in the pattern knocks the pattern out
> of shape. Attach it to the name-declaration instead.
>
> (pattern-case form ((n number)(m number) y z)
> (+ n m y) => `(+ ,(+ n m) y)
> (+ n y m) => `(+ ,(+ n m) y)
> (+ y n z) => (+ n y z))
ah, this is a nice way of embedding the type restriction into the
code. but what if I want to embed an arbitrary predicate instead? :-)
Nick
On Nov 5, 10:32 pm, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
...
> I worry about quoting issues. Suppose I wish to process data
> containing symbols such as ?FOO. I might want to use my
> pattern matcher to distinguish bewteen (?x 3) and (?y 4). So
> I write (?x ?x) ;pick out tentative x-coordinate. Whoops I
> need some way of quoting the first ?x to say that it is a
> literal.
>
> The idea that I have been playing with assumes that one
> usually has several patterns, and that it is therefore a
> small overhead to list the logic variables separately. So a
> crude simplifier might look like
>
> (pattern-case form (x)
> (+ x 0) => x
> (* x 0) => 0
> (* x 1) => x)
This is equivalent to let the universal quantifier back in.
> Suppose that the imp of the perverse has struck one a fatal
> blow:forcing one to use `x' as times, instead of `*'. How is
>
> (pattern-case form (x)
> (+ x 0) => x
> (x x 0) => 0
> (x x 1) => x)
>
> to be rescued?
>
> Since you must decide the literal elements of the pattern
> when you are writing the code, you can always change the
> variable names to miss them
>
> (pattern-case form (n)
> (+ n 0) => n
> (x n 0) => 0
> (x n 1) => 1)
Well, in this case, even with "regular" logic variables you will not
use ?x for the multiplication operator. The renaming trick is always
available.
> Sometimes you want a logic variable to be restricted so that
> it will only match a datum of a particular type. Embedding
> the type restriction in the pattern knocks the pattern out
> of shape. Attach it to the name-declaration instead.
>
> (pattern-case form ((n number)(m number) y z)
> (+ n m y) => `(+ ,(+ n m) y)
> (+ n y m) => `(+ ,(+ n m) y)
> (+ y n z) => (+ n y z))
As in (using CL-UNIFICATION):
CL-USER 12 > (unify:unify #T(number ?x) 42)
#<UNIFY ENVIRONMENT: 1 frame 2008C2EF>
CL-USER 13 > (unify:find-variable-value '?x *)
42
T
CL-USER 14 > (unify:unify #T(number ?x) 'qwe)
Error: Cannot unify symbol QWE with template #T(NUMBER ?X).
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other
options
With CL-UNIFICATION, PATTERN-CASE could be possibly be defined as:
(defmacro pattern-case (form vars &rest clauses)
(labels ((subst-vars (vars clauses-tests)
(if vars
(etypecase (first vars) ; untyped and typed.
(symbol
(subst-vars (rest vars) (subst (make-logical-var
(first vars))
(first vars)
clauses-tests)))
(cons
(subst-vars (rest vars) (subst (make-logical-var
(first vars))
(caar vars)
clauses-tests))))
clauses-tests))
)
(let ((new-clauses (mapcar 'cons
(subst-vars vars (mapcar #'first
clauses))
(mapcar #'rest clauses))))
`(match-case (,form) ,@new-clauses))))
(macroexpand-1 '(pattern-case form ((n integer))
((+ n 0) n)
((x n 0) 0)
((x n 1) 1)))
==>
(MATCH-CASE (FORM)
((+ #T(INTEGER ?N) 0) N)
((X #T(INTEGER ?N) 0) 0)
((X #T(INTEGER ?N) 1) 1))
>
> There are other notations beyound type restrictions that
> could usefully go in the name-declaration, such as a
> predicate that matched data must satisfy, or the equality
> test to be used when duplication of a variable is used to
> indicate that a datum must be duplicated in a pattern.
Sure. These are interesting issues. The more the better.
>
> These are interesting ideas, but perhaps a bit of a
> distraction if one has code to write.
>
What other code could be more interesting? :)
Cheers
--
Marco