Objects and the Stack?

Objects and the Stack?

[Freejack]

It's my understanding that one can eliminate the need for pointers (access
types) through prudent use of tagged types and classes. However it is also
my understanding that Gnat at least, when creating instances of Foo'class,
creates them on the stack.

So, for kicks, I'm gonna write a package that creates a stack, with the
stack being a tagged object which gets extended with each new element
object that's pushed onto it.

I don't see any problems with implementing this as far as the language
itself is concerned. However I'm guessing the actual stack object will
reach a point where it reeks hell with the system stack.

Anyone here have experience with similar constructs and machinations?

Just curious.

Freejack
 

Re: Objects and the Stack?

[Nick Roberts]

Freejack wrote:

> It's my understanding that one can eliminate the need for pointers (access
> types) through prudent use of tagged types and classes.

I don't think so. What made you think that?

-- 
Nick Roberts

Re: Objects and the Stack?

[Marc A. Criley]

"Nick Roberts" <nick.roberts@acm.org> wrote:
> Freejack wrote:
>
> > It's my understanding that one can eliminate the need for pointers
(access
> > types) through prudent use of tagged types and classes.
>
> I don't think so. What made you think that?

A cursory reading of comp.lang.ada would show that it is not uncommon to
read posts implying that Ada eliminates the need for a significant amount of
pointer usage, compared to other programming languages.  And comparatively
speaking, this may be true, but that point can be misunderstood to suggest
that there's only a few application areas where pointer usage remains
essential.

And apparently my development activities must center on those few areas,
since I'm constantly using access types due to the unknowable-in-advance
quantities and structural relationships of the data that I'm dealing with.

My 2c...

Marc A. Criley
McKae Technologies
www.mckae.com

Re: Objects and the Stack?

[Marius Amado Alves]

> ... apparently my development activities must center on those few areas,
> since I'm constantly using access types due to the unknowable-in-advance
> quantities and structural relationships of the data that I'm dealing with.

You should attend a "No Pointers, Great Programs" tutorial :-)

The whole problem with pointers is that languages (incorrectly) mix 
_allocation_ and _reference_ in them. Every complex design has 
referential needs (names). A pointerless approach tries to insolate that 
from the allocation troubles.

Re: Objects and the Stack?

[Dmitry A. Kazakov]

On Mon, 20 Dec 2004 16:22:44 +0000, Marius Amado Alves wrote:

>> ... apparently my development activities must center on those few areas,
>> since I'm constantly using access types due to the unknowable-in-advance
>> quantities and structural relationships of the data that I'm dealing with.
> 
> You should attend a "No Pointers, Great Programs" tutorial :-)
> 
> The whole problem with pointers is that languages (incorrectly) mix 
> _allocation_ and _reference_ in them. Every complex design has 
> referential needs (names). A pointerless approach tries to insolate that 
> from the allocation troubles.

This is exactly the idea of pointer, I am afraid. You allocate object
somewhere and reference it elsewhere. Isolation here means that you can
copy that reference independently from the object with all consequences of
that.

In my view there is only one approach to the problem: static scopes. It is
objects allocated on the stack and also it is accessibility rules if the
former does not help. These both are directly supported in Ada. When that
does not help there are smart pointers. And it is again about static
scopes, though ones of pointers. The decision to destroy an object is made
when a the last pointer goes out of scope.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Objects and the Stack?

[Jeffrey Carter]

Freejack wrote:

> It's my understanding that one can eliminate the need for pointers (access
> types) through prudent use of tagged types and classes. However it is also
> my understanding that Gnat at least, when creating instances of Foo'class,
> creates them on the stack.

The fact that pointers are generally not needed in Ada except when 
creating things such as dynamic data structures has nothing to do with 
tagged types. If you create objects of a classwide type, they are put on 
the stack if you declare them there, and in a storage pool if you 
allocate them there.

> So, for kicks, I'm gonna write a package that creates a stack, with the
> stack being a tagged object which gets extended with each new element
> object that's pushed onto it.

I'm not sure what you mean by "extended" here, whether you're referring 
to type extension or a value that becomes larger in 'Size, but this 
doesn't work the way I think you think it will.

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

Re: Objects and the Stack?

[Freejack]

On Fri, 17 Dec 2004 00:28:23 +0000, Jeffrey Carter wrote:

 
> The fact that pointers are generally not needed in Ada except when 
> creating things such as dynamic data structures has nothing to do with 
> tagged types. If you create objects of a classwide type, they are put on 
> the stack if you declare them there, and in a storage pool if you 
> allocate them there.
> 
Something like ...
	declare
		Stack : Obstack'Class := Item'(SomeIndex);
	begin
		IsPushed := Push(Item);
		NewItem := Pop;
	end;
Is what I have in mind. 

However what I'd like to be able to do( and what I'm working on. ) is
something like this...

	package body obstacks is
		type obstack is abstract tagged null record;
		
		Stack : Obstack'Class; -- Problematic, needs some kind
					  of discriminant.

		function pkgbodyPush(X : Item) return obstack'class is
			type NewStack is new Obstack with
				record
				Prev : Obstack'Class := Stack;
				NewItem : Item := X;
				end record;
			PushedStack : NewStack; --Again, problematic
		begin
			return PushedStack;
		
		end pkgbodyPush;

	And then, every time the internal pkgbodyPush is called we get..

		Stack := pkgbodyPush(X);

See where I'm going with this? The above code is riddled with problems
that I gotta figure out. But that's the gist of it. The "Stack" variable
should remain on the "stack" as long as the package body is in scope.
That's my assumption at least. I'll know soon enough if I'm wrong. Heh.
	
> I'm not sure what you mean by "extended" here, whether you're referring
> to type extension or a value that becomes larger in 'Size, but this
> doesn't work the way I think you think it will.

Probably not. But then again, that's what experimentation is for. ;->
That's one of the ways I learn new programming methods. By taking a
concept to the most absurd extreme I can imagine.

Re: Objects and the Stack?

[Martin Dowie]

Have you had a look at the 'simple polymorphic list' by Ehud Lamm @
http://www.adapower.com/index.php?Command=Class&ClassID=DataStructures&Title=Data+Structures

It might give you some pointers (no pun intended)...

-- Martin

Re: Objects and the Stack?

[Nick Roberts]

Freejack wrote:
> On Fri, 17 Dec 2004 00:28:23 +0000, Jeffrey Carter wrote:
> 
>  
> 
>>The fact that pointers are generally not needed in Ada except when 
>>creating things such as dynamic data structures has nothing to do with 
>>tagged types. If you create objects of a classwide type, they are put on 
>>the stack if you declare them there, and in a storage pool if you 
>>allocate them there.
>>
> 
> Something like ...
> 	declare
> 		Stack : Obstack'Class := Item'(SomeIndex);
> 	begin
> 		IsPushed := Push(Item);
> 		NewItem := Pop;
> 	end;
> Is what I have in mind. 
> 
> However what I'd like to be able to do( and what I'm working on. ) is
> something like this...
> 
> 	package body obstacks is
> 		type obstack is abstract tagged null record;
> 		
> 		Stack : Obstack'Class; -- Problematic, needs some kind
> 					  of discriminant.
> 
> 		function pkgbodyPush(X : Item) return obstack'class is
> 			type NewStack is new Obstack with
> 				record
> 				Prev : Obstack'Class := Stack;
> 				NewItem : Item := X;
> 				end record;
> 			PushedStack : NewStack; --Again, problematic
> 		begin
> 			return PushedStack;
> 		
> 		end pkgbodyPush;
> 
> 	And then, every time the internal pkgbodyPush is called we get..
> 
> 		Stack := pkgbodyPush(X);
> 
> See where I'm going with this? The above code is riddled with problems
> that I gotta figure out. But that's the gist of it. The "Stack" variable
> should remain on the "stack" as long as the package body is in scope.
> That's my assumption at least. I'll know soon enough if I'm wrong. Heh.
> 	
> 
>>I'm not sure what you mean by "extended" here, whether you're referring
>>to type extension or a value that becomes larger in 'Size, but this
>>doesn't work the way I think you think it will.
> 
> 
> Probably not. But then again, that's what experimentation is for. ;->
> That's one of the ways I learn new programming methods. By taking a
> concept to the most absurd extreme I can imagine.

I suppose so, but I think I should tell you now that what you trying 
(above) cannot work. The assumption in Ada is that the space reserved 
within a stack frame for an object cannot be resized (even though the space 
used /within/ the space reserved for an object can). So the compiler must 
be able to allocate the maximum size of an object on the stack. Since what 
you are attempting could cause Stack to grow to any size without limit, the 
compiler cannot know what maximum to allocate. It won't work, and so you 
must use the heap (or more correctly, a 'storage pool').

Ada has no equivalent of alloca() in C. It might be interesting to 
experiment with a compiler extension to provide this facility. Certain 
algorithms might benefit from it.

    declare
       Name: String := "";
       pragma Extensible_Object(Name);
    begin
       ...
       Name := Name & ':'; -- changes its size
       ...

It's an idea.

-- 
Nick Roberts

Re: Objects and the Stack?

[Freejack]

On Fri, 17 Dec 2004 11:46:11 +0000, Nick Roberts wrote:

> I suppose so, but I think I should tell you now that what you trying 
> (above) cannot work. The assumption in Ada is that the space reserved 
> within a stack frame for an object cannot be resized (even though the space 
> used /within/ the space reserved for an object can). So the compiler must 
> be able to allocate the maximum size of an object on the stack. Since what 
> you are attempting could cause Stack to grow to any size without limit, the 
> compiler cannot know what maximum to allocate. It won't work, and so you 
> must use the heap (or more correctly, a 'storage pool').
> 
> Ada has no equivalent of alloca() in C. It might be interesting to 
> experiment with a compiler extension to provide this facility. Certain 
> algorithms might benefit from it.
> 
>     declare
>        Name: String := "";
>        pragma Extensible_Object(Name);
>     begin
>        ...
>        Name := Name & ':'; -- changes its size
>        ...
> 
> It's an idea.

I think the florist bindings have an Interface to the brk() and sbrk()
system calls, which is how it's usually done in C/Asm.
Perhaps by declaring the Objects to be Controlled, and then putting in
calls to brk() one might achieve the same effect.

Freejack

Re: Objects and the Stack?

[Nick Roberts]

Freejack wrote:

> I think the florist bindings have an Interface to the brk() and sbrk()
> system calls, which is how it's usually done in C/Asm.
> Perhaps by declaring the Objects to be Controlled, and then putting in
> calls to brk() one might achieve the same effect.

Possibly, but you'd have to have intimate knowledge of the compiler to be 
sure that you weren't going to work at cross purposes with it. Obviously, 
it wouldn't be portable, especially not to any target which didn't support 
sbrk(). I think, in essence, compiler support would be required.

-- 
Nick Roberts

Re: Objects and the Stack?

[Dave Thompson]

On Fri, 17 Dec 2004 19:52:24 GMT, Freejack <freejack@nowhere.net>
wrote:

> On Fri, 17 Dec 2004 11:46:11 +0000, Nick Roberts wrote:
<snip>
> > Ada has no equivalent of alloca() in C. It might be interesting to 
> > experiment with a compiler extension to provide this facility. Certain 
> > algorithms might benefit from it.
> > 
> >     declare
> >        Name: String := "";
> >        pragma Extensible_Object(Name);
> >     begin
> >        ...
> >        Name := Name & ':'; -- changes its size
> >        ...
> > 
> > It's an idea.
> 
> I think the florist bindings have an Interface to the brk() and sbrk()
> system calls, which is how it's usually done in C/Asm.

I don't know any C implementation that uses s/brk for an individual
object; the overhead of hitting the kernel every time would be too
high, and anyway it's limited to only (one object at) the end of the
data area. What's usual is to get hunks of (heap) space from s/brk,
mmap, or similar, and parcel it out by malloc, calloc, and realloc.
s/brk only on systems that have it of course, that is Unix-like ones.
And not at all for stack, which as Nick noted can usually be accessed
by alloca(), although that is not standard (neither C nor POSIX).

> Perhaps by declaring the Objects to be Controlled, and then putting in
> calls to brk() one might achieve the same effect.
> 
Controlled doesn't affect allocation at all, only destruction and
copying. Using 'new' would almost certainly put you in the heap, but
the probability of landing exactly at the end of the data area is low
at best, and probably zero on some implementations.

- David.Thompson1 at worldnet.att.net

Re: Objects and the Stack?

[Warren W. Gay VE3WWG]

Nick Roberts wrote:
> Freejack wrote:
>> On Fri, 17 Dec 2004 00:28:23 +0000, Jeffrey Carter wrote:
>>> The fact that pointers are generally not needed in Ada except when 
>>> creating things such as dynamic data structures has nothing to do 
>>> with tagged types. If you create objects of a classwide type, they 
>>> are put on the stack if you declare them there, and in a storage pool 
>>> if you allocate them there.
...
> I suppose so, but I think I should tell you now that what you trying 
> (above) cannot work. The assumption in Ada is that the space reserved 
> within a stack frame for an object cannot be resized (even though the 
> space used /within/ the space reserved for an object can). So the 
> compiler must be able to allocate the maximum size of an object on the 
> stack. Since what you are attempting could cause Stack to grow to any 
> size without limit, the compiler cannot know what maximum to allocate. 
> It won't work, and so you must use the heap (or more correctly, a 
> 'storage pool').
> 
> Ada has no equivalent of alloca() in C. It might be interesting to 
> experiment with a compiler extension to provide this facility. Certain 
> algorithms might benefit from it.

The difference between what alloca() gets you and what you
get in the declare block is a minor difference:

    -- Pseudo Ada here (Ada-ised C code for alloca())
    declare
      My_String : String_Access := Alloca(String(1..8));
    begin
      ...
      Put_Line(My_String.all);

    -- Real Ada here
    declare
       My_String : String(1..8);
    begin
       ...
       Put_Line(My_String);

Apart from getting a pointer from alloca(), I don't see any
advantage. Both forms allocate from the stack frame.

>    declare
>       Name: String := "";
>       pragma Extensible_Object(Name);
>    begin
>       ...
>       Name := Name & ':'; -- changes its size
>       ...
> 
> It's an idea.

This is taking the alloca() idea further than I think it
goes. I could be wrong here, but can you realloc() an
alloca() region?  If so, that is something that Ada does
in fact lack (including a realloc() in general, which I
pine for when growing arrays).

Warren.

Re: Objects and the Stack?

[Freejack]

On Sat, 18 Dec 2004 14:41:33 -0500, Warren W. Gay VE3WWG wrote:

> The difference between what alloca() gets you and what you
> get in the declare block is a minor difference:
> 
>     -- Pseudo Ada here (Ada-ised C code for alloca())
>     declare
>       My_String : String_Access := Alloca(String(1..8));
>     begin
>       ...
>       Put_Line(My_String.all);
> 
>     -- Real Ada here
>     declare
>        My_String : String(1..8);
>     begin
>        ...
>        Put_Line(My_String);
> 
> Apart from getting a pointer from alloca(), I don't see any
> advantage. Both forms allocate from the stack frame.
> 
>>    declare
>>       Name: String := "";
>>       pragma Extensible_Object(Name);
>>    begin
>>       ...
>>       Name := Name & ':'; -- changes its size
>>       ...
>> 
>> It's an idea.
> 
> This is taking the alloca() idea further than I think it
> goes. I could be wrong here, but can you realloc() an
> alloca() region?  If so, that is something that Ada does
> in fact lack (including a realloc() in general, which I
> pine for when growing arrays).
> 
> Warren.

Hmmm... Perhaps we could do that, and even more, by using Tasks and/or
Protected Objects. After all, on a platform with stack frames, doesn't
instantiation of a new task initialize a new stack frame? A Task
Storage_Pool would also be a Pool of stack frames? 
I'll have to go look it up, but if there is a way to declare Tasks or
Protected Objects as Controlled or Limited_Controlled within a
Storage_Pool(or perhaps in the general storage_pool), then it might be
possible.

Another possibility would be duplicating exactly the current task in
another task with a larger stack frame, switching control to the new task,
and killing off the old one, or keeping it around if the current new task
shrinks to the point where it's larger stack frame is no longer needed.

I'm gonna have to read up on that. And look at some compiler source.

Freejack

Re: Objects and the Stack?

[Dmitry A. Kazakov]

On Sat, 18 Dec 2004 20:50:47 GMT, Freejack wrote:

> On Sat, 18 Dec 2004 14:41:33 -0500, Warren W. Gay VE3WWG wrote:
> 
>> The difference between what alloca() gets you and what you
>> get in the declare block is a minor difference:
>> 
>>     -- Pseudo Ada here (Ada-ised C code for alloca())
>>     declare
>>       My_String : String_Access := Alloca(String(1..8));
>>     begin
>>       ...
>>       Put_Line(My_String.all);
>> 
>>     -- Real Ada here
>>     declare
>>        My_String : String(1..8);
>>     begin
>>        ...
>>        Put_Line(My_String);
>> 
>> Apart from getting a pointer from alloca(), I don't see any
>> advantage. Both forms allocate from the stack frame.
>> 
>>>    declare
>>>       Name: String := "";
>>>       pragma Extensible_Object(Name);
>>>    begin
>>>       ...
>>>       Name := Name & ':'; -- changes its size
>>>       ...
>>> 
>>> It's an idea.
>> 
>> This is taking the alloca() idea further than I think it
>> goes. I could be wrong here, but can you realloc() an
>> alloca() region?  If so, that is something that Ada does
>> in fact lack (including a realloc() in general, which I
>> pine for when growing arrays).
>> 
>> Warren.
> 
> Hmmm... Perhaps we could do that, and even more, by using Tasks and/or
> Protected Objects. After all, on a platform with stack frames, doesn't
> instantiation of a new task initialize a new stack frame? A Task
> Storage_Pool would also be a Pool of stack frames? 
> I'll have to go look it up, but if there is a way to declare Tasks or
> Protected Objects as Controlled or Limited_Controlled within a
> Storage_Pool(or perhaps in the general storage_pool), then it might be
> possible.

They are limited but not controlled. When you allocate a task or protected
object using "new" you can put it in a storage pool you want. Though this
would not affect the task's stack.

> Another possibility would be duplicating exactly the current task in
> another task with a larger stack frame, switching control to the new task,
> and killing off the old one, or keeping it around if the current new task
> shrinks to the point where it's larger stack frame is no longer needed.

Ooch. The difference between stack and heap is exactly that stack objects
need not to be reallocated. So it seems that what you want is just a heap.
The only way a stack could be used for resizable objects is when the object
to resize is on the stack top. Let you have implemented that. How would you
deal with two objects:

declare
   O1 : Resizable;
   O2 : Resizable;
begin
   Enlarge (O1);
   Enlarge (O2);
   Enlarge (O1);
end;

Basically to cope with that you will need a pool of stacks per task. Each
object declaration in one block goes to a separate stack. Nice? Nope,
because of:

declare
   O1 : Resizable;
   declare
      O2 : Resizable;
   begin
      Enlarge (O1);
      Enlarge (O2);
      Enlarge (O1);
   end;
end;

In the end an implementation based on smart pointers to heap allocated
objects will beat your stacks. The only problem with smart pointers in Ada
is that controlled objects required for them are too heavy-weighted. So if
you want to patch Ada, better add proper constructors / destructors /
assignment (for user-defined access types) there!

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Objects and the Stack?

[Dave Thompson]

On Sat, 18 Dec 2004 14:41:33 -0500, "Warren W. Gay VE3WWG"
<ve3wwg@NoSpam.cogeco.ca> wrote:

> Nick Roberts wrote:
<snip>
> > Ada has no equivalent of alloca() in C. It might be interesting to 
> > experiment with a compiler extension to provide this facility. Certain 
> > algorithms might benefit from it.
> 
> The difference between what alloca() gets you and what you
> get in the declare block is a minor difference:
>
<snip pseudoexample>

Agree.

> >    declare
> >       Name: String := "";
> >       pragma Extensible_Object(Name);
> >    begin
> >       ...
> >       Name := Name & ':'; -- changes its size
> >       ...
> > 
> > It's an idea.
> 
> This is taking the alloca() idea further than I think it
> goes. I could be wrong here, but can you realloc() an
> alloca() region?  If so, that is something that Ada does

No. But, if you alloca() multiple times, with nothing intervening, you
can probably count on them being contiguous, although probably (on
nearly all machines) in reverse order and maybe not exactly the size
requested, and AFAICS (even) that's not formally guaranteed.

> in fact lack (including a realloc() in general, which I
> pine for when growing arrays).
> 

- David.Thompson1 at worldnet.att.net

Re: Objects and the Stack?

[Jeffrey Carter]

Freejack wrote:

> 		Stack : Obstack'Class; -- Problematic, needs some kind
> 					  of discriminant.

This must be initialized, and from then on cannot change its tag. I 
suspected you might be thinking along these lines, but it won't work. 
See ARM 6.2: "The tag of an object of a class-wide tagged type is that 
of its initialization expression."

-- 
Jeff Carter
"I soiled my armor, I was so scared."
Monty Python & the Holy Grail
71

Re: Objects and the Stack?

[Jeffrey Carter]

Jeffrey Carter wrote:

> See ARM 6.2: "The tag of an object of a class-wide tagged type is that 
> of its initialization expression."

I'm not sure how I did that, but the correct section is 3.9. Sorry.

-- 
Jeff Carter
"I soiled my armor, I was so scared."
Monty Python & the Holy Grail
71