TXL solution to TIL Chairmarks #2.4, Declarations-to-local, move all declarations to their most local location.

-- JamesCordy - 02 Nov 2005

File "TILtolocal.Txl"

% TXL transformation to move all declarations in a TIL program to their most local location

% Jim Cordy, October 2005

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Transformation to move all declarations to their most local location -
% immediately before their first use, in the innermost block they can be.
% It is done as two rules - one that moves declarations across statements
% that do not depend on them, and one that moves declarations inside statements
% they are not used outside of.

rule main
    % Since this rule's pattern matches its result, it has no natural termination point
    replace [program]
        Program [program]

    % We therefore add an explicit fixed-point guard - after each application 
    % of the two base transformations, we check to see that something more was actually done
    construct NewProgram [program]
            Program [immediatizeDeclarations]
                [localizeDeclarations]
    deconstruct not NewProgram
            Program
    by
        NewProgram 
end rule

rule immediatizeDeclarations
    % Move all declarations past statements that don't depend on them
    % This rule uses a one-pass traversal ($) since the case of two declarations in a row
    % has no natural fixed point for this rule
    replace $ [statement*]
        'var V [id];
        Statement [statement]
        MoreStatements [statement*]

    % We can move the declaration past a statement if the statement does
    % not refer to the declared variable
    deconstruct not * [id] Statement
            V
    by
        Statement 
        'var V;
        MoreStatements
end rule

rule localizeDeclarations
    % Move any declarations outside a structured statement inside it if
    % the statements following it do not depend on the declared variable
    % Again, use a one pass ($) traversal
    replace $ [statement*]
        Declaration [declaration]
        CompoundStatement [statement]
        MoreStatements [statement*]

    % Check that it is some kind of compound statement (one with a statement list inside)
    deconstruct * [statement*] CompoundStatement
            _ [statement*]

    % Check that the following statements don't depend on the declaration
    deconstruct * [id] Declaration
            V [id]
    deconstruct not * [id] MoreStatements
            V

    % Alright, then maybe we can move it in.  This transformation uses the natural
    % example-base style of TXL, and thus does each kind of compound statement separately
    % Another solution might use agile parsing to abstract similar cases into one
    by
        CompoundStatement [injectDeclarationWhile Declaration] 
                          [injectDeclarationFor Declaration]
                          [injectDeclarationIfThen Declaration]
                          [injectDeclarationIfElse Declaration]
        MoreStatements 
end rule

function injectDeclarationWhile Declaration [declaration]
    % Note that there is no legal way that the while Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
            'while Expn [expression] 'do
            Statements [statement*]
        'end
    by
            'while Expn 'do
            Declaration
            Statements 
        'end
end function

function injectDeclarationFor Declaration [declaration]
    % Note that there is no legal way that the while Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
            'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do
            Statements [statement*]
        'end
    by
            'for Id := Expn1 'to Expn2 'do
            Declaration
            Statements 
        'end
end function

function injectDeclarationIfThen Declaration [declaration]
    % Note that there is no legal way that the if Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
        'if Expn [expression] 'then
            ThenStatements [statement*]
         OptionalElse [opt else_statement]
        'end
    deconstruct Declaration
            'var V [id];
    deconstruct not * [id] OptionalElse
            V
    by
        'if Expn 'then
            Declaration
            ThenStatements 
         OptionalElse
        'end
end function

function injectDeclarationIfElse Declaration [declaration]
    % Note that there is no legal way that the if Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
        'if Expn [expression] 'then
            ThenStatements [statement*]
        'else
            ElseStatements [statement*]
        'end
    deconstruct Declaration
            'var V [id];
    deconstruct not * [id] ThenStatements
            V
    by
        'if Expn 'then
            ThenStatements 
        'else
            Declaration
            ElseStatements 
        'end
end function

Example run: "gvareg.til" is a meaningless little program with lots of data dependencies and all global declarations for demonstration purposes.

<linux> cat gvareg.til
// Meaningless example TIL program with lots of data dependencies
var d;
var r;
var y;
var z;
var x;
var a;
var j;
var b;
var k;
var e;
var c;
var m;
var n;
d := 17;
r := 5;
read y;
read z;
while y != 0 do
    x := y + z;
    a := 3;
    j := 1;
    while j != 100 do
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        e := (x + z) * r;
        j := j + 1;
    end
    c := a + y;
    m := y * b;
    n := r * y;
    write n;
    y := y - 1;
end
<linux> txl gvareg.til TILtolocal.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILtolocal.Txl ... 
Parsing gvareg.til ...
Transforming ...
// Meaningless example TIL program with lots of data dependencies
var d;
d := 17;
var r;
r := 5;
var y;
read y;
var z;
read z;
while y != 0 do
    var x;
    x := y + z;
    var a;
    a := 3;
    var j;
    j := 1;
    var b;
    while j != 100 do
        var k;
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        var e;
        e := (x + z) * r;
        j := j + 1;
    end
    var c;
    c := a + y;
    var m;
    m := y * b;
    var n;
    n := r * y;
    write n;
    y := y - 1;
end
<linux>