typefn: 012 - AST: Node Creation

012-ast-node-creation.md

Being able to describe—and thus, constrain—the type structure of different nodes within an Abstract Syntax Tree is all well and good, but would ultimately be not particularly useful if one had to manually write out the structure of any given node by hand. This would be especially more cumbersome for complicated interactions between nodes, such as when multiple nodes are added together.

This suggests that a set of type-specific functions which generate objects which adhere to the AST node types the functions represent would be ideal. Thus, having functions like add to create Addition nodes and numeric to create Numeric nodes. These functions should take, as parameters, only those details necessary to create their node representations; all other necessary details, such as their Categorization data, should be automatically added into the objects they generate by the functions themselves.

This, however, would lead to a lot of redundant, repetitious code, where the body of each of these functions replicates much of the same behavior all throughout the code base. Worse, this limits the opportunity to abstract certain behaviors, such as logic unique to common base types. (For example, consider silent type-casting of Bool instances to Numeric instances when performing an addition of a boolean and a numeric. Ideally, this wouldn't be behavior that is operation dependent, but could be abstracted out of Binary contexts.)

As has been showcased in previous articles within this series, such as in the discussion of Generic Tupled Rest Parameters, it is certainly possible to abstract behavior behind additional layers of higher order functions. One should be careful, however: while HOFs are great for making parameterized behavior, too much abstraction can lead to code which is less clear. Complexity for complexity's sake is likely to lead to maintenance nightmares down the line.

In this particular domain, while certain commonality exists between Nullary, Unary, and Binary, they all have downstream unique behaviors which, for the moment, should give a certain degree of pause on leaping immediately to a generic treeNode HOF which would generate HOFs for each type. Presented in the code for this article is a separate methodology, wherein a treeNode function exists for standardizing the construction of TreeNode objects, which is then used by structurally separate HOFs for each of the three direct sub-types.

However, this does lead to an interesting observation: as far as the currently discussed implementation of the spec presented in the overview, there really isn't any direct difference between an Addition node and a Multiplication node other than their respective species sub-field. Those could be safely abstracted behind a HOF. A similar argument exists for Unary sub-types. While future additions to the system will raise reasonable questions about this current assumption, it is nevertheless a safe direction in which to take the code.

The attached source suggests one approach for describing these interrelated functions, and also provides some sample use of the resulting closures. As should hopefully bb obvious, and building off of the conclusion of the discussion about AST specific type guards, the goal in designing much of the functionality of this domain is easy, clean downstream code.

012-ast-node-creation.ts

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

// As a motivational example of how redundancy and repetition can be
// obviated, consider the following example, loosely built around the
// AST TreeNode structure. The type presented in manual long-form, here,
// describes a concrete binary node. After that, a function is defined
// which will generate instances of these nodes whenever invoked. Note
// how, in order to satisfy the type constraints on the `about` field,
// `example` needs to specifically define string values for the sub-fields.
// Every function which attempts to create binary-style nodes would look
// similar, thus making for a lot of repeated logic. There doesn't exist
// any room in this design for abstracting out common behavior or adding
// extra capabilities.
type ExampleBinaryNode = {
  readonly about: {
    readonly arity: 'binary'
    readonly species: 'example'
  }
  readonly left: TreeNode
  readonly right: TreeNode
}

const example = (left: TreeNode, right: TreeNode): ExampleBinaryNode => ({
  about: {arity: 'binary', species: 'example'},
  left, right
})

// First, a utility function which standardizes the creation of TreeNode
// objects. This ensures that the standard object structure of TreeNode is
// followed, and casts the resulting POJO correctly. Not strictly necessary,
// but reduces some redundancy later.
const treeNode = <T extends TreeNode>(
  arity: string, species: string, fields: {}
) =>
  ({
    about: {arity, species},
    ...fields
  }) as T

// Now, to define `nullary`, the HOF which generates closures which create
// instances of `Nullary` sub-types. This uses the technique covered in the
// article about Generic Tupled Rest Parameters to allow sub-types to have
// varying representations of their respective `raw` fields, but allow for
// type-specific closure function parameters.
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)})

// Both `unary` and `binary` are fairly similar, with the primary exceptions
// being the name and cardinality of their fields/params. Note that due to the
// relative similarity between these two functions and `nullary` above, it would
// be conceivably possible to abstract the three by adding another layer of
// HOFs; doing so would likely make certain sub-type specific behaviors unique
// to any of the three sub-types a bit more difficult to code for. Abstractions
// are only really useful if they ease the burden of coding, not complicate it
// for the sake of complicating it.
export const unary = <T extends Unary>(species: string) =>
  (child: TreeNode) =>
    treeNode<T>('unary', species, {child})

export const binary = <T extends Binary>(species: string) =>
  (left: TreeNode, right: TreeNode) =>
    treeNode<T>('binary', species, {left, right})

// The two primitive closures, `numeric` and `bool`, are the two most
// complicated derived functions, as they have type-specific generic overrides.
// These are mostly just specifying the types of parameters and fields, as
// well as a function that maps parameters to fields.
export const numeric = nullary<[number, number], {a: number, b: number}, Numeric>(
  'numeric', (a, b) => ({a, b})
)
export const bool = nullary<[boolean], {value: boolean}, Bool>(
  'boolean', (value) => ({value})
)

// Finally, several examples of using `unary` and `binary` to create sub-type
// specific creation closures. The first two, `absolute` and `factorial`, return
// POJO's that are cast to their respective generic types, and which have the
// appropriate `unary` arity, respective species, and a singular `child` field,
// bound to their parameter.
// The latter two, `add` and `multiply`, behave similarly, but accept two
// parameters and have two fields, instead.
export const absolute = unary<Absolute>('absolute')
export const factorial = unary<Factorial>('factorial')

export const add = binary<Addition>('addition')
export const multiply = binary<Multiplication>('multiplication')

// Finally, to show usage of the above closures, contemplate the following:
// `r` is a real-valued, negative numeric; `s` is the result of taking the
// absolute value of `r`.
// `a`, therefore, adds `r` to the produce of `s` and the factorial of `s`.
// These functions allow for the expression of complicated mathematical
// formulas without having to worry about the underlying object structures.
// Very convenient.
const r = numeric(-5, 0), s = absolute(r);
const a = add(r, multiply(s, factorial(s)));