Predicate Classes ( was Re: Circle/Ellipse ) 
Author Message
 Predicate Classes ( was Re: Circle/Ellipse )

[ Our news spool got flushed to make disk space available for new stuff
  and somehow even the relatively recent comp.lang.dylan articles went too..
  So from memory .... ]

First off,  I don't think predicate classes are essential feature. I think
that they are nice "syntactic sugar" in certain cases that make the code
easier to deal with.  And, personally I like this way of added better then
"overloading" limited with yet another keyword. [ When you have a generic
function with a plethora of optional/alternative keywords applicable on some
but not all of the possible arguments , you should start wondering if it is
really one generic function you have there. ]

Second if you like to see what Cecil's predicate classes look like you
can look at the following page.

http://www.*-*-*.com/

[ There is also some constructs in the chapter on "types" that deal with
  describing with a group of  predicate "cover" a state space's possibles
  values or overlap , etc.   Types and objects/classes in Cecil are to
  "different" constructs...]

Now to the last response...

"Defects"

1. What if satisfy more than one predicate?

        Then it is an ambiguous multi-method dispatch. You could have
these before.  Although I suppose you couldn't on one argument methods.

        Note that he "ambiguity" would still be there in the "traverse
case stmt to derive state" approach. Only it would get resolved by
whichever predicate test came first.  What if you have two different
"tracks" of overloaded methods  m and n?  You'd need two different
state determiners for each one of these ( given that the predicates
used in both could be both be true. However, they aren't used in the
same context ).

[ In the aforementioned Cecil reference page there is an example where
  there is a non_empty_buffer and non_full_buffer  classes. I suppose that
  these are not exactly orthogonal to each other. :-)  ]

2.  To optimize keep state as an instance var.

    Much easier said than done in the arbitrarily complex case. First,
 the state in the circle/ellipse example is a "unidimensional" binary
 relationship.  It is either a circle or it isn't.  Second, in code that
 used side effects indiscriminately each "update" of a slot that "contributes"
 to the state would required a recalc of the the state variable.

 What if the test is more complicated than just  x == y . Something like
 if the phase of the moon is full and the collection that I'm apart of
 is  visible on the screen and I've been updated recently....

 Note that the predicate expression could depend upon non-local, but
 related in some way,  "state".  Now you have to track all of these state
 changes also.

"State Dispatch Construction Defect"

   If made into a macro then the construct would look something like

   define ........
        when predicate for state1
                state1's method code goes here
        when predicate for state2
                state2's method code goes here
   end

   Where there would be a predicate test and code for each state.
   Which would look a lot like the "inlined" case dispatch ( non predicate
   class )  example I had in my original post. In essence, both groups of
   code are grouped together into one larger , more complex construct.
   Explicitly writing custom dispatchers is always an option. ;-)

   From this perspective it seems like object.state method just allows one
   to "reuse" the state discriminator case stmt structure across several
   methods. Otherwise you might as well inline the various options.

--

Lyman S. Taylor          "Any sufficiently advanced technology is

                                   -- paraphrased Arthur C. Clarke
                                        seen somewhere on the USENET



Fri, 27 Aug 1999 03:00:00 GMT  
 Predicate Classes ( was Re: Circle/Ellipse )


Quote:

>> 1. What if satisfy more than one predicate?

...
...

Quote:
>resolving to a single state.  With predicate classes the compiler generates
>an implicit state determiner for you (as part of method dispatch) with the
>fixed format :-

>    case
>            pred1() => method1();
>            pred2() => method2();
>            ...
>    end

   The above is quite what the compiler would generate. It need only add
   state determining predicates to the "most specific method" lookup performed
   at some generic function invocation ( if such a method involved any
   predicate classes. The above could leads to errant behaviour.. example
   follows ).

Quote:
>into this. The difference to me seems minor.  Consider Craig Chambers'
>bounded buffer example,

   I probably should have used this example earlier...

Quote:

>    case
>    non_empty_state() & non_full_state()        => #"partially_full_state"
>    non_empty_state()                       => #"non_empty_state"
>    non_full_state()                        => #"non_full_state"
>    ~non_empty_state()                      => #"full_state"
>    ~non_full_state()                       => #"empty_state"
>    end;

  But with the above case stmt will you ever get to #"non_full_state"?
  Only if the buffer becomes empty? But what if you wish to dispatch before
  it is empty...

Quote:
>>  What if you have two different
>> "tracks" of overloaded methods  m and n?  You'd need two different
>> state determiners for each one of these ( given that the predicates
>> used in both could be both be true. However, they aren't used in the
>> same context ).

