Wanted: Ada STL. Reward: Ada's Future

Wanted: Ada STL. Reward: Ada's Future

[Alexy V Khrabrov]

Greetings --

I sent this message to several Ada gurus.  So far, only Norman Cohen
responded (thanks, Norm).  Since the issue is the most important for the
Ada's future, I publish it below and ask all active Ada programmers to
follow up with pointers to their preferred Ada reusable components.  SIGAda
must form a working group to decide on an Ada Standard Library.   -- Alexy
V. Khrabrov, UPenn CIS Dept.
--
To: Norman Cohen; Rober Dewar; Magnus Kempe; David Weller; Ben Brosgol; S.
Tucker Taft; Michael Feldman


Greetings --

I'm assembling a case for Ada for teaching at the University of Pennsylvania
in Philadelphia.  I compare Ada to Java, currently used here as the main
vehicle for teaching various programming disciplines.  Ben and Mike already
provided helpful presentation support, and Tuck promised to share his
theoretical and empirical knowledge of Ada versus Java in
cross-implementation and action.  Now, I'd like to ask all of you to
evaluate the status of reusable software for Ada, and first and foremost, an
analog of a standard library with basic data structures.  The main reference
point is C++ STL.  I'm very concerned there's nothing near  in Ada.  And yet
the main purpose of Ada is to facilitate software reuse!

In a comparative assessment of programming languages, the state of existing
reusable components is paramount.  Yet for Ada, it's rather dreadful.

Consider this simple task: a set.  In C++, you get it from the STL.  How do
you get one in Ada?

There seems to be no central library equivalent to STL.  I looked at HBAP,
and it turns out many links there are dangling -- to PAL for instance.
There's a passage diminishing STL, yet there should be a clear guide how to
find a complete replacement of all the necessary pieces of STL.  All serious
people program with C++ and STL.  If they turn to Ada, a replacement to STL
is like the first gulp of water they need for a break.

I didn't do much industrial programming in Ada for a few years, and
recently, when I started to put together a clean research system for KDD
(data mining), looking around for the reusable components, I was terrified.
I did found the Booch Components, fortunately picked up after David Weller
gave them up, but they don't even have sets, for Pete's sake!  Yet for
anything simple, you need sets the first thing in the morning.  I need them
for clustering.  Students need them for the beaten to death students/courses
problem.  Everybody needs sets.  Where do you get them in Ada 95?  The only
thing raising hope I found is the EPFL ADTs, yet they were not modified
after 1995, and mostly frozen after 1987.  None of these libraries are ready
to compile under ObjectAda and need tweaking on PCs.  The make files are for
Apex/Verdix, still in pre-GNAT era.

Let's do something about it. First of all, can you guys please list THE
reusable libraries YOU reuse the most?  I will assemble a list on my server,
and hope Magnus will update his -- dangerously and significantly outdated,
dangling all over the place.  ACT must put together a decent bundle looking
like an STL.  "The cell phone is only as good as the network it's on."  Same
for compilers and libraries.

Can you please share your thoughts on the status of an Ada STL?  (Let's code
name it Ada STL for the purpose of discussion.)  Is there anything close for
Ada 95?  What are YOU guys using for your Ada programming?  I can't believe
each of you has a jar with homegrown sets, linked lists, and queues, all
implemented differently!  OK, let's start small.  Can you please tell me
with as more URLs as possible, what exactly you use when you need

1.  Linked lists
2.  Trees
3.  Queues
4.  Sets

I feel Sets are the litmus tests for an Ada STL.  Where do you guys get
sets?
It's very important to assess the situation, and I hope to hear from you
with as much detail as your busy schedules permit.

Cheers,
Alexy

Re: Wanted: Ada STL. Reward: Ada's Future

[Simon Wright]

"Alexy V Khrabrov" <khrabrov.a@worldnet.att.net> writes:

> I did found the Booch Components, fortunately picked up after David Weller
> gave them up, but they don't even have sets, for Pete's sake!  Yet for
> anything simple, you need sets the first thing in the morning.

Personally I haven't needed to use a set for the last .. dunno how
long.  The BC's I've translated have by and large been what people
were asking for .. however, glad to have a go at sets next, shouldn't
be too bad now I've got hash tables out of the way ..

I've referenced some of the publicly-available component sets at the
bottom of http://www.pogner.demon.co.uk/components/

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

"Alexy V Khrabrov" <khrabrov.a@worldnet.att.net> writes:

> I did found the Booch Components, fortunately picked up after David Weller
> gave them up, but they don't even have sets, for Pete's sake!  Yet for
> anything simple, you need sets the first thing in the morning.  I need them
> for clustering.  Students need them for the beaten to death students/courses
> problem.  Everybody needs sets.  Where do you get them in Ada 95?


On the contrary, a set is next-to-useless as a collection abstraction in
any real program.

A set is an unordered collection without duplicates.  The problem with a
set is that when you add an item to the set, you have to check the
entire set to make sure that the item isn't already in the set.

That's fine if that's the behavior you want.  However, it has been my
personal experience that this is not the abstraction you require.

Typically, all you need is an abstraction for an unordered collection.
When you add an item to the collection, it puts (a copy of) the item in
the collection, without any checks.

The problem with many data structure texts is that they omit any
discussion of this important abstraction.  And so everyone goes through
life thinking that a set (or multiset) is the only kind of unordered
collection that exists.

