Expressions can be evaluated using a simple bottom-up traversal of the AST. The bottomup traversal strategy does just that; it applies its argument strategy first to the leaves of the tree, and then to each level above. The try strategy makes its argument strategy always succeeding. Thus, the eval-exp strategy performs a bottomup traversal of the AST of an expression, applying the Eval rules from module sim/til-eval. The eval-exp strategy is parameterized with a strategy for evaluating variables; their values depend on prior assignments in the program.

module til-eval-exp
imports til-eval
strategies

  eval-exp(eval-var) = 
    bottomup(try(
      eval-var <+ EvalAdd <+ EvalMul <+ EvalSub <+ EvalDiv <+ EvalMod
      <+ EvalLeq <+ EvalGeq <+ EvalLt <+ EvalGt <+ EvalEqu <+ EvalNeq
      <+ EvalOr <+ EvalAnd <+ EvalS2I <+ EvalI2S
    ))



    

The essence of an imperative language is the manipulation of values in the store, held by variables. In TIL variables are introduced by the Declaration construct. The values of variables is set, or changed by the Assign assignment statement, and the Read input statement. The Write statement prints the value of an expression. The interpreter uses the dynamic rewrite rule EvalVar to store the mappings from variables to their values.

When encountering a variable declaration, the current scope is labeled with the name of that variable, and its mapping is undefined, reflecting the fact that the variable doesn't have a value after being declared. Note that the scope of a variable in TIL is the rest of the current block. When encountering an assignment statement the EvalVar rule for the variable being assigned is updated. Thus, after an assignment to a variable x, EvalVar rewrites that variable to its value. Similarly, the Read input statement reads the next line from the stdin stream, decides whether it represents an integer or a string, and defines the EvalVar rule for the variable. Finally, the eval-exp strategy is now defined in terms of the parameterized eval-exp strategy from module run/til-eval-exp using the EvalVar rule as strategy for evaluating variables. In addition, the VarUndefined strategy is provided to catch variables that are used before being assigned to.

module til-eval-var
imports til-eval-exp
strategies

  eval-declaration = 
    (?Declaration(x) <+ ?DeclarationTyped(x, t))
    ; rules( EvalVar+x :- Var(x) )

  eval-assign = 
    Assign(?x, eval-exp => val)
    ; rules(EvalVar.x : Var(x) -> val)

  EvalRead :
    FunCall("read", []) -> String(x)
    where stdin-stream; read-text-line => x

  eval-write = 
    ?ProcCall("write", [<eval-exp>])
    ; ?String(<try(un-double-quote); try(unescape)>)
    ; <fprint>(<stdout-stream>, [<id>])

  VarUndefined =
    ?Var(<id>)
    ; fatal-err(|<concat-strings>["variable ", <id>, " used before being defined"])

  eval-exp = 
    eval-exp(EvalVar <+ VarUndefined <+ EvalRead)

What remains is the interpretation of control-flow statements. A block statements simply entails the execution of each statement in the block in order. Any variables declared within the block are local, and shadow variables with the same name in outer blocks. For this purpose a dynamic rule scope {| EvalVar : ... |} is used to restrict the scope of EvalVar rules to the block. The statements in a block are evaluated by mapping the eval-stat strategy over the list of statements. For the execution of the if-then-else construct, first the condition is evaluated. The EvalIf rule then evaluates the construct, reducing it to one of its branches. The resulting block statement is then evaluated by eval-stat. The while statement is evaluated by transforming the loop to an if-then-else statement, with a Goto at the end of the body. The dynamic rule EvalGoto maps the goto statement for the new label to the if-then-else statement.

module til-eval-stats
imports til-eval-var
signature
  constructors
    Goto : String -> Stat
strategies

  eval-block = 
    ?Block(<eval-stats>)

  eval-stats = 
    {| EvalVar : map(eval-stat) |}

  eval-stat = //debug(!"eval-stat: "); (
    eval-assign
    <+ eval-write
    <+ eval-declaration
    <+ eval-block
    <+ eval-if
    <+ eval-while
    <+ EvalGoto
  //)

  eval-if = 
    IfElse(eval-exp, id, id)
    ; EvalIf
    ; eval-stat

  eval-while = 
    ?While(e, st*)
    ; where(new => label)
    ; where(<conc>(st*, [Goto(label)]) => st2*)
    ; rules( EvalGoto : Goto(label) -> <eval-stat>IfElse(e, st2*, []) )
    ; <eval-stat> Goto(label)

To complete the interpreter we define an interpretation strategy for the Program constructor, and a main strategy that takes care of I/O. The program is compiled in the usual way, taking into account the include paths for the ../sig and ../sim directories that contain the TIL signature and evaluation rules, respectively.

module til-run
imports libstrategolib til-eval-stats
strategies

  io-til-run = 
    io-wrap(eval-program)

  eval-program = 
    ?Program(<eval-stats>)
    ; <exit> 0

#! /bin/sh -e

# compile til-simplify
strc -i til-run.str -I ../sig -I ../sim -la stratego-lib -m io-til-run

Now it is time to try out the interpreter at our test1.til program that computes the factorial of its input. Note that the interpreter operates on a parsed and simplified version of the program; not directly on the text file.

# run test1.til after parsing and simplification
echo "10" | ../run/til-run -i test1.sim.atil > test1.run

factorial of 10 is 3628800