>I'm not sure I really understand this question.  Could you elaborate?

  In light of the above "classes"...

   define method  m ( x :: <paritally_full_buffer> )  ;
   define method  m ( x :: <non_empty_buffer> )  ;

   define method  n ( x :: <buffer> ) ;
   define method  n ( X :: <non_full_buffer> ) ;

 [ I'm pretty sure somewhere in Chambers examples are methods which the
    specializations on for these "middle/overlapping" predicates are distinct.
    As long as these "overlapping" prediates are used to specialize different
    generic functions, no ambiguity can arise. ]

 In determining the most specific method for N the "non_empty_buffer" predicate
 class need not be considered at all....

 I guess you could write another state determiner for dispatching on
 N vs. M. This isn't necessary with predicate classes.

Quote:
>updated frequently but you only dispatch occasionally).  My main point
>however was that when such caching is desirable it is trivial to call your>already written state-determiner method at each point where a
>state-transition could occur and assign the result to the state instance
>var - with predicate classes there is no way to tell the compiler to

 The only thing predicate classes "intertwine" with message dispatch is
 when and where the predicates are invoked.

 My point is that FINDING the points at which a state-transition can occur
 in the arbitrary predicate case is hard.  If you wish to "cherry pick" to
 the case where the predicates denote non-overlapping states and these
 state-transitions are easy to find the an optimizing compiler could just
 dynamically change the object's "class" ( where the predicate classes would
 be legitamate runtime classes ). This would require no extra slots
 and fits transparently into the method dispatch process.
 [ Indeed in Cecil objects are "classless" and created using "prototypes".]

 However, I doubt this happens very often. Or is easily achievable
 "automagically".

Quote:
>> "State Dispatch Construction Defect"
...
>Actually, what I had in mind was a macro that defined the "state dispatcher
>stub methods".  ie.

>define state-dispatched-method name( p1, p2, ... ) using discriminant x;

> ( expands to ) =>

>    define method name( p1, p2, ... )
>            _name( x( p1 ), p1, p2, ... )
>    end;

   Seems awfully single argument dispatch oriented to me. What if the
   predicate object specializer is the second, third, etc. argument?  
   What if the method has two or more arguments that can be predicate classes?

Quote:
>I'm not saying that predicate classes have no value but rather that we need
>to keep that value in perspective.  An earlier poster on this thread
>refered to predicate function specializers as a "very powerful" feature.  I
>think this undervalues the power and expressiveness of the existing
>language.  The advantage is not as great as it may at first seem.

   I too do not wish to imply Dylan has to absolutely have them.
   The mechanism put for that I'm "arguing against" probably would cleanly
   work for many cases.

   Predicate classes may be too flexible a mechanism to optimize away in the
   cases where there is "a need for speed".

   [ Being able to dynamically create classes and add methods to generic
         functions is painful enough. Add in a heft dose of predicate classes
         and you'll be lucky to get rid of any dynamic dispatch at all.
         (sans some sort of profile directed feedback). ]
--

Lyman S. Taylor          "Any sufficiently advanced technology is

                                   -- paraphrased Arthur C. Clarke
                                        seen somewhere on the USENET



Sat, 28 Aug 1999 03:00:00 GMT  
 Predicate Classes ( was Re: Circle/Ellipse )

Quote:
> 1. What if satisfy more than one predicate?

>    Then it is an ambiguous multi-method dispatch. You could have
> these before.  Although I suppose you couldn't on one argument methods.

>    Note that he "ambiguity" would still be there in the "traverse
> case stmt to derive state" approach. Only it would get resolved by
> whichever predicate test came first.

True, but the programmer has control over the structure of the state
determiner method and could implement whatever behaviour is desired for
resolving to a single state.  With predicate classes the compiler generates
an implicit state determiner for you (as part of method dispatch) with the
fixed format :-

        case
                pred1() => method1();
                pred2() => method2();
                ...
        end

( As you indicated in your earlier post ).

So you then have to write a bunch of predicates for the compiler to plug
into this. The difference to me seems minor.  Consider Craig Chambers'
bounded buffer example,

as predicates:

        non_full_state          buffer size < max elements
        non_empty_state         buffer size > 0 elements
        full_state              ~non_empty_state
        empty_state             ~non_full_state
        partially_full_state    non_empty_state & non_full_state

as a state-determiner:

 ( first define two predicates "non_empty_state" and "non_full_state" as
before )

        case
        non_empty_state() & non_full_state()        => #"partially_full_state"
        non_empty_state()                       => #"non_empty_state"
        non_full_state()                        => #"non_full_state"
        ~non_empty_state()                      => #"full_state"
        ~non_full_state()                       => #"empty_state"
        end;

Either way each time you add a state you have to consider all your existing
states and (potentially) modify the existing ones to make room for the new
one.  In the above example if the bounded buffer originally defined only
the "full", "empty" and "partially_full" states and you wanted to add
"non_empty" and "non_full", then,