In my work on the ACL (which I suspended until gnat 3.11p came out: it
wouldn't compile otherwise), I call this kind of abstraction a
"container."  There is only a minimal set of operations on a Container
type:

o add an item to the container

o iterate over items in the container

o remove the item currently designated by an (active) iterator


The first thing in the morning you need a Container, not a Set.

Re: Wanted: Ada STL. Reward: Ada's Future

[Alexy V Khrabrov]

Matthew Heaney wrote in message ...

>On the contrary, a set is next-to-useless as a collection abstraction in
>any real program.


On the contrary, set is a useful abstraction.  In fact, it's the first
abstaction in mathematics, used by Euclid to prove that the SET of primes is
infinite.  Set was used by Euler, Bernoulli, Gauss, Turing, and others,
before you or I were born, Matthew, and will be used after us, Ada, C++, or
computers in general, for that matter.

Set is a part of C++ STL which is used all the time, and emphasized in all
STL books.
I've seen a gazillion programs using lists for mimicing set behavior, and
will see a bazillion more.

>A set is an unordered collection without duplicates.

Not necessarily unordered.  A very useful extension of math set is a set of
ordered items, for which a generic taking an "<" parameter along with the
Element type and "=" is most suitable form in Ada.

That's how in fact the best Ada ADTs I've seen so far, LGL components, were
written:

http://lglwww.epfl.ch/Components

>The problem with a
>set is that when you add an item to the set, you have to check the
>entire set to make sure that the item isn't already in the set.


If it's ordered as above, the search is as efficient as an AVL tree search
[read -- any] can be.

>That's fine if that's the behavior you want.  However, it has been my
>personal experience that this is not the abstraction you require.


And I do require sets, as many other people do, too.  Real world contains
sets, and any faithful OOP will need them.

>Typically, all you need is an abstraction for an unordered collection.
>When you add an item to the collection, it puts (a copy of) the item in
>the collection, without any checks.


I prefer ordered sets whenever I can supply the "<" -- and I almost always
can.  Give me one example where you can't.  I can even sort files on their
last access time, can't I?  Tasks on their name, etc. -- even limited
private types, that is.

>The problem with many data structure texts is that they omit any
>discussion of this important abstraction.  And so everyone goes through
>life thinking that a set (or multiset) is the only kind of unordered
>collection that exists.


And they also omit ordered sets.

>In my work on the ACL (which I suspended until gnat 3.11p came out: it
>wouldn't compile otherwise), I call this kind of abstraction a
>"container."  There is only a minimal set of operations on a Container
>type:
>
>o add an item to the container
>
>o iterate over items in the container
>
>o remove the item currently designated by an (active) iterator


Where is your ACL?  Is it public?

>The first thing in the morning you need a Container, not a Set.

Well, and I need sets, buddy!

Cheers,
Alexy V. Khrabrov
UPenn CIS/NEC Research Institute/Princeton/CMSC

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

"Alexy V Khrabrov" <khrabrov.a@worldnet.att.net> writes:

> Matthew Heaney wrote in message ...
> 
> >On the contrary, a set is next-to-useless as a collection abstraction in
> >any real program.
> 
> 
> On the contrary, set is a useful abstraction.  In fact, it's the first
> abstaction in mathematics, used by Euclid to prove that the SET of primes is
> infinite.

I don't care about mathematics or Euclid.  I care about writing real
computer programs that have to meet real deadlines.

> Set is a part of C++ STL which is used all the time, and emphasized in all
> STL books.
> I've seen a gazillion programs using lists for mimicing set behavior, and
> will see a bazillion more.

Then the STL has invented an abstraction I'll probably never use.

The STL is not a good model for an Ada components library, anyway.


> >A set is an unordered collection without duplicates.
> 
> Not necessarily unordered.  A very useful extension of math set is a set of
> ordered items, for which a generic taking an "<" parameter along with the
> Element type and "=" is most suitable form in Ada.

Ah, but there's the rub.  From a semantic point of view, a set is
unordered, even if it has an implementation that is ordered.

The reason you have to order the items (internally) is because the set
is being used to ... implement a computer program!  Requiring that the
items have a comparison operator is in fact exposing an implementation
detail, a detail that only manifests itself because you have to pay
attention to space & time semantics too.

If you need an unordered collection without duplicates, then by all
means use a set, and import a comparison operator if necessary (always a
good idea, actually).

But if you need just an unordered collection, and duplicates are
acceptable, then do NOT use a set, use a container.


> And I do require sets, as many other people do, too.  Real world contains
> sets, and any faithful OOP will need them.

Funny, I've been programming for over 10 years, and I've NEVER needed an
unordered collection without duplicates (i.e. a set).  But there have
been MANY times when I needed an unordered collection with duplicates
(i.e. a container).

Most of the time you just want to stuff something into a collection so
you can remember it for a little while, without incurring any insertion
overhead.

When we were using the old Booch Components, I NEVER used the Set
packages, because I never had a use for them.

What happens is that the programmer looks in his components library,
doesn't see what he needs, and instead of writing a high-level
container, uses a low-level linked list to implement his collection.
This is all wrong, because a linked list is at the wrong level of
abstraction.

 
> I prefer ordered sets whenever I can supply the "<" -- and I almost always
> can.  Give me one example where you can't.  I can even sort files on their
> last access time, can't I?  Tasks on their name, etc. -- even limited
> private types, that is.

I use sets when I need an unordered collection without duplicates
(which almost never need).

I use containers when I need an unordered collection with duplicates
(which I almost always need).

> >In my work on the ACL (which I suspended until gnat 3.11p came out: it
> >wouldn't compile otherwise), I call this kind of abstraction a
> >"container."  There is only a minimal set of operations on a Container
> >type:
> >
> >o add an item to the container
> >
> >o iterate over items in the container
> >
> >o remove the item currently designated by an (active) iterator
> 
> 
> Where is your ACL?  Is it public?

It will be made public as soon as some caring person ports gnat 3.11p to
LinuxPPC.  If I could only convince Robert Dewar to get himself a nice
Mac...


> >The first thing in the morning you need a Container, not a Set.
> 
> Well, and I need sets, buddy!

That, and a big cup of coffee...

Re: Wanted: Ada STL. Reward: Ada's Future

[Jeff Carter]

Matthew Heaney and Alexy V Khrabrov have been arguing about the need for
sets. Heaney never uses them and Khrabrov considers them essential.

I've recently used sets for a communications protocol. The task needs to
wait for one of a set of events; at other times it needs to wait for one
of another set of events. The sets of events overlap.

This mapped nicely to a protected object with a current event component.
Each Wait_ entry has a barrier of the form

when Member (Current_Event, Set_Of_Events_For_This_Kind_Of_Wait) is

Another task calls a Signal entry to set Current_Event. This worked very
well.

These are small, simple, discrete sets, as in Pascal, implemented as
arrays of Boolean, as opposed to the set-of-anything components I often
see discussed. I've never needed a set of anything except discrete
values, but I have needed bags of anything.
-- 
Jeff Carter
E-mail: carter commercial-at innocon [period | full stop] com
"We call your door-opening request a silly thing."
Monty Python & the Holy Grail

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On 31 Jan 1999, Alexy V Khrabrov wrote:
> Greetings --
> 
> I'm assembling a case for Ada for teaching at the University of Pennsylvania
> in Philadelphia.  I compare Ada to Java, currently used here as the main
> vehicle for teaching various programming disciplines.  Ben and Mike already
> provided helpful presentation support, and Tuck promised to share his
> theoretical and empirical knowledge of Ada versus Java in
> cross-implementation and action.  Now, I'd like to ask all of you to
> evaluate the status of reusable software for Ada, and first and foremost, an
> analog of a standard library with basic data structures.  The main reference
> point is C++ STL.  I'm very concerned there's nothing near  in Ada.  And yet
> the main purpose of Ada is to facilitate software reuse!

I started writing such a library a while ago, based on an earlier library
from RPI. I haven't been updating it much since I don't use Ada at work
and I currently have little free time. I'll fix problems and update the
library at the current glacial pace. If you want to contribute code that 
would be great too.

	http://www.best.com/~bpr/agl.html

I disagree with the opinion expressed by others replying that an STL like
library is an inappropriate map to Ada 95, and haven't heard a reasoned
argument for this assessment. I think Ada 95 is in some ways better than
C++ for this, in particular the style of connecting packages together
enabled by generic formal package parameters and null bodied generic
signature packages makes the structure of the library quite clear. 

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[Ehud Lamm]

On Mon, 1 Feb 1999, Brian Rogoff wrote:

> I disagree with the opinion expressed by others replying that an STL like
> library is an inappropriate map to Ada 95, and haven't heard a reasoned
> argument for this assessment. I think Ada 95 is in some ways better than
> C++ for this, in particular the style of connecting packages together
> enabled by generic formal package parameters and null bodied generic
> signature packages makes the structure of the library quite clear. 
> 

Some time ago I found on the web (sorry but I don't have the exact
reference) an article called "Implementing the C++ Standard Template
Libray in Ada 95" by Ulfar Erlingsson and Alexander Knostantinou. Those
interesetd in this question should read this.

It seems that one problem in implementing STL in Ada95 is the lack of
pointer arithmetic.  This causes perofremance problems in real sense (to
be exact the result is worse from a complexity point of view). This is a
"nice" result in that it tells you something about the price you pay for
pointer abstraction etc. However it is sad from a practical point of view.
I haven't really pursued this, so I can't vouch that there isn't some
trick to solve this problem.

I might also add, to those unfamiliar witht the history of STL and generic
programming, that the first attempts at producing such a library - by
Alexander Stepanov - were in Ada. My site points to two interives with
him, that you may find of interest.

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il
http://www2.cybercities.com/e/ehud   - Ada & SE & More! 

Re: Wanted: Ada STL. Reward: Ada's Future

[Richard D Riehle]

In article <Pine.A41.3.96-heb-2.07.990201214336.46206A
100000@pluto.mscc.huji.ac.il>,
	Ehud Lamm <mslamm@mscc.huji.ac.il> wrote:

>It seems that one problem in implementing STL in Ada95 is the lack of
>pointer arithmetic.  This causes perofremance problems in real sense (to
>be exact the result is worse from a complexity point of view). This is a
>"nice" result in that it tells you something about the price you pay for
>pointer abstraction etc. However it is sad from a practical point of view.
>I haven't really pursued this, so I can't vouch that there isn't some
>trick to solve this problem.

 Pointer arithmetic is not directly supported by Ada 95, true.  Also true,
 the absence of direct support encourages the designer to use the 
 better abstractions provided by the default.

 On the other hand, one can do pointer arithmetic in Ada via the 
 package System children, albeit with some difficulty.  It is first
 necessary to instantiate the generic package
             System.Address_To_Access_Conversions.
 Then, using another package,
             System.Storage_Elements
 one can do arithmetic on the address produced from the function,
             System.Address_To_Access_Conversions.To_Address.

 None of this is for the "faint of heart."  Certainly, it is not
 for anyone who is just tooling around with addresses.  However,
 these packages seem suited for most situations where such arithmetic
 is necessary.  But don't do this on the software that flies the
 airplane on which I am flying.

 Richard Riehle
 richard@adaworks.com
 http://www.adaworks.com 

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79817u$kqr@dfw-ixnews11.ix.netcom.com>,
  Richard D Riehle <LaoXhai@ix.netcom.com> wrote:
>  But don't do this on the software that flies the
>  airplane on which I am flying.

Please don't make statements like this. It encourages
idiotic rules like "unchecked conversion is forbidden",
which all too often force people to do the equivalent
operation in C.

There is absolutely no reason why pointer arithmetic as
Richard describes it should not be used in safety critical
code if it is the right thing to do.

For example, safety critical code, if it allows allocation
at all, probably requires that the allocator be written in
Ada by the user. Pointer arithmetic here is perfectly
legitimate, and indeed almost unavoidable.

Robert Dewar

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Mon, 1 Feb 1999, Ehud Lamm wrote:
> Some time ago I found on the web (sorry but I don't have the exact
> reference) an article called "Implementing the C++ Standard Template
> Libray in Ada 95" by Ulfar Erlingsson and Alexander Knostantinou. Those
> interesetd in this question should read this.

It is at www.adahome.com, in the "Online Articles" section. 

> It seems that one problem in implementing STL in Ada95 is the lack of
> pointer arithmetic.  This causes perofremance problems in real sense (to
> be exact the result is worse from a complexity point of view). 

I don't know what you mean here. Could you explain, or provide a pointer? :-)

> I might also add, to those unfamiliar witht the history of STL and generic
> programming, that the first attempts at producing such a library - by
> Alexander Stepanov - were in Ada. My site points to two interives with
> him, that you may find of interest.

Actually, a Scheme library predates the Ada one, and is predated itself by 
an attempt in a homemade functional language I think.

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

> On Mon, 1 Feb 1999, Ehud Lamm wrote:
> > It seems that one problem in implementing STL in Ada95
> > is the lack of pointer arithmetic.  This causes
> > perofremance problems in real sense (to
> > be exact the result is worse from a complexity point of
> > view).

That's odd, in talking to Alex, one of his comments about
why Ada was a better environment than C++ for the design of
such a library was *precisely* that Ada 95 does have
general pointer arithmetic (as should be familiar, if not
please look at System.Storage_Elements), and C++ does not
(since one can only for example compare pointers that point
into the same object meaningfully).

So if lack of pointer arithmetic is a handicap, it is one
that applies to C++, not to Ada 95.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Ehud Lamm]

On Tue, 2 Feb 1999 robert_dewar@my-dejanews.com wrote:

> That's odd, in talking to Alex, one of his comments about
> why Ada was a better environment than C++ for the design of
> such a library was *precisely* that Ada 95 does have
> general pointer arithmetic (as should be familiar, if not
> please look at System.Storage_Elements), and C++ does not
> (since one can only for example compare pointers that point
> into the same object meaningfully).

As I said I didn't study this in any detail yet. This was my first and
perhaps wrong impression from the article. Let me quote:

"..remaining restrictions on pointer arithmetic, which can lead to
inefficiencies in the implimentation of random access iterators, can be
cicumvented through the C langauge interface library package."

And:

"The main issue in and Ada implimentation of the vector container involves
the choice of the iterator type. Even with aliased type, Ada does not
allow for pointer arithmetic. Therfore, one cannot increment a pointer toa
vector element, or substract two pointers."

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Brian Rogoff wrote:
> On Mon, 1 Feb 1999, Ehud Lamm wrote:
> > It seems that one problem in implementing STL in Ada95 is the lack of
> > pointer arithmetic.  This causes perofremance problems in real sense (to
> > be exact the result is worse from a complexity point of view).
> 
> I don't know what you mean here. Could you explain, or provide a pointer? :-)

IMHO performance is not the problem for implementing the STL in Ada.

For STL, a nice consequence of the pointer semantics in C and C++ is
that for a collection of N items, there are N+1 points where you can
insert a new item, and C/C++ pointer semantics lets you refer to the
position past the end of an array. This means that you have a way of
referring to the "extra" position by using a "beyond the end" pointer
in an array. The STL uses ranges [i,j) which cover the range from the
iterator i up to but not including the position j.  This works just
as well for arrays as it does for vectors or maps or whatever.

In Ada this isn't possible -- e.g. type Foo is array(Boolean) of Bar
has no "beyond the end" index that can be used to form non-inclusive
ranges [i,j).  This makes it hard to support arrays as "just another
collection type" in the way that the STL does, so you can't easily
define algorithms which can be applied impartially to arrays or
vectors or maps or whatever.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

John English <je@bton.ac.uk> writes:

> In Ada this isn't possible -- e.g. type Foo is array(Boolean) of Bar
> has no "beyond the end" index that can be used to form non-inclusive
> ranges [i,j).  This makes it hard to support arrays as "just another
> collection type" in the way that the STL does, so you can't easily
> define algorithms which can be applied impartially to arrays or
> vectors or maps or whatever.

The problem in your example is your array index.  The rule in Ada is
that an enumeration type is its own base type, and type Boolean has no
other values than True and False.

If you need to fall off the beginning or end of an array, you just need
to make sure the base type of the index subtype has at least one extra
value on either end, something like:

  type Color_Base is (First, Red, Green, Blue, Last);

  subtype Color_Type is Color_Base
   range Color_Base'Succ (First) .. Color_Base'Pred (Last);

Now declare your array:

  type Color_Map is array (Color_Type) of Integer; -- or whatever

  Map : Color_Map := ...;

  Index : Color_Base := Color_Map'First;

begin

  loop

    <do something with Map (Index)>
    
    Index := Color_Base'Succ (Index);

    exit when Index > Map'Last;

  end loop;

end;

Because Index has subtype Color_Base, not Color_Type, you can safely
iterate pass the end of the array.

What motivated the STL approach is that this is a very common idiom for
iteration in C/C++.  You iterate pass the end of the array - that's your
loop termination condition:

  for (i = 0; i < len; i++) {
   ... a[i] ...

This scheme works because your array has indices 0 .. len - 1, but the
index goes from 0 to len.

You can implement the exact same iteration scheme in Ada, using the
technique I've shown above: declare a base type with an extra value on
the end, and then declare a subtype without the extra value.

Of course, there's no way to do this sort of thing using type Boolean,
because Boolean is its own base type.

That being said, the technique I've shown above is only rarely needed in
Ada, because standard loop idioms are different.  In Ada, I'd only need
to do this:

  for Index in Map'Range loop

    <do something with Map (Index)>

  end loop;

If this looks simpler than my earlier formulation, that's because it's
simpler.  Loop iteration in Ada is less error prone than in C.

This is yet another reason why I think that looking at the STL as a
model for a standard Ada library is dangerous and misleading.

The idioms in both languages are completely different.  So forget about
the STL as a model for an Ada library.

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Wed, 3 Feb 1999, Matthew Heaney wrote:
> ... snip ...
> 
>   for Index in Map'Range loop
> 
>     <do something with Map (Index)>
> 
>   end loop;
> 
> If this looks simpler than my earlier formulation, that's because it's
> simpler.  Loop iteration in Ada is less error prone than in C.
> 
> This is yet another reason why I think that looking at the STL as a
> model for a standard Ada library is dangerous and misleading.

Indeed. Just look at how incomprehensible AGL looping looks

    Os := Copy(Start(Deque'Access), Finish(Deque'Access), Os);

	or

    Pos := Find(Start(IVec'Access), Finish(IVec'Access), 42);

The horror, the horror ...
 
> The idioms in both languages are completely different.  So forget about
> the STL as a model for an Ada library.

If you do your homework, you'll find that completely independently of C++
or the STL, Judy Bishop wrote a similar library for Ada 83 (trying to
mimic CLU iterators), and it turns out to look remarkably similar to STL or 
AGL. See

Bishop, J.M. et al. "The effect of data abstraction on loop
programming techniques" IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
April 1990. vol.16, no.4, p. 389-402 (Journal Paper - English)

(Note that some of Bishop's complaints about Ada no longer apply to Ada 95)

So far, you've said nothing that indicates that you've looked seriously at 
the STL. Why don't you just get very specific and say exactly why you
think it is a bad model for an Ada library, using examples? I think the
idea of writing algorithms over collections in terms of their iterators is
a good one. 

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[Stephen Leake]

Brian Rogoff <bpr@shell5.ba.best.com> writes:

> On Wed, 3 Feb 1999, Matthew Heaney wrote:
> > ... snip ...
> > 
> >   for Index in Map'Range loop
> > 
> >     <do something with Map (Index)>
> > 
> >   end loop;
> > 
> > If this looks simpler than my earlier formulation, that's because it's
> > simpler.  Loop iteration in Ada is less error prone than in C.
> > 
> > This is yet another reason why I think that looking at the STL as a
> > model for a standard Ada library is dangerous and misleading.
> 
> Indeed. Just look at how incomprehensible AGL looping looks
> 
>     Os := Copy(Start(Deque'Access), Finish(Deque'Access), Os);
> 
> 	or
> 
>     Pos := Find(Start(IVec'Access), Finish(IVec'Access), 42);
> 
> The horror, the horror ...
>  
> > The idioms in both languages are completely different.  So forget about
> > the STL as a model for an Ada library.
> 
> If you do your homework, you'll find that completely independently of C++
> or the STL, Judy Bishop wrote a similar library for Ada 83 (trying to
> mimic CLU iterators), and it turns out to look remarkably similar to STL or 
> AGL. See
> 
> Bishop, J.M. et al. "The effect of data abstraction on loop
> programming techniques" IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
> April 1990. vol.16, no.4, p. 389-402 (Journal Paper - English)
> 
> (Note that some of Bishop's complaints about Ada no longer apply to Ada 95)
> 
> So far, you've said nothing that indicates that you've looked seriously at 
> the STL. Why don't you just get very specific and say exactly why you
> think it is a bad model for an Ada library, using examples? I think the
> idea of writing algorithms over collections in terms of their iterators is
> a good one. 

I thought Matthew just did that, but you haven't answered the question
"why does the STL allow iteration past the end of the array". This
bugs me too. Is there a real reason here, or is it an accident of the
implementation?

Perhaps it is the most general way to define an iterator that points
to nothing? Certainly if the underlying implementation of a collection
is an array, this makes sense. But if the underlying implementation is
a list, then a null pointer makes more sense. Why not make the
abstraction resemble a null pointer, rather than an out-of-bounds
index?

-- Stephe

Re: Wanted: Ada STL. Reward: Ada's Future

[Hyman Rosen]

Stephen Leake wrote:
> I thought Matthew just did that, but you haven't answered the question
> "why does the STL allow iteration past the end of the array". This
> bugs me too. Is there a real reason here, or is it an accident of the
> implementation?

STL iterators are analogous to C pointers; one goal of the STL design is to
be able to use C pointers as iterators in any STL algorithm. Given that C
allows a one-past-the-end pointer to an array, it becomes natural to
express
STL ranges as [i,j). This allows an entire array to be spanned, as well as
allowing an empty range to be easily specified.

> Perhaps it is the most general way to define an iterator that points
> to nothing? Certainly if the underlying implementation of a collection
> is an array, this makes sense. But if the underlying implementation is
> a list, then a null pointer makes more sense. Why not make the
> abstraction resemble a null pointer, rather than an out-of-bounds
> index?

Because you don't always want to operate on the entire container, of
course.
STL algorithms take a pair of iterators when they need a range specified,
and
this allows them to work on arbitrary sections of a container. Also, when
an
algorithm requires a bidirectional iterator, you can go back from a
past-the-end
iterator, but not from a null pointer.

Re: Wanted: Ada STL. Reward: Ada's Future

[Stephen Leake]

Hyman Rosen <hymie@prolifics.com> writes:

> Stephen Leake wrote:
> > I thought Matthew just did that, but you haven't answered the question
> > "why does the STL allow iteration past the end of the array". This
> > bugs me too. Is there a real reason here, or is it an accident of the
> > implementation?
> 
> STL iterators are analogous to C pointers; one goal of the STL design is to
> be able to use C pointers as iterators in any STL algorithm. Given that C
> allows a one-past-the-end pointer to an array, it becomes natural to
> express
> STL ranges as [i,j). This allows an entire array to be spanned, as well as
> allowing an empty range to be easily specified.

Ok, that's what I thought. The STL style of expressing ranges as [i,j)
is an consequence of the implementation, not a requirement of the
design.

I don't see why allowing pointers as iterators is a good idea in the
first place. How do you efficiently maintain the head and tail
pointers, or other list-wide state, for a doubly linked list when you
insert from a plain pointer? Apparently you don't!

So for an Ada "STL", we can either use [i,j) to be somewhat compatible
with C++ STL, or we can use [i .. j] to be more Ada-like. I'm not
clear what the best choice would be, but I lean towards being
Ada-like. I'd rather woo good Ada programers than ex-C++ programers :).
 
> > Perhaps it is the most general way to define an iterator that points
> > to nothing? Certainly if the underlying implementation of a collection
> > is an array, this makes sense. But if the underlying implementation is
> > a list, then a null pointer makes more sense. Why not make the
> > abstraction resemble a null pointer, rather than an out-of-bounds
> > index?
> 
> Because you don't always want to operate on the entire container, of
> course.
> STL algorithms take a pair of iterators when they need a range specified,
> and
> this allows them to work on arbitrary sections of a container. Also, when
> an
> algorithm requires a bidirectional iterator, you can go back from a
> past-the-end
> iterator, but not from a null pointer.

Depends on what else you store in the iterator data structure. If you
store a pointer to the container itself, you can do what's required.
Again, insisting that a plain pointer can be an iterator is too
restricting.

-- Stephe

Re: Wanted: Ada STL. Reward: Ada's Future

[Hyman Rosen]

Stephen Leake <Stephen.Leake@gsfc.nasa.gov> writes:
> Ok, that's what I thought. The STL style of expressing ranges as [i,j)
> is an consequence of the implementation, not a requirement of the
> design.

That is not at all what I said. It's a consequence of the desire to
allow arrays to function naturally as STL containers. That makes it
part of the design.

> I don't see why allowing pointers as iterators is a good idea in the
> first place. How do you efficiently maintain the head and tail
> pointers, or other list-wide state, for a doubly linked list when you
> insert from a plain pointer? Apparently you don't!

What in the world are you talking about? Every STL container has an
associated iterator type (two actually, one for constant containers).
STL algorithms operate on iterators, or ranges expressed as a pair of
iterators. The iterator for an array is a plain pointer to array
element, but the iterator into a more complicated container such as a
linked list is certainly not!

> So for an Ada "STL", we can either use [i,j) to be somewhat compatible
> with C++ STL, or we can use [i .. j] to be more Ada-like. I'm not
> clear what the best choice would be, but I lean towards being
> Ada-like. I'd rather woo good Ada programers than ex-C++ programers :).

OK. Just keep in mind that STL allows something like this:

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
	vector<int> a;

	copy(istream_iterator<int>(cin), istream_iterator<int>(),
	     back_insert_iterator(a));
}

Here, istream_iterator<int>() represents a one-past-the-end iterator of
an input stream. The other iterator, istream_iterator<int>(cin), becomes
equal to the end one when end-of-file is encountered. The copy algorithm
is simply

template <typename In, typename Out>
Out copy(In from, In to, Out where)
{
	while (from != to)
		*where++ = *from++;
	return where;
}

> Again, insisting that a plain pointer can be an iterator is too
> restricting.

As I said, a plain pointer is an iterator of an array. Iterators to
more complicated structures are not plain pointers to element types.

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

Stephen Leake <Stephen.Leake@gsfc.nasa.gov> writes:

> I thought Matthew just did that, but you haven't answered the question
> "why does the STL allow iteration past the end of the array". This
> bugs me too. Is there a real reason here, or is it an accident of the
> implementation?

To terminate an iteration, you always have to "fall off the end" of the
thing you're iterating over.  This is true of array iteration, loop
iteration, stream iteration, etc:

  for (i = 0; i < len; i++ { 
    ... a [i] ...
  }

The iteration terminates when i falls off the end the array.

  declare
     Node : Node_Access := List;
  begin
     while Node /= null loop
        <process Node.Item>
        Node := Node.Next;
     end loop;
  end;

This loop terminates when Node falls off the end of the list.

  loop
     Get (N);
     exit when N = 0;
     <process N>
  end loop;


This loop terminates when N falls off the end of the stream (eos being
indicated by a sentinal, the value 0).

Now what Ada does, is do this falling off the end behind the scenes, so
that you the programmer don't have to worry about whether your index has
an extra value.  However, you can use the low level approach (necessary
once in a while), by using the technique I showed in my earlier post.

I do this in the implementation of an iterator over a bounded data
structure implemented as an array:

type Stack_Iterator is
  record
    Index : Natural;  -- note that this is Natural, not Positive
    Stack : Stack_Access;
  end record;

function Initialize 
  (Stack : Stack_Type) return Stack_Iterator is
begin
  return (Index => Stack.Top, Stack => Stack'Access);
end;

function Is_Done (Iterator : Stack_Iterator) return Boolean is
begin
   return Iterator.Index = 0;  
   -- the value 0 is outside range of index subtype (Positive)
end;

procedure Advance (Iterator : Stack_Iterator) is
begin
  Iterator.Index := Iterator.Index - 1;
  -- this might case Index to fall off the end of the array
end;


Iteration would look like this:

declare
   Iter : Stack_Iterator := Initialize (Stack);
begin
   while not Is_Done (Iterator) loop
     <process Get_Item (Iter)>
     Advance (Iter);
   end loop;
end;


This loop terminates because Iter.Index falls of the end of the array
(in this case, the beginning of the array).

Iteration past the end of the array isn't an STL "problem," it is just
the nature of iteration, irrespective of language.  (Although in Ada's
case, this falling off the end is often hidden from the programmer.)

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On 4 Feb 1999, Stephen Leake wrote:
> Brian Rogoff <bpr@shell5.ba.best.com> writes:
> > On Wed, 3 Feb 1999, Matthew Heaney wrote:
> > > ... snip ...
> > > 
> > >   for Index in Map'Range loop
> > > 
> > >     <do something with Map (Index)>
> > > 
> > >   end loop;
> > > 
> > > If this looks simpler than my earlier formulation, that's because it's
> > > simpler.  Loop iteration in Ada is less error prone than in C.
> > > 
> > > This is yet another reason why I think that looking at the STL as a
> > > model for a standard Ada library is dangerous and misleading.
> > 
> > Indeed. Just look at how incomprehensible AGL looping looks
> > 
> >     Os := Copy(Start(Deque'Access), Finish(Deque'Access), Os);
> > 
> > 	or
> > 
> >     Pos := Find(Start(IVec'Access), Finish(IVec'Access), 42);
> > 
> > The horror, the horror ...
> >  
> > > The idioms in both languages are completely different.  So forget about
> > > the STL as a model for an Ada library.
... snip ...
> > 
> > So far, you've said nothing that indicates that you've looked seriously at 
> > the STL. Why don't you just get very specific and say exactly why you
> > think it is a bad model for an Ada library, using examples? I think the
> > idea of writing algorithms over collections in terms of their iterators is
> > a good one. 
> 
> I thought Matthew just did that, but you haven't answered the question
> "why does the STL allow iteration past the end of the array". This
> bugs me too. Is there a real reason here, or is it an accident of the
> implementation?

How do you even know that it points past the end of the array, in an Ada 
implementation? We have a constructor for an iterator called "Last" or 
"Finish" or whatever. Should it matter how Finish is implemented?

> Perhaps it is the most general way to define an iterator that points
> to nothing? 

It is *a* way to define a stopping condition or sentinel value. In the
case of a red-black tree, the null pointer is a sentinel. In the case of
an array, whose iterator conceptually looks like a pointer-offset pair, 
an offset one greater than the highest index of the array makes a fine
sentinel, and it just so happens that in C++ you can use this easily. 

> Certainly if the underlying implementation of a collection
> is an array, this makes sense. But if the underlying implementation is
> a list, then a null pointer makes more sense. Why not make the
> abstraction resemble a null pointer, rather than an out-of-bounds
> index?

In what way does the value of Finish not resemble a null pointer,indeed,
when iterating over a list and checking for nullness of a pointer, in what
way does that not resemble checking for an out of bounds index?

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[Stephen Leake]

Brian Rogoff <bpr@shell5.ba.best.com> writes:

> On 4 Feb 1999, Stephen Leake wrote:
> > Brian Rogoff <bpr@shell5.ba.best.com> writes:
> > > On Wed, 3 Feb 1999, Matthew Heaney wrote:
> > > > ... snip ...
> > > > 
> > > >   for Index in Map'Range loop
> > > > 
> > > >     <do something with Map (Index)>
> > > > 
> > > >   end loop;
> > > > 
> > > > If this looks simpler than my earlier formulation, that's because it's
> > > > simpler.  Loop iteration in Ada is less error prone than in C.
> > > > 
> > > > This is yet another reason why I think that looking at the STL as a
> > > > model for a standard Ada library is dangerous and misleading.
> > > 
> > > Indeed. Just look at how incomprehensible AGL looping looks
> > > 
> > >     Os := Copy(Start(Deque'Access), Finish(Deque'Access), Os);
> > > 
> > > 	or
> > > 
> > >     Pos := Find(Start(IVec'Access), Finish(IVec'Access), 42);
> > > 
> > > The horror, the horror ...
> > >  
> > > > The idioms in both languages are completely different.  So forget about
> > > > the STL as a model for an Ada library.
> ... snip ...
> > > 
> > > So far, you've said nothing that indicates that you've looked seriously at 
> > > the STL. Why don't you just get very specific and say exactly why you
> > > think it is a bad model for an Ada library, using examples? I think the
> > > idea of writing algorithms over collections in terms of their iterators is
> > > a good one. 
> > 
> > I thought Matthew just did that, but you haven't answered the question
> > "why does the STL allow iteration past the end of the array". This
> > bugs me too. Is there a real reason here, or is it an accident of the
> > implementation?
> 
> How do you even know that it points past the end of the array, in an Ada 
> implementation? We have a constructor for an iterator called "Last" or 
> "Finish" or whatever. Should it matter how Finish is implemented?

Ok, I agree, you've come up with a good abstraction, where you can't
tell / don't care what the implementation is. That's what I was
looking for.

Still, there is a distinction between "Last" and "Finish". In Ada,
indexing an array with Last gives a valid data element. In C++ STL,
dereferencing a "Finish" iterator does _not_ give a vaid data pointer.
That is the essential difference in style.

Let me ask my question this way. Define an iterator value "Last" that
represents the last valid data element in a container. Define an
iterator value "Finish" that represents no valid data element in a
container. Also define Prev (Finish) == Last.

1) Are there algorithms that can be expressed in terms of Finish that
   cannot be expressed in terms of Last?

2) Do we also need Begin and First? or just First?

Hmm, I think I'm implying an ordered container here. Do the answers
change for unordered containers?

-- Stephe

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On 5 Feb 1999, Stephen Leake wrote:
> Brian Rogoff <bpr@shell5.ba.best.com> writes:
> Still, there is a distinction between "Last" and "Finish". In Ada,
> indexing an array with Last gives a valid data element. In C++ STL,
> dereferencing a "Finish" iterator does _not_ give a vaid data pointer.
> That is the essential difference in style.

True, it is not the same as 'First and 'Last.  A zero length sequence has
no valid dereferenceable first or last element, so a general subsequence 
abstraction should have indices which refer to positions between the
elements, not the elements themselves. That makes for the most elegant
definition.

> Let me ask my question this way. Define an iterator value "Last" that
> represents the last valid data element in a container. Define an
> iterator value "Finish" that represents no valid data element in a
> container. Also define Prev (Finish) == Last.

How do we define Last if the container is empty? It seems we either just
use Finish, or we screw your definition up a bit.

> 1) Are there algorithms that can be expressed in terms of Finish that
>    cannot be expressed in terms of Last?
> 
> 2) Do we also need Begin and First? or just First?

I can't thinnk of a good reason why you need two "off the end" iterators. 
Just imagine the sequence is a ring buffer. 

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Stephen Leake wrote:
> I thought Matthew just did that, but you haven't answered the question
> "why does the STL allow iteration past the end of the array". This
> bugs me too. Is there a real reason here, or is it an accident of the
> implementation?

A "past-the-end" value makes it easy to insert items into collections --
you always insert BEFORE a particular position, so inserting before the
past-the-end position will append to the end.  In the case of arrays you
can't insert anything, but at least you have read access to arrays in
exactly the same way as any other collection type.  This means that
non-mutating algorithms (searching, counting, ...) can all be used
on arrays just as easily as on a linked list. And there's no performance
penalty either.

> Perhaps it is the most general way to define an iterator that points
> to nothing? Certainly if the underlying implementation of a collection
> is an array, this makes sense. But if the underlying implementation is
> a list, then a null pointer makes more sense. Why not make the
> abstraction resemble a null pointer, rather than an out-of-bounds
> index?

But which list is the null pointer pointing to?  I did something like
this in my Ada book (plug, plug :-); there's an iterator for linked
lists which is a record with two components: a pointer to the list,
and a pointer to the position within the list (null = past-the-end).
And of course, if the pointer to the list is null, it means that the
iterator is invalid.

But anyway: a strength of the STL which seems difficult (impossible?)
to reproduce in Ada is the ability to treat built-in collection types
(arrays) in *exactly* the same way as user-defined collection types
(vectors, maps, etc.).

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Wanted: Ada STL. Reward: Ada's Future

[Tucker Taft]

John English wrote:
> ... 
> But anyway: a strength of the STL which seems difficult (impossible?)
> to reproduce in Ada is the ability to treat built-in collection types
> (arrays) in *exactly* the same way as user-defined collection types
> (vectors, maps, etc.).

You could certainly create an iterator for arrays that matched
whatever general iterator scheme you decide is best (presumably
by instantiating a generic package).

In my view, the C++ STL is (appropriately) following along in the
general C/C++ philosophy emphasizing writability over readability.

An Ada 95 STL should follow Ada's emphasis of readability over
writability.  Combining the notion of an iterator and a handle
into a single thing which resembles a C/C++ pointer seems very
inappropriate for Ada.  If you have two separate types, one for
the iterator, and one for the handle, there is less confusion
for the reader, but probably more work for the writer.

Perhaps the C++ tendency of trying to have a single class do
everything is part of the source of the difference.  In Ada, you
could have a single package with multiple types (handle, various
iterators, etc), which in the case of a collection, seems very 
sensible.  Because C++ and other class-oriented OOPs typically
merge the notion of types and modules, they tend to get a bit
miserly with types/classes, and try to make a single type play 
several roles, which can be confusing to the reader.

> -----------------------------------------------------------------
>  John English              | mailto:je@brighton.ac.uk
>  Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
>  Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
>  University of Brighton    |    -- see http://burks.bton.ac.uk
> -----------------------------------------------------------------

-Tuck
-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Fri, 5 Feb 1999, Tucker Taft wrote:
> In my view, the C++ STL is (appropriately) following along in the
> general C/C++ philosophy emphasizing writability over readability.
> 
> An Ada 95 STL should follow Ada's emphasis of readability over
> writability.  Combining the notion of an iterator and a handle
> into a single thing which resembles a C/C++ pointer seems very
> inappropriate for Ada.  If you have two separate types, one for
> the iterator, and one for the handle, there is less confusion
> for the reader, but probably more work for the writer.

I don't follow you here. What do you mean by "handle" in that paragraph?
If you write a bit of pseudocode showing handles and iterators in a 
collection package spec that would help.

> Perhaps the C++ tendency of trying to have a single class do
> everything is part of the source of the difference.  In Ada, you
> could have a single package with multiple types (handle, various
> iterators, etc), which in the case of a collection, seems very 
> sensible.  Because C++ and other class-oriented OOPs typically
> merge the notion of types and modules, they tend to get a bit
> miserly with types/classes, and try to make a single type play 
> several roles, which can be confusing to the reader.

Yes indeed. One reason to like Ada more ;-). 

OTOH, Ada is a little miserly with inheritance, since it is an SI
language. Something like Java interfaces or GNU C++ signatures would 
be very appealing, since Ada is one of the few languages with MI of 
implementation (via generic mixins or access discriminants) but no
convenient MI of interface. 

None of which matters for an STL like library, which eschews inheritance.

-- Brian 

Re: Wanted: Ada STL. Reward: Ada's Future

[Richard D Riehle]

In article <36BB3910.B460D8B@averstar.com>,
	Tucker Taft <stt@averstar.com> wrote:

>In my view, the C++ STL is (appropriately) following along in the
>general C/C++ philosophy emphasizing writability over readability.

 It has been said that C is a universal assembler.  Sometimes I
 think C++ is a class-based universal assembler.  STL is a collection
 of macros a class-based universal assembler.  This is not evil. It
 is often a useful view since such a perspective serves as a warning
 to the developer about the risks associated with using C++ for 
 creating reliable software.  Once a programmer accepts the reality
 of those risks, she/he can successfully create high quality software.

 Many of those risks are absent in Ada.  However, Ada has risks that
 are addressed better in C++.  For example, access parameters in 
 Ada 95 functions permit modification of the content of a record
 (struct).  A C++ function can be defined with a const for the 
 function or the parameter to ensure that the function is a "query
 only" function.  For Ada programmers, the syntax is equivalent to

     constant function F1 (A : access T) return Y;

 which guarantees that no updating capability is possible in this 
 function (like a protected function), or

     function F2 (A : access constant T) return Y;

 which guarantees that no update of any part of A is permitted.

 There are features of C++ which some might say are "better" than Ada. 
 The point is that comparing languages at this level is unprofitable. I
 prefer Ada for any software that is important, but I can see a lot of 
 ideas in C++ and Eiffel that are attractive language features.  

 Richard Riehle
 richard@adaworks.com
 http://www.adaworks.com
 

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Fri, 5 Feb 1999, John English wrote:

> Stephen Leake wrote:
> > I thought Matthew just did that, but you haven't answered the question
> > "why does the STL allow iteration past the end of the array". This
> > bugs me too. Is there a real reason here, or is it an accident of the
> > implementation?
> 
> A "past-the-end" value makes it easy to insert items into collections --
> you always insert BEFORE a particular position, so inserting before the
> past-the-end position will append to the end.  In the case of arrays you
> can't insert anything, but at least you have read access to arrays in
> exactly the same way as any other collection type.  This means that
> non-mutating algorithms (searching, counting, ...) can all be used
> on arrays just as easily as on a linked list. And there's no performance
> penalty either.
> 
> > Perhaps it is the most general way to define an iterator that points
> > to nothing? Certainly if the underlying implementation of a collection
> > is an array, this makes sense. But if the underlying implementation is
> > a list, then a null pointer makes more sense. Why not make the
> > abstraction resemble a null pointer, rather than an out-of-bounds
> > index?
> 
> But which list is the null pointer pointing to?  I did something like
> this in my Ada book (plug, plug :-); there's an iterator for linked

Let me take this opportunity to independently plug John's book. While I 
think it is aimed at beginning programmers, there are quite a few very
nice examples, and some nice Ada tricks. 

> But anyway: a strength of the STL which seems difficult (impossible?)
> to reproduce in Ada is the ability to treat built-in collection types
> (arrays) in *exactly* the same way as user-defined collection types
> (vectors, maps, etc.).

Exactly true. Anyone seeking to achieve the seamlessness of STL in Ada
will fail. Since you can't overload array indexing or pointer operations 
in Ada, *no* pure Ada library will achieve this. 

Another strength of C++ is in automatic instantiation of generic 
subprograms. This reduces the number of instantiations, and makes code a 
lot more readable, IMO, in the same way that overloading properly used 
makes code more readable. There really are some nice features of C++, its 
just too bad that the language as a whole suffers so much from its C 
lineage.

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

Brian Rogoff <bpr@shell5.ba.best.com> writes:

> Another strength of C++ is in automatic instantiation of generic 
> subprograms. This reduces the number of instantiations, and makes code a 
> lot more readable, IMO, in the same way that overloading properly used 
> makes code more readable.

You can get some of this in Ada, by using default params for generic
formal subprograms:

generic

   type Item_Type is private;

   type Stack_Type is limited private;
   
   with procedure Push
     (Item : in     Item_Type;
      On   : in out Stack_Type) is <>;

package GP is ...;


If Push is directly visible at the point of instantiation, then you
don't need to specify explicitly:

  package Item_Stacks is new Stacks (Item_Type);
  use Item_Stacks;

  package P is new GP (Item_Type, Stack_Type);


Another, lesser-used technique is to provide default parameters by name:

generic
  ...
package GP is

...
   procedure Do_Nothing;

   generic
      with procedure Do_At_End_Of_Line is Do_Nothing;
   package GQ is 

      ...
   end GQ;

end GP;

A client that doesn't need to do an end-of-line processing, doesn't need
to say anything else in his instantiation:

  package Q is new P.GQ;

Of course, he may want to do something different from the default:

  procedure Write_EOL;

  package Q is new P.GQ (Write_EOL);

Re: Wanted: Ada STL. Reward: Ada's Future

[Nick Roberts]

Matthew Heaney wrote ...
[...]
|This is yet another reason why I think that looking at the STL as a
|model for a standard Ada library is dangerous and misleading.
|
|The idioms in both languages are completely different.  So forget about
|the STL as a model for an Ada library.


Hear hear.

Nick

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Matthew Heaney wrote:
> John English <je@bton.ac.uk> writes:
> 
> > In Ada this isn't possible -- e.g. type Foo is array(Boolean) of Bar
> > has no "beyond the end" index that can be used to form non-inclusive
> > ranges [i,j).  This makes it hard to support arrays as "just another
> > collection type" in the way that the STL does, so you can't easily
> > define algorithms which can be applied impartially to arrays or
> > vectors or maps or whatever.
> 
> The problem in your example is your array index.  The rule in Ada is
> that an enumeration type is its own base type, and type Boolean has no
> other values than True and False.

Indeed.

> If you need to fall off the beginning or end of an array, you just need
> to make sure the base type of the index subtype has at least one extra
> value on either end, something like:
> 
>   type Color_Base is (First, Red, Green, Blue, Last);
> 
>   subtype Color_Type is Color_Base
>    range Color_Base'Succ (First) .. Color_Base'Pred (Last);

... which means that you couldn't apply STL-type algorithms to *any*
array the way you can in C++.  IMHO the nice thing about STL is the way
it lets you deal with arrays and user-defined containers in a completely
uniform manner.

> The idioms in both languages are completely different.  So forget about
> the STL as a model for an Ada library.

Indeed.  But *something* is needed; having everyone invent their own
propietary versions of common data types and algorithms is a complete
waste of time.  Even if the STL model doesn't fit Ada, it's useful as
a reminder of what can/should be provided.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Wanted: Ada STL. Reward: Ada's Future

[Ehud Lamm]

On Wed, 3 Feb 1999, John English wrote:

> IMHO performance is not the problem for implementing the STL in Ada.
[snip]
>   This makes it hard to support arrays as "just another
> collection type" in the way that the STL does, so you can't easily
> define algorithms which can be applied impartially to arrays or
> vectors or maps or whatever.

So if understand you correctly, you are also of the opinion that a simple
port of STL may be problematic. But - the problems are not performance.
Ok.

By the way, there is an interesting cultural/memetic phenomena here. I
raise it since it seems that Ada fans are interested in the marketplace of
ideas ("future"/"java" threads etc.).

If I understood the original question on this thred - it was about SOME
libray LIKE the C++ STL for Ada. Supplying things like sets and lists. We
started by dicussing which of these featurees are really needed, but soon
slipped to discussing proting the STL. We somehow missed the obvious
question which is "Can we do something better or functionally equivalent,
but different - in Ada."

This, to my mind, show that STL won the day. It is strange, since it is
one of the more complex libraries I saw, and most C++ programmers are
either afraid of using it - or simply don't know how.

However I find it a happy thing that generics are now deeply established -
even outside Ada. 

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il

Re: Wanted: Ada STL. Reward: Ada's Future

[Pat Rogers]

Ehud Lamm wrote in message ...
<snip>
>If I understood the original question on this thred - it was about
SOME
>libray LIKE the C++ STL for Ada. Supplying things like sets and
lists. We
>started by dicussing which of these featurees are really needed, but
soon
>slipped to discussing proting the STL. We somehow missed the obvious
>question which is "Can we do something better or functionally
equivalent,
>but different - in Ada."


Why not have the Ada community "standardize" on the the free Ada 95
Booch Components?  Specifically, expanding them after the core from
the C++ version is completed?


---
Pat Rogers                          Training & Development in:
http://www.classwide.com    Deadline Schedulability Analysis
progers@acm.org                 Software Fault Tolerance
(281)648-3165                       Real-Time/OO Languages

Re: Wanted: Ada STL. Reward: Ada's Future

[Larry Kilgallen]

In article <79cc3q$mms$1@remarQ.com>, "Pat Rogers" <progers@NOclasswideSPAM.com> writes:

> Why not have the Ada community "standardize" on the the free Ada 95
> Booch Components?  Specifically, expanding them after the core from
> the C++ version is completed?

Because the variety of meanings of the word "free" covers some things
that cannot be included in commercial software.  At some point it is
easier to reinvent the wheel than to spend life pretending to be a
lawyer.

Larry Kilgallen

Re: Wanted: Ada STL. Reward: Ada's Future

[Pat Rogers]

Larry Kilgallen wrote in message <1999Feb4.141530.1@eisner>...
>In article <79cc3q$mms$1@remarQ.com>, "Pat Rogers"
<progers@NOclasswideSPAM.com> writes:
>
>> Why not have the Ada community "standardize" on the the free Ada 95
>> Booch Components?  Specifically, expanding them after the core from
>> the C++ version is completed?
>
>Because the variety of meanings of the word "free" covers some things
>that cannot be included in commercial software.  At some point it is
>easier to reinvent the wheel than to spend life pretending to be a
>lawyer.


Do you have specific issues with the ACL, or is this a general
"anything that smacks of a legal issue is sufficient to prevent use"?
I assume the latter...

Re: Wanted: Ada STL. Reward: Ada's Future

[Larry Kilgallen]

In article <79d0db$6h5$1@remarQ.com>, "Pat Rogers" <progers@NOclasswideSPAM.com> writes:
> Larry Kilgallen wrote in message <1999Feb4.141530.1@eisner>...
>>In article <79cc3q$mms$1@remarQ.com>, "Pat Rogers"
> <progers@NOclasswideSPAM.com> writes:
>>
>>> Why not have the Ada community "standardize" on the the free Ada 95
>>> Booch Components?  Specifically, expanding them after the core from
>>> the C++ version is completed?
>>
>>Because the variety of meanings of the word "free" covers some things
>>that cannot be included in commercial software.  At some point it is
>>easier to reinvent the wheel than to spend life pretending to be a
>>lawyer.
> 
> 
> Do you have specific issues with the ACL, or is this a general
> "anything that smacks of a legal issue is sufficient to prevent use"?
> I assume the latter...

The latter, particularly in light of the fact that there are now several
forms in which these come; not just the GPL and LGPL used by GNAT.

Larry Kilgallen

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <1999Feb4.171318.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
> The latter, particularly in light of the fact that there
> are now several forms in which these come; not just the
> GPL and LGPL used by GNAT.

Larry, you really do not know what you are talking about
here. In particular, GNAT does NOT use the LGPL, whatever
made you think it does? Our view is that the LGPL is too
restrictive, so we use a much less restrictive license.

But the real point is, as I said in my last message, you
cannot avoid legal issues when using someone else's
copyrighted software.

You are quite right that merely because something is "free"
does not mean you can use it. You must read and study the
license agreement, just as you would if you were using
Microsoft software.

For example, cygwin is "free", but the generally available
version is distributed under the GPL. This means that it
cannot be used in proprietary software (if you want
to use cygwin in proprietary software, you must use the
proprietary version also available from Cygnus).

However, it is equally absurd to decide that because
something is "free", you cannot use it in proprietary
software. (I think you said commercial software in your
first message, but of course you meant proprietary
software, this is a common confusion!)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Larry Kilgallen]

