typefn: 013 - AST: Basic Evaluation

013-ast-basic-evaluation.md

Previously, the AST node creation functions were discussed, in which a set of basic functions where defined which take varying amounts of TreeNode inputs and return a specially typed TreeNode sub-type output. These functions directly create POJO realizations of the typings described in TypeScript. In a standard, object-oriented approach to developing an AST, evaluation of these nodes would be either baked into a per-object-class evaluate method, or offloaded and centralized to a series of (potentially interconnected) Visitor patterns.

Recalling that part of the spec for this AST series is that "[...]these expressions [should] be capable of being evaluated to a singular numeric value[...]", it is insufficient to simply encode a series of nested operations as a tree and return that to whatever operational context made the request; these trees need to be evaluated! (In addition, again to spec, they need to be algebraically simplified, where appropriate.)

As a concession to the limited capability of TypeScript to describe algebraic data types (ADTs) after transpilation, POJOs (or Plain Old JavaScript Objects) are used to specify structured data. However, these objects are used purely for structural purposes: their underlying prototypes—what other languages might consider their class or even static/meta class—are not altered nor augmented. All operations performed on these typed POJOs is performed functionally.

This suggests that providing an evaluate method—certainly feasible in OOP-flavored TypeScript—is out, as doing so breaks the POJO prototype. Visitors could be used, but are typically implemented via objects, so would again break one of the underlying desires of writing this system: functional design.

So, why not provide an evaluate function, which takes an AST TreeNode and, through use of recursion, figures out what the result of the operations so encoded is? Recall that the spec mentions variables, and, as a general principle, the idea of algebraic/syntactic simplification. This suggests that structured rules for different configurations of sub-trees would need to be considered to make semantically equivalent substitutions. And there are a distressingly large number of rules, especially for arithmetic operations. Bundling all of that in a single, centralized context is muddy.

While not perfectly ideal—as pure representation of unevaluated operations is not readily available, and interstitial sub-calculations are burdensome to isolate and consider—a reasonable tradeoff would be a sort of in situ evaluation, wherein each node creation function codifies rules for evaluating sub-trees interrelated to the operation being represented. That is, for example, the add function would encode rules for simplifying trees whenever it is invoked, specifically looking at logic related to addition. Similarly for all other supported operations.

This is non-trivial to implement—again, there are many rules, and the exact space of all potential children a given node might have to separately consider can scale above P(n, c), where P is the permutation function, and n is the total number of TreeNode sub-types that the system supports, and c is the number of children a given node has. A given binary operation for a robustly sized system (at least, say, 40 different node types) could have well over P(40, 2) =~ 1500 different children permutations, each of which could have unique results.

Still, consider that most degenerate of cases: simple numeric evaluation. If all operations are solvable—even if evaluated to NaN—as a numeric at the point of evaluation, that implies that the data leaf-nodes within the tree are, themselves, either numeric or semantically equivalent ot a numeric. In considering just the former, it becomes obvious that, at the very least, the previously defined creation functions must be augmented with codifications of the operations they represent. The attached source for this article presents one potential solution to providing that behavior, but other alternatives will be made more apparent as this series develops.

The next article in this series will be a slight break from ASTs to consider a methodology that can help develop the behavior this article would like to provide some solution to.

013-ast-basic-evaluation.ts

import {
  TreeNode, Nullary, Unary, Binary,
  Absolute, Factorial, Addition, Multiplication, Numeric
} from './ast-tree'
import {
  isNumeric
} from './ast-guards'

// `treeNode`, `nullary`, and `numeric` all remain unaltered from the
// previous article, but are defined here for consistency.
const treeNode = <T extends TreeNode>(
  arity: string, species: string, fields: {}
) =>
  ({
    about: {arity, species},
    ...fields
  }) as T

export const nullary = <
  Params extends any[],
  Fields extends {},
  T extends Nullary & {readonly raw: Fields},
>(species: string, convert: (...raw: Params) => Fields) =>
  (...raw: Params) =>
    treeNode<T>('nullary', species, {raw: convert(...raw)})

export const numeric = nullary<[number, number], {a: number, b: number}, Numeric>(
  'numeric', (a, b) => ({a, b})
)    

// `unary` is altered in two ways:
// 1) the HOF takes a callback, `whenNNumeric`, which is invoked with the
//  child of the Unary when that child isNumeric; this callback returns a
//  Numeric.
// 2) the generated closure will return either a `Numeric` or a `T`, depending
//  upon whether `isNumeric(child)` is true or not.
export const unary = <T extends Unary>(
  species: string, whenNumeric: (child: Numeric) => Numeric
) =>
  (child: TreeNode) =>
    isNumeric(child) 
      ? whenNumeric(child) 
      : treeNode<T>('unary', species, {child})

