Design problem using Multiple Dispatch or Redispatch (long)

Design problem using Multiple Dispatch or Redispatch (long)

[Thom Brooke]

I've been struggling with a design problem for some time now, 
and I'm looking for suggestions (or some reason why it won't work).

I have developed a solution, but it's ugly -- little better than 
Ada83.  I want a nice, clean, Ada95 solution that does it _right_.

Here's the situation:
The system consists of a bunch of "commands", and several kinds of
"processor" which "execute" the commands. 

The commands are related in that commands can be received in any 
order, and they have some  common structure, but each specific 
command is distinct -- typically in terms of the fields defined
within the command.

The processors, too, are related, in that they represent 
alternative implementations of the same interface.  Each processor
supports a subset of the commands, and these subsets may overlap
(i.e., two processors may support the same command).  The
way that each processor executes a particular command may be
completely different.  In general, command execution requires
detailed knowledge of the internal representation of the processor,
as well as the structure and fields of the command itself.
Furthermore, there may be multiple instances of each "kind" of
processor.

The set of commands may change over time (typically, new commands
will be added.  But it is possible that existing commands will
be modified or deleted).  Also, the various processors may be
"upgraded" to support additional commands.

What I'm trying to do is define the commands, the processors, and
the mechanism for executing commands on the processors so as to 
reduce redundant and error-prone coding, and make it easier to add
new commands, new processors, or new processor command execution
support.

So far, I've been trying to devise some kind of multiple-dispatching
or redispatching architecture -- I've also tried to work in mixins --
to avoid parallel "if" or "case" statements, but I haven't gotten it
to work.  I suspect I'm either on entirely the wrong track, or I've
missed something really obvious.

Here are some of the things I've tried:

It seems "obvious" to me that the commands represent a family of
types.   There is a Root_Command type, with the general command
operations (the commands are received as a stream of bytes which
must be parsed and formatted into their internal representation).

Each specific command type is derived from the Root_Command type.
At this point, the family is 1-deep.  That is, all specific 
commands are derived directly from Root_Command; no commands are 
derived from other commands.  However, that may change (and it 
greatly complicates maintenance for if/case statememt based 
approaches).

So I have something like this:

with Supporting_Stuff;
package Commands is

    type Root_Command is abstract tagged private;

    function Parse_Command (Input : in Bytes) return Root_Command 
        is abstract;

    -- other general Command subprograms.  Not necessarily abstract

private 

    type Root_Command is ...

end Commands;

with Commands;
package Specific_Commands is

    type Command_1 is new Root_Command with ...

    function Parse_Command ...


    type Command_2 is new Root_Command with ...

    function Parse_Command ...

end Specific_Commands.


Similarly, since the Processors are "alternative implementations", 
an abstract root class with specific derived types for the various
implementations seemed obvious.  Each instance of a processor has 
some "fetch" function available:

function Get_Next_Command (P : Processor) return Root_Command'Class;

and some way to Execute specific commands. The objective was to be 
able to  write something like the following for each processor:

loop
    declare 
        Cmd : Root_Command'Class := Get_Next_Command(Myself);
    begin
        Execute (Myself, Cmd);
    end;
end loop;

where the Execute() procedure would dispatch on the specific Command
type, to some procedure written for that command and the current
processor.  With C different specific commands, and P different
processor variations, there could be up to (C * P) different Execute
procedures.  That's fine.  I want to be able to just write a new
Execute procedure, and have it "automatically" picked up (e.g., by
dispatching).  In particular, what I want to avoid is something like
the following:

loop
    declare 
        Cmd : Root_Command'Class := Get_Next_Command(Myself);
    begin
        if Cmd in Command_1'Class then
            Execute_Cmd_1 (Myself, Command_1(Cmd));
        elsif Cmd in Command_2'Class then
            Execute_Cmd_2 (Myself, Command_2(Cmd));
         ...
         end if;
    end;
end loop;

Initially, I made Execute a primitive operation of Root_Command.
However, that required that Commands know about Processors, which
seemed backwards.  Furthermore, it couldn't support multiple
processor variations:

-- In Commands:
procedure Execute (P : in out Root_Processors'Class;
                   Cmd : in Root_Comand) is
