TXL solution to [[TIL Chairmarks]] #2.5, Goto elimination, recognize and transform while-equivalent goto structures.

-- Main.JamesCordy - 31 Dec 2007


_File "TILgotoelim.Txl"_


<verbatim>
% Goto elimination in TIL programs
% Jim Cordy, January 2008

% Given a TIL program in an extended dialect that includes labelled statements 
% and goto statements, recognize and resolve while-equivalent goto structures.

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

% Preserve comments in this transformation
#pragma -comment

% Add labels and goto statements to TIL 
redefine statement
		  ...
	 |		  [labelled_statement]
	 |		  [goto_statement]
	 |		  [null_statement]
	 |		  [comment_statement]
end redefine

define labelled_statement
		  [label] ': [statement] 
end define

define goto_statement
		  'goto [label] ';  [NL]
end define

% Allow for trailing labels
define null_statement
		  [NL]
end define

define comment_statement
		  [comment]  [NL]
end define

define label 
		  [id]
end define


% Main program - just applies the rules for cases we know how to transform 

function main
	 replace [program]
		  P [program]
	 by
		  P [transformForwardWhile]
			 [transformBackwardWhile]
end function


% Case 1 - structures of the form
%		  loop:
%				if Cond then goto endloop; end
%				LoopStatements
%				goto loop;
%		  endloop:
%				TrailingStatements

rule transformForwardWhile
	 replace [repeat statement]
		  L0 [label] ': 
				'if X [expression] Op [op] Y [expression] 'then
					 'goto L1 [label] ';
				'end
		  Rest [repeat statement]
	 skipping [statement]
	 deconstruct * Rest
		  'goto L0 ';
		  L1 ':
				Follow [statement]
		  FinalRest [repeat statement]
	 construct NonRest [repeat statement]
		  Rest [truncateGoto L0 L1]
	 by
		  'while X Op [invertOp] Y 'do
				NonRest
		  'end
		  Follow
		  FinalRest
end rule

function truncateGoto L0 [label] L1 [label]
	 replace * [repeat statement]
		  'goto L0 ';
		  L1 ':
				Follow [statement]
		  FinalRest [repeat statement]
	 by
		  % nothing
end function

% Since TIL doesn't have a not operator, we need to invert comparisons
function invertOp
	 construct Ops [repeat op]
		  '= '!=
	 construct InvertOps [repeat op]
		  '!= '=
	 replace [op]
		  Op [op]
	 by
		  Op [replaceOriginalOp Op each Ops InvertOps]
end function

function replaceOriginalOp OriginalOp [op] PatternOp [op] ReplacementOp [op]
	 replace [op]
		  OriginalOp 
	 by
		  OriginalOp [$ PatternOp ReplacementOp]
end function


% Case 2 - structures of the form
%		  loop:
%				LoopStatements
%				if Cond then goto loop; end
%		  TrailingStatements

rule transformBackwardWhile
	 replace [repeat statement]
		  L0 [label] ': 
				First [statement]
		  Rest [repeat statement]
	 skipping [statement]
	 deconstruct * Rest
		  'if C [expression] 'then
				'goto L0 ';
		  'end
		  FinalRest [repeat statement]
	 construct NonRest [repeat statement]
		  Rest [truncateIfGoto L0]
	 construct WhileStatement [repeat statement]
		  'while C 'do
				First
				NonRest
		  'end
	 by
		  First
		  NonRest [. WhileStatement]
					 [. FinalRest]
end rule

function truncateIfGoto L0 [label]
	 skipping [statement]
	 replace * [repeat statement]
		  'if C [expression] 'then
				'goto L0 ';
		  'end
		  FinalRest [repeat statement]
	 by
		  % nothing
end function
</verbatim>


_Example run:_ "gotofactors.til" is a goto-based version of the factors.til example program.


<verbatim>
<linux> cat gotofactors.til
// Factor an input number - goto version
var n;
var f;
write "Input n please";
read n;
write "The factors of n are";
f := 2;
// Outer loop over potential factors
factors:
	 if  n = 1 then
		  goto endfactors;
	 end
// Inner loop over multiple instances of same factor
multiples: 
	 if (n / f) * f != n then
		  goto endmultiples;
	 end
	 write f;
	 n := n / f;
	 goto multiples;
endmultiples:
	 f := f + 1;
	 goto factors;
endfactors:

<linux> txl gotofactors.til TILgotoelim.Txl 
TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston
Compiling TILgotoelim.Txl ... 
Parsing gotofactors.til ...
Transforming ...

// Factor an input number - goto version
var n;
var f;
write "Input n please";
read n;
write "The factors of n are";
f := 2;
// Outer loop over potential factors
while n != 1 do
	 // Inner loop over multiple instances of same factor
	 while (n / f) * f = n do
		  write f;
		  n := n / f;
	 end
	 f := f + 1;
end

<linux>
</verbatim>