tinypie 0.2
Tree-Based Interpreter, Compiler and VM for TinyPie language
License: MIT

TinyPie - Tree-Based Interpreter, Compiler, and VM for TinyPie language
=======================================================================

Overview
--------

TinyPie is a tree-based interpreter for a simple programming
language with a Python-like syntax.

It's based on Pie language from [Language Implementation Patterns](http://pragprog.com/titles/tpdsl/language-implementation-patterns) Ch.9

Quote from [the book](http://pragprog.com/titles/tpdsl/language-implementation-patterns): "A tree-based interpreter is like a compiler front
end with an interpreter grafted onto the end instead of a code generator"

TinyPie also includes Bytecode Assembler and Register-Based Virtual Machine.

Goals of the project
--------------------

1. Self-education

2. To serve as an example for people interested in crafting
   their own interpreter in Python for a simple programming language or DSL


Installation
------------

1. Using `buildout`

        $ git clone git://github.com/rspivak/tinypie.git
        $ cd tinypie
        $ python bootstrap.py
        $ bin/buildout

        Run the interpreter

        $ bin/tinypie factorial.tp

2. Using `pip` or `easy_install` (no need for sudo if using `virtualenv`)

        $ sudo pip install tinypie

        (or run alternatively easy_install: $ sudo easy_install tinypie)

        Run the interpreter

        $ tinypie factorial.tp


Main interpreter features
-------------------------

- Implemented in Python

- Regexp-based lexer

- LL(k) recursive-descent parser

- Parser constructs homogeneous Abstract Syntax Tree (AST)

- Static / lexical scope support.
  Interpreter builds complete scope tree during AST construction.

- Interpeter manages global memory space and function space stack

- Interpreter implements external AST visitor

- Forward references support


High-level overview:

                   |                 +------------------------------------+
                   |  source code    |      Symbol Table / Scope Tree     |
                   |                 |                                    |
                  \|/                |      +-----------------------+     |
    +--------------X---------------+ |      |      GlobalScope      |     |
    |                              | |      +----/-------------\----+     |
    |     Regexp-based lexer       | |          /               \         |
    |                              | |+--------/-----+   +-------\-------+|
    +--------------+---------------+ ||FunctionSymbol|   |FunctionSymbol ||
                   |                 |+------X-------+   +-------X-------+|
                   |  token stream   |      /|\                 /|\       |
                  \|/                |       |                   |        |
    +--------------X---------------+ |+------+-------+   +-------+-------+|
    |                              | ||  LocalScope  |   |  LocalScope   ||
    |LL(k) recursive-descent parser| |+--------------+   +---------------+|
    |                              | +------------------------------------+
    +--------------+---------------+
                   |                 +------------------------------------+
                   |  AST            |           Memory Space             |
                  \|/                |                                    |
    +--------------X-------------+   |Function Space    Global Memory     |
    |        Interpreter         |   |Stack             Space             |
    | with external tree visitor |   |+-------------+   +----------------+|
    |                            |   ||FunctionSpace|   |  MemorySpace   ||
    +--------------+-------------+   |+-------------+   +----------------+|
                   |                 |+-------------+                     |
                   |  output         ||FunctionSpace|                     |
                  \|/                |+-------------+                     |
                   X                 +------------------------------------+



This Tree-Based Interpreter is similar to [Syntax-Directed Interpreter](http://github.com/rspivak/nososql) but instead of directly executing
source code during parsing the interpreter executes the source code by
constructing AST and then walking the tree.

Advantages of tree-based interperter over syntax-directed one:

1. Symbol definition and symbol resolution happen at different stages:
   - symbol definition is performed during parsing
   - symbol resolution is performed during interpretation

   This allows forward references and simplifies implementation -
   parser deals with scope tree only and interpreter deals with memory
   spaces.

2. More flexible because of AST as an intermediate representation.


Language grammar
----------------

    program             -> (function_definition | statement)+ EOF
    function_definition -> 'def' ID '(' (ID (',' ID)*)? ')' slist
    slist               -> ':' NL statement+ '.' NL
                           | statement
    statement           -> 'print' expr NL
                           | 'return' expr NL
                           | call NL
                           | assign NL
                           | 'if' expr slist ('else' slist)?
                           | 'while' expr slist
                           | NL
    assign              -> ID '=' expr
    expr                -> add_expr (('<' | '==') add_expr)?
    add_expr            -> mult_expr (('+' | '-') mult_expr)*
    mult_expr           -> atom ('*' atom)*
    atom                -> ID | INT | STRING | call | '(' expr ')'
    call                -> ID '(' (expr (',' expr)*)? ')'


Short language reference
------------------------

- statements: `print`, `return`, `if`, `while`,  and function call
- literals: integers and strings
- operators: <, ==, +, -, *

Expressions may contain identifiers.

Code examples
-------------

1. Factorial

        print factorial(6)               # forward reference

        def factorial(x):                # function definition
            if x < 2 return 1            # if statement
            return x * factorial(x - 1)  # return statement
        .                                # DOT marks the block end

2. WHILE loop

        index = 0

        while index < 10:
            print index
            index = index + 1
        .                                # DOT marks the block end

3. IF ELSE

        x = 10
        if x == 10 print 'Yes'
        else print 'No'

4. Variable lookup in different scopes

        x = 1        # global variable
        def foo(x):  # 'foo' is defined in global memory space
            print x  # prints 3 (parameter value)
        .            # DOT marks the block end
        def bar():   # 'bar' is defined in global memory space
            x = 7    # modify global variable
        .            # DOT marks the block end

        foo(3)       # prints 3
        bar()
        print x      # prints 7 ('bar' modified global variable)


AST Examples
------------

Trees in these examples are represented as S-expressions for tersness.

Function call:

    foo(5, 7)

    (CALL ID INT INT) means CALL is the root with children ID(foo), INT(5), and INT(7)

Function definition:

    def foo(x, y):
        z = x + y
        return z
    .

    (FUNC_DEF ID ID ID (BLOCK (ASSIGN ID (SUB ID ID)) (RETURN ID)))


Development
-----------

Install 'enscript' utility (optional).
If you are on Ubuntu:

    $ sudo apt-get install enscript

Boostrap the buildout and run it:

    $ cd tinypie
    $ python bootstrap.py
    $ bin/buildout

Run tests, test coverage and produce coverage reports:

    $ bin/test
    $ bin/coverage-test
    $ bin/coveragereport

    Check ./var/report/tinypie.html out for coverage report.

Run pep8 and pylint to check code style and search for potential bugs:

    $ bin/pep8
    $ bin/pylint

AST visualizer
--------------

To see how TinyPie AST for different language constructs looks
like you can use `gendot` command line utility that is generated
by buildout. This utility generates DOT file than can be further
processed by [dot](http://www.graphviz.org/) program to draw nice graphs.

    $ echo -n 'foo(3)' | bin/gendot
    digraph astgraph {
       node [shape=plaintext, fontsize=12, fontname="Courier", height=.1];
       ranksep=.3;
       edge [arrowsize=.5]

       node1 [label="BLOCK"];
       node2 [label="CALL"];
       node3 [label="ID (foo)"];
       node4 [label="INT (3)"];

       node2 -> node3
       node2 -> node4
       node1 -> node2
    }

    To draw graph and save it as a PNG image:

    $ echo -n 'foo(3)' | bin/gendot > funcall.dot
    $ dot -Tpng -o funcall.png funcall.dot


Bytecode Assembler
------------------

Converts assembly program into binary bytecodes.
The bytecode is further interpreted by the TinyPie
Register-Based Bytecode Interpreter / Virtual Machine.

TinyPie Assembly language grammar:

    program -> globals? (label | function_definition | instruction | NL)+
    globals -> '.globals' INT NL
    label -> ID ':' NL
    function_definition -> '.def' ID ':' 'args' '=' INT ',' 'locals' '=' INT NL
    instruction -> ID NL
                 | ID operand NL
                 | ID operand ',' operand NL
                 | ID operand ',' operand NL ',' operand NL
                 | 'call' ID ',' operand NL
                 | 'loadk' REG ',' (INT | STRING) NL
    operand -> REG | ID | STRING | INT


Assembler yields the following components:

1. *Code memory*: This is a `bytearray` containing
   bytecode instructions and their operands derived from
   the assembly source code.

2. *Global data memory size*: The number of slots allocated
   in global memory for use with GSTORE and GLOAD assembly commands.

3. *Program entry point*: An address of main function `.def main: ...`

4. *Constant pool*: A list of objects (integers, strings, function symbols)
   that are not part of the code memory. Bytecode instructions refer
   to those objects via integer index.


Here is a factorial function in TinyPie language:

    def factorial(x):
        if x < 2 return 1
        return x * factorial(x - 1)
    .

    print factorial(5)


Here is an equivalent TinyPie assembly code:

    .def factorial: args=1, locals=3
        # r1 holds argument 'n'
        loadk r2, 2
        lt r3, r1, r2        # n < 2 ?
        brf r3, cont         # if n >= 2 jump to 'cont'
        loadk r0, 1          # else return 1
        ret
    cont:
        loadk r2, 1          # r2 = 1
        move r3, r1          # r3 = n
        sub r1, r1, r2       # r1 = n - 1
        call factorial, r1   # factorial(n - 1)
        mul r0, r3, r0       # n = n * result of factorial(n - 1)
        ret

    .def main: args=0, locals=1
        loadk r1, 5
        call factorial, r1   # factorial(5)
        print r0             # 120
        halt

Here are the resulting elements produced by the Bytecode Assembler
by translating the above assembly code:

    Constant pool:
    0000: <FunctionSymbol: name='factorial', address=0, args=1, locals=3>
    0001: 2
    0002: 1
    0003: <FunctionSymbol: name='main', address=95, args=0, locals=1>
    0004: 3

    Code memory:
    0000:   6   0   0   0   2   0   0   0
    0008:   1   4   0   0   0   3   0   0
    0016:   0   1   0   0   0   2  13   0
    0024:   0   0   3   0   0   0  41   6
    0032:   0   0   0   0   0   0   0   2
    0040:   9   6   0   0   0   2   0   0
    0048:   0   2  14   0   0   0   3   0
    0056:   0   0   1   2   0   0   0   1
    0064:   0   0   0   1   0   0   0   2
    0072:  16   0   0   0   0   0   0   0
    0080:   1   3   0   0   0   0   0   0
    0088:   0   3   0   0   0   0   9   6
    0096:   0   0   0   1   0   0   0   4
    0104:  16   0   0   0   0   0   0   0
    0112:   1  15   0   0   0   0  10

Bytecode instructions are described in the following section.


Register-Based Bytecode Interpreter / Virtual Machine
-----------------------------------------------------

Virtual Machine architecture:

1. **IP**: Instruction pointer register that points into the *code memory*
   at the next instruction to execute.

2. **CPU**: Instruction dispatcher that simulates *fetch-decode-execute*
   cycle with a *switch* (if elif) statement in a loop - reads bytecode
   at IP, decodes its operands and executes corresponding operation.

3. **Global data memory**: a list of global objects. Contents is
   accessed via integer index.

4. **Code memory**: Holds bytecode instructions and their operands.

5. **Call stack**: Holds StackFrame objects with function return address,
   parameters, and local variables.

6. **Stack frame**: A StackFrame object that holds all required information
   to invoke a function:
   - function symbol
   - function return address
   - registers hold return value, arguments, locals, and temporary values

7. **FP**: Frame pointer - a special-purpose register that points to
   the top of the function `call stack`

8. **Constant pool**: Integers, strings, and function symbols all go into
   constant pool. Instructions refer to constant pool values via an integer
   index.


High-level overview:

                                       |
                               TinyPie | assembly
                                       |
                                       V
                            +-----------------------+
                            |                       |
                            |  Bytecode Assembler   |
                            |                       |
                            +----------+------------+
                                       |
                code memory(bytecode)  |  constant pool
                                       V
    +--------------------------------------------------------------------------+
    |                                                                          |
    |          Register-Based Bytecode Interpreter / Virtual Machine           |
    |                                                                          |
    | +------------------------+        +------------------------------------+ |
    | |                        |        |       Function Call Stack          | |
    | |     Constant Pool      +----+   |                                    | |
    | |   (integer, string,    |    |   |                                    | |
    | |    function symbol)    |    |   | +--------------------------------+ | |
    | +------------------------+    |   | |        Stack Frame             | | |
    |                               |   | |                                | | |
    |                               |   | |function symbol: FS('main')     | | |
    |                               |   | |return address:  0              | | |
    | +------------------------+    |   | |          ret| args|locals      | | |
    | |                        |    |   | |registers: r0|r1 r2|r3 r4 r5    | | |
    | |  Global data memory    |    |   | +--------------------------------+ | |
    | |                        +-|  |   |                                    | |
    | |                        | |  |   |                                    | |
    | +------------------------+ |  |   | +--------------------------------+ | |
    |                            |  |   | |        Stack Frame             | | |
    |                            |  |   | |                                | | |
    |                            |  |   | |function symbol: FS('fact')     | | |
    | +------------------------+ |  |   | |return address: 17              | | |
    | |                        | |  |   | |          ret| args   |locals   | | |
    | |    Code memory         | |  |   | |registers: r0|r1 r2 r3|r4       | | |
    | |    (bytecode)          | |  |   | +--------------------------------+ | |
    | |                        | |  |   |                                    | |
    | +----------+-------------+ |  |   |                                    | |
    |            |               |  |   +------------------------------------+ |
    |            V               |  |                                          |
    + +------------------------+ |  |                                          |
    | |                        | |  |                                          |
    | |         CPU            <-+  |                                          |
    | | (fetch-decode-execute) |    |                                          |
    | |                        <----+                                          |
    | +------------------------+                                               |
    |                                                                          |
    +--------------------------------------------------------------------------+


Bytecode instructions for TinyPie VM:

    # Index serves as an opcode
    INSTRUCTIONS = [
        None,
        Instruction('add', REG, REG, REG),   # A B C  R(A) = R(B) + R(C)
        Instruction('sub', REG, REG, REG),   # A B C  R(A) = R(B) - R(C)
        Instruction('mul', REG, REG, REG),   # A B C  R(A) = R(B) * R(C)
        Instruction('lt', REG, REG, REG),    # A B C  R(A) = R(B) < R(C)
        Instruction('eq', REG, REG, REG),    # A B C  R(A) = R(B) == R(C)
        Instruction('loadk', REG, POOL),     # A B    R(A) = CONST_POOL[B]
        Instruction('gload', REG, POOL),     # A B    R(A) = GLOBALS[B]
        Instruction('gstore', POOL, REG),    # A B    GLOBALS[A] = R(B)
        Instruction('ret'),
        Instruction('halt'),
        Instruction('br', INT),              # A      branch to A
        Instruction('brt', REG, INT),        # A B    R(A) is True -> branch to B
        Instruction('brf', REG, INT),        # A B    R(A) is False -> branch to B
        Instruction('move', REG, REG),       # A B    R(A) = R(B)
        Instruction('print', REG),           # A      print R(A)
        Instruction('call', FUNC, REG),      # A B    call A, R(B)
        ]

TinyPie VM comes with a `tpvm` command line utility:

    $ bin/tpvm -h
    Usage: tpvm [input file]

    If no input file is provided STDIN is used by default.


    Options:
      -h, --help            show this help message and exit
      -i FILE, --input=FILE
                            Input file. Defaults to standard input.
      -c, --coredump        Print coredump to standard output.
      -d, --disasm          Print disassembled code to standard output.
      -t, --trace           Print execution trace.

Example output:

    fact.tps
    .def fact: args=1, locals=3
        # r1 holds argument 'n'
        loadk r2, 2
        lt r3, r1, r2        # n < 2 ?
        brf r3, cont         # if n >= 2 jump to 'cont'
        loadk r0, 1          # else return 1
        ret
    cont:
        loadk r2, 1          # r2 = 1
        move r3, r1          # r3 = n
        sub r1, r1, r2       # r1 = n - 1
        call fact, r1        # fact(n - 1)
        mul r0, r3, r0       # n = n * result of fact(n - 1)
        ret

    .def main: args=0, locals=1
        loadk r1, 3
        call fact, r1        # fact(3)
        print r0             # 6
        halt

    $ bin/tpvm --coredump --disasm --trace -i /tmp/fact.tps
    0095: LOADK   r1, #4:3         main.registers=[? | ?]              calls=[main]
    0104: CALL    #0:fact@0, r1    main.registers=[? | 3]              calls=[main]
    0000: LOADK   r2, #1:2         fact.registers=[? | 3 | ? ? ?]      calls=[main fact]
    0009: LT      r3, r1, r2       fact.registers=[? | 3 | 2 ? ?]      calls=[main fact]
    0022: BRF     r3, 41           fact.registers=[? | 3 | 2 0 ?]      calls=[main fact]
    0041: LOADK   r2, #2:1         fact.registers=[? | 3 | 2 0 ?]      calls=[main fact]
    0050: MOVE    r3, r1           fact.registers=[? | 3 | 1 0 ?]      calls=[main fact]
    0059: SUB     r1, r1, r2       fact.registers=[? | 3 | 1 3 ?]      calls=[main fact]
    0072: CALL    #0:fact@0, r1    fact.registers=[? | 2 | 1 3 ?]      calls=[main fact]
    0000: LOADK   r2, #1:2         fact.registers=[? | 2 | ? ? ?]      calls=[main fact fact]
    0009: LT      r3, r1, r2       fact.registers=[? | 2 | 2 ? ?]      calls=[main fact fact]
    0022: BRF     r3, 41           fact.registers=[? | 2 | 2 0 ?]      calls=[main fact fact]
    0041: LOADK   r2, #2:1         fact.registers=[? | 2 | 2 0 ?]      calls=[main fact fact]
    0050: MOVE    r3, r1           fact.registers=[? | 2 | 1 0 ?]      calls=[main fact fact]
    0059: SUB     r1, r1, r2       fact.registers=[? | 2 | 1 2 ?]      calls=[main fact fact]
    0072: CALL    #0:fact@0, r1    fact.registers=[? | 1 | 1 2 ?]      calls=[main fact fact]
    0000: LOADK   r2, #1:2         fact.registers=[? | 1 | ? ? ?]      calls=[main fact fact fact]
    0009: LT      r3, r1, r2       fact.registers=[? | 1 | 2 ? ?]      calls=[main fact fact fact]
    0022: BRF     r3, 41           fact.registers=[? | 1 | 2 1 ?]      calls=[main fact fact fact]
    0031: LOADK   r0, #2:1         fact.registers=[? | 1 | 2 1 ?]      calls=[main fact fact fact]
    0040: RET                      fact.registers=[1 | 1 | 2 1 ?]      calls=[main fact fact fact]
    0081: MUL     r0, r3, r0       fact.registers=[1 | 1 | 1 2 ?]      calls=[main fact fact]
    0094: RET                      fact.registers=[2 | 1 | 1 2 ?]      calls=[main fact fact]
    0081: MUL     r0, r3, r0       fact.registers=[2 | 2 | 1 3 ?]      calls=[main fact]
    0094: RET                      fact.registers=[6 | 2 | 1 3 ?]      calls=[main fact]
    0113: PRINT   r0               main.registers=[6 | 3]              calls=[main]
    6
    Constant pool:
    0000: <FunctionSymbol: name='fact', address=0, args=1, locals=3>
    0001: 2
    0002: 1
    0003: <FunctionSymbol: name='main', address=95, args=0, locals=1>
    0004: 3

    Code memory:
    0000:   6   0   0   0   2   0   0   0
    0008:   1   4   0   0   0   3   0   0
    0016:   0   1   0   0   0   2  13   0
    0024:   0   0   3   0   0   0  41   6
    0032:   0   0   0   0   0   0   0   2
    0040:   9   6   0   0   0   2   0   0
    0048:   0   2  14   0   0   0   3   0
    0056:   0   0   1   2   0   0   0   1
    0064:   0   0   0   1   0   0   0   2
    0072:  16   0   0   0   0   0   0   0
    0080:   1   3   0   0   0   0   0   0
    0088:   0   3   0   0   0   0   9   6
    0096:   0   0   0   1   0   0   0   4
    0104:  16   0   0   0   0   0   0   0
    0112:   1  15   0   0   0   0  10

    Disassembly:
    0000: LOADK   r2, #1:2
    0009: LT      r3, r1, r2
    0022: BRF     r3, 41
    0031: LOADK   r0, #2:1
    0040: RET
    0041: LOADK   r2, #2:1
    0050: MOVE    r3, r1
    0059: SUB     r1, r1, r2
    0072: CALL    #0:fact@0, r1
    0081: MUL     r0, r3, r0
    0094: RET
    0095: LOADK   r1, #4:3
    0104: CALL    #0:fact@0, r1
    0113: PRINT   r0
    0118: HALT



=======
CHANGES
=======

0.2 (2011-03-03)
----------------

- Added Bytecode Assembler
- Added Register-Based Virtual Machine

0.1 (initial release)
---------------------

- Initial release of TinyPie interpreter