// The alterations to `binary` are similar to those to `unary`:
// 1) it also receives a callback as part of invoking the HOF, this time with
//  two Numeric parameters producing a Numeric
// 2) the previous callback will only be invoked should both the left and
//  right children be Numeric. Otherwise, generate the binary node 
//  representation.
export const binary = <T extends Binary>(
  species: string, whenNumeric: (left: Numeric, right: Numeric) => Numeric
) =>
  (left: TreeNode, right: TreeNode) =>
    isNumeric(left) && isNumeric(right)
      ? whenNumeric(left, right)
      : treeNode<T>('binary', species, {left, right})
     
// `absolute` changes with the addition of its callback; as Numeric stores
// complex number pairs, the absolute value of a complex will be defined as
// the magnitude of the pair treated as a vector. This also yields the
// appropriate value for real-valued Numerics.
export const absolute = unary<Absolute>(
  'absolute', c => numeric(Math.hypot(c.raw.a, c.raw.b), 0)
)

// `add` gets a callback, which is the vector addition of two complex numbers;
// note that when both children are real, their `b` is 0, so this is correct for
// real-values. 
export const add = binary<Addition>(
  'addition', (l, r) => numeric(l.raw.a + r.raw.a, l.raw.b + r.raw.b)
)

// `multiply` gets a callback for calculating the multiplication of two
// complex numbers. This derives from the distributive and commutative 
// properties wrt multiplying (l.a + l.b*i) * (r.a + r.b*i), and the fact
// that (i**2) === -1.
// Note that when both of the numbers' `b` components are 0, this devolves
// to straight real multiplication.
export const multiply = binary<Multiplication>(
  'multiplication', (l, r) => numeric(
    (l.raw.a * r.raw.a) - (l.raw.b * r.raw.b),
    (l.raw.a * r.raw.b) + (l.raw.b * r.raw.a)
  )
)

// Note that the implementation os `factorial` is non-trivial at this stage,
// especially wrt complex numbers. A real-only approximation could be provided, 
// but runs afoul of certain typing issues that the above modifications are
// currently side-stepping. `factorial` will be revisited in a future article.

013-ast-guards.ts

import { 
  TreeNode, Nullary, Unary, Binary,
  Numeric, Bool, Absolute, Factorial, Addition, Multiplication
} from './ast-tree'

export type TreeNodeGuardFn<T extends TreeNode> =
  (value: TreeNode) => value is T

export const isArity = <T extends TreeNode>(arity: string): TreeNodeGuardFn<T> =>
  (value): value is T => value.about.arity === arity

export const isSpecies = <T extends TreeNode>(species: string): TreeNodeGuardFn<T> =>
  (value): value is T => value.about.species === species

export const isSpeciesAlt = <T extends TreeNode>(
  species: string, fields: string[]
): TreeNodeGuardFn<T> =>
  (value): value is T => value.about.species === species 
    && fields.every(field => field in value)

export const isNullary = isArity<Nullary>('nullary')
export const isUnary = isArity<Unary>('unary')
export const isBinary = isArity<Binary>('binary')  

export const isNumeric = isSpecies<Numeric>('numeric')
export const isBool = isSpecies<Bool>('boolean')

export const isAbsolute = isSpecies<Absolute>('absolute')
export const isFactorial = isSpecies<Factorial>('factorial')

export const isAddition = isSpecies<Addition>('addition')
export const isMultiplication = isSpecies<Multiplication>('multiplication')

export const isAdditionAlt = isSpeciesAlt<Addition>('addition', ['left', 'right'])

013-ast-tree.ts

export type Categorization = {
  readonly arity: string
  readonly species: string
}

export type TreeNode = {
  readonly about: Categorization
}

export type ExtendTreeNode<Arity extends string, Fields extends {}> = TreeNode & {
  readonly about: {readonly arity: Arity}
} & Readonly<Fields>

export type FromExtendedTreeNode<Base extends TreeNode, Species extends string> = Base & {
  readonly about: {readonly species: Species}
}

export type Nullary = ExtendTreeNode<'nullary', {raw: unknown}>
export type FromNullary<Species extends string, Raw extends {}> = 
  FromExtendedTreeNode<Nullary, Species> & {
    readonly raw: Readonly<Raw>
  }

export type Numeric = FromNullary<'numeric', {a: number, b: number}>
export type Bool = FromNullary<'boolean', {value: boolean}>

export type Unary = ExtendTreeNode<'unary', {child: TreeNode}>
export type FromUnary<Species extends string> = FromExtendedTreeNode<Unary, Species>

export type Absolute = FromUnary<'absolute'>
export type Factorial = FromUnary<'factorial'>

export type Binary = ExtendTreeNode<'binary', {left: TreeNode, right: TreeNode}>
export type FromBinary<Species extends string> = FromExtendedTreeNode<Binary, Species>

export type Addition = FromBinary<'addition'>
export type Multiplication = FromBinary<'multiplication'>