3.3 The Yacas kernel functionality 

The kernel provides three basic data types: numbers, strings, and atoms, and two container types: list and static array (for speed). Atoms are implemented as strings that can be assigned values and evaluated. Boolean values are simply atoms True and False. Numbers are represented by objects on which arithmetic can be performed immediately. Expression trees, association (hash) tables, stacks, and closures (pure functions) are all implemented using nested lists. In addition, more data types can be provided by plugins. Kernel primitives are available for arbitrary-precision arithmetic, string manipulation, array and list access and manipulation, for basic control flow, for assigning variables (atoms) and for defining rules for functions (atoms with a function syntax).

The interpreter engine recursively evaluates expression trees according to user-defined transformation rules from the script library. Evaluation proceeds bottom-up, that is, for each function term, the arguments are evaluated first and then the function is applied to these values.

A HoldArg() primitive is provided to not evaluate certain arguments of certain functions before passing them on as parameters to these functions. The Hold() and Eval() primitives, similarly to LISP's QUOTE and EVAL, can be used to stop the recursive application of rules at a certain point and obtain an unevaluated expression, or to initiate evaluation of an expression which was previously held unevaluated.

When an expression can not be transformed any further, that is, when no more rules apply to it, the expression is returned unevaluated. For instance, a variable that is not assigned a value will return unevaluated. This is a desired behavior in a symbolic manipulation system. Evaluation is treated as a form of "simplification", in that evaluating an expression returns a simplified form of the input expression.

Rules are matched by a pattern expression which can contain pattern variables, i.e. atoms marked by the "_" operator. During matching, each pattern variable atom becomes a local variable and is tentatively assigned the subexpression being matched. For example, the pattern _x + _y can match an expression a*x+b and then the pattern variable x will be assigned the value a*x (unevaluated) and the variable y will have the value b.

This type of semantic matching has been frequently implemented before in various term rewriting systems (see, e.g., [C86]). However, the Y language offers its users an ability to create a much more flexible and powerful term rewriting system than one based on a fixed set of rules. Here are some of the features:

First, transformation rules in Y have predicates that control whether a rule should be applied to an expression. Predicates can be any Y expressions that evaluate to the atoms True or False and are typically functions of pattern variables. A predicate could check the types or values of certain subexpressions of the matching context (see the _x ^_y example in the previous subsection).

Second, rules are assigned a precedence value (a positive integer) that controls the order of rules to be attempted. Thus Y provides somewhat better control over the automatic recursion than the pattern-matching system of Mathematica which does not allow for rule precedence. The interpreter will first apply the rule that matches the argument pattern, for which the predicate returns True, and which has the least precedence.

Third, new rules can be defined dynamically as a side-effect of evaluation. This means that there is no predefined "ranking alphabet" of "ground terms" (in the terminology of [TATA99]), in other words, no fixed set of functions with predefined arities. It is also possible to define a "rule closure" that defines rules depending on its arguments, or to erase rules. Thus, a Y script library (although it is read-only) does not represent a fixed tree rewriting automaton. An implementation of machine learning is possible in Y (among other things). For example, when the module wordproblems.ys (mentioned in the previous subsection) "learns" from the user input that apple is a countable object, it defines a new postfix operator apples and a rule for its evaluation, so the expression 3 apples is later parsed as a function apples(3) and evaluated according to the rule.

Fourth, Y expressions can be "tagged" (assigned a "property object" a la LISP) and tags can be checked by predicates in rules or used in the evaluation.

Fifth, the scope of variables can be controlled. In addition to having its own local variables, a function can be allowed to access local variables of its calling environment (the UnFence() primitive). It is also possible to encapsulate a group of variables and functions into a "module", making some of them inaccessible from the outside (the LocalSymbols() primitive). The scoping of variables is a "policy decision", to be enforced by the script which defines the function. This flexibility is by design and allows to easily modify the behavior of the interpreter, effectively changing the language as needed.