I tries my best , but I still couldn't understand the Match function
and Binding function
in Paul Graham's book , ON LISP. I sincerely hope somebody can explan
these 2 functions
and give examples for match with binds not equal to nil and give
examples for using the
function bindings . Thanks.
The codes for the 2 functions from that book are below:
(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))))
··········@bbs.ee.ncu.edu.tw writes:
> I tries my best , but I still couldn't understand the Match function
> and Binding function
> in Paul Graham's book , ON LISP. I sincerely hope somebody can explan
> these 2 functions
> and give examples for match with binds not equal to nil and give
> examples for using the
> function bindings . Thanks.
>
> The codes for the 2 functions from that book are below:
Have a look at my answer in:
Message-ID: <··············@thalassa.informatimago.com>
--
"You question the worthiness of my code? I should kill you where you
stand!"
I recommend watching the SICP lecture video on "pattern matching"
(lecture 4a)
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
They basically outline the same function with a much clearer
explanation...
-Conrad
<··········@bbs.ee.ncu.edu.tw> wrote:
>I tries my best , but I still couldn't understand the Match function
> and Binding function
> in Paul Graham's book , ON LISP. I sincerely hope somebody can explan
> these 2 functions
....
Paul Graham's functions are not correct, what makes them perhaps a bit
difficult to understand. I noticed the error in an olde version of his book
and the strange thing is that the code has changed but the error is still in
it.
This is the old code which I think is easier to read. You should be able to
evaluate this.
(defun match (x y &optional binds)
(cond
((eql x y) (values binds t))
((assoc x binds) (match (binding x binds) y binds))
((assoc y binds) (match x (binding y binds) binds))
((var? x) (values (cons (cons x y) binds) t))
((var? y) (values (cons (cons y x) binds) t))
(t
(when (and (consp x) (consp y))
(multiple-value-bind (b2 yes)
(match (car x) (car y) binds)
(and yes (match (cdr x) (cdr y) b2)))))))
(defun var? (x)
(and (symbolp x)
(eql (char (symbol-name x) 0) #\?)))
(defun binding (x binds)
(let ((b (assoc x binds)))
(if b
(or (binding (cdr b) binds)
(cdr b)))))
; This unifier matches correctly but does not do back-substitution properly.
; The first argument of the 'or' in function 'binding' is an error. Graham
writes
; in his book that function binding needs to be recursive because back-
; substitution is delayed. Recursively looking for (cdr b) in bindings is
; however not enough since variables are not only bound to other variables.
; It works for the following example from his book. Graham uses it to
; demonstrate that binding must be recursive.
(binding '?x (match '(?x a) '(?y ?y)))
(binding '?y (match '(?x a) '(?y ?y)))
; The following example shows that the recursion in bind is not enough to
; do the proper backsubstitution.
(binding '?x (match '(?x a) '((?y b) ?y)))
(binding '?y (match '(?x a) '((?y b) ?y)))
; Recursively looking for (cdr b) in bindings does not seem to do any harm
; and maybe could be regarded as an optimization.
; To properly retreive bindings, true recursive back-substitution is needed.
; The following function 'binding-rec' is an example.
(defun binding-rec (x binds)
(let ((b (assoc x binds)))
(when b (subs-rec (cdr b) binds))))
(defun subs-rec (exp bindings)
(cond ((var? exp) (let ((binding (binding-rec exp bindings)))
(if binding binding exp)))
((consp exp) (cons (subs-rec (car exp) bindings)
(subs-rec (cdr exp) bindings)))
(t exp)))
; Now the examples do work:
(binding-rec '?x (match '(?x a) '((?y b) ?y)))
(binding-rec '?y (match '(?x a) '((?y b) ?y)))
; If back-substitution was not delayed the following substitution would
; suffice:
(defun subs (exp bindings)
(cond ((var? exp) (let ((binding (assoc exp bindings)))
(if binding (cdr binding) exp)))
((consp exp) (cons (subs (car exp) bindings)
(subs (cdr exp) bindings)))
(t exp)))
; Replacing the call to binding in match by a call to binding-rec also seems
; an option, but is not sufficient to enable use of subs instead of
subs-rec,
; so again at most an optimization.
Hope this helps
Paul Griffioen
Paul Griffioen wrote:
>
> ; The following example shows that the recursion in bind is not enough to
> ; do the proper backsubstitution.
>
> (binding '?x (match '(?x a) '((?y b) ?y)))
> (binding '?y (match '(?x a) '((?y b) ?y)))
(My following opinion may be just misunderstanding . If I am wrong ,
please let me know.)
The 3rd argument ?y in the function match will not happen , because the
3rd parameter binds is not key-in'ed by hand. It is prepared by the
"cons" in the following codes :
" ((varsym? x) (values (cons (cons x y) binds) t))
((varsym? y) (values (cons (cons y x) binds) t)) "
Of course , because the function match is defined as
(defun match (x y &optional binds) (...))
we can give binds' value manually , but this is what the function
designed for . The function is designed for comparing 2 trees. So ,
normally, we should begin with
(match tree1 tree2 ).
That is my stupid opinions. If I am wrong , please let me know.
Thanks!!
Sorry , I lost one word :
>Of course , because the function match is defined as
>(defun match (x y &optional binds) (...))
>we can give binds' value manually , but this is what the function
(the correct line should be:)
we can give binds' value manually , but this is NOT what the function
>designed for . The function is designed for comparing 2 trees. So ,
>normally, we should begin with
>(match tree1 tree2 ).
···········@bbs.ee.ncu.edu.tw" <··········@bbs.ee.ncu.edu.tw> writes:
> Sorry , I lost one word :
>>Of course , because the function match is defined as
>>(defun match (x y &optional binds) (...))
>>we can give binds' value manually , but this is what the function
>
> (the correct line should be:)
> we can give binds' value manually , but this is NOT what the function
>
>
>>designed for . The function is designed for comparing 2 trees. So ,
>>normally, we should begin with
>>(match tree1 tree2 ).
No. It really depends on the caller. Perhaps most of the callers
will avoid the optional argument, but if it was supposed to NOT be
used, the author could have written:
(defun match (x y)
(labels ((match-bindings (x y binds) ...))
(match-bindings x y nil)))
In anycase, it's very useful to be able to give it some default
bindings as I showed you in my example in a previous message, either
to allow you to partially match subexpressions, or when you have
predefined bindings and you want to check them.
--
"Specifications are for the weak and timid!"
<··········@bbs.ee.ncu.edu.tw> wrote:
>> (binding '?x (match '(?x a) '((?y b) ?y)))
>> (binding '?y (match '(?x a) '((?y b) ?y)))
>
> (My following opinion may be just misunderstanding . If I am wrong ,
> please let me know.)
> The 3rd argument ?y in the function match will not happen , because the
> 3rd parameter binds is not key-in'ed by hand.
> ...
I don't understand this. There is no third argument in above function
applications.
Paul Griffioen
Paul Griffioen 寫道：
> <··········@bbs.ee.ncu.edu.tw> wrote:
>
> >> (binding '?x (match '(?x a) '((?y b) ?y)))
> >> (binding '?y (match '(?x a) '((?y b) ?y)))
> >
> > (My following opinion may be just misunderstanding . If I am wrong ,
> > please let me know.)
> > The 3rd argument ?y in the function match will not happen , because the
> > 3rd parameter binds is not key-in'ed by hand.
> > ...
>
> I don't understand this. There is no third argument in above function
> applications.
>
> Paul Griffioen
(match '(?x a) '(?yb) ?y)
this function match gets 3 arguments :
the first is '(?x a)
the second is '(?yb)
the 3rd is ?y
I am sorry that I didn't make that so clear . Sorry again .
<··········@bbs.ee.ncu.edu.tw> wrote:
>Paul Griffioen ??:
>
>> <··········@bbs.ee.ncu.edu.tw> wrote:
>>
>> >> (binding '?x (match '(?x a) '((?y b) ?y)))
>> >> (binding '?y (match '(?x a) '((?y b) ?y)))
>> >
>> > (My following opinion may be just misunderstanding . If I am wrong ,
>> > please let me know.)
>> > The 3rd argument ?y in the function match will not happen , because the
>> > 3rd parameter binds is not key-in'ed by hand.
>> > ...
>>
>> I don't understand this. There is no third argument in above function
>> applications.
>>
>> Paul Griffioen
>
>(match '(?x a) '(?yb) ?y)
>this function match gets 3 arguments :
>the first is '(?x a)
>the second is '(?yb)
>the 3rd is ?y
>
>I am sorry that I didn't make that so clear . Sorry again .
Please check your system. Your copy and paste seems to be broken.
Paul Griffioen
Paul Griffioen wrote:
>
> Please check your system. Your copy and paste seems to be broken.
>
> Paul Griffioen
I use google's newsgroup service.
If it is difficult for your system to show my messages unbrokenly ,
you can get my complete message from google's service.
···········@bbs.ee.ncu.edu.tw" <··········@bbs.ee.ncu.edu.tw> writes:
> Paul Griffioen wrote:
> >
> > Please check your system. Your copy and paste seems to be broken.
> >
> > Paul Griffioen
>
> I use google's newsgroup service.
> If it is difficult for your system to show my messages unbrokenly ,
> you can get my complete message from google's service.
It would be better for all concerned if you simply used a decent
newsreader in the first place.
Gregm
If you can get this book:
COMMON LISP
An Interactive Approach
STUART C. SHAPIRO
Then get it, it's the easiest and most complete book I've seen for
learning modern lisp from scratch. And do all the (p1) marked exercies.
That way you will do a matching set of functions one step at a time.
That's what I did, and believe me, it's much easier to understand if
you write the code.