In article <79dp2o$s2h$1@nnrp1.dejanews.com>, robert_dewar@my-dejanews.com writes:

> However, it is equally absurd to decide that because
> something is "free", you cannot use it in proprietary
> software.

And nobody said that it was impossible, so you erect
a paper tiger.  I said that it was too much trouble,
in the context of a discussion of somebody's class
library snippet.  It is different for something as
large as a compiler, where significant investment
in contract-reading may be warranted.  But for a
large number of items advertised as "free" (but
only under certain terms) in this newsgroup, the
effort outweighs the benefit.

The term "free" when used on code samples of this
size thus has all the significance of "coded by
left-handers" or "tested without using lab animals"
(as applied to software).

> I think you said commercial software in your
> software. (I think you said commercial software in your
> first message, but of course you meant proprietary
> software, this is a common confusion!)

If that is what I said, that is what I meant, as
the term "proprietary" has risen from non-use to
become an epithet used by advocates of "free"
software to describe anything that does not
claim to be "free".

This time I would invite _you_ to read Deja-News
for the past few years where you and I have had
this conversation, and not bore everyone else with
a replay.

Larry Kilgallen

Re: Wanted: Ada STL. Reward: Ada's Future

[Tom Moran]

> GNAT does NOT use the LGPL, whatever
>made you think it does?
  Aye, that's *exactly* the question. 
  Perhaps if a new sacred terminology hadn't been invented for the FSF