begin
    P_Execute( P, Root_Command'Class(Cmd));
    -- where P_Execute is a primitive operation of 
    -- Root_Processor, and so is dispatching on P.
end Execute;

Even if Execute turned around and redispatched on the Processor
parameter to P_Execute, P_Execute still has to somehow figure 
out which specific command is coming in.  I can't have two 
controlling operands in Execute, so one has to be class-wide.

I looked at making Execute a primitive operation of Processors,
but that has the inverse problem: I can dispatch on specific 
processors (which isn't really necessary, anyway, since execution
stays within the same command/processor pipeline), but I can't 
then dispatch on the Commands.

I thought about mixin's, but I'm really not dealing with 
independent types.  Commands and Processors are related; I'm not
trying to add an orthogonal facet to, say, an Address_Book class.

Now, I can get dispatching on Commands within the different 
Processor variations by using creating second-level 
Commands derived in parallel for each supported specific command:

-- In Commands:
procedure Execute (P : in out Root_Processor'Class;
                   Cmd : in Root_Commands);
-- has "null" body.

with Specific_Commands;
package Processor_1_Commands is

    type P1_Command_1 is new Specific_Commands.Command_1 with null
record;

    procedure Execute (P : in out Root_Processor'Class;
                      Cmd : in P1_Command_1);
    -- keep inherited Command operations, like Parse_Command).

    -- etc.
end Processor_1_Commands;

And in the body of Processor_1_Commands, implement Execute to 
require and operate on a Processor_1 type.  Similarly, for 
Processor_2.  Unfortunately, this means that the Get_Next_Command
function has to return one of the P1_Command_x commands when 
called from Processor_1, and return a P2_Command_x when called
from Processor_2.   Only, the command structures are identical, 
so the only difference would be which specific Processor-Command
type the factory called.  Parallel code, again.

So my dilemma:
I _can_ solve the problem using Ada83-esque if/case statements.
But this seems like such a "mormal" thing to want to do.  It 
can't be that obscure; I can't believe there isn't some feature
or combination of features in Ada95 that will let me do this
cleanly.  Does anyone have any ideas?


-- 

-- Thom Brooke
-- Cut out "_CUT_OUT" to get my real email address.

Re: Design problem using Multiple Dispatch or Redispatch (long)

[David Kristola]

On Mon, 13 Mar 2000 18:59:57 -0800, Thom Brooke wrote
(in message <38CDAA56.36B9E1C1@yahoo.com>):
> Does anyone have any ideas? 

I'm not sure if this helps any (it is late, and i didn't follow all
of your post, sorry).

First, i think you might want to check out John Volan's page on the
"with-ing" problem (and solution).

http://home.bluemarble.net/~jvolan/WithingProblem/FAQ.html

Second, perhaps some sort of registration and match process could
help.  Processors could register with some dispatcher (not tagged
type dispatching), and provide a pattern matcher that identifies
a byte pattern that will be accepted by the processor.  Given new
input, the dispatcher would search down it's list of pattern
matchers until it finds a match, then call the associated processor.

--djk
email not spam to David95037 (at the dot com called america on-line)

Re: Design problem using Multiple Dispatch or Redispatch (long)

[tmoran]

Suppose you could have a two dimension dispatch table and dispatch
on both parameters in
  Execute(A_Processor, A_Command);
You said different processors execute different subsets of commands,
so, since the table couldn't have any holes, you would have to
have dummy entries - returning an error condition, say.  That
means that any time you add a new command, you'll have to add it,
or at least a dummy Execute for it, to each processor, and each
time you add a processor it will need Execute's for all known
commands.  Is that OK?

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Nick Roberts]

First, you define an access-to-procedure type as follows:

    type Command_Executor is procedure (Command: Root_Command_Type'Class;
                                            Processor:
Root_Processor_Type'Class);

Now - and this is the key bit - you define two types which classify your
commands and processors:

    type Command_Category is (...);
    type Processor_Category is (...);

And functions that will categorise a command or processor:

    function Category (Command: in Root_Command_Type) return
Command_Category;
    function Category (Processor: in Root_Processor_Type) return
Processor_Category;

Now you declare an array which relates categories to executors:

    Executor: constant array (Command_Category,
                                        Processor_Category) of
Command_Executor :=
        (Elbow_Bending =>
            Teenagers => Execute_Bend_Elbow_On_Teenager'Access,
            Twentysomethings =>
Execute_Bend_Elbow_On_Twentysomething'Access,
            ...
            Ancient_Crinklies => null);
         ...);

Null access values are used to indicate which kinds of command cannot be
executed by which kinds of processor. Note how commands and processors can
be added without necessarily having to change this lookup table (provided
they fit into existing categories). I've made the array constant, so the
addition of a new category could prompt substantial recompilation: if this
might be a problem, you might want to consider using a variable table, with
some kind of dynamic 'registration' method for populating it.

--
Nick Roberts
http://www.adapower.com/lab/adaos

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Simon Wright]

The code below may do what you want. There will be lots more (creating
new Real_Commands, for example, for a specific Processor; keeping a
queue of Commands, popping, and dispatching; and, because Command is
(has to be) limited, you'll need to manage allocated Commands as
well).

No need for arrays, sparse or otherwise.

