List container strawman

List container strawman

[Ted Dennison]

Since we do seem to be reaching a small amount of agreement on details, I went
ahead a put together a strawman package spec (sans private part) for the
unbounded list container, for the purposes of keeping the dicussions rolling in
a postitive direction. It is attached here, and available on my website at
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it
is close enough to be worth persuing, we may be able to use it as a starting
point.

(Note: The htmlization there was done by a tool I'm developing as part of the
next release of OpenToken. If you have comments on the job it did, I'd like them
too, but email would probably be the best venue for it).

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[James Rogers]

My attempts to access your website result in the following message:

The page that you have requested /dennison/Ted/htmlify.css was not
found.

Jim Rogers
Colorado Springs, Colorado USA

Ted Dennison wrote:
> 
> Since we do seem to be reaching a small amount of agreement on details, I went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it
> is close enough to be worth persuing, we may be able to use it as a starting
> point.
> 
> (Note: The htmlization there was done by a tool I'm developing as part of the
> next release of OpenToken. If you have comments on the job it did, I'd like them
> too, but email would probably be the best venue for it).
> 
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
> 
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ted Dennison]

In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says...
>
>My attempts to access your website result in the following message:
>
>The page that you have requested /dennison/Ted/htmlify.css was not
>found.

Out of curiosity, what browser were you using? It works fine for me with IE 5
and Mozilla 0.95. However, I have had someone else report trouble with an older
version of Netscape.

However, I just ran the page through the CSS validator, and it reports the same
error you are reporting. Basicly, I forgot to put up the style sheet that goes
with it. Ooops! I'll get that up there when I get back home.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Preben Randhol]

On Fri, 02 Nov 2001 14:23:32 GMT, Ted Dennison wrote:
> In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says...
>>
>>My attempts to access your website result in the following message:
>>
>>The page that you have requested /dennison/Ted/htmlify.css was not
>>found.
> 

> Out of curiosity, what browser were you using? It works fine for me
> with IE 5 and Mozilla 0.95. However, I have had someone else report
> trouble with an older version of Netscape.

It works with: w3m, links, lynx, opera, dillo, galeon, skipstone,
konqueror :-)

Preben
-- 
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: List container strawman

[Larry Kilgallen]

In article <E%xE7.9986$xS6.13571@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes:

> However, I just ran the page through the CSS validator, and it reports the same
> error you are reporting. Basicly, I forgot to put up the style sheet that goes
> with it. Ooops! I'll get that up there when I get back home.

CSS is a relatively new feature for browsers (and _working_ CSS is
even newer).

Unlike an Ada project where you pick a version (Ada95) and force
everyone to use that version, World Wide Web communications must
often work to people who have made different tool choices.

Dreamweaver 4 has the capability to take a CSS-designed web page
and create backward compatible source for actual deployment.

Re: List container strawman

[Eric Merritt]

Just out of curiosity, for the iteration functions
would it be more efficient/readable to provide a
Has_Next and Has_Previous routines that return a
boolean? I realize that you have already provided
mechenisims in teh Size function and the raiseing the
No_More exception.


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman

[Ted Dennison]

In article <mailman.1004675765.27706.comp.lang.ada@ada.eu.org>, Eric Merritt
says...
>
>Just out of curiosity, for the iteration functions
>would it be more efficient/readable to provide a
>Has_Next and Has_Previous routines that return a
>boolean? I realize that you have already provided
>mechenisims in teh Size function and the raiseing the
>No_More exception.

It certinaly shouldn't be tough to do, so I don't see a good reason for not
doing it. However, the iterators as presented have serious problems. I have to
redo them anyway, so it may be best to reserve discussion about them (other than
how to redo them of course) until that is done.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ehud Lamm]

Thanks fro the effort. Sorry I didn't have time these past week to
contribute anything.

A few questions/comments. I am not sure about many of these.

1. In my scheme "Element" is a generic parameter of the top package
(Containers), and not of the specific implementations.
(Remember, my attemp for having interface inheritance)

2. Why is List private? Shouldn't it be limited private, so we avoid
possible erros caused by aliasing?
We may need a private implementation, but I'd prefer this not to be the
default, since it can come and bite you when you don't know what you are
doing. The private version is for library builders and more advanced users,
best used as part of a layered design that hides the list itself.
(If the majority wants private, at least the spec should mention the
possbile problems)


3. "Construct" is indeed a long name. We can, as part of the library, decide
on some standard name for this like - or +

4. I've seen many implemenations that paremtrize Insert and Remove with a
direction parameter, instead of having seperate routines (_Back/_Front). I
am not sure I know which approach I prefer...

5. Front() and Back() raise execption on Empty List?


6. I like having a "No_More_Elements()" operation as part of the Iterator
interface. It saves time compared to Size (for containers that don't keep
count of size), and I don't like programming with exceptions ("exceptions
for control flow").

7. Sort should be in a child unit.

Finally, a more general question:
Is this a DeQueue or a Doubly-linked list? Should these be two different
abstractions? (IMO: Yes, they should).

Ehud

Re: List container strawman

[Marin David Condic]

Limited private sounds like a good idea to me - with operations to assign
one list to another via duplication.

One other thing: Allow me publically to display my ignorance. If Element is
private, how does this play with tagged records? I know there is a "tagged
private" formal type - but I've never played with it so I don't know what
the implications are for that. If the Element type is "private" only and
this precludes some things, that's probably O.K. for a first cut - it would
let you pile up most of the basic data types and so would be useful. Just
wondering how the tagged private thing works.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9rti6v$hcu$1@news.huji.ac.il...
>
> 2. Why is List private? Shouldn't it be limited private, so we avoid
> possible erros caused by aliasing?
> We may need a private implementation, but I'd prefer this not to be the
> default, since it can come and bite you when you don't know what you are
> doing. The private version is for library builders and more advanced
users,
> best used as part of a layered design that hides the list itself.
> (If the majority wants private, at least the spec should mention the
> possbile problems)
>

Re: List container strawman

[Francisco Javier Loma Daza]

On 2 Nov 2001, Marin David Condic wrote:
> Date: 2 Nov 2001 14:57:16 GMT
> To: comp.lang.ada@ada.eu.org
> From: "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]
> Reply-To: comp.lang.ada@ada.eu.org
> Sender: comp.lang.ada-admin@ada.eu.org
> Subject: Re: List container strawman
> 
> Limited private sounds like a good idea to me - with operations to assign
> one list to another via duplication.
> 
> One other thing: Allow me publically to display my ignorance. If Element
> is
> private, how does this play with tagged records? I know there is a
> "tagged
> private" formal type - but I've never played with it so I don't know what
> the implications are for that.


    If the formal is tagged private then you can derive a tagged type from
it.

generic
    type T is tagged private;
package DD

    type Object is new T with null record;

end DD;

Re: List container strawman

[Marin David Condic]

O.K. Thanks. Now I get it.

My guess is that you could still instantiate with a tagged type, so piling
up tagged records should not be a problem, right? Could you instantiate with
a 'Class wide type so anything of a class could be put on the list?

Of course you could not do an abstract type (to a plain old private formal)
since they don't exist yet, but I don't see that as a drawback.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Francisco Javier Loma Daza" <Francisco.Loma@isotrol.com> wrote in message
news:mailman.1004716745.9697.comp.lang.ada@ada.eu.org...
>
>     If the formal is tagged private then you can derive a tagged type from
> it.
>
> generic
>     type T is tagged private;
> package DD
>
>     type Object is new T with null record;
>
> end DD;
>
>

Re: List container strawman

[Ted Dennison]

In article <9ruhig$kef$1@nh.pace.co.uk>, Marin David Condic says...
>up tagged records should not be a problem, right? Could you instantiate with
>a 'Class wide type so anything of a class could be put on the list?

I don't believe so. However, you can't do that with an array either. In both
cases you'd have to use a pointer to your tagged type. That would mean you'd
have to avoid the funtional stuff ("&" routines), or at least be careful using
it.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ted Dennison]

In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
>1. In my scheme "Element" is a generic parameter of the top package
>(Containers), and not of the specific implementations.
>(Remember, my attemp for having interface inheritance)

I didn't do that because that is precisely what Booch does that makes it so
complicated to use. If one does that, then proper use of the package would
require 3 cascading generic package instantiations. If that is OK, then in my
opinion we should just bag this whole thing and use Booch.

>2. Why is List private? Shouldn't it be limited private, so we avoid
>possible erros caused by aliasing?

First off, I'd like to note for anyone who may have missed it, that any Element
passed in to be put on a list or taken off of one will be *copied*. Pointers to
elements will not be used.

If List were limited private, then we'd have to get rid of all those "&"
routines. My thinking was that Lisp-like functional list processing would be
desirable. You could indeed have aliasing problems, but only if your Element
type uses pointers. Having "&" avaliable also makes list operations somewhat
consistent with arrays, which also have "&".

However, any use of those "&" routines will involve creating a copy of every
element (much like using "&" with arrays does). That would probably be too
expensive in most cases, so perhaps it really isn't all that valuable. I'm
curious how others feel about this.

>(If the majority wants private, at least the spec should mention the
>possbile problems)

I can agree with this. At the least there should be some sort of warning in
there about using pointers in Element with those routines.

>3. "Construct" is indeed a long name. We can, as part of the library, decide
>on some standard name for this like - or +

As the comment said, I seriously considered that. However, it is not (yet) a
common idiom to use those for constructors. So I'm not sure if it would help or
hurt readability. Again, I'm curious what people think about this.

>4. I've seen many implemenations that paremtrize Insert and Remove with a
>direction parameter, instead of having seperate routines (_Back/_Front). I
>am not sure I know which approach I prefer...

>5. Front() and Back() raise execption on Empty List?

Assuming you are talking about the iterator routines "First" and "Last", that's
a good point. I seem to have totally neglected that case, and thus left serious
problems in there. For instance, the comment that says "For an empty list, First
= Last." is clearly wrong. That would indicate a list with one element, not an
empty one. I'll have to redo the iterators somehow...


>6. I like having a "No_More_Elements()" operation as part of the Iterator
>interface. It saves time compared to Size (for containers that don't keep
>count of size), and I don't like programming with exceptions ("exceptions
>for control flow").

That seems sensible. And I agree about using exceptions, which is why it is only
one example of 3. That stuff is all wrong anyway though...

>7. Sort should be in a child unit.

Why do you feel that way? What does putting it off in a separate unit gain you?

>
>Finally, a more general question:
>Is this a DeQueue or a Doubly-linked list? Should these be two different
>abstractions? (IMO: Yes, they should).

What specificly would the difference be?

Clearly it would have to be doubly-linked to support all those push and pop
operations, and both Next and Previous as iterators. You could implement those
on a singly-linked list, but it wouldn't be very efficient.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

O.K. I hereby revoke my agreement with Limited Private. If the List type
works kind of like the Ada.Strings.Unbounded.Unbounded_String type, then I
guess we're O.K. (Lists do look an awful lot like Ada.Strings.Unbounded,
don't they? You could view an unbounded string kind of as a list of
characters, eh? Maybe look at A.S.U for ideas about how it should look and
what sort of operations it should have?)

How is assignment handled here? If you don't inherit from Ada.Finalization
how do you make sure you copy the list rather than duplicate pointers to the
list? (Assuming the underlying implementation relies on pointers to list
elements.)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:1EyE7.10050$xS6.13527@www.newsranger.com...
>
> First off, I'd like to note for anyone who may have missed it, that any
Element
> passed in to be put on a list or taken off of one will be *copied*.
Pointers to
> elements will not be used.
>
> If List were limited private, then we'd have to get rid of all those "&"
> routines. My thinking was that Lisp-like functional list processing would
be
> desirable. You could indeed have aliasing problems, but only if your
Element
> type uses pointers. Having "&" avaliable also makes list operations
somewhat
> consistent with arrays, which also have "&".
>
> However, any use of those "&" routines will involve creating a copy of
every
> element (much like using "&" with arrays does). That would probably be too
> expensive in most cases, so perhaps it really isn't all that valuable. I'm
> curious how others feel about this.
>

Re: List container strawman

[Ted Dennison]

In article <9rue9f$j4t$1@nh.pace.co.uk>, Marin David Condic says...
>How is assignment handled here? If you don't inherit from Ada.Finalization
>how do you make sure you copy the list rather than duplicate pointers to the
>list? (Assuming the underlying implementation relies on pointers to list
>elements.)

Well, the honest answer is that I hadn't thought of that. :-(

I guess if the funcional stuff is going to remain in there, then it will have to
be a controlled type. That means that users won't be able to instantiate it from
within a subprogram (yuk!). If we *do* make it limited, then another issue I
just thought of is that we wouldn't be able to make lists of lists (we had
already decided that we won't allow limited list components). However, I can't
think of a good common use for lists of lists of the top of my head.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

If the List type is simply private, can it contain an element that is
Controlled? In other words, is this a problem that can be covered up with
just one more layer of indirection?

I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic
in its underlying implementation and it has to solve the problem of
assignment along the way. That either means a) the problem can be solved
from within the language or b) its done with smoke and mirrors behind the
scenes. I'm guessing that A is likely to be the case, so perhaps a solution
does exist?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:wVzE7.10194$xS6.14029@www.newsranger.com...
>
> I guess if the funcional stuff is going to remain in there, then it will
have to
> be a controlled type. That means that users won't be able to instantiate
it from
> within a subprogram (yuk!). If we *do* make it limited, then another issue
I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I
can't
> think of a good common use for lists of lists of the top of my head.
>

Re: List container strawman

[Jeffrey Carter]

Marin David Condic wrote:
> 
> If the List type is simply private, can it contain an element that is
> Controlled? In other words, is this a problem that can be covered up with
> just one more layer of indirection?

There's no problem with the actual type being Controlled if the formal
type is [limited] private. If there's anything about the actual type
that requires finalization we would hope the client would implement it
as a controlled type, since objects of this type are going to come and
go as items are added and removed from the structure.

> 
> I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic
> in its underlying implementation and it has to solve the problem of
> assignment along the way. That either means a) the problem can be solved
> from within the language or b) its done with smoke and mirrors behind the
> scenes. I'm guessing that A is likely to be the case, so perhaps a solution
> does exist?

Unbounded_String may be implemented as a controlled type. It's
implementation is not defined, so compiler writers may use any tricks
they think necessary, but you could write the implementation in plain
Ada.

Another place where some compiler writers use tricks is the interaction
between a random number Generator value and the Random function. The
generator holds the state data for the algorithm, which are supposed to
be updated when a number is generated. You can implement Generator as a
controlled type with a pointer to the state data, but again other tricks
are possible from within the compiler.

-- 
Jeffrey Carter

Re: List container strawman

[Matthew Heaney]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BE3235D.E292B890@boeing.com...
> Another place where some compiler writers use tricks is the interaction
> between a random number Generator value and the Random function. The
> generator holds the state data for the algorithm, which are supposed to
> be updated when a number is generated. You can implement Generator as a
> controlled type with a pointer to the state data, but again other tricks
> are possible from within the compiler.

Why would you need to implement type Generator as a Controlled type?
Generator state is allocated on the stack, so Finalization is not required.
Allocating state on the heap and using Controlled Finalization would be a
horribly inefficient way to implement that type.

No heap allocation or compiler magic is needed to implement Generator; just
use the Rosen Trick:

package P is
   type Generator is limited private;
   function Random (G : Generator) return Integer;
private
   type Handle_Type (G : access Generator) is null record;
   type Generator is limited record
      Handle : Handle_Type (G'Access);
      State : State_Type;  --whatever
   end record;
end P;

package body P is
   function Random (G : Generator) return Integer is
      State : State_Type renames G.Handle.G.all;
   begin
      -- modify State as necessary
      return X;
    end;
end P;

This is all perfectly legal.

Re: List container strawman

[Jeffrey Carter]

Matthew Heaney wrote:
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3BE3235D.E292B890@boeing.com...
> > Another place where some compiler writers use tricks is the interaction
> > between a random number Generator value and the Random function. The
> > generator holds the state data for the algorithm, which are supposed to
> > be updated when a number is generated. You can implement Generator as a
> > controlled type with a pointer to the state data, but again other tricks
> > are possible from within the compiler.
> 
> Why would you need to implement type Generator as a Controlled type?
> Generator state is allocated on the stack, so Finalization is not required.
> Allocating state on the heap and using Controlled Finalization would be a
> horribly inefficient way to implement that type.

The obvious way to modify an in parameter is to have it be an access
value and change what it points to. You would want this to be Controlled
so you could deallocate the storage when an object of the type goes out
of scope.

The GNAT implementation says

   --  The design of this spec is very awkward, as a result of Ada 95
not
   --  permitting in-out parameters for function formals (most naturally
   --  Generator values would be passed this way). In pure Ada 95, the
only
   --  solution is to use the heap and pointers, and, to avoid memory
leaks,
   --  controlled types.

> 
> No heap allocation or compiler magic is needed to implement Generator; just
> use the Rosen Trick:

Yes, that is a trick that can be used (although your example has a
couple of errors). Was it known before standardization? I somehow
suspect it would have been outlawed if it were.

GNAT uses

   type State is ...

   type Generator is limited record
      Gen_State : State;
   end record;

Following the above quote, they add

   --  This is awfully heavy, so what we do is to use
Unrestricted_Access to
   --  get a pointer to the state in the passed Generator. This works
because
   --  Generator is a limited type and will thus always be passed by
reference.

   type Pointer is access all State;

   function Random  (Gen : Generator) return Uniformly_Distributed is
      Genp : constant Pointer := Gen.Gen_State'Unrestricted_Access;

and then modify Genp.all. Since 'Unrestricted_Access is an
implementation-dependent attribute, I think this qualifies as a trick,
too. I wonder if there is some advantage to this trick over the Rosen
trick.

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail

Rosen Trick [List container strawman]

[Nick Roberts]

I've always felt that this whole charade is an academic Alice-in-Wonderland
adventure. The right solution, of course, is to use a procedure (with an
in-out parameter) instead of a function. Grrr.

PS: Why? Because functions should not have side-effects (in a language like
Ada). I don't care about expediencies that are to do with debugging,
profiling, auditing, and that sort of thing (where the effort of not using
functions would be silly), but where the main thrust of the logic has a side
effect, use a procedure! Good programming (in Ada) is not about what weird
and funny things you can do that will catch people by surpise (and so be
likely to cause bugs, or angst, or both).

PPS: I don't think allocating an RNG state block on the heap, rather than
the stack, is likely to have much effect on speed; surely the burden of
indirect access would be vastly outweighed by the burden of computation for
each number generation cycle? And why would using finalisation be
inefficient?

--
Nick Roberts

Re: Rosen Trick [List container strawman]

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9s230d$107b5a$2@ID-25716.news.dfncis.de>...

> PS: Why? Because functions should not have side-effects (in a language like
> Ada).

You present this as a kind of obvious ab initio fact, but
it is nothing of the kind.

Here are the facts:

Ada permits functions to have side effects, and does not
attempt to prohibit side effects in functions (an odd and
inconsistent exception is functions in protected types,
and that was indeed a major discussion point in the design)

There was some attept early on to consider trying to stop
functions from having side effects, and indeed I think one
published early version of Ada distinguished functions and
value returning procedures, or at least that was discussed.

But such attempts were firmly rejected, and the decision
was that there are situations where it makes perfectly good
sense for functions to have side effects, and an absolute
rule prohibiting them is in the same not-well-thought-out
category as absolute rules against use clauses, goto statements,
unchecked conversion, and various other very
useful features of Ada. Useful does not mean that they should be used
all the time, or misused, just that they
have some legitimate use.

Another important factor is that other languages agree with
Ada that functions should be allowed to have side effects.
In particular C takes this viewpoint, and side effects in
functions are common in C, including side effects in calls
to standard functions in the C library.

Now in Ada, the rule for functions is a bit odd:

  Side effects from access to global variables - permitted
  Side effects from modifying access type args - permitted
  Side effects from in out parameters - prohibited

I have never understood the rationale for this inconsistent
design. When I talk to someone like Tuck, who basically supports the
prohibition, it seems to come from a general
feeling that functions should not have side effects. OK,
but that's some other language than Ada, where functions
are permitted to have side effects.

Most annoyingly, the natural translation of a * arg in a
C function, e.g. *int, is to translate it to an IN OUT
parameter, but that is arbitrarily not allowed. It is of
course allowed to translate it to an access-to-int parameter, since
there is no restriction on the use of
such parameters for functions, even though they are obviously
logically equivalent from an expressive point
of view.

The trouble is that although in-out parameters and access-type-to-foo
parameters are equivalent from a logical
point of view, they are very different syntactically, and
we are left with the following unpleasant alternatives in
interfacing to C functions:

  1. Interface as procedures. This either requires a 
     wrapper or something like the Valued_Procedure
     interface available in GNAT. The trouble with 
     this is that the calls get really ugly. Yes, in
     the case where the result is just an error code
     it's acceptable, but that's by no means always
     the case.

  2. Interface using named access types. The calls are
     somewhat better here, but you get a plague of aliased
     variables appearing, and the access types need 
     defining which is messy.

  3. Use a wrapper with global variables for the missing
     parameters. But this is nasty anyway, and gets too
     far from the C form.

To me, the arguments for allowing IN OUT parameters, at
least for interfaced functions, are very strong, but
unfortunately, this is an argument that cannot be won.
There seem to be three kinds of people:

1. Those who are adamantly opposed to IN OUT parameters
on basically religeous (i.e. belief based) grounds without
very strong technical justification in many cases, or with
the technical justification being inconsistent with the
general permission for functions to have side effects in
Ada. This is a surprisingly large group.

2. Those who really don't like functions with side effects
much, but would tolerate IN OUT parameters if they had to,
but are certainly not going to fight for them, and would
vote no or abstain. I think I correctly label Tuck and the
design team in this second group, which is also fairly large.

3. Those who really find this restriction annoying, and have fought to
get it lifted. They are a large group, but
somewhat less than a working majority.

I don't see anything that would put group 3 in a position
to fix this annoying restriction in the near future, so it
to me is just a minor defect in the language that will stay
uncorrected, but we can live with it, it's not fatal, just
very annoying.

Side-Effects in Functions [Rosen Trick]

[Nick Roberts]

"Robert Dewar" <dewar@gnat.com> wrote in message
news:5ee5b646.0111040507.5ca7ea23@posting.google.com...
> "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:<9s230d$107b5a$2@ID-25716.news.dfncis.de>...
>
> > PS: Why? Because functions should not have side-effects (in a language
like
> > Ada).
>
> You present this as a kind of obvious ab initio fact, but
> it is nothing of the kind.

I was hoping that it would be obvious that I was putting this point in a
deliberately polemical style. I am merely stating my own strongly held
belief on this subject, based on perfectly good reasoning, as well as the
consensus of programming wisdom.

> Here are the facts:
> ...
> There was some attept early on to consider trying to stop
> functions from having side effects, and indeed I think one
> published early version of Ada distinguished functions and
> value returning procedures, or at least that was discussed.

I'm glad this didn't happen, because, as mentioned in my previous post,
there are occasions -- such as debugging, profiling, auditing -- when it is
useful for a function to have a side-effect, and forcing the programmer to
convert it to a procedure -- and thus all calls on it to procedure calls --
would be wholly unjustified.

> But such attempts were firmly rejected, and the decision
> was that there are situations where it makes perfectly good
> sense for functions to have side effects, and an absolute
> rule prohibiting them is in the same not-well-thought-out
> category as absolute rules against use clauses, goto statements,
> unchecked conversion, and various other very
> useful features of Ada. Useful does not mean that they should be used
> all the time, or misused, just that they have some legitimate use.

I agree there.

> Another important factor is that other languages agree with
> Ada that functions should be allowed to have side effects.
> In particular C takes this viewpoint, and side effects in
> functions are common in C, including side effects in calls
> to standard functions in the C library.

The fact that the C language permits something, or that C programmers do a
particular thing, is surely no recommendation that Ada programmers should do
the same!

> Now in Ada, the rule for functions is a bit odd:
>
>   Side effects from access to global variables - permitted
>   Side effects from modifying access type args - permitted
>   Side effects from in out parameters - prohibited

These rules may seem a little odd, but they pertain to what Ada allows
programmers to do, not what Ada programmers should do. My point was entirely
about what Ada programmers should do.

> I have never understood the rationale for this inconsistent
> design.

The rationale is simple and well-known Robert! Good grief, every Ada
textbook on the planet has an example of how side-effects in functions can
introduce subtle and pernicious bugs (especially on porting). Must I really
repeat these?

> Most annoyingly, the natural translation of a * arg in a
> C function, e.g. *int, is to translate it to an IN OUT
> parameter, but that is arbitrarily not allowed.

This isn't the most natural translation, and the prevention of the use of
in-out parameters in functions is not arbitrary, it was, as you said
earlier, carefully debated.

> It is of
> course allowed to translate it to an access-to-int parameter, since
> there is no restriction on the use of
> such parameters for functions, even though they are obviously
> logically equivalent from an expressive point of view.

They are not logically equivalent. The use of the access parameter implies
the (actual) object is aliased (kept in memory essentially all the time).
This may be something that C assumes for all its variables (clever compiler
deductions notwithstanding), but Ada does not, and rightly so.

> The trouble is that although in-out parameters and access-type-to-foo
> parameters are equivalent from a logical
> point of view, they are very different syntactically, and
> we are left with the following unpleasant alternatives in
> interfacing to C functions:
>
>   1. Interface as procedures. This either requires a
>      wrapper or something like the Valued_Procedure
>      interface available in GNAT. The trouble with
>      this is that the calls get really ugly. Yes, in
>      the case where the result is just an error code
>      it's acceptable, but that's by no means always
>      the case.
>
>   2. Interface using named access types. The calls are
>      somewhat better here, but you get a plague of aliased
>      variables appearing, and the access types need
>      defining which is messy.
>
>   3. Use a wrapper with global variables for the missing
>      parameters. But this is nasty anyway, and gets too
>      far from the C form.

To me, it is obvious that option 2 should be used. To describe the required
aliasing of variables as a 'plague' is rather an overstatement: it simply
means adding the word 'aliased' to the appropriate objects; that's not a
plague! It is absolutely right, since they must (at least in effect) be
aliased for the called C routine(s) to access them via a pointer.

> To me, the arguments for allowing IN OUT parameters, at
> least for interfaced functions, are very strong, but
> unfortunately, this is an argument that cannot be won.
> There seem to be three kinds of people:
>
> 1. Those who are adamantly opposed to IN OUT parameters
> on basically religeous (i.e. belief based) grounds without
> very strong technical justification in many cases, or with
> the technical justification being inconsistent with the
> general permission for functions to have side effects in
> Ada. This is a surprisingly large group.

Well, as I say above, there is indeed a very strong, very well documented,
and generally accepted technical justification for avoiding side-effects in
functions (which is the point I was originally making), and disallowing
in-out parameters in Ada functions seems to be be perfectly in tune with
this principle.

> ...

To sum up, I am amazed at Robert's opposition to what I have always
understood to be a very well established programming principle (in
procedural languages such as Ada). That principle is taught for very good
software engineering reasons. I said "Must I really repeat these?". If the
answer is simply "Yes.", then please just answer "Yes" and I will.

--
Nick Roberts

Re: Side-Effects in Functions [Rosen Trick]

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9s3tl3$111hco$1@ID-25716.news.dfncis.de>...
> I was hoping that it would be obvious that I was putting 
> this point in a
> deliberately polemical style. I am merely stating my own 
> strongly held
> belief on this subject, based on perfectly good 
> reasoning, as well as the
> consensus of programming wisdom.

No, this is by no means a consensus. Most procedural
languages, including Ada, allow functions to have side
effects. And on the narrower issue of allowing IN OUT
parameters in functions, there is nothing like a consensus
opposing this. Indeed my guess is that during the design
phase on Ada 95, if a show down had been insisted on, 
the side favoring IN OUT parameters would have (narrowly)
won, but it seemed inappropriate to force this change in
the absence of a consensus on the other side. So your
understanding of the consensus here is completely wrong.

> > Now in Ada, the rule for functions is a bit odd:
> >
> >   Side effects from access to global variables - permitted
> >   Side effects from modifying access type args - permitted
> >   Side effects from in out parameters - prohibited
> 
> These rules may seem a little odd, but they pertain to what Ada allows
> programmers to do, not what Ada programmers should do. My point was entirely
> about what Ada programmers should do.

Features in Ada are there to be used, anyone who announces
that some feature should never be used probably just does
not understand the issues. Of course they should not be
abused.

> The rationale is simple and well-known Robert! Good grief, every Ada
> textbook on the planet has an example of how side-effects in functions can
> introduce subtle and pernicious bugs (especially on porting). Must I really
> repeat these?

Please don't! Many people would say EXACTLY the same
about assignments, or global variables. Of course this
feature can be misused, as can many features. Forbidding
something because it can be misused is an absurd design
approach and one that fortunately Ada seldom indulges in.

> > Most annoyingly, the natural translation of a * arg in a
> > C function, e.g. *int, is to translate it to an IN OUT
> > parameter, but that is arbitrarily not allowed.
> 
> This isn't the most natural translation, and the prevention of the use of
> in-out parameters in functions is not arbitrary, it was, as you said
> earlier, carefully debated.

Actually the issue of IN OUT parameters was never carefully
debated. It was clear early on that it was one of these
religeous issues (note Nick's odd use of the phrase "strong
belief") which was not something that could be calmly debated (your
"good grief" shows this nicely -- why people
get so excercised over this issue is a puzzle to me).


> To me, it is obvious that option 2 should be used. To describe the required
> aliasing of variables as a 'plague' is rather an overstatement: it simply
> means adding the word 'aliased' to the appropriate objects; that's not a
> plague! It is absolutely right, since they must (at least in effect) be
> aliased for the called C routine(s) to access them via a pointer.

Most people feel that being forced to add aliased keywords
all over the place, just because of odd interfacing requirements for C
functions, is unfortunate. If you find
it perfectly fine to have aliased keywords around, fine,
but you obviously don't have the alergy to aliasing that
many people have. It is not accidental that aliased is not
the default.


> To sum up, I am amazed at Robert's opposition to what I
> have always understood to be a very well established 
> programming principle (in procedural languages such as 
> Ada).

No wonder if you are amazed if you think this is a "very
well established programming principle". That's just wrong.
As I noted earlier, nearly all procedural languages DO
allow side effects in functions.

And of course Ada does too (allow side effects in functions), but has
the odd attitude that side effects
are only OK if they are not announced in the spec. 

Consider the following:

   function f return integer;
   --  Increments the global variable Q and returns the
   --  incremented value.

   function f (Q : in out integer) return integer;
   --  Increments its argument and returns the incremented
   --  value.

I find it odd that Ada allows the first and disallows the
second, and many others would agree with me. Nick, no one
will try to convince you that you are wrong here, because
it is a waste of time, but you should learn that you are
quite wrong if you think your viewpoint somehow represents
a general consensus. I and many other experts in programming languages
in general, and Ada in particular,
disagree with you. The fact is there is no consensus on
either side of this issue.

Oddly, the feeling that goto statements should never be
used has much *stronger* support than the feeling that
IN OUT parameters should not be allowed in functions, yet
Ada does permit goto statements. I think the actual situation is that
this is one of these cases where the
designers get to decide, since there is no consensus.
JDI accepted gotos, but felt that functions should have
no side effects whatever. That was untenable, and he was
argued out of this extreme position, with the result that
we ended up with a rather odd compromise. Tuck is also
somewhat (though not fanatically like you) opposed to IN
OUT parameters for functions, so was not about to decree
that they should go in.

> That principle is taught for very good
> software engineering reasons. I said "Must I really
> repeat these?".

If you have been taught that functions should never ever
have side effects, you have been taught by a fanatic. Such
fanaticism is almost never helpful.

Re: Side-Effects in Functions [Rosen Trick]

[pete]

 
functions, in the mathemtical sense, do not accept an IN OUT paramters,
and do not have side effects.

y=f(x), x here can never be modified by the function f().

so, Ada function is more like a math function.

Re: Side-Effects in Functions [Rosen Trick]

[Dmitry A. Kazakov]

On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com>
wrote:

>functions, in the mathemtical sense, do not accept an IN OUT paramters,
>and do not have side effects.
>
>y=f(x), x here can never be modified by the function f().
>
>so, Ada function is more like a math function.

No function in a programming language may have no side effects. One
could say that there are side effects which are of no interest, but no
more than that.

The discussion about in out parameters is proved to be evergreen
(:-)). But what I presonally cannot understand is why not to allow
PROCEDUREs having a result, i.e.

