Friday, December 21, 2012

7. Evaluating Wally


Parts: 1 2 3 4 5 6 7

In the previous part of this tutorial, we've laid the ground work for actually being able to evaluate some (basic) Wally scripts.

If you don't already have the source created so far, get it here.

Okay, so the simple script like:

println(2 + 3 * 4)

throws an (expected) exception. Let's see what AST nodes are involved to be able to evaluate this properly. ANTLRv3 has some nice utility classes that can visualize the AST that make it easy to debug.

WallyParser parser = getParser("src/scripts/Test.wy");
CommonTree tree = (CommonTree) parser.parse().getTree();
DOTTreeGenerator gen = new DOTTreeGenerator();
System.out.println(gen.toDOT(tree));

The code posted above would print DOT output that corresponds to the following AST:

The AST above can be divided into 6 different nodes:

  • BlockNode - containing all statements in the script (just 1 in this case)
  • PrintlnNode - responsible to print the expression
  • AddNode - responsible to perform additions
  • MultNode - responsible to perform multiplications
  • NumberNode - holding numerical values
  • VoidNode - holds a 'void' constant

You might argue that there should/could also be a ReturnNode, in which case you would be right. However, I've decided not to because the last statement in a BlockNode will always contain the return statement.

Below is the code for each of these nodes listed with a bit of inline comments added to explain things:


BlockNode

package wally.ast;

import wally.lang.WValue;

import java.util.ArrayList;
import java.util.List;

public class BlockNode implements WNode {

    private List<WNode> nodes;

    public BlockNode() {
        nodes = new ArrayList<WNode>();
    }

    public void add(WNode node) {
        nodes.add(node);
    }

    @Override
    public WValue eval() {

        for(WNode node : nodes) {

            // evaluate the node
            WValue value = node.eval();

            // if the evaluated value is other than a VOID, return it
            if(value != WValue.VOID) {
                return value;
            }
        }

        // apparently this node has nothing to return
        return WValue.VOID;
    }
}

PrintlnNode

package wally.ast;

import wally.lang.WValue;

public class PrintlnNode implements WNode {

    private WNode expression;

    public PrintlnNode(WNode e) {
        expression = e;
    }

    @Override
    public WValue eval() {

        if(expression == null) {
            // if these is no expression, simply print an empty line
            System.out.println();
        }
        else {
            // evaluate the expression and print it to the console 
            WValue value = expression.eval();
            System.out.println(value.str());
        }
        
        // this node has nothing to return
        return WValue.VOID;
    }
}

AddNode

package wally.ast;

import wally.lang.WValue;

public class AddNode implements WNode {

    private WNode left;
    private WNode right;

    public AddNode(WNode l, WNode r) {
        left = l;
        right = r;
    }

    @Override
    public WValue eval() {
        
        // evaluate both the left and right children
        WValue v1 = left.eval();
        WValue v2 = right.eval();
        
        // and return them added together
        return v1.add(v2);
    }
}

MultNode

package wally.ast;

import wally.lang.WValue;

public class MultNode implements WNode {

    private WNode left;
    private WNode right;

    public MultNode(WNode l, WNode r) {
        left = l;
        right = r;
    }

    @Override
    public WValue eval() {

        // evaluate both the left and right children
        WValue v1 = left.eval();
        WValue v2 = right.eval();

        // and return them multiplied
        return v1.mult(v2);
    }
}

NumberNode

package wally.ast;

import wally.lang.WNumber;
import wally.lang.WValue;

public class NumberNode implements WNode {

    private Number number;

    public NumberNode(String v) {
        number = Double.valueOf(v);
    }

    @Override
    public WValue eval() {
        // create a WNumber instance and return it
        return new WNumber(number);
    }
}

VoidNode

package wally.ast;

import wally.lang.WValue;

public class VoidNode implements WNode {

    @Override
    public WValue eval() {
        // simply return the VOID constant
        return WValue.VOID;
    }
}

Okay, we're halfway being able to evaluate that simply script. We only need to adjust the tree walker rules so that they actually use our new nodes posted above. I'll not post the entire tree grammar, but only those rules that need to be changed.


walk-rule

walk returns [BlockNode root]
@init{$root = new BlockNode();}
 : ^(BLOCK (file_atom {$root.add($file_atom.n);})* return_stat {$root.add($return_stat.n);})
 ;

