Chapter 6. Interpretation

Table of Contents

6.1. Evaluating Expressions
6.2. Evaluating Variable Accesses
6.3. Evaluating Statements
6.4. The Complete Interpreter
6.5. Running TIL Programs

Interpreting programs does not seem a typical application of program transformation. However, in partial evaluation a program is evaluated as far as possible. Also in simpler transformations, evaluating a part of a program is a common operation. Furthermore, in order to execute programs in our TIL language, it is useful have an interpreter.

This chapter shows how to construct an interpreter for typical elements of an imperative language, such as expressions, variable access constructs, and control-flow statements. The specification uses advanced features of Stratego such as traversal strategies, pattern match operations, match-project, and dynamic rewrite rules. So don't be surprised if you don't get it all on a first reading.

The interpreter developed in this chapter requires the parsing and simplification infrastructure from the previous chapters. That is, the interpreter operates on the abstract syntax tree of a program after simplification.

6.1. Evaluating Expressions

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.

Figure 6.1. file: til/run/til-eval-exp.str

module til-eval-exp
imports til-eval

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


6.2. Evaluating Variable Accesses

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.

Figure 6.2. file: til/run/til-eval-var.str

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

  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 =
    ; fatal-err(|<concat-strings>["variable ", <id>, " used before being defined"])

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

6.3. Evaluating Statements

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.

Figure 6.3. file: til/run/til-eval-stats.str

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

  eval-block = 

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

  eval-stat = //debug(!"eval-stat: "); (
    <+ 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)

6.4. The Complete Interpreter

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.

Figure 6.4. file: til/run/til-run.str

module til-run
imports libstrategolib til-eval-stats

  io-til-run = 

  eval-program = 
    ; <exit> 0

Figure 6.5. file: til/run/maak

#! /bin/sh -e

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

6.5. Running TIL Programs

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.

Figure 6.6. file: til/xmpl/run-test1

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

Figure 6.7. file: til/xmpl/

factorial of 10 is 3628800