religion, but ordinary words had ordinary meanings, fewer people would
misunderstand or feel that they didn't understand.  Company lawyers
don't freak out when they see a Microsoft copyright, but they may say
"what's this" when they see a "copyleft".  Non-lawyers think they
understand "free" but it turns out to have a secondary, different,
meaning than the first one that came to mind - and the non-lawyers
start getting scared and running to the lawyers.
  But what's done is done and FSF software will just have to bear with
it..

Re: Wanted: Ada STL. Reward: Ada's Future

[dewar]

In article <36ba730b.35540068@news.pacbell.net>,
  tmoran@bix.com (Tom Moran) wrote:
> > GNAT does NOT use the LGPL, whatever
> >made you think it does?
>   Aye, that's *exactly* the question.
> Perhaps if a new sacred terminology hadn't been
> invented for the FSF religion, but ordinary words had
> ordinary meanings, fewer people would
> misunderstand or feel that they didn't understand.
> Company lawyers don't freak out when they see a Microsoft
> copyright, but they may say "what's this" when they see a
> "copyleft".

Note that Tom is involved with selling proprietary
software, so it is certainly in his interest that people
be worried about this :-)

But in fact, there is no problem here.

Lawyers do not "freak out" when they see the General
Public License, which incidentally does not use the
term "copyleft". This license is a legal document,
written by lawyers with the help of technical people,
intended to be read by both users and lawyers (just
like any other software license).

Yes it can be confusing to people who have not read
the license that the "free" in free software talks
about freedom and not lack of $$$. This is an unfortunate
ambiguity in English, but one that should not be too
difficult for people to deal with (I assume that when
people read a license plate that says "Live Free or
Die", they do not think that this is about saving money!)

Yes, that needs explaining, not to lawyers, since the GPL
is quite explicit and clear (paragraph two of the preamble
says:

  When we speak of free software, we are referring to
  freedom, not price.)

but it does need explaining to non-lawyers, especially
when they have been confused by posts such as those
recently made by Tom and Larry.

Lawyers certainly have no trouble understanding such
language, and in our experience, we have had no trouble in
interacting with lawyers who are reading the GPL. We have
occasionally in the past, much less recently, run into
situations where there have been rules against the use of
"free software", but once the lawyers get their hands on
the appropriate license agreements, they are then quite
comfortable.

The are often a bit puzzled that we would use a license
agreement that is so generous, and so unconcerned with
desparate protection of our "intellectual property", but
they can easily understand that from the point of view of
the licensee, all their requirements are met.

It is definitely true that the term open software causes
less confusion in some (non-legal) circles, since it
emphasizes an important aspect of free software.

However, there is open source software and open source
software, and not all of it is anywhere near "free" in the
sense of "freedom", so you also have to be careful with
license agreements there too.

The bottom line: the world of free software and open source
software does not somehow free you of your obligation to
carefully check that when you are using someone else's
software you are not violating their leagl rights under the
appropriate copyright law.

Robert Dewar
Ada Core Technologies

P.S. It's easier in other languages. ACT/Europe uses the
slogan "GNAT, c'est libre, mais c'est n'est pas gratuit",
but that's not easily translatable into English :-)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Tom Moran]

>Note that Tom is involved with selling proprietary
>software, so it is certainly in his interest that people
>be worried about this :-)
  To start with the ad hominem argument, yes, I am a professional
programmer - I earn my livelihood by selling my programming.  Since
ACT sells GNAT ("supported GNAT" costs $$$, while "unsupported GNAT"
has other restrictions in its copyright, but a requirement to send a
check to ACT is not among them), I think Dr. Dewar is also involved
with selling software.  He of course has an interest in having people
not worried, but rather attracted by words like "free".
>but it does need explaining to non-lawyers, especially
>when they have been confused by posts such as those
>recently made by Tom and Larry.
  That is exactly the problem, and it predates posts by myself or
Larry.  In English, as George Orwell among others have pointed out,
you are free (libre) to use words with any definition you like.  If
that aids your cause, OK; if it hinders your cause, as I believe it
does in this case for Larry and I, among others,  tough.
  One of the problems with reuse is that it needs to be easier than
reinvention.   For small pieces of code (not compilers) reinvention is
relatively easy.  As Larry points out, reading and feeling comfortable
with, or having your lawyer read and agree to, someone's
idiosyncratic restrictions on their "free" software is often harder
than reinvention.  

Re: Wanted: Ada STL. Reward: Ada's Future

[dewar]

In article <36bb301f.2303870@news.pacbell.net>,
  tmoran@bix.com (Tom Moran) wrote:

> As Larry points out, reading and feeling comfortable
> with, or having your lawyer read and agree to, someone's
> idiosyncratic restrictions on their "free" software is
> often harder than reinvention.

A good argument for *not* inventing idiosyncratic
restrictions, but rather using standard documents like
the (at this stage) very well understood GPL.

We often find sales people for other companies trying to
"scare" people into being worried about open source
software, but in these days of Linux and the open source
movement gathering real momentum, such tactics do not seem
to be successful in practice, and we have not run into
any situation where people were worried about the use of
open source software where a short conversation and
interchange of information did not entirely calm any
concerns.

Robert Dewar
Ada Core Technologies

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79fmg1$fn0$1@nnrp1.dejanews.com>,
  dewar@gnat.com wrote:
> In article <36bb301f.2303870@news.pacbell.net>,
>   tmoran@bix.com (Tom Moran) wrote:
>
> > As Larry points out, reading and feeling comfortable
> > with, or having your lawyer read and agree to, someone's
> > idiosyncratic restrictions on their "free" software is
> > often harder than reinvention.
>
> A good argument for *not* inventing idiosyncratic
> restrictions, but rather using standard documents like
> the (at this stage) very well understood GPL.

Bingo! I think that was the original point (at least that's what I thought it
was).

I'm currently trying to find a good open-source license to use, and this
trips over just the issue I'm comming up against. I don't wan't to use some
"idiosyncratic" license, because that in and of itself could somewhat limit
the software's use. But at the same time the GPL (and even to a lesser extent
the LGPL) seem to have unfortunate "infectious" attributes. Next chance I get
I'll look into the Ada Community License; hopefully it's better.

> We often find sales people for other companies trying to
> "scare" people into being worried about open source
> software, but in these days of Linux and the open source
> movement gathering real momentum, such tactics do not seem
> to be successful in practice, and we have not run into
> any situation where people were worried about the use of
> open source software where a short conversation and
> interchange of information did not entirely calm any
> concerns.

I've also seen open source advocates using similar "scare" arguments against
non-open source software. Frankly, I think the open source folks in many cases
have a better point.



T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dewar]

In article <79fvk4$npp$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:
> But at the same time the GPL (and even to a lesser extent
> the LGPL) seem to have unfortunate "infectious"
> attributes. Next chance I get I'll look into the Ada
> Community License; hopefully it's better.

Why not use the GNAT modified GPL? It is well understood
at this stage in the Ada community, and is well adapted
to Ada. It allows completely free use in proprietary
software, which is presumably the issue you want to address
here. Alternatively, you could use the BSD license.

As to whether it is unfortunate or not to prevent the use
of straight GPL'ed software in proprietary products, that
depends on your point of view.

The original GNAT project was required to use the GPL,
precisely to ensure that the resulting software could not
be "proprietarized" at any time in the future. This was
DoD's decision, and I think it serves the Ada community
well that GNAT is guaranteed to remain open, and that for
example, not even ACT could make a proprietary version of
GNAT (of course we don't want to do this anyway, but still
it is good for the Ada community to have a guarantee of
this continued openness, without depending on the good
will of ACT :-)

Robert Dewar
Ada Core Technologies

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79gro0$dhs$1@nnrp1.dejanews.com>,
  dewar@gnat.com wrote:
> In article <79fvk4$npp$1@nnrp1.dejanews.com>,
>   dennison@telepath.com wrote:
> > But at the same time the GPL (and even to a lesser extent
> > the LGPL) seem to have unfortunate "infectious"
> > attributes. Next chance I get I'll look into the Ada
> > Community License; hopefully it's better.
>
> Why not use the GNAT modified GPL? It is well understood
> at this stage in the Ada community, and is well adapted
> to Ada. It allows completely free use in proprietary
> software, which is presumably the issue you want to address
> here. Alternatively, you could use the BSD license.

That's a definite possiblity. Too bad it doesn't have a catchy name or
acronym. :-)

I'm not entirely sure I'd qualify it as "well understood", though. I'm not
even sure the GPL is all that well understood. I certainly seem to notice
something different every time I read it. And every time I see a thread about
it, there seem to be an awful lot of misunderstandings.


T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79mua4$242$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:

>  I'm not even sure the GPL is all that well understood. I
> certainly seem to notice something different every time I
> read it. And every time I see a thread about
> it, there seem to be an awful lot of misunderstandings.

I am talking about the people who matter, namely
procurement people at large companies. The fact that
there are CLA readers who misunderstand something proves
very little, as any reader of CLA is well aware :-)


-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79n7a3$9mk$1@nnrp1.dejanews.com>,
  robert_dewar@my-dejanews.com wrote:
> In article <79mua4$242$1@nnrp1.dejanews.com>,
>   dennison@telepath.com wrote:
>
> >  I'm not even sure the GPL is all that well understood. I
> > certainly seem to notice something different every time I
> > read it. And every time I see a thread about
> > it, there seem to be an awful lot of misunderstandings.
>
> I am talking about the people who matter, namely
> procurement people at large companies. The fact that
> there are CLA readers who misunderstand something proves
> very little, as any reader of CLA is well aware :-)

That's a good argument for something really large, or something that has to
be purchased (eg: Gnat). But the original question was about
freely-distributed open source libraries, downloaded from the net. Are you
saying that folks should to run things like the Ada95 Booch Components by
their procurement people?

From my experience at a large company, it would be far easier to just rewrite
what I need myself! They'd make me fill out a purchase order and a
sole-source justification form, then they'd flounder around for weeks trying
to do a market survey...

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79ngjc$hko$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:
> In article <79n7a3$9mk$1@nnrp1.dejanews.com>,
>   robert_dewar@my-dejanews.com wrote:
> Are you
> saying that folks should to run things like the Ada95
> Booch Components by their procurement people?

Most certainly if you used copyrighted software, you had
better run it by your legal people to make sure that it is
properly licensed. The fact that it is open source is quite
irrelevant to this requirement.

The idea that this means that it is easier to rewrite it
yourself is an old NIH argument that seldom holds water.
I have seen any number of occasions on which huge amounts
of time has been spent reinventing the wheel. Just remember
that typical software productivity is of the order of 10-20
lines/day, and you are unlikely to be at the high end of
this range when writing general purpose reusable libraries,
where the design is often very difficult.

I would be very suspicious of anyone making the claim that
Ted did that "oh we can rewrite it ourselves easily".

The point about using a standard license like the modified
GPL, is that it is already fairly familiar to the lawyers
who are likely to have to check out these kinds of
licenses.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79ojjt$en1$1@nnrp1.dejanews.com>,
  robert_dewar@my-dejanews.com wrote:
> of time has been spent reinventing the wheel. Just remember
> that typical software productivity is of the order of 10-20
> lines/day, and you are unlikely to be at the high end of
> this range when writing general purpose reusable libraries,
> where the design is often very difficult.
>
> I would be very suspicious of anyone making the claim that
> Ted did that "oh we can rewrite it ourselves easily".

Not quite. I said "easier", not "easily".

If it takes four weeks to get procurement to OK it, then by the above I could
write about 200 to 400 lines in that amount of time. If I'm looking to use the
Booch components, but all I *really* need is a simple queue targetted to one
specific purpose, it may well come in under 40 LOC.

I'm *not* saying that's the way to go. And I'm not saying "I never reuse code
because of this", so please don't try to cast me in that light. I'm just
pointing out the situation developers in large companies often find themselves
in.

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Nick Roberts]

Tsk tsk Robert. Cynicism in one so young.

;-)

robert_dewar@my-dejanews.com wrote in message
<79n7a3$9mk$1@nnrp1.dejanews.com>...
|The fact that
|there are CLA readers who misunderstand something proves
|very little, as any reader of CLA is well aware :-)

Re: Wanted: Ada STL. Reward: Ada's Future

[Simon Wright]

dennison@telepath.com writes:

> I'm currently trying to find a good open-source license to use, and this
> trips over just the issue I'm comming up against. I don't wan't to use some
> "idiosyncratic" license, because that in and of itself could somewhat limit
> the software's use. But at the same time the GPL (and even to a lesser extent
> the LGPL) seem to have unfortunate "infectious" attributes. Next chance I get
> I'll look into the Ada Community License; hopefully it's better.

I don't know who aside from the BCs uses the ACL (which was derived
from the Perl Artistic Licence). I'm contemplating using the licence
used by ACT in their Ada.* code instead .. seems to meet all anyone
could wish. However, no rush as yet!

Re: Wanted: Ada STL. Reward: Ada's Future

[Corey Minyard]

dennison@telepath.com writes:
> I'm currently trying to find a good open-source license to use, and this
> trips over just the issue I'm comming up against. I don't wan't to use some
> "idiosyncratic" license, because that in and of itself could somewhat limit
> the software's use. But at the same time the GPL (and even to a lesser extent
> the LGPL) seem to have unfortunate "infectious" attributes. Next chance I get
> I'll look into the Ada Community License; hopefully it's better.
> 

What is the problem with the LGPL?  I used that for my components.  It
allows inclusion into 3rd party programs without releasing source to
that 3rd party program.  It does require that you distribute (or tell
how to get) the included library.  If you make any changes to the
LGPL'ed library, you are also required to give the changes away.

So is there some reason I should switch?

-- 
Corey Minyard                   Internet:  minyard@acm.org
  Work: minyard@nortelnetworks.com  UUCP:  minyard@wf-rch.cirr.com

Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[dennison]

In article <m2hfsxgcz7.fsf@wf-rch.cirr.com>,
  minyard@acm.org wrote:
> dennison@telepath.com writes:
> > I'm currently trying to find a good open-source license to use, and this
> > trips over just the issue I'm comming up against. I don't wan't to use some
> > "idiosyncratic" license, because that in and of itself could somewhat limit
> > the software's use. But at the same time the GPL (and even to a lesser
extent
> > the LGPL) seem to have unfortunate "infectious" attributes. Next chance I
get
> > I'll look into the Ada Community License; hopefully it's better.
> >
>
> What is the problem with the LGPL?  I used that for my components.  It
> allows inclusion into 3rd party programs without releasing source to
> that 3rd party program.  It does require that you distribute (or tell
> how to get) the included library.  If you make any changes to the
> LGPL'ed library, you are also required to give the changes away.

According to section 5(p2), an executable linked with LGPL software is a
"derivative of the Library", and thus must be distributed under the rules in
section 6.

Section 6 seems to require that licensing terms for such derivatives must
allow users to reverse-engineer the executable. That is incompatable with a
typical closed-source license.

Paragraph 3 of section 6 looks like it would require a Windows user to
provide a linker to anyone they distribute the executable to!

I also am not quite sure how a child package would be accounted for here.
Would a court decide that is a modification to the library itself, or simply
a "work that uses the Library"?

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[Corey Minyard]

dennison@telepath.com writes:
> >
> > What is the problem with the LGPL?  I used that for my components.  It
> > allows inclusion into 3rd party programs without releasing source to
> > that 3rd party program.  It does require that you distribute (or tell
> > how to get) the included library.  If you make any changes to the
> > LGPL'ed library, you are also required to give the changes away.
> 
> According to section 5(p2), an executable linked with LGPL software is a
> "derivative of the Library", and thus must be distributed under the rules in
> section 6.
> 
> Section 6 seems to require that licensing terms for such derivatives must
> allow users to reverse-engineer the executable. That is incompatable with a
> typical closed-source license.

Right to reverse-engineer is guaranteed by law in the US (Nintento vs
Galoob).  What the licenses say means nothing.  US Congress is working
to change that, but maybe they can be stopped.

> 
> Paragraph 3 of section 6 looks like it would require a Windows user to
> provide a linker to anyone they distribute the executable to!

A DLL or shared library should be sufficient to meet this requirement.
The paragraph after paragraph d) in that section states that you don't
have to give them the linkers, compilers, etc.

How a generic might fit into this would be questionable.  Would it be
a "definition file" and thus recompiling would not be possible as
stated in that paragraph?  I'd guess so.

This would be the biggest restriction that might cause me to abandon
the LGPL.  It does seem a little excessive and might cause headaches
for a company supporting a product.

> 
> I also am not quite sure how a child package would be accounted for here.
> Would a court decide that is a modification to the library itself, or simply
> a "work that uses the Library"?

Difficult to say.  But if people are adding child packages to my
library, I want them to give me the new packages, since they are
extending my library.

-- 
Corey Minyard                   Internet:  minyard@acm.org
  Work: minyard@nortelnetworks.com  UUCP:  minyard@wf-rch.cirr.com

Re: Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[dennison]

In article <m2btj4hbbs.fsf@wf-rch.cirr.com>,
  minyard@acm.org wrote:
> dennison@telepath.com writes:
> >
> > Paragraph 3 of section 6 looks like it would require a Windows user to
> > provide a linker to anyone they distribute the executable to!
>
> A DLL or shared library should be sufficient to meet this requirement.
> The paragraph after paragraph d) in that section states that you don't
> have to give them the linkers, compilers, etc.

The passage we are referring to reads:

 "For an executable, the required form of the "work that uses the Library"
must include any data and utility programs needed for reproducing the
executable from it. However, as a special exception, the source code
distributed need not include anything that is normally distributed (in either
source or binary form) with the major components (compiler, kernel, and so
on) of the operating system on which the executable runs, unless that
component itself accompanies the executable."

It looks as if the intent is to allow rebuilding of the executable when a
newer version of the LGPL library is released. It seems to say that if a
compiler and linker normally comes with the OS, (eg: Unix) a developer
doesn't need to distribute it with their executable that used the GPL'ed
code. But that is not the case for Windows, so they would have distribute a
linker with their binary if they use LGPL software on Windows. Either way
they'd have to distribute all their object files so relinking can occur.

I think part of the problem is that this is really geared towards proper
object libraries, not files of reusable source code.

> How a generic might fit into this would be questionable.  Would it be
> a "definition file" and thus recompiling would not be possible as
> stated in that paragraph?  I'd guess so.

I hadn't thought about the generic issue.

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[Corey Minyard]

dennison@telepath.com writes:

> The passage we are referring to reads:
> 
>  "For an executable, the required form of the "work that uses the Library"
> must include any data and utility programs needed for reproducing the
> executable from it. However, as a special exception, the source code
> distributed need not include anything that is normally distributed (in either
> source or binary form) with the major components (compiler, kernel, and so
> on) of the operating system on which the executable runs, unless that
> component itself accompanies the executable."
> 
> It looks as if the intent is to allow rebuilding of the executable when a
> newer version of the LGPL library is released. It seems to say that if a
> compiler and linker normally comes with the OS, (eg: Unix) a developer
> doesn't need to distribute it with their executable that used the GPL'ed
> code. But that is not the case for Windows, so they would have distribute a
> linker with their binary if they use LGPL software on Windows. Either way
> they'd have to distribute all their object files so relinking can occur.

I would read it as a compiler is a "major component" of the operating
system and since the linker is part of that major component, the
linker need not be supplied.

> 
> I think part of the problem is that this is really geared towards proper
> object libraries, not files of reusable source code.
> 

Yes, you are right.  I'm going to change my license from LGPL to
something else.  I'm figuring out what to change it to now.

-- 
Corey Minyard                   Internet:  minyard@acm.org
  Work: minyard@nortelnetworks.com  UUCP:  minyard@wf-rch.cirr.com

Re: Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[robert_dewar]

In article <m2btj4hbbs.fsf@wf-rch.cirr.com>,
  minyard@acm.org wrote:

> Right to reverse-engineer is guaranteed by law in the US
> (Nintento vs Galoob).  What the licenses say means
> nothing.  US Congress is working
> to change that, but maybe they can be stopped.

Corey, you are not a lawyer, so you should be very careful
about making misleading statements like this. The case,
which by the way is misspelled here, it is Nintendo vs
Galoob, does not have anything like the general sweeping
interpretation that you suggest.

You need to study case law in much more detail, and I am
afraid you will find it is more depressing than you think
with respect to reverse engineering. Look for example at
Microsoft vs Stacker, and many other cases (if you go into
one of the standard legal search engines, and look for
reverse engineering, you will pull up quite a few cases).

You also need to study the recent legislation passed by
congress, which also affects the situation here.

It would be nice if you were right, but unfortunately, the
situation with reverse engineering is not nearly so black
and white as your wishful thinking would suggest.

I certainly agree that this is an area requiring people to
be educated, and to make their voices known. The situation
is already much worse than you suppose here.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future)

[Corey Minyard]

robert_dewar@my-dejanews.com writes:

> In article <m2btj4hbbs.fsf@wf-rch.cirr.com>,
>   minyard@acm.org wrote:
> 
> > Right to reverse-engineer is guaranteed by law in the US
> > (Nintento vs Galoob).  What the licenses say means
> > nothing.  US Congress is working
> > to change that, but maybe they can be stopped.
> 
> Corey, you are not a lawyer, so you should be very careful
> about making misleading statements like this. The case,
> which by the way is misspelled here, it is Nintendo vs
> Galoob, does not have anything like the general sweeping
> interpretation that you suggest.

I apologize for speaking out of line.  You are correct, I am not a
lawyer and should be more careful about what I say.

My knowledge (reading articles and the like) is old in this area.  

> 
> You need to study case law in much more detail, and I am
> afraid you will find it is more depressing than you think
> with respect to reverse engineering. Look for example at
> Microsoft vs Stacker, and many other cases (if you go into
> one of the standard legal search engines, and look for
> reverse engineering, you will pull up quite a few cases).

You are correct.  The reason you are reverse engineering matters, I
believe.  And the method, too.  Care should be taken.  And it is
depressing.

> 
> You also need to study the recent legislation passed by
> congress, which also affects the situation here.

This is true, and is also depressing.


Thank you for your response.

-- 
Corey Minyard                   Internet:  minyard@acm.org
  Work: minyard@nortelnetworks.com  UUCP:  minyard@wf-rch.cirr.com

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <m2hfsxgcz7.fsf@wf-rch.cirr.com>,
  minyard@acm.org wrote:
> What is the problem with the LGPL?  I used that for my
> components.  It allows inclusion into 3rd party programs
> without releasing source to that 3rd party program.  It
> does require that you distribute (or tell how to get) the
> included library.  If you make any changes to the LGPL'ed
> library, you are also required to give the changes away.
>
> So is there some reason I should switch?


There are two potential problems with the LGPL, the "you"
in the following is someone trying to use your LGPL'ed
library.

1. It does not deal with the issue of instantiation of
generics, since it talks only about linking, so if you
do instantiate generics, you create a fully GPL'ed program,
since the exception does not apply.

2. It forces you to avoid inlining against the library, and
also to distribute your program in object form, since it
requires that the user of your program be able to relink
the program with a modified version of the library.

If neither of these points is an issue, then the use of the
LGPL is just fine.

Note that the modified GPL used for GNAT is basically the
same language that is used for the runtime components of
GNU C and G++, with the addition of special language to
handle the case of generic instantiations.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79oi8n$dna$1@nnrp1.dejanews.com>,
  robert_dewar@my-dejanews.com wrote:
> In article <m2hfsxgcz7.fsf@wf-rch.cirr.com>,
>   minyard@acm.org wrote:
> > What is the problem with the LGPL?  I used that for my
> > components.  It allows inclusion into 3rd party programs
> > without releasing source to that 3rd party program.  It
> > does require that you distribute (or tell how to get) the
> > included library.  If you make any changes to the LGPL'ed
> > library, you are also required to give the changes away.
> >
> > So is there some reason I should switch?
>
> There are two potential problems with the LGPL, the "you"
> in the following is someone trying to use your LGPL'ed
> library.
>
> 1. It does not deal with the issue of instantiation of
> generics, since it talks only about linking, so if you
> do instantiate generics, you create a fully GPL'ed program,
> since the exception does not apply.
>
> 2. It forces you to avoid inlining against the library, and
> also to distribute your program in object form, since it
> requires that the user of your program be able to relink
> the program with a modified version of the library.
>
> If neither of these points is an issue, then the use of the
> LGPL is just fine.
>
> Note that the modified GPL used for GNAT is basically the
> same language that is used for the runtime components of
> GNU C and G++, with the addition of special language to
> handle the case of generic instantiations.

Hmmm. It looks like you exempt linked in code from the GPL "infection", but
does that extend to code that also needs the package spec to compile? I'd
think it would, but it isn't clear to me from the text.

As you were quick to point out, it doesn't have to be clear to me to hold up
in court. But I certainly want to be clear on what it means before I license
my own code with it!

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79qe6k$33d$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:
> Hmmm. It looks like you exempt linked in code from the
> GPL "infection", but does that extend to code that also
> needs the package spec to compile? I'd think it would,
> but it isn't clear to me from the text.

Yes, of course, why on earth do you raise this as a special
issue? You have to link in the specification to your
application to use it! Probably this question comes from
not being familiar with the structure of GNAT.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Simon Wright]

tmoran@bix.com (Tom Moran) writes:

>   One of the problems with reuse is that it needs to be easier than
> reinvention.   For small pieces of code (not compilers) reinvention is
> relatively easy.  As Larry points out, reading and feeling comfortable
> with, or having your lawyer read and agree to, someone's
> idiosyncratic restrictions on their "free" software is often harder
> than reinvention.  

Do you bother to read the header files that come with your C compiler?
full of legalese, as I recall!

Seems to me you guys are putting yourselves at a distinct competitive
disadvantage here ..

-- 
Simon Wright                        Work Email: simon.j.wright@gecm.com
Alenia Marconi Systems                         Voice: +44(0)1705-701778
Command & Information Systems Division           FAX: +44(0)1705-701800

Re: Wanted: Ada STL. Reward: Ada's Future

[Larry Kilgallen]

Reply-To: Kilgallen@eisner.decus.org.nospam
Organization: LJK Software
Lines: 21

In article <79fmg1$fn0$1@nnrp1.dejanews.com>, dewar@gnat.com writes:
> In article <36bb301f.2303870@news.pacbell.net>,
>   tmoran@bix.com (Tom Moran) wrote:
> 
>> As Larry points out, reading and feeling comfortable
>> with, or having your lawyer read and agree to, someone's
>> idiosyncratic restrictions on their "free" software is
>> often harder than reinvention.
> 
> A good argument for *not* inventing idiosyncratic
> restrictions, but rather using standard documents like
> the (at this stage) very well understood GPL.

Precisely.

And for clarification, I am not intellectually opposed to paying
lawyers to look at licenses.  I have done it, but only in cases
where software in question was much more valuable to me than
a set of subprograms.

Larry Kilgallen

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79d0db$6h5$1@remarQ.com>,
  "Pat Rogers" <progers@NOclasswideSPAM.com> wrote:
> Do you have specific issues with the ACL, or is this a
> general "anything that smacks of a legal issue is
> sufficient to prevent use"? I assume the latter...

The odd thing here is that you can't use ANY copyrighted
software without reading and understanding the license
and making sure you are following the conditions of the
license. The idea that a license that gives you access to
the sources is somehow more worrisome than one that does
not is truly bizarre -- well actually it is usually more
a matter of ignorance or deliberate obfuscation to think
that there is any issue here at all.

An important thing to remember with, for example, GPL'ed
software is that it is copyrighted, licensed software. You
can only use it if you conform to the conditions of the
license, otherwise you are violating the copyright. Yes,
the license is less restrictive than some other licenses,
it is more restrictive than some other licenses.

The point here is that when using copyrighted software, you
cannot avoid legal issues, you need to make sure you have
the legal right to use it and that you are properly
licensed for this use, and that applies if you are using
Microsoft Word, or GNU EMACS.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <1999Feb4.141530.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
> Because the variety of meanings of the word "free" covers
> some things that cannot be included in commercial
> software.  At some point it is easier to reinvent the
> wheel than to spend life pretending to be a lawyer.


This is nonsense obfuscation.

It is perfectly possible for open source software to be
licensed in such a way that it can perfectly well be
included in commercial software. To imply otherwise is
a common marketing trick by those involved with proprietary
software, but it is bogus.

Examples of licensing provisions that are consistent with
such usage are the modified GPL used in GNAT, and the BSD
licensing used for X. There is lots of commercial software
using both of these items!

Robert Dewar
Ada Core Technologies

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Larry Kilgallen]

In article <79do2l$r62$1@nnrp1.dejanews.com>, robert_dewar@my-dejanews.com writes:
> In article <1999Feb4.141530.1@eisner>,
>   Kilgallen@eisner.decus.org.nospam wrote:
>> Because the variety of meanings of the word "free" covers
>> some things that cannot be included in commercial
>> software.  At some point it is easier to reinvent the
>> wheel than to spend life pretending to be a lawyer.
> 
> 
> This is nonsense obfuscation.
> 
> It is perfectly possible for open source software to be
> licensed in such a way that it can perfectly well be
> included in commercial software. To imply otherwise is
> a common marketing trick by those involved with proprietary
> software, but it is bogus.

And _that_ is non-responsive.  My complaint is not that any
particular meaning (e.g., those terms chosen by GNAT) is not
compatible, but that everyone who has a different idea seems
to come up with their _own_ license terms for "free" software,
and at least some of those are not compatible with commercial
use.

Sure it is "perfectly possible", but it is certainly not
"always done" with all software labeled "free" that is
discussed in this group.

For other constituencies, such as academic researchers, the
restrictions may never matter.  Even Robert Dewar has twisted
a discussion of "free" software into one of "open source"
software.  Certainly "free" has a very loose set of meanings,
and that is exactly the point.

Larry Kilgallen

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <1999Feb4.230015.1@eisner>,
  Kilgallen@eisner.decus.org.nospam wrote:
> And _that_ is non-responsive.  My complaint is not that
> any particular meaning (e.g., those terms chosen by GNAT)
> is not compatible, but that everyone who has a different
> idea seems to come up with their _own_ license terms for
> "free" software, and at least some of those are not
> compatible with commercial use.

And why not, the same is true for proprietary software. You
might just as well have said

  "My complaint is not that any particular meaning (e.g.
   those terms chosen by Microsoft) is not compatible, but
   that everyone who has a different idea seems to come up
   with their own license terms for "proprietary" software
   and at least some of those are not compatible with
   commercial use."

So what????

Yes, of course for any use (I have no idea what you mean by
commercial use), you are *legally* obligated to check
carefully before you use someone else's software that you
are legally entitled to do so, otherwise you may be
violating the copyright law.

Some people may have the completely wrong idea that this
step can be skipped with "free" software, but they are
plain mistaken!

So what's the complaint here? That everyone does not decide
to license their work on the same basis? Why on earth
should they? The copyright holder has a perfect right to
decide on the license conditions.

Robert Dewar

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <36BB4162.52FC6D9F@averstar.com>,
  Tucker Taft <stt@averstar.com> raised his virtual hand and wrote:
> dennison@telepath.com wrote:
>
> > ... Lets
> > take the very popular VisualC++ compiler as an example here. It comes with a
> > very lengthy license that is prominently displayed during installation. Now
> > let's have a virtual show of hands. How many people here have ever read the
> > entire license carefully to make sure that it provides them the legal right
> > to do what they want to do with the code it produces? I predict I won't see
a
> > lot of hands. Why not? Well, I'm no sociologist, but it appears folks
*trust*
> > Microsoft to not restrict the commercial use of the code developed with
their
> > tools.
>
> Well, it is always fun to take Microsoft as an example.  This
> one is particularly interesting.  If you build your product
> using Visual C++ and decide to leave debugging enabled in
> the released product, you will find that you *cannot* distribute
> your product, because it now has dependencies on DLLs that
> you do not have the right to distribute.   What a pain...
>

Ooooh. That *is* interesting!

I suppose it would be OK if the recipients have VC++ installed. What's an
extra $250? :-)

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <36BB4162.52FC6D9F@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> Well, it is always fun to take Microsoft as an example.
> This one is particularly interesting.  If you build your
> product using Visual C++ and decide to leave debugging
> enabled in the released product, you will find that you
> *cannot* distribute your product, because it now has
> dependencies on DLLs that you do not have the right to
> distribute.   What a pain...


Well I am sure that T.E.D can go right ahead and distribute
his program with the DLL's. After all they don't have time
to read license agreements, and they trust Microsoft,
right? :-)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79eo76$kkk$1@nnrp1.dejanews.com>,
  robert_dewar@my-dejanews.com wrote:
> In article <1999Feb4.230015.1@eisner>,
>   Kilgallen@eisner.decus.org.nospam wrote:
> > And _that_ is non-responsive.  My complaint is not that
> > any particular meaning (e.g., those terms chosen by GNAT)
> > is not compatible, but that everyone who has a different
> > idea seems to come up with their _own_ license terms for
> > "free" software, and at least some of those are not
> > compatible with commercial use.
>
> Yes, of course for any use (I have no idea what you mean by
> commercial use), you are *legally* obligated to check
> carefully before you use someone else's software that you
> are legally entitled to do so, otherwise you may be
> violating the copyright law.

Technicly, yes that's true. But we are talking actual practice, here. Lets
take the very popular VisualC++ compiler as an example here. It comes with a
very lengthy license that is prominently displayed during installation. Now
let's have a virtual show of hands. How many people here have ever read the
entire license carefully to make sure that it provides them the legal right
to do what they want to do with the code it produces? I predict I won't see a
lot of hands. Why not? Well, I'm no sociologist, but it appears folks *trust*
Microsoft to not restrict the commercial use of the code developed with their
tools.

As you yourself point out, putting the same trust in random open-source tools
would be foolhardy. The fact of the matter is that I'm a S/W engineer and not
a lawyer. The thought of possibly rendering several man-years of my own and
other people's work useless due to my own misreading of a license is pretty
chilling. For myself, I think the benifits of open-source software tend to be
worth the risk. But I can certianly understand the position of those who
don't agree.

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[robert_dewar]

In article <79f24e$t14$1@nnrp1.dejanews.com>,
  dennison@telepath.com wrote:
> Technicly, yes that's true. But we are talking actual
> practice, here. Lets take the very popular VisualC++
> compiler as an example here. It comes with a
> very lengthy license that is prominently displayed during
> installation. Now let's have a virtual show of hands. How
> many people here have ever read the entire license
> carefully to make sure that it provides them the legal
> right to do what they want to do with the code it
> produces?

I strongly suggest that you *do* read the license agreement
that comes with *any* product. You will find lots of
surprises, and you may well find restrictions that will
indeed cause you difficulties. This is actually *more*
likely to happen with a commercial compiler than in the
case of a GNU compiler.

Why -- because, for example, in the case of GNAT, the
license agreement has been written to ensure that (a) you
have the rights you need and (b) it is easy for you to
ensure that this is the case.

In the case of a proprietary compiler, it is not clear that
(a) or (b) is a goal, and indeed historically many
proprietary Ada compilers, some of which at least are still
on the market, charge run time fees, and do NOT license
free use of generated code.

Better check!!!!!!!!!!!!

(or indeed you can be in hot water)

We have the impression from a number of previous posts that
the environment that Ted works in is, shall we say,
somewhat laissez-faire, but to advocate ignoring license
agreements is definitely going a bit far, and can get you
in hot water indeed.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <79flvt$f7r$1@nnrp1.dejanews.com>,
  robert_dewar@my-dejanews.com wrote:
> In article <79f24e$t14$1@nnrp1.dejanews.com>,
>   dennison@telepath.com wrote:
> We have the impression from a number of previous posts that
> the environment that Ted works in is, shall we say,
> somewhat laissez-faire, but to advocate ignoring license

(sigh)

Due to a few selective twists of the meaning of things I've said, that does
appear to be your impression. (Exhibit A: I never *advocated* anything of the
sort). But luckily for the US taxpayer the DoD doesn't tend to put up with
that kind of thing.

But believe what you want. It ceritainly makes it easier to dismiss whatever I
say.


T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Nick Roberts]

Hand

Re: Wanted: Ada STL. Reward: Ada's Future

[Tucker Taft]

dennison@telepath.com wrote:

> ... Lets
> take the very popular VisualC++ compiler as an example here. It comes with a
> very lengthy license that is prominently displayed during installation. Now
> let's have a virtual show of hands. How many people here have ever read the
> entire license carefully to make sure that it provides them the legal right
> to do what they want to do with the code it produces? I predict I won't see a
> lot of hands. Why not? Well, I'm no sociologist, but it appears folks *trust*
> Microsoft to not restrict the commercial use of the code developed with their
> tools.

Well, it is always fun to take Microsoft as an example.  This
one is particularly interesting.  If you build your product
using Visual C++ and decide to leave debugging enabled in
the released product, you will find that you *cannot* distribute
your product, because it now has dependencies on DLLs that
you do not have the right to distribute.   What a pain...

> T.E.D.

-Tuck
-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: Wanted: Ada STL. Reward: Ada's Future

[Al Christians]

Ehud Lamm wrote:
> 
> This, to my mind, show that STL won the day. It is strange, since it is
> one of the more complex libraries I saw, and most C++ programmers are
> either afraid of using it - or simply don't know how.
> 

There must be lessons to be learned from the C++ experience with STL.
1. It is powerful and if it delivers what it should, it allows the
programmer using it to program at a higher level of abstraction.
2. Unfortunately, it is hard to implement, so there are multiple
inconsistent, incomplete, incorrect versions available, making it much 
less pleasant to use.
3. When it doesn't work, it is very hard for the to debug and/or fix.
4. When some deep bug occurs in a C++ program using STL (for example
an attempt to free memory not currently owned), the STL is suspect,
but it is very hard to determine if the cause is in the STL or
elsewhere.   

Any attempts to provide similar library for Ada should be made in light
of such experience. 

Al

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Thu, 4 Feb 1999, Ehud Lamm wrote:

> On Wed, 3 Feb 1999, John English wrote:
> 
> > IMHO performance is not the problem for implementing the STL in Ada.
> [snip]
> >   This makes it hard to support arrays as "just another
> > collection type" in the way that the STL does, so you can't easily
> > define algorithms which can be applied impartially to arrays or
> > vectors or maps or whatever.

There is an obvious way to do it, and that is simply to define the array
iterator as a record with a pointer to an array and an index. This may not
satisfy John's definition of "easily", but it shows that it can be done.

Incidentally, the language Ness which was a part of the Andrew Toolkit had 
as a basic data type the "subsequence reference", which consists of a 
pointer to a string and two indices (lo and hi, say) and uses these
instead of strings. Many basic string algorithms are expressed elegantly 
in terms of operations on subsequences. Nice stuff, and easily implemented
in Ada. See http://www.cs.cmu.edu/~wjh/papers/subseq.html

> So if understand you correctly, you are also of the opinion that a simple
> port of STL may be problematic. But - the problems are not performance.
> Ok.
> 
> By the way, there is an interesting cultural/memetic phenomena here. I
> raise it since it seems that Ada fans are interested in the marketplace of
> ideas ("future"/"java" threads etc.).
> 
> If I understood the original question on this thred - it was about SOME
> libray LIKE the C++ STL for Ada. Supplying things like sets and lists. We
> started by dicussing which of these featurees are really needed, but soon
> slipped to discussing proting the STL. We somehow missed the obvious
> question which is "Can we do something better or functionally equivalent,
> but different - in Ada."