package Commands is
  type Command is abstract tagged limited private;
  type Command_P is access all Command'Class;
  procedure Handle (The_Command : Command) is abstract;
private
  type Command is abstract tagged limited null record;
end Commands;

package Processors is
  type Processor is abstract tagged limited private;
private
  type Processor is abstract tagged limited null record;
end Processors;

with Commands;
with Processors;
package Real_Processors is
  type Real_Processor is new Processors.Processor with private;
  type Real_Command (For_The_Processor : access Real_Processor)
  is new Commands.Command with private;
  procedure Handle (The_Command : Real_Command);
  -- other Real_Commands here, each with its own Handle
private
  type Real_Processor is new Processors.Processor
     with null record;
  type Real_Command (For_The_Processor : access Real_Processor)
  is new Commands.Command with null record;
end Real_Processors;

package body Real_Processors is
  procedure Handle (The_Command : Real_Command) is
    The_Processor : Real_Processor renames The_Command.For_The_Processor.all;
  begin
    null; -- do stuff for this Command for this Processor
  end Handle;
end Real_Processors;

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Thom Brooke]

Nick Roberts wrote:
> 
> First, you define an access-to-procedure type as follows:
> 
>     type Command_Executor is procedure (Command: Root_Command_Type'Class;
>                                             Processor:
> Root_Processor_Type'Class);
> 
> Now - and this is the key bit - you define two types which classify your
> commands and processors:
> 
>     type Command_Category is (...);
>     type Processor_Category is (...);
> 
> And functions that will categorise a command or processor:
> 
>     function Category (Command: in Root_Command_Type) return
> Command_Category;
>     function Category (Processor: in Root_Processor_Type) return
> Processor_Category;
> 
> Now you declare an array which relates categories to executors:
> 
>     Executor: constant array (Command_Category,
>                                         Processor_Category) of
> Command_Executor :=
>         (Elbow_Bending =>
>             Teenagers => Execute_Bend_Elbow_On_Teenager'Access,
>             Twentysomethings =>
> Execute_Bend_Elbow_On_Twentysomething'Access,
>             ...
>             Ancient_Crinklies => null);
>          ...);
> 
> Null access values are used to indicate which kinds of command cannot be
> executed by which kinds of processor. Note how commands and processors can
> be added without necessarily having to change this lookup table (provided
> they fit into existing categories). I've made the array constant, so the
> addition of a new category could prompt substantial recompilation: if this
> might be a problem, you might want to consider using a variable table, with
> some kind of dynamic 'registration' method for populating it.
> 
> --
> Nick Roberts
> http://www.adapower.com/lab/adaos

I was looking at something like this.  Although it was more
Processor-centric,
in that each Processor would define its own Command/Execution
association table.
Command "categorization" would have been more by a
"chain-of-responsibility" pattern.

Unfortunately, each Command really is unique, so each one has distinct
Execute for
each supporting processor.

Thanks.  I'll give this a try.

-- 

-- Thom Brooke
-- Cut out "_CUT_OUT" to get my real email address.

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Thom Brooke]

tmoran@bix.com wrote:
> 
> Suppose you could have a two dimension dispatch table and dispatch
> on both parameters in
>   Execute(A_Processor, A_Command);
> You said different processors execute different subsets of commands,
> so, since the table couldn't have any holes, you would have to
> have dummy entries - returning an error condition, say.  That
> means that any time you add a new command, you'll have to add it,
> or at least a dummy Execute for it, to each processor, and each
> time you add a processor it will need Execute's for all known
> commands.  Is that OK?

Yes, this would work.  And it's kind of along the line I was heading.

But I'm really trying to avoid any kind of "explicit dispatching"; I'd
like to get the compiler/run-time to do it for me :-)

Of course, if that doesn't work, I'll be back to this.

Thanks.
-- 

-- Thom Brooke
-- Cut out "_CUT_OUT" to get my real email address.

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Thom Brooke]

David Kristola wrote:
> 
> On Mon, 13 Mar 2000 18:59:57 -0800, Thom Brooke wrote
> (in message <38CDAA56.36B9E1C1@yahoo.com>):
> > Does anyone have any ideas?
> 
> I'm not sure if this helps any (it is late, and i didn't follow all
> of your post, sorry).
> 
> First, i think you might want to check out John Volan's page on the
> "with-ing" problem (and solution).
> 
> http://home.bluemarble.net/~jvolan/WithingProblem/FAQ.html
> 
> Second, perhaps some sort of registration and match process could
> help.  Processors could register with some dispatcher (not tagged
> type dispatching), and provide a pattern matcher that identifies
> a byte pattern that will be accepted by the processor.  Given new
> input, the dispatcher would search down it's list of pattern
> matchers until it finds a match, then call the associated processor.
> 
> --djk
> email not spam to David95037 (at the dot com called america on-line)