file_atom returns [WNode n]
 : block_atom {$n = $block_atom.n;}
 ;

// block

block_atom returns [WNode n]
 : assignment    {/* TODO */}
 | function_call {$n = $function_call.n;}
 | for_stat      {/* TODO */}
 | if_stat       {/* TODO */}
 | while_stat    {/* TODO */}
 | Break         {/* TODO */}
 ;

// for_stat

// if_stat

// while_stat

// assignment

function_call returns [WNode n]
 : lookup                   {/* TODO */}
 | ^(Print expr)            {/* TODO */}
 | ^(Println expr?)         {$n = new PrintlnNode($expr.n);}
 | ^(Assert a=expr b=expr?) {/* TODO */}
 ;

return_stat returns [WNode n]
 : ^(RETURN expr) {$n = $expr.n;}
 | ^(RETURN VOID) {$n = new VoidNode();}
 ;

expr returns [WNode n]
 : ^((Or | OR) a=expr b=expr)      {/* TODO */}
 | ^((And | AND) a=expr b=expr)    {/* TODO */}
 | ^(Lt a=expr b=expr)             {/* TODO */}
 | ^(Gt a=expr b=expr)             {/* TODO */}
 | ^(LtEq a=expr b=expr)           {/* TODO */}
 | ^(GtEq a=expr b=expr)           {/* TODO */}
 | ^(Eq a=expr b=expr)             {/* TODO */}
 | ^(NEq a=expr b=expr)            {/* TODO */}
 | ^((Add | ADD) a=expr b=expr)    {$n = new AddNode($a.n, $b.n);}
 | ^((Sub | SUB) a=expr b=expr)    {/* TODO */}
 | ^((Mult | MULT) a=expr b=expr)  {$n = new MultNode($a.n, $b.n);}
 | ^((Div | DIV) a=expr b=expr)    {/* TODO */}
 | ^((Mod | MOD) a=expr b=expr)    {/* TODO */}
 | ^(U_MINUS a=expr)               {/* TODO */}
 | ^(Not a=expr)                   {/* TODO */}
 | ^((Pow | POW) exprs)            {/* TODO */}
 | ^(TERNARY a=expr b=expr c=expr) {/* TODO */}
 | ^(In a=expr b=expr)             {/* TODO */}
 | ^(New Id e=expr_params)         {/* TODO */}
 | lookup                          {/* TODO */}
 | list                            {/* TODO */}
 | Param                           {/* TODO */}
 | Str                             {/* TODO */}
 | Num                             {$n = new NumberNode($Num.text);}
 | (True | TRUE)                   {/* TODO */}
 | False                           {/* TODO */}
 | None                            {/* TODO */}
 ;

// lookup

// tail

// exprs

// expr_params

// list

If you now recreate a JAR (also causing new parser file to be created) and rerun the **Test.wy** script:

ant jar
java -jar Wally.jar src/scripts/Test.wy

you would see the following being printed to your console:

14

Which, obviously, is the correct answer to 2 + 3 * 4.

If you'd like to experiment with Wally in it's current state, download the unfinished project here. And if you want to get all nodes implemented, download the complete project here.

If you like, you can even test Wally online: I deployed a small interpreter in Appspot here.

6. Wally ground work


Parts: 1 2 3 4 5 6 7

So, we've got the lexer, parser and tree-walker done for Wally. However, during the parsing phase, we've ignored functions, objects and use statements. We're going to handle them in this part of the tutorial. We'll also start with the implementation of Wally's data types.

We'll put the functions and objects in two instance variables in the parser (java.util.Maps) when we parse them. And we'll create a method handleUse(String name, String fileName) that will parse another Wally script when it is used.

grammar Wally;

// code omitted for brevity

@parser::members 
{
  private File file;
  private Map<String, Function> functions = new LinkedHashMap<String, Function>();
  private Map<String, Obj> objects = new LinkedHashMap<String, Obj>();

  public WallyParser(File f, CommonTokenStream stream) {
    super(stream);
    file = f;
  }

  public Map<String, Function> getFunctions() {
    return functions;
  }

  public Map<String, Obj> getObjects() {
    return objects;
  }

  private void handleUse(String name, String fileName) {
    try {
      File newFile = new File(file.getParentFile(), fileName);
      WallyParser parser = Wally.getParser(newFile);
      parser.parse();

      Map<String, Obj> objs = parser.getObjects();
      Map<String, Function> fns = parser.getFunctions();

      if(name.equals("*")) {
        objects.putAll(objs);
        functions.putAll(fns);
      }
      else {
        Obj obj = objs.get(name);

        if(obj != null) {
          objects.put(name, obj);
        }
        else {
          Function f = fns.get(name);

          if(f == null) {
            throw new RuntimeException("no such object or function: " + 
                                        name + " in: " + newFile);
          }

          functions.put(name, f);
        }
      }
    } catch(Exception e) {
      throw new RuntimeException(e);
    }
  }
}

// code omitted for brevity

use_stat
 : Use (t=Id | t='*') From Str EOL+ {handleUse($t.text, $Str.text);}
 ;

As you can see in the code above, I introduced some extra classes: Function and Obj. Let's define some more Wally-specific data-type, and related classes:



wally/Function.java

As the name suggests, a class that encapsulates a Wally-function. Below is a UML diagram of it:



wally/Scope.java

A class holding all variables in a certain scope.



wally/Obj.java

A class representing the "blue print" of a Wally object-instance.



wally/ast/WNode.java

A WNode is a simple interface all our AST classes will implement. It has just a single method defined in it:



wally/lang/WValue.java

A WValue is an abstract class that has mostly abstract methods:

Most methods are implemented so that they throw an exception when being invoked. Every "real" Wally value extends this class and only overrides those methods that make sense to that particular value, ignoring the other methods (causing an exception to be thrown when invoked).

For example, the boolean-Wally type would (at least) override not(), and(WValue) and or(WValue), but not mult(WValue), causing code like true * false to throw an exception.



wally/lang/WNumber.java

Wally's numerical type:



wally/lang/WBoolean.java

Wally's boolean type:



wally/lang/WString.java

Wally's string type:



wally/lang/WList.java

Wally's list type:



wally/lang/ObjInstance.java

The instance of a Wally object:



Tree walker

We will also adjust the constructor of the tree walker to take a Scope (the global scope) and the Map<String, Obj> and Map<String, Function> the parser built from the input script:
tree grammar WallyEvaluator;

// ...

@members {
  private Map<String, Obj> objects;
  private Map<String, Function> functions;
  private Scope globalScope;
  private Scope currentScope;

  // constructor used in the Function class
  public WallyEvaluator(CommonTreeNodeStream nodes, 
                        Scope s, 
                        Map<String, Obj> os, 
                        Map<String, Function> fns) {
    super(nodes);
    globalScope = s;
    currentScope = globalScope;
    objects = os;    
    functions = fns;
  }

  public WallyEvaluator(CommonTreeNodeStream nodes, 
                        Map<String, Obj> obj,
                        Map<String, Function> fns,
                        String[] params) {
    super(nodes);
    objects = obj;
    globalScope = new Scope();
    functions = fns;
    
    int num = 1;

    // add command line parameters to the global scope, put a `$` in front of it
    for(String param : params) {
      String name = "$" + num;
      WValue value = param.matches("[-+]?\\d+(\\.\\d*)?") ? 
          new WNumber(Double.valueOf(param)) : new WString(param);
      globalScope.put(name, value);
      num++;
    }

    // let the parent scope of all function-scopes be the global scope of the 
    // Wally script that is being evaluated at this moment
    ObjInstance globalFunctions = new ObjInstance("@functions", null, fns, null);
    Scope functionScope = new Scope();
    functionScope.put("this", globalFunctions);
    globalScope.put("this", globalFunctions);
    
    for(Function f : functions.values()) {
      f.setParentScope(functionScope);
    }
    
    currentScope = globalScope;
  }
}

walk returns [WNode root] 
@init{$root = null;}
 : ^(BLOCK file_atom* return_stat)
 ;
 
 // ...

If you now create a jar file of the project by executing the Ant task ant jar, and then execute the Wally script src/scripts/Test.wy, containing a simple script like this:

a = 2 + 40
println(a)

like this:

ant jar
java -jar Wally.jar src/scripts/Test.wy

you would get a java.lang.NullPointerException, but don't worry, that was expected. After all, the walk rule in tree walker simply returns null, where it's supposed to return an instance of a WNode. We will have to implement the AST nodes that actually evaluate the input. But that will be the subject of the next part of this tutorial.

Download the source of the project here created so far.