By necessity, a port of the STL to Ada will be different. C++ templates
and Ada generics are quite different, the overloading schemes are
different, etc., etc. 

In that the STL is sometimes used to effect a functional style of
programming in C++, I think Ada will look better since Ada generics take 
subprogram parameters, Ada has nested subprograms, etc., etc., 

C++ provides more syntactic sugar, allowing the overloading of array
indexing amongst others, so there is a seamlessness to the STL that 
probably won't be achieved in a "pure Ada" translation. 

What troubles me about this discussion is the notion that anything that is 
done in C++ is anathema to Ada. There is a C++ Booch Component Library, so 
therefore the Booch Components are the wrong model for any Ada library. 

> This, to my mind, show that STL won the day. It is strange, since it is
> one of the more complex libraries I saw, and most C++ programmers are
> either afraid of using it - or simply don't know how.

It's actually a fairly simple library, the problem is that many C++ compilers
still don't handle the C++ template system in its glory (;-)) so that 
many C++ programmers probably stick to a simple subset of the language. 
I expect that will change as C++ compilers mature, and the STL becomes
more popular.

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[Matthew Heaney]

Brian Rogoff <bpr@shell5.ba.best.com> writes:

> What troubles me about this discussion is the notion that anything that is 
> done in C++ is anathema to Ada. There is a C++ Booch Component Library, so 
> therefore the Booch Components are the wrong model for any Ada library. 

I think this is a misreading of what has been said.

The point is that idioms naturally expressible one language aren't easily
expressible the other.

For example, here's a quote from Robert Dewar about a French expression:

>P.S. It's easier in other languages. ACT/Europe uses the
>slogan "GNAT, c'est libre, mais c'est n'est pas gratuit",
>but that's not easily translatable into English :-)

The literal English translation is, "GNAT, it's free, but it's not
free."

But you wouldn't say it that way in English, because that wouldn't make
any sense.

So be careful about literal translations of C++ to Ada95.

Re: Wanted: Ada STL. Reward: Ada's Future

[Brian Rogoff]

On Fri, 5 Feb 1999, Matthew Heaney wrote:

> Brian Rogoff <bpr@shell5.ba.best.com> writes:
> 
> > What troubles me about this discussion is the notion that anything that is 
> > done in C++ is anathema to Ada. There is a C++ Booch Component Library, so 
> > therefore the Booch Components are the wrong model for any Ada library. 
> 
> I think this is a misreading of what has been said.
> 
> The point is that idioms naturally expressible one language aren't easily
> expressible the other.

Since I've frequently acknowledged that a literal translation of STL is
not possible, and asked for specific reasons why an STL like library
(please take the time to read the *like*) is somehow a "bad" idea in Ada, 
I can only guess that you haven't read anything I've written, or examined 
any of the C++ STL implementations, or the Ada implementations, which are 
fairly different.

John English thinks that the nicest thing about the STL is the way that it 
works with C++ native arrays and pointers, so I see why he may think an 
Ada library in this style won't be nice, and I completely disagree, since
I think the STL is nice even when just dealing with STL containers.

> For example, here's a quote from Robert Dewar about a French expression:

Instead of this example, how about a real example from AGL or SGL or your
own library showing why the STL approach is so bad in Ada. Quotes from
Robert Dewar about French and English are just not convincing to me. I am 
aware of Ada's deficiencies vis-a-vis C++, and I still like the STL
approach.

> So be careful about literal translations of C++ to Ada95.

Setting up the strawman of "literal translation", and knocking it down.

Once again, there is a large chunk of available code for you to critique, 
use it for examples. I have no doubt you can find flaws, and if you help 
me or the RPI guys to get a better Ada library, even if you don't like it, 
we all win.

-- Brian

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Brian Rogoff wrote:
> John English thinks that the nicest thing about the STL is the way that it
> works with C++ native arrays and pointers, so I see why he may think an
> Ada library in this style won't be nice, and I completely disagree, since
> I think the STL is nice even when just dealing with STL containers.

Oh, don't get me wrong. I'd like to see a standard Ada library that
provides a selection of containers and algorithms -- but in Ada it
will either need a wrapper to provide a containerish interface for
arrays, or Java-like conversion operations between arrays and container
types. However the main thing is that it should:

a) be *standard*, so everyone can use it portably and expect it to
   be universally available
b) provide not just containers but also *algorithms* -- it's no good
   having linked lists, sets, maps and so on without standard operations
   like sort/search/partition/count.

I think the way the STL uses pointer semantics is neat and very very
clever. But as we've all been saying for the last week, we can't do
it that way in Ada. What we need to do is find an Ada-natural way of
doing what the STL does and providing the facilities that the STL
provides.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Ehud Lamm wrote:
> If I understood the original question on this thred - it was about SOME
> libray LIKE the C++ STL for Ada. Supplying things like sets and lists. We
> started by dicussing which of these featurees are really needed, but soon
> slipped to discussing proting the STL. We somehow missed the obvious
> question which is "Can we do something better or functionally equivalent,
> but different - in Ada."

Don't forget the algorithms that the STL provides. Data structures would
be nice to have, but I don't want to have to (re)write algorithms to
sort/search/count/permute/partition those data structures.

> This, to my mind, show that STL won the day. It is strange, since it is
> one of the more complex libraries I saw, and most C++ programmers are
> either afraid of using it - or simply don't know how.

True!

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Wanted: Ada STL. Reward: Ada's Future

[micro_ada]

In article <36BAEEA5.A01CACEA@bton.ac.uk>,
  John English <je@bton.ac.uk> wrote:
> Ehud Lamm wrote:
> > If I understood the original question on this thred - it was about SOME
> > libray LIKE the C++ STL for Ada. Supplying things like sets and lists. We
> > started by dicussing which of these featurees are really needed, but soon
> > slipped to discussing proting the STL. We somehow missed the obvious
> > question which is "Can we do something better or functionally equivalent,
> > but different - in Ada."
>
> Don't forget the algorithms that the STL provides. Data structures would
> be nice to have, but I don't want to have to (re)write algorithms to
> sort/search/count/permute/partition those data structures.

"A Systematic Catalogue of Reusable Abstract Data Types" by Jurgen Uhl and
Hans Albrecht Schmid (1990, Springer-Verlag, ISBN 0-387-53229-3) provides a
useful general strategy.  However, concrete information is presented as Ada +
macro language specifications which are expressly copyrighted by the authors
but with no mention of licensing terms.  I have not bothered to investigate
licensing terms of their software interfaces because I don't have their
implementations. And the only point I wish to make concerning licensing
issues for an Ada standard generic library is that its' public interface must
be non-proprietary and unquestionably open to access from the entire Ada
community.

Their Ada 87 design needs to be updated to use Ada 95 object-oriented features
or improved generics.  They used generics to simulate Ada 95-like abstract
types, and "variant parameter" macros to simulate Ada 95-like generic
parameters.  A cpp macro preprocessor produced various Ada compilation units.
The authors compare the pros and cons of using Ada versus C++ circa 1990.  The
structure of their catalogue is a hierarchy of building blocks, where higher
level data types partially inherit operations from lower level ones.

Unique features include:

1) A three level hierarchy of building blocks.  The low level is the Ada array
and access types.  The middle level is the linked collection, tabular
collection, and hash table types.  The high level is intended for the general
user and supports list, stack, queue/deque (double ended queue), tree, order,
set, map, and bag types.  The functional behavior is defined by these high
level abstract data types, which have a standardized interface across all data
types.  Each high level abstract data type has on the order of a thousand
different implementations to be accessed from one uniform interface.  Thus a
clear and strict separation is made between functional aspects and performance
efficiency aspects.

2) Reuse within reuse for the library maintainer because every data
representation and access algorithm is implemented only once but available
for every suitable abstract data type.	Additionally a user enjoys
flexibility to select the most general abstract data type suitable and
stepwise refine among variants for performance reasons.  Later, the user may
readily switch to a more capable general abstract data type if the
requirements change drastically enough.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Nick Roberts]

John English wrote in message <36B856E4.D921C1D@bton.ac.uk>...
[...] ranges [i,j) which [...]

A true mathematician!
(As rare as a breeding Hoopoe, these days :-)

Nick Roberts

BTW: John's assertion that Ada library has to be written for Ada: agreed.

Re: Wanted: Ada STL. Reward: Ada's Future

[John English]

Nick Roberts wrote:
> John English wrote in message <36B856E4.D921C1D@bton.ac.uk>...
> [...] ranges [i,j) which [...]
> 
> A true mathematician!
> (As rare as a breeding Hoopoe, these days :-)

But notice that I have to explain what I mean just in case anyone
thinks I've just maid a typping misteak.  :-)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[adam]

In article
<Pine.A41.3.96-heb-2.07.990201214336.46206A-100000@pluto.mscc.huji.ac.il>,
  Ehud Lamm <mslamm@mscc.huji.ac.il> wrote:

> It seems that one problem in implementing STL in Ada95 is the lack of
> pointer arithmetic.  This causes perofremance problems in real sense (to
> be exact the result is worse from a complexity point of view). This is a
> "nice" result in that it tells you something about the price you pay for
> pointer abstraction etc. However it is sad from a practical point of view.
> I haven't really pursued this, so I can't vouch that there isn't some
> trick to solve this problem.

I don't know how this relates to STL, but I think I can see what the poster
is getting at.	Pointer arithmetic can be efficient when you're trying to
step through an array, since you don't have to keep multiplying an index by a
constant value to access the array elements.  I'm not sure how much of a
difference that makes these days---chips have gotten so fast that
multiplication might not be that big a deal any more.  But anyway, let's
assume for argument's sake that efficiency is a concern and that we want to
avoid multiplication if we can.

I believe one of the strengths of Ada is that it gives implementors choice
about how to implement data.  Unless you use Unchecked_Conversion or other
overlaying tricks, you really don't care just what bits are stored in a
variable.  (I don't believe C/C++ gives this kind of flexibility, although
I haven't read the standards for those languages.)  So is there any reason an
implementor couldn't provide pointer arithmetic with a pragma like:

    type My_Index is range 0 .. 100;
    Arr : array (My_Index range 1 .. 100) of Some_Nasty_Record_Type;
    pragma Index_Into_Array (My_Index, Arr);

This pragma states that all objects of type "My_Index" will be indexes into
the array object Arr, and that therefore they could be implemented as
pointers to array elements.  So if Index is declared as type "My_Index", then
"Index := 1;" would set Index to the address of Arr(1); "Index := Index+3;"
would increment Index by three times the size of Some_Nasty_Record_Type;
and indexing Arr (e.g. Arr(Index).Field) would be a pointer dereference, as
in C.

Questions:
(1) Is there anything in the RM that would make such an implementation of
    My_Index illegal?
(2) Has any compiler vendor tried something like this?

				-- Adam


-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[William Clodius]

adam@irvine.com wrote:
> <snip>
> I don't know how this relates to STL, but I think I can see what the poster
> is getting at.  Pointer arithmetic can be efficient when you're trying to
> step through an array, since you don't have to keep multiplying an index by a
> constant value to access the array elements.  I'm not sure how much of a
> difference that makes these days---chips have gotten so fast that
> multiplication might not be that big a deal any more.  But anyway, let's
> assume for argument's sake that efficiency is a concern and that we want to
> avoid multiplication if we can.
> <snip>

???

What are your reasons for thinking that indexing an array requires
multiplications that are not also required for the useage of pointers?

For most machines in use the most efficient implementations of arrays is
as a single contiguous block that is accessed by mapping indices
directly to the equivalent pointer operations. (The exceptions are more
easilly mapped to arrays and not to pointers.) It is true that mapping
involving an index other than the most rapidly varying one can be
thought of as involving a multiplication, but the same is true of the
equivalent pointer arithmetic. In both cases the same functionality can
be obtained by adding a (n easilly determined)  finite integer to the
current memory index. The analysis for the compiler to do this is so
simple, I would not be surprized if Ada Lovelace discussed it for
Babage's machine in the 1800s.  Any compiler that does not perform that
analysis is broken.

It is sometimes thought that because it is relatively easy for the
programmer to move some of the pointer arithmetic outside the loop, that
pointer arithmetic is more efficient, but the algorithms necessary to
perform that motion by the compiler have been available since the first
Fortran compiler, ca. 1957. Any compiler that does not perform that
analysis is a toy and not a professional system. It is more likely that
a programmer will not perform the necessary analysis for the pointers,
than that a compiler will not perform the analysis.

-- 

William B. Clodius		Phone: (505)-665-9370
Los Alamos Nat. Lab., NIS-2     FAX: (505)-667-3815
PO Box 1663, MS-C323    	Group office: (505)-667-5776
Los Alamos, NM 87545            Email: wclodius@lanl.gov

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[adam]

In article <36B78CDD.1372@lanl.gov>,
  William Clodius <wclodius@lanl.gov> wrote:

> For most machines in use the most efficient implementations of arrays is
> as a single contiguous block that is accessed by mapping indices
> directly to the equivalent pointer operations. (The exceptions are more
> easilly mapped to arrays and not to pointers.) It is true that mapping
> involving an index other than the most rapidly varying one can be
> thought of as involving a multiplication, but the same is true of the
> equivalent pointer arithmetic. In both cases the same functionality can
> be obtained by adding a (n easilly determined)  finite integer to the
> current memory index. The analysis for the compiler to do this is so
> simple, I would not be surprized if Ada Lovelace discussed it for
> Babage's machine in the 1800s.  Any compiler that does not perform that
> analysis is broken.
>
> It is sometimes thought that because it is relatively easy for the
> programmer to move some of the pointer arithmetic outside the loop, that
> pointer arithmetic is more efficient, but the algorithms necessary to
> perform that motion by the compiler have been available since the first
> Fortran compiler, ca. 1957. Any compiler that does not perform that
> analysis is a toy and not a professional system. It is more likely that
> a programmer will not perform the necessary analysis for the pointers,
> than that a compiler will not perform the analysis.

I'm not quite following everything you say.  I agree that if you're using
the index variable inside a FOR loop, it should be easy for the compiler to
optimize the index operations so that no multiplication is used, e.g.

    for I in Arr'range loop
        Do_Something_With (Arr (I));
    end loop;

But what if the operation of stepping through the array isn't so neatly
packaged?  Note that while I was talking about stepping through an array,
I never said anything about this stepping taking place inside a single loop.
It's certainly conceivable (if you have a package that declares
an iterator, for example) that the index manipulation might not even be
handled within the same subprogram call.  You might have to provide a
routine that steps to the next element of the array, then saves the index
in a global variable or an object's "work area" before the subprogram exits,
and then use the saved index the next time the subprogram is called.  It
seems to me that it would be a lot harder for a compiler to perform the
analysis required to determine that the index should be implemented with
pointer arithmetic.  Granted, when a program starts getting this complex,
it's hard for me to come up with a real-life example where the few nanoseconds
saved by avoiding multiplications would really make a difference.

				-- Adam

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[robert_dewar]

In article <798d2s$cce$1@nnrp1.dejanews.com>,
  adam@irvine.com wrote:
> In article <36B78CDD.1372@lanl.gov>,
> But what if the operation of stepping through the array
> isn't so neatly packaged?  Note that while I was talking
> about stepping through an array, I never said anything
> about this stepping taking place inside a single loop.

Find a real program and measure the effect, you will be
surprised how small it is in practice, and indeed I doubt
you will find anything to measure in a real program.

Yes, you can always construct an artifical benchmark that
shows something, but in practice this particular issue is
a non-issue in real programs.

The kind of program you postulate just does not occur in
practice, or occurs so seldom that the optimization effect
you are talking about is negligible.

Figuring out what really makes a difference in real
programs is not an easy task, and most people's intution
in this area is just plain wrong.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[Jean-Pierre Rosen]

robert_dewar@my-dejanews.com a �crit dans le message
<799eph$7gf$1@nnrp1.dejanews.com>...
>Figuring out what really makes a difference in real
>programs is not an easy task, and most people's intution
>in this area is just plain wrong.
>
Can't resist to take the opportunity to quote one of my favorite
sayings:
"The only constant thing I found when trying to measure efficiency is
that you don't spend your time where you thought you would"
---------------------------------------------------------
           J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://perso.wanadoo.fr/adalog

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[Nick Roberts]

adam@irvine.com wrote in message <798d2s$cce$1@nnrp1.dejanews.com>...
[...]
|It's certainly conceivable (if you have a package that declares
|an iterator, for example) that the index manipulation might not even be
|handled within the same subprogram call.  You might have to provide a
|routine that steps to the next element of the array, then saves the index
|in a global variable or an object's "work area" before the subprogram
exits,
|and then use the saved index the next time the subprogram is called.
[...]

In a case like this - where speed really mattered (and it does sometimes) -
the programmer would make the inner subroutine 'inline' - so that it was
effectively expanded into its constituent statements in place of every call.
The compiler would then be able to optimise the code from indexes into
pointers (and all the other ways) with no problem. Some compilers can
perform inter-procedural optimisations anyway, including the keeping of an
intermediate value in a register between calls.

-------------------------------------------
Nick Roberts
-------------------------------------------

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[William Clodius]

adam@irvine.com wrote:
> <snip>
> It's certainly conceivable (if you have a package that declares
> an iterator, for example) that the index manipulation might not even be
> handled within the same subprogram call.  You might have to provide a
> routine that steps to the next element of the array, then saves the index
> in a global variable or an object's "work area" before the subprogram exits,
> and then use the saved index the next time the subprogram is called.  It
> seems to me that it would be a lot harder for a compiler to perform the
> analysis required to determine that the index should be implemented with
> pointer arithmetic.  Granted, when a program starts getting this complex,
> it's hard for me to come up with a real-life example where the few nanoseconds
> saved by avoiding multiplications would really make a difference.
> <snip>

The procedure call is liable to overwhelm any performance gains in any
case, but it depends on how sophisticated the language is in its
treatment of arrays. I am more familiar with Fortran than with Ada so I
will use it as an example. In Fortran you can change the mapping of
indices onto an array in different contests, i.e., treat a one
dimensional array as a multidimensional array and a multidimensional
array as one dimensional. Indexing in the one dimensional mapping is
exactly equivalent to using a pointer on most processors. In Fortran for
your example you could replace the global pointer value with a "global"
index value into the single dimensional array mapping and there is no
difference in what the compiler should be doing, in that context. In
other contexts  using arrays instead of pointers allows better out of
bounds checking, and easier memory management by the processor.


-- 

William B. Clodius		Phone: (505)-665-9370
Los Alamos Nat. Lab., NIS-2     FAX: (505)-667-3815
PO Box 1663, MS-C323    	Group office: (505)-667-5776
Los Alamos, NM 87545            Email: wclodius@lanl.gov

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[Nick Roberts]

All unnecessary, Adam. Nowadays, (most) optimising compilers do what you
suggest automatically, without the need for a pragma.

A loop of the kind

   for i in 1..10 loop
      a(i) := b(i) + c(i);
   end loop;

will be compiled as if you had written

   xyz *pa = &a[0];
   xyz *pb = &b[0];
   xyz *pc = &c[0];
   <10 times>{ *pa++ = *pb++ + *pc++; };

and is also likely to have loop unrolling, instruction scheduling, and lots
of other things, applied, all to speed up your humble loop.

-------------------------------------------
Nick Roberts
-------------------------------------------

adam@irvine.com wrote in message <797na3$obg$1@nnrp1.dejanews.com>...
[...]
|Pointer arithmetic can be efficient when you're trying to
|step through an array, since you don't have to keep multiplying an index by
a
|constant value to access the array elements.
[...]

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[robert_dewar]

In article <798lej$69d$1@plug.news.pipex.net>,
  "Nick Roberts" <Nick.Roberts@dial.pipex.com> wrote:
> All unnecessary, Adam. Nowadays, (most) optimising
> compilers do what you suggest automatically, without the
> need for a pragma.

Adam is claiming that the pointer arithmetic in C speeds
up generated code by eliminating stride computations in
some programs. While it is true that of course there are
programs in which stride computations can be eliminated,
the wide spread use of pointers in C in general *damages*
the quality of the code by introducing uncontrolled
aliasing that the compiler cannot deal with.

If in C we see an isolated statement

   *p++ = 5;

as opposed to

   x[i++] = 5;

it is true we saved the stride computation in accessing
the array, BUT, in the absence of global information quite
unlikely to be available in the case Adam is looking at
(i.e. the case where the index computation cannot be
strength reduced), the assignment to *p++ potentially
destroys all sorts of aliasing linkes, requiring things
to be dumped from registers etc. This latter effect is
FAR more damaging than the stride computation, which you
might want to note is free on many machines in many cases
(e.g. on the ia32 for strides of 1,2,4,8).

The design of C in general is effective in allowing the
user to do some optimization when using a completely stupid
compiler that does no optimization at all. For example, the
register declaration is in this category.

But with a modern optimizing compiler, the excessively low
level of C code (in particular its over-reliance on
explicit pointers) is counter productive (it is interesting
to note that most modern optimizing C compilers simply
ignore the register declaration, they can do a better job
than the programmer of figuring out what to keep in
registers), but these same optimizing compilers cannot undo
the (mis)use of pointer arithmetic for, e.g. array
referencing.

Robert Dewar

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[Robert A Duff]

robert_dewar@my-dejanews.com writes:

> The design of C in general is effective in allowing the
> user to do some optimization when using a completely stupid
> compiler that does no optimization at all. For example, the
> register declaration is in this category.

True, but to be fair, both compiler and hardware technology have changed
somewhat since C was designed.

> But with a modern optimizing compiler, the excessively low
             ^^^^^^
> level of C code (in particular its over-reliance on
> explicit pointers) is counter productive

Indeed.

>... (it is interesting
> to note that most modern optimizing C compilers simply
> ignore the register declaration, they can do a better job
> than the programmer of figuring out what to keep in
> registers), but these same optimizing compilers cannot undo
> the (mis)use of pointer arithmetic for, e.g. array
> referencing.

True for locals and parameters.  I know of a couple of modern C
compilers that obey the "register" keyword when the variable is not
local to a function.  This can be an efficiency win in some kinds of
programs.

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[robert_dewar]

In article <797na3$obg$1@nnrp1.dejanews.com>,
  adam@irvine.com wrote:
> Pointer arithmetic can be efficient when you're trying to
> step through an array, since you don't have to keep
> multiplying an index by a constant value to access the
> array elements.

Please don't guess at something like this without looking
at generated code. Any half-way decent compiler will be
able to strength reduce these multiplications in a typical
loop and produce code that is EXACTLY as efficient as the
low level encoding in C, if not more efficient, depending
on the machine.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Stanley R. Allen]

Alexy V Khrabrov wrote:
> 
>  Now, I'd like to ask all of you to
> evaluate the status of reusable software for Ada, and first and foremost, an
> analog of a standard library with basic data structures.  The main reference
> point is C++ STL.  I'm very concerned there's nothing near  in Ada.  And yet
> the main purpose of Ada is to facilitate software reuse!
> 

Ada's version of STL is called SGL (get it?).  The last download
that I made is SGL version 2.0, alpha 3.  SGL is (or was) being
worked by people at Rensselaer Polytech.  The ftp site is
ftp://ftp.cs.rpi.edu/pub/stl -- the file is still there.

RPI folks also were responsible for STL.  I don't know their future
plans for SGL.

-- 
Stanley Allen
mailto:srallen@hti.com

Re: Wanted: Ada STL. Reward: Ada's Future

[Jerry van Dijk]

Alexy V Khrabrov (khrabrov.a@worldnet.att.net) wrote:

: cross-implementation and action.  Now, I'd like to ask all of you to
: evaluate the status of reusable software for Ada, and first and foremost, an
: analog of a standard library with basic data structures.  The main reference
: point is C++ STL.  I'm very concerned there's nothing near  in Ada.  And yet

Well, it do not think anyone is stopping you to write an STL equivalent in
Ada. Maybe it has not been done yet because most people, like myself, already
have a directory full of standard components, which we have been using for
years, and know and trust.

--
-- Jerry van Dijk | Leiden, Holland
-- Team Ada       | jdijk@acm.org
-- see http://stad.dsl.nl/~jvandyk

Re: Wanted: Ada STL. Reward: Ada's Future

[Marin David Condic]

Jerry van Dijk wrote:
> Well, it do not think anyone is stopping you to write an STL equivalent in
> Ada. Maybe it has not been done yet because most people, like myself, already
> have a directory full of standard components, which we have been using for
> years, and know and trust.
> 
I've evolved a number of similar tools myself. Our group makes an effort
to take anything that is general in nature and keep it in reuse
libraries. Problem #1: You don't always know what is in the reuse
library because it is a) undocumented and/or b) too large to effectively
search.

What would be nice is to have an appendix to the ARM that described
package specifications for various common data structures, etc. We have
it for Strings and various math functions, but why not some of the
garden variety data structures? (you'd need several flavors of these for
different requirements, much like there are three flavors of strings
supported.) The appendix could be optional since not all targets would
be interested in it. But at least with a written down specification of
what the packages should look like and what the behavior of the
operations should be, I could implement my own if necessary and be
asured that the usage would be portable and comprehensible to other Ada
programmers. Having it written down in an agreed-upon standard would be
a major advantage for reusability.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy,
            Ecole Superieure de Guerre.

Re: Wanted: Ada STL. Reward: Ada's Future

[dennison]

In article <790f4q$3l@bgtnsc01.worldnet.att.net>,
  "Alexy V Khrabrov" <khrabrov.a@worldnet.att.net> wrote:

> Consider this simple task: a set.  In C++, you get it from the STL.  How do
> you get one in Ada?

Back in the Ada 83 days I looked into creating a reusable set package, along
the lines of the SET type available for Pascal and Modula-2. What I quickly
discovered was that Ada's support for Boolean operations on arrays of booleans
made it completely unnessecary. For all intents and purposes, you *do* have a
set type in Ada!

Example:
   type Color is (Red, Green, Blue, Black, Teal);
   type Color_Set is array (Color) of Boolean;
   Palette : Color_Set;

Inclusion:
      if Palette(Red) then ...
Intersection:
      Colorblind_Palette := Palette and Colorblind_Visible_Colors;
Union:
      Palette := Palette or Colors_At_The_Artshop;
Negation:
      Unavailable_Colors := not Palette;

etc.

Admittedly, an implementation of a very large sparse set using only boolean
arrays is not the best way to go. But I have yet to ever need that
functionality myself...

T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Wanted: Ada STL. Reward: Ada's Future

[Jeff Carter]

Alexy V Khrabrov wrote:
> ...
> Can you please share your thoughts on the status of an Ada STL?  (Let's code
> name it Ada STL for the purpose of discussion.)  Is there anything close for
> Ada 95?  What are YOU guys using for your Ada programming?  I can't believe
> each of you has a jar with homegrown sets, linked lists, and queues, all
> implemented differently!  OK, let's start small.  Can you please tell me
> with as more URLs as possible, what exactly you use when you need
> 
> 1.  Linked lists
> 2.  Trees
> 3.  Queues
> 4.  Sets
> ...

FWIW, I use the PragmAda Reusable Components. I don't use trees; I
prefer to use skip lists when I need a balanced structure.

-- 
Jeff Carter
E-mail: carter commercial-at innocon [period | full stop] com
"We call your door-opening request a silly thing."
Monty Python & the Holy Grail

Re: Wanted: Ada STL. Reward: Ada's Future

[Michael F Brenner]

> 1.  Linked lists
> 2.  Trees
> 3.  Queues
> 4.  Sets
> ...            

I agree with Jeff in that I use skip lists instead of most tree
structures used for lookups. Code for skip lists has been posted 
here several times. An extensible (unlimited size) vector (also
called long_array) package that divides an array up into 
contiguous banks of memory (effectively a linked list of
blocks of objects) can be the basis of many kinds of sets, 
the data storage for trees and graphs, and be the entire basis
of linked lists, stacks, and queues of any fixed length objects.

That is the easy part. 

The medium part is variable length objects. To do this, you need
to simulate string sliceing, only not on characters, but on 
complex objects. That can be done by adding a layer of
heap management that does the slicing and reallocates storage
within your pool (or, if your run-time has memory leaks or an
insufficiently powerful garbage collector, then within you
heap of heaps). This could use a free list, for example, to
reclaim storage within the heap of heaps.

The hard part might be complex, highly nested structures of
variable length objects nested within variable length objects
to many levels of nesting. I am about to implement a 
heap-of-heaps reclamation on exactly such a datastructure
(the SJ Neural Net, I guess we should call it). I will let you
know how it goes.

Where do you get this code? Most of it is on-line for downloading,
but if you have specific needs, post them here and ask specific 
questions.

Re: Wanted: Ada STL. Reward: Ada's Future

[Corey Minyard]

I've stayed out of this fray for a while, but I thought I would throw in
my 2 cents.

"Alexy V Khrabrov" <khrabrov.a@worldnet.att.net> writes:
> 
> Greetings --
> 
> I'm assembling a case for Ada for teaching at the University of Pennsylvania
> in Philadelphia.  I compare Ada to Java, currently used here as the main
> vehicle for teaching various programming disciplines.  Ben and Mike already
> provided helpful presentation support, and Tuck promised to share his
> theoretical and empirical knowledge of Ada versus Java in
> cross-implementation and action.  Now, I'd like to ask all of you to
> evaluate the status of reusable software for Ada, and first and foremost, an
> analog of a standard library with basic data structures.  The main reference
> point is C++ STL.  I'm very concerned there's nothing near  in Ada.  And yet
> the main purpose of Ada is to facilitate software reuse!
> 
> In a comparative assessment of programming languages, the state of existing
> reusable components is paramount.  Yet for Ada, it's rather dreadful.

There are many useful reusable components for Ada.  There is the Booch
components, for instance.  I have written a set of components, too,
which can not come into general usage since they will compile with
gnat-3.11p :-), but not gnat-3.10p :-(.

> 
> Consider this simple task: a set.  In C++, you get it from the STL.  How do
> you get one in Ada?

I looked very strongly at the STL as a model when I was writing my
components.  I gave up on it after a while.  IMHO, it is too focused
(low-level) and not general enough to be useful.

For instance, you mention sets.  Well, any container is technically
either a set (no duplicates) or a bag (allows duplicates).  So when I
wrote my containers, I created general set/bag operations that work on
any container type.  Of course, efficiency varies with container type,
you would probably want to use the hash table or btree, but there is
nothing that prevents someone from doing a set/bag operation on a
list, for instance.

The STL seemed very inflexible on storage management, too.  Not a lot
of options.

> 
> There seems to be no central library equivalent to STL.  I looked at HBAP,
> and it turns out many links there are dangling -- to PAL for instance.
> There's a passage diminishing STL, yet there should be a clear guide how to
> find a complete replacement of all the necessary pieces of STL.  All serious
> people program with C++ and STL.  If they turn to Ada, a replacement to STL
> is like the first gulp of water they need for a break.

I do agree that it would be nice if the Ada community would
standardize on a set of reusable components, but better ones than the
STL.  Maybe we could come up with a standards committee for this?
Maybe not, those things take forever :-).

> Can you please share your thoughts on the status of an Ada STL?  (Let's code
> name it Ada STL for the purpose of discussion.)  Is there anything close for
> Ada 95?  What are YOU guys using for your Ada programming?  I can't believe
> each of you has a jar with homegrown sets, linked lists, and queues, all
> implemented differently!  OK, let's start small.  Can you please tell me
> with as more URLs as possible, what exactly you use when you need
> 
> 1.  Linked lists
> 2.  Trees
> 3.  Queues
> 4.  Sets
> 
> I feel Sets are the litmus tests for an Ada STL.  Where do you guys get
> sets?
> It's very important to assess the situation, and I hope to hear from you
> with as much detail as your busy schedules permit.

My components have all of these (and a lot more).  You can get them at
 http://www.concentric.net/~Minyard.
Comments are welcome.

-- 
Corey Minyard                   Internet:  minyard@acm.org
  Work: minyard@nortelnetworks.com  UUCP:  minyard@wf-rch.cirr.com