for predicate classes:
        add two new predicate classes for "non_empty" and "non_full"
        change the existing predicate class for "partially_full" so that it now
inherits from the two new predicate classes (this is neccesary so that
ambiguity with the new states is avoided) and delete its original
predicate.

for the state-determiner:
        add two new case clauses for "non_empty" and "non_full" *after* the clause
for "partially_full"

I think that the level of code factoring achieved with the state-determiner
approach is just as good.

Quote:
>  What if you have two different
> "tracks" of overloaded methods  m and n?  You'd need two different
> state determiners for each one of these ( given that the predicates
> used in both could be both be true. However, they aren't used in the
> same context ).

I'm not sure I really understand this question.  Could you elaborate?

Quote:
> 2.  To optimize keep state as an instance var.

>    Much easier said than done in the arbitrarily complex case. First,
> the state in the circle/ellipse example is a "unidimensional" binary
> relationship.  It is either a circle or it isn't.  Second, in code that
> used side effects indiscriminately each "update" of a slot that
"contributes"
> to the state would required a recalc of the the state variable.

> What if the test is more complicated than just  x == y . Something like
> if the phase of the moon is full and the collection that I'm apart of
> is  visible on the screen and I've been updated recently....

Sure, if you cant cache the objects state then you cant optimize and even
when you can it may be more efficient not to cache (if your object is being
updated frequently but you only dispatch occasionally).  My main point
however was that when such caching is desirable it is trivial to call your
already written state-determiner method at each point where a
state-transition could occur and assign the result to the state instance
var - with predicate classes there is no way to tell the compiler to
provide you with an objects current "state" - this processing is intimately
intertwined into method dispatch.  The best you can do is hack all your
predicates to read an instance var you define and write your own state
determiner function for updating that var.

Quote:
> "State Dispatch Construction Defect"

>   If made into a macro then the construct would look something like

>   define ........
>    when predicate for state1
>            state1's method code goes here
>    when predicate for state2
>            state2's method code goes here
>   end

Actually, what I had in mind was a macro that defined the "state dispatcher
stub methods".  ie.

define state-dispatched-method name( p1, p2, ... ) using discriminant x;

 ( expands to ) =>

        define method name( p1, p2, ... )
                _name( x( p1 ), p1, p2, ... )
        end;

the client of the object always calls "name" but this is a stub function
that simply invokes a method called "_name" with an additional first
parameter: a singleton returned by the state determiner function "x".

So overall, what you do is:

        define class <myclass> ( ... )
                ...
        end;

        // write the state-determiner method
        define method x( obj :: <myclass> ) => ( state :: <symbol> );
                ...
        end;

        // define each method that will be dispatched based on object state

        define state-dispatched-method a(...) using discriminant x;
        define state-dispatched-method b(...) using discriminant x;
        define state-dispatched-method c(...) using discriminant x;
        ... etc

        // now define each state-specific method

        define method _a( state == #"state1", ... )
                ...
        end method;

        define method _a( state == #"state2", ... )
                ...
        end method;

        ... etc

Quote:
>   From this perspective it seems like object.state method just allows one
>   to "reuse" the state discriminator case stmt structure across several
>   methods. Otherwise you might as well inline the various options.

But in essence this is also the only benefit of predicate classes except
that you write a set of closely related predicates that the compiler plugs
into a standard "case" statement for you.

In Craig Chambers analysis, he notes two key benefits for predicate objects
:-

1) Important object states are clearly documented ( each predicate class is
a "state" and each state can have one or more methods associated
specifically with it )
2) Better factoring of code with fewer if/case statements

The "state-determiner with singletons" approach also achieves (1) and comes
close to achieving (2) except for the fact that you still have to write the
state determiner method.  However I dont see that as being less well
factored code since as I tried to show earlier, when you want to modify/add
or remove states you still have to potentially do some reworking of
existing code either way.

I'm not saying that predicate classes have no value but rather that we need
to keep that value in perspective.  An earlier poster on this thread
refered to predicate function specializers as a "very powerful" feature.  I
think this undervalues the power and expressiveness of the existing
language.  The advantage is not as great as it may at first seem.

Louis Madon



Sun, 29 Aug 1999 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. programming isn't about math Re: Newbie question re: circle and ellipse

2. Opinions on Ellipse-Circle dilemma?

3. Opinions on Ellipse-Circle dilemma?

4. Finding the ovality of a circle/ellipse

5. Ellipse Circle dilemma?

6. Newbie question re: circle and ellipse

7. Dynamic class (was Oh, no! Not circles and ellipses...)

8. ?COver larger circle by smaller circle

9. Predicate Classes

10. predicate classes

11. Predicates that create new predicates.

12. Am lost in ObjetLand... (BaseHTTPServer class hierarchy)

 

 
Powered by phpBB® Forum Software