Wow.  Lots of information on that page.  It's going to take a little 
while to dig through it all.  I'll let you know if it helps.

Thanks.
-- 

-- Thom Brooke
-- Cut out "_CUT_OUT" to get my real email address.

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Thom Brooke]

Hmmm.  I tried something like this, and ran into the following problem:
I couldn't avoid duplicate code to construct the Real_Commands for the 
different processors.

Consider a command that has three fields:  ID, Number, and Version.  And 
two kinds of Processors.  I would do this, right?

with Commands;
with Processors;
package Real_Processor1 is

    type Processor1 is new Processors.Processor with private;

    type Command1 (For_The : access Processor1) is new Commands.Command
with private;
    procedure Handle (The_Command : Command1);
    -- and I added this as a new primitive abstract operation:
    procedure Construct (The_Command : in out Command1; From : in
Byte_Stream);
private
    type Processor1 is new Processors.Processor with ...

    type Command1 (For_The : access Processor1) is new Commands.Command
with record
        ID : Natural;
        Number : Integer;
        Version : Positive;
    end record;
end Real_Processor1;

-- same thing for Real_Processor2

So the problem is, how can I write the "Construct" procedure one time
(the resulting
Commands will look identical, and they come from identical byte
streams.  The only
difference is one is of type Real_Processor1.Command1, and the other is
of the
completely different, but structurally identical type
Real_Processor2.Command1)?

Am I missing something obvious?

-- Thom 

Simon Wright wrote:
> 
> The code below may do what you want. There will be lots more (creating
> new Real_Commands, for example, for a specific Processor; keeping a
> queue of Commands, popping, and dispatching; and, because Command is
> (has to be) limited, you'll need to manage allocated Commands as
> well).
> 
> No need for arrays, sparse or otherwise.
> 
> package Commands is
>   type Command is abstract tagged limited private;
>   type Command_P is access all Command'Class;
>   procedure Handle (The_Command : Command) is abstract;
> private
>   type Command is abstract tagged limited null record;
> end Commands;
> 
> package Processors is
>   type Processor is abstract tagged limited private;
> private
>   type Processor is abstract tagged limited null record;
> end Processors;
> 
> with Commands;
> with Processors;
> package Real_Processors is
>   type Real_Processor is new Processors.Processor with private;
>   type Real_Command (For_The_Processor : access Real_Processor)
>   is new Commands.Command with private;
>   procedure Handle (The_Command : Real_Command);
>   -- other Real_Commands here, each with its own Handle
> private
>   type Real_Processor is new Processors.Processor
>      with null record;
>   type Real_Command (For_The_Processor : access Real_Processor)
>   is new Commands.Command with null record;
> end Real_Processors;
> 
> package body Real_Processors is
>   procedure Handle (The_Command : Real_Command) is
>     The_Processor : Real_Processor renames The_Command.For_The_Processor.all;
>   begin
>     null; -- do stuff for this Command for this Processor
>   end Handle;
> end Real_Processors;

-- 

-- Thom Brooke
-- Cut out "_CUT_OUT" to get my real email address.

Re: Design problem using Multiple Dispatch or Redispatch (long)

[Simon Wright]

Thom Brooke <tcb_cut_out_80908@yahoo.com> writes:

> Consider a command that has three fields: ID, Number, and Version.
> And two kinds of Processors.  I would do this, right?
> 
> with Commands;
> with Processors;
> package Real_Processor1 is
> 
>     type Processor1 is new Processors.Processor with private;
> 
>     type Command1 (For_The : access Processor1)
>     is new Commands.Command with private;
>     procedure Handle (The_Command : Command1);
>     -- and I added this as a new primitive abstract operation:
>     procedure Construct (The_Command : in out Command1;
>                          From : in Byte_Stream);
> 
> -- same thing for Real_Processor2
> 
> So the problem is, how can I write the "Construct" procedure one
> time (the resulting Commands will look identical, and they come from
> identical byte streams.  The only difference is one is of type
> Real_Processor1.Command1, and the other is of the completely
> different, but structurally identical type
> Real_Processor2.Command1)?

Are lots of commands repeated for different processors? in the
application form which this came, they were all wildly different.

I suppose you could have an intermediate Shared_Command with a
Construct? (could it still be abstract?)

  type Shared_Command is abstract new Command with private;
  procedure Construct (The_Command : in out Shared_Command;
                       From : in Byte_Stream);

and then in the Real_Processor1 package

  type Command1 is new Shared_Command with private;
  procedure Handle (The_Command : Command1);

-- 
Simon Wright                        Work Email: simon.j.wright@gecm.com
Alenia Marconi Systems                        Voice: +44(0)23-92-701778
Integrated Systems Division                     FAX: +44(0)23-92-701800