typefn: 010 - AST: Initial Type Restructure

010-ast-itr.md

In the Abstract Syntax Trees Overview, the code for the article presented a set of distinct types for defining a very basic AST. These types each manually redefined the entire representation of a TreeNode, as pertained to the type in question. This is not only repetitious and prone to error, but it also reduces to possibility for these types to be more consistently generated automatically.

Is it possible, in TypeScript, to generate types automatically, and have them define, very loosely, a series of interrelated connections? Certainly, as has been seen previously in the discussion of Generics. Perhaps it would be possible to utilize some of the techniques previously discussed here, and thus redefine the type structure of the AST; this would also allow for easy and rapid expansion of the set of types the system could support.

As a refresher, recall that a type in TypeScript represents the set of known behaviors of the data it is said to represent. As such, it describes the fields and operations that are permissable on the type. A type can also be the composite of multiple existing types, via use of the &, type intersection combination operator. With this operator, subsequent types in the list will add their fields to the type definition built in previous stages; should this process hit a duplicate field name, the most recent instance will overwrite.

Generic type definitions can use this functionality to establish a base type—such as TreeNode—and extend its functionality via a series of overrides, some of which might be contextually programmed into the generic via a generic type parameter. This can simplify the definition of a new derivative type, limit the repetition of specifying certain types of fields, ensure that all fields within a type are readonly, and also limit the impact of mistyping key string literals.

With this minor restructure in hand, defining new derived types to add to the system is comparably trivial: typically, a simple one-liner that invokes a single generic type, passing a single string-based type parameter. This allows the types, and their data, to be handled in a nicely uniform fashion, largely consistent across the ensuing system. Also, should the need arise to expand or alter some aspect of the type system, these edits will be easier to address.

010-ast-itr.ts

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

type TreeNode = {
  readonly about: Categorization
}

// Create a generic type which takes two type parameters: the first representing
// the Categorization arity of the extended TreeNode; the second representing
// the common shared fields that types derived from the extended TreeNode have.
// This generic establishes that types created from it are TreeNodes, have the
// specified Arity, and the set of Fields, which are made Readonly.
// This is intended to define abstract interstitial base classes for different
// sub-groupings of TreeNode. E.g., for TreeNodes which are binary.
type ExtendTreeNode<Arity extends string, Fields extends {}> = TreeNode & {
  readonly about: {readonly arity: Arity}
} & Readonly<Fields>

// Create a generic type which would take two type parameters: the first being
// a type generated by the previous generic, and the second being the Species
// the node should have. This defines the new derived type as the intersection
// of these data.
// This would be used to create new derived types directly, or as generic type
// which another generic type can delegate to.
type FromExtendedTreeNode<Base extends TreeNode, Species extends string> = Base & {
  readonly about: {readonly species: Species}
}

// Nullary becomes much simpler, compared to the previous iteration. A generic,
// FromNullary, is provided which mostly just wraps FromExtendedTreeNode, but
// allows a deriving type to override the `raw` field in a consistent fashion.
type Nullary = ExtendTreeNode<'nullary', {raw: unknown}>
type FromNullary<Species extends string, Raw extends {}> = 
  FromExtendedTreeNode<Nullary, Species> & {
    readonly raw: Readonly<Raw>
  }

// Numeric becomes vastly simplified, and Bool is introduced.
// NB. as per the generic type definitions above, the Fields object type
// parameter will be made Readonly, so it is sufficient to pass a basic,
// writeable definition here. This can also improve clarity, to a degree.
type Numeric = FromNullary<'numeric', {a: number, b: number}>
type Bool = FromNullary<'boolean', {value: boolean}>

// Unary, like Nullary, is simplified; its helper generic is a very basic
// wrapper around FromExtendedTreeNode. Not entirely necessary, but does
// make the resulting derived type definitions a bit easier to read.
type Unary = ExtendTreeNode<'unary', {child: TreeNode}>
type FromUnary<Species extends string> = FromExtendedTreeNode<Unary, Species>

// Two unary types; Absolute is much simpler compared to previously, while
// Factorial is newly introduced.
type Absolute = FromUnary<'absolute'>
type Factorial = FromUnary<'factorial'>

// Binary is similarly simplified, and its helper generic is similar in
// design to `Unary`'s. 
type Binary = ExtendTreeNode<'binary', {left: TreeNode, right: TreeNode}>
type FromBinary<Species extends string> = FromExtendedTreeNode<Binary, Species>

// Addition is simpler, and now Multiplication has been introduced.
type Addition = FromBinary<'addition'>
type Multiplication = FromBinary<'multiplication'>