Re: How do functions return unbounded arrays?

[Robert A Duff <bobduff@world.std.com>]

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> writes:

> One of the things that still puzzles me about Ada is: how do
> compilers implement functions such as "&" that return variable
> length strings or arrays.

Many compilers special-case predefined "&".

There are several ways to implement a user-defined function whose result
size is not known at the call site.

One is to use the heap -- do an implicit "new" at the point of the
return_statement, and do a Free in the caller when the value is no
longer needed.  Or skip the free, and do garbage collection.

Another is to leave the function result on the stack.  Do a funny sort
of return, which does not pop the stack, and return a pointer to the
result.  Then, at the call site, move the value down the stack to where
it belongs, and chop back the stack.

Another is to use a "secondary stack".  The normal stack ("primary
stack") stores the usual stuff, such as known-size locals, parameters
that don't fit in registers, and return addresses.  But store the
results of these fancy functions on the secondary stack.  Upon return
from such a function, pop the primary stack as usual, but leave the
result on the secondary stack, and don't pop.  At the call site, move
the result to where it belongs, and simultaneously chop back the
secondary stack.  In addition to caller-unknown-size function results,
the secondary stack might also contain all run-time-known-sized objects,
and/or large objects.

In the second and third techniques, the compiler might try to optimize
by avoiding unnecessary copies in various cases.

> To get such a functionality under C, I would have to malloc() the
> memory for a String in the C function and then I am left with
> the question of when to free this memory. Does an Ada function
> such as "&" (concatenation of arrays) allocate secretly memory
> on the heap to get a space to store the result?

It might.  I don't much like the implicit heap implementation (unless
you also have garbage collection).  But at least the compiler takes care
of figuring out when to free the storage (unlike the by-hand malloc you
would do in C).

> If yes, when exactly is this memory deallocated? Are there Ada
> programs that cause a heap overflow just by calling "&" in a long loop
> and where this danger of a heap overflow is not explicit in the
> program text as no allocator is visible? In other words, are there
> any safety (heap overflow) risks associated with functions like "&"?

I would consider such a storage leak to be a bug.

> Is there a good paper that describes those things that silently
> go on between the lines of an Ada program and that still keep me
> from getting the warm fuzzy C programmer feeling that I really
> know what exactly is going on when my code executes?

Ada is a bit higher level than C, so you get less of that particular
"warm fuzzy" -- there are several features of Ada that can be
implemented in various ways, and you just have to know what your
particular compiler does, or what "typical" compilers do.  I guess
that's just the price of using a high level language.  I don't know of
any useful papers about this; sorry.  When you program in C, you can
usually guess roughly what the compiler is going to do.  Less so in Ada.
More so in assembly language.

In C, you don't have to worry about whether the compiler does
code-sharing for generic bodies.  In C, you don't wonder whether the
compiler uses displays or static links for nested functions.

> Also, is there any documentation around that describes the interface
> that GNAT expects from the run-time library, i.e. whatever one
> would need in order to write a new GNAT runtime library with all
> the tasking, memory management, etc. (Again, just to get the feeling
> that I know what is going on behind the scenes.)

You can read the sources.  They're pretty well commented, IMHO.

- Bob

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