Expression trees and evaluation

From sygnm
Jump to: navigation, search

Expression trees and evaluation context

The central data structure of the sygnm framework is the expression tree. Every tree represents a mathematical expression. Expression trees are built from sygnm nodes (which can be data types, functions or dynamic nodes). The children of a node are the current function parameters of the node (usually only function nodes and dynamic nodes have children in a tree).

Expression trees can be created from a string by a parser object or built programatically using the sygnm API.

The nodes of a tree are the function, data type or dynamic node objects themselves, which means that every such object can be viewed as a tree with a single node. This also means that in the sygnm framework, every mathematical function takes expression trees as arguments and returns an expression tree.

Every node of a tree possesses an evaluation context, which is an object storing key-value pairs. The evaluation context objects in an expression tree also form a tree, which is always rooted in the global evaluation context. The purpose of evaluation context objects is to set arbitrary properties for subtrees. This means that any sygnm function which is being executed can query the current evaluation context for keys. If a key is not found in the context of the currently running function, the query traverses the tree moving up until the key is found or the global evaluation context is reached. A typical application of evaluation contexts is to set the precision of numerical evaluation (in bits) for a subtree.

Evaluation of expression trees

The evaluation of expression trees is done by the tree evaluator found in sygnm core. The evaluator is implemented as a simple tree-walking interpreter with some extensions. The process of evaluation is roughly the following:

  1. The evaluator is called with an expression tree.
  2. Tree transformations[1] run on the whole tree before start of evaluation.
  3. The tree is evaluated: the evaluator recursively descends the tree.
    • Data types are returned as-is, functions are called and their results returned.
    • let-expressions (including user defined functions) and if-expressions are evaluated the usual way.
    • call-expressions and dynamic nodes are evaluated using function overload resolution: the function implementation which best matches the actual parameters is called (see Objects, types and function overloading for details).
  4. Tree transformations run on the result of the evaluation before it is returned to the caller.

The evaluator also has many other features, some of which are:

  • Custom evaluation context for every instance of the evaluator
  • Time limit
  • Automatic parallelization of expression evaluation
  • Storing evaluation history, recalling previous results

It is also possible to control the flow of evaluation through special object attributes. Currently setting the "hold" attribute causes the evaluator to skip the node and all its children, which makes it possible to pass entire unevaluated subtrees to functions.

The result of expression tree evaluation only[2] depends on the evaluated expression tree, the evaluation context and the value of some configuration options (e.g. loaded packages).

Runtime overloaded function resolution

Usually functions are only represtend by their names in an expression tree, which is not enough to uniquely determine a function implementation when there are many functions with the same name. In this case, the evaluator looks at the current parameter list and finds all matching implementations, then calls the best match. If no suitable function is found (even with automatic type conversion) or there are multiple functions with the exact same match score (rare) then the evaluator does nothing and leaves the function call as-is. The details of function overload resolution are found in Objects, types and function overloading.

If the evaluation of the best candidate early-fails (see next section) then the next best candidate is used and so on.

Function overload resolution is completely deterministic, its result depends on the loaded packages, configuration and evaluation context.

Error handling and side effects

sygnm functions handle errors by throwing exceptions containing error objects which describe what error happened. These exceptions are caught and handled by either the evaluator or the caller of the function (if the throwing function is called directly and not while evaluating an expression tree).

It is also possible to do additional checks on the arguments at the start of a function and return a special early-fail value. If such a value is encountered, the evaluator continoues execution with the next best matching function. This is useful to place additional restrictions on the input of a function which can't be expressed in the parameter list.

sygnm functions should be pure (i.e. should not have any side effects). This is assumed by the evaluator and functions with side effects (while not forbidden) can lead to unexpected behavior during evaluation. The assumed lack of side effects confirms to the mathematical viewpoint and also enables several optimizations.

  1. ^  Tree transformations are special functions which can run either at the beginning or end of evaluation and are given the whole expression tree as input. A typical use case is automatic simplification of mathematical expressions.
  2. ^  Assuming all called functions are pure (lack side effects).