A simple Julia package for representing and evaluating expression-like trees. Each vertex of the tree may contain:

A constant: an arbitrary Julia value that is assumed not to depend on any variables. A leaf vertex.
A variable: a wrapper around a symbol, used for binding a value to some vertices of the tree after the tree's construction. A leaf vertex.
A tree. A non-leaf vertex.

Each non-leaf vertex contains a salient value and a collection. The former is interpreted as an operation, while the latter is at the same time interpreted as the child vertices of the tree and as the arguments of the operation. An expression is evaluated by calling the operation.

To evaluate an expression, a value must be provided for each variable.

Partial evaluation is accomplished using the expression_map_matched function, see below.

The implementations

Constants:

DynamicConstant: stores an arbitrary value
StaticConstant: stores an arbitrary value in the type domain

Variables:

DynamicVariable: stores a symbol
StaticVariable: stores a symbol in the type domain

Expression trees:

DynamicExpression: a recursive data structure storing an operation and its arguments. The operation is stored as an object exposing several possible operations as properties, and a symbol that selects one of the available operations.
StaticExpression: a recursive data structure storing an operation and its arguments.
MoreStaticExpression: a recursive data structure storing an operation and its arguments. The operation is stored in the type domain.

Dynamic* and *Static* implementation variants are always interchangeable, except that StaticConstant may not wrap values that Julia doesn't allow moving to the type domain. It's possible to mix-and-match Dynamic* and *Static* arbitrarily.

NB: if the terms type domain or type stability are not clear, just use the Dynamic* version of each implementation. In some cases it will make sense to partially switch to a *Static* implementation as a performance optimization.

Type aliases

The ExpressionTypeAliases module exports some type aliases that might be useful:

julia> using CallableExpressions

julia> ExpressionTypeAliases.Constant
Union{DynamicConstant, StaticConstant}

julia> ExpressionTypeAliases.Variable
Union{DynamicVariable, StaticVariable}

julia> ExpressionTypeAliases.Expression
Union{DynamicExpression, MoreStaticExpression, StaticExpression}

julia> ExpressionTypeAliases.ExpressionLoosely
Union{DynamicVariable, DynamicConstant, DynamicExpression, MoreStaticExpression, StaticConstant, StaticExpression, StaticVariable}

Usage example

Represent (x, y) -> y*sind(x - 5) as an expression and evaluate it with x set to 17.9 and y set to 2:

julia> using CallableExpressions

julia> x = DynamicVariable(:x)
DynamicVariable(:x)

julia> y = StaticVariable{:y}()
StaticVariable{:y}()

julia> c5 = DynamicConstant(5)
DynamicConstant{Int64}(5)

julia> subtraction = StaticExpression((x, c5), -)
StaticExpression{Tuple{DynamicVariable, DynamicConstant{Int64}}, typeof(-)}((DynamicVariable(:x), DynamicConstant{Int64}(5)), -)

julia> trig = DynamicExpression((subtraction,), :sind, (; sind = sind));  # in practice there would be more ops in the named tuple

julia> multiplication = MoreStaticExpression{<:Any,*}((y, trig));

julia> var_vals = (; x = 17.9, y = 2)  # `NamedTuple` isn't mandatory, anything with `getproperty` should work
(x = 17.9, y = 2)

julia> multiplication(var_vals) === ((x, y) -> y*sind(x - 5))(var_vals.x, var_vals.y)
true

Pretty printing and display using AbstractTrees.jl

The expressions here implement the AbstractTrees.jl interface. This allows pretty-printing using AbstractTrees.print_tree. Some other packages, like D3Trees.jl , build on the AbstractTrees.jl interface, providing graphic display capabilities.

TermInterface.jl support

A package extension for TermInterface.jl support is provided. It should enable interfacing with packages like SymbolicUtils.jl or Metatheory.jl.

Here's a small example of using the SymbolicUtils.jl rewriting functionality to rewrite e + e into 2 * e:

