I read Paul Graham's ON LISP but something really difficult happened to
me. Can somebody explan the machanism of function "match" ? How is it
possible for the parameter of binds in the function match to appear ?
Can somebody give an example of the function match that the parameter
binds is not nil ? Can somebody give an example of the usage of the
function binding ?Here are the codes of these functions from "ON LISP":
(defun match (x y &optional binds)
(acond2
((or (eql x y) (eql x '_) (eql y '_)) (values binds t))
((binding x binds) (match it y binds))
((binding y binds) (match x it binds))
((varsym? x) (values (cons (cons x y) binds) t))
((varsym? y) (values (cons (cons y x) binds) t))
((and (consp x) (consp y) (match (car x) (car y) binds))
(match (cdr x) (cdr y) it))
(t (values nil nil))))
(defun varsym? (x)
(and (symbolp x) (eq (char (symbol-name x) 0) #\?)))
(defun binding (x binds)
(labels ((recbind (x binds)
(aif (assoc x binds)
(or (recbind (cdr it) binds)
it))))
(let ((b (recbind x binds)))
(values (cdr b) b))))
Many thanks!!
··········@bbs.ee.ncu.edu.tw writes:
> I read Paul Graham's ON LISP but something really difficult happened to
> me. Can somebody explan the machanism of function "match" ? How is it
> possible for the parameter of binds in the function match to appear ?
> Can somebody give an example of the function match that the parameter
> binds is not nil ? Can somebody give an example of the usage of the
> function binding ? Here are the codes of these functions from "ON LISP":
In lisp, bindings are associations between a variable name and a value.
We can see in match that it expects binds to held bindings in the form
of a list of conses, with the variable name in the car and the value
in the cdr, ie. a mere a-list.
(match '(?x is ?y) '(blue is red))
--> ((?Y . RED) (?X . BLUE)) ; T
As you can see, the returned a-list describe these bindings:
the variable ?Y is "bound" to the value RED
the variable ?X is "bound" to the value BLUE
Now, if you try:
(trace match)
(match '(?x is ?x is ?x) '(big is big is big))
you'll see that some of the recursive calls of match are given the
bindings collected so far, to let it further check that ?x always
matches big.
Compare the above trace with that of this:
(match '(?x is ?x is ?x) '(big is fat is grand))
The call that pass the collected bindings is the last one in the match
function: (match (cdr x) (cdr y) it) ; <-- note the 'it'.
This can also be used from the client function; you can have
pre-existing bindings and be wanting to check if an expression matches
them:
(let ((bindings (match '(rasca is a cat) '(?x is a cat))))
(match '(and (?x eats ?y) (?y is a mouse))
'(and (rasca eats pica) (pica is a mouse))
bindings))
(ext:shell "wget http://lib.store.yahoo.net/lib/paulgraham/onlisp.lisp")
(load "onlisp.lisp")
;; ...
> (defun match (x y &optional binds)
> (acond2
> ((or (eql x y) (eql x '_) (eql y '_)) (values binds t))
> ((binding x binds) (match it y binds))
> ((binding y binds) (match x it binds))
> ((varsym? x) (values (cons (cons x y) binds) t))
> ((varsym? y) (values (cons (cons y x) binds) t))
> ((and (consp x) (consp y) (match (car x) (car y) binds))
> (match (cdr x) (cdr y) it))
> (t (values nil nil))))
>
> (defun varsym? (x)
> (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))
>
> (defun binding (x binds)
> (labels ((recbind (x binds)
> (aif (assoc x binds)
> (or (recbind (cdr it) binds)
> it))))
> (let ((b (recbind x binds)))
> (values (cdr b) b))))
>
> Many thanks!!
>
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Pascal , thanks for teaching me so lots.
I tried again for understanding tose codes and I got something below:
1. the main part of the codes is "((and (consp x) (consp y) (match (car
x) (car y) binds))
(match (cdr x) (cdr y) it)) ", these codes destruct the 2 trees to
be matched by recurrsion.
2. after decomposition of the 2 paterns into atoms , the codes
"((varsym? x) (values (cons (cons x y) binds) t)) ((varsym? y)
(values (cons (cons y x) binds) t)) " check if the atom is a variable
beginning with a question mark , if yes , it is collect with it's
corresponding value .
3. Some conditions have to be handled specially . If the same variable
appears twice or more
, eg (match '(?x ?x) '(1 2)) , the variable ?x appears twice with
different corresponding values,
the function match should return nil . This job was done mainly by the
codes
"((or (eql x y) (eql x '_) (eql y '_)) (values binds t))
((binding x binds) (match it y binds))
((binding y binds) (match x it binds)) "
It checks if the symbol got bound before . If so , whether it's the
same to the current value.
4. the coes "((or (eql x y) (eql x '_) (eql y '_)) (values binds t)) "
also serves to check if two atoms in the same corresponding positions
get the same values. If they get different values ,
the function match should return nil.
5. Consider the following situations : If we get these bindings ?x to
?y ,?y to 1 , what should be the constant value bound to ?x ? This job
was done by the local function recbind in the function binding.
OK , that's my best understanding for those codes . Please give me
comments if I am wrong .
Thanks!!
···········@bbs.ee.ncu.edu.tw" <··········@bbs.ee.ncu.edu.tw> writes:
> OK , that's my best understanding for those codes . Please give me
> comments if I am wrong .
I think you've understood correctly.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.