procedure Find (Folder : in out Table) return Table_Token;

procedure GetNext  (Item_List : in out Iterator) return Element;

etc.

Regards,
Dmitry Kazakov

Re: Side-Effects in Functions [Rosen Trick]

[pete]

In article <3be666fe.6426140@News.CIS.DFN.DE>, dmitry@elros.cbb-automation.de
says...
>
 
>But what I presonally cannot understand is why not to allow
>PROCEDUREs having a result, i.e.
>
>procedure Find (Folder : in out Table) return Table_Token;
>
>procedure GetNext  (Item_List : in out Iterator) return Element;
>
 
this is a joke, right?

Re: Side-Effects in Functions [Rosen Trick]

[Dmitry A. Kazakov]

On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com>
wrote:

>In article <3be666fe.6426140@News.CIS.DFN.DE>, dmitry@elros.cbb-automation.de
>says...
>>
> 
>>But what I presonally cannot understand is why not to allow
>>PROCEDUREs having a result, i.e.
>>
>>procedure Find (Folder : in out Table) return Table_Token;
>>
>>procedure GetNext  (Item_List : in out Iterator) return Element;
>>
> 
>this is a joke, right?

Nope. It is exactly what is required, namely a subroutine having a
distinguished parameter called result and allowed to modify its
arguments. It is not a function (in Ada sense), thus it is a
procedure. Compare:

procedure Find (Folder : in out Table) return Table_Token;

with

procedure Find (Folder : in out Table; Result : out Table_Token);

The difference between them is rather syntactical. Semantically they
do same: search table, cash internally the result of search (thus in
out for the fist argument), return the found element.

Regards,
Dmitry Kazakov

Re: Side-Effects in Functions [Rosen Trick]

[Preben Randhol]

On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote:
> On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com>
> wrote:
> 
> procedure Find (Folder : in out Table) return Table_Token;
> 
> with
> 
> procedure Find (Folder : in out Table; Result : out Table_Token);
> 
> The difference between them is rather syntactical. Semantically they

Yes and I don't understand why you want it. What if you expect to change
two wariables in the procedure like:

procedure Find (Folder : in out Table; Result : out Table_Token; 
                Unique : out Boolean);

to do it like: 

procedure Find (Folder : in out Table; Unique : out Boolean) return Table_Token;

looks a bit messy I think.

What is the difference between a function with in out and a procedure
with a return value? It amounts to the same thing I think.

Preben

Re: Side-Effects in Functions [Rosen Trick]

[Ted Dennison]

In article <slrn9udfg3.4dc.randhol+abuse@kiuk0156.chembio.ntnu.no>, Preben
Randhol says...
>
>What is the difference between a function with in out and a procedure
>with a return value? It amounts to the same thing I think.

I think it would actually give functions *back* their purity. It would allow
functions to continue to be used for non-side-effect functions, but give folks
who would otherwise have to resort to pointers, unchecked_access tricks, or the
Rosen trick in a function a language-defined way to achieve the result they
require. When reading a spec, "function" would be a bit stronger of a statement
about what is going on. Plus folks who feel religously about it could just
outlaw value-returning procedures like they always have for "goto".

However, I think about %90 of this issue would go away if some other method of
modifying "bookkeeping" fields in private types was provided.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Side-Effects in Functions [Rosen Trick]

[Dmitry A. Kazakov]

On Mon, 5 Nov 2001 15:21:13 +0000 (UTC), Preben Randhol
<randhol+abuse@pvv.org> wrote:

>On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote:
>> On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com>
>> wrote:
>> 
>> procedure Find (Folder : in out Table) return Table_Token;
>> 
>> with
>> 
>> procedure Find (Folder : in out Table; Result : out Table_Token);
>> 
>> The difference between them is rather syntactical. Semantically they
>
>Yes and I don't understand why you want it. What if you expect to change
>two wariables in the procedure like:
>
>procedure Find (Folder : in out Table; Result : out Table_Token; 
>                Unique : out Boolean);

Well, multiple results is another story. Some languages have return
tuples, but I am not convinced that Ada really needs it.

Then your argument could be well applied to pure functions as well.
Why not to replace them by procedures with an extra out parameter? A
bit more work with temporal variables, unability to initialize
constants, but generally no problem (:-))

>to do it like: 
>
>procedure Find (Folder : in out Table; Unique : out Boolean) return Table_Token;
>
>looks a bit messy I think.

Yes. But I still have a choice to make it:

procedure Find (Folder : in out Table; Result : out Table_Token; 
                Unique : out Boolean);

It is of course not so that any out parameter has to be declared as
the result. All we need is an impure function. As Robert have pointed,
it is ridiculous to have an ability to write impure functions and have
no right to manifest them as such (openly using in out parameters). If
the word "function" makes people so sensitive, let's use "procedure"
instead!

>What is the difference between a function with in out and a procedure
>with a return value? It amounts to the same thing I think.

There is no difference other than functions with in out parameters are
unacceptable for some part of Ada community, which is enough powerful
to ban them forever (:-)).

P.S. I do not belong to this part.

Regards,
Dmitry Kazakov

Re: Side-Effects in Functions [Rosen Trick]

[Warren W. Gay VE3WWG]

Dmitry A. Kazakov wrote:

> On Mon, 5 Nov 2001 15:21:13 +0000 (UTC), Preben Randhol
> <randhol+abuse@pvv.org> wrote:
>>On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote:
>>>On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com>
>>>wrote:
...
> Yes. But I still have a choice to make it:
> 
> procedure Find (Folder : in out Table; Result : out Table_Token; 
>                 Unique : out Boolean);
> 
> It is of course not so that any out parameter has to be declared as
> the result. All we need is an impure function. As Robert have pointed,
> it is ridiculous to have an ability to write impure functions and have
> no right to manifest them as such (openly using in out parameters). If
> the word "function" makes people so sensitive, let's use "procedure"
> instead!
> 
>>What is the difference between a function with in out and a procedure
>>with a return value? It amounts to the same thing I think.
> 
> There is no difference other than functions with in out parameters are
> unacceptable for some part of Ada community, which is enough powerful
> to ban them forever (:-)).
> 
> P.S. I do not belong to this part.
> 
> Regards,
> Dmitry Kazakov


I think one of the issues at stake here is that Ada was meant to be

easy to read. If you allow procedures to return values, then it is
no longer a valid assumption that what looks like a function call,
does not produce side effects (ie. you cannot assume that the arguments
are not modified, without looking at the declaration).


To pull it off, you'd have to make some sort of syntactical difference

in procedure-function calls, to maintain the status quo for functions.
In case I am not explaining this clear enough, the following example
might help:

declare
    Arg : Boolean;		-- Argument
    R   : Boolean;		-- Result
begin

    R := My_Function(Arg);	-- Assumed that Arg is not modified
    R := My_Proc_Function[Arg];	-- A procedure returning.. identified by []


I am not suggesting the [] make a good syntax here, but you'd have
to do something like this to maintain the distinction that Functions
already enjoy within Ada.
-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Side-Effects in Functions [Rosen Trick]

[Preben Randhol]

On Mon, 05 Nov 2001 17:42:14 GMT, Warren W. Gay VE3WWG wrote:
> 
> I think one of the issues at stake here is that Ada was meant to be
> 
> easy to read. If you allow procedures to return values, then it is
> no longer a valid assumption that what looks like a function call,
> does not produce side effects (ie. you cannot assume that the arguments
> are not modified, without looking at the declaration).

Not only that. If one allow return values in procedures one cannot know
that the procedure won't return a value unless one look at the
definition. It would make things a mess and I think it clearly would
break down readability. 

>     R := My_Function(Arg);	-- Assumed that Arg is not modified
>     R := My_Proc_Function[Arg];	-- A procedure returning.. identified by []
> 
> 
> I am not suggesting the [] make a good syntax here, but you'd have
> to do something like this to maintain the distinction that Functions
> already enjoy within Ada.

Ouch! Very bad (I think) as you then will introduce:

1. Very confusing syntax for beginners
2. Harder to "read" the difference => Lower readability
3. More easy to write wrong code. You may type [] and mean (). 
4. How should one solve dispatching?

I don't understand the need for neither function with in out nor
procedure with return values.

Preben Randhol
-- 
Please, stop bombing civilians in Afghanistan. One cannot write off
killing innocent children and other civilians as "collateral damage".
A civilian is a civilian whether he or she is American or from another
country in the world.           http://web.amnesty.org/11september.htm

Re: Side-Effects in Functions [Rosen Trick]

[Dmitry A. Kazakov]

On Mon, 05 Nov 2001 17:42:14 GMT, "Warren W. Gay VE3WWG"
<ve3wwg@home.com> wrote:

>I think one of the issues at stake here is that Ada was meant to be
>
>easy to read. If you allow procedures to return values, then it is
>no longer a valid assumption that what looks like a function call,
>does not produce side effects (ie. you cannot assume that the arguments
>are not modified, without looking at the declaration).

Why something that looks like a call returning a result should have no
side effects? There are two completely different and independent
properties of a subroutine:

a) It does not modify arguments
b) It returns a result

What we have in Ada is:

subroutine is a function => a & b
subroutine is a procedure => not b

Now the question, why on Earth b=>a?

>To pull it off, you'd have to make some sort of syntactical difference
>
>in procedure-function calls, to maintain the status quo for functions.
>In case I am not explaining this clear enough, the following example
>might help:
>
>declare
>    Arg : Boolean;		-- Argument
>    R   : Boolean;		-- Result
>begin
>
>    R := My_Function(Arg);	-- Assumed that Arg is not modified
>    R := My_Proc_Function[Arg];	-- A procedure returning.. identified by []
>
>I am not suggesting the [] make a good syntax here, but you'd have
>to do something like this to maintain the distinction that Functions
>already enjoy within Ada.

Seems like Hungarian notation reincarnation. It is IMO a wrong idea.
All that a user should know about a subroutine is its contract. The
parameter mode is a part of the contract. When a user do not want (in
your example) Arg to be modified, he/she must simply say it by
declaring Arg constant, which would make the second call illegal.

Regards,
Dmitry Kazakov

Re: Side-Effects in Functions [Rosen Trick]

[tgingold]

In article <3be79e7c.551796@News.CIS.DFN.DE>, Dmitry A. Kazakov wrote:
> On Mon, 05 Nov 2001 17:42:14 GMT, "Warren W. Gay VE3WWG"
><ve3wwg@home.com> wrote:
> 
>>I think one of the issues at stake here is that Ada was meant to be
>>
>>easy to read. If you allow procedures to return values, then it is
>>no longer a valid assumption that what looks like a function call,
>>does not produce side effects (ie. you cannot assume that the arguments
>>are not modified, without looking at the declaration).
Just for your information, VHDL-93 has PURE and IMPURE keyword.  Such a
declaration:
  pure function sum (a,b : integer) return integer;
means that SUM has no side effects (and therefore is expected to return
the same result when the set of argument is the same).
However, INOUT and OUT mode are not allowed in IMPURE FUNCTION.

Note also that return a value is *VERY* different from an OUT parameter, since
the return type can be unconstrained.

Tristan.

Re: Side-Effects in Functions [Rosen Trick]

[Nick Roberts]

"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message
news:3be666fe.6426140@News.CIS.DFN.DE...
> On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com>
> wrote:
>
> >functions, in the mathemtical sense, do not accept an IN OUT paramters,
> >and do not have side effects.
> >
> >y=f(x), x here can never be modified by the function f().
> >
> >so, Ada function is more like a math function.

From a pedagogical point of view, care needs to be taken not to give the
impression that a function in a procedural programming language (most
programming languages, really) is the same thing as a mathematical function.
Clearly it isn't: a mathematical function is a kind of relation called a
'bijection' (and is nowadays specifically defined as such, I think); a
programming function is really just an encapsulated computation.

Nevertheless, because a great many (practically useful) computations are, in
fact, essentially to work out the mapping represented by a mathematical
function from one value to another, it has become idiomatic to call these
computations functions. Classic examples include such functions as sin, cos,
and tan. Since the computations involve no side-effects, they neatly fit the
'no side-effects' model for programming functions.

> No function in a programming language may have no side effects. One
> could say that there are side effects which are of no interest, but no
> more than that.

I think, perhaps, that depends on precisely how you define a side-effect. If
you include modification of registers or memory as side-effects, then it's
true. However, we are only interested in side-effects in which we are
interested!

> The discussion about in out parameters is proved to be evergreen
> (:-)). But what I presonally cannot understand is why not to allow
> PROCEDUREs having a result, i.e.
>
> procedure Find (Folder : in out Table) return Table_Token;
>
> procedure GetNext  (Item_List : in out Iterator) return Element;

It would be pointless to have value-returning procedures in Ada. The reason
why is because procedures of this kind would suffer from precisely the same
dangers as functions (and would therefore be of no benefit over functions).

I'm going to spell out the problems with side-effects in functions, so that
(hopefully) everyone will be aware of them.

Ada (like many procedural languages) permits compilers to evaluate the
arguments of a function call in any order it chooses. (Obviously we are
talking about a functions with more than one parameter here.) The arguments
to this function call could be other function calls (nested within). For
example:

   A := B(C(E),D(E));

B, C, and D are all functions. First, the compiler will compile code to
evaluate E, then it will compile code to evaluate (call) C and D, and then
finally code that evaluates (calls) B, passing in the results from C and D.
The code calling C may come before or after the code calling D: it is the
choice of the compiler.

Now, suppose B, C, and D all have a side-effect when called: they print
their name onto a log file. The result on the log file of compiling and
executing this line of code with one compiler could be "C D B", but with
another compiler it could be "D C B". You have the self-same program,
compiled on two perfectly correct and compliant compilers, doing two
different things.

The two different behaviours may seem innocuous in the above example, but
consider this example, adapted from a real-life situation:

   Header := Decode(Data(1..4)) & Decode(Data(5..8));

The Decode function was really a pseudo-random number generator, but it used
the values it generated to decode an encrypted message. It used a global
variable for its state, which had to be seeded with the correct encryption
key; its side-effect was to update this state. Each 'chunk' that it decoded
had to be 4 bytes long.

The header of a certain message format was 8 bytes long, so we passed it
into Decode in two 4-byte chunks, as shown. This code worked fine for us,
but half-way through the project we changed compilers, and suddenly it
stopped working. Nobody had altered the code. Recriminations flew. Can you
see what had happened?

Answer: the first compiler evaluated Decode(Data(1..4)) first, and
Decode(Data(5..8)) second. So the first decryption value generated (at that
point in the program) by Decode was used on Data(1..4) first, and the second
on Data(5..8); the second compiler did it the other way around (as it was
perfectly entitled to do, since the two calls to Decode are the two
arguments of a call to "&").

If we had declared Decode as a procedure instead, and then written:

   Decode(Data(1..4),Header(1..4));
   Decode(Data(5..8),Header(5..8));

this bizarre and mystifying problem would never had occurred (and a certain
blameless manager -- not myself, I was a junior at the time -- would
probably not had been sacked).

Side-effects can be programmed into functions quite safely, if you know what
you're doing. As a rule of thumb, either: (a) diligently ensure that the
side-effect can't possibly cause a (significant) problem due to an
'order-of-evaluation dependency', or (b) remove the side-effect.

Typically, the easiest way to remove a side-effect from a function is to
turn the function into a procedure.

I hope I've convinced any doubters, at this point. If you're still not sure,
just trust your uncle Nicky, eh?

--
Nick Roberts

Re: Side-Effects in Functions [Rosen Trick]

[Dmitry A. Kazakov]

On Tue, 6 Nov 2001 00:10:31 -0000, "Nick Roberts"
<nickroberts@adaos.worldonline.co.uk> wrote:

>"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message
>news:3be666fe.6426140@News.CIS.DFN.DE...
>> On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com>
>> wrote:
>>
>> >functions, in the mathemtical sense, do not accept an IN OUT paramters,
>> >and do not have side effects.
>> >
>> >y=f(x), x here can never be modified by the function f().
>> >
>> >so, Ada function is more like a math function.
>
>From a pedagogical point of view, care needs to be taken not to give the
>impression that a function in a procedural programming language (most
>programming languages, really) is the same thing as a mathematical function.
>Clearly it isn't: a mathematical function is a kind of relation called a
>'bijection' (and is nowadays specifically defined as such, I think); a
>programming function is really just an encapsulated computation.
>
>Nevertheless, because a great many (practically useful) computations are, in
>fact, essentially to work out the mapping represented by a mathematical
>function from one value to another, it has become idiomatic to call these
>computations functions. Classic examples include such functions as sin, cos,
>and tan. Since the computations involve no side-effects, they neatly fit the
>'no side-effects' model for programming functions.
>
>> No function in a programming language may have no side effects. One
>> could say that there are side effects which are of no interest, but no
>> more than that.
>
>I think, perhaps, that depends on precisely how you define a side-effect. If
>you include modification of registers or memory as side-effects, then it's
>true. However, we are only interested in side-effects in which we are
>interested!

It is a great problem to give a careful definition of side-effects.
Ada follows rather a pragmatic view, side-effects are ones of
arguments. Unfortunately this definition is too weak for correctness
checks. Though I doubt that a correct definition exists. Just consider
an assertion that includes absolute time!

>> The discussion about in out parameters is proved to be evergreen
>> (:-)). But what I presonally cannot understand is why not to allow
>> PROCEDUREs having a result, i.e.
>>
>> procedure Find (Folder : in out Table) return Table_Token;
>>
>> procedure GetNext  (Item_List : in out Iterator) return Element;
>
>It would be pointless to have value-returning procedures in Ada. The reason
>why is because procedures of this kind would suffer from precisely the same
>dangers as functions (and would therefore be of no benefit over functions).
>
>I'm going to spell out the problems with side-effects in functions, so that
>(hopefully) everyone will be aware of them.
>
>Ada (like many procedural languages) permits compilers to evaluate the
>arguments of a function call in any order it chooses. (Obviously we are
>talking about a functions with more than one parameter here.) The arguments
>to this function call could be other function calls (nested within). For
>example:
>
>   A := B(C(E),D(E));
>
>B, C, and D are all functions. First, the compiler will compile code to
>evaluate E, then it will compile code to evaluate (call) C and D, and then
>finally code that evaluates (calls) B, passing in the results from C and D.
>The code calling C may come before or after the code calling D: it is the
>choice of the compiler.
>
>Now, suppose B, C, and D all have a side-effect when called: they print
>their name onto a log file. The result on the log file of compiling and
>executing this line of code with one compiler could be "C D B", but with
>another compiler it could be "D C B". You have the self-same program,
>compiled on two perfectly correct and compliant compilers, doing two
>different things.
>
>The two different behaviours may seem innocuous in the above example, but
>consider this example, adapted from a real-life situation:
>
>   Header := Decode(Data(1..4)) & Decode(Data(5..8));
>
>The Decode function was really a pseudo-random number generator, but it used
>the values it generated to decode an encrypted message. It used a global
>variable for its state, which had to be seeded with the correct encryption
>key; its side-effect was to update this state. Each 'chunk' that it decoded
>had to be 4 bytes long.
>
>The header of a certain message format was 8 bytes long, so we passed it
>into Decode in two 4-byte chunks, as shown. This code worked fine for us,
>but half-way through the project we changed compilers, and suddenly it
>stopped working. Nobody had altered the code. Recriminations flew. Can you
>see what had happened?
>
>Answer: the first compiler evaluated Decode(Data(1..4)) first, and
>Decode(Data(5..8)) second. So the first decryption value generated (at that
>point in the program) by Decode was used on Data(1..4) first, and the second
>on Data(5..8); the second compiler did it the other way around (as it was
>perfectly entitled to do, since the two calls to Decode are the two
>arguments of a call to "&").
>
>If we had declared Decode as a procedure instead, and then written:
>
>   Decode(Data(1..4),Header(1..4));
>   Decode(Data(5..8),Header(5..8));
>
>this bizarre and mystifying problem would never had occurred (and a certain
>blameless manager -- not myself, I was a junior at the time -- would
>probably not had been sacked).
>
>Side-effects can be programmed into functions quite safely, if you know what
>you're doing. As a rule of thumb, either: (a) diligently ensure that the
>side-effect can't possibly cause a (significant) problem due to an
>'order-of-evaluation dependency', or (b) remove the side-effect.
>
>Typically, the easiest way to remove a side-effect from a function is to
>turn the function into a procedure.
>
>I hope I've convinced any doubters, at this point. If you're still not sure,
>just trust your uncle Nicky, eh?

The above is of course correct. Perhaps everybody enjoyed things like
that at least once [lucky ones did it several times (:-))] 

Yet it proves nothing more than if you have side-effects then, well,
there are side-effects.

Side-effects are bad, dangerous, nasty,... but sometimes necessary.
Then, can Ada's functions prevent users from writting things like
above? The answer is no.

P.S. A comment about computation order. I am not sure, but maybe it
would be worth to think about introducing lazy parameters (Algol's by
name). Ada already has them hard-wired in "and then" and "or else".
The order lazy parameters are evaluated is obviously defined by the
implementation of the subroutine, thus the above problems will
disappear, or better to say, become the responsibility of the
implementation. In your example "&" should have the second parameter
lazy, so 

    Decode(Data(1..4)) & Decode(Data(5..8));

would  mean: evaluate Decode(Data(1..4)); call "&", which internally
calls Decode(Data(5..8)).

Regards,
Dmitry Kazakov

Lazy Evaluation [Side-Effects in Functions]

[Nick Roberts]

"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message
news:3be7a31d.1736453@News.CIS.DFN.DE...
above? The answer is no.
> ...
> P.S. A comment about computation order. I am not sure, but maybe it
> would be worth to think about introducing lazy parameters (Algol's by
> name). Ada already has them hard-wired in "and then" and "or else".
> The order lazy parameters are evaluated is obviously defined by the
> implementation of the subroutine, thus the above problems will
> disappear, or better to say, become the responsibility of the
> implementation. In your example "&" should have the second parameter
> lazy, so
>
>     Decode(Data(1..4)) & Decode(Data(5..8));
>
> would  mean: evaluate Decode(Data(1..4)); call "&", which internally
> calls Decode(Data(5..8)).

Briefly, the combination of lazy evaluation and side-effects, as such, would
be rather like the combination of a keg of TNT and a blowtorch.

The problem of side-effects in Ada would be largely solved by fixing the
order in which arguments are evaluated (e.g. strictly in the order they are
declared) for all functions. But this would be a pity in that it would
significantly hamper many compilers' efforts to optimise a lot of ordinary
code.

Lazy evaluation is an interesting idea. How about:

   function Sin (X: delay in Float) return Float;

