Implementation

MOA Compiler Steps

Every effort has been made to restrict the data structures and algorithms used in the implementation. For this work only tuples(namedtuples), dictionaries, and enums have been used. All of which map to low level data structures. Parts of MOA that are not involved directly with compilation may use more complex structures to appear pythonic.

python-moa is both a numeric and symbolic compiler. It is numeric whenever possible and resorts to symbolic expressions only when the value is not known at compile time. Examples of when python-moa must be symbolic is when the shape of an array is not known \(\shape A = \vcc2n\). All unknown symbols are represented as scalar arrays for example the array A above would be represented in the symbol table as follows. This means that once a value becomes symbolic it is inside a nested tuple structure. Allowing it to become compatible with the internal representation.

symbol_table = {
   'A': ast.SymbolNode(ast.NodeSymbol.ARRAY, (2, ast.Node((ast.NodeSymbol.ARRAY,), (), ('n',), ())), None, None)),
   'n': ast.SymbolNode(ast.NodeSymbol.ARRAY, (), None, None)
}

Everything in MOA has a shape. Everything. Scalars, vectors, n-dimensional arrays, operations on arrays, and even functions. Thus shape are included with each node in the abstract syntax tree.

Symbol Table

A symbol table is used to keep track of all arrays in the abstract syntax tree.

symbol_table = {
   'A': ast.SymbolNode(ast.NodeSymbol.ARRAY, (2, 3), (1, 2, 3, 4, 5, 6)),
   '_i1': ast.SymbolNode(ast.NodeSymbol.INDEX, (), (0, 5, 1),
   '_a2': ast.SymbolNode(ast.NodeSymbol.ARRAY, (2,), (1, ast.Node((NodeSymbol.ARRAY,), (), ('_i1',), ())))
}

At this present moment not much work is done to garbage collect the tree as reductions take place.

Abstract Syntax Tree

The abstract syntax tree takes inspiration from lisp where each node is a tuple with the first node determining the node_type by an enum. There are three main types of nodes for the frontend. These types are array, unary operation, and binary operation. Originally plain tuples were used to represent the nodes however this lead to ugly node[2][1] syntax. Using namedtuples allowed a similar experience with node.right_node.shape. The abstract syntax tree is heavily tied to the symbol table.

For example the following moa expression \(\vc0 \psi \transpose (A + B)\) can be represented with the following symbol table and ast.

Array

Tuple representation ArrayNode(type, shape, name, value)

Create array named A with shape (1, 3) values (1, 2, 3)

Create array without name and unknown values

Unary Operation

Unary representation UnaryNode(type, shape, right_node)

Available unary operations: PLUSRED, MINUSRED, TIMESRED, DIVIDERED, IOTA, DIM, TAU, SHAPE, RAV, TRANSPOSE.

Binary Operation

Binary representation BinaryNode(type, shape, left_node, right_node)

Available binary operations: PLUS, MINUS, TIMES, DIVIDE, PSI, TAKE, DROP, CAT, TRANSPOSEV.

Symbol Table

More work need to be done on unknown shape fixed dimension before writing.

Shape Calculation

Shape calculation can be done with a single pass post-order traversal (left, right, root) node.

How shapes are calculated for given types.

Array

For now the shape of an array is required to be defined on the node and cannot be computed from another value. Thus the second argument (shape) cannot be None.

ArrayNode(MOANodeTypes.ARRAY, (2, 3), None, None))

Transpose

Transpose has two forms a unary and binary definition.

\[\transpose A = (\reverse \iota \dims A) \transpose A\]

For the simple case of the unary operator.

Reduction

Reduction can be done with a single pass pre-order traversal with multiple replacements on each node (root, left, right) node. These replacements have the Church-Rosser property meaning that when applying reductions the ordering of the replacements does not change the final result.