Breaking a circularity

Breaking a circularity

[Gene]

Need some expert help here with a circularity in the data structures
for a discrete event simulation.

We need event queues and an arbitrary number of event types.  The
handlers for events must have access to a simulation state record, so
used a generic thus:

generic
   type State_Type is private;
package Event_Queues is

   type Event_Type is abstract tagged limited private;

   procedure Handle(State : in out State_Type;
                    Event : access Event_Type) is abstract;

   type Event_Ptr_Type is access all Event_Type'Class;

   procedure Add(Event_Queue : in out Event_Queue_Type;
                 Time : in Time_Type;
                 Event : access Event_Type'Class);

   -- other methods not shown.
private

   type Event_Type is abstract record
      Id : Positive;
      Time : Time_Type;
   end record;

   function Sooner_Than(A, B : in Event_Ptr_Type) return Boolean;

   -- We are just going to put a thin wrapper around Ada ordered sets
to
   -- implement our event queue.
   package Event_Queues is
     new Ada.Containers.Ordered_Sets(Event_Ptr_Type, Sooner_Than,
"=");
   type Event_Queue_Type is new Event_Queues.Set with null record;

end Event_Queues;

Here's the circularity:  Instantiating an event queue requires the
simulation state type, but the simulation state must contain an event
queue (of the instantiated type).

This is the best I've come up with so far:

private
   type Event_Queue_Wrapper_Type;

   type State_Type is
      record
         Future_Events : access Event_Queue_Wrapper_Type;
         -- other stuff not shown
      end record;

   package Simulation_Events is
     new Event_Queues(State_Type);

   -- Now we can define the wrapper to contain the event queue.
   type Event_Queue_Wrapper_Type is
      record
         Queue : Simulation_Events.Event_Queue_Type;
      end record;

Is there a cleaner way to do this?  The painful part is introducing a
pointer to the event queue in State_Type just to break the
circularity, when this seems superfluous and means I should make
State_Type controlled to release the queue.

Re: Breaking a circularity

[Ludovic Brenta]

Gene wrote on comp.lang.ada:
> Need some expert help here with a circularity in the data structures
> for a discrete event simulation.
>
> We need event queues and an arbitrary number of event types.  The
> handlers for events must have access to a simulation state record, so
> used a generic thus:
[...]
> Here's the circularity:  Instantiating an event queue requires the
> simulation state type, but the simulation state must contain an event
> queue (of the instantiated type).
[...]
> Is there a cleaner way to do this?  The painful part is introducing a
> pointer to the event queue in State_Type just to break the
> circularity, when this seems superfluous and means I should make
> State_Type controlled to release the queue.

How about this:

generic
   type State_Type is tagged private;
package States_With_Event_Queues is

   type State_With_Event_Queue_Type is new State_Type with private;

   type Event_Type is abstract tagged limited private;

   procedure Handle(State : in out State_Type;
                    Event : access Event_Type) is abstract;

   type Event_Ptr_Type is access all Event_Type'Class;

   procedure Add(Event_Queue : in out Event_Queue_Type;
                 Time : in Time_Type;
                 Event : access Event_Type'Class);

   -- other methods not shown.
private

   type Event_Type is abstract record
      Id : Positive;
      Time : Time_Type;
   end record;

   function Sooner_Than(A, B : in Event_Ptr_Type) return Boolean;

   -- We are just going to put a thin wrapper around Ada ordered sets
   -- to implement our event queue.
   package Event_Queues is
     new Ada.Containers.Ordered_Sets(Event_Ptr_Type, Sooner_Than,
"=");
   type Event_Queue_Type is new Event_Queues.Set with null record;

   type State_With_Event_Queue_Type is new State_Type with record
      Event_Queue : Event_Queue_Type;
   end record;

end States_With_event_Queues;



Would that work?

BTW, why does Event_Type have to be limited? If it weren't limited,
you would not need Event_Ptr_Type.  Also, why does it have to be
abstract?

--
Ludovic Brenta.

Re: Breaking a circularity

[Simon Wright]

How is the Event_Queue going to know which instance of State_Type to
pass to a call of Handle (State, Event)?

Could the same State instance be passed to more than one Event_Queue?

Will you really be using different State_Types? (just checking.) 

You could try constraining an Event_Queue by "access State_Type'Class".

Should State_Type be tagged as well as Event_Type? (I realise this ends
up double-dispatching in Handle, would need to be class-wide in -
probably - State_Type.)

I think that with this sort of problem you are going to have to bite the
bullet and use access and controlled types (well, controlled if you are
going to delete queues. If not, why bother?)

Re: Breaking a circularity

[Martin]

On Mar 28, 5:11 am, Gene <gene.ress...@gmail.com> wrote:
> Need some expert help here with a circularity in the data structures
> for a discrete event simulation.
>
> We need event queues and an arbitrary number of event types.  The
> handlers for events must have access to a simulation state record, so
> used a generic thus:
>
> generic
>    type State_Type is private;
> package Event_Queues is
>
>    type Event_Type is abstract tagged limited private;
>
>    procedure Handle(State : in out State_Type;
>                     Event : access Event_Type) is abstract;
>
>    type Event_Ptr_Type is access all Event_Type'Class;
>
>    procedure Add(Event_Queue : in out Event_Queue_Type;
>                  Time : in Time_Type;
>                  Event : access Event_Type'Class);
>
>    -- other methods not shown.
> private
>
>    type Event_Type is abstract record
>       Id : Positive;
>       Time : Time_Type;
>    end record;
>
>    function Sooner_Than(A, B : in Event_Ptr_Type) return Boolean;
>
>    -- We are just going to put a thin wrapper around Ada ordered sets
> to
>    -- implement our event queue.
>    package Event_Queues is
>      new Ada.Containers.Ordered_Sets(Event_Ptr_Type, Sooner_Than,
> "=");
>    type Event_Queue_Type is new Event_Queues.Set with null record;
>
> end Event_Queues;
>
> Here's the circularity:  Instantiating an event queue requires the
> simulation state type, but the simulation state must contain an event
> queue (of the instantiated type).
>
> This is the best I've come up with so far:
>
> private
>    type Event_Queue_Wrapper_Type;
>
>    type State_Type is
>       record
>          Future_Events : access Event_Queue_Wrapper_Type;
>          -- other stuff not shown
>       end record;
>
>    package Simulation_Events is
>      new Event_Queues(State_Type);
>
>    -- Now we can define the wrapper to contain the event queue.
>    type Event_Queue_Wrapper_Type is
>       record
>          Queue : Simulation_Events.Event_Queue_Type;
>       end record;
>
> Is there a cleaner way to do this?  The painful part is introducing a
> pointer to the event queue in State_Type just to break the
> circularity, when this seems superfluous and means I should make
> State_Type controlled to release the queue.


Not sure you can do better in the sense of removing the access but
perhaps you can bundle all that up into a generic wrapper? e.g.

package States is
   type State is record
      I : Integer;
   end record;
end States;

with Ada.Containers.Ordered_Sets;
generic
   type State_Type is private;
package Event_Queues is
   subtype Time_Type is Duration;
   type Event_Type is abstract tagged limited private;
   procedure Handle (State : in out State_Type;
                     Event : access Event_Type) is abstract;
   type Event_Ptr_Type is access all Event_Type'Class;
   type Event_Queue_Type is private;
   procedure Add (Event_Queue : in out Event_Queue_Type;
                  Time        : in     Time_Type;
                  Event       : access Event_Type'Class);
private
   type Event_Type is abstract tagged limited record
      Id   : Positive;
      Time : Time_Type;
   end record;
   function Sooner_Than (A, B : in Event_Ptr_Type) return Boolean;
   package Event_Queues is new Ada.Containers.Ordered_Sets
(Event_Ptr_Type, Sooner_Than, "=");
   type Event_Queue_Type is new Event_Queues.Set with null record;
end Event_Queues;

with Event_Queues;
generic
   type State_Type is private;
package Event_Queue_Wrappers is
   type Event_Queue_Wrapper_Type is private;
private
   type EQW_State_Type is
      record
         State         : State_Type;
         Future_Events : access Event_Queue_Wrapper_Type;
      end record;
   package Simulation_Events is new Event_Queues (EQW_State_Type);
   type Event_Queue_Wrapper_Type is record
         Queue : Simulation_Events.Event_Queue_Type;
      end record;
end Event_Queue_Wrappers;

with Event_Queue_Wrappers;
with States;

procedure Temp is
   package EQW is new Event_Queue_Wrappers (State_Type =>
States.State);
   EQ : EQW.Event_Queue_Wrapper_Type;
begin
   null;
end Temp;


At least that decouples the state your interested in from the queue
mechanism.

Better names might help too, why expose that it is a 'wrapper' to the
user? I'd probably call what I have a '_Wrapper' as 'Event_Queue' and
then find a better name for the Event_Queues - Event_Queues_With_State
perhaps.

-- Martin

Re: Breaking a circularity

[Simon Wright]

Ludovic Brenta <ludovic@ludovic-brenta.org> writes:

> BTW, why does Event_Type have to be limited? If it weren't limited,
> you would not need Event_Ptr_Type.  Also, why does it have to be
> abstract?

When I made my events limited, it was because any two events are
different. In this case, we have

   type Event_Type is abstract record
      Id : Positive;
      Time : Time_Type;
   end record;

so it probably won't make any sense for an Event to be copyable (what
would Id be in the copy?). Of course the events could be privately
nonlimited.

I do wonder what Id is _for_.

You'll certainly need pointers somewhere, because Event_Type instances
have to be held in the Queue. Indefinite_Ordered_Sets might do the
trick, though. It would save the bother of having Handle deallocate the
Event.

Re: Breaking a circularity

[Gene]

On Mar 28, 5:59 am, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:
> Gene wrote on comp.lang.ada:
>
> > Need some expert help here with a circularity in the data structures
> > for a discrete event simulation.
>
> > We need event queues and an arbitrary number of event types.  The
> > handlers for events must have access to a simulation state record, so
> > used a generic thus:
> [...]
> > Here's the circularity:  Instantiating an event queue requires the
> > simulation state type, but the simulation state must contain an event
> > queue (of the instantiated type).
> [...]
> > Is there a cleaner way to do this?  The painful part is introducing a
> > pointer to the event queue in State_Type just to break the
> > circularity, when this seems superfluous and means I should make
> > State_Type controlled to release the queue.
>
> How about this:
>
> generic
>    type State_Type is tagged private;
> package States_With_Event_Queues is
>
>    type State_With_Event_Queue_Type is new State_Type with private;
>
>    type Event_Type is abstract tagged limited private;
>
  [...]
>    -- other methods not shown.
> private
>
  [...]
>    -- We are just going to put a thin wrapper around Ada ordered sets
>    -- to implement our event queue.
>
> end States_With_event_Queues;
>
> Would that work?

Interesting.  Ought to be fine, but

>
> BTW, why does Event_Type have to be limited? If it weren't limited,
> you would not need Event_Ptr_Type.  

Events are "serial numbered" at creation time and meant to be unique.
Pointer equality should be equivalent to content equality.

> Also, why does it have to be
> abstract?

Events only have meaning in their specializations to particular kinds,
i.e. requests, mission starts, mission completions, etc.  So the root
event type is just an (abtract) placeholder, not something you'd want
to create.

Thanks again.

Re: Breaking a circularity

[Gene]

On Mar 28, 6:15 am, Simon Wright <si...@pushface.org> wrote:
> How is the Event_Queue going to know which instance of State_Type to
> pass to a call of Handle (State, Event)?

There is currently only one state per simulation. The user of an
Event_Queue
instantiation is in a tight loop removing events from its event queue
(which is embedded in its state), then calling Handle(State, Event)
using its current state.  This is dispatched to the correct handler
based on (derived) event type. Handlers often schedule new events
in the same event queue.  It's essentially a callback.  The state is
the callback's execution context.
>
> Could the same State instance be passed to more than one Event_Queue?
>

It's easy to imagine simulations needing more than one event queue.
These would all need access through the state. But the current
application has only a single queue.

> Will you really be using different State_Types? (just checking.)

Not in this version, but it's foreseeable.

>
> You could try constraining an Event_Queue by "access State_Type'Class".
>
> Should State_Type be tagged as well as Event_Type? (I realise this ends
> up double-dispatching in Handle, would need to be class-wide in -
> probably - State_Type.)
>
> I think that with this sort of problem you are going to have to bite the
> bullet and use access and controlled types (well, controlled if you are
> going to delete queues. If not, why bother?)

Thanks for the ideas.

Re: Breaking a circularity

[Gene]

> Better names might help too, why expose that it is a 'wrapper' to the
> user? I'd probably call what I have a '_Wrapper' as 'Event_Queue' and
> then find a better name for the Event_Queues - Event_Queues_With_State
> perhaps.
>
> -- Martin-

Thanks.  But the only routine that needs to mention "Wrapper" is the
initializer
for the State.  In this case, Wrapper says pretty clearly what's going
on.
Throughout all other code, it's

State.Future_Events.Queue

which is pretty clear as well.

Re: Breaking a circularity

[Gene]

On Mar 28, 7:37 am, Simon Wright <si...@pushface.org> wrote:
> Ludovic Brenta <ludo...@ludovic-brenta.org> writes:
> > BTW, why does Event_Type have to be limited? If it weren't limited,
> > you would not need Event_Ptr_Type.  Also, why does it have to be
> > abstract?
>
> When I made my events limited, it was because any two events are
> different. In this case, we have
>
>    type Event_Type is abstract record
>       Id : Positive;
>       Time : Time_Type;
>    end record;
>
> so it probably won't make any sense for an Event to be copyable (what
> would Id be in the copy?). Of course the events could be privately
> nonlimited.

Yes.

>
> I do wonder what Id is _for_.

For tracing simulations.  They're consecutive in temporal order.

>
> You'll certainly need pointers somewhere, because Event_Type instances
> have to be held in the Queue. Indefinite_Ordered_Sets might do the
> trick, though. It would save the bother of having Handle deallocate the
> Event.

Yes and no.  The only reason for making Event_Queue generic is
so that a State can be passed through the dispatching Handle call.
Since this is an "in out" parameter that's invariably a record type,
it's being passed by pointer behind the scenes.  Yet there doesn't
seem
to be a way to take advantage of *this* pointer for breaking the
circularity.  (In (eeewwww) C  we could use a void* or other pointer
trick here.)

E.g. if there were a generic parameter type for "access to
incompletely
declared type," we could pull it off by making Event_Queue generic in
this way.

Re: Breaking a circularity

[Randy Brukardt]

"Gene" <gene.ressler@gmail.com> wrote in message 
news:f22049a1-0983-4c22-ba94-b5da81aaba88@s9g2000yqm.googlegroups.com...
On Mar 28, 7:37 am, Simon Wright <si...@pushface.org> wrote:
>Yes and no.  The only reason for making Event_Queue generic is
>so that a State can be passed through the dispatching Handle call.
>Since this is an "in out" parameter that's invariably a record type,
>it's being passed by pointer behind the scenes.  Yet there doesn't
>seem
>to be a way to take advantage of *this* pointer for breaking the
>circularity.  (In (eeewwww) C  we could use a void* or other pointer
>trick here.)

The way we handled this problem in Claw was to make State an abstract tagged 
type (rather than using a generic). Then, the parameter to the Handle call 
can be class-wide, which allows it to access any extension of the type.

I suspect that this also breaks the circularity (since the State type 
doesn't need to be defined until much later), but I haven't tried to figure 
it out.

                    Randy.

Re: Breaking a circularity

[Martin]

On Mar 28, 11:26 pm, Gene <gene.ress...@gmail.com> wrote:
> > Better names might help too, why expose that it is a 'wrapper' to the
> > user? I'd probably call what I have a '_Wrapper' as 'Event_Queue' and
> > then find a better name for the Event_Queues - Event_Queues_With_State
> > perhaps.
>
> > -- Martin-
>
> Thanks.  But the only routine that needs to mention "Wrapper" is the
> initializer
> for the State.  In this case, Wrapper says pretty clearly what's going
> on.
> Throughout all other code, it's
>
> State.Future_Events.Queue
>
> which is pretty clear as well.

Yeah, I just meant if you added the extra generic layer, it might be
worth a renaming.

And between generics and package renames you can always replace
horrible names with 'good names' very easily. :-)

-- Martin