[M3devel] reference to globals in globals?

[Hendrik Boom]

On Thu, Aug 16, 2012 at 12:27:17PM -0500, Rodney M. Bates wrote:
> 
> 
> On 08/15/2012 07:55 PM, Hendrik Boom wrote:
> >On Wed, Aug 15, 2012 at 09:51:41AM -0500, Rodney M. Bates wrote:
> >>
> >>
> >>On 08/14/2012 10:04 PM, Jay K wrote:
> >>>
> >>>Heck, even if these weren't global, is it that unreasonble,
> >>>from the programmer's point of view, for the language/compiler
> >>>to do some pointer escape analysis and let me take the address
> >>>of a local, as long as I don't store it somewhere that outlives
> >>>the local?
> >>>
> >>
> >>This is ultimately an undecidable problem and even conservative
> >>approximations of reasonable sophistication are far too involved
> >>for a language to require of every compiler.
> >
> >Not to mention the obscurityof the language definition.
> >
> 
> Yes, yes, yes!!!
> 
> >But isn't there something like that with the addresses of top-level
> >proocedures?  the ones whose environments are completely static?
> >Or am I thinking of another type-safe language?  Or am I thinking of
> >assigning the procedures themselves?
> 
> Yes.  If you can assign a procedure (or pointer to function, which is
> equivalent, for this discussion) to a variable, then there are ways to
> call the procedure when its environment does not exist, i.e, one or
> more scopes of variables that the procedure is declared inside of and
> can refer to.  The outermost scope always exists, so we need three
> nested scopes to get an example.
> 
> MODULE Outer
> 
> ; PROCEDURE Middle ( MiddleFormal : INTEGER )
> 
>   = PROCEDURE Inner ( ) : INTEGER
> 
>     = BEGIN
>         RETURN MiddleFormal
>       END
> 
>   ; BEGIN (* Middle *)
>       ProcVar := Inner (* Statically illegal because Inner is not top-level. *)
>     END (* Middle
> 
> ; VAR ProcVar : PROCEDURE ( ) : INTEGER
> ; VAR X : INTEGER
> 
> ; BEGIN (* Outer *)
>     Middle ( 7 )
>   ; X := ProcVar ( )
>   END Outer
> .
> 
> If the assignment ProcVar := Inner were legal, the call ProcVar ( )
> goes to Inner, which refers to MiddleFormal of Middle, but there is no
> active invocation of Middle, and MiddleFormal doesn't exist.
> 
> Pascal (if I remember all this right) allows procedures to be passed
> as parameters, but not assigned to variables.  The procedure constant
> in question can only be named where it has an environment.  If all you
> can do with it is pass it, any use of it can only be deeper inside the
> dynamic call chain, where its environment continues to exist.
> 
> Modula-2 allows procedures to be either passed or assigned, but in
> either case, only a top-level procedure, which always has an
> environment, can be given.
> 
> Both passing and assigning procedures have reasonable uses, both for
> variations on the callback theme.
> 
> Modula-3 supports both by allowing any procedure to be passed but only
> a top-level one to be assigned.  Enforcing the latter restriction
> sometimes means a runtime check at the point of an assignment, if the
> RHS of the assignment is a procedure formal parameter, which could
> dynamically be top-level or not.  This is probably not a
> high-frequency situation.  Assigning a procedure constant and passing
> any procedure can be fully checked at compile time.
> 
> I think it is possible to define a weaker, yet safe rule that
> postpones runtime environment existence checking until the point of a
> call on a procedure variable, but I don't recall seeing this in any
> language.  Maybe Algol68 or something.

Algol 68 restricted assignment.  The 'scope' of the procedure had to 
be at most as deeply nested as the 'scope' of the variable.  This was a 
general restriction that applied to everything, though, not just 
procedures.  This meant you could assign nested procedures to more 
nested variables.  The 'scope' of a procedure was determined by its 
most local global variable.

But scope checking led to heavy overhead on just about anything having 
to do with pointers, so it tended to be rarely inplemented.  As on 
implementer said, this isn't the kind of mistake programmers make, 
anyway.

The CDC Cyber implementation performed the check when called.  Each 
scope (or rather, each scope for with this situation could arise) caused 
a small object to be allocated on the heap on scope entry.  The stack 
frame would point to this object, and the object would point back to 
the stack frame.  A procedure would contain a pointer to this object 
for the stak frame contining its most local globals..  
WHen the procedure was called, it would check that this object indeed 
pointed to the place on the stack frame where there would be a pointer 
back to the object.

Still, the restriction eliminated the possibility of writing a 
function-composition function.

The only way I see of making this more liberal is to perform escape 
analysis on procedures, and subsequently choosing a few blocks whose 
stack frame would be allocated on the heap.  You could apply run-time 
tests to prevent you from jumping into stack frames that have already 
been exited (of course in Modula 3, there aren't any GOTOs.  It turns 
out that the analysis isn't all that difficult, and that for normal 
programs, almost no frames get allocated on the heap, hence little 
run-time overhead.  The mechanism could be useful for callbacks.

This is is the kind of analysis every decent Scheme compiler does to 
avoid accomodating the full force of conitinuation passing where it is 
not needed.

-- hendrik

> 
> In gcc-enhanced C, which allows nested functions, in addition to both
> assigning and passing (pointers to) functions, you are on your own to
> avoid calling something that lacks an environment.  The one help the
> language gives is to say in the reference, "all hell will break loose"
> if you get this wrong.

Does gcc-enhanced C allow you to put stack frames on the heap?

-- hendrik