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.

No comments: