[cl-unification-devel] Questions and patches involving cl-unification's MATCH* macros
Greetings! I was looking into improving the efficiency of MATCH-CASE and while working on that I've ended up with a few questions regarding some implementation decisions, and drafted up some patches both to help you see my thoughts and for consideration of inclusion if you think they're in the right direction. Patches are numbered in the order created, and generally depend on lower-numbered patches (not always intentionally--it's hard to avoid inter-patch dependencies when making multiple changes to a small area). I thought I made the patches in a reasonable order while I was making them, but I find myself referring to them in a different sequence than what I made them in, so apologies if that causes any confusion. I've also put up a darcs mirror (in darcs2 format) of the CVS repository plus the attached patches, in case you find that more convenient. You can find it at http://repo.kepibu.org/cl-unification/ ** Duplicate code There's a fair bit of code duplication between MATCH, MATCHF, and MATCHING in the form of GENERATE-VAR-BINDINGS and the production of the let forms that surround FORMS in those macros. (Nevermind that MATCH and MATCHF are identical except in what they do with template.) Patches 0 and 2 help somewhat. 0) Extract template handling of MATCH[ING] into %TEMPLATE-FOR-MATCH Should be fairly self-explanatory; not much of a win in lines. 2) Extract the bits that wrap forms with bindings for template variables This patch extracts the assorted flet GENERATE-VAR-BINDINGS into a single common function. It's slightly less straightforward than that, however, because it also extracts the (let ...) forms which actually used those bindings. This results in a decent win for code size, but in some cases it swaps the order of execution of %TEMPLATE-FOR-MATCH and COLLECT-TEMPLATE-VARS. I'm pretty sure this doesn't have any noticable effect, but thorough testing is probably wise. ** (unify* ...) and (ignore-errors (unify ...)) The MATCHING macro produces the form (ignore-errors (unify ...)), presumably because it existed before the convenience function UNIFY*. But I'm curious about UNIFY* and/or the ignore-errors form in MATCHING. Is ignore-errors the proper form in either of these places, or was it just easier to type than (handler-case (unify ...) (unification-failure () nil)) ? Looking at some of the assorted UNIFY methods, I see UNIFICATION-FAILUREs aren't the only possible condition which might be thrown during unification (e.g., LAMBDA-LIST-PARSING-ERROR is also a possibility). However, while MATCHING treats any error as a failure to unify, MATCH, MATCHF, MATCH-CASE, and MATCHF-CASE all limit themselves to only UNIFICATION-FAILUREs. This inconsistency leads me to wonder which is correct. I assume only UNIFICATION-FAILUREs should be treated as such in patch 5 because all ERRORs seems a bit heavy-handed in a language with such an excellent condition system, but can see the argument that any error /is/ a failure to unify. 1) Use (unify* ...) rather than (ignore-errors (unify ...)) Same thing, so might as well use the convenience function. Not particularly exciting. And this bit is changed again in patch 5 to ignore only UNIFICATION-FAILUREs. 5) Make MATCHING agree with MATCH[F][-CASE] about the conditions of failure Rather than skipping to the next clause on any error, UNIFICATION-FAILUREs--and /only/ UNIFICATION-FAILUREs--skip to the next clause. Under the assumption that UNIFY* is implemented as intended, this creates a new utility function UNIFY** (terrible name, I know!) which is like UNIFY* but ignores /only/ UNIFICATION-FAILUREs rather than all ERRORs. This of course results in a library-user-visible change to how MATCHING operates, which may or may not be considered acceptable. ** (matching (otherwise ...)) 3) Fix (matching (otherwise ...)) (matching (otherwise ...)) expands into (cond (otherwise ...)), which generates an unbound-variable error when executed, because COND does not special-case OTHERWISE as CASE does. Pretty self-explanatory and not very interesting. ** &body vs. &rest 4) Use &body instead of &rest for (arguably) prettier auto-indentation I prefer the smaller indentation provided with using &body instead of &rest. Not a big deal either way, but I was in there so I figured I'd throw it in the mix. Fortunately, if you disagree, this patch shouldn't affect any of the others. :) ** Multiple #:UNIFICATION-ENVs in MATCHING 6) Only use one variable to store the unification environment in MATCHING Because of the way MATCHING expands, and what UNIFY** returns, each (setf #:env (unify** ...)) call will do one of two things: it will set #:env to NIL or it will set #:env to an ENVIRONMENT structure. If #:env is set to NIL--the same value it entered the (setf) with!--the COND will continue on to the next clause. If #:env is set to an ENVIRONMENT structure, none of the remaining (setf) clauses will be evaluated. Thus, because the variable will only ever be set to a non-nil value once, this is perfectly safe. ** MATCH-CASE MATCH-CASE has the surprising behavior of (ignore-errors (match-case ("foo") ("foo" (error 'unification-failure)) (t :default))) => :default Hardly CASE-like behavior! I think it sensible to redefine MATCH-CASE in terms of MATCHING, rather than MATCH. E.g., so the above would expand into something like (ignore-errors (let ((#:object-var "foo")) (matching (:errorp nil :default-substitution nil :matching-named nil) (("foo" #:object-var) (error 'unification-failure)) (t :default)))) which greatly simplifies the definition of MATCH-CASE and makes it much more CASE-like in behavior. 7) Redefine MATCH-CASE in terms of MATCHING This both greatly simplifies the MATCH-CASE macro as well as its expansion. HOWEVER, this version is *NOT* 100% compatible with the previous version. Specifically, UNIFICATION-FAILUREs signalled from within clause-forms will /not/ cause the next unification clause to be attempted, but will instead propogate outward as the -case name suggests they should. That is, (ignore-errors (match-case ("foo") ("foo" (error 'unification-failure ...)) (t :default))) => :default ;; before patch => nil, #<unification-failure> ;; after patch Patch 7 suggests that MATCHING, MATCH-CASE, MATCHF-CASE, and the possible future MATCH-COND and MATCHF-COND are all fairly trivial variations on each other. I'll be happy to explore that possibility in future patches if it's of interest, but I'm already asking you to look at too many patches at once, so I'll refrain for now. :) ** MATCH Though documented, MATCH's behavior when its body forms signal UNIFICATION-FAILURE seems at odds with expectations, for pretty much the same reason the behavior seems nonsensical in MATCH-CASE. Was it a deliberate design decision, or a side-effect of how MATCH was implemented? If a side effect of implementation, would it make sense to redefine MATCH to have an expansion more like (match ("foo" "foo" :errorp <e?> :error-value <ev>) <body>) => (m-v-b (#:env #:error) (unify** "foo" "foo") (cond ((and #:error <e?>) (error #:error)) (#:error <ev>) (t (let* (#| template vars |#) <body>)))) so UNIFICATION-FAILUREs inside <body> can be independent of errorp? (No patch for this one yet.) ** :MATCH-NAMED, :MATCHING-NAMED, :MATCH-CASE-NAMED It seems a bit redundant to have <macro-name>-named arguments for block names rather than simply having a :named argument as in, say, LOOP. Any particular reason it wasn't done that way? (No patch for this one, either.) ** Apologies Sorry about the massive brain dump. I /may/ have gotten carried away. :)
Hello there. thanks a lot for all the work. I have read through the messages and I agree with your analysis with a few comments. I think all the changes you propose are worth including. Let me comment on a few of these. On Jan 16, 2010, at 06:43 , Pixel // pinterface wrote:
Greetings! I was looking into improving the efficiency of MATCH- CASE and while working on that I've ended up with a few questions regarding some implementation decisions, and drafted up some patches both to help you see my thoughts and for consideration of inclusion if you think they're in the right direction.
Patches are numbered in the order created, and generally depend on lower-numbered patches (not always intentionally--it's hard to avoid inter-patch dependencies when making multiple changes to a small area). I thought I made the patches in a reasonable order while I was making them, but I find myself referring to them in a different sequence than what I made them in, so apologies if that causes any confusion.
I've also put up a darcs mirror (in darcs2 format) of the CVS repository plus the attached patches, in case you find that more convenient. You can find it at http://repo.kepibu.org/cl-unification/
** Duplicate code
There's a fair bit of code duplication between MATCH, MATCHF, and MATCHING in the form of GENERATE-VAR-BINDINGS and the production of the let forms that surround FORMS in those macros. (Nevermind that MATCH and MATCHF are identical except in what they do with template.)
Yep. Most of the code in the MATCH-BLOCK file is cut'n'paste.
Patches 0 and 2 help somewhat.
0) Extract template handling of MATCH[ING] into %TEMPLATE-FOR-MATCH Should be fairly self-explanatory; not much of a win in lines.
2) Extract the bits that wrap forms with bindings for template variables This patch extracts the assorted flet GENERATE-VAR-BINDINGS into a single common function. It's slightly less straightforward than that, however, because it also extracts the (let ...) forms which actually used those bindings.
This results in a decent win for code size, but in some cases it swaps the order of execution of %TEMPLATE-FOR-MATCH and COLLECT-TEMPLATE-VARS. I'm pretty sure this doesn't have any noticable effect, but thorough testing is probably wise.
This is good. However, I would set up a bunch of regression tests before moving on and change things. I usually use the test suite from Franz, but I'd be willing to change to another test suite.
** (unify* ...) and (ignore-errors (unify ...))
The MATCHING macro produces the form (ignore-errors (unify ...)), presumably because it existed before the convenience function UNIFY*. But I'm curious about UNIFY* and/or the ignore-errors form in MATCHING. Is ignore- errors the proper form in either of these places, or was it just easier to type than (handler-case (unify ...) (unification-failure () nil)) ?
Most implementations expand IGNORE-ERRORS in something like that. But I agree that (as you point out later on) that UNIFY* should be written as (defmethod unify* (a b &optional (env (make-empty-environment))) (handler-case (unify a b env) (unification-failure () nil)) In this way other conditions are passed on.
Looking at some of the assorted UNIFY methods, I see UNIFICATION- FAILUREs aren't the only possible condition which might be thrown during unification (e.g., LAMBDA-LIST-PARSING-ERROR is also a possibility). However, while MATCHING treats any error as a failure to unify, MATCH, MATCHF, MATCH-CASE, and MATCHF-CASE all limit themselves to only UNIFICATION-FAILUREs. This inconsistency leads me to wonder which is correct.
I assume only UNIFICATION-FAILUREs should be treated as such in patch 5 because all ERRORs seems a bit heavy-handed in a language with such an excellent condition system, but can see the argument that any error / is/ a failure to unify.
1) Use (unify* ...) rather than (ignore-errors (unify ...)) Same thing, so might as well use the convenience function.
Not particularly exciting. And this bit is changed again in patch 5 to ignore only UNIFICATION-FAILUREs.
Yep. See above.
5) Make MATCHING agree with MATCH[F][-CASE] about the conditions of failure Rather than skipping to the next clause on any error, UNIFICATION-FAILUREs--and /only/ UNIFICATION-FAILUREs--skip to the next clause.
Under the assumption that UNIFY* is implemented as intended, this creates a new utility function UNIFY** (terrible name, I know!) which is like UNIFY* but ignores /only/ UNIFICATION-FAILUREs rather than all ERRORs.
This of course results in a library-user-visible change to how MATCHING operates, which may or may not be considered acceptable.
Yep.
** (matching (otherwise ...))
3) Fix (matching (otherwise ...)) (matching (otherwise ...)) expands into (cond (otherwise ...)), which generates an unbound-variable error when executed, because COND does not special-case OTHERWISE as CASE does.
Pretty self-explanatory and not very interesting.
Good catch.
** &body vs. &rest
4) Use &body instead of &rest for (arguably) prettier auto-indentation I prefer the smaller indentation provided with using &body instead of &rest. Not a big deal either way, but I was in there so I figured I'd throw it in the mix. Fortunately, if you disagree, this patch shouldn't affect any of the others. :)
I agree. It is better self documentation as well.
** Multiple #:UNIFICATION-ENVs in MATCHING
6) Only use one variable to store the unification environment in MATCHING Because of the way MATCHING expands, and what UNIFY** returns, each (setf #:env (unify** ...)) call will do one of two things: it will set #:env to NIL or it will set #:env to an ENVIRONMENT structure.
If #:env is set to NIL--the same value it entered the (setf) with!--the COND will continue on to the next clause.
If #:env is set to an ENVIRONMENT structure, none of the remaining (setf) clauses will be evaluated.
Thus, because the variable will only ever be set to a non-nil value once, this is perfectly safe.
I think this is ok as well.
** MATCH-CASE
MATCH-CASE has the surprising behavior of (ignore-errors (match-case ("foo") ("foo" (error 'unification-failure)) (t :default))) => :default Hardly CASE-like behavior!
I think it sensible to redefine MATCH-CASE in terms of MATCHING, rather than MATCH. E.g., so the above would expand into something like (ignore-errors (let ((#:object-var "foo")) (matching (:errorp nil :default-substitution nil :matching- named nil) (("foo" #:object-var) (error 'unification-failure)) (t :default)))) which greatly simplifies the definition of MATCH-CASE and makes it much more CASE-like in behavior.
7) Redefine MATCH-CASE in terms of MATCHING This both greatly simplifies the MATCH-CASE macro as well as its expansion.
HOWEVER, this version is *NOT* 100% compatible with the previous version. Specifically, UNIFICATION-FAILUREs signalled from within clause-forms will /not/ cause the next unification clause to be attempted, but will instead propogate outward as the -case name suggests they should.
That is, (ignore-errors (match-case ("foo") ("foo" (error 'unification-failure ...)) (t :default))) => :default ;; before patch => nil, #<unification-failure> ;; after patch
Patch 7 suggests that MATCHING, MATCH-CASE, MATCHF-CASE, and the possible future MATCH-COND and MATCHF-COND are all fairly trivial variations on each other. I'll be happy to explore that possibility in future patches if it's of interest, but I'm already asking you to look at too many patches at once, so I'll refrain for now. :)
I agree with this as well. The behavior you suggest is the one that's needed.
** MATCH
Though documented, MATCH's behavior when its body forms signal UNIFICATION-FAILURE seems at odds with expectations, for pretty much the same reason the behavior seems nonsensical in MATCH-CASE. Was it a deliberate design decision, or a side-effect of how MATCH was implemented?
Never attribute to malice what can be attributed to incompetence. Of course it is a side-effect of the implementation :) I knew I needed a test suite :)
If a side effect of implementation, would it make sense to redefine MATCH to have an expansion more like (match ("foo" "foo" :errorp <e?> :error-value <ev>) <body>) => (m-v-b (#:env #:error) (unify** "foo" "foo") (cond ((and #:error <e?>) (error #:error)) (#:error <ev>) (t (let* (#| template vars |#) <body>)))) so UNIFICATION-FAILUREs inside <body> can be independent of errorp?
(No patch for this one yet.)
** :MATCH-NAMED, :MATCHING-NAMED, :MATCH-CASE-NAMED
It seems a bit redundant to have <macro-name>-named arguments for block names rather than simply having a :named argument as in, say, LOOP. Any particular reason it wasn't done that way?
Having the :NAMED option would be preferable, with NIL or the macro name as fall-back.
(No patch for this one, either.)
** Apologies
Sorry about the massive brain dump. I /may/ have gotten carried away. :)
Absolutely not. All of this is most welcome. I am just a little swamped (what an euphemism!) and maybe not all that reactive. But let's keep the discussion going. all the best Marco
"Marco Antoniotti" <marcoxa@cs.nyu.edu> sayeth thusly:
Hello there.
thanks a lot for all the work. I have read through the messages and I agree with your analysis with a few comments.
I think all the changes you propose are worth including.
Let me comment on a few of these.
Woo! Glad to know I didn't get myself lost digging around. :)
On Jan 16, 2010, at 06:43 , Pixel // pinterface wrote: [snip]
Patches 0 and 2 help somewhat.
0) Extract template handling of MATCH[ING] into %TEMPLATE-FOR-MATCH Should be fairly self-explanatory; not much of a win in lines.
2) Extract the bits that wrap forms with bindings for template variables This patch extracts the assorted flet GENERATE-VAR-BINDINGS into a single common function. It's slightly less straightforward than that, however, because it also extracts the (let ...) forms which actually used those bindings.
This results in a decent win for code size, but in some cases it swaps the order of execution of %TEMPLATE-FOR-MATCH and COLLECT-TEMPLATE-VARS. I'm pretty sure this doesn't have any noticable effect, but thorough testing is probably wise.
This is good. However, I would set up a bunch of regression tests before moving on and change things. I usually use the test suite from Franz, but I'd be willing to change to another test suite.
Agreed. More tests are needed. I'll add that to my TODO list. :) I have no preference for any particular test suite; largely because I (regrettably) have no experience with any of the myriad of test suites available. I'm good with whatever. [snip]
** MATCH
Though documented, MATCH's behavior when its body forms signal UNIFICATION-FAILURE seems at odds with expectations, for pretty much the same reason the behavior seems nonsensical in MATCH-CASE. Was it a deliberate design decision, or a side-effect of how MATCH was implemented?
Never attribute to malice what can be attributed to incompetence. Of course it is a side-effect of the implementation :) I knew I needed a test suite :)
Well, "incompetence" hardly seems fair to yourself! It's a tricky bit, that.
** :MATCH-NAMED, :MATCHING-NAMED, :MATCH-CASE-NAMED
It seems a bit redundant to have <macro-name>-named arguments for block names rather than simply having a :named argument as in, say, LOOP. Any particular reason it wasn't done that way?
Having the :NAMED option would be preferable, with NIL or the macro name as fall-back.
Should :<macro-name>-NAMED also work, for backwards-compatibility? If yes, should it warn about deprecation during compilation? (A warning that would undoubtedly be lost in the scroll of compilation output, but c'est la vie.)
** Apologies
Sorry about the massive brain dump. I /may/ have gotten carried away. :)
Absolutely not. All of this is most welcome. I am just a little swamped (what an euphemism!) and maybe not all that reactive. But let's keep the discussion going.
Oh, good. I was worried. :) --
On Jan 16, 2010, at 06:43 , Pixel // pinterface wrote:
I've also put up a darcs mirror (in darcs2 format) of the CVS repository plus the attached patches, in case you find that more convenient. You can find it at http://repo.kepibu.org/cl-unification/
I was actually toying with the idea of moving to git. But I have darcs installed as well. If I remember, darcs is supported by cl.net, isn't it? -- Marco Antoniotti
"Marco Antoniotti" <marcoxa@cs.nyu.edu> said:
On Jan 16, 2010, at 06:43 , Pixel // pinterface wrote:
I've also put up a darcs mirror (in darcs2 format) of the CVS repository plus the attached patches, in case you find that more convenient. You can find it at http://repo.kepibu.org/cl-unification/
I was actually toying with the idea of moving to git. But I have darcs installed as well. If I remember, darcs is supported by cl.net, isn't it?
git would also be a fine choice. Both are supported by cl.net[1]. [1] http://common-lisp.net/viewrep.shtml --
participants (2)
-
Marco Antoniotti -
Pixel // pinterface