Experiment with type for AST

[DylanSp]

Ideas from https://matklad.github.io/2023/08/17/typescript-is-surprisingly-ok-for-compilers.html:

Idea 1: Parametrize AST nodes with associated data

interface Expr<T> {
  location: Location; // location in source code, for error reporting
  data: T;
  kind: ExprKind<T>; // "underlying" AST node
}

// union of AST node types
type ExprKind<T> =
  | ExprBool<T>
  | ExprInt<T>
  | ExprBinary<T>
  | ExprControl<T>;

Could be used for type-checking - parsing produces an Expr<void>, typechecking produces Expr<Type>.

Idea 2: More parametrization for representation of sugared/desugared ASTs

(At very bottom of linked article)

interface Expr<K> {
  location: Location,
  kind: K,
}

// binary operation
interface ExprBinary<E> {
  op: BinaryOp,
  lhs: E,
  rhs: E,
}

// Fundamental, primitive expressions. (totally desugared)
type ExprKindCore<E> =
    ExprInt<E> | ExprBinary<E> | ExprIf<E>

// Expressions which are either themselves primitive,
// or can be desugared to primitives.
// (includes sugar)
type ExprKindSugar<E> = ExprKindCore<E>
    | ExprCond<E> | ExprUnless<E>

// recursively parametrized types
type ExprCore = Expr<ExprKindCore<ExprCore>>; 
type ExprSugar = Expr<ExprKindSugar<ExprSugar>>;

// Desugaring works by reducing the set of expression kinds.
function desugar(expr: ExprSugar): ExprCore { /* implement */ }

// A desugaring steps takes a (potentially sugar) expression,
// whose subexpression are already desugared,
// and produces an equivalent core expression.
function desugar_one(
    expr: ExprKindSugar<ExprCore>,
): ExprKindCore<ExprCore>

(I'm not sure how the last one would be used, but it's worth noting)