where the 'delay' means that what is passed into Sin is an access value to a
temporary routine (X'Computation) that computes the required value of X. In
the body of Sin, a flag X'Computed is set False, and any reference to X
either: if X'Computed is False, causes a call to the temporary routine,
places the result into a temporary store for X, and sets X'Computed to True;
if X'Computed is True, retrieves the value of X from its temporary store.
Hey presto! Lazy evaluation. "and then" and "or else" could become first
class citizens.

The access value X'Computation would be subject to the same accessibility
rules as any other access (-to-subprogram) value. This business is, I guess,
closely related to that of lambdas etc.

I not actually saying that I like this idea, by the way, just that it's
intriguing.

--
Nick Roberts

Re: Lazy Evaluation [Side-Effects in Functions]

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote 

> Briefly, the combination of lazy evaluation 
> and side-effects, as such, would
> be rather like the combination of a keg of TNT and a 
> blowtorch.

Well yes, of course this is a text book answer, but in
fact we are not talking about lazy evaluation here, but
rather call by name (referring to call by name as lazy
evaluation is a recipe for confusion).

Of course there is no particular conflict between side
effects and call by name, as anyone who has programmed
in Algol-60 extensively is perfectly aware.

Re: Lazy Evaluation [Side-Effects in Functions]

[Darren New]

Robert Dewar wrote:
> Of course there is no particular conflict between side
> effects and call by name, as anyone who has programmed
> in Algol-60 extensively is perfectly aware.

Uh, unless you do something like
  Swap(A(I), I)
(where A is an array, of course)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: Lazy Evaluation [Side-Effects in Functions]

[Robert Dewar]

Darren New <dnew@san.rr.com> wrote in message news:<3BE8BBC2.A8563DBD@san.rr.com>...
> Robert Dewar wrote:
> > Of course there is no particular conflict between side
> > effects and call by name, as anyone who has programmed
> > in Algol-60 extensively is perfectly aware.
> 
> Uh, unless you do something like
>   Swap(A(I), I)
> (where A is an array, of course)

Well yes, we all know Algol-60! (or at least I hope any
serious student of programming languages does). But there
is no special problem here. In Algol-60, the effect will be canonical,
depending on the exact order of statements in the body. Sure, it might
not do what the programmer expects
in this case, but it will do EXACTLY what the programmer
programmed. No language can avoid this discrepancy in
all cases.

Are you arguing that in practice call-by-name is troublesome for this
reason? I think that's a bogus
argument. I certainly never found it to be the case
in my Algol-60 programming days, how about you?

Note that in Ada, simple out parameters generate similar
concerns, except that the result is *not* canonical, if
you do

   x (m.m)

when x has two out parameters, the order in which things
get assigned is undefined in Ada.

Re: Lazy Evaluation [Side-Effects in Functions]

[Florian Weimer]

dewar@gnat.com (Robert Dewar) writes:

>> Uh, unless you do something like
>>   Swap(A(I), I)
>> (where A is an array, of course)
>
> Well yes, we all know Algol-60! (or at least I hope any
> serious student of programming languages does). But there
> is no special problem here. In Algol-60, the effect will be canonical,
> depending on the exact order of statements in the body.

Even if you use two temporary variables instead of a single one (which
is more usual, but in this case, the implementation hardly reflects
the symmetry of the operation)?

Re: Lazy Evaluation [Side-Effects in Functions]

[Jean-Marc Bourguet]

Florian Weimer <fw@deneb.enyo.de> writes:

> dewar@gnat.com (Robert Dewar) writes:
> 
> >> Uh, unless you do something like
> >>   Swap(A(I), I)
> >> (where A is an array, of course)
> >
> > Well yes, we all know Algol-60! (or at least I hope any
> > serious student of programming languages does). But there
> > is no special problem here. In Algol-60, the effect will be canonical,
> > depending on the exact order of statements in the body.
> 
> Even if you use two temporary variables instead of a single one (which
> is more usual, but in this case, the implementation hardly reflects
> the symmetry of the operation)?

Swap(I, A(I))

-- 
Jean-Marc

Re: Lazy Evaluation [Side-Effects in Functions]

[Ted Dennison]

In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar
says...
>Well yes, we all know Algol-60! (or at least I hope any
>serious student of programming languages does). But there

I have to say I don't, and unless there's a free PC implmentation floating
around somewhere, that's not liable to change. I may have learned some stuff
about it indirectly, but I won't say I "know" a language unless I've used it at
least a little.

So it seems you permanently restricting the set of "serious students of
programming languages" to folks who were around when Algol-60 compilers were
commonly available.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Lazy Evaluation [Side-Effects in Functions]

[M. A. Alves]

On Fri, 9 Nov 2001, Ted Dennison wrote:
> In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar
> says...
> >Well yes, we all know Algol-60! (or at least I hope any
> >serious student of programming languages does). But there
>
> I have to say I don't, and unless there's a free PC implmentation floating
> around somewhere, that's not liable to change. I may have learned some stuff
> about it indirectly, but I won't say I "know" a language unless I've used it at
> least a little.
>
> So it seems you permanently restricting the set of "serious students of
> programming languages" to folks who were around when Algol-60 compilers were
> commonly available.

Yes. Well, I am sure Dewar was not expecting such _practical_ knowledge of
Algol from all such students ;-)

-- 
   ,
 M A R I O   data miner, LIACC, room 221   tel 351+226078830, ext 121
 A M A D O   Rua Campo Alegre, 823         fax 351+226003654
 A L V E S   P-4150 PORTO, Portugal        mob 351+939354002

Re: Lazy Evaluation [Side-Effects in Functions]

[Georg Bauhaus]

Ted Dennison <dennison@telepath.com> wrote:
: In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar
: says...
: 
: there's a free PC implmentation floating
: around somewhere,


http://packages.debian.org/stable/interpreters/nase-a60.html

georg

Re: Lazy Evaluation [Side-Effects in Functions]

[Harri J Haataja]

Georg Bauhaus wrote:
>Ted Dennison <dennison@telepath.com> wrote:
>: In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar
>: says...
>: 
>: there's a free PC implmentation floating
>: around somewhere,
>
>http://packages.debian.org/stable/interpreters/nase-a60.html

$ grep MAST /export/pkgsrc/lang/a60/Makefile 
MASTER_SITES=	ftp://ftp.ibr.cs.tu-bs.de/pub/local/algol60/

The real address might be that.

-- 
Seagoon: Will my aeroplane need a hangar?
Crun:    It'd lose its shape hanging on a nail, you know.
	-- T.A.Milligan & L.Stephens 10 Jan 1957

Re: Lazy Evaluation [Side-Effects in Functions]

[Dmitry A. Kazakov]

On Tue, 6 Nov 2001 16:18:12 -0000, "Nick Roberts"
<nickroberts@adaos.worldonline.co.uk> wrote:

>"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message
>news:3be7a31d.1736453@News.CIS.DFN.DE...
>above? The answer is no.
>> ...
>> P.S. A comment about computation order. I am not sure, but maybe it
>> would be worth to think about introducing lazy parameters (Algol's by
>> name). Ada already has them hard-wired in "and then" and "or else".
>> The order lazy parameters are evaluated is obviously defined by the
>> implementation of the subroutine, thus the above problems will
>> disappear, or better to say, become the responsibility of the
>> implementation. In your example "&" should have the second parameter
>> lazy, so
>>
>>     Decode(Data(1..4)) & Decode(Data(5..8));
>>
>> would  mean: evaluate Decode(Data(1..4)); call "&", which internally
>> calls Decode(Data(5..8)).
>
>Briefly, the combination of lazy evaluation and side-effects, as such, would
>be rather like the combination of a keg of TNT and a blowtorch.
>
>The problem of side-effects in Ada would be largely solved by fixing the
>order in which arguments are evaluated (e.g. strictly in the order they are
>declared) for all functions. But this would be a pity in that it would
>significantly hamper many compilers' efforts to optimise a lot of ordinary
>code.

Yes. Then fixing the order does not solve another problem of
side-effects: when same objects are visible through different
arguments. The problem is of course in-out parameters per se. To the
list of their "crimes": LSP violation by generalization or
specialization; interesting effects in by-value vs. by-reference
parameter passing etc.

>Lazy evaluation is an interesting idea. How about:
>
>   function Sin (X: delay in Float) return Float;
>
>where the 'delay' means that what is passed into Sin is an access value to a
>temporary routine (X'Computation) that computes the required value of X. In
>the body of Sin, a flag X'Computed is set False, and any reference to X
>either: if X'Computed is False, causes a call to the temporary routine,
>places the result into a temporary store for X, and sets X'Computed to True;
>if X'Computed is True, retrieves the value of X from its temporary store.
>Hey presto! Lazy evaluation. "and then" and "or else" could become first
>class citizens.

Something like this. Maybe pragma Volatile (X) should ensure that X is
computed each time it is accessed. Otherwise, X is computed only once.

Then (a crazy idea), it would be nice to have an ability for a lazy
parameter to evaluate discriminants (and type tags) separately from
the value. I do not know whether it possible, but it could solve the
"problem of measurement units". The type of dimensioned values will
have a discriminant specifying the unit of measure. Being static (in
most cases) it can be evaluated statically (for inlined subroutines),
thus units checks can be efficiently removed by the compiler.

>The access value X'Computation would be subject to the same accessibility
>rules as any other access (-to-subprogram) value. This business is, I guess,
>closely related to that of lambdas etc.
>
>I not actually saying that I like this idea, by the way, just that it's
>intriguing.

It would be a dangerous stuff in right hands (:-)). Then I think to
get pragma Inlined working efficiently for subroutines with lazy
parameters would be not very easy.

Regards,
Dmitry Kazakov

Re: Side-Effects in Functions [Rosen Trick]

[Florian Weimer]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> From a pedagogical point of view, care needs to be taken not to give the
> impression that a function in a procedural programming language (most
> programming languages, really) is the same thing as a mathematical function.
> Clearly it isn't: a mathematical function is a kind of relation called a
> 'bijection' (and is nowadays specifically defined as such, I think);

A function f : M -> N are two sets M, N and a subset G_f of the
Cartesian product M x N with the following property: for all m in M,
there exists exactly one n in N such that (m, n) in G_f.

> a programming function is really just an encapsulated computation.

Yes, such functions take an additional implicit argument (the machine
state before execution) and have an invisible result (the machine
state after execution).

However, there are programming languages which use only mathematical
functions, and a special construct for I/O, Haskell for example.

Re: Side-Effects in Functions [Rosen Trick]

[Nick Roberts]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87itcn8xxx.fsf@deneb.enyo.de...
> "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:
>
> > From a pedagogical point of view, care needs to be taken not to give the
> > impression that a function in a procedural programming language (most
> > programming languages, really) is the same thing as a mathematical
function.
> > Clearly it isn't: a mathematical function is a kind of relation called a
> > 'bijection' (and is nowadays specifically defined as such, I think);
>
> A function f : M -> N are two sets M, N and a subset G_f of the
> Cartesian product M x N with the following property: for all m in M,
> there exists exactly one n in N such that (m, n) in G_f.

That actually sounds like an injection to me (1 to 1), whereas I get the
impression mathematicians (discrete ones anyway ;-) tend to insist nowadays
on the definition of a function as a bijection (both 1 to 1 and 'onto', i.e.
both an injection and a surjection, so that f' is also a bijection). However
IANAM.

> > a programming function is really just an encapsulated computation.
>
> Yes, such functions take an additional implicit argument (the machine
> state before execution) and have an invisible result (the machine
> state after execution).

Neatly put. Of course, if the (programming) function might perform I/O, we
are potentially talking about 'world state' (or even 'universe state')
rather than just machine state! (And then we have the problem with enthalpy,
but that, as they say, is a different game of banana and clotted cream.)

> However, there are programming languages which use only mathematical
> functions, and a special construct for I/O, Haskell for example.

I'm not a Haskell expert, but functional languages in general do fix the
order of evaluation of their functions (or some of their functions)
precisely because of the side-effect problem. I presume lazy evaluation can
be a serious hazard, if used without care, nevertheless.

--
Nick Roberts

Re: Side-Effects in Functions [Rosen Trick]

[Florian Weimer]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> "Florian Weimer" <fw@deneb.enyo.de> wrote in message
> news:87itcn8xxx.fsf@deneb.enyo.de...
>> "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:
>>
>> > From a pedagogical point of view, care needs to be taken not to give the
>> > impression that a function in a procedural programming language (most
>> > programming languages, really) is the same thing as a mathematical
> function.
>> > Clearly it isn't: a mathematical function is a kind of relation called a
>> > 'bijection' (and is nowadays specifically defined as such, I think);
>>
>> A function f : M -> N are two sets M, N and a subset G_f of the
>> Cartesian product M x N with the following property: for all m in M,
>> there exists exactly one n in N such that (m, n) in G_f.
>
> That actually sounds like an injection to me (1 to 1), 

Actually, it's many to one.  The uniqueness constraint is only there
to ensure that for each value m in M, there is only one value of
the function at m (usually denoted by "f(m)" or "m f", if you write
functions from the right).

> whereas I get the impression mathematicians (discrete ones anyway
> ;-) tend to insist nowadays on the definition of a function as a
> bijection (both 1 to 1 and 'onto', i.e.  both an injection and a
> surjection, so that f' is also a bijection).

I've yet to meet a mathematician who claims that functions are always
bijective.  Quite the contrary, in almost all the set-based categories
I've seen so far, morphisms weren't generally bijective.

>> However, there are programming languages which use only mathematical
>> functions, and a special construct for I/O, Haskell for example.
>
> I'm not a Haskell expert, but functional languages in general do fix the
> order of evaluation of their functions (or some of their functions)
> precisely because of the side-effect problem.

Haskell functions do not have side effects.  Side effects are
introduced by a special construct call a "monad", which essentially
introduces explicit machine state parameters.  There's a construct
("do") which makes them implicit again, too.

> I presume lazy evaluation can be a serious hazard, if used without
> care, nevertheless.

Lazy evaluation is a nice thing, as long as functions have no side
effects.

Re: Side-Effects in Functions [Rosen Trick]

[Robert Dewar]

pete@nospam <pete_member@newsguy.com> wrote in message news:<9s5eub02j61@drn.newsguy.com>...
> functions, in the mathemtical sense, do not accept an IN OUT paramters,
> and do not have side effects.
> 
> y=f(x), x here can never be modified by the function f().
> 
> so, Ada function is more like a math function.

Yes of course, that is the naive view that might be taught
in a beginning course, but it is bogus. Sure, Ada functions
can be used to model mathematical functions, that's true
in any case, but Ada functions are not a bit like math
functions. Mathematical functions cannot take pointer
arguments allowing modification of the calling variable,
mathematical functions cannot generate output on files,
mathematical functions cannot modify global variables.

Mathematical functions are very restrictive, and the language makes no
attempt to limit the semantics to
functions that have some sensible meaning as mathematical
functions.

That's the whole point here. Functions in Ada DO allow
side effects quite freely, and what seems odd is the
Ada rule in this case:

Functions are allowed to have side effects, providing that
there is no trace of this in the function specification :-)

The real issue here, and the point at which this becomes
significant, is that we use functions in Ada for interfacing to
foreign languages and there the restriction
is quite onerous, as anyone who has designed bindings to
C knows. Yes, access parameters help, but the requirement
that access parameters be non-null means that this usage
often is inapplicable.

For an example of functions that modify their parameters,
which is in fact possible in GNAT in some cases, using
implementation dependent features, see gnat.spitbol.patterns
(g-spipat.ads). Here the goal was
to model SNOBOL-4 style as closely as possible, and in
some cases, functions modifying their parameters lead to
the most natural usage from a SNOBOL-4 point of view. 
Since the point of this package is to assist in translation
of existing SNOBOL-4 programs, stylistic considerations
are significant. 

If (important criterion) you are familiar with SNOBOL4,
feel free to suggest other approaches that would avoid
this usage, I didn't find anything as convenient, and
would have preferred being able to program this in a more
direct manner.

Re: Side-Effects in Functions [Rosen Trick]

[Ted Dennison]

In article <5ee5b646.0111050556.1f9137ff@posting.google.com>, Robert Dewar
says...
>
>The real issue here, and the point at which this becomes
>significant, is that we use functions in Ada for interfacing to
>foreign languages and there the restriction
>is quite onerous, as anyone who has designed bindings to
>C knows. Yes, access parameters help, but the requirement
>that access parameters be non-null means that this usage
>often is inapplicable.

Actually access parameters are next to useless in C bindings for that very
reason.

However this isn't a huge issue with C bindings, as C has no "out" parameters in
functions either. At *worst*, you have to do what C coders have to do: use
pointers. If you lie down with dogs, you are going to get up with fleas. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Side-Effects in Functions [Rosen Trick]

[Warren W. Gay VE3WWG]

Ted Dennison wrote:

> In article <5ee5b646.0111050556.1f9137ff@posting.google.com>, Robert Dewar
> says...
...

> However this isn't a huge issue with C bindings, as C has no "out" parameters in
> functions either. At *worst*, you have to do what C coders have to do: use
> pointers. If you lie down with dogs, you are going to get up with fleas. :-)


You may also "smell like dogs" ;-)


-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Side-Effects in Functions [Rosen Trick]

[Ted Dennison]

In article <5ee5b646.0111041846.93f3e07@posting.google.com>, Robert Dewar
says...
>No, this is by no means a consensus. Most procedural
>languages, including Ada, allow functions to have side
>effects. And on the narrower issue of allowing IN OUT

C actually does not allow "OUT" parameters in functions either. In fact its even
worse than Ada here, in that it doesn't have procedures either, so there is *no*
language-defined way to pass values out through a paramter. I does allow one to
get around this restriction using pointers, but then so does Ada.

>Most people feel that being forced to add aliased keywords
>all over the place, just because of odd interfacing requirements for C
>functions, is unfortunate. If you find

Any C interfacing code is going to be somewhat ugly, not due to any failing in
Ada, just because C *is* ugly. That's why "most people" I talk to prefer thick C
bindings, to localize the uglyness.

Now all this being said, I am beginning to come around to your point of view.
Perhaps value-returning procedures should be reconsidered for the next Ada rev?
That would let folks keep their no (visible) side-effect functions.

I'm also beginning to think that some rethinking needs to be done about Ada's
whole parameter-passing scheme. It works well for public types, but blows for
private types. For a private type, its quite possible for me to not want to
change the users' view of a parameter, but to want to change some internal data
in it (eg: cache a location in a structure to speed up the next access if it is
liable to be nearby). Labelling such parameters as "in out" misleads the clients
(and not so incidentally, prevents use of functions). I'm getting really tired
of the gymnastics the language makes me go through to do this. Rosen trick
aside, there ought to be a way to specify certian portions of a private record
and tagged types as "internal", and thus always updatatable.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Side-Effects in Functions [Rosen Trick]

[Nick Roberts]

Just briefly, because I don't want to waste any more of my time on this, I'm
not entirely sure whether Robert is being serious, or is just arguing for
the fun of it (or something).

As to the issue of whether Ada should permit in-out parameters in functions,
I hold no strong opinion, and my original point had nothing to do with this.
Maybe it would be a nice idea, but you can always use a procedure instead;
no big deal. The 'problems' cited by various people about using access
parameters for interfacing with C functions are silly: if you need to be
able to pass a null value, you use an access type (and pass it in as an 'in'
parameter); again, no big deal.

On whether it is good practice to program functions with side-effects, in a
procedural language which doesn't specify the order in which the arguments
of functions are evaluated (such as Ada), I hold the very strong opinion
that it is generally not, for the perfectly rational, and well-established,
reason that it can introduce subtle and pernicious bugs. Robert has said
absolutely nothing to refute this. Twisting the argument between what can
and should be done may be a clever rhetorical technique, but it isn't good
science.

--
Nick Roberts

Re: Side-Effects in Functions [Rosen Trick]

[Georg Bauhaus]

Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote:
 
: On whether it is good practice to program functions with side-effects,

Well, that's it, then?


If your opinion is that strong, maybe you should really give
Haskell a chance. Also, I've found Paulson's remarks on the
issue (in an early chapter of his ML book) instructive.
(But then I am not someone with an abundance of languages and their
compilation techniques in his head, like others here, but I seem
to recall that this subject has been debated for decades?)

Georg

Re: List container strawman

[Vincent Marciante]

Jeffrey Carter wrote:
> 
> Matthew Heaney wrote:
> >
> > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> > news:3BE3235D.E292B890@boeing.com...
> > > Another place where some compiler writers use tricks is the interaction
> > > between a random number Generator value and the Random function.

<snip>

> > No heap allocation or compiler magic is needed to implement Generator; just
> > use the Rosen Trick:
> 
> Yes, that is a trick that can be used (although your example has a
> couple of errors). Was it known before standardization? I somehow
> suspect it would have been outlawed if it were.
> 
> GNAT uses

<snip> 

> I wonder if there is some advantage to this trick over the Rosen
> trick.

IIRC

The GNAT code was written before the Rosen Trick was first described.
The GNAT code worked and there was no important reason to change it.
If the Rosen Trick was known at the time, it would have been used. 

Vincent Marciante

Re: List container strawman

[Marin David Condic]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BE3235D.E292B890@boeing.com...
>
> There's no problem with the actual type being Controlled if the formal
> type is [limited] private. If there's anything about the actual type
> that requires finalization we would hope the client would implement it
> as a controlled type, since objects of this type are going to come and
> go as items are added and removed from the structure.
>
I think you missed it. Its the other way around. I was asking if the list
type you might be exporting from the generic package can be private and
contain something that is controlled.

generic
    type Something is private ;
package A_Package is
    type Something_Else is private ;
private
    type Something_Else is record
        X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ;
    end record ;
end A_Package ;

Without having passed anything like this past a compiler, I just don't know
if it is legal and gets Ted the ability to instantiate the generic from
within a non-library-level scope.


>
> Unbounded_String may be implemented as a controlled type. It's
> implementation is not defined, so compiler writers may use any tricks
> they think necessary, but you could write the implementation in plain
> Ada.
>
The spec in the appendix does not indicate a "with Ada.Finalization;"
anywhere I can see, so it isn't clear how they intended for it to be done.
That's why I was wondering how they dealt with assignment if, for example,
one were to want Unbounded_String to be implemented with some version of
dynamic allocation.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: List container strawman

[Ted Dennison]

In article <9s6a60$a49$1@nh.pace.co.uk>, Marin David Condic says...
>generic
>    type Something is private ;
>package A_Package is
>    type Something_Else is private ;
>private
>    type Something_Else is record
>        X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ;
>    end record ;
>end A_Package ;
>
>Without having passed anything like this past a compiler, I just don't know
>if it is legal and gets Ted the ability to instantiate the generic from
>within a non-library-level scope.

The problem with this approach is that the X field in Something_Else can have no
knowledge of any of other the fields in Something_Else, and thus is unable to
control it. It can control itself, but not its parent Something_Else. 

I think you can sometimes use tricks like this if the thing being controlled has
nothing to do with any of the generic parameters (or anything dependant upon
them). But in all other cases you are hosed, as near as I can tell.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

Hmmmmmmm..........


So basically, you're saying that a library level generic that contained as
part of it a Controlled element, you'd be able to instantiate it in a
procedure (non-library level)? But if a data item in it is itself derived
from Controlled, you can't? (Seems kind of strange, but I'm sure there's
going to be some corner-case of the rules to explain it.)

The Controlled thing clearly can't have anything to do with the generic
parameters since it needs to be itself declared in some other package. You
could pass the generic parameter making an instance of the Controlled thing,
but this is just pushing the problem off by one package - not really a
solution. So it would probably have to use something either convoluted
enough to fool the compiler into doing what you want, or it would need to do
something kind of "dirty" like using System.Address in the Controlled part
and doing some kind of access type to the generic parameter with a
conversion to address. (Kinky, but since it all remains hidden down in the
bowels of the implementation, probably not a hopelessly bad idea.)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:yWAF7.13454$xS6.17694@www.newsranger.com...
>
> The problem with this approach is that the X field in Something_Else can
have no
> knowledge of any of other the fields in Something_Else, and thus is unable
to
> control it. It can control itself, but not its parent Something_Else.
>
> I think you can sometimes use tricks like this if the thing being
controlled has
> nothing to do with any of the generic parameters (or anything dependant
upon
> them). But in all other cases you are hosed, as near as I can tell.
>

Re: List container strawman

[Ted Dennison]

In article <9s6o5m$fsi$1@nh.pace.co.uk>, Marin David Condic says...

>So basically, you're saying that a library level generic that contained as
>part of it a Controlled element, you'd be able to instantiate it in a
>procedure (non-library level)? But if a data item in it is itself derived
>from Controlled, you can't? (Seems kind of strange, but I'm sure there's
>going to be some corner-case of the rules to explain it.)

Yes. It isn't controlled per se. Its just that you can't declare a derived
tagged type at a lower level than its parent, and Controlled is a tagged type.
The rule goes for all tagged types. Its just that controlled was unfortunately
implemented as a tagged type declared at the library level.

>solution. So it would probably have to use something either convoluted
>enough to fool the compiler into doing what you want, or it would need to do
>something kind of "dirty" like using System.Address in the Controlled part
>and doing some kind of access type to the generic parameter with a
>conversion to address. (Kinky, but since it all remains hidden down in the
>bowels of the implementation, probably not a hopelessly bad idea.)

Any solution would have to have the library-level controlled type somehow know
how to control the non-library-level type. If the controlled stuff isn't a
generic parameter or dependent on one, there are (nasty) ways to do that. If it
is, then you are just plain hosed (unless someone knows a neat trick I don't).

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Stephen Leake]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> Hmmmmmmm..........
> 
> 
> So basically, you're saying that a library level generic that contained as
> part of it a Controlled element, you'd be able to instantiate it in a
> procedure (non-library level)? But if a data item in it is itself derived
> from Controlled, you can't? (Seems kind of strange, but I'm sure there's
> going to be some corner-case of the rules to explain it.)

The issue is where the Controlled _type_ is declared, not where the
_object_ of that type is declared. The _type_ must be declared at
library level, so pointers to it's base class are at the same level as
Controlled itself.

In this case, the Controlled type is still declared at library level;
the generic instantiation declares another type, which happens to
contain a component object of the Controlled type.

> The Controlled thing clearly can't have anything to do with the

You need to distinguish between declaring the type and declaring the
object. "Thing" is not specific enough.


-- 
-- Stephe

Re: List container strawman

[Mark Johnson]

Ted Dennison wrote:

> [snip]  If we *do* make it limited, then another issue I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I can't
> think of a good common use for lists of lists of the top of my head.

Examples of a list (or nested) of lists...
 - represent the nested scope of names (e.g., A.X.3) or other items
 - a sparse array implementation (2d or 3d...)
 - associative lookups of data
are a few that come off the top of my head. I kept thinking of LISP when I thought
of other applications as well. Not to say there are not better algorithms to
implement such capabilities, but you will likely be surprised at what people come up
with.
  --Mark

Re: List container strawman

[Marin David Condic]

Or a Unix/WinNT directory - that could be modeled as a list of lists of
lists of... (Sounds like recursion to me...)

Its something that would be nice to be able to do, but its not necessarily
something that won't have its own drawbacks. We can't expect everything out
of one little list package, so maybe we take a cut at what is possible and
think about alternate designs as possible additions. Maybe thats an
indication of a need for alternate list packages - or possibly other data
structures like trees?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Mark Johnson" <Mark_H_Johnson@Raytheon.com> wrote in message
news:3BE2E1DD.EE0078C7@Raytheon.com...
>
> Examples of a list (or nested) of lists...
>  - represent the nested scope of names (e.g., A.X.3) or other items
>  - a sparse array implementation (2d or 3d...)
>  - associative lookups of data
> are a few that come off the top of my head. I kept thinking of LISP when I
thought
> of other applications as well. Not to say there are not better algorithms
to
> implement such capabilities, but you will likely be surprised at what
people come up
> with.

Re: List container strawman

[Larry Kilgallen]

