* Smarter Generics
@ 2004-08-14 19:55 Frank J. Lhota
2004-08-15 1:14 ` Georg Bauhaus
` (3 more replies)
0 siblings, 4 replies; 8+ messages in thread
From: Frank J. Lhota @ 2004-08-14 19:55 UTC (permalink / raw)
The recent thread on "A Simple Ada Problem" got me thinking about a
limitation of Ada generics. Generic are a great way of generalizing an
implementation strategy for a particular problem, but generics cannot (or
cannot easily) select one of several implementation strategies based on the
generic parameters.
Take the following simple example: Assume that I want to implement stacks of
limited length, e.g. a stack that I can push or pop elements of a given
type, but with a limit on how many elements will be on the stack at one
time:
generic
type Stack_Element is private;
Max_Length : in Positive;
package Limited_Stacks is
type Stack_Type is limited private;
Stack_Overflow, Stack_Underflow : exception;
procedure Push ( Item : in Stack_Element; Onto : in out
Stack_Type );
procedure Pop ( Item : out Stack_Element; Onto : in out
Stack_Type );
private
...
end Limited_Stacks;
Two possible implementation strategies:
1. We could implement the stack as an array of Max_Length elements, along
with a component indicating the current length.
2. We could maintain an adjustable list of pointers to elements allocated
from the heap.
Obviously, implementation 1 would be faster and more convenient if
Max_Length * Stack_Element'Size is relatively small. Implementation 2
involves additional overhead, but can handle cases where stack elements can
vary quite a bit in size.
What would be great is if there were some way to write Limited_Stacks so
that the implementation strategy could be chosen based on the generic
parameters, so that we could do something like this:
if Max_Length * Stack_Element'Size <= Some_Threshold then
-- Static memory allocation should be fine
Implement Limited_Stacks using strategy 1;
else
-- Size could be a problem, better go with pointers.
Implement Limited_Stacks using strategy 2;
end if;
AFAIK neither Ada generics nor C++ templates have this level of
intelligence. Would smarter generics be a worthwhile addition to Ada, and if
so, what form should it take?
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-14 19:55 Smarter Generics Frank J. Lhota
@ 2004-08-15 1:14 ` Georg Bauhaus
2004-08-15 1:32 ` Francois G. Dorais
` (2 subsequent siblings)
3 siblings, 0 replies; 8+ messages in thread
From: Georg Bauhaus @ 2004-08-15 1:14 UTC (permalink / raw)
Frank J. Lhota <NOSPAM.lhota.adarose@verizon.net> wrote:
: What would be great is if there were some way to write Limited_Stacks so
: that the implementation strategy could be chosen based on the generic
: parameters, so that we could do something like this:
The following can be compiled, don't know if it is sufficiently
general, though.
generic
type Stack_Element is private;
Max_Length : in Positive;
package Dyn_Stacks is
type Stack_Type is limited private;
Stack_Overflow, Stack_Underflow : exception;
procedure Push ( Item : in Stack_Element; Onto : in out Stack_Type );
procedure Pop ( Item : out Stack_Element; Onto : in out Stack_Type );
private
Some_Threshold: constant := 1_000;
subtype Stack_Array_Index is Natural range 0 .. Some_Threshold;
type Stack_Array is array(Stack_Array_Index) of Stack_Element;
type Implementation is tagged null record;
-- not yet decided what strategy to use, maybe abstract?
type Array_Implementation is new Implementation with record
items: Stack_Array;
end record;
type List_Implementation is new Implementation with record
null; -- replace with a list type
end record;
type Strategy(which: Boolean) is limited record
case which is
when False =>
a_items: Array_Implementation;
when true =>
l_item: List_Implementation;
end case;
end record;
type Stack_Type is new Strategy(Max_Length > Some_Threshold);
-- there we are ;-)
end Dyn_Stacks;
-- Georg
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-14 19:55 Smarter Generics Frank J. Lhota
2004-08-15 1:14 ` Georg Bauhaus
@ 2004-08-15 1:32 ` Francois G. Dorais
2004-08-16 5:36 ` Wes Groleau
2004-08-16 13:52 ` Jean-Marc Bourguet
3 siblings, 0 replies; 8+ messages in thread
From: Francois G. Dorais @ 2004-08-15 1:32 UTC (permalink / raw)
Frank J. Lhota wrote:
> The recent thread on "A Simple Ada Problem" got me thinking about a
> limitation of Ada generics. Generic are a great way of generalizing an
> implementation strategy for a particular problem, but generics cannot (or
> cannot easily) select one of several implementation strategies based on the
> generic parameters.
>
> Take the following simple example: Assume that I want to implement stacks of
> limited length, e.g. a stack that I can push or pop elements of a given
> type, but with a limit on how many elements will be on the stack at one
> time:
>
> generic
> type Stack_Element is private;
> Max_Length : in Positive;
> package Limited_Stacks is
>
> type Stack_Type is limited private;
> Stack_Overflow, Stack_Underflow : exception;
>
> procedure Push ( Item : in Stack_Element; Onto : in out
> Stack_Type );
> procedure Pop ( Item : out Stack_Element; Onto : in out
> Stack_Type );
>
> private
> ...
> end Limited_Stacks;
>
> Two possible implementation strategies:
>
> 1. We could implement the stack as an array of Max_Length elements, along
> with a component indicating the current length.
> 2. We could maintain an adjustable list of pointers to elements allocated
> from the heap.
>
> Obviously, implementation 1 would be faster and more convenient if
> Max_Length * Stack_Element'Size is relatively small. Implementation 2
> involves additional overhead, but can handle cases where stack elements can
> vary quite a bit in size.
>
> What would be great is if there were some way to write Limited_Stacks so
> that the implementation strategy could be chosen based on the generic
> parameters, so that we could do something like this:
>
> if Max_Length * Stack_Element'Size <= Some_Threshold then
> -- Static memory allocation should be fine
> Implement Limited_Stacks using strategy 1;
> else
> -- Size could be a problem, better go with pointers.
> Implement Limited_Stacks using strategy 2;
> end if;
>
> AFAIK neither Ada generics nor C++ templates have this level of
> intelligence. Would smarter generics be a worthwhile addition to Ada, and if
> so, what form should it take?
Hmmm... I guess Ada is smarter than C++ after all :)
-- Alternative Methods Example
generic
type Element_Type is private;
Stack_Limit : in Positive;
package Limited_Stacks is
type Limited_Stack_Type is limited private;
procedure Push (Stack : in out Limited_Stack_Type;
Item : in Element_Type);
procedure Pop (Stack : in out Limited_Stack_Type;
Item : out Element_Type);
function Method (Stack : in Limited_Stack_Type) return
String;
-- Returns "ARRAY" or "LIST" for testing purposes...
Stack_Overflow, Stack_Underflow : exception;
private
type Element_Array is array (1 .. Stack_Limit) of
Element_Type;
type Element_Record;
type Element_Pointer is access Element_Record;
type Element_Record is record
Item : Element_Type;
Pred : Element_Pointer;
end record;
Null_Element_Pointer : constant Element_Pointer := null;
type Limited_Stack_Alternative (Use_Array : Boolean) is
record
Stack_Length : Natural := 0;
case Use_Array is
when True =>
Stack_Array : Element_Array;
when False =>
Stack_Pointer : Element_Pointer :=
Null_Element_Pointer;
end case;
end record;
type Limited_Stack_Type is new Limited_Stack_Alternative
(Element_Type'Size * Stack_Limit <= 1024 * 8);
end Limited_Stacks;
with Ada.Unchecked_Deallocation;
package body Limited_Stacks is
procedure Free is new Ada.Unchecked_Deallocation
(Element_Record, Element_Pointer);
procedure Push (Stack : in out Limited_Stack_Type;
Item : in Element_Type) is
begin
if Stack.Stack_Length = Stack_Limit then
raise Stack_Overflow;
end if;
Stack.Stack_Length := Stack.Stack_Length + 1;
case Stack.Use_Array is
when True =>
Stack.Stack_Array(Stack.Stack_Length) := Item;
when False =>
declare
New_Pointer : Element_Pointer
:= new Element_Record'(Item => Item, Pred
=> Stack.Stack_Pointer);
begin
Stack.Stack_Pointer := New_Pointer;
end;
end case;
end Push;
procedure Pop (Stack : in out Limited_Stack_Type;
Item : out Element_Type) is
begin
if Stack.Stack_Length = 0 then
raise Stack_Underflow;
end if;
case Stack.Use_Array is
when True =>
Item := Stack.Stack_Array(Stack.Stack_Length);
when False =>
declare
Old_Pointer : Element_Pointer :=
Stack.Stack_Pointer;
begin
if Stack.Stack_Pointer =
Null_Element_Pointer then
-- This shouldn't happen but this
-- implementation is not meant for
-- concurrent access...
raise Program_Error;
end if;
Stack.Stack_Pointer := Stack.Stack_Pointer.Pred;
Free(Old_Pointer);
end;
end case;
Stack.Stack_Length := Stack.Stack_Length - 1;
end Pop;
function Method (Stack : in Limited_Stack_Type) return
String is
begin
case Stack.Use_Array is
when True =>
return "ARRAY";
when False =>
return "LIST";
end case;
end Method;
end Limited_Stacks;
with Ada.Text_IO;
use Ada.Text_IO;
with Limited_Stacks;
procedure Test_Limited_Stacks is
type Kilo_String is new String (1 .. 1000);
type Deca_String is new String (1 .. 10);
package Kilo_Stacks is new Limited_Stacks (Kilo_String, 16);
package Deca_Stacks is new Limited_Stacks (Deca_String, 16);
Kilo_Stack : Kilo_Stacks.Limited_Stack_Type;
Deca_Stack : Deca_Stacks.Limited_Stack_Type;
begin
Put_Line("Kilo_Stack uses method " &
Kilo_Stacks.Method(Kilo_Stack));
Put_Line("Deca_Stack uses method " &
Deca_Stacks.Method(Deca_Stack));
end Test_Limited_Stacks;
-- End Example
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-14 19:55 Smarter Generics Frank J. Lhota
2004-08-15 1:14 ` Georg Bauhaus
2004-08-15 1:32 ` Francois G. Dorais
@ 2004-08-16 5:36 ` Wes Groleau
2004-08-16 13:45 ` Jean-Marc Bourguet
2004-08-16 13:52 ` Jean-Marc Bourguet
3 siblings, 1 reply; 8+ messages in thread
From: Wes Groleau @ 2004-08-16 5:36 UTC (permalink / raw)
Frank J. Lhota wrote:
I have seen an implementation of Generic_Elementary_Functions
in which every subprogram had an IF statement on the precision
of the formal floating point parameter.
I suppose C++ could do this as well.
--
Wes Groleau
Those who make peaceful revolution impossible
will make violent revolution inevitable.
-- John F. Kennedy
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-16 5:36 ` Wes Groleau
@ 2004-08-16 13:45 ` Jean-Marc Bourguet
0 siblings, 0 replies; 8+ messages in thread
From: Jean-Marc Bourguet @ 2004-08-16 13:45 UTC (permalink / raw)
Wes Groleau <groleau+news@freeshell.org> writes:
> Frank J. Lhota wrote:
>
> I have seen an implementation of Generic_Elementary_Functions
> in which every subprogram had an IF statement on the precision
> of the formal floating point parameter.
>
> I suppose C++ could do this as well.
C++ has specialisations (which is to say, when the template parameters
are these, use this implementation, when they are those, use this
other one), which would be the natural mecanism to implement such
choice.
Yours,
--
Jean-Marc
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-14 19:55 Smarter Generics Frank J. Lhota
` (2 preceding siblings ...)
2004-08-16 5:36 ` Wes Groleau
@ 2004-08-16 13:52 ` Jean-Marc Bourguet
2004-08-18 5:31 ` Florian Weimer
3 siblings, 1 reply; 8+ messages in thread
From: Jean-Marc Bourguet @ 2004-08-16 13:52 UTC (permalink / raw)
"Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> writes:
> AFAIK neither Ada generics nor C++ templates have this level of
> intelligence.
Look at partial specialisation, which what I'd use to do such choice.
(with one level of indirection). Ask in c.l.c++.m if you need more
info.
BTW C++ template is a turing-complete compile langage able to
manipulate types and is the only implementation of genericity with
such an expressing power. But it can be *very* inconveniant to use.
A+
--
Jean-Marc
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-16 13:52 ` Jean-Marc Bourguet
@ 2004-08-18 5:31 ` Florian Weimer
2004-08-24 17:37 ` Jean-Marc Bourguet
0 siblings, 1 reply; 8+ messages in thread
From: Florian Weimer @ 2004-08-18 5:31 UTC (permalink / raw)
* Jean-Marc Bourguet:
> BTW C++ template is a turing-complete compile langage able to
> manipulate types and is the only implementation of genericity with
> such an expressing power.
Lisp macros offer similar flexibility.
> But it can be *very* inconveniant to use.
That's because the compile-time and run-time programming languages are
so different, it's not just the syntax that is a bit hairy.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Smarter Generics
2004-08-18 5:31 ` Florian Weimer
@ 2004-08-24 17:37 ` Jean-Marc Bourguet
0 siblings, 0 replies; 8+ messages in thread
From: Jean-Marc Bourguet @ 2004-08-24 17:37 UTC (permalink / raw)
Florian Weimer <fw@deneb.enyo.de> writes:
> * Jean-Marc Bourguet:
>
> > BTW C++ template is a turing-complete compile langage
> > able to manipulate types and is the only implementation
> > of genericity with such an expressing power.
>
> Lisp macros offer similar flexibility.
I don't think that Lisp macros and Forth immediate words are
implementation of genericity, but I agree that they are the
two languages I known which have similar power at run-time
-- and with a more conveniant syntax.
> > But it can be *very* inconveniant to use.
>
> That's because the compile-time and run-time programming
> languages are so different, it's not just the syntax that
> is a bit hairy.
It's not only the syntax. Semantic of C++ templates is also
"a bit hairy".
Yours,
--
Jean-Marc
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2004-08-24 17:37 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-08-14 19:55 Smarter Generics Frank J. Lhota
2004-08-15 1:14 ` Georg Bauhaus
2004-08-15 1:32 ` Francois G. Dorais
2004-08-16 5:36 ` Wes Groleau
2004-08-16 13:45 ` Jean-Marc Bourguet
2004-08-16 13:52 ` Jean-Marc Bourguet
2004-08-18 5:31 ` Florian Weimer
2004-08-24 17:37 ` Jean-Marc Bourguet
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox