Escapes
*******

Escaping Variables
==================

A language is said to support the block structure when all the nesting levels have the same rights.  For instance C does not have this property since you are not allowed to introduce functions in functions, but only at the top level.

One of the most typical features of languages with block structure is the ability for nested functions to access the variables of the outer functions.  Tiger being one such language, here is a dummy example of this sharing:

     let function outer () =
         let var escaping := "Bye Bye!"
             var prisoner := "Boowoo..."
             function inner (msg:string) =
               (print (msg); print (escaping))
          in
            inner (prisoner)
          end
     in
       outer ()
     end

The variable escaping is used by a nested function, and this nested function will need an access to it.  This variable is said to escape.  The variable prisoner does not escape.

As we will see with more details later, escaping variables require a special treatment.  For a start, you can easily imagine that we cannot put an escaping variable in a register (Actually it is possible, but it would require inter function register allocation.  Since we compile functions, nested or not, independently, we cannot.).  As you can see, we need to know whether a variable escapes where it is defined: the IR translation will need to know where to allocate the newly declared variable (register or stack).  Unfortunately the escaping status of a variable is not known until all its uses have been checked.

Therefore, we have to compute the escapes before performing the translation: these two phases cannot be done concurrently (well, sure you can, but that makes it hacky, hairy, fragile, and complex).  You are free to compute them before or after type checking, they are commutative when there are no error in the source.

What if there are errors?

Obviously not only variables are concerned by this: formals too:

     let function print_escaping (escaping: int, not_escaping: int) : int =
         let function escaping_value () : int = escaping
         in
            escaping_value () + not_escaping
         end
     in
       print_escaping (1, 2)
     end

Finally, note that the outer level, the top level, with this regard, should be considered as a function:

     let var escaping     := "I rule the world!"
         var not_escaping := "Peace on Earth for humans of good will."
         function print_escaping () = print (escaping)
     in
       not_escaping;
       print_escaping ()
     end

Computing the Escapes
=====================

The algorithm is dead simple: walk the abstract syntax tree, tag each variable declaration tag as ``not escaping'', each time you see a use of a variable that was not declared with the current scope, tag its definition site as ``escaping''.

This means we need a means to recover the definition site of a variable each time we find a use: we need a table of symbols.  Obviously the boundaries we are interested in are related to the definition of functions, therefore, scope_begin and scope_end are invoked when visiting a function declaration.

You are encouraged to study the following example, which might exhibit something you did not consider...

     let var public  := 0
     in
        /* Redefine PUBLIC to stress the escape checker. */
        let var public  := 1 in public end;
        /* Now actually use PUBLIC as an escaping variable. */
        let function inner () : int = public
        in
          inner ()
        end
     end