In article <3BE2E1DD.EE0078C7@Raytheon.com>, Mark Johnson <Mark_H_Johnson@Raytheon.com> writes:

> Examples of a list (or nested) of lists...
>  - represent the nested scope of names (e.g., A.X.3) or other items

It seems to me that would be a list inside a record, since if the
list contained elements for X, Y and Z, something associated with
the list would have to indicate A.

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:wVzE7.10194$xS6.14029@www.newsranger.com...

> I guess if the funcional stuff is going to remain in there, then it will
have to
> be a controlled type. That means that users won't be able to instantiate
it from
> within a subprogram (yuk!). If we *do* make it limited, then another issue
I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I
can't
> think of a good common use for lists of lists of the top of my head.

Lists of lists are frequently useful, but the problem you suggest is easily
(and efficiently) solved by having lists of access values to lists. E.g.:


   package Item_Collections is new Collections(Game_Item);

   subtype Item_List is Item_Collections.Utility.Linked_List;

   type Game_Room is limited
      record
         ...
         Contents: Item_List;
      end record;

   type Room_Reference is access all Game_Room;

   package Room_Collections is new Collections(Room_Reference);


and so on.

--
Nick Roberts

Re: List container strawman

[Ted Dennison]

In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
>2. Why is List private? Shouldn't it be limited private, so we avoid
>possible erros caused by aliasing?

Ahh. It finally dawned on me what your objection to private was. (I'm a little
slow today again.) We are talking about what happens when you do a 
"List1 := List2;", aren't we?

Yeah, it is either going to have to be limited, or be derived from
Ada.Finalization.Controlled. Limited gets rid of the ability to perform
funtional operations on it; Controlled get rid of the ability to instantiate it
from within a subprogram.

Have I mentioned lately how much I dislike the implementation of controlled
types? :-{

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

I'd think that in *most* instances you aren't going to need to instantiate
from within a subprogram. Hence, Controlled is probably not that much of a
burden. (We don't live in a perfect world do we?)

How does Ada.Strings.Unbounded handle not being limited? I didn't see an
indication of it being derived from Controlled and it is doing something
fairly similar to lists. Or does it rely on behind-the-scenes magic to cope
with their dynamic nature?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:WOzE7.10186$xS6.14012@www.newsranger.com...
>
> Ahh. It finally dawned on me what your objection to private was. (I'm a
little
> slow today again.) We are talking about what happens when you do a
> "List1 := List2;", aren't we?
>
> Yeah, it is either going to have to be limited, or be derived from
> Ada.Finalization.Controlled. Limited gets rid of the ability to perform
> funtional operations on it; Controlled get rid of the ability to
instantiate it
> from within a subprogram.
>
> Have I mentioned lately how much I dislike the implementation of
controlled
> types? :-{
>

Re: List container strawman

[Ted Dennison]

In article <9rui2b$kku$1@nh.pace.co.uk>, Marin David Condic says...
>How does Ada.Strings.Unbounded handle not being limited? I didn't see an
>indication of it being derived from Controlled and it is doing something
>fairly similar to lists. Or does it rely on behind-the-scenes magic to cope
>with their dynamic nature?

The one implementation I know about (and I haven't looked at Gnat's so I could
easily make it two) does indeed use a controlled type. Since it isn't a generic,
and is indeed declared at the library level, this is no problem. We have the
problem here because its a generic. 

Remember, declaring objects of type List isn't the issue. The issue is declaring
the list type itself.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Yeah, it is either going to have to be limited, or be derived from
> Ada.Finalization.Controlled. Limited gets rid of the ability to perform
> funtional operations on it; Controlled get rid of the ability to instantiate it
> from within a subprogram.

Functions may return limited values; the function call may be used as
the actual for a parameter or renamed as a (constant) object of the
type.

Controlled requires instantiating at the library level, which is a pain,
but I think it's required anyway for an unbounded structure, since
otherwise you will have memory leaks when objects of the type go out of
scope.

-- 
Jeffrey Carter

Re: List container strawman

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:WOzE7.10186$xS6.14012@www.newsranger.com...
> In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
> >2. Why is List private? Shouldn't it be limited private, so we avoid
> >possible erros caused by aliasing?
>
> Ahh. It finally dawned on me what your objection to private was. (I'm a
little
> slow today again.) We are talking about what happens when you do a
> "List1 := List2;", aren't we?


Yep.

And to make things worse the scoping issues with Controlled are really
confusing for beginners.
Now I don't see any reason why newcomers shouldn't be able to reuse standard
containers, but I really don't want to start explaining "controled type must
be declared at library level".
Amusingly, a student just asked about this problem, in my course newsgroup,
trying to reuse a linked list package. They are now just learning about the
basics of ADTs, and Ada packages...

Are we coming to the conclusion that Ada95 approaches to memory management
(Controlled and storage pools), simply aren't enough for creating reliable
components, without imposing inessential restrictions?
We want user created abstractions to be as much like language supplied types
as possible, remember.

Ehud

Better Finalisation [List container strawman]

[Nick Roberts]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9sdnb2$dd4$1@news.huji.ac.il...
> ...
> Are we coming to the conclusion that Ada95 approaches to memory management
> (Controlled and storage pools), simply aren't enough for creating reliable
> components, without imposing inessential restrictions?
> We want user created abstractions to be as much like language supplied
types
> as possible, remember.

I am of this conclusion, as regards finalisation. It's not a criticism of
the designers of Ada 95: it's so very easy to be wise when you have the
benefit of hindsight, and I think we'd all agree that overall those
designers did a superb job.

However, it seems feasible to me to introduce a new finalisation mechanism
in the next revision. All we really need (am I wrong?) is three attributes,
applying to any type T, which are the procedures carried out whenever an
object of the type is created, copied, and destroyed:

   procedure T'Construct (Object: in out T);
   procedure T'Destroy (Object: in out T);
   procedure T'Assign (Source, Target: in out T);

These attributes would, naturally, have implementation-supplied defaults,
but could be overidden by attribute definition clauses, as normal.

Obviously Assign would not apply to a limited type. It would probably be
best if none applied to a task or protected type. The exact details of when
these procedures were called, etc., would be quite complex, but I think this
is essentially all we need.

As for storage pools, I think the existing design is fine. I would like to
see the addition (in the next language revision) of a package declaring a
type, derived from Root_Storage_Pool, which had extra operations better
supporting full garbage collection. I posted something (maybe a little
premature) about this a while back; perhaps I'll write a paper on the
subject, or something.

--
Nick Roberts

Re: Better Finalisation [List container strawman]

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9seup3$12h0ar$2@ID-25716.news.dfncis.de>...

>    procedure T'Construct (Object: in out T);
>    procedure T'Destroy (Object: in out T);
>    procedure T'Assign (Source, Target: in out T);

It's easy to suggest something at this level, but much much
harder to work out the full implications. A starting point
would be to work up a full complete coherent description
based on the above thought.

You will find it much harder than you think. 

You should also thoroughly review the discussion of this
issue during the design phase. In fact finalization (note
by the way that we spell it with a z in the Ada world, and
indeed that's the preferred spelling anyway) was extensively discussed
during the design phase, and of
course the above general idea was explored (this is hardly
a non-obvious idea).

The conclusion at that time (I don't see anything that would change
it) is that this was too complex to work out,
and the feature was dropped.

Finalization was reintroduced when a suggestion based on
the current semantics was made. This seemed much simpler,
and was put in relatively late. However, it has turned out
from an implementation point of view that even this proposal was far
harder to implement that expected.

But anyway, read the old stuff, no point in reinventing
the wheel. As so often happens in language design, ideas
that seem simple at the naive user level turn out to be
a den of vipers at the detailed semantic specification
level.

Nick, you should certainly have all the old mapping documents on your
shelf. You will find these a fertile
source of interesting ideas. The old mapping documents
are full of coherent well worked out useful ideas that
did not make it into the final language not because they
were wrong (*) but simply because there was a requirement
to keep the entire language at an acceptable level of
complexity (**).

Can we do more for the next version? Perhaps in some
critical areas, but not much. If the next version of
Ada is too big a delta, it will simply be ignored by
vendors at this stage. Even now, we have lots of customers
running Ada 83 rather than Ada 95 -- transition takes a long long
time.

Robert Dewar

(*) Tuck always used to demand that we show why a feature
was wrong before he would agree to remove it, but most often there was
nothing wrong. The straw was all high
quality, but the camel's back was still in danger :-)

(**) I think we probably hit about the right level in
retrospect. We lost one major vendor (DEC, who decided
that the effort in moving to Ada 95 would be too great,
and so abandoned their successful and profitable Ada
product), and we lost a couple of other front ends
(Alsys and Telesoft), but we gained a couple of front
ends (GNAT and Intermetrics), and it proved possible
to move an Ada 83 compiler to Ada 95 (Rational and
others).

Re: Better Finalisation [List container strawman]

[Florian Weimer]

dewar@gnat.com (Robert Dewar) writes:

> Can we do more for the next version?

I would like to see a generic version of Ada.Finalization, to work
around the problem that all objects with finalizers have to be
declared at the library level.

Re: Better Finalisation [List container strawman]

[Nick Roberts]

"Robert Dewar" <dewar@gnat.com> wrote in message
news:5ee5b646.0111090536.5fe5852e@posting.google.com...
> ...
> You should also thoroughly review the discussion of this
> issue during the design phase.
> ...
> But anyway, read the old stuff, no point in reinventing
> the wheel.
> ...
> Nick, you should certainly have all the old mapping documents on your
> shelf.

Okay, I'll look over them (on the ARA web site). Are they available in
print?

--
Nick Roberts

Re: Better Finalisation [List container strawman]

[Ted Dennison]

In article <9seup3$12h0ar$2@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
>news:9sdnb2$dd4$1@news.huji.ac.il...
>However, it seems feasible to me to introduce a new finalisation mechanism
>in the next revision. All we really need (am I wrong?) is three attributes,

The suggestion I heard that I think is most doable was to simply make a generic
version of Ada.Finalization. The current package could then be a library-level
instantiation of the new generic one. That would fix the library-level problem,
and still be backwards-compatable with old code. The only old code I could think
of that could get hosed would be something that checks types against
Ada.Finialzation.Controlled'Class, and assumes that failure means it isn't
controlled.

As Robert pointed out, I haven't looked deeply enough into this to know that it
isn't unfeasable somehow.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Better control of assignment

[Jeffrey Carter]

Nick Roberts wrote:
> 
> However, it seems feasible to me to introduce a new finalisation mechanism
> in the next revision. All we really need (am I wrong?) is three attributes,
> applying to any type T, which are the procedures carried out whenever an
> object of the type is created, copied, and destroyed:
> 
>    procedure T'Construct (Object: in out T);
>    procedure T'Destroy (Object: in out T);
>    procedure T'Assign (Source, Target: in out T);

Assignment should not be able to modify the RHS, especially as it may be
an expression, not a variable.

> 
> These attributes would, naturally, have implementation-supplied defaults,
> but could be overidden by attribute definition clauses, as normal.

I was thinking recently of how to provide a different implementation of
Ada.Strings.Unbounded, and came to the conclusion that the current
controlled-type handling of user-defined assignment is not able to
handle the concept I had in mind. Of course, I might be wrong about
this, and would be happy if I am.

The basic idea is to define an Unbounded_String as

Initial_Max_Length : constant := ...;

type Unbounded_String is [new Ada.Finalization.Controlled with] record
   Length : Natural := 0;
   Value  : String_Access := new String (1 .. Initial_Max_Length);
end record;

Finalization would free Value.

Then, given

LHS : Unbounded_String;
...
LHS := RHS;

where RHS is an expression of type Unbounded_String, would operate along
the lines of

LHS.Length := RHS.Length;

if LHS.Value'Length < RHS.Length then
   Free (LHS.Value);
   LHS.Value := new String (1 .. RHS.Value'Length);
end if;

LHS.Value (1 .. RHS.Length) := RHS.Value (1 .. RHS.Length);

The general idea is to exchange some space for the ability to avoid
deallocation and reallocation with every assignment, doing so only when
it is necessary.

Although I have used Unbounded_String as an example, this basic idea
would be useful for many user-defined types. It appears that controlled
types are unable to implement this, while the proposal above could. Of
course, such things are easy to propose but difficult to specify
completely, and the implementation burden may be unacceptable. The
implications of redefining assignment in C++ are extremely complex, and
we should avoid such complexity in Ada. On the other hand, this is a
very useful capability that we should consider including in Ada 0X.

One can implement this capability with a limited type and an Assign
procedure, but Unbounded_String may not be implemented that way.

-- 
Jeffrey Carter

Re: Better control of assignment

[Nick Roberts]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BEC12BA.E72A81EC@boeing.com...
> Nick Roberts wrote:
> >    procedure T'Construct (Object: in out T);
> >    procedure T'Destroy (Object: in out T);
> >    procedure T'Assign (Source, Target: in out T);
>
> Assignment should not be able to modify the RHS, especially as it may be
> an expression, not a variable.

Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it
seems obvious (of course ;-) that if the RHS is a constant, this procedure
is not invoked; it is only invoked for a copy (including parameter passing
by copy (if selected)) from one variable object of type T to another. If
this does not deliver enough control, you must make the type private. For
example:

   type Odd_Counter is new Integer;
   procedure Assign_Odd (Src, Tgt: in out Odd_Counter);
   for Odd_Counter'Copy use Assign_Odd;
   ...
   procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is
   begin
      if not Is_Odd(Src) then
         raise Oddness_Error;
      else
         Tgt := Src; -- inherited assignment used here by a language rule
      end if;
   end;

The idea is that an object of type Odd_Counter can only ever hold an odd
number. But nothing prevents:

   C: Odd_Counter := 2; -- oddness violation, but it will not be caught

So we must instead declare (in a package specification):

      type Odd_Counter is private;
      ...
      procedure Init (Ctr: in out Odd_Counter; Int: in Integer);
      ...
   private
      type Odd_Counter is new Integer;
      ...

And then (in the package body) we can check for oddness:

      procedure Init (Ctr: in out Odd_Counter; Int: in Integer) is
      begin
         if not Is_Odd(Int) then
            raise Oddness_Error;
         else
            Ctr := Odd_Counter(Int);
         end if;
      end;

Of course, in this case, if we want the bastion of operations pre-defined
for Integer, we must explicitly declare functions for "+", "-", "*", "/" and
so on. Too bad.

> I was thinking recently of how to provide a different implementation of
> Ada.Strings.Unbounded, and came to the conclusion that the current
> controlled-type handling of user-defined assignment is not able to
> handle the concept I had in mind. Of course, I might be wrong about
> this, and would be happy if I am.

I believe my proposal would solve the problem of the kind of implementation
of Ada unbounded strings that Jeff suggests.

--
Nick Roberts

Re: Better control of assignment

[Jeffrey Carter]

Nick Roberts wrote:
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> > Assignment should not be able to modify the RHS, especially as it may be
> > an expression, not a variable.
> 
> Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it
> seems obvious (of course ;-) that if the RHS is a constant, this procedure
> is not invoked; it is only invoked for a copy (including parameter passing
> by copy (if selected)) from one variable object of type T to another. If
> this does not deliver enough control, you must make the type private. For
> example:
> 
>    type Odd_Counter is new Integer;
>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter);
>    for Odd_Counter'Copy use Assign_Odd;
>    ...
>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is
>    begin
>       if not Is_Odd(Src) then
>          raise Oddness_Error;
>       else
>          Tgt := Src; -- inherited assignment used here by a language rule
>       end if;
>    end;

There is still no need for Src to be mode in out.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: Better control of assignment

[Craig Carey]

On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org>
wrote:

>Nick Roberts wrote:
>> 
>> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
>> > Assignment should not be able to modify the RHS, especially as it may be
>> > an expression, not a variable.
>> 
>> Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it
>> seems obvious (of course ;-) that if the RHS is a constant, this procedure
>> is not invoked; it is only invoked for a copy (including parameter passing
>> by copy (if selected)) from one variable object of type T to another. If
>> this does not deliver enough control, you must make the type private. For
>> example:
>> 
>>    type Odd_Counter is new Integer;
>>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter);
>>    for Odd_Counter'Copy use Assign_Odd;
>>    ...
>>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is
>>    begin
>>       if not Is_Odd(Src) then
>>          raise Oddness_Error;
>>       else
>>          Tgt := Src; -- inherited assignment used here by a language rule
>>       end if;
>>    end;
>
>There is still no need for Src to be mode in out.

---

>Nick Roberts wrote:
>> 
>> However, it seems feasible to me to introduce a new finalisation 
>> in the next revision. All we really need (am I wrong?) is three
>> attributes,
...
>>    procedure T'Construct (Object: in out T);
>>    procedure T'Destroy (Object: in out T);
>>    procedure T'Assign (Source, Target: in out T);
>
>Assignment should not be able to modify the RHS, especially as it may
> be an expression, not a variable.
>

Are you sure you want to allow Strings to be destroyed?.

Suppose the pointers got copied, as in this example:

procedure Crash_Ada is
   A, B, C : Unlimited_String;
begin
   Make_New (A);
   B.Ref := A.Ref;
   B.Length := ...
   C.Ref := A.Ref;
      --  At scope exit, the Destructor presumably is called onto all
      --  3 variables.
end Crash_Ada;

A fix is to stop the assignments to the ".Ref" fields.
There could be an agreement that we want to allow assigning to the
Length and Ref.all fields to quite available to packages with-ing
the package.

The whole program could crash when the Destructor frees the same
memory twice.

---

One problem is that letting the programmer do a swapping assign
instead of a copying assign, e.g.

       A :=. B

is that the routine holding B might have to be recoded like this:

From:

    procedure T (B : in Unlimited_String)

into:

    procedure T (B : in out Unlimited_String).

That is undesirable and it may be possible to allow records to have
read-only fields that can be altered (by routines declared in the same
package that declares the type), even though they are supposed to be
constant because they are an "in" mode parameter.

An aim here is to not force people to have pointers to pointers just
to avoid rewritng

   procedure F (B : in Unlimited_String.Vstr) is
   begin
      A :=. B;   --  Fast Assign with pointer swapping and loss of RHS
   end F;

as 

   procedure F (B : in Unlimited_String.Vstr) is
   begin
      A :=. B;
   end F;


It can be just a matter of adding the "out" mode to a record field
which makes the type have a read-only field.

An example of a new proposed feature for Ada:

package Q is
   type Vstr is
      record                             --  Ref is exported read only
         Ref      : out String_Access := Null_String_Access;
         Length   : Natural := 0;
      end record;
   procedure ":=." (L : out Vstr; R : in Vstr);
      --  Swaps pointers and changes the pointer value, R.Ref. It is
      --   read-only, not constant.
end Q;

package body Q is
   procedure ":=." (L : out Vstr; R : in Vstr) is
      Tmp    : Access_String;   --  Fast assign with ptr swapping
   begin
      LHS.Length := RHS.Length;
      Tmp := LHS.Ref;
      LHS.Ref := RHS.Ref;
      RHS.Ref := Tmp;
      RHS.Length := 0;     --  Invalidate the RHS pointer
   end ":=.";
end Y;

procedure R (B : in Q.Vstr) is
   A    : Q.Vstr;
begin
   Unknown1 (Alter_It => B);  --  This proc is not able to alter B.Ref
                              --  but it can change B.Ref.all.

   ...       --  Final access of the data from B destroys it.
             --  It is either that for inefficiency or lazy ":="-ing

   A :=. B;  --  B.Ref can be changed by the Fast Assignment operator
             --  since it is in the package defining (or extending)
             --   the type. That B (and B.Ref) is of the "in" mode
             --   would not stop any routine in Q from altering B.Ref.
   ...
end R;


A big advantage of that is that there are no pointers to pointers to
mislead the language into believing a value changed is not.


Maybe lazy assignments could be slower and it is not clear why such
a complex scheme ought be implented, with its destructors, when this
far simpler can't properly get destructors.

http://groups.google.com/groups?hl=en&rnum=11&selm=dewar.848839209%40merv

  > From: Robert Dewar
  > Subject: Re: Unbounded strings (Was: Java vs Ada 95 (Was Re: Once
  >   again, Ada absent from DoD SBIR solicitation)) 
  > Newsgroups: comp.lang.ada
  > Date: 1996/11/24 

Mr Dewar's lazy assignment idea might not be a remedy for the problem
of slow String handling code.

To put a pointer inside of a record and make it private or limited,
won't stop writing to the pointer while allowing writing to the ".all"
value. It is a bug in the language. No is "access constant [subtype]"
helpful.

Maybe M Carter can come up with an example arguing for user defining
of assignment that keeps away from Strings where what seem to be
language design defects become explicit.

When there are two pointers, then the first pointer can be made a
pointer to a 2nd pointer that is defined to be of this type:

   type [name] is access constant [second_pointer_subtype];

That stops all alteration of the B.Ref1.Ref2 while fully allowing
alterating of

     B.Ref1.Ref12.all (1 .. Sockets_Buffer_Maxlength).

Re: Better control of assignment

[Craig Carey]

On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org>
wrote:

>Nick Roberts wrote:
>> 
>> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
>> > Assignment should not be able to modify the RHS, especially as it may be
>> > an expression, not a variable.
>> 
>> Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it
>> seems obvious (of course ;-) that if the RHS is a constant, this procedure
>> is not invoked; it is only invoked for a copy (including parameter passing
>> by copy (if selected)) from one variable object of type T to another. If
>> this does not deliver enough control, you must make the type private. For
>> example:
>> 
>>    type Odd_Counter is new Integer;
>>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter);
>>    for Odd_Counter'Copy use Assign_Odd;
>>    ...
>>    procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is
>>    begin
>>       if not Is_Odd(Src) then
>>          raise Oddness_Error;
>>       else
>>          Tgt := Src; -- inherited assignment used here by a language rule
>>       end if;
>>    end;
>
>There is still no need for Src to be mode in out.

---

>Nick Roberts wrote:
>> 
>> However, it seems feasible to me to introduce a new finalisation 
>> in the next revision. All we really need (am I wrong?) is three
>> attributes,
...
>>    procedure T'Construct (Object: in out T);
>>    procedure T'Destroy (Object: in out T);
>>    procedure T'Assign (Source, Target: in out T);
>
>Assignment should not be able to modify the RHS, especially as it may
> be an expression, not a variable.
>

Are you sure you want to allow Strings to be destroyed?.

Suppose the pointers got copied, as in this example:

procedure Crash_Ada is
   A, B, C : Unlimited_String;
begin
   Make_New (A);
   B.Ref := A.Ref;
   B.Length := ...
   C.Ref := A.Ref;
      --  At scope exit, the Destructor presumably is called onto all
      --  3 variables.
end Crash_Ada;

A fix is to stop the assignments to the ".Ref" fields.
There could be an agreement that we want to allow assigning to the
Length and Ref.all fields to quite available to packages with-ing
the package.

The whole program could crash when the Destructor frees the same
memory twice.

---

One problem is that letting the programmer do a swapping assign
instead of a copying assign, e.g.

       A :=. B

is that the routine holding B might have to be recoded like this:

From:

    procedure T (B : in Unlimited_String)

into:

    procedure T (B : in out Unlimited_String).

That is undesirable and it may be possible to allow records to have
read-only fields that can be altered (by routines declared in the same
package that declares the type), even though they are supposed to be
constant because they are an "in" mode parameter.

An aim here is to not force people to have pointers to pointers just
to avoid rewritng

   procedure F (B : in Unlimited_String.Vstr) is
   begin
      A :=. B;   --  Fast Assign with pointer swapping and loss of RHS
   end F;

as 

   procedure F (B : in Unlimited_String.Vstr) is
   begin
      A :=. B;
   end F;


It can be just a matter of adding the "out" mode to a record field
which makes the type have a read-only field.

An example of a new proposed feature for Ada:

package Q is
   type Vstr is
      record                             --  Ref is exported read only
         Ref      : out String_Access := Null_String_Access;
         Length   : Natural := 0;
      end record;
   procedure ":=." (L : out Vstr; R : in Vstr);
      --  Swaps pointers and changes the pointer value, R.Ref. It is
      --   read-only, not constant.
end Q;

package body Q is
   procedure ":=." (L : out Vstr; R : in Vstr) is
      Tmp    : Access_String;   --  Fast assign with ptr swapping
   begin
      LHS.Length := RHS.Length;
      Tmp := LHS.Ref;
      LHS.Ref := RHS.Ref;
      RHS.Ref := Tmp;
      RHS.Length := 0;     --  Invalidate the RHS pointer
   end ":=.";
end Y;

procedure R (B : in Q.Vstr) is
   A    : Q.Vstr;
begin
   Unknown1 (Alter_It => B);  --  This proc is not able to alter B.Ref
                              --  but it can change B.Ref.all.

   ...       --  Final access of the data from B destroys it.
             --  It is either that for inefficiency or lazy ":="-ing

   A :=. B;  --  B.Ref can be changed by the Fast Assignment operator
             --  since it is in the package defining (or extending)
             --   the type. That B (and B.Ref) is of the "in" mode
             --   would not stop any routine in Q from altering B.Ref.
   ...
end R;


A big advantage of that is that there are no pointers to pointers to
mislead the language into believing a value changed is not.


Maybe lazy assignments could be slower and it is not clear why such
a complex scheme ought be implented, with its destructors, when this
far simpler can't properly get destructors.

http://groups.google.com/groups?hl=en&rnum=11&selm=dewar.848839209%40merv

  > From: Robert Dewar
  > Subject: Re: Unbounded strings (Was: Java vs Ada 95 (Was Re: Once
  >   again, Ada absent from DoD SBIR solicitation)) 
  > Newsgroups: comp.lang.ada
  > Date: 1996/11/24 

Mr Dewar's lazy assignment idea might not be a remedy for the problem
of slow String handling code.

To put a pointer inside of a record and make it private or limited,
won't stop writing to the pointer while allowing writing to the ".all"
value. It is a bug in the language. No is "access constant [subtype]"
helpful.

Maybe M Carter can come up with an example arguing for user defining
of assignment that keeps away from Strings where what seem to be
language design defects become explicit.

When there are two pointers, then the first pointer can be made a
pointer to a 2nd pointer that is defined to be of this type:

   type [name] is access constant [second_pointer_subtype];

That stops all alteration of the B.Ref1.Ref2 while fully allowing
alterating of

     B.Ref1.Ref12.all (1 .. Sockets_Buffer_Maxlength).

Re: Better control of assignment

[Craig Carey]

On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org>
wrote:

>s only invoked for a copy (including parameter passing
>> by copy (if selected)) from one variable object of type T to another. If
>> this does not deliver enough control, you must make the type private. For
>> example:
>> 
>>    type Odd_Counter is new Integer;
>>    procedure Assign_O


The Oberon-2 language implements a feature of read-only record field
components.

Also it allows package spec variables (Module identifiers) to be
exported read-only.


A page on Oberon-2, that mentions the "read-only" "export mark"
feature of Oberon-2, is here:

http://www-cse.ucsd.edu/classes/sp01/cse131B_A/oberon2.htm

|
|[Module] Identifiers [variables] marked with " - " in their declaration
| are read-only in importing modules. 


|  Qualident = [ident "."]ident.
|  IdentDef  = ident [" * " | " - "].

...

|If a [an array] or r [a record or a component record in a record] are
| read-only, then also a[e] and r.f are read-only.
...

|MODULE Trees;  (* exports: Tree, Node, Insert, Search, Write, Init *)
|  IMPORT Texts, Oberon;  (* exports read-only: Node.name *)
|
|  TYPE
|    Tree* = POINTER TO Node;
|    Node* = RECORD
|      name-: POINTER TO ARRAY OF CHAR;
|      left, right: Tree
|    END;
...

I never saw a comment saying that a using module can't assign chars
to x.name^ [X.name.all]. 


If Ada were following closely an Oberon-2 style, then this could a
 the way to make Ref be read-only:

   type Unbounded_String is [? new Ada.Finalization.Controlled with]
      record
         Length : Natural := 0;
         Ref-   : String_Access := ...;
      end record;

That is sure to be rejected: the modifier ought be on the right of the
":" since it affects the type and not the name.

More on Modula-2: http://www.cetus-links.org/oo_oberon.html



Some selected Error messages of the "Optimizing Oberon-2 Compiler",
follow.
Error messages 244 & 245 imply that in Oberon, making X.Ref be
exported as read-only [either the type of a module variable], where
X is a record type and Ref is a pointer, does not cause X.Ref.all
(i.e. X.Ref^) to be read-only. Just as is hoped for.


http://ooc.sourceforge.net/OOCref/OOCref_19.html

|
|*201: Can only be exported with **'' 
|
|Constants, types, and procedures cannot be exported with *-'
|because the notion of a restricted, read-only access doesn't make
|sense for these objects. 
|
|
|*244: This isn't a variable designator' 
|
|This applies to the following cases: 
|  Only a modifiable variable designator may appear on the left
|    side of an assignment statement. The variable designator may
|    not refer to a variable or record field that has been
|    exported as read-only. 
|  The control variable of a FOR statement has to be an
|    unqualified (i.e., local) variable identifier. 
|Note that dereferencing a read-only pointer variable will grant
|unrestricted access to the pointer's contents. 
|
|
|*245: This is imported read-only' 
|
|This applies to the left side of an assignment statement and to
|variables passed to a VAR parameter as part of a procedure call.
|This means that the destination variable (or designator) has to be
|either
|  1. imported as read-write (and no following selector accesses
|       a read-only record field), or
|  2. the value of a dereferenced pointer variable. 
|Contrary to a pointer dereference, an element of a read-only array
|is read-only, just like a field of a read-only record variable. 
|


I have doubts about Mr Carter's assignment, with its familiar right
 hand side is read only and left hand side is written too nature.

I my proposal, the left side is read-only [i.e. writable to only by
subprocedures in its package], and the right hand side can be written
to (pointers swapped) even though an "in" mode parameter [this last
may need to be checked].

Either that or C-isms of pointers to pointers may appear.



---------

PS. I accidentally 'double posted' the same message.
In some cases the duplicate could be deleted.

PS. By sending data through a debugging TCP proxy, such accidents
ought be harder to do. 

Here is Win32 GUI debugging proxy that shows bytes passing through it:

TCP Viewer:   http://www.westbrooksoftware.com/ 

Re: Better control of assignment

[Craig Carey]

In this message I propose a way if importing package spec variables as
 being read-only even though they were not exported as being
 read-only.
Faster strings too.




On Tue, 13 Nov 2001 21:53:21 +1300, Craig Carey <research@ijs.co.nz>
wrote:

>On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org>
>wrote:
>>Nick Roberts wrote:
>>s only invoked for a copy (including parameter passing
>>> by copy (if selected)) from one variable object of type T to another. If
>>> this does not deliver enough control, you must make the type private. For
>>> example:
...
No need to make the type 'private' if there is a read-only feature
like what Oberon has.

>
>http://www-cse.ucsd.edu/classes/sp01/cse131B_A/oberon2.htm
...
>More on Modula-2: http://www.cetus-links.org/oo_oberon.html
...
>http://ooc.sourceforge.net/OOCref/OOCref_19.html
...
>|'245: This is imported read-only' 
>|
>|This applies to the left side of an assignment statement and to
>|variables passed to a VAR parameter as part of a procedure call.
>|This means that the destination variable (or designator) has to be
>|either
>|  1. imported as read-write (and no following selector accesses
>|       a read-only record field), or
>|  2. the value of a dereferenced pointer variable. 
>|Contrary to a pointer dereference, an element of a read-only array
>|is read-only, just like a field of a read-only record variable. 
>|
...

It seems that a record with both read-only and read-write fields,
and that is exported as being read-write, can be imported as being
read-only. That read-only importing overrides the read-write
exporting. That seems to Oberon feature that can be copied and
implemented with pragmas. It is 

Here is a quick proposed way of making imported package variables
be read only:

   package RW is
      X  : in out Integer;
   end RW;
   ---

   with RW;
   package P is
      package RO renames out RW;  --  Rename, make T2.* be read-only
      RO.X := 5;      --  illegal!, can use RW.X to get write access
   end P;

---

>subprocedures in its package], and the right hand side can be written
>to (pointers swapped) even though an "in" mode parameter [this last
>may need to be checked].

That is wrong (the fields of an "in" mode record parameter do not get
copied back to the caller, and presumably that is not going to be
altered).

Hence the improved fast Strings package with no use of private may
need to have pointers to pointers even in the distant future.

Here is fragment of a new spec file. This thread has been useful since
it got to conclude the pointers to pointers seem to be needed.


package Strings_Unlimited is
      --  Note: duplicating pointers may lead to faulty behaviour
      --  The arrival of read-only or limited pointers can lead to
      --   a fix.
   type String_Access is access all String;
   type String_Access_Ptr is access constant String_Access;

   Null_String_Access      : aliased constant String_Access :=
                                 new String (1 .. 0);
   Null_String_Access_Ptr  : aliased constant String_Access_Ptr :=
                                 Null_String_Access'Access;

   type Unlimited_String is
      limited record
         Ref         : String_Access_Ptr := Null_String_Access_Ptr;
         Len         : Natural := 0;
      end record;
   ...
end Strings_Unlimited;

I would have some code implementing this package once it is checked
and/or debugged. I wonder how the US military gets on with those
slow Strings.

Pointer copying could also be stopped by allowing pointer types to be
"limited". What a interesting finding: Oberon-2 is a better than
Ada 95 in sime areas.

Re: List container strawman

[Ted Dennison]

In article <9sdnb2$dd4$1@news.huji.ac.il>, Ehud Lamm says...
>
>Now I don't see any reason why newcomers shouldn't be able to reuse standard
>containers, but I really don't want to start explaining "controled type must
>be declared at library level".

To make matters worse, that isn't even where you'd have to start. You'd have to
start by talking about tagged types and declaration levels, then move to the
fact that controlled is a tagged type declared at the library level. :-)

>Are we coming to the conclusion that Ada95 approaches to memory management
>(Controlled and storage pools), simply aren't enough for creating reliable
>components, without imposing inessential restrictions?

I don't think there's anything horribly wrong with the rest of the language, but
we can certianly come to the conclusion that the way Controlled is currently
implemented blows. I've said as much to any who would listen for about the last
year or so. However, I would like to agree with Nick's point that my contempt is
aimed solely at the feature in its current state, not the folks who worked on
the language design. I could easily see where this consequence was either not
forseen, or it wasn't realised how big of a problem the restriction would be.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:72SG7.18851$xS6.30225@www.newsranger.com...
> However, I would like to agree with Nick's point that my contempt is
> aimed solely at the feature in its current state, not the folks who worked
on
> the language design. I could easily see where this consequence was either
not
> forseen, or it wasn't realised how big of a problem the restriction would
be.
>

I am sure we can all agree that no one here feels contempt for the Ada95
designers.

Ehud

Re: List container strawman

[Marin David Condic]

Aside from the restrictions, I've found it to be just plain buggy. By
combining Controlled with other features, either Controlled breaks, or the
other features break. Granted, the experience I have, has only been with a
handful of versions of a single compiler, but because it seems to kill
things in new and interesting ways in a variety of settings, I begin to
wonder if the feature is just simply not reliable in its current design.

We need something very much like Controlled, but perhaps it is possible to
design something that is a little less restrictive and/or a little easier to
make reliable?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:72SG7.18851$xS6.30225@www.newsranger.com...
>
> I don't think there's anything horribly wrong with the rest of the
language, but
> we can certianly come to the conclusion that the way Controlled is
currently
> implemented blows. I've said as much to any who would listen for about the
last
> year or so. However, I would like to agree with Nick's point that my
contempt is
> aimed solely at the feature in its current state, not the folks who worked
on
> the language design. I could easily see where this consequence was either
not
> forseen, or it wasn't realised how big of a problem the restriction would
be.
>

Re: List container strawman

[Ted Dennison]

In article <9sh2qq$nu6$1@nh.pace.co.uk>, Marin David Condic says...
>
>Aside from the restrictions, I've found it to be just plain buggy. By
>combining Controlled with other features, either Controlled breaks, or the
>other features break. Granted, the experience I have, has only been with a
>handful of versions of a single compiler, but because it seems to kill
>things in new and interesting ways in a variety of settings, I begin to
>wonder if the feature is just simply not reliable in its current design.

I've often found trouble when doing complicated or unusual things with the
language with any compiler. Perhaps what you are seeing is just a combination of
the fact that, as Robert pointed out, Controlled is tricky to implement
properly, and the fact that as designed it isn't as useful (and therefore as
exercised in compilers) as it could be.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Matthew Heaney]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9sh2qq$nu6$1@nh.pace.co.uk...
> Aside from the restrictions, I've found it to be just plain buggy. By
> combining Controlled with other features, either Controlled breaks, or the
> other features break. Granted, the experience I have, has only been with a
> handful of versions of a single compiler, but because it seems to kill
> things in new and interesting ways in a variety of settings, I begin to
> wonder if the feature is just simply not reliable in its current design.

Well, I can only speak from my experience (several versions of GNAT), but I
have never had a problem with Controlled types.

Which features "break" when you use Controlled?

Re: List container strawman

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> Well, I can only speak from my experience (several versions of
> GNAT), but I have never had a problem with Controlled types.
> 
> Which features "break" when you use Controlled?

I don't remember the exact details, but I see a remark in the BC's
release notes:
  Iterators are visibly Controlled. The Controlled bit is because of
  work on synchronized forms, and the visible bit is because of a GNAT
  3.13 problem with finalization when using a function return value to
  initialize a classwide value.

.. GNAT's WITH TYPE sometimes fails when you have a record which
contains a field of a WITH TYPE IS ACCESS type and a field of a
controlled type and you create an access type for the record and you
try to use a non-standard storage pool ..

.. like Ted said, it can take some poking at extreme cases to get this
stuff to show!

Re: List container strawman

[Ted Dennison]

[-- Attachment #1: Type: text/plain, Size: 337 bytes --]

Ted Dennison wrote:

> Ted Dennison wrote:
> 
>> a postitive direction. It is attached here, and available on my 
>> website at
> 
> Whoops. No, it wasn't. That was probably for the best, as Newsranger 
> likes to hose formatting. It is attached here (posted w/ Mozilla).


(sigh)

My aplogies for posting HTML. Here's the text file.




[-- Attachment #2: containers-lists-unbounded.ads --]
[-- Type: text/plain, Size: 5343 bytes --]

-------------------------------------------------------------------------------
-- This file contains a proposal for a standard Ada list package.
--
-- version - Strawman 1.0
-------------------------------------------------------------------------------
generic
   type Element is private;
package Containers.Lists.Unbounded is

   -----------------------------------------------------------------------------
   -- The list type. I know the name's a bit redundant, but it doesn't look too
   -- bad, and any fully-named use will have to have a different name for the
   -- package anyway.
   -----------------------------------------------------------------------------
   type List is private;

   -----------------------------------------------------------------------------
   -- List construction operations. The returned list will contain *copies* of
   -- all the elements in the source lists, so these routines could get
   -- time-consuming. However, they should be useful for Lisp-like processing.
   --
   -- I considered using unary minus ("-") for the "Construct" routine, but
   -- that's not a common idiom right now.
   -----------------------------------------------------------------------------
   function "&" (Left, Right : Element) return List;
   function "&" (Left : Element; Right : List) return List;
   function "&" (Left : List; Right : Element) return List;
   function "&" (Left, Right : List) return List;
   function Construct (Initial_Element : Element) return List;

   -----------------------------------------------------------------------------
   -- "push" and "pop" operations.
   -----------------------------------------------------------------------------
   procedure Push_Front (Target : in out List; New_Element : in     Element);
   procedure Pop_Front  (Target : in out List; Old_Element :    out Element);
   procedure Push_Back  (Target : in out List; New_Element : in     Element);
   procedure Pop_Back   (Target : in out List; Old_Element :    out Element);

   -----------------------------------------------------------------------------
   -- Non-modifying query operations.
   -----------------------------------------------------------------------------
   function Is_Empty (Subject : List) return Boolean;
   function Size     (Subject : List) return Natural;
   function Front    (Subject : List) return Element;
   function Back     (Subject : List) return Element;

   -----------------------------------------------------------------------------
   -- I'm not too sure how useful these are, since they have to work on global
   -- data.
   -----------------------------------------------------------------------------
   generic
      with procedure Operation (Target : in out Element);
   procedure Closure_Operation (Target : in out List);

   -----------------------------------------------------------------------------
   -- Iteration routines. Next and Previous raise No_More if there is no item in
   -- the given direction. For an empty list, First = Last. As written, a
   -- typical iteration idiom would look like:
   --
   --    i := My_Lists.First (My_List);
   --    loop
   --       do stuff with My_Lists.Item(i);
   --       exit when i = My_Lists.Last (My_List);
   --       i := My_Lists.Next (i);
   --    end loop;
   --
   -- Another alternative using exception handling would be:
   --
   --    declare
   --       i := My_Lists.First (My_List);
   --    begin
   --       loop
   --          do stuff with My_Lists.Item(i);
   --          i := My_Lists.Next (i);
   --       end loop;
   --    exception
   --       when My_Lists.No_More =>
   --          null;
   --    end;
   --
   -- A third alternative using "Size" would be:
   --
   --  i := My_Lists.First (My_List);
   --  for iteration_count in 1..My_Lists.Size (My_List) loop
   --    do stuff with My_Lists.Item (i);
   --    i := My_Lists.Next (i);
   --  end loop;
   --
   -----------------------------------------------------------------------------
   type Iterator is private;
   No_More : exception;

   function First    (Subject : List)      return Iterator;
   function Last     (Subject : List)      return Iterator;
   function Next     (Location : Iterator) return Iterator;
   function Previous (Location : Iterator) return Iterator;
   function Item     (Location : Iterator) return Element;

   -- Ideally this routine would verify that Location was issued for the Subject
   -- list and is still valid, but that would be tough to enforce. Better to call
   -- such misuse a "bounded error", or somesuch.
   procedure Remove   (Subject : in out List; Location : Iterator);

   -----------------------------------------------------------------------------
   -- Sorting routine.
   -- To sort in increasing order, use the ">" routine for the Reverse_Order
   -- parameter. To sort in decreasing order, substitute your "<" routine for
   -- the Reverse_Order parameter. :-)
   -----------------------------------------------------------------------------
   generic
      with function Reverse_Order (Left, Right : in Element) return Boolean;
   procedure Sort (Subject : in out List);

private
   -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
   type List is new Boolean;
   type Iterator is new Boolean;

end Containers.Lists.Unbounded;

Re: List container strawman

[Larry Kilgallen]

In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
> This is a multi-part message in MIME format.
> --------------060706040909060005070802
> Content-Type: text/plain; charset=us-ascii; format=flowed
> Content-Transfer-Encoding: 7bit
> 
> Ted Dennison wrote:
> 
>> Ted Dennison wrote:
>> 
>>> a postitive direction. It is attached here, and available on my 
>>> website at
>> 
>> Whoops. No, it wasn't. That was probably for the best, as Newsranger 
>> likes to hose formatting. It is attached here (posted w/ Mozilla).
> 
> 
> (sigh)
> 
> My aplogies for posting HTML. Here's the text file.
> 
> 
> 
> 
> --------------060706040909060005070802
> Content-Type: text/plain;
>  name="containers-lists-unbounded.ads"
> Content-Transfer-Encoding: 7bit
> Content-Disposition: inline;
>  filename="containers-lists-unbounded.ads"

So why _do_ you continue to post HTML if you know it is undesired ?

But thanks for _finally_ changing to a reasonable title.

Re: List container strawman

[Ted Dennison]

In article <TOPqAssaO5$l@eisner.encompasserve.org>, Larry Kilgallen says...
>
>So why _do_ you continue to post HTML if you know it is undesired ?

Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought
posting it as a text attachment would make it text. I guess I should have posted
it to alt.text first.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Preben Randhol]

On Fri, 02 Nov 2001 15:09:39 GMT, Ted Dennison wrote:
> Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought
> posting it as a text attachment would make it text. I guess I should have posted
> it to alt.text first.
        ^^^^^^^^
        alt.test I hope? ;-)

Preben
-- 
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: List container strawman

[David Starner]

On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote:
> In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>> --------------060706040909060005070802
>> Content-Type: text/plain;
>>  name="containers-lists-unbounded.ads"
>> Content-Transfer-Encoding: 7bit
>> Content-Disposition: inline;
>>  filename="containers-lists-unbounded.ads"
> 
> So why _do_ you continue to post HTML if you know it is undesired ?

That's not HTML; that's MIME.   

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I saw a daemon stare into my face, and an angel touch my breast; each 
one softly calls my name . . . the daemon scares me less."
- "Disciple", Stuart Davis

Re: List container strawman

[Larry Kilgallen]

In article <9rv0qq$8i41@news.cis.okstate.edu>, David Starner <dvdeug@x8b4e53cd.dhcp.okstate.edu> writes:
> On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote:
>> In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>>> --------------060706040909060005070802
>>> Content-Type: text/plain;
>>>  name="containers-lists-unbounded.ads"
>>> Content-Transfer-Encoding: 7bit
>>> Content-Disposition: inline;
>>>  filename="containers-lists-unbounded.ads"
>> 
>> So why _do_ you continue to post HTML if you know it is undesired ?
> 
> That's not HTML; that's MIME.   

Correct.

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> -- This file contains a proposal for a standard Ada list package.

This is NOT a list. A list allows insertions at any point in the
sequence. This is a dequeue.

> --
> -- version - Strawman 1.0
> -------------------------------------------------------------------------------
> generic
>    type Element is private;

This specifies that the package requires "=" for Element. I see no need
for "=" in implementing a dequeue. The generic formal part is improperly
specified.

> package Containers.Lists.Unbounded is
> 
>    -----------------------------------------------------------------------------
>    -- The list type. I know the name's a bit redundant, but it doesn't look too
>    -- bad, and any fully-named use will have to have a different name for the
>    -- package anyway.
>    -----------------------------------------------------------------------------
>    type List is private;

This either needs to be limited private or a controlled type. Since this
is an unbounded dequeue, assignment of one dequeue to another will
result in sharing the internal structure implementing the source
dequeue.

What are the time/space implications for the operations. For example, is
Size O(1) or O(N)?

> 
>    -----------------------------------------------------------------------------
>    -- List construction operations. The returned list will contain *copies* of
>    -- all the elements in the source lists, so these routines could get
>    -- time-consuming. However, they should be useful for Lisp-like processing.
>    --
>    -- I considered using unary minus ("-") for the "Construct" routine, but
>    -- that's not a common idiom right now.
>    -----------------------------------------------------------------------------
>    function "&" (Left, Right : Element) return List;
>    function "&" (Left : Element; Right : List) return List;
>    function "&" (Left : List; Right : Element) return List;
>    function "&" (Left, Right : List) return List;
>    function Construct (Initial_Element : Element) return List;

I suggest Make rather than Construct.

> 
>    -----------------------------------------------------------------------------
>    -- "push" and "pop" operations.
>    -----------------------------------------------------------------------------
>    procedure Push_Front (Target : in out List; New_Element : in     Element);
>    procedure Pop_Front  (Target : in out List; Old_Element :    out Element);
>    procedure Push_Back  (Target : in out List; New_Element : in     Element);
>    procedure Pop_Back   (Target : in out List; Old_Element :    out Element);

What happens if you Pop from an empty list?

> 
>    -----------------------------------------------------------------------------
>    -- Non-modifying query operations.
>    -----------------------------------------------------------------------------
>    function Is_Empty (Subject : List) return Boolean;
>    function Size     (Subject : List) return Natural;
>    function Front    (Subject : List) return Element;
>    function Back     (Subject : List) return Element;
> 
>    -----------------------------------------------------------------------------
>    -- I'm not too sure how useful these are, since they have to work on global
>    -- data.

They are global to Operation, but they are no more global to the client
code than are any variables used in the "do stuff" part of your examples
below.

>    -----------------------------------------------------------------------------
>    generic
>       with procedure Operation (Target : in out Element);
>    procedure Closure_Operation (Target : in out List);

This is an iterator and should be so named ("Iterate"). I recommend
adding a Quit or Continue out Boolean parameter to Operation to allow
the client to terminate the iteration early.

> 
>    -----------------------------------------------------------------------------
>    -- Iteration routines. Next and Previous raise No_More if there is no item in
>    -- the given direction. For an empty list, First = Last. As written, a
>    -- typical iteration idiom would look like:
>    --
>    --    i := My_Lists.First (My_List);
>    --    loop
>    --       do stuff with My_Lists.Item(i);
>    --       exit when i = My_Lists.Last (My_List);
>    --       i := My_Lists.Next (i);
>    --    end loop;
>    --
>    -- Another alternative using exception handling would be:
>    --
>    --    declare
>    --       i := My_Lists.First (My_List);
>    --    begin
>    --       loop
>    --          do stuff with My_Lists.Item(i);
>    --          i := My_Lists.Next (i);
>    --       end loop;
>    --    exception
>    --       when My_Lists.No_More =>
>    --          null;
>    --    end;
>    --
>    -- A third alternative using "Size" would be:
>    --
>    --  i := My_Lists.First (My_List);
>    --  for iteration_count in 1..My_Lists.Size (My_List) loop
>    --    do stuff with My_Lists.Item (i);
>    --    i := My_Lists.Next (i);
>    --  end loop;
>    --
>    -----------------------------------------------------------------------------

This is really ugly. Why should the client have to include all this
framing code every time he uses an iterator? The passive iterator
(generic) given above does the same thing without all this extra client
code, and allows the value stored in the dequeue to be changed as well.

>    type Iterator is private;
>    No_More : exception;
> 
>    function First    (Subject : List)      return Iterator;
>    function Last     (Subject : List)      return Iterator;
>    function Next     (Location : Iterator) return Iterator;
>    function Previous (Location : Iterator) return Iterator;
>    function Item     (Location : Iterator) return Element;
> 
>    -- Ideally this routine would verify that Location was issued for the Subject
>    -- list and is still valid, but that would be tough to enforce. Better to call
>    -- such misuse a "bounded error", or somesuch.

This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
an example.

>    procedure Remove   (Subject : in out List; Location : Iterator);

Using a given Iterator value, what is the value of Next or Previous
after Remove? How about Item? What about when you remove the first or
last Elements in the dequeue?

> 
>    -----------------------------------------------------------------------------
>    -- Sorting routine.
>    -- To sort in increasing order, use the ">" routine for the Reverse_Order
>    -- parameter. To sort in decreasing order, substitute your "<" routine for
>    -- the Reverse_Order parameter. :-)
>    -----------------------------------------------------------------------------

This seems ugly and easy to get wrong. Why not import "<" and specify
that after calling Sort, the Elements in Subject will be in order
according to "<"? Then the meaning of the imported function is clear
without such a comment.

>    generic
>       with function Reverse_Order (Left, Right : in Element) return Boolean;
>    procedure Sort (Subject : in out List);
> 
> private
>    -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
>    type List is new Boolean;
>    type Iterator is new Boolean;
> 
> end Containers.Lists.Unbounded;

-- 
Jeffrey Carter

Re: List container strawman

[Ted Dennison]

In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> 
>> -- This file contains a proposal for a standard Ada list package.
>
>This is NOT a list. A list allows insertions at any point in the
>sequence. This is a dequeue.

Ahhh. I *knew* I forgot a routine. :-) I'll add Insert next to Remove.


>This either needs to be limited private or a controlled type. Since this
>is an unbounded dequeue, assignment of one dequeue to another will
>result in sharing the internal structure implementing the source
>dequeue.

Right again.

>What are the time/space implications for the operations. For example, is
>Size O(1) or O(N)?

That's something we should most certianly discuss (for all these ops). I'd be
for specifying that Size *should* be O(1), which implies that it will be kept
with the main list structure rather than calculated at every Size call.

>I suggest Make rather than Construct.

Fair enough. I'm used to seeing "make" in terms of GNU make, but the term
"Construct" has a fair bit of baggage too. Do we have a second on this motion?

>What happens if you Pop from an empty list?

Good catch. I'll add an exception for that.

(talking about the Closure_Operation generic's Operation procedure parameter)
>They are global to Operation, but they are no more global to the client
>code than are any variables used in the "do stuff" part of your examples
>below.

True. I'm so used to avioding using globals in routines that its tough to
retrain my thinking in this case. But I guess its OK, since you can instantiate
this generic at any level you choose. Thus it could still be data local to the
calling subroutine, but "global" to Operation.

>>    generic
>>       with procedure Operation (Target : in out Element);
>>    procedure Closure_Operation (Target : in out List);
>
>This is an iterator and should be so named ("Iterate"). I recommend
>adding a Quit or Continue out Boolean parameter to Operation to allow
>the client to terminate the iteration early.

Both seem like good suggestions. I'll work on it.

>>    -- Iteration routines. Next and Previous raise No_More if there is no 
>This is really ugly. Why should the client have to include all this
>framing code every time he uses an iterator? The passive iterator
>(generic) given above does the same thing without all this extra client
>code, and allows the value stored in the dequeue to be changed as well.

I messed that interface up a bit, so I'd appreciate it if you would look over
the next version and reconsider your comment. It does clean it up a bit. Also
note that to use the passive iterator, you need a generic instantiation and a
custom Operation routine, both of which this solution does not require. I think
most folks would at least find it a wash.

Even if it isn't as nice as the passive iterator, I think it is still needed, as
that is how Insert and Remove (your middle of the list operations) are
performed.

>This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
>an example.

Hmmm. Yeah, I guess one could keep a copy of the address of the list around,
assuming that it is implemented in a way in which that makes sense. That still
doesn't prevent further operations from invalidating your iterator. To detect
that, you'd need to somehow keep track of every iterator issued along with the
list (in a little mini-list inside it) %-( .

>
>>    procedure Remove   (Subject : in out List; Location : Iterator);
>
>Using a given Iterator value, what is the value of Next or Previous
>after Remove? How about Item? What about when you remove the first or
>last Elements in the dequeue?

Yet another good catch (one would think you've done this before ;-) ). I'd say
that:

o  The mode for "Location" should be "in out" so it won't be invalid afterwards.
o  If Location=First, then Location will be set to the new First.
o  If Location=Last, then Location will be set to Done_Iterating.
o  If Location=Done_Iterating, then No_Item will be raised.
o  otherwise, Location will be set to what Next was previously (the next element
after the removal).



>
>> 
>>    -----------------------------------------------------------------------------
>>    -- Sorting routine.
>>    -- To sort in increasing order, use the ">" routine for the Reverse_Order
>>    -- parameter. To sort in decreasing order, substitute your "<" routine for
>>    -- the Reverse_Order parameter. :-)
>>    -----------------------------------------------------------------------------
>
>This seems ugly and easy to get wrong. Why not import "<" and specify
>that after calling Sort, the Elements in Subject will be in order
>according to "<"? Then the meaning of the imported function is clear
>without such a comment.

I started with that, but it wasn't clear to *me* when I read it back to myself.
(Hint: which end of the list is on the "left"?) Admittedly, I'm not always the
perfect judge of such things though. Does anyone else think that would be
clearer?

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Even if it isn't as nice as the passive iterator, I think it is still needed, as
> that is how Insert and Remove (your middle of the list operations) are
> performed.

OK. Then this isn't really an iterator type; it's the "Position" type
that indicates where in the list you're operating. Now this is starting
to look like a list, except I expect to see the general operations
(obtain a Position for a list and operate on a specific Position within
a list) first, with the bells and whistles later.

> 
> >This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
> >an example.
> 
> Hmmm. Yeah, I guess one could keep a copy of the address of the list around,
> assuming that it is implemented in a way in which that makes sense. That still
> doesn't prevent further operations from invalidating your iterator. To detect
> that, you'd need to somehow keep track of every iterator issued along with the
> list (in a little mini-list inside it) %-( .

The technique used by PragmARC.List_Unbounded_Unprotected is that the
list object contains a pointer to a "mini-node" (a node with no data
stored in it). This makes insertions and deletions at the beginning and
end of the list look exactly the same as insertions and deletions in the
middle, but it also follows that the value of this pointer is unique to
the list object. Call this value the list ID. Every node in the list
contains a copy of this ID, as does every Position value generated for
the list. An operation is not permitted unless the IDs for the list,
position, and node match. When a node is deleted, its ID is invalidated
(set to null), and the position used to delete the node is similarly
invalidated (both its ID and pointer are set to null). If a client makes
a copy of a Position and uses one to delete a node, he cannot then
manipulate the deallocated node through the other since it has an
invalid ID. Easy to implement and fairly foolproof.

> 
> >
> >>    procedure Remove   (Subject : in out List; Location : Iterator);
> >
> >Using a given Iterator value, what is the value of Next or Previous
> >after Remove? How about Item? What about when you remove the first or
> >last Elements in the dequeue?
> 
> Yet another good catch (one would think you've done this before ;-) ). I'd say
> that:
> 
> o  The mode for "Location" should be "in out" so it won't be invalid afterwards.
> o  If Location=First, then Location will be set to the new First.
> o  If Location=Last, then Location will be set to Done_Iterating.
> o  If Location=Done_Iterating, then No_Item will be raised.
> o  otherwise, Location will be set to what Next was previously (the next element
> after the removal).

Now that I know that this is standard list manipulation, not iteration,
I'd recommend calling it Delete. It's also a lot simpler to make
Location in out and invalidate it.

There should probably be an Update procedure that changes the Element
stored at a location.

> >>    -----------------------------------------------------------------------------
> >>    -- Sorting routine.
> >>    -- To sort in increasing order, use the ">" routine for the Reverse_Order
> >>    -- parameter. To sort in decreasing order, substitute your "<" routine for
> >>    -- the Reverse_Order parameter. :-)
> >>    -----------------------------------------------------------------------------
> >
> >This seems ugly and easy to get wrong. Why not import "<" and specify
> >that after calling Sort, the Elements in Subject will be in order
> >according to "<"? Then the meaning of the imported function is clear
> >without such a comment.
> 
> I started with that, but it wasn't clear to *me* when I read it back to myself.
> (Hint: which end of the list is on the "left"?) Admittedly, I'm not always the
> perfect judge of such things though. Does anyone else think that would be
> clearer?

A list is a sequence; it has a first Element, a second Element, and so
on. The postcondition here is that for any 2 valid locations L1 and L2
such that L1 /= L2 and L2 = Next (L1),

not (Item (L2) < Item (L1) ).

-- 
Jeffrey Carter

Re: List container strawman

[Ted Dennison]

In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says...
>The technique used by PragmARC.List_Unbounded_Unprotected is that the
>list object contains a pointer to a "mini-node" (a node with no data
>stored in it). This makes insertions and deletions at the beginning and
>end of the list look exactly the same as insertions and deletions in the
>middle, but it also follows that the value of this pointer is unique to
>the list object. Call this value the list ID. Every node in the list
>contains a copy of this ID, as does every Position value generated for
>the list. An operation is not permitted unless the IDs for the list,
>position, and node match. When a node is deleted, its ID is invalidated
>(set to null), and the position used to delete the node is similarly
>invalidated (both its ID and pointer are set to null). If a client makes
>a copy of a Position and uses one to delete a node, he cannot then
>manipulate the deallocated node through the other since it has an
>invalid ID. Easy to implement and fairly foolproof.

So you are saying that you are placing values into the memory before it is
deallocated, in the hopes that any code trying to access it through a stale
pointer will still find that value there (telling it not to use this)?

What if:
a) The memory at that location gets reallocated to something else in the
meantime, which then puts what looks like a valid value in there.

b) The OS marks that location as not allocated, and issues a segfault (or
whatever) when you try to access it.

>Now that I know that this is standard list manipulation, not iteration,
>I'd recommend calling it Delete. It's also a lot simpler to make
>Location in out and invalidate it.

That could be done. "Delete" would also be a natural name for toasting a list,
but then I guess in the current scheme "-" would make more sense for that.

>There should probably be an Update procedure that changes the Element
>stored at a location.

That sounds right.


---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says...
> >The technique used by PragmARC.List_Unbounded_Unprotected is that the
> >list object contains a pointer to a "mini-node" (a node with no data
> >stored in it). This makes insertions and deletions at the beginning and
> >end of the list look exactly the same as insertions and deletions in the
> >middle, but it also follows that the value of this pointer is unique to
> >the list object. Call this value the list ID. Every node in the list
> >contains a copy of this ID, as does every Position value generated for
> >the list. An operation is not permitted unless the IDs for the list,
> >position, and node match. When a node is deleted, its ID is invalidated
> >(set to null), and the position used to delete the node is similarly
> >invalidated (both its ID and pointer are set to null). If a client makes
> >a copy of a Position and uses one to delete a node, he cannot then
> >manipulate the deallocated node through the other since it has an
> >invalid ID. Easy to implement and fairly foolproof.
> 
> So you are saying that you are placing values into the memory before it is
> deallocated, in the hopes that any code trying to access it through a stale
> pointer will still find that value there (telling it not to use this)?

That's right. You don't get 100% confidence, but it's better than the
nothing that most lists provide.

> 
> What if:
> a) The memory at that location gets reallocated to something else in the
> meantime, which then puts what looks like a valid value in there.

It's certainly possible that the memory could be reallocated to the same
list, so the dangling reference becomes valid again. I did say *fairly*
foolproof. :)

> 
> b) The OS marks that location as not allocated, and issues a segfault (or
> whatever) when you try to access it.

Then you're no worse off than without the check.

> That could be done. "Delete" would also be a natural name for toasting a list,
> but then I guess in the current scheme "-" would make more sense for that.

Let me record my vote against unary operators as primary names. I
probably won't object if they're renames of other subprograms. I suggest
Clear for deleting all Elements in a List; Make_Empty might also be
acceptable.

Finally, what you're calling an iterator is what is usually called a
"position within a list" in discussing lists as an abstraction, and the
manipulation of a list is usually defined in terms of positions. I think
it would make the package easier to understand if it adheres to this
convention: call the type Position and present the operations for
obtaining positions and using them to manipulate a list before the
dequeue- and string-like operations.

-- 
Jeff Carter
"I fart in your general direction."
Monty Python & the Holy Grail

Re: List container strawman

[Darren New]

Jeffrey Carter wrote:
> > a) The memory at that location gets reallocated to something else in the
> > meantime, which then puts what looks like a valid value in there.
> 
> It's certainly possible that the memory could be reallocated to the same
> list, so the dangling reference becomes valid again. I did say *fairly*
> foolproof. :)

If you really want it to be foolproof, then for each "Location" pointer,
you keep a pointer to the list, a pointer to the element being indexed,
and a list number counter. In each list head, you keep a list number
counter, a counter of the number of Location pointers outstanding, and
the head and tail of the list.

Creating a Location copies the list number counter into the Location
record and otherwise initializes it. It also increments the reference
count in the List head. Deleting a Location decrements the ref count in
the list head. Deleting the list is defered (via finalization) until the
reference count goes to zero.

Each access to the pointer in the Location can run thru the linked list
that the Location claims it points to, to make sure the node it points
to is still on the list. This makes indirection become O(N) instead of
O(1), but it's also the kind of check that would be easy to turn on and
off at runtime, let alone compile time.

Did this for a Pascal compiler, so students using dangling pointers
would be told that instead of just dumping core.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman

[Larry Kilgallen]

In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:

> If you really want it to be foolproof,

Yes please.

Re: List container strawman

[Darren New]

> > If you really want it to be foolproof,
> Yes please.

Well, yes. However, the performance overhead can be significant. There
are ways of reducing it (see, for example, some of the fields in the
private structures in my offering) but to be 100% bullet-proof, you'd at
least need to have O(N) access times. Given user-programmable and
multiple storage pools, this would be harder than in Pascal. The trick
is to make it so you can turn it on and off at runtime, or for only a
particular type of list (i.e., particular instantiations) so you can
narrow down the problem.

Actually, I never really thought of it with user-definable storage
pools. There may be a much more efficient way of working it.

A couple other points:
1) Does Ada even ensure there's only one default storage pool? I would
think that perhaps the storage pool for Integers might be different than
the storage pool for big records.... perhaps a different storage pool
for each size item being stored or some such? Hence, I'm not surprised
that it's difficult to find out what the "default" storage pool is. Or
am I wrong in this?

2) Perhaps using terms from Unbounded_String might be wise? I.e., stuff
that treats an unbounded string as an array of elements that happen to
be characters rather than relying on the fact that they're characters.
Ie., calling the routines Element(), Replace_Element(), Slice(),
Overwrite(), Delete(), "*", etc?  This isn't what I think of as the best
naming convention, but it's at least going to be familiar to other Ada
programmers.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman

[ramatthews]

In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote:
> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:
> 
>> If you really want it to be foolproof,
> 
> Yes please.


While I see a foolproof list does not have universal appeal I have
been successfully using one for some time so I thought its 
specification would help discussions.

Robert Matthews

-----------------------------------------------------
with Ada.Finalization;
with Ada.IO_Exceptions;
with Ada.Streams;
with Ada.Tags;

generic
   type Data_Type (<>) is private;
package Containers.Lists.Unbounded is

   --  This package provides facilities for manipulating simple list structures.
   --
   --  A list is an ordered sequence of data elements. It can also be empty,
   --  containing no data elements.
   --
   --  Client software creates an empty list by declaring a variable of type
   --  List_Type. Data elements can then be added to the list via the subprograms
   --  Prepend and Append. Note that data is copied into the list - pointers are not
   --  retained to the original data.
   --
   --  All data elements can be removed from a list via subprogram Delete_All.
   --  Applying this subprogram to an already empty list will have no effect.
   --
   --  When applied to an empty list, Is_Empty will return True, otherwise it will
   --  return False.
   --
   --  A list can be assigned to another. The target list will be emptied then loaded with
   --  a copy of each data element in the source list. The copying will be done such that
   --  the ordering of the data elements in each list will be the same.
   --  Note that if the source list is empty, then the target will be set empty.
   --
   --  Two lists can be compared for equality. To be equal they must have equal data elements
   --  at corresponding positions. Two empty lists are considered equal.
   --
   --  The elements in a list can be accessed via an enumerator: the client software
   --  declares a variable of type Enumerator_Type which it then attaches to a list via
   --  the function New_Enumerator.
   --
   --  At any one time an enumerator denotes a single element in its associated list. This
   --  element is termed the "current" element. Initially current will be set to the first
   --  element in the list; the following subprograms allow current to move to a different
   --  element: Goto_Next, Goto_Previous, Goto_First, Goto_Last.
   --
   --  The following subprograms allow an enumerator's current element to be retrieved,
   --  changed, or deleted: Current, Update, Delete. Note that after Delete, current
   --  still denotes the same point in the list, even though the associated data
   --  element no longer exists.
   --
   --  The subprogram Insert allows a new data element to be added to the list either
   --  before or after the current element. Note that if the list is empty then this
   --  subprogram will still insert the data even though current does not exist.
   --  Alternatively if current has been deleted then Insert will insert the data at
   --  the point in the list from which current was deleted.
   --  After the insertion, current will be set to the new data element.
   --
   --  When current is at the start of a list, Is_First will return True,
   --  otherwise it will return False.
   --  When current is at the end of a list,   Is_Last  will return True,
   --  otherwise it will return False.
   --
   --  If current exists Current_Exists will return True, otherwise it will return False
   --  (current will not exist if the element denoted by current has been deleted, or if
   --  the associated list is empty).
   --
   --  If the list associated with an enumerator exists List_Exists will return True, otherwise
   --  it will return False (a list can cease to exist if the list's variable goes out of scope).
   --
   --  An enumerator can be assigned to another enumerator. The target enumerator will then
   --  be associated with the same list and denote the same current element. Note that
   --  if the source enumerator's list and/or current do not exist then these characteristics
   --  will be transferred to the target enumerator.
   --
   --  Two enumerators can be compared for equality. They must be associated with the same
   --  list and their current elements must be the same element. Note that two enumerators whose
   --  lists do not exist are deemed equal. Also two enumerators whose lists exist but whose current
   --  elements do not, are deemed equal if:
   --   1) the lists are the same and empty; or
   --   2) the lists are the same and non-empty, and each current denotes the same point in the list.
   --
   --  Note that two or more enumerators can change the same list; changes made via one enumerator
   --  will be visible to the other enumerators. Similarly changes made directly to a list will be
   --  visible to its enumerators. However, concurrent access from more than one task is not supported;
   --  concurrent access may well lead to list and enumerator corruption.
   --
   --  Note also that the storage associated with lists and enumerators is automatically deallocated
   --  when their variables go out of scope.
   --
   --  Stream input/output can be used with lists via the stream oriented attributes List_Type'Write
   --  and List_Type'Read.
   --  For the Write attribute, each data element in the list is sent to the stream via
   --  Data_Type'Output.
   --  For the Read attribute, data elements are extracted from the stream (via Data_Type'Input)
   --  and inserted into the list. Note that any data elements previously in the list will be deleted.
   --  Note also that an empty list will be suitably flagged in the stream data, and so will be
   --  correctly handled when read back in.
   --
   --
   --  When applied to an empty list, the following will raise No_Data:
   --   Goto_First, Goto_Last, Goto_Next, Goto_Previous, Is_First, Is_Last.
   --
   --  When current is the last  data element in a list, Goto_Next     will raise No_Data.
   --  When current is the first data element in a list, Goto_Previous will raise No_Data.
   --
   --  When current does not exist, the following will raise No_Data:
   --   Delete, Current, Update.
   --
   --  When an enumerator's list does not exist, the following will raise No_List:
   --   Insert, Delete, Current, Update, Goto_First, Goto_Last, Goto_Next, Goto_Previous,
   --   Is_First, Is_Last, Current_Exists, Is_Empty[Enumerator_Type].
   --
   --  When the stream I/O attributes are used, the following exceptions may be raised:
   --    Device_Error, Data_Error, Constraint_Error, Tag_Error, End_Error and Mode_Error.
   --  See the Ada Reference Manual for details.
   --
   ------------------------------------------------------------------------------------------------

   type List_Type       is tagged private;
   type Enumerator_Type is        private;

   --  Subprograms for directly dealing with lists...

   procedure Prepend       (List  : in out List_Type; Data : in Data_Type);   -- Insert data at start of list.
   procedure Append        (List  : in out List_Type; Data : in Data_Type);   -- Insert data at end of list.
   procedure Delete_All    (List  : in out List_Type);                        -- Delete all data from list.

   function  Is_Empty      (List  : in     List_Type) return Boolean;
   function  "="           (Left  : in     List_Type;                   -- Check lists have equal.
                            Right : in     List_Type) return Boolean;   -- elements at matching positions.

   function New_Enumerator (List  : in     List_Type'Class) return Enumerator_Type;
   --  Enumerator will denote the list and its current will be the first in the list.

   --  Note: can also assign list to list: target list will contain a copy of all the elements in the source
   --  list, with each element and its copy having the same position in their respective lists.
   ----------------------------------------------------------------------

   --  Subprograms for dealing with the current element of an enumerator...

   type Position_Type is (Before_Current, After_Current);

   procedure Insert         (Enumerator : in out Enumerator_Type;
                                   Data : in Data_Type;
                                   Position : in Position_Type);
   procedure Delete         (Enumerator : in     Enumerator_Type);
   function  Current        (Enumerator : in     Enumerator_Type) return Data_Type; 

   procedure Update         (Enumerator : in out Enumerator_Type; Data : in Data_Type);
   --  Update current element.
   --  Note that if new data is larger, then new data will be loaded into a new element that replaces
   --  the old in the list. The location in the list will not have changed but current will now denote
   --  that new data element - hence the in out mode.

   procedure Goto_First     (Enumerator : in out Enumerator_Type); 
   procedure Goto_Last      (Enumerator : in out Enumerator_Type);
   procedure Goto_Next      (Enumerator : in out Enumerator_Type);
   procedure Goto_Previous  (Enumerator : in out Enumerator_Type);

   function  Is_First       (Enumerator : in     Enumerator_Type) return Boolean;
   function  Is_Last        (Enumerator : in     Enumerator_Type) return Boolean;

   function  Current_Exists (Enumerator : in     Enumerator_Type) return Boolean;
   function  List_Exists    (Enumerator : in     Enumerator_Type) return Boolean;

   function  Is_Empty       (Enumerator : in     Enumerator_Type) return Boolean;
   -- Is the associated list empty.


   function  "="            (Left       : in     Enumerator_Type; 
                             Right      : in     Enumerator_Type) return Boolean;

   --  Note: can also assign enumerator to enumerator: target will denote same list
   --  and have same current as source.
   --------------------------------------------------------

   --  The subprograms can raise the following exceptions:

   No_Data      : exception;
   No_List      : exception;
   
   --  And for stream I/O...
   
   Device_Error : exception renames Ada.IO_Exceptions.Device_Error;
   Data_Error   : exception renames Ada.IO_Exceptions.Data_Error;
   End_Error    : exception renames Ada.IO_Exceptions.End_Error;
   Mode_Error   : exception renames Ada.IO_Exceptions.Mode_Error;
   Tag_Error    : exception renames Ada.Tags.Tag_Error;
   --  Also Constraint_Error may be raised.

   ---------------------------------------------------

private
   type Data_Access_Type is access Data_Type;

   type Data_Envelope_Type;
   type Data_Envelope_Access_Type is access Data_Envelope_Type;

   type Enumerator_Envelope_Type;
   type Enumerator_Envelope_Access_Type is access Enumerator_Envelope_Type;

   type List_Header_Type;
   type List_Header_Access_Type is access List_Header_Type;

   type Data_Envelope_Type is record
      Data     : Data_Access_Type;
      Next     : Data_Envelope_Access_Type;
      Previous : Data_Envelope_Access_Type;
   end record;

   type List_Header_Type is
   record
      First       : Data_Envelope_Access_Type;
      Last        : Data_Envelope_Access_Type;
      Enumerators : Enumerator_Envelope_Access_Type;   -- Sub-list of enumerators attached to this List.
   end record;

   type List_Type is new Ada.Finalization.Controlled with
   record
      Header : List_Header_Access_Type;
   end record;

   procedure Initialize (List : in out List_Type);
   procedure Adjust     (List : in out List_Type);
   procedure Finalize   (List : in out List_Type);

   procedure List_Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in  List_Type);
   for List_Type'Write use List_Write;
   
   procedure List_Read  (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out List_Type);
   for List_Type'Read use List_Read;


   type Enumerator_Envelope_Type is
   record
      List_Header         : List_Header_Access_Type;           -- List that Enumerator applies to.
      Current             : Data_Envelope_Access_Type;         -- List element that Enumerator denotes.
      Next_Enumerator     : Enumerator_Envelope_Access_Type;   -- Enumerators are linked in their own sub-list,
      Previous_Enumerator : Enumerator_Envelope_Access_Type;   --  within the relevant List.
      Next_Data           : Data_Envelope_Access_Type;         -- List element that follows current.
      Previous_Data       : Data_Envelope_Access_Type;         -- List element that precedes current.
   end record;
   --  Note that in the above record, components Next_Data and Previous_Data duplicate the Next and Previous
   --  components of the record referenced by Current. This duplication is necessary for the case when Current
   --  is Null (ie. the corresponding data element has been deleted), Next_Data and Previous_Data then indicate
   --  where in the list the enumerator is.

   type Enumerator_Type is new Ada.Finalization.Controlled with
   record
      Header : Enumerator_Envelope_Access_Type;
   end record;

   procedure Initialize (Enumerator : in out Enumerator_Type);
   procedure Adjust     (Enumerator : in out Enumerator_Type);
   procedure Finalize   (Enumerator : in out Enumerator_Type);

end Containers.Lists.Unbounded;
-------------------------------------------------------------

Re: List container strawman

[Darren New]

ramatthews@tinuviel.com wrote:
> While I see a foolproof list does not have universal appeal I have
> been successfully using one for some time so I thought its
> specification would help discussions.

Heh. This looks almost exactly like what I came up with and posted
earlier. :-) Except you've actually written it. ;-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman

[Jeffrey Carter]

ramatthews@tinuviel.com wrote:
> 
> While I see a foolproof list does not have universal appeal I have
> been successfully using one for some time so I thought its
> specification would help discussions.

How does this extra complexity ensure that the list is foolproof? It is
not clear, for example, how this prevents updating a node through one
Position (which you call Enumerator_Type) that has been deleted through
another.

The initial block of comments is rather a lot to digest all at once, and
might be better distributed among the type and subprogram declarations
it refers to. The use of "current" by itself is a bit confusing; it
sounds as if it is a global property of a list, when actually it is a
property of a position within a list.

Overall, the package looks quite usable. I might suggest a default of
Before_Current in the Insert procedure.

-- 
Jeff Carter
"Sons of a silly person."
Monty Python & the Holy Grail

Re: List container strawman

[ramatthews]

In article <3BEA0F08.AD9AB7C1@acm.org>, Jeffrey Carter <jrcarter@acm.org> wrote:

> 
> How does this extra complexity ensure that the list is foolproof? It is
> not clear, for example, how this prevents updating a node through one
> Position (which you call Enumerator_Type) that has been deleted through
> another.
> 

> 


If two Positions (of Enumerator_Type) are denoting the same
element in a list and one is used to delete the element then
BOTH will return False to 'Current_Exists' and BOTH will raise
'No_Data' on using 'Update'.

This is ensured by the (behind the scenes) two-way linkage
between the list and all of its Positions.

As an aside, if I were re-implementing this I would use the
term 'Cursor' in place of 'Enumerator' - but then arguments
over names can go on for ever!

Robert Matthews.

Re: List container strawman

[Ted Dennison]

In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says...
>
>In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote:
>> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:
>> 
>>> If you really want it to be foolproof,
>> 
>> Yes please.
>
>
>While I see a foolproof list does not have universal appeal I have
>been successfully using one for some time so I thought its 
>specification would help discussions.

Yup. That does exactly what is needed to make it safe. I never said it was
impossible, just that its a lot of work, inculding some extra runtime work that
might not endear the facility to real-time users. One problem is that creating
an iterator with this facility involves dynamic allocation and linked-list
traversal. That violates our general principle of avoiding runtime vs. setup
overhead, but that could probably(?) be fixed or at least avoided by the user if
noted. Another issue is that it puts a controlled type in the generic package,
which I was trying to avoid so that it was instantiateable at lower levels.
However, it turned out that List has to be controlled anyway, so perahps this
isn't so bad.

I'm interested in what the general consensus is here. Should we do the extra
work to make iterators safe, given that this will have at least the following
effects:

o  Add extra dynamic memory operations to any list modification (there were some
there already).
o  Add a (usually small) internal list traversal to any element deletion.
o  Add a small validity check (or possibly two) to every iterator operation.
o  Possibly make iterator creation non-determistic (time-wise).
o  Possibly make iterator assignment non-deterministic. Note that functions are
currently used for iterating, so that would make just about any use of iterators
non-determinstic, unless procedure variants are introduced.

If there's a way to get rid of the last two "possibly"s (which there probably
is, but I don't know), I think I'd vote in favor of it. Otherwise I'd lean
against it just on the basis that I don't generaly go for one small
"nice-to-have" feature accounting for large amounts of the implmentation's code
and complexity, which is what would happen here.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says...
> > In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net
> >(Larry Kilgallen) wrote:
> >> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com>
> >>writes:
> >> 
> >>> If you really want it to be foolproof,
> >>  Yes please.
> >
> >
> >While I see a foolproof list does not have universal appeal I have been
> >successfully using one for some time so I thought its specification would
> >help discussions.
> 
> Yup. That does exactly what is needed to make it safe. I never said it was
> impossible, just that its a lot of work, inculding some extra runtime work
> that might not endear the facility to real-time users. One problem is that
> creating an iterator with this facility involves dynamic allocation and
> linked-list traversal. 

Why do you need dynamic allocation.  The pointer can be in the
iterator and put at the start of the list.  As most lists have few
iterators and when they have more than one, a majority of the uses are
nested the list traversal will be done only on list modifications.

> That violates our general principle of avoiding
> runtime vs. setup overhead, but that could probably(?) be fixed or at least
> avoided by the user if noted. Another issue is that it puts a controlled
> type in the generic package, which I was trying to avoid so that it was
> instantiateable at lower levels.  However, it turned out that List has to
> be controlled anyway, so perahps this isn't so bad.
> 
> I'm interested in what the general consensus is here. Should we do the
> extra work to make iterators safe, given that this will have at least the
> following effects:

I'm for.
 
> o Add extra dynamic memory operations to any list modification (there were
> some there already).  

I don't think so.

> o Add a (usually small) internal list traversal to any element
> deletion.

Agree.

> o Add a small validity check (or possibly two) to every iterator
> operation.

Agree.

> o Possibly make iterator creation non-determistic (time-wise).  

I don't think so. (Iterator deletion would be made non deterministic
if they are assigned in a non nested way and the iterator list is a
singly linked one).

> o Possibly make iterator assignment non-deterministic. 

Not if the iterator list is doubly linked.

-- 
Jean-Marc

Re: List container strawman

[Ted Dennison]

In article <3bec1cbe$0$15824$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>Why do you need dynamic allocation.  The pointer can be in the

The implementation he presented (a working one, I believe) had it. Since I've
only thought about it before, and he's actually implemented it, I'm assuming
there's some implementation reason he needed to do it that way that isn't
apparent just looking at a spec. Perhaps there isn't. That's what I'd like to
hear.

>> o Add extra dynamic memory operations to any list modification (there were
>> some there already).  
>
>I don't think so.

Hmmm. Yeah, your'e right. Its actually another one of those "ususally small"
internal list traversals. What will happen is that you have to check all other
iterators. But that's probably only nessecary when an item is deleted, which I
covered below.

>> o Add a (usually small) internal list traversal to any element
>> deletion.
>
>Agree.
>
>> o Add a small validity check (or possibly two) to every iterator
>> operation.
>
>Agree.
>
>> o Possibly make iterator creation non-determistic (time-wise).  
>
>I don't think so. (Iterator deletion would be made non deterministic
>if they are assigned in a non nested way and the iterator list is a
>singly linked one).

I said "probably" this for both the last bulletts because he implemented
iterators using accesses to controlled types. If it can be done on the stack,
then both these "possibly"s go away (and I would thus vote for it).

Perhaps it would be best if I could play with an implementation and see if its
doable. That would mean I'd have to tear myself away from Civ3 for a few hours
though...

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Nick Roberts]

I'm sorry, I'm throw one of classic spanners in the works here, but I'm
afraid I think you've got your approach horribly horribly wrong!

For a start, all this mularchy about insertion and deletion is just plain
silly! It really is. You don't need them, and shouldn't implement them. Yes,
really. Let me show you why.

Suppose you want to have a list of names (strings), and you want to
normalise them as follows:

(a) convert them all to uppercase;
(b) all beginning with "MACxy", where x is a letter, to have "MCxy" inserted
afterwards;
(c) all beginning with "?" to be deleted.

I'm going to frame the answer in terms of my own proposal, please forgive me
for that. The essential answer is that you don't keep a list of the strings,
but you keep a list of access values to them. You then simply build a new
list (of access values), and then delete the old one:

   with Ada.Characters.Handling; use Ada.Characters.Handling;
   ...
   type Name_Ref is access [all] String;
   package Name_Ref_Iteration is new Iteration(Name_Ref);

   procedure Normalize_Names (
      From: in out Name_Ref_Iteration.Sequence_Recorder'Class;
      Into: Name_Ref_Iteration.Sequence_Recorder'Class) is
      Ref: Name_Ref; N: Natural;
   begin
      Rewrite(Into); -- possibly redundant (possibly poor design, actually)
      Restart(From); -- ditto
      while not End_of_Data(From) loop
         Read(From,Ref);
         if Ref /= null and then Ref.all'Length > 0 and then
Ref(Ref.all'First) /= '?' then
            To_Upper(Ref.all);
            Write(Into,Ref);
            N := Ref.all.First-1; -- in case string doesn't start at 1
            if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then
Is_Letter(Ref(N+4)) then
               Write(Into, new String'("MC"&Ref(N+4..Ref.all'Last)));
            end if;
         else
            Ref := null; -- or maybe use Unchecked_Deallocation
         end if;
      end loop;
      Rewrite(From); -- erases it (again, possibly wrong here)
      Restart(Into); -- again possibly redundant
   end Normalize_Names;

Note how this procedure can be passed parameters of ANY 'sequence recorder'
container type (instantiated on Name_Ref), not just lists. Supposing we
wanted to use a list container type:

   package Name_Ref_Lists is new xyz.Lists(Name_Ref_Iteration);
   subtype Name_List is Name_Ref_Lists.List_Type;
   L1, L2: Name_List;
   ... set up L1 with names
   Normalize_Names(L1,L2);

A note about the Restarts and Rewrites: they are probably better left
outside procedures such as this, in fact. I have quietly deleted oddities
like null pointers: a real program should probably raise exceptions.

Trust me, guys, this approach is majorly better in every way (easier to use,
easier to read & understand, easier to implement, more memory efficient,
more speed efficient) than messing around with inserts and deletes, for the
vast majority of situations.

I know I can seem pompous, overbearing, etc., etc., especially about this
subject, but it pains me to see you going so far astray, and spending so
much time arguing about features that you don't need anyway!

It also gives me another opportunity to demonstrate the idea of having a set
of abstract container types, upon which operations (such as Normalize_Names)
can be hung, thus freeing you of: (1) having to worry about which container
type to use when writing the procedure; (2) the procedure shackling you to
one particular container type. Do you turn away from this Utopia? ;-)

--
Best wishes,
Nick Roberts

Re: List container strawman

[Ted Dennison]

In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says...
>For a start, all this mularchy about insertion and deletion is just plain
>silly! It really is. You don't need them, and shouldn't implement them. Yes,
>really. Let me show you why.

I'm not sure I understand this. It looks like you are talking about having the
users manage the internal details of all their own data structures, to which my
first reaction would be "ewwwww.". I'll admit there may be some interesting
possiblities I don't see in this though.

>It also gives me another opportunity to demonstrate the idea of having a set
>of abstract container types, upon which operations (such as Normalize_Names)
>can be hung, thus freeing you of: (1) having to worry about which container
>type to use when writing the procedure; (2) the procedure shackling you to
>one particular container type. Do you turn away from this Utopia? ;-)

But remember that one of our stipulations is essentially "no multilevel generic
instantiations required". Does this work that way? Without that restriction you
could do all sorts of cool things, as has been done in Booch and others. In that
enviroment I'd say that we already have plenty of players, and one of them is
liable to be perfectly suitable (although I suppose more are always welcome). I
don't want to discourage you from making the ultimate container library. But for
the purposes of what we are doing here it has to be very easy to use, and
frankly I couldn't figure out quite what was going on in the code you presented.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:L6dH7.20105$xS6.32596@www.newsranger.com...
> In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says...
> >For a start, all this mularchy about insertion and deletion is just plain
> >silly! It really is. You don't need them, and shouldn't implement them.
Yes,
> >really. Let me show you why.
>
> I'm not sure I understand this. It looks like you are talking about having
the
> users manage the internal details of all their own data structures, to
which my
> first reaction would be "ewwwww.". I'll admit there may be some
interesting
> possiblities I don't see in this though.

In general, of course, you want to hide details such as pointers. But don't
get carried away! Sometimes the application programmer has got to deal with
things like pointers.

In the example I gave, the fact that the list container was used to
(explicitly) contain pointers is likely to actually have many advantages for
the application programmer: other manipulations of the data - not involving
containers - can also be carried out more efficiently (and sometimes more
conveniently) using those same pointers.

> >It also gives me another opportunity to demonstrate the idea of having a
set
> >of abstract container types, upon which operations (such as
Normalize_Names)
> >can be hung, thus freeing you of: (1) having to worry about which
container
> >type to use when writing the procedure; (2) the procedure shackling you
to
> >one particular container type. Do you turn away from this Utopia? ;-)
>
> But remember that one of our stipulations is essentially "no multilevel
generic
> instantiations required". Does this work that way? Without that
restriction you
> could do all sorts of cool things, as has been done in Booch and others.
In that
> enviroment I'd say that we already have plenty of players, and one of them
is
> liable to be perfectly suitable (although I suppose more are always
welcome). I
> don't want to discourage you from making the ultimate container library.
But for
> the purposes of what we are doing here it has to be very easy to use, and
> frankly I couldn't figure out quite what was going on in the code you
presented.

I'm not quite trying to make 'the ultimate library' ;-) but I suppose I am
aiming at something that would be useful for 'real' programming, rather than
just for students and demos. Ada is not a toy language, it's not a Pascal or
BASIC, it's an industrial language intended for building real, big software.
Honestly, I think it's a mistake to try to defend students (or anyone else)
from this fact.

When we make a wooden box for the first time in kindergarten we use one nail
per joint. As grown ups, when we make a box for some real purpose, we use
two nails per joint. When making toy programs at university we may have used
one instantiation per data type; but when as professionals we start writing
real software, we use two instantiations per data type! (It's all a part of
the maturing process ;-)

At the end of the day, a box that falls to pieces (because you only used one
nail) doesn't make life easier for anyone. As I say in my reply to Ehud, I
really believe this is a situation where trying to make things easier for
the user will end up making things much harder for them.

To me, you really seem to be saying something like "Oh, there shouldn't be
any safety catches on guns: it makes them too complicated for the user! Our
guns have just the trigger and nothing else." It may sound nice, but you are
inevitably going to cause of lot of users to end up shooting themselves (in
the foot, or worse :-)

I hope you'll forgive me if I re-post the code I gave, corrected and cleaned
up a little, and with a blow-by-blow commentary on what's going on.

   with Ada.Characters.Handling; use Ada.Characters.Handling;

This is to conveniently obtain some character-handling functions provided by
Ada.

   type Name_Ref is access [all] String;

Here we declare the access type that is going to be the 'data type' stored
by containers.

   package Name_Ref_Iteration is new Iteration(Name_Ref);

This instantiates the package of abstract container types (including
Sequence_Recorder), so that they are specialised for Name_Refs (but they are
still abstract).

   procedure Normalize_Names (
      Source: in out Name_Ref_Iteration.Sequence_Recorder'Class;
      Target: in out Name_Ref_Iteration.Sequence_Recorder'Class) is

Source and Target are both in the class of the abstract container type
Sequence_Recorder. This means that the corresponding actuals, when the
procedure is called, must be (concrete types) derived from
Sequence_Recorder, and therefore that they must, at the very least,
implement the procedures Read, Restart, Rewrite, and Write, and the function
End_of_Data.

      Ref: Name_Ref;
      N: Natural;

Just a couple of temporary variables.

   begin
      while not End_of_Data(Source) loop

We will iterate over the elements (name pointers, of type Name_Ref) in the
Source container.

         Read(Source,Ref);

We read one reference in from the Source container. This is a dispatching
call: the correct Read for the actual container will be called.

         if Ref /= null and then Ref.all'Length > 0 and then
Ref(Ref.all'First) /= '?' then

This just checks various conditions to ensure the name pointer (in Ref) is
usable, and not to be deleted (indicated by the leading '?').

            To_Upper(Ref.all);

Convert the string (pointed to by the pointer in Ref) to uppercase.

            Write(Target,Ref);

Write the pointer into the Target container. Again, this is a dispatching
call.

            N := Ref.all.First-1; -- in case string doesn't start at 1
            if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then
Is_Letter(Ref(N+4)) then
               Write(Target, new String'("MC"&Ref(N+4..Ref.all'Last)));
            end if;

This is just a bit of messing about with the Macs. The important thing to
note is that another Write may be performed, thus achieving the effect of
insertion.

         else
            Ref := null; -- or maybe use Unchecked_Deallocation

The effect of deletion is achieved by simply not writing the pointer into
Target.

         end if;
      end loop;
   end Normalize_Names;

The usage of this procedure, in conjunction with a (concrete) list container
type (which we assume is derived from Sequence_Recorder), might be:

   package Name_Ref_Lists is new SCL.Lists.Unbounded(Name_Ref_Iteration);

Now we instantiate the package that will export a list type for use
(List_Type) wich is specialised for name pointers (type Name_Ref).

   subtype Name_List is Name_Ref_Lists.List_Type;

This just conveniently renames the exported list type.

   L1, L2: Name_List;

Here we declare two list variables.

   ... set up L1 with names

We will do something (not shown, but e.g. read a file) to read the names,
and put the pointers to them into L1.

   Rewrite(L2);

This prepares (and erases, if necessary) L2 for being written into.

   Restart(L1);

This prepares (and rewinds to the start, if necessary) L1 for being read
from.

   Normalize_Names(L1,L2);

We call the procedure. The actuals, L1 and L2, could have been of any
container type (provided they were both derived from Sequence_Recorder). In
this case, they happen to both be lists.

   Rewrite(L1);

This is just a simple way to erase L1.

   Restart(L2);

Get L2 ready to be read, for the next step in the overall processing
(whatever that might be).

I really hope this helps clarify things. The vital point is that the
procedure Normalize_Names can be used with any container type (derived from
Sequence_Recorder), rather than being permanently tied down to one container
type.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Larry Hazel]

Nick Roberts wrote:
> 
> I hope you'll forgive me if I re-post the code I gave, corrected and cleaned
> up a little, and with a blow-by-blow commentary on what's going on.
> 
This mostly looks very good to me except it seems terribly inefficient to have
to copy the whole list into a new list then delete the old list if all I need to
do is modify a few entries, delete a few others and insert a few.  Seems as if
we still need methods to delete, update, and insert elements.

Larry

Re: List container strawman

[Nick Roberts]

"Larry Hazel" <lhhazel@otelco.net> wrote in message
news:3BEDB57E.1203D638@otelco.net...
> Nick Roberts wrote:
> >
> > I hope you'll forgive me if I re-post the code I gave, corrected and
cleaned
> > up a little, and with a blow-by-blow commentary on what's going on.
> >
> This mostly looks very good to me except it seems terribly inefficient to
have
> to copy the whole list into a new list then delete the old list if all I
need to
> do is modify a few entries, delete a few others and insert a few.  Seems
as if
> we still need methods to delete, update, and insert elements.

In fact, I completely agree with you. It was extremely clumsy of me to
simply say "you don't need inserts or delete". You do. What you don't need
is insert or delete in association with an iterator (or a separate iterator
type at all). All you need are straightforward insert and delete functions
and procedures that identify the position of insertion or deletion with a
number (type Positive), starting at 1 for the first item in the list.

Detail: A container object would have three modes: seq read; seq write;
normal. Calling Read or End_of_Data other than in seq read mode, or calling
Write or Terminate_Data other than in seq write mode, would raise an
exception (SCL.Exceptions.Mode_Error). Restart causes a switch to seq read
mode. Rewrite causes a switch to seq write mode. Any other operation when
not in normal mode causes a switch to normal mode. This way, non-sequential
modification cannot interfere with iteration. Simple.

Doing the equivalent of what my example procedure Normalize_Names did using
inserts and deletes with an iterator would have ended up with code that was
more difficult to program, more difficult to read, slower in execution, and
(I think) more wasteful of memory. Showing this was the true purpose of my
example. Admittedly, I really need to add more detail, but it's finding the
time :-(

--
Best wishes,
Nick Roberts

Re: List container strawman

[Darren New]

Nick Roberts wrote:
> Doing the equivalent of what my example procedure Normalize_Names did using
> inserts and deletes with an iterator would have ended up with code that was
> more difficult to program, more difficult to read, slower in execution, and
> (I think) more wasteful of memory. Showing this was the true purpose of my
> example. Admittedly, I really need to add more detail, but it's finding the
> time :-(

Using sequences like this when the problem is expressed in terms of a
loop over all elements makes sense. Using sequences when the problem is
expressed in other forms may not. If your list is a list of characters
that you're trying to parse, for example, matching up parens or doing
reg-exp sorts of stuff (yes, I know you'd use strings) then only doing
reads *or* writes, only going in one direction doesn't make good sense.
If you have an ordered list and you want to insert an element in the
right place, copying the entire list to do so isn't very efficient.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container strawman

[Nick Roberts]

"Darren New" <dnew@san.rr.com> wrote in message
news:3BF01760.A21F56B3@san.rr.com...
> Nick Roberts wrote:
> > Doing the equivalent of what my example procedure Normalize_Names did
using
> > inserts and deletes with an iterator would have ended up with code that
was
> > more difficult to program, more difficult to read, slower in execution,
and
> > (I think) more wasteful of memory. Showing this was the true purpose of
my
> > example. Admittedly, I really need to add more detail, but it's finding
the
> > time :-(
>
> Using sequences like this when the problem is expressed in terms of a
> loop over all elements makes sense. Using sequences when the problem is
> expressed in other forms may not. If your list is a list of characters
> that you're trying to parse, for example, matching up parens or doing
> reg-exp sorts of stuff (yes, I know you'd use strings) then only doing
> reads *or* writes, only going in one direction doesn't make good sense.
> If you have an ordered list and you want to insert an element in the
> right place, copying the entire list to do so isn't very efficient.

In essence, I agree, and I've devised a new proposal with bi-directional
cursor operations. Hopefully I'll have this ready to send to Ted Dennison in
a couple of days time, for him to kindly put on his web site.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Ehud Lamm]

Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9sib27$13aeg3$5@ID-25716.news.dfncis.de...
>
> It also gives me another opportunity to demonstrate the idea of having a
set
> of abstract container types, upon which operations (such as
Normalize_Names)
> can be hung, thus freeing you of: (1) having to worry about which
container
> type to use when writing the procedure; (2) the procedure shackling you to
> one particular container type. Do you turn away from this Utopia? ;-)


These goal are vrey worthy. In fact they are one of the reasons people want
inheritance.
Problem is that we are looking for a way of achieving these goal, without
making newcomers struggle with nested instatiations, and complexities of the
Ada tagged type approach (freezing, scope of access types etc. etc.)
Perhaps I missed the point - but does your approach solve the dillema?

Ehud

Re: List container strawman

[Nick Roberts]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9sjvrl$2pd$1@news.huji.ac.il...
> ...
> These goal are vrey worthy. In fact they are one of the reasons people
want
> inheritance.
> Problem is that we are looking for a way of achieving these goal, without
> making newcomers struggle with nested instatiations, and complexities of
the
> Ada tagged type approach (freezing, scope of access types etc. etc.)
> Perhaps I missed the point - but does your approach solve the dillema?

I thought we were agreed that there was no way to achieve the goals (of
decoupling) without the multiple instantiations. In any case, I believe that
is so, and I suppose I am trying to convince people that it's (very much!)
the lesser of two evils to have the multiple instantiations and the
decoupling. I really think this is a case where the apparently easier way is
in fact the harder one.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Larry Kilgallen]

In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes:

> I'm interested in what the general consensus is here. Should we do the extra
> work to make iterators safe, given that this will have at least the following
> effects:

For my world, I favor safety over efficiency.

I have already decided not to use assembly language, and despite a lack
of demand from me, "they" keep making the computers faster.

I understand that some might have use for a more efficient package,
but I believe the one promulgated to the masses should be the one
with maximum error detection.

Re: List container strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

I vote for having a truly safe list implementation, like this one, if
only for reference. I vote for also having an Unchecked_List package,
so we can use it in higher-level abstractions that add safety in
different ways.

That way, when someone says "why isn't this list package _safe_? I
thought Ada was a _safe_ language!", we can say "look at the safe list
package; it has too much overhead for _this_ use, but it's available
if you want it".

It might also inspire some grad student to make a version with less
overhead, or a compiler optimization that removes the overhead, or
something.

-- 
-- Stephe

Re: List container strawman

[Ted Dennison]

In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>I vote for having a truly safe list implementation, like this one, if
..

Just to make things perfectly clear, these are Stephen's words, not mine. I'm
sure he wasn't confused about this, but someone else might be. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Larry Kilgallen]

In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> Ted Dennison<dennison@telepath.com> writes:
> 
> I vote for having a truly safe list implementation, like this one, if
> only for reference. I vote for also having an Unchecked_List package,
> so we can use it in higher-level abstractions that add safety in
> different ways.
> 
> That way, when someone says "why isn't this list package _safe_? I
> thought Ada was a _safe_ language!", we can say "look at the safe list
> package; it has too much overhead for _this_ use, but it's available
> if you want it".

Then how about naming the packages Safe_List and Unchecked_List ?

Is it possible for them to have the same profile, allowing people
to switch easily if they change their mind or need to debug ?

Re: List container strawman

[Nick Roberts]

"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:RyJAqQJQiv6e@eisner.encompasserve.org...
> ...
> Is it possible for them to have the same profile, allowing people
> to switch easily if they change their mind or need to debug ?

The answer to this is yes: by basing them both on an abstract type.

(On the other hand, I've demonstrated in another post in this thread that
you don't need insert or delete anyway.)

--
Nick Roberts

Re: List container strawman

[ramatthews]

In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> wrote:

> 
> I'm interested in what the general consensus is here. Should we do the extra
> work to make iterators safe, given that this will have at least the following
> effects:
> 
> o  Add extra dynamic memory operations to any list modification (there were some
> there already).
> o  Add a (usually small) internal list traversal to any element deletion.
> o  Add a small validity check (or possibly two) to every iterator operation.
> o  Possibly make iterator creation non-determistic (time-wise).
> o  Possibly make iterator assignment non-deterministic. Note that functions are
> currently used for iterating, so that would make just about any use of iterators
> non-determinstic, unless procedure variants are introduced.
> 

You express some implementation concerns that, for the implementation
I have to hand, I hope I can clarify.

The list contains two doubly-linked lists: one for the data, the
other for the enumerators (also called Iterators and Positions in
this discussion on cla). The enumerators list is traversed when the following
subprograms are called: Prepend, Append, Delete_All, Insert, Delete and
Finalize (for a list). In addition Update will cause a traversal of the
enumerators list when the new value cannot be assigned to the existing
data element (eg when the new value has a different tag); in this case
the new value is assigned to a new data element and the old data element
deleted - hence the need to update the enumerators. (Note that the
package specification gives an incorrect comment on this).

When a list is declared in client code, two data items are created:
(1) the list that the client code directly sees (List_Type), and
(2) the list header (List_Header_Type) that is created on the heap.
A similar situation exists for an enumerator (Enumerator_Type and
the heap held Enumerator_Envelope_Type). This split was made, on stylistic
grounds, to avoid use of the attribute Unchecked_Access in the body.

Having 'safe' enumerators does introduce some extra checking. For example
when retrieving the data denoted by an enumerator the subprogram 'Current'
checks:
(1) that the enumerator's list exists: "Enumerator.Header.List_Header /= null",
(2) that the data exists: "Enumerator.Header.Current /= null".

Enumerator creation, assignment and finalization involves manipulation of
the affected enumerator lists - but does not require list traversal.

Robert Matthews.

Re: List container strawman

[Ted Dennison]

In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says...
>
>If you really want it to be foolproof, then for each "Location" pointer,
>you keep a pointer to the list, a pointer to the element being indexed,
>and a list number counter. In each list head, you keep a list number
>counter, a counter of the number of Location pointers outstanding, and
>the head and tail of the list.

That's not good enough either, since the List could change to make the location
itself invalid. The List itself could even go out of scope while the location
doesn't. I've implemented a lot of these types of iterators in my time, so I
have thought through the issue quite a bit already.

The best I could come up with for a Right Thing would be to keep a list of
extant Location pointers in each List object. That way the list itself can go
and invalidate the Location whenever it needs to (probably by flipping some
"valid" boolean in the Location type). Locations would have to be limited for
this to work, so the functions that return locations would have to be changed to
procedures.

To my mind, that's a rediculous amount of work and overhead to support a mild
"safeing up" of one small facility (iterators). I'm of the inlincation that if
you aren't going to do the Right Thing here, then bag it. Half-measures are
liable to cause as much harm as good by giving folks a false sense of security.
You might as well just aviod the whole issue, save all the work and overhead,
and just put it on the user to use this one feature correctly. As long as the
issues are well documented (eg: Its a "Bounded Error" to use an iterator after
any modification of its list not involving that iterator), then I don't see a
big problem.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Jean-Marc Bourguet]

Ted Dennison wrote:
[...]
> The best I could come up with for a Right Thing would be to keep a list of
> extant Location pointers in each List object. That way the list itself can go
> and invalidate the Location whenever it needs to (probably by flipping some
> "valid" boolean in the Location type). Locations would have to be limited for
> this to work, so the functions that return locations would have to be changed to
> procedures.

Why should they be limited?  If they are controlled, that should be enough or
do I miss something?

[...]

-- 
Jean-Marc

Re: List container strawman

[Ted Dennison]

In article <3BE6EBB1.EF463656@free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison wrote:
>[...]
>> The best I could come up with for a Right Thing would be to keep a list of
>> extant Location pointers in each List object. That way the list itself can go
>> and invalidate the Location whenever it needs to (probably by flipping some
>> "valid" boolean in the Location type). Locations would have to be limited for
>> this to work, so the functions that return locations would have to be changed to
>> procedures.
>
>Why should they be limited?  If they are controlled, that should be enough or
>do I miss something?

That would be a lot tougher, as they'd have to somehow go add themselves and
remove themselves from the List's list dynamcily. I guess its doable, its just
even more work. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Darren New]

Ted Dennison wrote:
> 
> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says...
> >
> >If you really want it to be foolproof, then for each "Location" pointer,
> >you keep a pointer to the list, a pointer to the element being indexed,
> >and a list number counter. In each list head, you keep a list number
> >counter, a counter of the number of Location pointers outstanding, and
> >the head and tail of the list.
> 
> That's not good enough either, since the List could change to make the location
> itself invalid.

I'm not sure how that could happen. The "location" record itself would
be separate from the list.

> The List itself could even go out of scope while the location
> doesn't.

Yes. That's why I suggested that it have a reference count, and
finalization would need to either be defered until all the locations are
also finalized or all locations would have to be invalidated when the
list goes out of scope.  Of course, in Ada this is probably a little
more complex, and you'd wind up with the public "List" type probably
just being a pointer to a controlled record.

> I've implemented a lot of these types of iterators in my time, so I
> have thought through the issue quite a bit already.

Yep.
 
> The best I could come up with for a Right Thing would be to keep a list of
> extant Location pointers in each List object. That way the list itself can go
> and invalidate the Location whenever it needs to (probably by flipping some
> "valid" boolean in the Location type). Locations would have to be limited for
> this to work, so the functions that return locations would have to be changed to
> procedures.

That could work too. You could have a linked list of Locations pointed
to by the List object.
 
> To my mind, that's a rediculous amount of work and overhead to support a mild
> "safeing up" of one small facility (iterators).

Agreed. On the other hand, you could include different bodies depending
on whether you were having trouble or not. :-) I.e., the interface
shouldn't *preclude* adding all kinds of safety checks, I think.

> I'm of the inlincation that if
> you aren't going to do the Right Thing here, then bag it. Half-measures are
> liable to cause as much harm as good by giving folks a false sense of security.
> You might as well just aviod the whole issue, save all the work and overhead,
> and just put it on the user to use this one feature correctly. As long as the
> issues are well documented (eg: Its a "Bounded Error" to use an iterator after
> any modification of its list not involving that iterator), then I don't see a
> big problem.

Agreed. But it *is* doable. Probably not worth doing, tho. My
expectation is that it would be a debugging aid you turned on if you
need it, kind of like "Purify" for your C code.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman

[Ted Dennison]

In article <3BE6F58C.7C88F6CD@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> That's not good enough either, since the List could change to make the 
>> location itself invalid.
>
>I'm not sure how that could happen. The "location" record itself would
>be separate from the list.

Lots of ways. For instance, the element pointed to could be deleted using
another iterator. It could get removed with a Pop. It could get removed with
that global list empty that someone suggested I add.

>> I'm of the inlincation that if
>> you aren't going to do the Right Thing here, then bag it. Half-measures are
>
>Agreed. But it *is* doable. Probably not worth doing, tho. My

Exactly.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman; Construct alternatives

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says...
> <snip> 
> >I suggest Make rather than Construct.
> 
> Fair enough. I'm used to seeing "make" in terms of GNU make, but the term
> "Construct" has a fair bit of baggage too. Do we have a second on this motion?

I like "Create". 

However, if you do end up with "type List" being
derived from Controlled, then you do _not_ want "Create" to be a
primitive operation; derived types must have their own "Create". One
good solution is to put the "Create" routines (there are usually more
than one) in a local nested package:

package Containers.Lists is

   type List_Type is ...

   package Creators is
      procedure Create (List : in out List_Type);
      -- Create an empty list

      procedure Create 
         (List    : in out List_Type; 
          Initial : in     Element);

   end Creators;

end Containers.Lists;


Also, I prefer "List_Type" and "Element_Type", for all the reasons in
the recent thread on that topic!

-- 
-- Stephe

Re: List container strawman

[Simon Wright]

Jeffrey Carter <jeffrey.carter@boeing.com> writes:

> This is an iterator and should be so named ("Iterate"). I recommend
> adding a Quit or Continue out Boolean parameter to Operation to
> allow the client to terminate the iteration early.

One of my users suggests making this an in out parameter, initialized
to "carry on", so that he doesn't have to (remember to) assign it
before exit.

Re: List container strawman

[Stephen Leake]

Do you have an example implimentation? I don't see how you can
implement "Sort" without a "Compare" operation on Element. Typically,
a user will want more than one "Compare" operation (ie Sort on first
name, sort on date). Moving Sort into a child package, that takes a
generic parameter of "Compare", would provide this.

Also, the semantics of the operations need to be clearly defined. Does
calling "Remove" invalidate other Iterators? What, exactly, does
"Closure_Operation" do?

There should be a "Insert (Iterator)" to add an element at the current
iterator position.

"List" should be limited, to prevent non-deep copies when Element is
an access type. Or it should be derived from Controlled, to allow the
user to override Adjust to provide a deep copy. Or a "Copy_Element"
generic procedure should be provided.

-- 
-- Stephe

Re: List container strawman

[Simon Wright]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> "List" should be limited, to prevent non-deep copies when Element is
> an access type.

I don't see why you would want to do this specifically? (perhaps I've
misunderstood).

If I make a List of Bank_Account_Access whose 5th element is a pointer
to my bank account, and then make a copy of it, what would you expect
the 5th element of the new List to point to? Better not be a *copy* of
my bank account!

Re: List container strawman

[Stephen Leake]

Simon Wright <simon@pushface.org> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> > "List" should be limited, to prevent non-deep copies when Element is
> > an access type.
> 
> I don't see why you would want to do this specifically? (perhaps I've
> misunderstood).
> 
> If I make a List of Bank_Account_Access whose 5th element is a pointer
> to my bank account, and then make a copy of it, what would you expect
> the 5th element of the new List to point to? Better not be a *copy* of
> my bank account!

Good example. But there are many other examples where copying a list
does _not_ make sense. For example, if I have a list of controls in a
GUI dialog box, and I pop up another dialog box, I want a list of
_new_ controls, not the same ones.

So the base list container must allow the user to control the copying
process. That means either making it Limited and providing a Copy
operation, or making it Controlled and providing Adjust. In either
case, the user of the package must provide a Copy_Element operation
that does the Right Thing.

-- 
-- Stephe

Re: List container strawman

[Jeffrey Carter]

Stephen Leake wrote:
> 
> Good example. But there are many other examples where copying a list
> does _not_ make sense. For example, if I have a list of controls in a
> GUI dialog box, and I pop up another dialog box, I want a list of
> _new_ controls, not the same ones.

Since an unbounded list creates values of the Element type, assigns to
them, and deallocates them, we must rely on the client to provide an
actual type that handles this properly. If an Element contains a pointer
and the client wants a deep copy, assignment must perform a deep copy.
If the client wants multiple pointers to the same object, assignment
need only copy the pointer. This is not a concern of the list.

-- 
Jeffrey Carter

Re: List container strawman

[Jeffrey Carter]

Stephen Leake wrote:
> 
> So the base list container must allow the user to control the copying
> process. That means either making it Limited and providing a Copy
> operation, or making it Controlled and providing Adjust. In either
> case, the user of the package must provide a Copy_Element operation
> that does the Right Thing.

If the client has to provide an Assign procedure for the Element type,
then the Element type should be limited private. While I have no problem
with this, I think most of the participants in this discussion have
already decided that's too complicated for them.

-- 
Jeffrey Carter

Re: List container strawman

[Nick Roberts]

To my mind (and you need to understand that I live in my own little closeted
world :-) there might be some mileage in providing some generic functions
that provide a deep copy operation:


   generic
      type Element_Type(<>) is private;
      type Access_Type is access Element_Type;

   function SCL.Deep_Copy_by_Access
      (Ref: in Access_Type)
      return Access_Type;


   function SCL.Deep_Copy_by_Access
      (Ref: in Access_Type)
      return Access_Type is
   begin
      return new Element_Type'(Ref.all);
   end;


This just provides a convenient way to get a Deep_Copy function for a
(pool-specific) access type of a (non-access) data type. Then we could
provide a deep copy for unbounded lists:


   generic
      with function Deep_Copy
         (Item: in Element_Type)
         return Element_Type is <>;

   function SCL.Lists.Unbounded.List_Deep_Copy
      (Source: in Unbounded_List)
      return Unbounded_List;


There would be the same for unbounded lists and other container types.


--
Best wishes,
Nick Roberts

Re: List container strawman

[Ehud Lamm]

Indeed one advantage of having a standard design for the different packages
in the library is to encourage this sort of general utilities.

Ehud

Re: List container strawman

[Marin David Condic]

I don't think I'd characterize it as "complicated" - more like "awkward". In
the past, I've built data structures that would have a "private" flavor and
a "limited private" flavor so that when I had the simple case (assignment
and equality inherently available) I didn't have to go to the effort of
inventing small subprograms or otherwise jockying around the fact that the
limited case was going to insist I provide something that was already there.

I think the reason for "private" being preferable over "limited private" is
that now we can build things that inherit from Controlled, so if you need to
do something to control behavior on assignment, you can, but you don't have
to for the simple case. Hence, you can save yourself some generic parameters
and make instantiation a simpler matter. (Do you really want to have to
define an "Assign" procedure every time you want to stack up some integers?
Its not complicated - just a pain in the posterior.)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF1A33D.73DE084F@boeing.com...
>
> If the client has to provide an Assign procedure for the Element type,
> then the Element type should be limited private. While I have no problem
> with this, I think most of the participants in this discussion have
> already decided that's too complicated for them.
>

Re: List container strawman

[Jeffrey Carter]

Marin David Condic wrote:
> 
> I don't think I'd characterize it as "complicated" - more like "awkward". In
> the past, I've built data structures that would have a "private" flavor and
> a "limited private" flavor so that when I had the simple case (assignment
> and equality inherently available) I didn't have to go to the effort of
> inventing small subprograms or otherwise jockying around the fact that the
> limited case was going to insist I provide something that was already there.
> 
> I think the reason for "private" being preferable over "limited private" is
> that now we can build things that inherit from Controlled, so if you need to
> do something to control behavior on assignment, you can, but you don't have
> to for the simple case. Hence, you can save yourself some generic parameters
> and make instantiation a simpler matter. (Do you really want to have to
> define an "Assign" procedure every time you want to stack up some integers?
> Its not complicated - just a pain in the posterior.)
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3BF1A33D.73DE084F@boeing.com...
> >
> > If the client has to provide an Assign procedure for the Element type,
> > then the Element type should be limited private. While I have no problem
> > with this, I think most of the participants in this discussion have
> > already decided that's too complicated for them.
> >

Yes, but I was referring to a comment that suggested an Assign procedure
needs to be provided even though Element is private. In that case you
might as well make Element limited private since it buys you additional
applicability without changing how the component is instantiated.

Of course, the real reason not to import Element as private is that it
is an incorrect specification, and precise specification is essential to
design by contract. A generic package has 2 specifications: the generic
formal part, which should specify precisely what the client must provide
to use the package, and the package specification, which should specify
precisely what services the package provides to its clients.

A formal private type specifies that the package requires "=" for type,
when in fact a list does not use "=" for its Element type.

-- 
Jeffrey Carter

Re: List container strawman

[Marin David Condic]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF2A186.F1911068@boeing.com...
>
> Yes, but I was referring to a comment that suggested an Assign procedure
> needs to be provided even though Element is private. In that case you
> might as well make Element limited private since it buys you additional
> applicability without changing how the component is instantiated.
>
I would agree that once you've gone to the effort of insisting there be an
Assign and an "=" in the generic formal part, then you might just as well
have made it limited private and enabled the creation of lists of just about
anything.

But I don't want to have to specify an Assign and an "=" every time I want
to stack up some integers or something similarly simple. I just want to get
the job done with as little effort or excess baggage as is possible.


> Of course, the real reason not to import Element as private is that it
> is an incorrect specification, and precise specification is essential to
> design by contract. A generic package has 2 specifications: the generic
> formal part, which should specify precisely what the client must provide
> to use the package, and the package specification, which should specify
> precisely what services the package provides to its clients.
>
Interesting, but IMHO, not compelling. Some folks may want a list package to
satisfy all sorts of requirements that are of some kind of academic
interest. They may even want a formal mathematical proof of correctness. I
don't think any of this Moves The Mission Forward. My big questions are
"Does it work reliably?" and "Is it easy to use?". Design by contract,
Ravenscar profiles, Mathematical proofs, etc. may all contribute something
to question #1, but if they start getting in the way of question #2, I'd
find that a hindrance to producing something large numbers of people will
want to use.

If we insist on Design By Contract or some other approaches as requirements,
I'd ask "Do all the other packages provided by the Ada standard meet these
requirements?" I'd suggest that they probably don't - in which case, why
should a data-structures-add-on to the language need to do so?


> A formal private type specifies that the package requires "=" for type,
> when in fact a list does not use "=" for its Element type.
>

I'd suggest that no matter how hard you try, you aren't going to get me to
shed a single tear over the fact that an "=" operation came along for the
ride even though a List package (according to what definition? mine is
pretty loose!) doesn't need it. Every time I write a math function for a
type Float, I bring in a whole slew of operations I may not need. Every time
I "with" a package, the same thing happens. Every time you have a generic
formal of "digits <>" or similar, you bring in operations that may not be
needed. I respectfully submit the question: "So What?" :-)

No matter what we do, we will *never* arrive at a "Perfect" List package.
The best we can hope for is a "Good Enough" List package that covers some
sufficient bulk of the possible uses and does so as easily and with as much
functionality as can reasonably be had.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: List container strawman

[Nick Roberts]

Have I missed something in this discussion? If it is, as I get the
impression, over whether the data type (the type of each element of a list)
generic parameter should be private or limited private, I think I can give
you the definitive answer.

Unless I'm really missing something, it's got to be private (non-limited),
because otherwise how do you copy values of that type into or out of the
list? End of argument (isn't it?).

--
Best wishes,
Nick Roberts

Re: List container strawman

[Marin David Condic]

Nope. Sorry. You can (and I have) make a list package using limited private
that insists on having a procedure called "Assign" and a function called "="
as generic formals. The advantage of that is that now you could do something
like make a List of Lists (assuming your list type is limited). The
disadvantage is that when you just need a list of integers, you've still got
to go define the "Assign" at least - assuming the "=" has the "is <>", so it
gloms onto the existing "=" function. O.K. It's not the end of civilization
as we know it, but its a pain in the backside - especially where you might
have library level instantiations, etc. Who wants to keep writing trivial
"Assign" subprograms (and maintaining them in separate files, etc., if you
have to do library level instantiations.) for every usage of a list - which
most of the time won't need anything tricky in the "Assign" procedure
anyway.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9svf7q$161cka$1@ID-25716.news.dfncis.de...
>
> Unless I'm really missing something, it's got to be private (non-limited),
> because otherwise how do you copy values of that type into or out of the
> list? End of argument (isn't it?).
>

Re: List container strawman

[Nick Roberts]

Hah, it's pretty funny, Marin. You've made me spot an error in my just
released proposal for the list package! I've declared the Abstract_List type
limited, and it shouldn't be.

Sorry, but my point (now ;-) would be that, whilst you can indeed do what
you say, you wouldn't want to. Because lists are non-limited (hah :-) you
can have a list of lists (etc.) without any problem. If you have a limited
type, you don't want a list of objects of that type, you want a list of
access values referencing them (e.g. consider a list of tasks).

So, to sum up, I'm certain the data type (generic parameter) should be
non-limited, so it can be copied without any sillyness.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Marin David Condic]

Back in the days of Ada83, this was more of a problem. Now that you have
Finalization, making a List type non-limited is less of a problem.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9t1q26$16frj1$1@ID-25716.news.dfncis.de...
>
> Sorry, but my point (now ;-) would be that, whilst you can indeed do what
> you say, you wouldn't want to. Because lists are non-limited (hah :-) you
> can have a list of lists (etc.) without any problem. If you have a limited
> type, you don't want a list of objects of that type, you want a list of
> access values referencing them (e.g. consider a list of tasks).
>

Re: List container strawman

[Nick Roberts]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9t3ddg$c9c$1@nh.pace.co.uk...
> Back in the days of Ada83, this was more of a problem. Now that you have
> Finalization, making a List type non-limited is less of a problem.

Acknowledged.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Matthew Heaney]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9svf7q$161cka$1@ID-25716.news.dfncis.de...
> Have I missed something in this discussion? If it is, as I get the
> impression, over whether the data type (the type of each element of a
list)
> generic parameter should be private or limited private, I think I can give
> you the definitive answer.

The problem is worse, because most of the participants in this discussion
have assumed that "list" means a polylithic structure (elements are shared),
a la LISP.  This is an incorrect model.  The container abstraction is
monolithlic, and refering to it as a "list" only means that it has constant
time insertion and removal.  So you don't need "construct" or "cons" or
"singleton" or "head" or "tail" or whatever.

Furthermore, you can add an item to the list at the front, back, or
somewhere in the middle.  You can remove any iteim of the list.

with Ada.Finalization;
generic
   type Item_Type is private;
   with function "=" (L, R : Item_Type) return Boolean is <>;
package Lists is
   type List_Type is private;  --implies Controlled
   procedure Push_Front (List : in out List_Type; Item : in Item_Type);
   procedure Push_Back (List : in out List_Type; Item : in Item_Type);
   procedure Pop_Front (List : in out List_Type);
   procedure Pop_Back (List : in out List_Type);
   function Front (List : List_Type) return Item_Type;
   function Back (List : List_Type) return Item_Type;
   function Length (List : List_Type) return Natural;

   type Iterator_Type (List : access List_Type) is limited private;
   procedure Insert (Iterator : in Iterator_Type; Item : in Item_Type);
   procedure Remove (Iterator : in out Iterator_Type);
   procedure Advance (Iterator : in out Iterator_Type);
   procedure Backup (Iterator : in out Iterator_Type);
   function Item (Iterator : in Iterator_Type) return Item_Type;
--or maybe
--type Iterator_Type is private;
--function Front (List : List_Type) return Iterator_Type;
--function Back (List : List_Type) return Iterator_Type;
--bounded form would probably require:
--function Front (List : access List_Type) return Iterator_Type;
--procedure Insert (List : in out List_Type; Iterator : Iterator_Type; Item
: Item_Type);
--procedure Remove (List : in out List_Type; Iterator : in out
Iterator_Type);
--etc
...
end;

That's the general idea.  I'm undecided about how to declare the iterator
type, because the limited form may have a false sense of security, e.g.

declare
   List : aliased Integer_Lists.List_Type;
begin
   Push_Front (List, 42);
   declare
      Iter : Iterator_Type (List'Access);
   begin
      Pop_Front (List);
      X := Item (Iter); --uh oh
   end;
end;

it may be simpler to just

declare
   List : List_Type;
   Iter : Iterator_Type;
begin
   Push_Front (List, 42);
   Iter := Front (List);
...
end;

It may also be necessary to use "First" and "Last" to refer to the first and
last elements in the sequence, and "Front" and "Back" to refer to the nonce
values that immediately preceed First and immediately follow Last, eg

declare
   List : List_Type;
   Iter : Iterator_Type := First (List);
begin
   while Iter /= List.Back loop
      ...
      Remove (List, Iter);
   end loop;
end;

You could then use First and Back to specify a half-open range, a la the STL
in C++.

Some food for thought...

Re: List container strawman

[Marin David Condic]

I just took a quick look at it & I think it would be workable. It has
simplicity on its side. Without having thought about it for any real length
of time I don't see anything major missing, but perhaps there might be some
desirable operations to be added. For example, I think it ought to have a
"Load/Store" operation to get/put the contents to a file using Streams.
("You give me a file name string and a list & I handle the I/O") It would be
handy to have 'Input and 'Output working on it as well so you could get it
in and out of a Stream_Element_Array.

Also, I think it would be wise to have this (and any other packages) rooted
at some common package with a name like "ASCL" just to make the whole thing
identifiable as a conglomerate. (But that would be arguing about names and I
promised I would not do that! :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

"Ted Dennison" <dennison@telepath.com> wrote in message
news:kPoE7.9567$xS6.13287@www.newsranger.com...
> Since we do seem to be reaching a small amount of agreement on details, I
went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions
rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .
If it
> is close enough to be worth persuing, we may be able to use it as a
starting
> point.
>
> (Note: The htmlization there was done by a tool I'm developing as part of
the
> next release of OpenToken. If you have comments on the job it did, I'd
like them
> too, but email would probably be the best venue for it).
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ted Dennison]

In article <9rubqc$i1u$1@nh.pace.co.uk>, Marin David Condic says...
>desirable operations to be added. For example, I think it ought to have a
>"Load/Store" operation to get/put the contents to a file using Streams.
>("You give me a file name string and a list & I handle the I/O") It would be
>handy to have 'Input and 'Output working on it as well so you could get it
>in and out of a Stream_Element_Array.

Definitely.

>Also, I think it would be wise to have this (and any other packages) rooted
>at some common package with a name like "ASCL" just to make the whole thing
>identifiable as a conglomerate. (But that would be arguing about names and I
>promised I would not do that! :-)

:-)
Actually, that's a perfectly reasonable discussion to be having. I picked the
root name of "Containers" just to have something. If it were part of the Ada
standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good root
name either on top of, or instead of, "Containers".

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

The problem with Ada.Containers is that a) it presumes we're going to get it
into the standard and b) it makes it difficult for someone to modify the
source since compilers are free to restrict you from manipulating things
under Ada... (Try declaring Ada.Containers and see if it will compile.)

Probably it is better to have it rooted as its own thing so it can be as
flexible as possible until such time as The Powers That Be decide to
immortalize you by including The Dennison Components into the standard. :-)
It could probably be accommodated at a later date through a bunch of
"renames" things...

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:JMyE7.10064$xS6.13823@www.newsranger.com...
> Actually, that's a perfectly reasonable discussion to be having. I picked
the
> root name of "Containers" just to have something. If it were part of the
Ada
> standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good
root
> name either on top of, or instead of, "Containers".

Re: List container strawman

[Ted Dennison]

In article <9rueje$j69$1@nh.pace.co.uk>, Marin David Condic says...
>
>The problem with Ada.Containers is that a) it presumes we're going to get it
>into the standard and b) it makes it difficult for someone to modify the
>source since compilers are free to restrict you from manipulating things
>under Ada... (Try declaring Ada.Containers and see if it will compile.)

All of which is why it isn't currently named that. :-)

>Probably it is better to have it rooted as its own thing so it can be as
>flexible as possible until such time as The Powers That Be decide to
>immortalize you by including The Dennison Components into the standard. :-)

Fine by me. It might be a good idea if it were something reasonably
interchangable with "Ada." when/if the time comes. But then again, perhaps it
would be best to have somthing that we would be comfortable with on its own for
perpetuity.

I know the "Dennison Components" bit was just a joke, but I'd like to make one
thing perfectly clear: I don't want or need my name prominently attached to
this. This has been and should contiune to be a community effort. We have just
reached a point in the discussion where we really need something tangible to
talk around. I'm trying to see if it is possible to synthesize our agreements
into source code form. If it is possible, great. If not, it was worth a shot. If
I wanted to make my *own* component library, I'd just do it rather than come up
here asking for input on everything. More likely, I'd *not* do it and use Booch.
:-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

I think we're clear that this is a group-consensus effort to at least see
what sort of requirements people have for such a library. So far, we're at
least kicking around some concrete ideas, which IMHO is a good thing.

I know we've got a couple of BC fans here & if there was a consensus to
accept that, I'd get on board, so maybe its still an idea worth kicking
around. But I can understand and agree with the objection that it is not as
simple and straightforward as one might like. Is there any way we might
identify interested parties and get a straw-poll on it? Any chance the
vendors would likely get on board?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:j8AE7.10206$xS6.13935@www.newsranger.com...
>
> I know the "Dennison Components" bit was just a joke, but I'd like to make
one
> thing perfectly clear: I don't want or need my name prominently attached
to
> this. This has been and should contiune to be a community effort. We have
just
> reached a point in the discussion where we really need something tangible
to
> talk around. I'm trying to see if it is possible to synthesize our
agreements
> into source code form. If it is possible, great. If not, it was worth a
shot. If
> I wanted to make my *own* component library, I'd just do it rather than
come up
> here asking for input on everything. More likely, I'd *not* do it and use
Booch.
> :-)

Re: List container strawman

[Nick Roberts]

I tried to kick start the Ada Structured Component Library (ASCL) group more
than a year ago, on eGroups, but weirdly I seemed to get a pile of interest
which fizzled out as fast as it arrived. Very odd.

Anyway, I am interested!

--
Nick Roberts


"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9ruk02$lft$1@nh.pace.co.uk...
> I think we're clear that this is a group-consensus effort to at least see
> what sort of requirements people have for such a library. So far, we're at
> least kicking around some concrete ideas, which IMHO is a good thing.
>
> I know we've got a couple of BC fans here & if there was a consensus to
> accept that, I'd get on board, so maybe its still an idea worth kicking
> around. But I can understand and agree with the objection that it is not
as
> simple and straightforward as one might like. Is there any way we might
> identify interested parties and get a straw-poll on it? Any chance the
> vendors would likely get on board?

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:j8AE7.10206$xS6.13935@www.newsranger.com...
> ...
> I know the "Dennison Components" bit was just a joke, but I'd like to make
one
> thing perfectly clear: I don't want or need my name prominently attached
to
> this. This has been and should contiune to be a community effort. We have
just
> reached a point in the discussion where we really need something tangible
to
> talk around. I'm trying to see if it is possible to synthesize our
agreements
> into source code form. If it is possible, great. If not, it was worth a
shot. If
> I wanted to make my *own* component library, I'd just do it rather than
come up
> here asking for input on everything. More likely, I'd *not* do it and use
Booch.

I'm afraid I feel it ought to be named 'Iteration'. It's terribly insipid,
but it seems to fit the bill, to me:


   generic
      type Element_Type is private;

   package Iteration is

      ...

   end Iteration;


This would then be instantiated in a very clear way:



   package Thingy_Iteration is new Iteration(Thingy_Type);

   Thingy_List_1: Thingy_Iteration.Lists.Unbounded.Doubly_Linked_List;


I think perhaps there should be a child package Lists, which declares an
abstract List_Type with attendant common list operations. This should then
have children such as Unbounded which declares concrete utility types based
on List_Type. We could then have other hierarchies implementing queues,
content-addressed containers, and so on.

See also my other posting.

--
Nick Roberts

Re: List container strawman

[David Botton]

Why not start with the Original (as in Ada 83) Booch
http://www.adapower.com/original_booch components and just modify them (they
are under the GMGPL)? They are a very close fit already.

"Ted Dennison" <dennison@telepath.com> wrote
> Since we do seem to be reaching a small amount of agreement on details

Re: List container strawman

[David Botton]

Just to clarify, I am not referring to the BC components.

"David Botton" <David@Botton.com> wrote in message
news:tu5kdq7ej2j3e6@corp.supernews.com...
> Why not start with the Original (as in Ada 83) Booch
> http://www.adapower.com/original_booch components and just modify them
(they
> are under the GMGPL)? They are a very close fit already.
>
> "Ted Dennison" <dennison@telepath.com> wrote
> > Since we do seem to be reaching a small amount of agreement on details
>
>

Re: List container strawman

[Nick Roberts]

May I make a suggestion, which, though I say it myself, I feel is rather
important!

Please make the type List derived from an abstract 'iterator' type. List
would then inherit the iteration operations of this type. An alternative is
for List to provide a function that generates or gives access to an object
derived from this iterator type.

For example:


generic
   type Element_Type is private;

package Containers is

   ...

   type Terminating_Producer is abstract tagged limited private;

   procedure Read (Producer: in out Terminating_Producer; Item: out
Element_Type) is abstract;

   function End_of_Data (Producer: in Terminating_Producer) return Boolean
is abstract;

   ...

   type Sequence_Reproducer is abstract new Terminating_Producer with
private;

   procedure Restart (Reproducer: in out Sequence_Reproducer) is abstract;

   type Sequence_Recorder is abstract new Sequence_Reproducer with private;

   procedure Rewrite (Reproducer: in out Sequence_Reproducer) is abstract;

   procedure Write (Recorder: in out Sequence_Recorder; Item: in
Element_Type) is abstract;

   function Count (Recorder: in Sequence_Recorder) return Natural is
abstract;

   function Is_Recording (Recorder: in Sequence_Recorder) return Boolean is
abstract;

   ...

end Containers;


The Restart procedure tells a sequence reproducer to start producing its
data over again. The Rewrite procedure tells a sequence recorder to start
recording data (at which point Write can be used and Read cannot;
Is_Recording returns True). Restart than tells it to start reading again (at
which point Write cannot be used; Is_Recording returns False). Count returns
the number of items currently recorded.


package Containers.Lists.Unbounded is

   type Linked_List is new Sequence_Recorder with private;

   -- Representing a singly-linked (forward) list type, with typical
operations.

   function "&" (Left, Right: in Linked_List) return Linked_List is
abstract;
   ...

   procedure Push (List: in out Linked_List; Item: in  Element_Type);
   procedure Pop  (List: in out Linked_List; Item: out Element_Type);

   ... -- etc

   type Doubly_Linked_List is new Sequence_Recorder with private;

   function "&" (Left, Right: in Linked_List) return Abstract_List is
abstract;
   ...

   procedure Push (List: in out Linked_List; Item: in  Element_Type);
   procedure Pop  (List: in out Linked_List; Item: out Element_Type);

   procedure Reverse_Push (List: in out Linked_List; Item: in
Element_Type);
   procedure Reverse_Pop  (List: in out Linked_List; Item: out
Element_Type);

   ... -- etc

end Containers.Utility.Lists;


In this way, a piece of software which only needs to iterate over a
container can be passed any of the list types, or other container types.
E.g.:


generic
   with package Specific_Containers is new Containers(<>);

procedure Print_a_List (List: in out
Specific_Containers.Sequence_Producer'Class);

...

   package Thingy_Containers is new Containers(Thingy_Type);

   Thingies_1: Thingy_Containers.Lists.Unbounded.Linked_List;
   Thingies_2: Thingy_Containers.Lists.Unbounded.Doubly_Linked_List;

   ...

   package Print_Thingies is new Print_a_List(Thingy_Containers);

   ...

   Print_Thingies(Thingies_1);
   Print_Thingies(Thingies_2);


We can call instantiations of Print_a_List with objects of type Linked_List,
or Doubly_Linked_List, or anything else (i.e. other containers) derived from
Sequence_Producer.

My choice of identifiers, and the details of my design may not be ideal, but
the basic idea is right.

Please don't get this elementary aspect of the design wrong!

--
Nick Roberts



"Ted Dennison" <dennison@telepath.com> wrote in message
news:kPoE7.9567$xS6.13287@www.newsranger.com...
> Since we do seem to be reaching a small amount of agreement on details, I
went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions
rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .
If it
> is close enough to be worth persuing, we may be able to use it as a
starting
> point.

Re: List container strawman

[M. A. Alves]

On Fri, 2 Nov 2001, Ted Dennison wrote:
> Since we do seem to be reaching a small amount of agreement on
> details, . . . I went ahead a put together a strawman package spec
> (sans private part) for the unbounded list container . . .
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> . . .

For some time ago now package Unbounded_Array has been serving me well.  A
public version is at

  http://lexis.di.fct.unl.pt/ADaLIB/misc.htm

and may be worth perusing.  A more recent version exists, if someone is
interest (the indicated version has a little bug, that site is no longer
under my control, I am also looking for web hosting for Adlib, Adlib
itself is changing status).

I would expect PragmArc, a very nice effort for an Ada standard components
library, to have a list containers package also--and very OO as you like
it.

Just my 2 cents for the List Container thread.

Cheers,

-- 
   ,
 M A R I O   data miner, LIACC, room 221   tel 351+226078830, ext 121
 A M A D O   Rua Campo Alegre, 823         fax 351+226003654
 A L V E S   P-4150 PORTO, Portugal        mob 351+939354002

Re: List container strawman

[Jeffrey Carter]

"M. A. Alves" wrote:
> 
> I would expect PragmArc, a very nice effort for an Ada standard components
> library, to have a list containers package also--and very OO as you like
> it.

Yes, I have already mentioned PragmARC.List_Unbounded_Unprotected in
this discussion, and there is also PragmARC.List_Unbounded which is task
safe. There are also unbounded stack and queue components built on the
list component, and bounded queue components.

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Re: List container strawman

[Ted Dennison]

In article <mailman.1005231504.1899.comp.lang.ada@ada.eu.org>, M. A. Alves
says...
>For some time ago now package Unbounded_Array has been serving me well.  A
>public version is at
>
>  http://lexis.di.fct.unl.pt/ADaLIB/misc.htm

I wouldn't be adverse to us doing something like that in a separate package (eg:
Containers.Vector if I use STL lingo). The implementation for using direct
indexing in Lists would probably be too inneficient to bother with though. But I
could see another package implementing a big chunk of contiguous storage, where
things like extending the size can be arbitrarily expensive but direct indexing
is O(1).

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Ehud Lamm]

This is indeed a useful abstraction.

Ehud