TXL solution to [[TIL Chairmarks]] #5.1: A complete [[Tiny Imperative Language]] interpreter implemented as a standalone TXL source transformation. No other libraries or support modules are required, the entire interpreter is here. -- Main.JamesCordy - 10 Oct 2005 _File "til.Txl"_ Notes: (1) Because the transformation is named "til.Txl", TXL will infer that it is the default transformation for source files named ending in ".til". This is convenient for an interpreter! (2) Because it's small, we've put all the source code in one file. Normally a real interpreter would have the VM module, statement module and expression module separated into include files. % Tiny Imperative Language interpreter % Jim Cordy, August 2005 % This program is a simple interpreter that directly executes TIL programs % by transforming them to their meaning statement-by-statement. % Some details not well defined in the TIL grammar are assumed: % % - It is not clear whether TIL is scoped or not. This interpreter assumes % all declarations are in one scope. The change to traditional nested % scoping, if required, is trivial. % % - The comment for the "for" statement in the grammar says it is a % "declaring for". We assume this means the for automatically declares % its control variable, with the same scope as a variable declaration. % % - As a consequence of the above, it is assumed that redeclaration is not % an error, rather simply uninitializes the variable. % % - It is not clear whether TIL write statements output a whole line or a % partial line. We assume whole. % % All these decisions are easy to change. % Begin with the TIL base grammar, with priority parse #define PRIORITY include "TIL.Grm" % Marker for detecting uninterpretable statements redefine statement ... | 'null; end redefine % VM (virtual machine) memory cells define memory_cell [id] [literal] end define % Execute the program statement by statement function main % The VM memory export Memory [memory_cell*] _ % Initially empty replace [program] Statements [statement*] by Statements [executeStatements] end function % Consume each statement we execute rule executeStatements replace [statement*] S [statement] Rest [statement*] construct Execution [statement] S [executeStatement] by Rest end rule % It must be one of the statement forms we know (all of those in TIL). % Each statement interpreted is transformed into the special statement % "null;" so that we can tell when interpretation of a statement fails % for some reason and give an error message function executeStatement replace [statement] S [statement] by S [executeDeclaration] [executeAssignment] [executeIf] [executeWhile] [executeFor] [executeRead] [executeWrite] [failure] end function % If the statement was not transformed to "null;" by one of the % statement interpretations, then we were unable to interpret it % so give a message and halt function failure match [statement] S [statement] deconstruct not S 'null; construct ErrorMessage [stringlit] _ [+ "*** Error: unable to interpret statement: '"] [quote S] [+ "'"] [print] [quit 101] end function % Interpret a declaration statement by adding an entry for the variable % to the VM memory. If a previous one of the same name is already in % the memory, remove it function executeDeclaration replace [statement] 'var Id [id] ; import Memory [memory_cell*] export Memory Id "--UNDEFINED--" Memory [removeOldDeclaration Id] by 'null; end function function removeOldDeclaration Id [id] replace * [memory_cell*] Id _ [literal] RestOfMemory [memory_cell*] by RestOfMemory end function % Interpret an assignment statement by evaluating the expression and % setting the VM memory cell for the variable to that value function executeAssignment replace [statement] Id [id] := Expn [expression] ; construct ExpnValue [expression] Expn [evaluateExpression] deconstruct ExpnValue Value [literal] import Memory [memory_cell*] export Memory Memory [checkDefined Id] [setValue Id Value] by 'null; end function % Interpret an if statement by evaluating the expression and % executing the appropriate branch function executeIf replace [statement] 'if Expn [expression] 'then S [statement*] OptElse [opt else_statement] 'end construct ExpnValue [expression] Expn [evaluateExpression] deconstruct ExpnValue Value [literal] construct TruePart [statement*] S [executeThen Value] construct FalsePart [opt else_statement] OptElse [executeElse Value] by 'null; end function function executeThen Value [literal] deconstruct not Value 0 replace [statement*] S [statement*] by S [executeStatements] end function function executeElse Value [literal] deconstruct Value 0 replace [opt else_statement] 'else S [statement*] by 'else S [executeStatements] end function % Interpret a while statement by transforming to its recursive meaning, % that is: while E do S end => if E then S while E do S end end function executeWhile replace [statement] WhileStatement [statement] deconstruct WhileStatement 'while Expn [expression] 'do S [statement*] 'end construct IfStatement [statement] 'if Expn 'then S [. WhileStatement] 'end by IfStatement [executeStatement] end function % Interpret a for statement by transforming to its while meaning, that is: % for I := E1 to E2 do S end => % var I; I := E1; var I_Upper; I_Upper := E2; while I - I_Upper do S end function executeFor replace [statement] 'for Id [id] := E1 [expression] 'to E2 [expression] 'do S [statement*] 'end construct UpperId [id] Id [_ 'Upper] [!] construct InitialStatements [statement*] 'var Id; Id := E1; 'var UpperId; UpperId := (E2) + 1; construct IterateStatement [statement] Id := Id + 1; construct WhileStatement [statement] 'while Id - UpperId 'do S [. IterateStatement] 'end construct Initialize [statement*] InitialStatements [executeStatements] by WhileStatement [executeStatement] end function % Interpret a read statement by reading an input value and transforming % to an assignment to the variable function executeRead replace [statement] 'read Id [id] ; construct Input [opt literal] _ [getp "read: "] deconstruct Input Value [literal] construct Assignment [statement] Id := Value; by Assignment [executeStatement] end function % Interpret a write statement by evaluating the expression and outputting % it to the terminal % Note: not clear whether items are output as a whole a line (assume yes) function executeWrite replace [statement] 'write Expn [expression] ; construct ExpnValue [expression] Expn [evaluateExpression] [writeString] [writeInteger] by 'null; end function function writeString match [expression] S [stringlit] construct Output [stringlit] S [print] end function function writeInteger match [expression] I [integernumber] construct Output [integernumber] I [print] end function % Utility functions for the VM function checkDefined Id [id] match [memory_cell*] Memory [memory_cell*] deconstruct not * [id] Memory Id construct ErrorMessage [stringlit] _ [+ "*** Error: undeclared variable : '"] [quote Id] [+ "'"] [print] [quit 102] end function function setValue Id [id] Value [literal] replace * [memory_cell] Id _ [literal] by Id Value end function % Expression evaluation rule evaluateExpression replace [expression] E [expression] construct NewE [expression] E [evaluateParens] [evaluatePrimaries] [evaluateMultiplications] [evaluateDivisions] [evaluateAdditions] [evaluateSubtractions] [evaluateEquals] [evaluateNotEquals] deconstruct not NewE E by NewE end rule rule evaluateParens replace [primary] ( Expn [expression] ) construct ExpnValue [expression] Expn [evaluateExpression] deconstruct Expn Value [literal] by Value end rule rule evaluatePrimaries replace [primary] Id [id] import Memory [memory_cell*] construct Check [memory_cell*] Memory [checkDefined Id] deconstruct * [memory_cell] Memory Id Value [literal] by Value end rule rule evaluateEquals replace [expression] I1 [integernumber] = I2 [integernumber] by I1 [- I2] [toBoolean] [+ 1] [rem 2] end rule rule evaluateNotEquals replace [expression] I1 [integernumber] != I2 [integernumber] by I1 [- I2] [toBoolean] end rule function toBoolean replace [integernumber] N [integernumber] deconstruct not N 0 by 1 end function rule evaluateAdditions replace [term] I1 [integernumber] + I2 [integernumber] by I1 [+ I2] end rule rule evaluateSubtractions replace [term] I1 [integernumber] - I2 [integernumber] by I1 [- I2] end rule rule evaluateMultiplications replace [factor] I1 [integernumber] * I2 [integernumber] by I1 [* I2] end rule rule evaluateDivisions replace [factor] I1 [integernumber] / I2 [integernumber] by I1 [div I2] end rule _Example run:_ 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 txl factors.til TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling til.Txl ... Parsing factors.til ... Transforming ... Input n please read: 76 The factors of n are 2 2 19