Reprise: 'in out' parameters for functions

Reprise: 'in out' parameters for functions

[Stephen Leake]

I just ran across a need for an 'in out' parameter in a function, in
"real code", so I thought I post it here "just for fun" :).

This is what I wanted to declare:

function Parse
  (Error_Label : in     String;
   Token       : in out Token_List.List_Iterator)
  return String;
  --  Process Token, which should contain '([Config_File =>] <string>)'.
  --  Return the string.
  --  Delete parsed tokens from Token.

Token must be 'in out', because the next parse function called wants
to work on the stuff after the config file.

Parse must be a function, because I'm returning a String.

The work-around is to use a procedure and a bounded string:

   procedure Parse
     (Error_Label      : in     String;
      Token            : in out Token_List.List_Iterator;
      Config_File_Name :    out OpenToken.Buffers.Bounded_String);

In this instance, the body of Parse deals with
OpenToken.Buffers.Bounded_String anyway, so there's no actual new
overhead introduced. But the user interface is not as clean as it
could be.

-- 
-- Stephe

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Stephen Leake <stephen_leake@acm.org> wrote:
 
:   Token       : in out Token_List.List_Iterator)
Is
    Token       : access Token_List.List_Iterator)
not an option?

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Georg Bauhaus" <sb463ba@l1-hrz.uni-duisburg.de> wrote in message
news:c546fd$lkb$3@a1-hrz.uni-duisburg.de...
> Stephen Leake <stephen_leake@acm.org> wrote:
>
> :   Token       : in out Token_List.List_Iterator)
> Is
>     Token       : access Token_List.List_Iterator)
> not an option?

It's rarely an option, because it (a) forces a particular declaration
('aliased') on users that have no need to know and (b) makes a messy call
with the need to use '[Unchecked_]Access in every call.

I prefer to simply make the List_Iterator a type that internally contains
indirection. (That usually requires it to be a controlled type). Then the
actual data can be manipulated.

But whether that solution is worth the extra work depends on how much the
interface is going to be used. (It isn't worth the effort for a rarely used
interface.)

                 Randy.

Re: Reprise: 'in out' parameters for functions

[okellogg]

On Apr 8 2004, 1:32 pm, Randy Brukardt wrote:
>
> "Georg Bauhaus" <sb463ba@l1-hrz.uni-duisburg.de> wrote in message
> news:c546fd$lkb$3@a1-hrz.uni-duisburg.de...
> > Stephen Leake <stephen_leake@acm.org> wrote:
> >
> > :   Token       : in out Token_List.List_Iterator)
> > Is
> >     Token       : access Token_List.List_Iterator)
> > not an option?
>
> It's rarely an option, because it (a) forces a particular declaration
> ('aliased') on users that have no need to know and (b) makes a messy
call
> with the need to use '[Unchecked_]Access in every call.
>

This triggers a different question:

With Ada2005's support for object-dot-operation notation, will it be
possible to write the following?

package test is
type obj_t is tagged private;
function f (self : access obj_t) return integer;
-- need 'access' mode here because f modifies self
private
-- ...
end test;

with test;
procedure main is
object : test.obj_t;
retval : integer;
begin
retval := object.f;
end main;


My point here is whether main.object need be declared aliased or not.
I would much prefer if it needn't be.

Thanks,

Oliver M. Kellogg

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"okellogg" <okellogg@freenet.de> wrote in message
news:1105542923.381339.189580@z14g2000cwz.googlegroups.com...
...
> This triggers a different question:
>
> With Ada2005's support for object-dot-operation notation, will it be
> possible to write the following?
>
> package test is
> type obj_t is tagged private;
> function f (self : access obj_t) return integer;
> -- need 'access' mode here because f modifies self
> private
> -- ...
> end test;
>
> with test;
> procedure main is
> object : test.obj_t;
> retval : integer;
> begin
> retval := object.f;
> end main;
>
>
> My point here is whether main.object need be declared aliased or not.
> I would much prefer if it needn't be.

I agree with you, but I lost that discussion. It was felt that it was
important that this notation was just syntactic sugar, and didn't have any
effect on semantics.

I would have prefered that "aliased" be not required for tagged objects at
all, given that they are always by reference anyway (and you can always take
'access of them once they're passed as a parameter), so there isn't much
point to the declaration. But some people thought that "aliased" was useful
for readers. I didn't press the point...

                            Randy.

Re: Reprise: 'in out' parameters for functions

[Stephen Leake]

Georg Bauhaus <sb463ba@l1-hrz.uni-duisburg.de> writes:

> Stephen Leake <stephen_leake@acm.org> wrote:
>  
> :   Token       : in out Token_List.List_Iterator)
> Is
>     Token       : access Token_List.List_Iterator)
> not an option?

Good point. I had not actually considered that. In general, access
types are as much a pain (in different ways) than globals.

List_Iterator itself is a private access type, so it's not much of a
stretch here.

-- 
-- Stephe

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Stephen Leake wrote:

> This is what I wanted to declare:
> 
> function Parse
>   (Error_Label : in     String;
>    Token       : in out Token_List.List_Iterator)
>   return String;
...
> The work-around is to use a procedure and a bounded string:
> 
>    procedure Parse
>      (Error_Label      : in     String;
>       Token            : in out Token_List.List_Iterator;
>       Config_File_Name :    out OpenToken.Buffers.Bounded_String);

IMHO a better workaround is to use an access parameter:

function Parse
    (Error_Label : in     String;
     Token       : access Token_List.List_Iterator)
    return String;

Yeah, I know, access is not a parameter mode.  But it certainly works 
like one which is why I tend to align access as if it were a mode.

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Alexander E. Kopilovich]

Stephen Leake wrote:

> I just ran across a need for an 'in out' parameter in a function, in
> "real code", so I thought I post it here "just for fun" :).
>
> This is what I wanted to declare:
>
> function Parse
>   (Error_Label : in     String;
>    Token       : in out Token_List.List_Iterator)
>   return String;
>   --  Process Token, which should contain '([Config_File =>] <string>)'.
>   --  Return the string.
>   --  Delete parsed tokens from Token.
>
> Token must be 'in out', because the next parse function called wants
> to work on the stuff after the config file.
>
> Parse must be a function, because I'm returning a String.
>
> The work-around is to use a procedure and a bounded string:
>
>    procedure Parse
>      (Error_Label      : in     String;
>       Token            : in out Token_List.List_Iterator;
>       Config_File_Name :    out OpenToken.Buffers.Bounded_String);
>
> In this instance, the body of Parse deals with
> OpenToken.Buffers.Bounded_String anyway, so there's no actual new
> overhead introduced. But the user interface is not as clean as it
> could be.

One thing is missing in this your explanation: why exactly you don't want to
make that List_Iterator global (instead of passing it as IN OUT argument) ?



Alexander Kopilovitch                      aek@vib.usr.pu.ru
Saint-Petersburg
Russia

Re: Reprise: 'in out' parameters for functions

[Stephen Leake]

"Alexander E. Kopilovich" <aek@VB1162.spb.edu> writes:

> Stephen Leake wrote:
> 
> > This is what I wanted to declare:
> >
> > function Parse
> >   (Error_Label : in     String;
> >    Token       : in out Token_List.List_Iterator)
> >   return String;
> >   --  Process Token, which should contain '([Config_File =>] <string>)'.
> >   --  Return the string.
> >   --  Delete parsed tokens from Token.
> >
> One thing is missing in this your explanation: why exactly you don't want to
> make that List_Iterator global (instead of passing it as IN OUT argument) ?

Hmm. I suppose that is a legitimate question. 

My answer is "I never make anything global unless it has to be,
because that usually leads to trouble".

In this case, Token is actually the contents of an aggregate, part of
a larger statement that is dynamically allocated. It must be modified
in place; copying it to a global to pass it to this routine would be a
maintenance nightmare.

And no, I don't consider "Ada doesn't allow 'in out' in functions" a
good reason to make something global; I'll change it to a procedure
first.

-- 
-- Stephe

Re: Reprise: 'in out' parameters for functions

[Alexander E. Kopilovich]

Stephen Leake wrote:

> > > This is what I wanted to declare:
> > >
> > > function Parse
> > >   (Error_Label : in     String;
> > >    Token       : in out Token_List.List_Iterator)
> > >   return String;
> > >   --  Process Token, which should contain '([Config_File =>] <string>)'.
> > >   --  Return the string.
> > >   --  Delete parsed tokens from Token.
> > >
> > One thing is missing in this your explanation: why exactly you don't want to
> > make that List_Iterator global (instead of passing it as IN OUT argument) ?

> My answer is "I never make anything global unless it has to be,
> because that usually leads to trouble".

Yes, but this is general attitude, and it says nothing definite about
particular case - it can be that detailed analysis of this particular case
will show reasons to make it global.

> In this case, Token is actually the contents of an aggregate, part of
> a larger statement that is dynamically allocated. It must be modified
> in place; copying it to a global to pass it to this routine would be a
> maintenance nightmare.

I did not think about copying. I think that real question may be whether
Parse conceptually deals with Token_List.List_Iterator or with the whole
List_Iterator. In the latter case a global is generally possible without any
copying.

> And no, I don't consider "Ada doesn't allow 'in out' in functions" a
> good reason to make something global; I'll change it to a procedure
> first.

Certainly. But there may be other reasons (originated from detailed design).



Alexander Kopilovich                      aek@vib.usr.pu.ru
Saint-Petersburg
Russia

Re: Reprise: 'in out' parameters for functions

[Stephen Leake]

"Alexander E. Kopilovich" <aek@VB1162.spb.edu> writes:

> Stephen Leake wrote:
> 
> > > > This is what I wanted to declare:
> > > >
> > > > function Parse
> > > >   (Error_Label : in     String;
> > > >    Token       : in out Token_List.List_Iterator)
> > > >   return String;
> > > >   --  Process Token, which should contain '([Config_File =>] <string>)'.
> > > >   --  Return the string.
> > > >   --  Delete parsed tokens from Token.
> > > >
> > > One thing is missing in this your explanation: why exactly you don't want to
> > > make that List_Iterator global (instead of passing it as IN OUT argument) ?
> > In this case, Token is actually the contents of an aggregate, part of
> > a larger statement that is dynamically allocated. It must be modified
> > in place; copying it to a global to pass it to this routine would be a
> > maintenance nightmare.
> 
> I did not think about copying. I think that real question may be whether
> Parse conceptually deals with Token_List.List_Iterator or with the whole
> List_Iterator. In the latter case a global is generally possible without any
> copying.

Yes, there are times when globals are appropriate. No, this is not one
of those times. You'll just have to take my word for it.

Ada has a wart. Let's admit it, and move on.
-- 
-- Stephe

Re: Reprise: 'in out' parameters for functions

[Florian Weimer]

Stephen Leake <stephen_leake@acm.org> writes:

> Ada has a wart. Let's admit it, and move on.

Can't we fix that one without breaking backwards compatibility?  Or
are politics involved?

-- 
Current mail filters: many dial-up/DSL/cable modem hosts, and the
following domains: postino.it, tiscali.co.uk, tiscali.cz, tiscali.it,
voila.fr.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Florian Weimer wrote:

> Stephen Leake <stephen_leake@acm.org> writes:
> 
>> Ada has a wart. Let's admit it, and move on.
> 
> Can't we fix that one without breaking backwards compatibility?

procedure Has_A_Result (...) return Result;

> Or are politics involved?

I think so. But there also is the problem of evaluation order, though simply
ignored for access parameters of functions.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Martin Krischik]

Dmitry A. Kazakov wrote:

> Florian Weimer wrote:
> 
>> Stephen Leake <stephen_leake@acm.org> writes:
>> 
>>> Ada has a wart. Let's admit it, and move on.
>> 
>> Can't we fix that one without breaking backwards compatibility?
> 
> procedure Has_A_Result (...) return Result;

This solution would call for precise documentation (advantages,
disadvantages) etc. pp. Plus a quick summary ("functions are faster") for
the beginner.

Otherwise the same problems as with "access all" will arise. Many programers
use "access all" all the time - even when not needed, ignoring the
diadvantages.

>> Or are politics involved?
> 
> I think so. But there also is the problem of evaluation order, though
> simply ignored for access parameters of functions.

See above. Have you heard of GNATs "pragma Pure_Function"?

Prehaps making function even more restive plus procedures with return plus a
"functions are faster" statement might do the trick.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Martin Krischik wrote:

> Dmitry A. Kazakov wrote:
> 
>> Florian Weimer wrote:
>> 
>>> Stephen Leake <stephen_leake@acm.org> writes:
>>> 
>>>> Ada has a wart. Let's admit it, and move on.
>>> 
>>> Can't we fix that one without breaking backwards compatibility?
>> 
>> procedure Has_A_Result (...) return Result;
> 
> This solution would call for precise documentation (advantages,
> disadvantages) etc. pp. Plus a quick summary ("functions are faster") for
> the beginner.
>
> Otherwise the same problems as with "access all" will arise. Many
> programers use "access all" all the time - even when not needed, ignoring
> the diadvantages.

This is very true. And there is also a nasty problem with specific access
types for beginners:
 
   type Root is tagged ...;
   type Handle is access Root'Class;

   type Derived is new Root with ...;
   type Derived_Ptr is access Derived;

function Factory return Handle is
   Ptr : Derived_Ptr := new Derived;
begin
   Prepare (Ptr.all);
   return Handle (Ptr); -- Error!
end Factory;

Should cast:

function Factory return Handle is
   Ptr : Handle := new Derived;
begin
   Prepare (Derived (Ptr.all));
   return Ptr;
end Factory;

>>> Or are politics involved?
>> 
>> I think so. But there also is the problem of evaluation order, though
>> simply ignored for access parameters of functions.
> 
> See above. Have you heard of GNATs "pragma Pure_Function"?

Yes, it is a very good thing. I'd like to see it in the standard and
moreover not as a pragma, but as a part of the syntax (in the contract). It
could be very useful, for example, to declare an abstract function as pure,
to force any implementation to conform. Even more useful would be to allow
pure functions in static expressions. The compiler could get an advantage
from knowing that a function is pure:

while Match (Pattern ("..."), Standard_Input) loop
   ... -- Pattern is pure, so the result is a constant
end loop; 

> Prehaps making function even more restive plus procedures with return plus
> a "functions are faster" statement might do the trick.

I think that one should also either 1) fix evaluation order for non-pure
functions and procedures with results or, better, but backward
incompatible, 2) disallow them where the order is not fixed.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:c565si$2qlp6q$1@ID-77047.news.uni-berlin.de...
> Martin Krischik wrote:
> > See above. Have you heard of GNATs "pragma Pure_Function"?
>
> Yes, it is a very good thing. I'd like to see it in the standard and
> moreover not as a pragma, but as a part of the syntax (in the contract).
It
> could be very useful, for example, to declare an abstract function as
pure,
> to force any implementation to conform. Even more useful would be to allow
> pure functions in static expressions. The compiler could get an advantage
> from knowing that a function is pure:

I agree with all of this too. Also not going to happen. See AI-290, also
voted "No Action".

               Randy.

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Randy Brukardt wrote:

> I agree with all of this too. Also not going to happen. See AI-290, also
> voted "No Action".

On pragma Pure and static expressions, I think that you (Randy) are 
being a little premature.  It may come up again for Ada 1Z.  AI-290 is 
about pragma Pure_Function.

Of course, I think that in out for functions is never going to happen. 
(The idea of making 'Access implicit in some contexts is interesting, 
and may end up allowing the reality without changing the rule.)  If you 
want in out parameters for functions, use GNAT and modify it, or use the 
existing GNAT value returning proceedure pragma.

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Robert I. Eachus" <rieachus@comcast.net> wrote in message
news:kf2dnS2GIr_00ODdRVn-hA@comcast.com...
> Randy Brukardt wrote:
>
> > I agree with all of this too. Also not going to happen. See AI-290, also
> > voted "No Action".
>
> On pragma Pure and static expressions, I think that you (Randy) are
> being a little premature.  It may come up again for Ada 1Z.  AI-290 is
> about pragma Pure_Function.

Well, I'm not considering what may or may not happen in Ada 1Z. If it has
the same ground rules as Ada 0Y has, then "not going to happen" is probably
accurate. But, in any case, in a business that moves as fast as the computer
business, the difference between "not sooner than 12-15 years from now" and
"not going to happen" is not particularly interesting.

                   Randy.

Re: Reprise: 'in out' parameters for functions

[Florian Weimer]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> > Can't we fix that one without breaking backwards compatibility?
> 
> procedure Has_A_Result (...) return Result;

Well, this is solution is obviously quite bad because "procedure" and
"function" are now almost (but not quite) interchangeable.

> > Or are politics involved?
> 
> I think so. But there also is the problem of evaluation order,
> though simply ignored for access parameters of functions.

Does making parameters "in out" really make things considerably worse?

-- 
Current mail filters: many dial-up/DSL/cable modem hosts, and the
following domains: postino.it, tiscali.co.uk, tiscali.cz, tiscali.it,
voila.fr.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Florian Weimer wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> > Can't we fix that one without breaking backwards compatibility?
>> 
>> procedure Has_A_Result (...) return Result;
> 
> Well, this is solution is obviously quite bad because "procedure" and
> "function" are now almost (but not quite) interchangeable.

Isn't an access parameter almost interchangeable with an "in out" parameter?
The word "procedure" tells that there are many results. "Return" tells that
among them there is one dedicated.

>> > Or are politics involved?
>> 
>> I think so. But there also is the problem of evaluation order,
>> though simply ignored for access parameters of functions.
> 
> Does making parameters "in out" really make things considerably worse?

Let me use your argument: what would be the difference between "function"
and "procedure" then?

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Florian Weimer]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:


> > Well, this is solution is obviously quite bad because "procedure" and
> > "function" are now almost (but not quite) interchangeable.
> 
> Isn't an access parameter almost interchangeable with an "in out"
> parameter?

No, it isn't.  You can't obtain an access value for most objects.

> Let me use your argument: what would be the difference between "function"
> and "procedure" then?

Its use.  A procedure call is a statement, a function call is a name
(and thus part of an expression).

-- 
Current mail filters: many dial-up/DSL/cable modem hosts, and the
following domains: postino.it, tiscali.co.uk, tiscali.cz, tiscali.it,
voila.fr.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Florian Weimer wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> > Well, this is solution is obviously quite bad because "procedure" and
>> > "function" are now almost (but not quite) interchangeable.
>> 
>> Isn't an access parameter almost interchangeable with an "in out"
>> parameter?
> 
> No, it isn't.  You can't obtain an access value for most objects.

So what? The only reasonable use of an access parameter is to have "in out"
where it is not allowed. [I do not count circumventing by-copy parameter
passing for reasonable]

>> Let me use your argument: what would be the difference between "function"
>> and "procedure" then?
> 
> Its use.  A procedure call is a statement, a function call is a name
> (and thus part of an expression).

Expression is a part of a statement, so I see as much difference as between
+ and "+".

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:

 
:  The only reasonable use of an access parameter is to have "in out"
: where it is not allowed.

Access parameters go well with access discriminants...?

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Georg Bauhaus wrote:

> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> 
> :  The only reasonable use of an access parameter is to have "in out"
> : where it is not allowed.
> 
> Access parameters go well with access discriminants...?

Yes, but

1) .all works fine. If that is too much to type one could make access types
more transparent.

2) why don't we have discriminants of any type? In many cases discriminants
are used just because of absence of MI.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Stephen Leake]

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

> Stephen Leake <stephen_leake@acm.org> writes:
> 
> > Ada has a wart. Let's admit it, and move on.
> 
> Can't we fix that one without breaking backwards compatibility?  

We could; simply permit 'in out' in functions.

> Or are politics involved?

Yes. There are some people (members of the ARG included) who don't
want 'in out' in functions.

I have only talked seriously with one person who holds that view (Rod
Chapman, at the last SigAda). I can't really do justice to his view
here, so I won't try, but it was based on serious considerations. I
had the impression that if I spent enough time, I could convince him
to change. On the other hand, he may have had the same impression
about me :).

As Robert Dewar says, there are no new arguments here, so there is no
reason to reopen the discussion. I was just venting :).

-- 
-- Stephe

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87brm1pksa.fsf@deneb.enyo.de...
> Stephen Leake <stephen_leake@acm.org> writes:
>
> > Ada has a wart. Let's admit it, and move on.
>
> Can't we fix that one without breaking backwards compatibility?  Or
> are politics involved?

Sure. But there is no will. So it won't be fixed. (See AI-323, voted "No
Action").

             Randy.

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Hello,

> Ada has a wart. Let's admit it, and move on.

Several warts. For example, abstraction inversion (just look at ACT
PolyOrb code, or try to implement tree crabbing), type system unable
to express physical units, very limited standard library (compare it
to say CM3 Modula, or Java). But the problem real problem IMO is that
the development of the language has stagnated.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Wojtek Narczynski <wojtek@power.com.pl> wrote:
: Several warts. For example, abstraction inversion (just look at ACT
: PolyOrb code, or try to implement tree crabbing),

I take it Ada forces abstraction in version in cases?
Could you name an example unit to look at?

: type system unable
: to express physical units,

Still, you might have

   type Quantity is abstract tagged private;

   function in_meters (x: Quantity) return Units.meter;
   function in_yards (x: Quantity) return Units.yard;
   --  etc...

: But the problem real problem IMO is that
: the development of the language has stagnated.

What's missing?

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Hello,

> I take it Ada forces abstraction in version in cases?
> Could you name an example unit to look at?

'Inversion' not 'in version' incase it were more than a typo. When you
implement a semaphore over a protected object, or in general when you
need to lock / unlock by yourself. Classic example:

polyorb-tasking-profiles-full_tasking-mutexes.adb

Or try to implement tree crabbing. Hell, try to implement a list
updateable concurrently from multiple tasks. You _will_ end up
implementing a semaphore over a protected, over a semaphore.

Or the simplest possible: two protected counters, try to get the sum
atomically.

> : type system unable
> : to express physical units,
> 
> Still, you might have
> 
>    type Quantity is abstract tagged private;
> 
>    function in_meters (x: Quantity) return Units.meter;
>    function in_yards (x: Quantity) return Units.yard;
>    --  etc...

Sure, let us continue:

function in_kilograms (x: Quantity) return Units.yard;
-- Blows at runtime

This just cannot be done right in Ada.

> : But the problem real problem IMO is that
> : the development of the language has stagnated.
> 
> What's missing?

From the language? For example parameters for exceptions.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Wojtek Narczynski <wojtek@power.com.pl> wrote:
: Hello,
: 
:> I take it Ada forces abstraction in version in cases?
:> Could you name an example unit to look at?
: 
: 'Inversion' not 'in version' incase it were more than a typo.

A typo, sorry.

: When you
: implement a semaphore over a protected object, or in general when you
: need to lock / unlock by yourself. Classic example:
: 
: polyorb-tasking-profiles-full_tasking-mutexes.adb

Thanks. Given that mutex and semaphores have been known
when Ada was made, I wonder whether there aren't some
external forces at work which lead to the requirement
of using tasking constructs below language level.
Not Ada's fault from this perspective.

Incidentally, there is some abstraction inversion criticism
quoting Ada, mutex, and tasks. But has not been brought up
to date where date refers to 1995. So there is another
meaning of "classic".

 
: function in_kilograms (x: Quantity) return Units.yard;
: -- Blows at runtime

I don't think so. How do you write an expression expecting
Unis.kilogram, where the compiler sees a function returning
Units.yard, such that the compiler does not reject?

: This just cannot be done right in Ada.


:> What's missing?
: 
: From the language? For example parameters for exceptions.

Not a good idea I think, though practical for use in quick and
dirty fixes of design errors. Programm logic can be programmed.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

>> I take it Ada forces abstraction in version in cases?
>> Could you name an example unit to look at?
> 
> 'Inversion' not 'in version' incase it were more than a typo. When you
> implement a semaphore over a protected object, or in general when you
> need to lock / unlock by yourself. Classic example:
> 
> polyorb-tasking-profiles-full_tasking-mutexes.adb
> 
> Or try to implement tree crabbing. Hell, try to implement a list
> updateable concurrently from multiple tasks. You _will_ end up
> implementing a semaphore over a protected, over a semaphore.
> 
> Or the simplest possible: two protected counters, try to get the sum
> atomically.

This has nothing to do with abstraction inversion. The problem here is that
Ada does not have multiple protected actions. Same problem with tasks,
there cannot be rendezvous with multiple tasks. It is much work to solve
that. Especially to convince people that prefix notation is inherently bad.

>> : type system unable
>> : to express physical units,
>> 
>> Still, you might have
>> 
>>    type Quantity is abstract tagged private;
>> 
>>    function in_meters (x: Quantity) return Units.meter;
>>    function in_yards (x: Quantity) return Units.yard;
>>    --  etc...
> 
> Sure, let us continue:
> 
> function in_kilograms (x: Quantity) return Units.yard;
> -- Blows at runtime
> 
> This just cannot be done right in Ada.

This is wrong:

http://home.t-online.de/home/Christ-Usch.Grein/Ada/Dimension.html

The type system is capable to express dimensioned units. The major problem
here is not the type system, but inability to get rid of statically known
discriminants, which makes an implementation inefficient.

>> : But the problem real problem IMO is that
>> : the development of the language has stagnated.
>> 
>> What's missing?
> 
> From the language? For example parameters for exceptions.

How they could have parameters? There are only two ways for dealing with
exceptions. Either 1) all of them are of one [specific] type (maybe an
implicit one) or 2) they are of different types (maybe rooted in the same
root type [class-wide approach]). Ada has 1), which excludes parameters. If
you think that 2) would be better for Ada then solve the following:

generic
package Crazy is
   type Virtual is new Exception with ...;
      -- Note that Virtual exists in an instance of Crazy only.
      -- It is finalized together with the instance.
   procedure Show_Me (Object : Virtual);
end Crazy;

package body Crazy is
   Local : Integer := 0;

   procedure Show_Me (Object : Virtual) is
   begin
      Put_Line (Integer'Image (Local));
   end Show_Me;
begin
   raise Virtual (your fine parameters);
end Crazy;

declare
   package Catch_It is new Crazy;
begin
   null;
exception
   when Error : others =>
      -- What sort of type has Error?
      -- Can I dispatch to Show_Me?
      -- What it will print?

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Dimitry,

> This has nothing to do with abstraction inversion. 

Would you please take care to explain to me, what abstraction
inversion is, according to you? For me abstraction inversion is when
you need to build low level primitives from high level primitives
(built on low level primitives), because the high level primitives are
not expressive enough.

> The problem here is that Ada does not have multiple
> protected actions.

Google has not heard of "multiple protected actions", neither have I.
But I think know what you mean, for my own needs I was calling this
"compound protected". It seems to require proper tail recursion to
work.

At least we seem to agree that Ada concurrency features also have
warts.

---

> This is wrong:
> 
> http://home.t-online.de/home/Christ-Usch.Grein/Ada/Dimension.html
> 
> The type system is capable to express dimensioned units.

By "express" I don't mean bent over in an such a way that your
compiler checked your units for you, nor have your compiler mostly
check your units for you, nor write yet another compiler to work on
top of your compiler. I mean have your compiler statically check your
units for you.

I am afraid that this link show exactly that I am, unfortunately,
right. The two compile time solutions are: 1. "Checks in assignments
concerning physical dimensions are not performed.", 2. From what I've
been able to understand Macks has a language, which compiles to Ada.

---

> > From the language? For example parameters for exceptions.
> 
> How they could have parameters? There are only two ways for dealing
> with  exceptions. Either 1) all of them are of one [specific] type
> (maybe an implicit one) or 2) they are of different types (maybe
> rooted in the same root type [class-wide approach]).

You seem to be very well educated in Matematics. Thus you know that
inexistence proofs are among the hardest. Please don't provoke me to
ask you to proove that there are only two ways of dealing with
exceptions.

And once you assume false, you can prove anything.

> Ada has 1), which excludes parameters. If you think that 2) would be
> better for Ada then solve the following:

You assumed that the root type for Exception would be tagged record.
Indeed with this assumption it may be hard to maintain the conceptual
integrity of the language. But I think this level of parametrization
is an overkill. I'd rather use something like "discriminated records
with discriminants only".

Here is a version to start with (which actually compiles and "works"):

generic
package Crazy is
   Bang: exception;
   function T return Boolean;
end Crazy;
 
package body Crazy is
   function T return Boolean is begin return True; end T;
begin
   raise Bang;
end Crazy;

with Crazy;
procedure Sample is
   package Catch_It is new Crazy;
begin
   null;
exception
   when Catch_It.Bang => 
      null;
end Sample;


Here is a parametrized version:

generic
package Crazy is
 
   type Severity_Type is (Hard, Tough, Difficult, Killer, ...);
   type Urgency_Type is (Urgent, Immediate, Now, Asap, ...);
   type Native_Code_Type is new Integer;
 
   exception Bang (Severity : Severity_Type;
      Urgency : Urgency_Type; Native_Code : Native_Code_Type)
 
   function T return Boolean;
 
end Crazy;
 
package body Crazy is
   function T return Boolean is begin return True; end T;
begin
   raise Bang( Hard, Urgent, -1);
end Crazy;

with Crazy;
procedure Sample is
   package Catch_It is new Crazy;
begin
   null;
exception
   when B : Catch_It.Bang =>
      -- Here you'd be are able to access the values,
      -- but not to call anything from the already gone package.
      -- Regarding scope it is not any differnt from the previous
      -- example - we were also accessing Bang in hander.
      Put_Line (B.Severity);
      Put_Line (B.Urgency);
      Put_Line (B.Native_Code);
end Sample;

Please note that this actually works in Modula-3, but you are only
limited to one parameter. Well, all languages have their warts.

GNAT.Sockets is perhaps the best example how the code could benefit
from parametrized exceptions. There you have Socket_Error and that's
it. You need to use compiler specific tricks to extract more info. Or
you can declare a coule dozen of different exceptions. Or a couple
hundred, it depends.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Wojtek Narczynski <wojtek@power.com.pl> wrote:


: I mean have your compiler statically check your
: units for you.

IIRC, Hyman Rosen has demonstrated, a few month ago, how
this can be done with C++ templates.

Re: Reprise: 'in out' parameters for functions

[Georg Bauhaus]

Wojtek Narczynski <wojtek@power.com.pl> wrote:
:   raise Bang( Hard, Urgent, -1);

Isn't this just a work around a message passing technique?
If I have a task that may fail in a few hundred ways, and
I know another service task that can deal with these errors, 
I just say attention_please( Hard, Urgent, -1); to this task,
and then abort the first, for example.

Absent tasks, if I jump long with parameters, doesn't this parameter
passing mechanism for "exceptional gotos" create a situation where
program flow is just as hard to follow, or even more so because
the tasking protocol won't be taken into account?

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

>> This has nothing to do with abstraction inversion.
> 
> Would you please take care to explain to me, what abstraction
> inversion is, according to you? For me abstraction inversion is when
> you need to build low level primitives from high level primitives
> (built on low level primitives), because the high level primitives are
> not expressive enough.

or because of using them in an inappropriate way?

However it is questionable, whether protected objects have a higher level of
abstraction than semaphores. They are more generic but no less fundamental.

>> The problem here is that Ada does not have multiple
>> protected actions.
> 
> Google has not heard of "multiple protected actions", neither have I.

ARM 9.5.1 defines "protected action"

> But I think know what you mean, for my own needs I was calling this
> "compound protected". It seems to require proper tail recursion to
> work.

What I meant is the following. Presently one can define an entry to only of
one protected object or task.

Provided that:

1) protected object and tasks would be tagged (inheritable from);
2) multiple inheritance would be supported;
3) entries, procedures and functions would be primitive operations;
4) functional notation would be permitted (instead of prefix notation)

one could have entries of multiple protected objects and tasks. A call to
such entry would start multiple protected actions (one per each protected
object parameter) and multiple rendezvous (one per each task object
parameter). Could we agree that 1-4 is a damn *lot* of work?

BTW, for your protected counters example, (4) would be enough:

protected type Counter is
   procedure Inc; -- Increments this counter
private
   Value : Integer := 0;
end Counter;

procedure Inc_One (First : in out Counter);
   -- Same as Inc, but uses functional notation
procedure Inc_Two (First, Second : in out Counter);
   -- Increments two counters atomically, starts two protected actions,
   -- one per argument

> At least we seem to agree that Ada concurrency features also have
> warts.

I do not see them as warts. Nothing is inherently wrong with them. They
might be extended in a consistent way to make the language more regular
(see 1-4). Make an AI and send it to ARG! (:-))

>> This is wrong:
>> 
>> http://home.t-online.de/home/Christ-Usch.Grein/Ada/Dimension.html
>> 
>> The type system is capable to express dimensioned units.
> 
> By "express" I don't mean bent over in an such a way that your
> compiler checked your units for you, nor have your compiler mostly
> check your units for you, nor write yet another compiler to work on
> top of your compiler. I mean have your compiler statically check your
> units for you.
> 
> I am afraid that this link show exactly that I am, unfortunately,
> right. The two compile time solutions are: 1. "Checks in assignments
> concerning physical dimensions are not performed.", 2. From what I've
> been able to understand Macks has a language, which compiles to Ada.

First of all I do not count compile time solutions for true solutions. A
true one would include an ability to work with dimensioned values which
units are unknown at compile time. A simpliest possible example is to write
a physicist calculator.

So to solve the problem one should either use tagged types or discriminated
ones. And this indeed works in Ada.

Now to static checks. Nothing in Ada prevents a compiler to from checking
discriminants or type tags statically.

What I see as a real problem is that neither discriminants nor type tags can
be removed from an object if they are statically known. On the contrary
array bounds are indeed removed.

So again, we have more fundamental and complex problem than just "let's
remove a wart".

>> > From the language? For example parameters for exceptions.
>> 
>> How they could have parameters? There are only two ways for dealing
>> with  exceptions. Either 1) all of them are of one [specific] type
>> (maybe an implicit one) or 2) they are of different types (maybe
>> rooted in the same root type [class-wide approach]).
> 
> You seem to be very well educated in Matematics. Thus you know that
> inexistence proofs are among the hardest. Please don't provoke me to
> ask you to proove that there are only two ways of dealing with
> exceptions.

OK, there are only two ways I know of, if you find a third way...

> And once you assume false, you can prove anything.
>
>> Ada has 1), which excludes parameters. If you think that 2) would be
>> better for Ada then solve the following:
> 
> You assumed that the root type for Exception would be tagged record.

See above, either you derive a new type or not. There is no third way.

> Indeed with this assumption it may be hard to maintain the conceptual
> integrity of the language. But I think this level of parametrization
> is an overkill. I'd rather use something like "discriminated records
> with discriminants only".

How it differs from (2)? You just replaced the official mechanism of
inheritance with some hard-wired other. Discriminants are just special kind
of members.

> Here is a version to start with (which actually compiles and "works"):
> 
> generic
> package Crazy is
>    Bang: exception;
>    function T return Boolean;
> end Crazy;
>
[...]  
>  
> package body Crazy is
>    function T return Boolean is begin return True; end T;
> begin
>    raise Bang( Hard, Urgent, -1);
> end Crazy;
> 
> with Crazy;
> procedure Sample is
>    package Catch_It is new Crazy;
> begin
>    null;
> exception
>    when B : Catch_It.Bang =>

This won't work. The exception out of Catch_It will be propagated *after*
"end Sample". So you cannot catch it here! In any point you could, the type
B will be already finalized. So you would have a zombie object of an
unexisting type.

>       -- Here you'd be are able to access the values,
>       -- but not to call anything from the already gone package.
>       -- Regarding scope it is not any differnt from the previous
>       -- example - we were also accessing Bang in hander.
>       Put_Line (B.Severity);
>       Put_Line (B.Urgency);
>       Put_Line (B.Native_Code);
> end Sample;

As I said, because it is in fact (2) it has all its problems:

generic
package Crazy is
   exception Bang (Times : access Integer);
end Crazy;

package body Crazy is
   I : aliased Integer := 0; 
begin
   raise Bang (I'Access);
end Crazy;

> Please note that this actually works in Modula-3, but you are only
> limited to one parameter. Well, all languages have their warts.

This works in C++ too, because all functions and types are global there. I'd
better stick to Ada's way.

> GNAT.Sockets is perhaps the best example how the code could benefit
> from parametrized exceptions. There you have Socket_Error and that's
> it. You need to use compiler specific tricks to extract more info. Or
> you can declare a coule dozen of different exceptions. Or a couple
> hundred, it depends.

Why (1) cannot work here? The only real problem with (1) I can see, is that
the exception type does not have ranges or other forms of subsets. One need
some syntactic suggar to define a set of exceptions which could be then
named in "when".

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:c5b6pt$2pcs4d$2@ID-77047.news.uni-berlin.de...
...
> Provided that:
>
> 1) protected object and tasks would be tagged (inheritable from);
> 2) multiple inheritance would be supported;
> 3) entries, procedures and functions would be primitive operations;
> 4) functional notation would be permitted (instead of prefix notation)

See AI-345, which extends the interface mechanism (itself a Ada 200y
proposal) to cover task and protected types. (1) is true if the PT or TT
inherits from one or more interfaces; (2) follows from the definition of
interfaces; (3) is true for calls through interfaces (as opposed to directly
to the PO or TOs); (4) is true for calls through interfaces.

> one could have entries of multiple protected objects and tasks.

I don't see how this follows from (1) to (4), though. Each call is just a
dispatching call to a single operation; there is no implementation
inheritance.

> A call to such entry would start multiple protected actions (one per each
protected
> object parameter) and multiple rendezvous (one per each task object
> parameter). Could we agree that 1-4 is a damn *lot* of work?

Not really. *Interfaces* is a lot of work, but presuming that we're going to
have those anyway, adding protected and task support to them is not a
significant increment.

                 Randy.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:c5b6pt$2pcs4d$2@ID-77047.news.uni-berlin.de...
> ...
>> Provided that:
>>
>> 1) protected object and tasks would be tagged (inheritable from);
>> 2) multiple inheritance would be supported;
>> 3) entries, procedures and functions would be primitive operations;
>> 4) functional notation would be permitted (instead of prefix notation)
> 
> See AI-345, which extends the interface mechanism (itself a Ada 200y
> proposal) to cover task and protected types. (1) is true if the PT or TT
> inherits from one or more interfaces; (2) follows from the definition of
> interfaces; (3) is true for calls through interfaces (as opposed to
> directly to the PO or TOs); (4) is true for calls through interfaces.
> 
>> one could have entries of multiple protected objects and tasks.
> 
> I don't see how this follows from (1) to (4), though. Each call is just a
> dispatching call to a single operation; there is no implementation
> inheritance.

Yes, but if I could have two dispatching parameters of same protected type
(no MD involved) in a primitive operation, then a call to it should start
two protected actions. Same with task entries, (4) should allow something
like:

task type Foo is ... end Foo;
entry Double_Rendezvous (X, Y : in out Foo);
   -- Declared after "end Foo";

task body Foo is
begin
   loop
      accept Double_Rendezvouz;
         -- Cannot give the body here
   end loop;
end Foo;

entry Double_Rendezvouz (X, Y : in out Foo) is
begin
   ...
end Double_Rendezvouz;

[ I cannot see any direct use of things like that, except for demonstrating
race conditions to students (:-)), but who knows... ]

>> A call to such entry would start multiple protected actions (one per each
> protected
>> object parameter) and multiple rendezvous (one per each task object
>> parameter). Could we agree that 1-4 is a damn *lot* of work?
> 
> Not really. *Interfaces* is a lot of work, but presuming that we're going
> to have those anyway, adding protected and task support to them is not a
> significant increment.

I am glad to hear it from you, because of course, you know it better.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:c5gh0e$1ba02$3@ID-77047.news.uni-berlin.de...
> Randy Brukardt wrote:
>
> > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> > news:c5b6pt$2pcs4d$2@ID-77047.news.uni-berlin.de...
> > ...
...
> > I don't see how this follows from (1) to (4), though. Each call is just
a
> > dispatching call to a single operation; there is no implementation
> > inheritance.
>
> Yes, but if I could have two dispatching parameters of same protected type
> (no MD involved) in a primitive operation, then a call to it should start
> two protected actions. Same with task entries, (4) should allow something
> like:
>
> task type Foo is ... end Foo;
> entry Double_Rendezvous (X, Y : in out Foo);
>    -- Declared after "end Foo";

This isn't allowed by AI-345; entries can only be declared inside a task
(with the current rules). An interface can have procedures that match
entries (and interface procedure calls can be used in select statements),
but there is no separate existence to entries.

You could declare a procedure like that

procedure Double_Rendezvous (X, Y : in out Foo);

but of course it doesn't have any special semantics.

...
> >> A call to such entry would start multiple protected actions (one per
each protected
> >> object parameter) and multiple rendezvous (one per each task object
> >> parameter). Could we agree that 1-4 is a damn *lot* of work?
> >
> > Not really. *Interfaces* is a lot of work, but presuming that we're
going
> > to have those anyway, adding protected and task support to them is not a
> > significant increment.
>
> I am glad to hear it from you, because of course, you know it better.

I should point out that not everyone agrees with my assessment here. But
it's not clear to me that everyone understands the implementation model for
these, so they may be trying a harder-than-necessary implementation
approach.

                  Randy.

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Randy Brukardt wrote:

> An interface can have procedures that match
> entries (and interface procedure calls can be used in select statements),
> but there is no separate existence to entries.

I see, it is a one-way road. (:-))

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Dimitry,

You silently refused to say what abstraction inversion is according to
you :-)

> However it is questionable, whether protected objects have a higher level of
> abstraction than semaphores. They are more generic but no less fundamental.

Well, let's look at them as manual (semaphores) vs. automated
(protected objects).

> BTW, for your protected counters example, (4) would be enough:
> 
> protected type Counter is
>    procedure Inc; -- Increments this counter
> private
>    Value : Integer := 0;
> end Counter;
> 
> procedure Inc_One (First : in out Counter);
>    -- Same as Inc, but uses functional notation
> procedure Inc_Two (First, Second : in out Counter);
>    -- Increments two counters atomically, starts two protected actions,
>    -- one per argument

Cool. 

> First of all I do not count compile time solutions for true solutions. A
> true one would include an ability to work with dimensioned values which
> units are unknown at compile time. A simpliest possible example is to write
> a physicist calculator.

Then we're talking about two distinct things. I am talking about a
compile time solution only.

> OK, there are only two ways I know of, if you find a third way...

The first way can be viewed as an incarnation of the second. 

Or you can ensure that there are no runtime exceptions.

> How it differs from (2)? You just replaced the official mechanism of
> inheritance with some hard-wired other. Discriminants are just special kind
> of members.

It differst in that it can be implemented, because there are no
pointers to inexistent trampolines, only (immutable, integer) values.

> This won't work. The exception out of Catch_It will be propagated *after*
> "end Sample". So you cannot catch it here! In any point you could, the type
> B will be already finalized. So you would have a zombie object of an
> unexisting type.

Well, this is how it goes with exceptions. That's why the "type"
should be limited (in ordinary sense) to only: declaration, raising /
construction, catching and extracting immutable values in handlers.

> Why (1) cannot work here? The only real problem with (1) I can see, is that
> the exception type does not have ranges or other forms of subsets. One need
> some syntactic suggar to define a set of exceptions which could be then
> named in "when".

Feel free to perceive my 'code' as syntactic sugar.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

> Dimitry,
> 
> You silently refused to say what abstraction inversion is according to
> you :-)

We can use your definition if you want. (:-))

>> First of all I do not count compile time solutions for true solutions. A
>> true one would include an ability to work with dimensioned values which
>> units are unknown at compile time. A simpliest possible example is to
>> write a physicist calculator.
> 
> Then we're talking about two distinct things. I am talking about a
> compile time solution only.

Why should they be distinct? The key advantage of Ada strings as compared to
Pascal ones, is that they works in both static and dynamic cases. Why units
should be handled otherwise? How would you then mix both approaches in one
program? In my view a real solution should respond the requirements I
mentioned in another thread answering Russ.

>> OK, there are only two ways I know of, if you find a third way...
> 
> The first way can be viewed as an incarnation of the second.

Surely the second way is more general.

> Or you can ensure that there are no runtime exceptions.

I didn't say that (2) is not solvable. I just invited you to think about it
more deeply, before making some final statements. For example, one could
make the exception object mutating to its parent type, when the exception
type goes out of scope. This would then influnce the language. In which
way? What are the consequences, I mean all consequences, etc.

>> How it differs from (2)? You just replaced the official mechanism of
>> inheritance with some hard-wired other. Discriminants are just special
>> kind of members.
> 
> It differst in that it can be implemented, because there are no
> pointers to inexistent trampolines, only (immutable, integer) values.

Discriminants can be of access types.

>> This won't work. The exception out of Catch_It will be propagated *after*
>> "end Sample". So you cannot catch it here! In any point you could, the
>> type B will be already finalized. So you would have a zombie object of an
>> unexisting type.
> 
> Well, this is how it goes with exceptions. That's why the "type"
> should be limited (in ordinary sense) to only: declaration, raising /
> construction, catching and extracting immutable values in handlers.

Here you create a new class of types, limited in some particular way. Doing
so, you have to precisely define this class, you have to name it, you have
to consider types other than exceptions of being of this class, you have to
give it a formal name for generics and so on and so far. And in the end you
have to answer some newbie, why Ada does it that complex!

>> Why (1) cannot work here? The only real problem with (1) I can see, is
>> that the exception type does not have ranges or other forms of subsets.
>> One need some syntactic suggar to define a set of exceptions which could
>> be then named in "when".
> 
> Feel free to perceive my 'code' as syntactic sugar.

It is not (1) it is (2), which has a lot of problems.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Dimitry,

>> You silently refused to say what abstraction inversion is according
>> to you :-)

> We can use your definition if you want. (:-))

My impression was that, according to you, mine was wrong. Certainly, I
would prefer to use the right one.

---

>> Then we're talking about two distinct things. I am talking about a
>> compile time solution only.
 
> Why should they be distinct? 

Checking physical units statically would be helpful for high integrity
software. I don't see any practical use for runtime unit checks.

---

> I didn't say that (2) is not solvable. I just invited you to think about it
> more deeply, before making some final statements. 

It is unclear to me what final statements you are referring to.

---

> Discriminants can be of access types.

Good point, my bad.

---

> Here you create a new class of types, limited in some particular way. Doing
> so, you have to precisely define this class, you have to name it, you have
> to consider types other than exceptions of being of this class, you have to
> give it a formal name for generics and so on and so far. And in the end you
> have to answer some newbie, why Ada does it that complex!

Fortunately a distinct class already exists, and it's called
exceptions. I'd only extend it to be able to convey some additional
info down the callstack, but the added complexity is, of course, a
valid point.


Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

>>> You silently refused to say what abstraction inversion is according
>>> to you :-)
> 
>> We can use your definition if you want. (:-))
> 
> My impression was that, according to you, mine was wrong. Certainly, I
> would prefer to use the right one.

I did not disagree with your definition. I did with your statement that
Ada's protected objects are wrong way. They might have problems, though.
But it appeared, as you treating them as completely wrong.

>>> Then we're talking about two distinct things. I am talking about a
>>> compile time solution only.
>  
>> Why should they be distinct?
> 
> Checking physical units statically would be helpful for high integrity
> software. I don't see any practical use for runtime unit checks.

Only because I see no smiley... How would you implement:

procedure Put (Stream : File, Value : Measurement);
procedure Get (Stream : File, Value : out Measurement);

For example, a requirement of one of our customer was to have a button in
his MMI to switch between European and American units in all visual
elements and printouts. Now go, figure out, how would you solve that using
templates. BTW, European /= SI, because of km/h, ps, Celsius degree etc.
Not to forget dozens of external devices all working with units of their
own, all need to be hot pluggable etc.

>> I didn't say that (2) is not solvable. I just invited you to think about
>> it more deeply, before making some final statements.
> 
> It is unclear to me what final statements you are referring to.

That Ada exception model should be replaced by some other.
 
-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

> I did not disagree with your definition. I did with your statement that
> Ada's protected objects are wrong way. They might have problems, though.
> But it appeared, as you treating them as completely wrong.

"Wrong" seems to be one of your favourite words. I merely said that
Ada concurrency features are not expressive enough not to require
abstraction inversion in many cases.

---

>> Checking physical units statically would be helpful for high
integrity
>> software. I don't see any practical use for runtime unit checks.
 
> Only because I see no smiley... How would you implement:
> 
> procedure Put (Stream : File, Value : Measurement);
> procedure Get (Stream : File, Value : out Measurement);
> 
> For example, a requirement of one of our customer was to have a button in
> his MMI to switch between European and American units in all visual
> elements and printouts. Now go, figure out, how would you solve that using
> templates.

Huhm, we are talking about _checks_, then we are suddenly talking
about _conversions_. But even for conversions, even though they are
most certainly useful in many cases at runtime, the idea to hardcode
the external representation of values with units into the compiler and
runtime, is unfortunate.

---
 
>>> I didn't say that (2) is not solvable. I just invited you to think
about
>>> it more deeply, before making some final statements.
>> 
>> It is unclear to me what final statements you are referring to.
> 
> That Ada exception model should be replaced by some other.

I hate it when somebody puts words I have not said in my mouth. I
suggest that you proofread your own posts for final statements
instead.


Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

>> I did not disagree with your definition. I did with your statement that
>> Ada's protected objects are wrong way. They might have problems, though.
>> But it appeared, as you treating them as completely wrong.
> 
> "Wrong" seems to be one of your favourite words. I merely said that
> Ada concurrency features are not expressive enough not to require
> abstraction inversion in many cases.

Sorry, but I still do not get your point. Either Ada features are 1) beyond
any help; 2) OK, but has to be impoved in some definite way; 3) Excellent.
It seems that you do not agree with (3). So either (1) or (2) remain. Which
one?

>>> Checking physical units statically would be helpful for high
> integrity
>>> software. I don't see any practical use for runtime unit checks.
>  
>> Only because I see no smiley... How would you implement:
>> 
>> procedure Put (Stream : File, Value : Measurement);
>> procedure Get (Stream : File, Value : out Measurement);
>> 
>> For example, a requirement of one of our customer was to have a button in
>> his MMI to switch between European and American units in all visual
>> elements and printouts. Now go, figure out, how would you solve that
>> using templates.
> 
> Huhm, we are talking about _checks_, then we are suddenly talking
> about _conversions_.

I gave you an example of a *real* application requiring units (and units
checks, because surely in any place where the system expects, say, a
velocity, the operator may give it in any compatible unit: knot, km/h, m/s,
mph, whatsoever, but not in kPa. So units are indeed checked.)

> But even for conversions, even though they are
> most certainly useful in many cases at runtime, the idea to hardcode
> the external representation of values with units into the compiler and
> runtime, is unfortunate.

I do not follow you here. My example shows that static *only* checks are
insufficient. Period. This does not imply that it is impossible to create a
unit system which would be statically checkable. I already mentioned in my
previous post that Ada designers managed to do a similar job with the type
String. Carefully observe how Ada deals with statically constrained String
subtypes. In my view it is quite possible to deal this way with dimensioned
values too.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Hello,

> Sorry, but I still do not get your point. Either Ada features are 1) beyond
> any help; 2) OK, but has to be impoved in some definite way; 3) Excellent.
> It seems that you do not agree with (3). So either (1) or (2) remain. Which
> one?

Depends on the application. For highly concurrent data structures that
would be 1, for tutorials 3. For many applications they are probably
okay. I am talking about concurrency features only now, but other
parts of the language also have their problems. Still, with all the
problems, Ada is  overall the best procedural language I've seen.

---
 
> I gave you an example of a *real* application requiring units (and units
> checks, because surely in any place where the system expects, say, a
> velocity, the operator may give it in any compatible unit: knot, km/h, m/s,
> mph, whatsoever, but not in kPa. So units are indeed checked.)

You could make it unable to enter a wrong unit in the interface. So
this would be ensuring that 'Unit_Error' cannot be raised, rather than
catching and handling it. But it is not always possible, for example
when reading from an untrusted file, so you are right.

> I already mentioned in my  previous post that Ada designers managed to do a 
> similar job with the type String. Carefully observe how Ada deals with 
> statically constrained String subtypes. In my view it is quite possible to 
> deal this way with dimensioned values too.

I've studied your code on units, I admit I should have done that
before engaging in discussion about units with you.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Wojtek Narczynski wrote:

>> Sorry, but I still do not get your point. Either Ada features are 1)
>> beyond any help; 2) OK, but has to be impoved in some definite way; 3)
>> Excellent. It seems that you do not agree with (3). So either (1) or (2)
>> remain. Which one?
> 
> Depends on the application. For highly concurrent data structures that
> would be 1, for tutorials 3.

Does it mean that 1.a) there is a better approach, or that 1.b) parallel
applications are hard to develop? I would definitely disagree with the
first and agree with the second.

> For many applications they are probably
> okay. I am talking about concurrency features only now, but other
> parts of the language also have their problems.

Any language has problems.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Dimitry,

> Does it mean that 1.a) there is a better approach, or that 1.b) parallel
> applications are hard to develop? I would definitely disagree with the
> first and agree with the second.

Clearly parallel applications extremely hard to develop.

Regarding better approach (than protected for highly concurrent data
structures). It depends on what "better" means in a given context. For
example, there are more time and space efficient, allowing higher
concurrency, approaches.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Dmitry A. Kazakov wrote:

> This has nothing to do with abstraction inversion. The problem here is that
> Ada does not have multiple protected actions. Same problem with tasks,
> there cannot be rendezvous with multiple tasks. It is much work to solve
> that. Especially to convince people that prefix notation is inherently bad.

Not quite right.  A decision was made early in the development of Ada 
that a CALLING task can only rendezvous with a single task.  A task can 
accept arbitrarily many calls simultaneously.  You might prefer that the 
rule worked the other way around, but we felt that we had to choose one 
or the other.  Many-to-many rendezvous looked just too messy to contemplate.

AFAIK, the only pattern that uses this feature is the one where you have 
multiple servers and a task that allocates requesting tasks to servers. 
  I have actually used this pattern.

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Dmitry A. Kazakov]

Robert I. Eachus wrote:

> Dmitry A. Kazakov wrote:
> 
>> This has nothing to do with abstraction inversion. The problem here is
>> that Ada does not have multiple protected actions. Same problem with
>> tasks, there cannot be rendezvous with multiple tasks. It is much work to
>> solve that. Especially to convince people that prefix notation is
>> inherently bad.
> 
> Not quite right.  A decision was made early in the development of Ada
> that a CALLING task can only rendezvous with a single task.  A task can
> accept arbitrarily many calls simultaneously.  You might prefer that the
> rule worked the other way around, but we felt that we had to choose one
> or the other.  Many-to-many rendezvous looked just too messy to
> contemplate.

Right, I do not know how difficult it would be to implement, but definitely,
it would make statical analysis more complicated. So it is not clear
whether this feature would give any real advantage.

> AFAIK, the only pattern that uses this feature is the one where you have
> multiple servers and a task that allocates requesting tasks to servers.
>   I have actually used this pattern.

Thank you for the example, because I never needed multiple rendezvous.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

> function in_kilograms (x: Quantity) return Units.yard;
> -- Blows at runtime

Oops :-)

"The morning is wiser than the evening."

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Wojtek Narczynski wrote:

> Or the simplest possible: two protected counters, try to get the sum
> atomically.

Since this is trivial, I can only assume that you have two protected 
counters with no support for external locking in mind.  Actually, you 
can even do that, by having one counter have a Sum operation that calls 
the other.

The fact that two arbitrary counters cannot be added atomically in all 
cases is a feature of the real world, not of Ada. Certainly any two 
counters that can be managed with a P,V protocol can be added 
atomically.  It is also possible if only one counter has P, V support.

However, this whole subject is probably silly.  If I give you a total 
outside of any locking which is guaranteed to have been correct at some 
point in the past, how do you know whether it was atomic or not?  The 
answer has to be that it was possible to increment both counters with an 
atomic operation. (For example, any odd sum could be invalid.)  But once 
we postulate atomic joint increments, atomic sums are obviously also 
possible.

Reminds me of a lot of improvement requests for Ada 9X.  "We want to do 
such and such."

"Well, here is a simple example of how to do it in current Ada."

"Oh, but our software development plan doesn't allow us to use 
Unchecked_Conversion."

Well, fix your bloody SDP, you nit!

Hmm. It sounds harsh said like that, but what they wanted to do was 
exactly the reason that their SDP forbid Unchecked_Conversion.  Whether 
the SDP or the guy writing the improvement request was "right" in the 
context of a particular project was irrelevant to the design of Ada 9X. 
  Ada, as designed, allowed SDPs to easily allow or forbid use of some 
features.  (Right now the best example of this is the SPARK checker that 
forbids exceptions and dynamic allocations.)  The intent was exactly to 
allow projects to "tailor" the subset they used.  (I just ran into 
another CS professor who didn't understand that the Ada 83 "no subsets" 
rule was for validated compilers, not for projects. Sigh.)

Back to the example that started all this.  Either it "makes sense" to 
atomically lock both counters, or it doesn't.  This is a design 
criteria, and will affect how the counters are implemented.  If a later 
change adds this requirement, you may have to change the implementation 
of the counters.  Said like that, it sounds so _obvious_.
-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

>> Or the simplest possible: two protected counters, try to get the
>> sum atomically.
 
> Since this is trivial, I can only assume that you have two protected 
> counters with no support for external locking in mind.

I had in mind implementing it without the need to resort to
abstraction inversion, which I understand as -for example-
implementing semaphores over protected objects, which are implemented
over semaphores.

> Actually, you can even do that, by having one counter have a Sum operation 
> that calls the other. However, this whole subject is probably silly.

Yes, this is silly because I oversimplifed the problem.

The original problem I run into was how to implement a highly
concurrent, space and time efficient list, tree, and finally lock
manager.

And before that, I wanted to grab a ready implementation of this
(list, tree) from some library, but I could not find such a thing...

> Reminds me of a lot of improvement requests for Ada 9X.  "We want to do 
> such and such."
> 
> "Well, here is a simple example of how to do it in current Ada."
> 
> "Oh, but our software development plan doesn't allow us to use 
> Unchecked_Conversion."

Yes, I should probably have dropped protected type in favor of raw
semaphores.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Wojtek Narczynski wrote:

> I had in mind implementing it without the need to resort to
> abstraction inversion, which I understand as -for example-
> implementing semaphores over protected objects, which are implemented
> over semaphores.

Protected objects _may_ be implemented using semaphores, or mutexes, or 
counters, or any viable atomic action.  But when you are programming in 
Ada, you have to take the tasking model, complex as it seems, as the 
fundamental primitive for concurrency.  Protected objects were added to 
Ada 9X to eliminate some of the baggage that most implementations of Ada 
tasking carried.  And to some extent they did just that.  But if I need 
fast semaphores, I use a semaphore abstraction, then I try various 
implementations of the abstraction to find one which has the performance 
I need.  If implementing a semaphore portably as a protected object 
works?  Done.

> Yes, I should probably have dropped protected type in favor of raw
> semaphores.

Protected objects are a very useful model for a lot of jobs that require 
management of concurrency.  But it is a characteristic of protected 
objects that they manage _their_own_ concurrency, and nothing else.  As 
long as that model fits what you are doing, great protected objects have 
great advantages over other techniques, such as semaphores.

But there are two important points.  First you _must_ as part of your 
analysis of the problem domain identify the objects that need to be 
managed.  For lists and trees, two of the examples you mentioned, what 
usually needs to be managed is the list, or the tree:

protected type List is
   procedure Append(E: in Element);
   procedure Prepend(E: in Element);
   ...
   function Is_Empty return Boolean;
   function Length return Natural;
private
   ...
end List;

Should you expect to find a ready made implementation that meets your 
needs?  Possibly.  But you almost certainly won't find it by looking for 
libraries of protected objects.  The usual in Ada is to provide a 
generic package abstraction where the protected object is hidden from 
the user's sight.  This allows it to "reuse" the interface of a List 
that doesn't need protection from concurrent access.  In fact, one of 
the changes in Ada 95 was intended to make it easier to 'hide' such a 
protected type in the body of a (generic) package.

To go back to the example that sparked the discussion, it is not that 
difficult to create a protected type which protects an array of 
counters.  It then seems natural to have both a set of atomic operations 
on a single counter and on a set of counters:

type Index is (<>);
generic package Counters is

    type Set is array (Index) of Boolean;

    type Count_Array is (Index range <>) of Integer;

    protected type Counters is
       procedure Reset(I: Index);
       procedure Reset(S: Set);
       procedure Reset; -- Zero all counters.
       function Count(I: Index) return Integer;
       function Count(S: Set) return Count_Array;
       function Count return Count_Array;
       --return a snapshot of all counts
    private
       ...
    end Counters;

Now you may think that this is an abstraction inversion, but I don't. 
That is really a comment on thinking Ada.  Even with Ada 83, it was 
_hard_ to correctly identify the 'right' objects to make the rest of the 
project easy, and Ada 95 has made those choices much harder.  But the 
way it has done that is by making the object calculus much more powerful.

I used to have a fully worked out example that demonstrated the issue. 
It was a simulation of a barber shop, with multiple chairs and barbers, 
customers who decided to return later if there were too many other 
customers waiting, and so on.  But none of that was the point of the 
example.  There was a simple elegant object-oriented solution.  The 
insight you needed to find it though, was that the key objects were the 
haircuts!

You could also probably come up with just as clean a model if you made 
the customers the key objects, but somehow _trying_ to do that leads you 
astray.  If a parent comes into the barber shop with a child, who is the 
customer?  Much easier to get it right, if you are thinking that a 
father comes into the barber shop to get _haircuts_ for both himself and 
his son, or only his son, or whatever.

There are lots of ways to identify the potential objects in a program. 
Grady Booch's method of describing the problem space and underlining all 
the nouns is probably as good as any.  But that is where the hard work 
begins.  As in the barber shop example, there is some minimal set of 
objects that need to be modelled, or perhaps a better way to say that is 
that there is a minimal set of expensive objects that does the job. 
What makes objects expensive? It can be storage space, allocation and 
deallocation, active state, or some combination of the above.  But you 
often don't know what cost function for the project will be at that 
stage of the analysis.  You have to try strawmen, see which project 
constraints bind hardest, then start looking for opportunties to trade 
one resource for another.  Sometimes, as in the barber shop example, 
there will be one elegant model which minimizes the cost in all 
dimensions.  Other times, the engineering tradeoffs need to be decided 
before you can actually start coding.

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Robert,

First of all, thanks for writing me an essay. One day you might think
of gathering all your c.l.a posts into a book. I would definitely buy
a copy.

But let me push it a bit more.

> But there are two important points. First you _must_ as part of your 
> analysis of the problem domain identify the objects that need to be 
> managed. 

Analysis for generic data structures has been done decades ago. I'd
prefer to use something readily available and not redo the analysis at
this level.

But let's grant that, as a result of throughout analysis, you conclude
that you need a list that is sorted, space efficient, time efficient,
updateable from many tasks at the same time. Any hint on how to
implement this?

> protected type List is
>    procedure Append(E: in Element);
>    procedure Prepend(E: in Element);
>    ...
>    function Is_Empty return Boolean;
>    function Length return Natural;
> private
>    ...
> end List;

If you do this, only one task / thread will be able to update the data
structure.

> Should you expect to find a ready made implementation that meets your 
> needs?  Possibly.  But you almost certainly won't find it by looking for 
> libraries of protected objects. 

I found no examples of data structures with lock granularity lower
than the whole data structure.

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Wojtek Narczynski wrote:

> I found no examples of data structures with lock granularity lower
> than the whole data structure.

That is what I would expect you would find.  Why would you expect 
anything different?  For a list you might be able to prepend and append 
at the same time, but the more complex organization just doesn't seem 
worth it.

For trees you can have one lock per object, and insertions, for example, 
would only hold the locks on those nodes needed for the insertion.  From 
experience it is _possible_ but the performance of one lock per data 
structure instance performs much better.  (Look at it this way.  If you 
have one lock per node, then every query needs to start by locking the 
root node, so your transactions are going to be serialized anyway.  As 
long as the whole tree _structure_ is in memory, doing the tree walk 
inside that one lock is more efficient than having to acquire and 
release a dozen locks, even though the first lock will serialize everything.

If you have a situation where you need to lock a node for the duration 
of a transaction, the best choice--again from experience--is to have one 
lock for the tree structure, and one lock for the _contents_ of each 
node.  That way you can have many transactions walking the tree at the 
same time (many readers) but the time consuming part of the transaction, 
which may require waiting for human interaction has a write lock on the 
content, not on the tree.  Deleting or inserting a new node does require 
a write lock on the tree as a whole, but for AVL trees or B-trees the 
difference between that and locking 'just' the part of the tree which is 
potentially changing just isn't worth the extra overhead.

To sum up, in theory there is no difference between theory and practice, 
but in practice there is.

Oh one last observation, it may seem that to do an update of a tree node 
only requires a lock on the node contents, but this is not true in all 
cases.  If the update of the contents changes the key, you have to 
delete the entry from the tree and reinsert it.  This means you want to 
choose a key which is not often changed.  (Just one reason why so many 
things are keyed by SSAN.)


-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Randy Brukardt]

"Wojtek Narczynski" <wojtek@power.com.pl> wrote in message
news:5ad0dd8a.0404160338.5a1c9116@posting.google.com...
...
> I found no examples of data structures with lock granularity lower
> than the whole data structure.

That's because it would be hard to avoid deadlock in such data structures.
(And, as Robert points out, the cost of grabbing a lot of locks would be
very high.)

The usual way of avoiding deadlock is the use the onion-skin model of
locking. But that would serialize the data structure anyway, so there
wouldn't be much point in separate locks.

To see the problem, consider a tree struction. You'd have to lock many nodes
if an insertion caused a rebalancing. If a second task tried to do a nearby
insertion at the same time, it also could lock a number nodes. It would be
quite likely for the second task to lock the nodes that it is going to
insert into, then the first task try to lock the same nodes to do a
rebalancing. So it would have to wait. Then the second task would discover
that it, too needs to do a rebalancing - but it can't, because the first
task already has locked some of the nodes that it needs to change for the
rebalancing. Classic deadlock.

To avoid this situation, you have to lock the whole data structure. The only
place where you could get parallel operation is in modifying the elements
once inserted. (And in a library like Ada.Containers, that's done updating a
copy of the element, then calling the library to replace the previous
element.)

                  Randy.

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Randy,

> That's because it would be hard to avoid deadlock in such data structures.

Yes, it is hard to avoid deadlocks.

> The usual way of avoiding deadlock is the use the onion-skin model of
> locking. 

With acyclic strucutres you do "crabbing" to avoid deadlocks.

> To see the problem, consider a tree struction. You'd have to lock many nodes
> if an insertion caused a rebalancing. If a second task tried to do a nearby
> insertion at the same time, it also could lock a number nodes. It would be
> quite likely for the second task to lock the nodes that it is going to
> insert into, then the first task try to lock the same nodes to do a
> rebalancing. So it would have to wait. Then the second task would discover
> that it, too needs to do a rebalancing - but it can't, because the first
> task already has locked some of the nodes that it needs to change for the
> rebalancing. Classic deadlock. To avoid this situation, you have to lock the
> whole data structure. 

This is not easy but solveable. For example ADABAS (and forks)
relational database is organized as one large B* tree. It can be
edited concurrently, it rebalances, and does not deadlock.

One more example: Java heap, millions of objects, 64 CPUs, thousands
of threads. Would you like to have one lock for the whole data
strucutre?

Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Wojtek Narczynski wrote:

> This is not easy but solveable. For example ADABAS (and forks)
> relational database is organized as one large B* tree. It can be
> edited concurrently, it rebalances, and does not deadlock.
> 
> One more example: Java heap, millions of objects, 64 CPUs, thousands
> of threads. Would you like to have one lock for the whole data
> strucutre?

You are missing the point.  The answer is no, one lock per storage pool. 
  How many storage pools do you have?  At least one per CPU, more 
usually two or three due to different storage management protocols.  But 
the major insight is that you either update a copy of an object and then 
  swap it in atomically as Randy said, or (my preference) the lock for 
the data structure controls the data structure and a separate per object 
lock controls the object updates.  (Except changing index keys, which 
has to be done Randy's way.)

The simplest data structure locking protocol is usually by far the most 
efficient.  Spending a dozen times as many CPU cycles on lock management 
to double or triple the effective concurrency is a joke, and you will 
find that holding complex schemes to only a dozen times as long is 
difficult.  Factor in memory caches, and anything else is crazy.

What is important, in real cases, is memory management.  Having any part 
of a data structure paged to disk can kill performance.  (The data 
structure now, not the actual data.)  This is why I tend to implement 
the tree or whatever with a pointer (excuse me access value) designating 
  the data.  That way the next data structure entry you need will be in 
main memory, and is much more likely to be in cache.

(If you also figure from this that I am one of those people who designs 
large objects and not that many of them, you are right.  Complex data 
dictionaries are all right for the theoretical part of design, but when 
it comes to practice, you want to merge data nodes to the maximum extent 
possible.)

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Robert,

> What is important, in real cases, is memory management.  Having any part 
> of a data structure paged to disk can kill performance. (The data 
> structure now, not the actual data.)

Another problem of this kind is that the lock owner thread can get
preempted by the operating system. This is more frequent, but less
devastating than a page fault.

> (Complex data dictionaries are all right for the theoretical part of design,
> but when it comes to practice, you want to merge data nodes to the maximum
> extent possible.)

Okay, practitioners speaking, so I will just listen. Should I ask for
a refunt for "Transaction Processing: Concept and Techniques" by
J.Gray & A. Reuter? :-)


Regards,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Robert I. Eachus]

Wojtek Narczynski wrote:

> Another problem of this kind is that the lock owner thread can get
> preempted by the operating system. This is more frequent, but less
> devastating than a page fault.

There are "tricks" to minimize this.  Even if I am programming at system 
independent level, I try to insure that all pages that may be needed 
inside a lock have been referenced outside the lock first.  In a formal 
sense, this won't improve things, but in practice it can make the 
difference between good performance and bad.

The best of all possible worlds is a compiler that wraps protected 
actions in an interrupt-deferred region.  Like all real-time features, 
this is a two-edged sword, but one you have to use in some cases.

> Okay, practitioners speaking, so I will just listen. Should I ask for
> a refunt for "Transaction Processing: Concept and Techniques" by
> J.Gray & A. Reuter? :-)

Theory is important, so is practice.  Without the theory you don't know 
what is and isn't correct in a formal sense.  But in real-time 
programming, too late is just as bad as any other error, and it is an 
emergent property of the whole system.

It is very frustrating to design a race free and deadlock free system, 
then find that to meet the performance requirements you have to violate 
some of the assumptions necessary to make the system deadlock free. 
Yes, you can often go "back to the drawing board" and come up with a 
more complex solution that works and meets the requirements.  But far 
more often, you end up with a solution which is only deadlock free 
because it occasionally aborts lower priority transactions.

-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Hello,

> I found no examples of data structures with lock granularity lower
> than the whole data structure.

...lock granularity higher than...

Sorry,
Wojtek

Re: Reprise: 'in out' parameters for functions

[Pascal Obry]

wojtek@power.com.pl (Wojtek Narczynski) writes:

> to say CM3 Modula, or Java). But the problem real problem IMO is that
> the development of the language has stagnated.

This seems just strange to me! Latest Ada standard has moved forward a lot and
all this is many aspects of the language. And Ada0Y is another step (admitedly
smaller one) in this direction!

Or maybe you are just trolling :)

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Reprise: 'in out' parameters for functions

[Wojtek Narczynski]

Hello,

> Or maybe you are just trolling :)

Indeed I might have been, but only a litte.

Regards,
Wojtek