ExprRules.jl

This is the base package to support the generation and optimization of Julia expressions from a grammar. The package contains many basic functions for declaring and working with grammars and expression trees.

Installation

Pkg.add("ExprRules")

Once it's installed, start using the package by calling:

In [1]:
using ExprRules

Usage

Define a grammar

Grammars are specified by production rules that specify substitutions of non-terminal symbols. Each production rule is an equality with a non-terminal on the left side and a Julia expression on the right side.

The _() syntax is a special function where the argument is evaluated at the time of derivation tree's construction and the value is held constant throughout the life of the tree. The pipe (|) syntax is a short-hand that allows the user to define multiple production rules on a single line (i.e., Backus-Naur Form). The |() syntax is another similar short-hand that takes a collection as argument and creates a production rule for each element in the collection.

In [2]:
grammar = @grammar begin
    Real = x                      # symbol
    Real = Real * Real            # julia expression
    Real = f(Real)                # function call
    Real = _(Base.rand(1.0:5.0))  # special syntax, eval argument of _() at derivation time
    Real = A | B | cos(Real)        # multiple rules on a single line
    Real = 1 | 2 | 3
    Real = |(4:6)                 # same as Real = 4 | 5 | 6
    Real = |([7,8,9])             # same as Real = 7 | 8 | 9 
end
Out[2]:
1: Real = x
2: Real = Real * Real
3: Real = f(Real)
4: Real = _(Base.rand(1.0:5.0))
5: Real = A
6: Real = B
7: Real = cos(Real)
8: Real = 1
9: Real = 2
10: Real = 3
11: Real = 4
12: Real = 5
13: Real = 6
14: Real = 7
15: Real = 8
16: Real = 9
In [3]:
f(x) = 2x
Out[3]:
f (generic function with 1 method)

Grammar helper functions

List non-terminals of the grammar:

In [4]:
nonterminals(grammar)
Out[4]:
1-element Array{Symbol,1}:
 :Real

Grammars are indexed by non-terminal symbols and return the corresponding production rule numbers with that nonterminal.

In [5]:
grammar[:Real]
Out[5]:
16-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16

Get the return type of the first production rule:

In [6]:
return_type(grammar, 1)
Out[6]:
:Real

Get the number of children of the second production rule:

In [7]:
nchildren(grammar, 2)
Out[7]:
2

Get the child types of the second production rule:

In [8]:
child_types(grammar, 2)
Out[8]:
2-element Array{Symbol,1}:
 :Real
 :Real

Get the maximum number of children (arity) of the grammar:

In [9]:
max_arity(grammar)
Out[9]:
2

Determine if the third production rule is terminal:

In [10]:
isterminal(grammar, 3)
Out[10]:
false

Determine if the fourth production rule is a special _() function:

In [11]:
iseval(grammar, 4)
Out[11]:
true

Expression trees

An expression tree represents the derivation of an expression as a tree. The nodes in an expression tree contain an index to a production rule.

Define an expression tree manually:

In [ ]:
rulenode = RuleNode(3, [RuleNode(6)])
display(rulenode, grammar)

Generate a random expression tree from the grammar:

In [ ]:
using Random
In [ ]:
Random.seed!(138)
rulenode = rand(RuleNode, grammar, :Real, 10)
display(rulenode, grammar)

Evaluate the expression defined by the expression tree:

In [ ]:
x=0.5
Core.eval(rulenode, grammar)

Get the executable Julia expression from an expression tree:

In [ ]:
ex = get_executable(rulenode, grammar)

Rather than using Julia's built-in eval function, a much more performant way of evaluating an expression is to use ExprRule's interpreter by providing a custom symbol table. SymbolTable can try to automatically populate the symbol table by analyzing the grammar. Symbols corresponding to input variables should be provided at on-the-fly. Benchmarking suggests that using the custom interpreter can yield up to 20x performance improvement.

In [ ]:
S = SymbolTable(grammar)
S[:x] = 5
Core.eval(S, ex)

Sample a random node in the tree:

In [ ]:
Random.seed!(0)
sample(rulenode)

Sample a random node of type :Real in the expression tree:

In [ ]:
Random.seed!(3)
sample(rulenode, :Real, grammar)

Sample a random node in the tree and store the location in a NodeLoc object:

In [ ]:
Random.seed!(1)
loc = sample(NodeLoc, rulenode)

Retrieve the node pointed to by the NodeLoc object:

In [ ]:
get(rulenode, loc)

Replace the subtree pointed to by loc with a randomly generated subtree:

In [ ]:
Random.seed!(28)
insert!(rulenode, loc, rand(RuleNode, grammar, :Real, 3))
display(rulenode, grammar)

Minimum Depth Map

Compute the minimum depth of all possible subtrees for each production rule:

In [ ]:
dmap = mindepth_map(grammar)

Compute the minimum depth of all possible subtrees starting from a given start symbol:

In [ ]:
mindepth(grammar, :Real, dmap) #zero for terminals

Expression Iterator

Iterate over all possible expressions of a grammar up to depth 2:

In [ ]:
grammar = @grammar begin
    Real = Real + Real
    Real = 1 | 2
end
iter = ExpressionIterator(grammar, 2, :Real)
collect(iter)

Count the number of expressions of a grammar up to depth 2:

In [ ]:
count_expressions(grammar, 2, :Real)

AbstractTrees.jl Interface

In [ ]:
using AbstractTrees

Print RuleNode tree in textual format. Leaf nodes are the rule numbers in the grammar.

In [ ]:
tree = RuleNode(1, [RuleNode(2), RuleNode(1, [RuleNode(2), RuleNode(3)])])
print_tree(tree)
In [ ]: