Filtered functions
in [Lisp]
|
Prev: [ANN] Filtered functions
Next: Filtered functions.
From: Pascal Costanza on 5 Dec 2009 19:06 Ron Garret wrote: > In article <7o00puF3nuc41U1(a)mid.individual.net>, > Pascal Costanza <pc(a)p-cos.net> wrote: > >> Ron Garret wrote: >>> In article <7nvteeF3mopq6U1(a)mid.individual.net>, >>> Pascal Costanza <pc(a)p-cos.net> wrote: >>> >>>> Ron Garret wrote: >>>>> In article <7nvrpuF3nupc4U1(a)mid.individual.net>, >>>>> Pascal Costanza <pc(a)p-cos.net> wrote: >>>>> >>>>>> Ron Garret wrote: >>>>>>> In article <7ntfj7F3m9fjiU1(a)mid.individual.net>, >>>>>>> Pascal Costanza <pc(a)p-cos.net> wrote: >>>>>>> >>>>>>>> Filtered functions are an extension of generic functions, extended >>>>>>>> with >>>>>>>> a filtering step where the arguments received by a generic function >>>>>>>> are >>>>>>>> mapped to other values based on user-defined mapping functions. Those >>>>>>>> filtered values are then used to perform the actual selection and >>>>>>>> execution of applicable methods. Nevertheless, the methods that are >>>>>>>> eventually executed see the original objects as received by the >>>>>>>> generic >>>>>>>> function, and not the filtered ones. >>>>>>> I like this concept, but is there a reason you designed the API the way >>>>>>> you did instead of simply providing a facility for subclassing built-in >>>>>>> classes? In other words, why not simply do: >>>>>>> >>>>>>> (def-subclass positive-integer integer 'plusp) >>>>>>> >>>>>>> (defmethod factorial ((n positive-integer)) ...) >>>>>>> >>>>>>> That would seem to me to provide the same functionality, and would make >>>>>>> code using this feature easier to write and debug. >>>>>> Maybe this would work for this particular example (but factorial is >>>>>> really not that interesting now, is it? ;). >>>>>> >>>>>> Just check the other examples as well, I don't think you could solve >>>>>> them that easily. >>>>> Obviously factorial is not the definitive test case, but I'm pretty sure >>>>> that the two APIs are formally equivalent. Is there a particular >>>>> example that you think could not be easily rendered in terms of >>>>> def-subclass? >>>> Yes, the other two examples in the paper. Especially the interpreter, >>>> but also the state example. I actually want to experiment with state >>>> being dynamically scoped such that you can have behavior depend on >>>> particular special variables. In conjunction with special slots in >>>> ContextL this means that it should be possible to have context-dependent >>>> object-specific behavior - something which is currently not possible >>>> with ContextL. >>>> >>>> Maybe you can express such things with class hierarchies, but I don't >>>> think that's convenient. >>> Well, here's how I'd do it: >>> >>> (defun make-filter (key-function expected-result) >>> (lambda (thing) (eq (funcall key-function thing) expected-result))) >>> >>> (def-subclass regular-stack stack (make-filter 'stack-state 'normal)) >>> >>> (def-subclass full-stack stack (make-filter 'stack-state 'full)) >>> >>> (def-subclass empty-stack stack (make-filter 'stack-state 'empty)) >>> >>> (defmethod stack-whatever ((stack regular-stack) ...) ...) >>> (defmethod stack-whatever ((stack empty-stack) ...) ...) >>> (defmethod stack-whatever ((stack full-stack) ...) ...) >>> >>> And the EVAL example: >>> >>> (defun make-form-type-checker (spec) >>> (lambda (form) (eq (car form) spec))) >>> >>> (def-subclass quote-form cons (make-filter 'car 'quote)) >>> (def-subclass lambda-form cons (make-filter 'car 'lambda)) >>> etc... >>> >>> (defmethod eval ((form quote-form)) form) >>> (defmethod eval ((form lambda-form)) (make-closure ...)) >>> >>> Seems pretty convenient to me. >> Can you provide a definition for def-subclass? > > Probably, though I might have to shadow defmethod and defgeneric. I do > not posses your level of MOP guruness. But first things first: would > you agree that def-subclass can do everything (or at least all the > worthwhile things) that filtered functions can do and that the interface > is cleaner? It may look cleaner (not sure about that), but I don't know how this should work... You seem to want to have a global space for defining potential filters, and then somehow infer from the defined methods which of them are used for a particular generic function. But that leaves the question open which one is the most specific one if several of them apply. Consider: (def-subclass prime-number integer (make-filter 'primep t)) (def-subclass even-number integer (make-filter 'evenp t)) (defmethod foo ((n prime-number)) (do-this)) (defmethod foo ((n even-number)) (do-that)) (foo 2) => should this perform do-this or do-that? Neither prime-number is a subclass/subset of even-number, nor the other way around, so it's unclear what the method specificity should be. Now with filtered functions: (define-filtered-function foo (n) (:filters (:prime #'primep) (:even #'evenp))) (defmethod foo :filter :prime ((n (eql t)) (do-this)) (defmethod foo :filter :even ((n (eql t))) (do-that)) (foo) => this will perform do-that, because the filter :even comes after the filter :prime in the define-filtered-function form. So how do you want to specify that when using def-subclass? Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Ron Garret on 5 Dec 2009 19:07 In article <7o0365F3m83ioU1(a)mid.individual.net>, Pascal Costanza <pc(a)p-cos.net> wrote: > Ron Garret wrote: > > In article <7ntfj7F3m9fjiU1(a)mid.individual.net>, > > Pascal Costanza <pc(a)p-cos.net> wrote: > > > >> Filtered functions are an extension of generic functions, extended with > >> a filtering step where the arguments received by a generic function are > >> mapped to other values based on user-defined mapping functions. Those > >> filtered values are then used to perform the actual selection and > >> execution of applicable methods. Nevertheless, the methods that are > >> eventually executed see the original objects as received by the generic > >> function, and not the filtered ones. > > > > I like this concept, but is there a reason you designed the API the way > > you did instead of simply providing a facility for subclassing built-in > > classes? In other words, why not simply do: > > > > (def-subclass positive-integer integer 'plusp) > > > > (defmethod factorial ((n positive-integer)) ...) > > > > That would seem to me to provide the same functionality, and would make > > code using this feature easier to write and debug. > > How does the factorial function know which def-subclass definitions to > take into account? The same way it knows which methods to take into account. (Maybe I don't understand the question.) > Should it try all of them? A subset? Based on what criteria? I'm not sure what you mean by "try" in this context. It should proceed in the same way as any method application, by assembling a set of applicable methods and combining them according to the appropriate method combination. Implementing this efficiently could be tricky, but I don't see why this should be at all problematic on a conceptual level. > What does it do with the ones where the predicate fails (by > signaling an error)? Of course not. Why would you think that would even be a reasonable possibility? > If several of the def-subclass forms apply, which one is selected? Are > they all selected? In what order? What is the most specific one, what is > the last specific one, and so on? I presume you mean something like this: (def-subclass positive-integer 'integer 'plusp) (def-subclass odd-integer 'integer 'oddp) (defmethod m1 ((x positive-integer)) 'positive) (defmethod m1 ((x odd-integer)) 'odd) (m1 3) --> ??? This situation is completely analogous to: (defclass c1 () ()) (defclass c2 () ()) (defclass c3 (c1 c2) ()) (defmethod m1 ((x c1)) 1) (defmethod m1 ((c c2)) 2) (m1 (make-instance 'c3)) --> ??? In the latter case the ambiguity is resolved because the superclasses of C3 are listed in order. A similar solution could be applied to sub-classes, i.e. a total order could be imposed on all sub-classes of a given class. Exactly how this would be done is TBD, but surely you don't dispute that it could be done this way? > These are the typical issues you have to solve when designing > predicate-dispatch-style systems, and they are not trivial to solve > (basically because of the halting problem). I don't see why. Certainly there are designs that would run afoul of the halting problem, but I don't see that this is necessarily so. So all you have to do is pick a design that doesn't, like imposing a total order on all the subclasses of a given class, and then making the rest of the design analogous to what already exists in CLOS. > Filtered functions solve this by defining the acceptable filters along > with the filtered function definition, and by defining an order among > filters along the way that can be chosen per filtered function. > > The idea to specify an order between custom filters (specializers) was > first described by Jim Newton, and is described in more detail in a > paper by Jim Newton and Christophe Rhodes. The difference between their > approach and ours is that in their approach, the order is defined at the > meta-level (as part of the MOP), whereas here it is defined at the > base-level (as part of the define-filtered-function form). I think the > latter is more convenient, since the orders tend to be ad hoc anyway, as > far as I can tell. > > Having per-function orders seems to have been adopted by now in Clojure > as well. I have still not had a chance to actually read your paper (and probably won't until tomorrow at the earliest) so I may well be missing something really important. But based on your responses so far I can't imagine what that might be. rg
From: Kenneth Tilton on 5 Dec 2009 19:18 Raffael Cavallaro wrote: > On 2009-12-05 17:52:27 -0500, Kenneth Tilton <kentilton(a)gmail.com> said: > >> Oh, good! You don't know what "sour grapes" means! > > I know perfectly, you're just having difficulty identifying the > metaphorical grapes. They are, to spell it out in painful detail once > again, writing a *publication quality* *well documented* *well received* > extension to CLOS. Since you haven't done this, you're criticizing > someone who *has* as performing "stupid CLOS tricks." This critique > ("stupid CLOS tricks") of something you wish you had done (a > *publication quality* *well documented* *well received* extension to > CLOS) is crying "sour grapes." Sour grapes is about pooh-poohing something I cannot have. I can have filtered functions*. QED. Don't feel bad, your english is way better than my spanish. * I would not blame Pascal for modifying the license to exclude me. >> Meanwhile, I provided a thumbs-down analysis on the whole idea of GFs >> to justify my assessment of an enhancement thereto, to which you >> responded with irrelevant guesswork as to my motivation. I guess if >> you have no defense of GFs to offer, that was a smart move. > > The only justification for any feature in an extensible language like > lisp is whether or not it allows you to more easily shape the language > to the way you think. Oy, vey. The proof is in the pudding, aka the application, not some abstract guess about "shaping". I have developed hundreds of application KLOC with Cells during which (to my surprise) I honestly lost interest in GFs as anything more than incrementally nice. Sorry to keep dragging the discussion back to the value of GFs, I know you want to make me feel bad about some unrelated software. kt
From: Ron Garret on 5 Dec 2009 19:22 In article <rNOSPAMon-D137E5.16071705122009(a)news.albasani.net>, Ron Garret <rNOSPAMon(a)flownet.com> wrote: > > What does it do with the ones where the predicate fails (by > > signaling an error)? > > Of course not. Why would you think that would even be a reasonable > possibility? Oops, I just realized I parsed that question completely wrong. > I have still not had a chance to actually read your paper (and probably > won't until tomorrow at the earliest) so I may well be missing something > really important. But based on your responses so far I can't imagine > what that might be. I've now had a chance to skim the paper, and so I think I now understand the motivation behind doing it the way you did. FWIW, I still think I would personally prefer a dispatch system which leaves it up to me (the programmer) to insure that the predicates I use halt, don't raise errors, and have some kind of total ordering defined on them. But I now see how a reasonable person could disagree, and how filtered functions solve certain problems that dispatch has to either punt on or fob off onto the programmer. rg
From: Ron Garret on 5 Dec 2009 19:26
In article <7o0asgF3l7u67U1(a)mid.individual.net>, Pascal Costanza <pc(a)p-cos.net> wrote: > Ron Garret wrote: > > In article <7o00puF3nuc41U1(a)mid.individual.net>, > > Pascal Costanza <pc(a)p-cos.net> wrote: > > > >> Ron Garret wrote: > >>> In article <7nvteeF3mopq6U1(a)mid.individual.net>, > >>> Pascal Costanza <pc(a)p-cos.net> wrote: > >>> > >>>> Ron Garret wrote: > >>>>> In article <7nvrpuF3nupc4U1(a)mid.individual.net>, > >>>>> Pascal Costanza <pc(a)p-cos.net> wrote: > >>>>> > >>>>>> Ron Garret wrote: > >>>>>>> In article <7ntfj7F3m9fjiU1(a)mid.individual.net>, > >>>>>>> Pascal Costanza <pc(a)p-cos.net> wrote: > >>>>>>> > >>>>>>>> Filtered functions are an extension of generic functions, extended > >>>>>>>> with > >>>>>>>> a filtering step where the arguments received by a generic function > >>>>>>>> are > >>>>>>>> mapped to other values based on user-defined mapping functions. > >>>>>>>> Those > >>>>>>>> filtered values are then used to perform the actual selection and > >>>>>>>> execution of applicable methods. Nevertheless, the methods that are > >>>>>>>> eventually executed see the original objects as received by the > >>>>>>>> generic > >>>>>>>> function, and not the filtered ones. > >>>>>>> I like this concept, but is there a reason you designed the API the > >>>>>>> way > >>>>>>> you did instead of simply providing a facility for subclassing > >>>>>>> built-in > >>>>>>> classes? In other words, why not simply do: > >>>>>>> > >>>>>>> (def-subclass positive-integer integer 'plusp) > >>>>>>> > >>>>>>> (defmethod factorial ((n positive-integer)) ...) > >>>>>>> > >>>>>>> That would seem to me to provide the same functionality, and would > >>>>>>> make > >>>>>>> code using this feature easier to write and debug. > >>>>>> Maybe this would work for this particular example (but factorial is > >>>>>> really not that interesting now, is it? ;). > >>>>>> > >>>>>> Just check the other examples as well, I don't think you could solve > >>>>>> them that easily. > >>>>> Obviously factorial is not the definitive test case, but I'm pretty > >>>>> sure > >>>>> that the two APIs are formally equivalent. Is there a particular > >>>>> example that you think could not be easily rendered in terms of > >>>>> def-subclass? > >>>> Yes, the other two examples in the paper. Especially the interpreter, > >>>> but also the state example. I actually want to experiment with state > >>>> being dynamically scoped such that you can have behavior depend on > >>>> particular special variables. In conjunction with special slots in > >>>> ContextL this means that it should be possible to have context-dependent > >>>> object-specific behavior - something which is currently not possible > >>>> with ContextL. > >>>> > >>>> Maybe you can express such things with class hierarchies, but I don't > >>>> think that's convenient. > >>> Well, here's how I'd do it: > >>> > >>> (defun make-filter (key-function expected-result) > >>> (lambda (thing) (eq (funcall key-function thing) expected-result))) > >>> > >>> (def-subclass regular-stack stack (make-filter 'stack-state 'normal)) > >>> > >>> (def-subclass full-stack stack (make-filter 'stack-state 'full)) > >>> > >>> (def-subclass empty-stack stack (make-filter 'stack-state 'empty)) > >>> > >>> (defmethod stack-whatever ((stack regular-stack) ...) ...) > >>> (defmethod stack-whatever ((stack empty-stack) ...) ...) > >>> (defmethod stack-whatever ((stack full-stack) ...) ...) > >>> > >>> And the EVAL example: > >>> > >>> (defun make-form-type-checker (spec) > >>> (lambda (form) (eq (car form) spec))) > >>> > >>> (def-subclass quote-form cons (make-filter 'car 'quote)) > >>> (def-subclass lambda-form cons (make-filter 'car 'lambda)) > >>> etc... > >>> > >>> (defmethod eval ((form quote-form)) form) > >>> (defmethod eval ((form lambda-form)) (make-closure ...)) > >>> > >>> Seems pretty convenient to me. > >> Can you provide a definition for def-subclass? > > > > Probably, though I might have to shadow defmethod and defgeneric. I do > > not posses your level of MOP guruness. But first things first: would > > you agree that def-subclass can do everything (or at least all the > > worthwhile things) that filtered functions can do and that the interface > > is cleaner? > > It may look cleaner (not sure about that), but I don't know how this > should work... > > You seem to want to have a global space for defining potential filters, > and then somehow infer from the defined methods which of them are used > for a particular generic function. But that leaves the question open > which one is the most specific one if several of them apply. > > Consider: > > (def-subclass prime-number integer (make-filter 'primep t)) > (def-subclass even-number integer (make-filter 'evenp t)) > > (defmethod foo ((n prime-number)) (do-this)) > (defmethod foo ((n even-number)) (do-that)) > > (foo 2) => should this perform do-this or do-that? Neither prime-number > is a subclass/subset of even-number, nor the other way around, so it's > unclear what the method specificity should be. > > Now with filtered functions: > > (define-filtered-function foo (n) > (:filters (:prime #'primep) > (:even #'evenp))) > > (defmethod foo :filter :prime ((n (eql t)) > (do-this)) > > (defmethod foo :filter :even ((n (eql t))) > (do-that)) > > (foo) => this will perform do-that, because the filter :even comes after > the filter :prime in the define-filtered-function form. > > So how do you want to specify that when using def-subclass? In the exact same way: by providing a mechanism to specify a total ordering on the sub-classes of a given class, just as you provide a mechanism to specify a total ordering on filters. (Exactly what that mechanism would be is TBD.) rg |