Geometric algebra + TypeScript experiments

branding.ts

/*
Branding of vector spaces
-------------------------

Each vector belongs to a vector space.  A vector space should operate on its
own vectors only.  We can check this at run time, but we can also use branded
types to separate vector spaces already at compile time, at least to some
degree.

(That same idea is of course also applicable to geometric algebras.)
*/

{ // Run-time checks only

  class Vector {
    constructor(
      readonly owner: VectorSpace,
      readonly x: number,
      readonly y: number,
    ) {}
  }
  
  class VectorSpace {
    vector(x: number, y: number) { return new Vector(this, x, y); }
  
    checkMine(v: Vector) {
      if (v.owner !== this) throw "foreign vector given";
    }
  
    add(a: Vector, b: Vector) {
      this.checkMine(a);
      this.checkMine(b);
      return this.vector(a.x + b.x, a.y + b.y);
    }
  }
  
  const vs1 = new VectorSpace();
  const a = vs1.vector(1, 2), b = vs1.vector(3, 4);
  
  const vs2 = new VectorSpace();
  const c = vs2.vector(5, 6);
  
  vs1.add(a, b); // ok
  vs1.add(a, c); // throws  
}

{ // Run-time and compile-time checks

  class Vector<Brand> {
    constructor(
      readonly owner: VectorSpace<Brand>,
      readonly x: number,
      readonly y: number,
    ) {}
  }
  
  class VectorSpace<Brand> {
    vector(x: number, y: number) {
      return new Vector(this, x, y);
    }
  
    checkMine(v: Vector<Brand>) {
      if (v.owner !== this) throw "foreign vector given";
    }
  
    add(a: Vector<Brand>, b: Vector<Brand>) {
      this.checkMine(a);
      this.checkMine(b);
      return this.vector(a.x + b.x, a.y + b.y);
    }
  
    get #brand(): Brand { return undefined as Brand; }
  }
  
  // Enable one of the following blocks to define brands for vs1 and vs2:
  
  /*/
  type vs1_brand = "vs1";
  type vs2_brand = "vs2";
  /*
  declare const vs1_: unique symbol; type vs1_brand = typeof vs1_;
  declare const vs2_: unique symbol; type vs2_brand = typeof vs2_;
  /*/
  const enum vs1_brand {}
  const enum vs2_brand {}
  /**/
  
  const vs1 = new VectorSpace<vs1_brand>;
  const vs2 = new VectorSpace<vs2_brand>;
  
  const a = vs1.vector(1, 2), b = vs1.vector(3, 4), c = vs2.vector(5, 6);
  
  const d: Vector<vs2_brand> = c;
  
  vs1.add(a, b); // ok
  // vs1.add(a, c); // doesn't typecheck
  
  // In VS Code place the cursor after "." and type Ctrl-Blank to get suggestions:
  a.x  
}

GA+TS_experiments.md

This gist contains some experiments/ideas for typing geometric-algebra code in TypeScript.

These ideas might be applied to PEGEAL at some point.

multivector-typing.ts

/*
TypeScript Experiments for Geometric Algebra
============================================

Linear Algebra
--------------

In a vector space with a set C of coordinates (for example {"x", "y", "z"})
a vector maps each member of C to a real number.

These real numbers may have TypeScript type `number`, but we also allow
different types (to support partial evaluation). So we parameterize vectors
and other types by some type T, which should be a generalization of `number`.

A vector for coordinates {"x", "y", "z"} might have the TypeScript type

  {x: T, y: T, z: T}


Geometric Algebra
-----------------

In geometric algebra (a.k.a. Clifford algebra) we use "multivectors". 
A multivector maps each subset of the coordinate set C to a real number.
So with our coordinates {"x", "y", "z"} we have components for the 2**3 = 8
subsets

  {}, {"x"}, {"y"}, {"x", "y"}, {"z"}, {"x", "z"}, {"y", "z"}, {"x", "y", "z"}.

A multivector for our coordinates might have this TypeScript type:

  {"1": T, x: T, y: T, x_y: T, z: T, x_z: T, y_z: T, x_y_z: T}


Using Tuples
------------

Alternatively we might address components numerically, which leads to vectors
of type

  [T, T, T]

and multivectors of type

  [T, T, T, T, T, T, T, T]

We need some standard assignment of components to array positions.
But this is easy: Just represent a subset S ⊆ C as an integer `i` interpreted
as a bitmap where the bits represent the presence of "x", "y" and "z" in S,
starting from the least significant bit.  Then `i` is also the corresponding
index for the multivector 8-tuple.


Potential Usage
---------------

Actually for the implementation of multivector operations arrays with computed
indices are more natural than tuples and objects.  But:

- Object and tuple types might make sense in higher-level APIs for specialized
  geometric algebras such as projective and conformal GAs.

- The techniques explored here might also be used to declare stricter types to
  the functions in
  https://github.com/hcschuetz/pegeal/blob/main/src/componentNaming.ts.

- And another idea: PEGEAL could easily emit JS code.  To use that emitted code
  from hand-written code we can wrap it in JS `Function`s.  Could the types of
  such functions be expressed with the types introduced here? (Analogous
  considerations hold for calling PEGEAL-generated WASM code from JS.)

*/