julia> using CallableExpressions, SymbolicUtils, AbstractTrees

julia> e0 = DynamicVariable(:x);

julia> e1 = StaticExpression((e0, e0), +);

julia> print_tree(e1)
+
├─ DynamicVariable(:x)
└─ DynamicVariable(:x)

julia> r = @rule (~x + ~x) => StaticExpression((DynamicConstant(2), ~x), *)
~x + ~x => StaticExpression((DynamicConstant(2), ~x), *)

julia> print_tree(r(e1))
*
├─ DynamicConstant{Int64}(2)
└─ DynamicVariable(:x)

Functionality

`Base` interfaces: equality and hashing

We have, e.g., DynamicVariable(:x) == StaticVariable{:x}().

`Base` interfaces: conversion and promotion

In some cases it's possible to promote and convert between the different implementations:

julia> using CallableExpressions

julia> promote_type(StaticVariable{:x}, StaticVariable{:y})
DynamicVariable

julia> promote_type(StaticVariable{:x}, DynamicVariable)
DynamicVariable

julia> promote_type(StaticConstant{3}, StaticConstant{7})
DynamicConstant{Int64}

julia> promote_type(StaticConstant{3}, DynamicConstant{Int})
DynamicConstant{Int64}

julia> promote_type(StaticConstant{3}, DynamicConstant{Float64})
DynamicConstant{Float64}

julia> promote_type(DynamicConstant{Int}, DynamicConstant{Float64})
DynamicConstant{Float64}

julia> convert(StaticVariable, DynamicVariable(:x))
StaticVariable{:x}()

`expression_is_constant`

Use expression_is_constant(expr)::Bool to tell whether expr is constant, in the sense of not depending on any variables.

`expression_map_matched`

The expression_map_matched function allows functionality such as constant folding or substitution:

julia> using CallableExpressions, AbstractTrees

julia> multiplication = ...  # as above

julia> print_tree(multiplication)
*
├─ StaticVariable{:y}()
└─ sind
   └─ -
      ├─ DynamicVariable(:x)
      └─ DynamicConstant{Int64}(5)

julia> match_x = isequal(StaticVariable{:x}())
(::Base.Fix2{typeof(isequal), StaticVariable{:x}}) (generic function with 1 method)

julia> mult2 = expression_map_matched(match_x, (_ -> DynamicConstant(0.1)), multiplication);

julia> print_tree(mult2)
*
├─ StaticVariable{:y}()
└─ sind
   └─ -
      ├─ DynamicConstant{Float64}(0.1)
      └─ DynamicConstant{Int64}(5)

julia> mult3 = expression_map_matched(expression_is_constant, (e -> DynamicConstant(e((;)))), mult2);

julia> print_tree(mult3)
*
├─ StaticVariable{:y}()
└─ DynamicConstant{Float64}(-0.0854169)

`expression_into_type_domain`

The expression_into_type_domain function tries to move expressions wholly into the type domain:

julia> using CallableExpressions

julia> expr = DynamicExpression((DynamicVariable(:x), DynamicConstant(3)), :op, (; op = +));

julia> Base.issingletontype(typeof(expr))
false

julia> of_singleton_type = expression_into_type_domain(expr);

julia> Base.issingletontype(typeof(of_singleton_type))
true

julia> expr == of_singleton_type
true

It throws when Julia isn't able to use a relevant value as a type parameter.

Designed to preserve the singleton type property when possible

julia> using CallableExpressions

julia> e = StaticExpression(
           (
               StaticVariable{:x}(),
               StaticConstant{7}(),
           ),
           +,
       )
StaticExpression{Tuple{StaticVariable{:x}, StaticConstant{7}}, typeof(+)}((StaticVariable{:x}(), StaticConstant{7}()), +)

julia> Base.issingletontype(typeof(e))
true

CallableExpressions

JuliaHub links

About