typefn: 011 - AST: Type Guarding

011-ast-guards.md

For any sufficiently complicated system involving interrelated types, it will eventually become desirable to be able to ascertain the precise type of a given configuration of data; that is, more exactly, given data, figure out whether it adheres to a given specification.

In the discussion about Type Guards, methodologies for ascertaining, and seamlessly casting to, types was presented. Could such behavior be adapted to the context of the type system which was previously refined for the abstract syntax tree? Certainly!

Type guards, as a refresher, are predicates which, as a secondary effect of evaluating a relative truth about a passed value, also assert that the passed value is or is not of a given type. This latter functionality is purely behavior which exists only within the context of a TypeScript runtime; it is not transpiled to JavaScript, so never sees presence within a browser or server environment. Any given type guard can use any sort of predicate to ascertain what sort of data it is operating on; as far as failure conditions go, any sort of false result is a negative assertion about type, and conversely with respect to truth.

Knowing the application domain is key: should one be suspicious about the validity of the data that is being evaluated—the auspices under which it was generated, or whether one might trust the context from which it originated—a degree of rigorous and fastidious hyper-specificity would be called for. On the other hand, should the data only ever be created from well defined, well known, well trusted sources, a degree of laxity might be allowable. As always, robust testing of a system, as well as vigilance with respect to a live system, is necessary.

For the AST being developed in this system, it will be sufficient to simply test various sub-fields within a given TreeNode's about field: a given species is unique to a given type, thus not reused or re-contextualized; meanwhile, while an arity is shared between types, a given arity always comports with a given data structure. It would be relatively safe to assume these invariants, and simplify tests accordingly. The code presented with this discussion makes this assumption in developing its type guards.

(Should, however, one be overly paranoid, the code also presents an alternative approach which more exactingly evaluates a given object to ensure it contains specific fields. This alternative is isomorphic with the simpler approach in terms of the generated guard function type, and so would be interchangeable in future code.)

As a continuing goal of this series, derivative code and consuming code well downstream should be simple to write, maintain, use, and reason about. Many of these aspects can be accomplished via sufficient abstraction. Through use of HOFs, generics, and closures, as well as knowing system invariants, it is possible to write clean, tidy, minimalistic code.

011-ast-guards.ts

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

// Define a generic type for type guard predicates that ascertain if
// a given TreeNode is of a specific type.
export type TreeNodeGuardFn<T extends TreeNode> =
  (value: TreeNode) => value is T

// Create a HOF which generates TreeNodeGuardFn closures which test a
// passed TreeNode for a given arity. See discussion of `isSpeciesAlt`
// for an alternative to this
export const isArity = <T extends TreeNode>(arity: string): TreeNodeGuardFn<T> =>
  (value): value is T => value.about.arity === arity

// Create a HOF which generates TreeNodeGuardFn closures which test a
// passed TreeNode for a given species. This, while similar to the preceding
// function, verifies a more specific categorization determinant.
export const isSpecies = <T extends TreeNode>(species: string): TreeNodeGuardFn<T> =>
  (value): value is T => value.about.species === species

// Create a HOF which generates TreeNodeGuardFn closures which test a
// passed TreeNode for a given species, also ensuring that the specified fields
// are present on the object. Assuming certain invariants about the system---
// e.g. that a given `species` is only ever used on data which conforms to the
// species definition---this level of specific verification is, while more
// fastidious, not necessary in normal use. However, if this level of verification
// is desirable, this is one way in which to do it. A similar function can be
// created for `isArity` for `arity` checks, to ensure that anything that claims
// to be of a given arity conforms to its respective spec.
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)

// Some examples of using the above closure-generating HOFs to create
// 1) three instances of the `isArity` guard, and
// 2) six instances of the `isSpecies` guard.
// These are mostly superfluous, as one could always call the functions above
// as below wherever needed, but providing names to these checks makes for
// code that features less redundancy and that reads clearer. This also is
// less circumstantial overhead, as these functions only need to be created
// once, rather than once per contextual invocation.
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')

// Finally, an example of using the `isSpeciesAlt` HOF provided above. This
// mostly resembles the standard use, but adds in the field names to check
// for.
// NB: `isAddition` and `isAdditionAlt` both conform to `TreeNodeGuardFn`, so
// they have the exact same interface. As such, they are substitutable to one
// another without any contextual alterations. This function, here, just performs
// more checks on its passed value.
export const isAdditionAlt = isSpeciesAlt<Addition>('addition', ['left', 'right'])

011-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'>