{ console.log("Addressing components by name (object) =======================");

  console.log("To be used in examples: --------------------------------------");

  const xy = Object.freeze(["x", "y"] as const);
  type XY = typeof xy;
  console.log(xy);

  const xyz = Object.freeze(["x", "y", "z"] as const);
  type XYZ = typeof xyz;
  console.log(xyz);

  console.log("Vector-level definitions: ------------------------------------");

  /** **R**ead-**O**nly **S**tring **A**rray */
  type ROSA = readonly string[];

  type Vector<Keys extends ROSA, T> = Record<Keys[number], T>;

  const complete =
    <C extends ROSA, T>(defaults: Vector<C, 0>) =>
    (partial: Partial<Vector<C, T>>): Vector<C, T | 0> =>
    Object.assign({}, defaults, partial);

  const zeroVector = <C extends ROSA>(c: C) =>
    Object.freeze(c.reduce((acc, k) => Object.assign(acc, {[k]: 0}), {})) as Vector<C, 0>;

  console.log("Vector-level examples:----------------------------------------");

  const zeroVector_XYZ = zeroVector(xyz);
  console.log(zeroVector_XYZ)

  const completeXYZ = complete(zeroVector_XYZ) as
    <T>(partial: Partial<Vector<XYZ, T>>) => Vector<XYZ, T>;

  let v: Partial<Vector<XYZ, number | string>> = {x: 2, y: "foo"};
  console.log(completeXYZ(v));

  console.log("Multivector-level type definitions: --------------------------");

  type ExtendString<T extends string, U extends string> = `${T}_${U}`;

  type MapExtendString<A extends ROSA, S extends string> =
    { [K in keyof A]: ExtendString<A[K], S> }
  ;

  type PowRaw<Names extends ROSA> =
    Names extends readonly [...infer Rest extends ROSA, infer Last extends string]
    ? readonly [...PowRaw<Rest>, ...MapExtendString<PowRaw<Rest>, Last>]
    : readonly ["1"]
  ;

  type Simplify<T extends string> =
    T extends `1_${infer U extends string}` ? U : T
  ;

  type MapSimplify<Raw extends ROSA> = { [K in keyof Raw]: Simplify<Raw[K]> };

  type Pow<Names extends ROSA> = MapSimplify<PowRaw<Names>>;

  let a: Pow<XYZ>;

  type MultiVector<Keys extends ROSA, T> = Vector<Pow<Keys>, T>;

  console.log("Multivector-level function definitions: ----------------------");

  function powRaw(keys: ROSA): ROSA {
    if (keys.length === 0) return ["1"];
    const [first, ...rest] = keys;
    const rec = pow(rest);
    return rec.flatMap(r => [r, `${first}_${r}`]);
  }

  const pow = <Keys extends ROSA>(keys: Keys) =>
    powRaw(keys).map(s => s.replace(/_1$/, "")) as Pow<Keys>;
  
  const zeroMV = <C extends ROSA>(c: C) =>
    zeroVector(pow(c)) as MultiVector<C, 0>;

  console.log("Examples: ----------------------------------------------------");

  // Shorthands for particular type parameters:
  const zeroMV_XYZ = zeroMV(xyz);
  console.log(zeroMV_XYZ);

  type MV3 = MultiVector<XYZ, number | string>;
  const completeMV3 = complete(zeroMV_XYZ) as (partial: Partial<MV3>) => MV3;

  const mv3 = completeMV3({"1": 4, x_y: 6.28, x_z: "foo", y_z: "bar"});
  console.log(mv3);

  // Some other type parameters:
  const zeroMV_XY = zeroMV(xy);
  console.log(zeroMV_XY);

  type MV2 = MultiVector<XY, number>;
  const completeMV2 = complete(zeroMV_XY) as (partialMV: Partial<MV2>) => MV2;

  const mv2 = completeMV2({"1": 4, x_y: 6.28});
  console.log(mv2);

  // We can even "lift" mv2 to type MV3:
  console.log(completeMV3(mv2));
  // ... or project 
  const powXY = pow(xy) as Pow<XY>;
  const project3to2 = (from: MV3) =>
    powXY.reduce(
      (to, key) => { to[key] = from[key]; return to; },
      {} as MultiVector<XY, number | string>,
    );
  console.log(project3to2(mv3));
}

{ console.log('"Disjunctive" implementation of Pow: =========================');

  type ROSA = readonly string[];

  type PowRaw<A extends ROSA> =
    A extends [...infer Rest extends ROSA, infer Last extends string]
    ? PowRaw<Rest> | `${PowRaw<Rest>}_${Last}`
    : "1"
  ;

  type Simplify<T extends string> = T extends `1_${infer U}` ? U : T;

  type Pow<A extends ROSA> = Simplify<PowRaw<A>>

  type MultiVector<A extends ROSA, T> = Record<Pow<A>, T>;

  let b: Partial<MultiVector<["x", "y", "z"], number | symbol>> = {
    "1": 5,
    x_y: Symbol("foo"),
    y_z: 9
  };
}

{ console.log("Addressing components numerically (array/tuple): =============");

  // See https://2ality.com/2025/01/typescript-tuples.html#utility-type-Repeat
  type CreateTuple<Len extends number, T, Acc extends Array<unknown> = []> = 
    Acc['length'] extends Len
    ? Acc
    : CreateTuple<Len, T, [...Acc, T]>
  ;

  type Duplicate<A extends Array<unknown>> = [...A, ...A];

  type MVAux<T, Tuple> =
    Tuple extends readonly [unknown, ...infer Rest]
    ? Duplicate<MVAux<T, Rest>>
    : [T]
  ;

  type MultiVector<T, N extends number> = MVAux<T, CreateTuple<N, unknown>>;

  let a: MultiVector<number | string, 3>;
  let b: MVAux<number | string, ["x", "y", "z"]>;
}