Self Tracing Programs Using TXL

TXL solution to TIL Chairmarks #4.3: Self-tracing program transformation.

-- JamesCordy - 10 Oct 2005

File "TILtrace.Txl"

% Simple transform to make a Tiny Imperative Language program self-tracing
% Jim Cordy, August 2005

% Replaces every statement in the program with a write statement of its text
% followed by itself.  For example:
%
%    write ("x := 5;");
%    x := 5;

% Begin with the TIL base grammar
include "TIL.Grm"

% We don't bother preserving comments in this transformation
% since we're not interested in maintaining the result, just running it

% Tell TXL what our string escape convention is
#pragma -esc "\"

% Allow for concise elided structured statements
redefine statement
        ... 
    |     [SP] '... [SP]
end redefine

% Allow for traced statements - the attribute TRACED marks statements already done
redefine statement
        ...
    |    [traced_statement]
end redefine

define traced_statement
    [statement] [attr 'TRACED]
end define

% Replace every statement by a tracing write statement followed by itself
rule main
    % Since our result requires two statements where one was before,
    % we work on the statement sequence one level up
    replace [repeat statement]
        S [statement]
        Rest [repeat statement]
    % Semantic guard: if it's already done don't do it again
    deconstruct not S
        _ [statement] 'TRACED
    % Make a concise version of structured statements
    construct ConciseS [statement]
        S [deleteBody]
    % Make a string literal of the text of the concise statement
    construct QuotedS [stringlit]
        _ [+ "Trace: "] [quote ConciseS] 
    by
        'write QuotedS;    'TRACED
        S                  'TRACED
        Rest
end rule

% Replace any embedded statement sequence in the printed version of 
% a traced statement with an elision symbol for conciseness
function deleteBody
    replace * [statement*]
        _ [statement*]
    by
        '...
end function

Example run:

<linux> cat factors.til
// Factor an input number
var n;
write "Input n please";
read n;
write "The factors of n are";
var f;
f := 2;
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
    f := f + 1;
end
<linux> txl factors.til TILtrace.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILtrace.Txl ... 
Parsing factors.til ...
Transforming ...
write "Trace: var n;";
var n;
write "Trace: write \"Input n please\";";
write "Input n please";
write "Trace: read n;";
read n;
write "Trace: write \"The factors of n are\";";
write "The factors of n are";
write "Trace: var f;";
var f;
write "Trace: f := 2;";
f := 2;
write "Trace: while n != 1 do ... end";
while n != 1 do
    write "Trace: while (n / f) * f = n do ... end";
    while (n / f) * f = n do
        write "Trace: write f;";
        write f;
        write "Trace: n := n / f;";
        n := n / f;
    end
    write "Trace: f := f + 1;";
    f := f + 1;
end
<linux>