Skip to content

Instantly share code, notes, and snippets.

@raganwald

raganwald/fractran.ts

Last active June 25, 2025 19:22
Show Gist options
  • Save raganwald/ac3ef0c7bfa9f307677485d95af03cc8 to your computer and use it in GitHub Desktop.
Save raganwald/ac3ef0c7bfa9f307677485d95af03cc8 to your computer and use it in GitHub Desktop.
Download ZIP
A FRACTRAN interpreter in type-level TypeScript
Raw
fractran.ts
/*
FRACTRAN in type-level TypeScript:
Q. What is FRACTRAN?
A. FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway.
A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer
input n. The program is run by updating the integer n as follows:
1. for the first fraction f in the list for which nf is an integer, replace n by nf
2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
Q. Hunh?
A. https://en.wikipedia.org/wiki/FRACTRAN
Q. Why does FRACTRAN matter?
A. https://raganwald.com/2020/05/03/fractran.html
Q. Why in type-level TypeScript?
A. https://raganwald.com/assets/books/pleasure-of-finding-things-out.pdf
Q. How do I try it?
A. "Programs" are written as ordered lists one or more proper fractions, comma-delimited. In this implementation,
"(2/3, 2/5)" is a FRACTRAN program that adds two numbers. FRACTRAN does not have any syntax for composing
programs, or operators, or even a syntax for invoking a program with data.
The initial value encodes one or more values using Gödel encoding: Two numbers a and b could be
encoded in a single initial number by raising the prime 3 to the power of a, then muliplying it by the
prime 5 raised to the power of b: 3^a·5^b.
The result or results are also Gödel encoded, the result of adding a and b might be encoded as the prime
2 raised to the power of the sum of a and b. This is informally expressed as 3^a·5^b -> 2^(a+b),
which serves as non-executable documentation of our intent.*/
// 3^a·5^b -> 2^(a+b)
type _0 = Expect<Equal<32, FRACTRAN.Evaluate<"(2/3, 2/5)", 1125>>>;
// 2^a·3^b -> 5^(a·b)
type _1 = Expect<Equal<15625, FRACTRAN.Evaluate<"(455/33, 11/13, 1/11, 3/7, 11/2, 1/3)", 72>>>;
/*
Q. Anything odd about the implementation?
A. The bulk of the code builds the arithmatic we need to divide and multiply
large numbers, because Gödel encoding quickly runs into numbers that
overwhelm a type system built for types, not for using types to ape values.
It turns the numbers into tuples of decimal digits, and then implements
the same effective procedure for addition, subtraction, multiplication, and
Euclidean division as are taught in elemntary school for use with pencils
and paper.
Were we building a computing machine that doesn’t need to work with large numbers,
we could have used simpler ways to impement basic arithmetic.
Q. Are there any other limitations?
A. Plenty! Large and complex FRACTRAN programs are unlikely to work properly.
Even with programs written in tail-recursive form, TypeScript has a hard limit
of 1,000 recursive function calls.
At the very minimum, this limits FRACTRAN programs from executing more than 1,000
repititions of the main evaluation loop. Working around that limitation would be
another effort.
Q. Is there a low-effort way to try the code?
A. Copy -> https://www.typescriptlang.org/play/ -> Paste.
Q. Let me read the code!
A. 👇🏽
*/
// ---------- A FRACTRAN interpreter ----------
namespace FRACTRAN {
// Fractions
type Fraction = { numerator: number, denominator: number };
// 💭 It is not obvious to me how to use FractionFrom in the ProgramFrom
// code. This should be a basic building block, conceptually:
//
// S extends `${infer F extends FractionFrom<_>}`
//
// Where _ is a hole that we stuff the string into. The notation is
// wrong, but the concept is that given a generic A<B extends C>,
// it should be possible to insert A<...> somewhere we expect a C,
// and then we can write infer D extends A<...> and it will pattern match
// B unless A<B> evaluates to never.
type FractionFrom<S extends string> =
S extends `${infer N extends number}/${infer D extends number}`
? { numerator: N, denominator: D }
: never;
namespace TestFractionFrom {
type _0 = Expect<IsNever<FractionFrom<"">>>;
type _2 = Expect<IsNever<FractionFrom<"1/">>>;
type _4 = Expect<IsNever<FractionFrom<"/2">>>;
type _8 = Expect<Equal<{ numerator: 1, denominator: 2 }, FractionFrom<"1/2">>>;
// @ts-expect-error: has to be a digit
type _16 = Expect<IsNever<FractionFrom<1>>>;
}
// Fraction strings are comma separated lists of fractions, and a FractionPattern is a matcher
// TypeScript requires fixed patterns, so this is the maximum number of fractions in a program
type MAX_FRACTIONS = 50;
// We are repeating ourselves here: A fraction pattern for simple
// boolean checking is used again with inferences to extract
// values within the pattern.
type FractionPattern = `${number}/${number}`;
type FractionsPattern<P extends any[] = [FractionPattern]> =
P["length"] extends MAX_FRACTIONS
? P[number] // return a union of the patterns
: P extends [...any, infer LastPattern extends string]
? FractionsPattern<[...P, `${LastPattern}, ${FractionPattern}`]>
: Fail<"unable to derive the last pattern">;
namespace TestFractionPattern {
type IsFractionsString<S extends string> = S extends FractionsPattern ? true : false;
type _0 = Expect<Equal<false, IsFractionsString<"">>>;
type _1 = Expect<Equal<false, IsFractionsString<"12">>>;
type _2 = Expect<Equal<false, IsFractionsString<"1.2">>>;
// @ts-expect-error TODO: Check for negatve numbers and zeroes.
type _3 = Expect<Equal<false, IsFractionsString<"-1/2">>>;
// @ts-expect-error TODO: Check for negatve numbers and zeroes.
type _4 = Expect<Equal<false, IsFractionsString<"1/-2">>>;
// @ts-expect-error TODO: Check for negatve numbers and zeroes.
type _5 = Expect<Equal<false, IsFractionsString<"1/0">>>;
// @ts-expect-error TODO: Check for negatve numbers and zeroes.
type _6 = Expect<Equal<false, IsFractionsString<"0/1">>>;
type _7 = Expect<Equal<false, IsFractionsString<"1/2 3/5">>>;
type _10 = Expect<IsFractionsString<"1/2">>;
type _11 = Expect<IsFractionsString<"1/2, 3/5">>;
type _12 = Expect<IsFractionsString<"1/2, 3/5, 7/11">>;
}
// programs are lists of fractions
type Program = [Fraction, ...Fraction[]];
type ProgramPattern = `(${FractionsPattern})`;
type ProgramFrom<S extends ProgramPattern> =
S extends `(${infer FractionsString extends FractionsPattern})`
? ProgramFromFractionsString<FractionsString>
: never
type ProgramFromFractionsString<S extends string, ACC extends Fraction[] = []> =
S extends `${infer N extends number}/${infer D extends number}`
// degenerate/base case
? [...ACC, { numerator: N, denominator: D }]
// linear recursion
: S extends `${infer N extends number}/${infer D extends number}, ${infer Rest extends FractionsPattern}`
? ProgramFromFractionsString<Rest, [...ACC, { numerator: N, denominator: D }]>
: Fail<`"${S}" does not match a FractionsPattern`>;
namespace TestProgramFrom {
// @ts-expect-error should be caught by the type system
type _0 = Expect<IsNever<ProgramFrom<"">>>;
// @ts-expect-error should be caught by the type system
type _1 = Expect<IsNever<ProgramFrom<"42">>>;
type _2 = Expect<Equal<[{ numerator: 5, denominator: 3 }], ProgramFrom<"(5/3)">>>;
type _3 = Expect<Equal<[{ numerator: 5, denominator: 3 }, { numerator: 1, denominator: 2 }], ProgramFrom<"(5/3, 1/2)">>>;
type _4 = Expect<Equal<[{ numerator: 2, denominator: 3 }, { numerator: 2, denominator: 5 }], ProgramFrom<"(2/3, 2/5)">>>;
type _F = Expect<Equal<
[
{ numerator: 17, denominator: 65 },
{ numerator: 133, denominator: 34 },
{ numerator: 17, denominator: 19 },
{ numerator: 23, denominator: 17 },
{ numerator: 2233, denominator: 69 },
{ numerator: 23, denominator: 29 },
{ numerator: 31, denominator: 23 },
{ numerator: 74, denominator: 341 },
{ numerator: 31, denominator: 37 },
{ numerator: 41, denominator: 31 },
{ numerator: 129, denominator: 287 },
{ numerator: 41, denominator: 43 },
{ numerator: 13, denominator: 41 },
{ numerator: 1, denominator: 13 },
{ numerator: 1, denominator: 3 },
],
ProgramFrom<"(17/65, 133/34, 17/19, 23/17, 2233/69, 23/29, 31/23, 74/341, 31/37, 41/31, 129/287, 41/43, 13/41, 1/13, 1/3)">
>>;
}
type EvalFraction<F extends Fraction, Value extends number> =
F extends { numerator: infer Multiplier extends number, denominator: infer Divisor extends number }
? DigitalArithmetic.DivideEvenly<Value, Divisor> extends infer DividedValue extends number
? DigitalArithmetic.Multiply<DividedValue, Multiplier>
: Fail<"Does not divide evenly in EvalFraction">
: Fail<"Not a fraction">;
namespace TestEvalFraction {
type _0 = Expect<Equal<2, EvalFraction<FractionFrom<"2/3">, 3>>>;
type _1 = Expect<Equal<4, EvalFraction<FractionFrom<"2/3">, 6>>>;
type _2 = Expect<IsFail<EvalFraction<FractionFrom<"2/3">, 5>>>;
type _3 = Expect<Equal<6, EvalFraction<FractionFrom<"3/5">, 10>>>;
type _4 = Expect<Equal<675, EvalFraction<FractionFrom<"3/5">, 1125>>>;
}
type DOES_NOT_EVALUATE = Fail<"Does not evaluate">;
type DoesNotEvaluate<T> = T extends DOES_NOT_EVALUATE ? true : false;
type EvalIteration<RemainingFractions extends Fraction[], Value extends number> =
RemainingFractions extends [infer First extends Fraction, ...infer Rest extends Fraction[]]
? EvalFraction<First, Value> extends infer Result extends number
? Result
: EvalIteration<Rest, Value>
: DOES_NOT_EVALUATE;
namespace TestEvalIteration {
type _0 = Expect<DoesNotEvaluate<EvalIteration<[], 6>>>;
type _1 = Expect<Equal<9, EvalIteration<ProgramFrom<"(3/2)">, 6>>>;
type _2 = Expect<DoesNotEvaluate<EvalIteration<ProgramFrom<"(3/5)">, 6>>>;
type _3 = Expect<Equal<4, EvalIteration<ProgramFrom<"(3/5, 2/3)">, 6>>>;
type _4 = Expect<DoesNotEvaluate<EvalIteration<ProgramFrom<"(3/5, 2/3)">, 4>>>;
type _5 = EvalIteration<ProgramFrom<"(2/3)">, 1125>;
type _6 = EvalIteration<ProgramFrom<"(2/5)">, 1125>;
type _7 = EvalIteration<ProgramFrom<"(2/3, 2/5)">, 1125>;
}
type UNKNOWN_EVAL_ITERATION_RESULT = Fail<"Unknown EvalIteration Result">;
type NEVER_EVAL_ITERATION_RESULT = Fail<"Never EvalIteration Result">;
type Interpret<Fractions extends Program, Value extends number> =
EvalIteration<Fractions, Value> extends infer Result
? Result extends DOES_NOT_EVALUATE
? Value
: Result extends number
? Interpret<Fractions, Result>
: Fail<"Unknown EvalIteration Result">
: Fail<"Unknown EvalIteration Result">;
namespace TestInterpret {
// if it doesn't evaluate, it returns the parameter
type _0 = Expect<Equal<6, Interpret<ProgramFrom<"(2/11)">, 6>>>;
type _1 = Expect<Equal<4, Interpret<ProgramFrom<"(2/3)">, 6>>>;
type _2 = Expect<Equal<4, Interpret<ProgramFrom<"(1/11, 2/3)">, 6>>>;
// 2 + 2 = 4 in FRACTRAN
type _3 = Expect<Equal<16, Interpret<ProgramFrom<"(2/3)">, 36>>>;
}
// Evaluates a
export type Evaluate<Source extends string, InitialValue extends number> =
Source extends `${infer ProgramSource extends ProgramPattern}`
? Interpret<ProgramFrom<ProgramSource>, InitialValue>
: Fail<"Pass a program string and a positive number">;
namespace TestEvaluate {
type _0 = Expect<IsFail<Evaluate<"3/5", 25>>>;
type _1 = Expect<Equal<9, Evaluate<"(3/5)", 25>>>;
}
// ---------- Gödel Encoding/Decoding for convenience ----------
type Example1 = Expect<Equal<16, FRACTRAN.Evaluate<"(2/3, 2/5)", 225>>>;
// This is equivalent to ((a, b) => a + b)(2, 2).
// The parameters a and b are represented as 3^2·5^2 = 225.
// The result is represented as 2^4 = 16.
//
// The FRACTRAN program (2/3, 2/5) has a _schema_, which we write: (3, 5) => (2),
// meaning, it takes two parameters that are encoded as the product of the
// number 3 raised to the first parameter and the number 5 raised to the
// second parameter, and it returns one parameter, encoded as 2 raised to the
// single return value.
//
// It is possible for a program to take one paramter, one such schema might be
// (3) => (2). And multiple return values are possible. The schema of a FRACTRAN
// program that performs Euclidean division might be (5, 7) => (2, 3), as
// Euclidean division takes parameters for dividend and divisor, and returns
// values for quotient and remainder.
//
// The schema has two lists of unique primes, A => B. Each must be (p1, p2, ..., pn)
// The primes must be unqiue within each list, but it is allowed for primes
// to be common between parameters and return values. (Whether that is a good
// idea is not a consideration.)
// “If you have a procedure with ten parameters, you probably missed some.”—Dr. Alan J. Perlis
//
// This implementation is limited to a maximum of 25 parameters and 25 return types, and requires
// That all programs make use of the first 25 primes for parameters and return types. It is possible
// to use larger primes within the programs for temporary registers.
export type PrimesLessThan100 = [
2, 3, 5, 7, 11,
13, 17, 19, 23, 29,
31, 37, 41, 43, 47,
53, 59, 61, 67, 71,
73, 79, 83, 89, 97
];
export type PrimeLessThan100 = PrimesLessThan100[number];
type L = PrimesLessThan100["length"]
type NumberPattern = `${number}`;
// uses linear recursion to match a list of numbers no
// longer than the length of PrimesLessThan100 because
// this exists to match lists of primes
type NumbersPattern<P extends any[] = [NumberPattern]> =
P["length"] extends PrimesLessThan100["length"]
? P[number] // return a union of the patterns
: P extends [...any, infer LastPattern extends string]
? NumbersPattern<[...P, `${LastPattern}, ${NumberPattern}`]>
: Fail<"unable to derive the last pattern">;
namespace TestNumbersPatternPattern {
// @ts-expect-error the empty string is not a parameter pattern
type _0 = Expect<Extends<"", NumbersPattern>>;
type _2 = Expect<Extends<"2", NumbersPattern>>;
type _2_3 = Expect<Extends<"2, 3", NumbersPattern>>;
type _37_17_5 = Expect<Extends<"37, 17, 5", NumbersPattern>>;
// does not enforce primes
type _42_16 = Expect<Extends<"37, 17, 5", NumbersPattern>>;
// does not enforce uniqueness
type __6_6 = Expect<Extends<"6, 6", NumbersPattern>>;
}
type AsUniquePrimes<S extends NumbersPattern, Parameters extends number[] = [], AvailableParameters = PrimeLessThan100> =
S extends `${infer Parameter extends number}`
// degenerate/base case is one number
? Parameter extends AvailableParameters
? [...Parameters, Parameter]
: Fail<`${Parameter} is not a terminal unique prime < 100`>
// linear recursion
: S extends `${infer Parameter extends number}, ${infer Rest extends NumbersPattern}`
? Parameter extends AvailableParameters
? AsUniquePrimes<Rest, [...Parameters, Parameter], Exclude<AvailableParameters, Parameter>>
: Fail<`${Parameter} is not a unique prime < 100`>
: Fail<`${S} does not match a pattern of parameters`>;
namespace TestAsUniquePrimes {
// @ts-expect-error empty string are not parameters
type _01 = AsUniquePrimes<"">;
type _02 = Expect<Equal<[2], AsUniquePrimes<"2">>>;
type _03 = Expect<Equal<[17, 3, 7], AsUniquePrimes<"17, 3, 7">>>;
type _04 = Expect<Equal<
[
2, 3, 5, 7, 11,
13, 17, 19, 23, 29,
31, 37, 41, 43, 47,
53, 59, 61, 67, 71,
73, 79, 83, 89, 97
],
AsUniquePrimes<"2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97">
>>;
// 31 is repeated
type _05 = Expect<IsFail<
AsUniquePrimes<"2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 31, 67, 71, 73, 79, 83, 89, 97">
>>;
}
type Schema = [PrimeLessThan100[], PrimeLessThan100[]];
type SchemaPattern = `(${NumbersPattern}) => (${NumbersPattern})`;
// Extract the parameters and return base, but fail if they are not unique primes < 100
type SchemaFrom<S extends SchemaPattern> =
S extends `(${infer ParameterPrimesString extends NumbersPattern}) => (${infer ReturnPrimesString extends NumbersPattern})`
? [AsUniquePrimes<ParameterPrimesString>, AsUniquePrimes<ReturnPrimesString>] extends [
infer ParameterPrimes extends PrimeLessThan100[],
infer ReturnPrimes extends PrimeLessThan100[]
]
? [ParameterPrimes, ReturnPrimes]
: Fail<`(${ParameterPrimesString}) and (${ReturnPrimesString}) are not lists of unique primes < 100`>
: never;
namespace TestSchemaFrom {
// @ts-expect-error empty string are not parameters
type _01 = SchemaFrom<"">;
// @ts-expect-error numbers must be parenthesized
type _02 = Expect<IsFail<SchemaFrom<"2">>>;
// @ts-expect-error numbers must be parenthesized
type _03 = Expect<IsFail<SchemaFrom<"2 => 3">>>;
type _04 = Expect<Equal<[[2], [5]], SchemaFrom<"(2) => (5)">>>;
type _05 = Expect<Equal<[[2, 5], [3, 7]], SchemaFrom<"(2, 5) => (3, 7)">>>;
type _06 = Expect<IsFail<SchemaFrom<"(2, 5, 5) => (3, 7)">>>;
type _07 = Expect<IsFail<SchemaFrom<"(2, 5) => (7, 3, 7)">>>;
}
type ProgramWithSchemaPattern = `${ProgramPattern}: ${SchemaPattern}`;
namespace testProgramPattern {
type _0 = Expect<Extends<"(2/3, 2/5): (3, 5) => (2)", ProgramWithSchemaPattern>>;
type _1 = Expect<IsFalse<Extends<"(2/3, 2/5)", ProgramWithSchemaPattern>>>;
}
export type EvaluateWithSchema<
S extends ProgramWithSchemaPattern,
P0 extends number = 0, P1 extends number = 0, P2 extends number = 0, P3 extends number = 0, P4 extends number = 0,
P5 extends number = 0, P6 extends number = 0, P7 extends number = 0, P8 extends number = 0, P9 extends number = 0,
P10 extends number = 0, P11 extends number = 0, P12 extends number = 0, P13 extends number = 0, P14 extends number = 0,
P15 extends number = 0, P16 extends number = 0, P17 extends number = 0, P18 extends number = 0, P19 extends number = 0,
P20 extends number = 0, P21 extends number = 0, P22 extends number = 0, P23 extends number = 0, P24 extends number = 0
> = S extends `${infer ProgramSource extends ProgramPattern}: ${infer SchemaSource extends SchemaPattern}`
? ProgramFrom<ProgramSource> extends infer P extends Program
? SchemaFrom<SchemaSource> extends [infer ParameterPrimes extends PopulatedTupleOf<PrimeLessThan100>, infer ReturnValuePrimes extends PopulatedTupleOf<PrimeLessThan100>]
? TrimToLengthOfExemplar<[
P0, P1, P2, P3, P4,
P5, P6, P7, P8, P9,
P10, P11, P12, P13, P14,
P15, P16, P17, P18, P19,
P20, P21, P22, P23, P24
],
ParameterPrimes
> extends infer Parameters extends PopulatedTupleOf<number>
? Godel.AsEncodedDigitTuple<Parameters, ParameterPrimes> extends infer InitialValue extends DigitalArithmetic.WellFormedDigitTuple
? Interpret<P, DigitalArithmetic.Tuple.AsNumber<InitialValue>> extends infer ValueWhenHalted extends number
? Godel.AsDecodedNumbers<ValueWhenHalted, ReturnValuePrimes> extends infer ReturnValues extends number[]
? ReturnValues["length"] extends 1 ? ReturnValues[0] : ReturnValues
: Fail<"Unable to decode">
: Fail<"Unable to interpret">
: Fail<"Unable to aggregate the initial value">
: Fail<"Unable to trim parameters to expected length">
: Fail<"Inference conditional doesn't match constraint 3">
: Fail<"Inference conditional doesn't match constraint 2">
: Fail<`Inference conditional doesn't match constraint in ${S}`>
namespace TestEvaluateWithSchema {
type _0 = Expect<Equal<4, EvaluateWithSchema<"(2/3, 2/5): (3, 5) => (2)", 2, 2>>>;
}
type TrimToLengthOfExemplar<T extends number[], Exemplar extends number[]> =
T["length"] extends Exemplar["length"]
? T
: T extends [...infer ButLast extends number[], infer Last extends number]
? TrimToLengthOfExemplar<ButLast, Exemplar>
: Fail<"Exemplar exceeded length of tuple to trim">
namespace TestTrimToLengthOfExemplar {
type _0 = Expect<IsFail<TrimToLengthOfExemplar<[], [2, 3, 5]>>>;
type _1 = Expect<IsFail<TrimToLengthOfExemplar<[1], [2, 3, 5]>>>;
type _2 = Expect<Equal<[1, 2, 3], TrimToLengthOfExemplar<[1, 2, 3], [2, 3, 5]>>>;
type _3 = Expect<Equal<[1, 2, 3], TrimToLengthOfExemplar<[1, 2, 3, 4, 5], [2, 3, 5]>>>;
}
// Godel encoding and decoding for wrapping FRACTRAN in TS-style parameters and a return value
namespace Godel {
type DigitTuple = DigitalArithmetic.DigitTuple;
type WellFormedDigitTuple = DigitalArithmetic.WellFormedDigitTuple;
type AsDigitTuple<T extends number> = DigitalArithmetic.AsDigitTuple<T>;
// TODO: Move to namespace DigitalArithmetic.Tuple
type AsDigitTuples<N extends number[], ACC extends DigitTuple[] = []> =
N extends []
? ACC
: N extends [infer First extends number, ...infer Rest extends number[]]
? AsDigitTuple<First> extends infer FirstDigitTuple extends DigitalArithmetic.DigitTuple
? AsDigitTuples<Rest, [...ACC, FirstDigitTuple]>
: Fail<"Unexpected failure to convert a number to a DigitTuple">
: Fail<"Unexpected failure to pattern match">;
namespace TestAsDigitTuples {
type _0 = Expect<Equal<[], AsDigitTuples<[]>>>;
type _1 = Expect<Equal<[[1]], AsDigitTuples<[1]>>>;
type _42 = Expect<Equal<[[4, 2]], AsDigitTuples<[42]>>>;
type _birthday = Expect<Equal<[[1, 9, 6, 2], [6], [1, 4]], AsDigitTuples<[1962, 6, 14]>>>;
}
export type AsEncodedDigitTuple<
Parameters extends PopulatedTupleOf<number>,
ParameterPrimes extends (PopulatedTupleOf<PrimeLessThan100> & { length: Parameters["length"] })
> =
[AsDigitTuples<Parameters>, AsDigitTuples<ParameterPrimes>] extends [
infer ParametersTT extends DigitTuple[], infer ParameterPrimesTT extends DigitTuple[]
]
? EncodeTT<ParametersTT, ParameterPrimesTT>
: Fail<"Unexpected failure to convert parameters and parameter primes to tuples of DigitTuples">;
namespace TestAsEncodedDigitTuple {
// @ts-expect-error empty tuples verboten
type _0 = AsEncodedDigitTuple<[], []>;
// @ts-expect-error empty tuples verboten
type _1 = AsEncodedDigitTuple<[], [2]>;
// @ts-expect-error both tuples must have the same length
type _2 = AsEncodedDigitTuple<[5], [2, 3]>;
type _3 = Expect<Equal<[8], AsEncodedDigitTuple<[3], [2]>>>;
type _4 = Expect<Equal<[2, 2, 5], AsEncodedDigitTuple<[2, 2], [3, 5]>>>;
type _5 = Expect<Equal<[1, 8, 5, 9], AsEncodedDigitTuple<[1, 2], [11, 13]>>>;
}
type EncodeTT<
ParametersTT extends DigitTuple[],
ParameterPrimesTT extends DigitTuple[],
GodelEncoded extends WellFormedDigitTuple = [1]
> =
[ParametersTT, ParameterPrimesTT] extends [
[infer OnlyParameter extends WellFormedDigitTuple],
[infer OnlyPrime extends WellFormedDigitTuple]
]
? DigitalArithmetic.Tuple.Power<OnlyPrime, OnlyParameter> extends infer EncodedParameter extends WellFormedDigitTuple
? DigitalArithmetic.Tuple.Multiply<EncodedParameter, GodelEncoded> // degenerate case
: Fail<"Should be able to get a power">
: [ParametersTT, ParameterPrimesTT] extends [
[infer FirstParameter extends WellFormedDigitTuple, ...infer ButFirstParameters extends WellFormedDigitTuple[]],
[infer FirstPrime extends WellFormedDigitTuple, ...infer ButFirstPrimes extends WellFormedDigitTuple[]]
]
? DigitalArithmetic.Tuple.Power<FirstPrime, FirstParameter> extends infer EncodedParameter extends WellFormedDigitTuple
? EncodeTT<ButFirstParameters, ButFirstPrimes, DigitalArithmetic.Tuple.Multiply<EncodedParameter, GodelEncoded>>
: Fail<"unexpected failure to encode a parameter">
: Fail<"unexpected failure to destructure">;
export type AsDecodedNumbers<ValueWhenHalted extends number, ReturnValuePrimes extends PopulatedTupleOf<PrimeLessThan100>> =
[AsDigitTuple<ValueWhenHalted>, AsDigitTuples<ReturnValuePrimes>] extends [
infer ValueWhenHaltedT extends WellFormedDigitTuple,
infer ReturnValuePrimesTT extends DigitTuple[]
]
? DecodeTT<ValueWhenHaltedT, ReturnValuePrimesTT>
: Fail<"Unexpected failure to convert to digit tuples">;
export type DecodeTT<
ValueWhenHalted extends WellFormedDigitTuple,
ReturnValuePrimes extends DigitTuple[],
ReturnValues extends number[] = []
> =
ReturnValuePrimes extends []
? ReturnValues // degenerate case
: ReturnValuePrimes extends [
infer FirstReturnValuePrime extends WellFormedDigitTuple,
...infer RestReturnValuePrimes extends DigitTuple[]
]
? DigitalArithmetic.Tuple.FactorExponent<ValueWhenHalted, FirstReturnValuePrime> extends infer Factor extends WellFormedDigitTuple
? DecodeTT<ValueWhenHalted, RestReturnValuePrimes, [...ReturnValues, DigitalArithmetic.Tuple.AsNumber<Factor>]>
: Fail<"Unable to factor">
: Fail<"unexpected failure to match a list of return value primes">;
namespace TestDecodeTT {
type _0 = Expect<Equal<[], DecodeTT<[4, 2], []>>>;
type _1 = Expect<Equal<[3, 1], DecodeTT<[4, 0], [[2], [5]]>>>;
}
}
}
// ---------- Utility Types ----------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type PopulatedTupleOf<T> = [T, ...T[]];
// From “Fizz Buzz using the TypeScript Type System”
// https://nickangeli.com/posts/fizz-buzz-using-the-typescript-type-system/$0
type Length<A extends unknown[]> = A extends { length: infer L} ? L : never;
// ---------- Ways of signalling a failure to pattern match ----------
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
// ---------- Basic Arithmetic ----------
namespace DigitalArithmetic {
// basic arithmatic (addition, subtraction, multiplication, division)
// implemented as digitwise operations on tuples of digits
//
// roughly speaking, this works around TypeScript's type-level
// limit of 1,000 on tail-recursive operations by requiring Olog10n
// operations in most cases rather than On
// ---------- shared types ----------
type DigitZero = 0;
type DigitOneOrMore = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;
export type Digit = DigitZero | DigitOneOrMore;
export type DigitTuple = Digit[];
export type WellFormedDigitTuple = [DigitZero] | [DigitOneOrMore, ...DigitTuple];
export type Comparator = "<" | "=" | ">";
// ---------- Operations on numbers in the range 0..9 ----------
namespace Digit {
// Operations on single digits
// not ENTIRELY decoupled from
// opperations on tuples of digits,
// as some operations return a tuple of digits
export type LessThan = {
0: never,
1: 0,
2: 0 | 1,
3: 0 | 1 | 2,
4: 0 | 1 | 2 | 3,
5: 0 | 1 | 2 | 3 | 4,
6: 0 | 1 | 2 | 3 | 4 | 5,
7: 0 | 1 | 2 | 3 | 4 | 5 | 6,
8: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7,
9: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
};
export type Compare<A extends Digit, B extends Digit> =
Equal<A, B> extends true
? "="
: A extends LessThan[B]
? "<"
: ">"
namespace TestCompare {
type _0 = Expect<Equal<"=", Compare<0, 0>>>;
type _1 = Expect<Equal<"=", Compare<5, 5>>>;
type _2 = Expect<Equal<"=", Compare<9, 9>>>;
type _3 = Expect<Equal<"<", Compare<0, 9>>>;
type _5 = Expect<Equal<"<", Compare<0, 5>>>;
type _4 = Expect<Equal<"<", Compare<4, 9>>>;
type _6 = Expect<Equal<"<", Compare<4, 5>>>;
type _7 = Expect<Equal<">", Compare<9, 0>>>;
type _8 = Expect<Equal<">", Compare<6, 0>>>;
type _9 = Expect<Equal<">", Compare<9, 5>>>;
type _A = Expect<Equal<">", Compare<6, 5>>>;
// @ts-expect-error: has to be a digit
type _E0 = Compare<"D", 5>
// @ts-expect-error: has to be a digit
type _E1 = Compare<4, "E">
// @ts-expect-error: has to be a single digit
type _E2 = Compare<4, 42>
}
// AddTable[augend: digit][addend: Digit] -> (augend + addend): DigitTuple
type AddTable = {
0: { 0: [ 0], 1: [ 1], 2: [ 2], 3: [ 3], 4: [ 4], 5: [ 5], 6: [ 6], 7: [ 7], 8: [ 8], 9: [ 9] },
1: { 0: [ 1], 1: [ 2], 2: [ 3], 3: [ 4], 4: [ 5], 5: [ 6], 6: [ 7], 7: [ 8], 8: [ 9], 9: [1, 0] },
2: { 0: [ 2], 1: [ 3], 2: [ 4], 3: [ 5], 4: [ 6], 5: [ 7], 6: [ 8], 7: [ 9], 8: [1, 0], 9: [1, 1] },
3: { 0: [ 3], 1: [ 4], 2: [ 5], 3: [ 6], 4: [ 7], 5: [ 8], 6: [ 9], 7: [1, 0], 8: [1, 1], 9: [1, 2] },
4: { 0: [ 4], 1: [ 5], 2: [ 6], 3: [ 7], 4: [ 8], 5: [ 9], 6: [1, 0], 7: [1, 1], 8: [1, 2], 9: [1, 3] },
5: { 0: [ 5], 1: [ 6], 2: [ 7], 3: [ 8], 4: [ 9], 5: [1, 0], 6: [1, 1], 7: [1, 2], 8: [1, 3], 9: [1, 4] },
6: { 0: [ 6], 1: [ 7], 2: [ 8], 3: [ 9], 4: [1, 0], 5: [1, 1], 6: [1, 2], 7: [1, 3], 8: [1, 4], 9: [1, 5] },
7: { 0: [ 7], 1: [ 8], 2: [ 9], 3: [1, 0], 4: [1, 1], 5: [1, 2], 6: [1, 3], 7: [1, 4], 8: [1, 5], 9: [1, 6] },
8: { 0: [ 8], 1: [ 9], 2: [1, 0], 3: [1, 1], 4: [1, 2], 5: [1, 3], 6: [1, 4], 7: [1, 5], 8: [1, 6], 9: [1, 7] },
9: { 0: [ 9], 1: [1, 0], 2: [1, 1], 3: [1, 2], 4: [1, 3], 5: [1, 4], 6: [1, 5], 7: [1, 6], 8: [1, 7], 9: [1, 8] }
};
export type Add<A extends Digit, B extends Digit> = AddTable[A][B];
namespace TestAdd {
type _0 = Expect<Equal<[4], Add<0, 4>>>;
type _1 = Expect<Equal<[4], Add<4, 0>>>;
type _2 = Expect<Equal<[8], Add<4, 4>>>;
type _3 = Expect<Equal<[1, 2], Add<8, 4>>>;
}
// SubtractTable[minuend: digit][subtrahend: Digit] -> subtrahend <= minuend
// ? [minuend - subtrahend]: DigitTuple
// : [1, 10 + minuend - subtrahend]: DigitTuple
type SubtractTable = {
0: { 0: [ 0], 1: [1, 9], 2: [1, 8], 3: [1, 7], 4: [1, 6], 5: [1, 5], 6: [1, 4], 7: [1, 3], 8: [1, 2], 9: [1, 1] },
1: { 0: [ 1], 1: [ 0], 2: [1, 9], 3: [1, 8], 4: [1, 7], 5: [1, 6], 6: [1, 5], 7: [1, 4], 8: [1, 3], 9: [1, 2] },
2: { 0: [ 2], 1: [ 1], 2: [ 0], 3: [1, 9], 4: [1, 8], 5: [1, 7], 6: [1, 6], 7: [1, 5], 8: [1, 4], 9: [1, 3] },
3: { 0: [ 3], 1: [ 2], 2: [ 1], 3: [ 0], 4: [1, 9], 5: [1, 8], 6: [1, 7], 7: [1, 6], 8: [1, 5], 9: [1, 4] },
4: { 0: [ 4], 1: [ 3], 2: [ 2], 3: [ 1], 4: [ 0], 5: [1, 9], 6: [1, 8], 7: [1, 7], 8: [1, 6], 9: [1, 5] },
5: { 0: [ 5], 1: [ 4], 2: [ 3], 3: [ 2], 4: [ 1], 5: [ 0], 6: [1, 9], 7: [1, 8], 8: [1, 7], 9: [1, 6] },
6: { 0: [ 6], 1: [ 5], 2: [ 4], 3: [ 3], 4: [ 2], 5: [ 1], 6: [ 0], 7: [1, 9], 8: [1, 8], 9: [1, 7] },
7: { 0: [ 7], 1: [ 6], 2: [ 5], 3: [ 4], 4: [ 3], 5: [ 2], 6: [ 1], 7: [ 0], 8: [1, 9], 9: [1, 8] },
8: { 0: [ 8], 1: [ 7], 2: [ 6], 3: [ 5], 4: [ 4], 5: [ 3], 6: [ 2], 7: [ 1], 8: [ 0], 9: [1, 9] },
9: { 0: [ 9], 1: [ 8], 2: [ 7], 3: [ 6], 4: [ 5], 5: [ 4], 6: [ 3], 7: [ 2], 8: [ 1], 9: [ 0] }
};
export type Subtract<Minuend extends Digit, Subtrahend extends Digit> = SubtractTable[Minuend][Subtrahend];
namespace TestSubtract {
type _0 = Expect<Equal<[1, 6], Subtract<0, 4>>>;
type _1 = Expect<Equal<[4], Subtract<4, 0>>>;
type _2 = Expect<Equal<[0], Subtract<4, 4>>>;
type _3 = Expect<Equal<[4], Subtract<8, 4>>>;
}
// MultiplyTable[multiplier: digit][multiplicand: Digit] -> (multiplier · multiplicand): DigitTuple
type MultiplyTable = {
0: { 0: [ 0], 1: [ 0], 2: [ 0], 3: [ 0], 4: [ 0], 5: [ 0], 6: [ 0], 7: [ 0], 8: [ 0], 9: [ 0] },
1: { 0: [ 0], 1: [ 1], 2: [ 2], 3: [ 3], 4: [ 4], 5: [ 5], 6: [ 6], 7: [ 7], 8: [ 8], 9: [ 9] },
2: { 0: [ 0], 1: [ 2], 2: [ 4], 3: [ 6], 4: [ 8], 5: [1, 0], 6: [1, 2], 7: [1, 4], 8: [1, 6], 9: [1, 8] },
3: { 0: [ 0], 1: [ 3], 2: [ 6], 3: [ 9], 4: [1, 2], 5: [1, 5], 6: [1, 8], 7: [2, 1], 8: [2, 4], 9: [2, 7] },
4: { 0: [ 0], 1: [ 4], 2: [ 8], 3: [1, 2], 4: [1, 6], 5: [2, 0], 6: [2, 4], 7: [2, 8], 8: [3, 2], 9: [3, 6] },
5: { 0: [ 0], 1: [ 5], 2: [1, 0], 3: [1, 5], 4: [2, 0], 5: [2, 5], 6: [3, 0], 7: [3, 5], 8: [4, 0], 9: [4, 5] },
6: { 0: [ 0], 1: [ 6], 2: [1, 2], 3: [1, 8], 4: [2, 4], 5: [3, 0], 6: [3, 6], 7: [4, 2], 8: [4, 8], 9: [5, 4] },
7: { 0: [ 0], 1: [ 7], 2: [1, 4], 3: [2, 1], 4: [2, 8], 5: [3, 5], 6: [4, 2], 7: [4, 9], 8: [5, 6], 9: [6, 3] },
8: { 0: [ 0], 1: [ 8], 2: [1, 6], 3: [2, 4], 4: [3, 2], 5: [4, 0], 6: [4, 8], 7: [5, 6], 8: [6, 4], 9: [7, 2] },
9: { 0: [ 0], 1: [ 9], 2: [1, 8], 3: [2, 7], 4: [3, 6], 5: [4, 5], 6: [5, 4], 7: [6, 3], 8: [7, 2], 9: [8, 1] }
};
export type Multiply<A extends Digit, B extends Digit> = MultiplyTable[A][B];
namespace TestMultiplyTable {
type _0 = Expect<Equal<[0], Multiply<0, 4>>>;
type _1 = Expect<Equal<[0], Multiply<4, 0>>>;
type _2 = Expect<Equal<[1, 6], Multiply<4, 4>>>;
type _3 = Expect<Equal<[3, 2], Multiply<8, 4>>>;
}
}
// ---------- arithmatic operations on tuples of digits ----------
export namespace Tuple {
// operations on tuples of digits
export type TrimLeadingZeroes<T extends DigitTuple> =
T extends [0, ...infer Rest extends [Digit, ...DigitTuple]]
? TrimLeadingZeroes<Rest>
: T;
namespace TestTrimLeadingZeroes {
type _0 = Expect<Equal<[], TrimLeadingZeroes<[]>>>;
type _1 = Expect<Equal<[0], TrimLeadingZeroes<[0]>>>;
type _2 = Expect<Equal<[6], TrimLeadingZeroes<[6]>>>;
type _3 = Expect<Equal<[6], TrimLeadingZeroes<[0, 6]>>>;
type _4 = Expect<Equal<[6], TrimLeadingZeroes<[0, 0, 6]>>>;
type _5 = Expect<Equal<[0], TrimLeadingZeroes<[0, 0, 0]>>>;
type _6 = Expect<Equal<[1, 4], TrimLeadingZeroes<[0, 0, 0, 1, 4]>>>;
}
type NOT_DIGIT_STRING = Fail<"Not a digit string">;
type InnerFromDigitString<T extends string, ACC extends DigitTuple = []> =
T extends ""
? NOT_DIGIT_STRING
: T extends `${infer First extends Digit}${infer Rest extends string}`
? Rest extends ""
? [...ACC, First]
: InnerFromDigitString<Rest, [...ACC, First]>
: NOT_DIGIT_STRING;
export type FromNumber<T extends number> =
InnerFromDigitString<`${T}`> extends infer Result extends WellFormedDigitTuple
? Result
: NOT_DIGIT_STRING;
namespace TestFromNumber {
type _1 = Expect<Equal<[3], FromNumber<3>>>;
type _2 = Expect<Equal<[4, 2], FromNumber<42>>>;
type _4 = Expect<Equal<1, Length<FromNumber<9>>>>;
type _5 = Expect<Equal<3, Length<FromNumber<125>>>>;
type _1125 = Expect<Equal<[1, 1, 2, 5], FromNumber<1125>>>;
}
export type AsNumber<T extends DigitTuple, ACC extends string = ""> =
T extends [infer First extends Digit, ...infer ButFirst extends DigitTuple]
? AsNumber<ButFirst, `${ACC}${First}`>
: ACC extends `${infer N extends number}`
? N
: never;
namespace TestAsNumber {
type _0 = Expect<Equal<0, AsNumber<[0]>>>;
type _1 = Expect<Equal<6, AsNumber<[6]>>>;
type _2 = Expect<Equal<42, AsNumber<[4, 2]>>>;
type _3 = Expect<Equal<1125, AsNumber<[1, 1, 2, 5]>>>;
}
type NOT_DIGIT_TUPLES = Fail<"not digit tuples">;
type NOT_COMPARATOR = Fail<"not a comparator">;
type EXPECTED_NON_EMPTY_DIGIT_TUPLES = Fail<"expected non-empty digit tuples">;
export type Compare<AA extends DigitTuple, BB extends DigitTuple> =
[AA, BB] extends [[infer A1 extends Digit], [infer B1 extends Digit]] // one each
? Digit.Compare<A1, B1>
: [FromNumber<Length<AA>>, FromNumber<Length<BB>>] extends [infer AAL extends DigitTuple, infer BBL extends DigitTuple]
? Compare<AAL, BBL> extends infer C extends Comparator
? C extends "="
? [AA, BB] extends [[infer A1 extends Digit, ...infer AR extends DigitTuple], [infer B1 extends Digit, ...infer BR extends DigitTuple]]
? Digit.Compare<A1, B1> extends infer C2 extends Comparator
? C2 extends "="
? Compare<AR, BR>
: C2
: NOT_COMPARATOR
: EXPECTED_NON_EMPTY_DIGIT_TUPLES
: C // if AA is shorter than BB, AA must be less than BB for well-formed numbers
: NOT_COMPARATOR
: NOT_DIGIT_TUPLES
export type LessThan<AT extends DigitTuple, BT extends DigitTuple> =
Tuple.Compare<AT, BT> extends infer Result extends Comparator
? Result extends "<" ? true : false
: never
export type GreaterThan<AT extends DigitTuple, BT extends DigitTuple> =
Tuple.Compare<AT, BT> extends infer Result extends Comparator
? Result extends ">" ? true : false
: never
export type Add<Augend extends DigitTuple, Addend extends DigitTuple, Sum extends DigitTuple = []> =
Augend extends []
? [...Addend, ...Sum]
: Addend extends []
? [...Augend, ...Sum]
: [Augend, Addend] extends [
[...infer AugendButLast extends DigitTuple, infer AugendLast extends Digit],
[...infer AddendButLast extends DigitTuple, infer AddendLast extends Digit]
]
? Digit.Add<AugendLast, AddendLast> extends [...infer Carry extends DigitTuple, infer SumLastLast extends Digit]
? Add<AugendButLast, Carry> extends infer SumOfAugendButLastAndCarry extends DigitTuple
? Add<SumOfAugendButLastAndCarry, AddendButLast, [SumLastLast, ...Sum]>
: never
: never
: never;
namespace TestAdd {
type _0 = Expect<Equal<[4, 2], Add<[4, 2], []>>>;
type _1 = Expect<Equal<[4, 2], Add<[], [4, 2]>>>;
type _2 = Expect<Equal<[0], Add<[0], [0]>>>;
type _3 = Add<[4, 2], [0]>;
type _4 = Expect<Equal<[4, 2], Add<[0], [4, 2]>>>;
type _5 = Expect<Equal<[4, 8], Add<[6], [4, 2]>>>;
type _6 = Expect<Equal<[5, 0], Add<[8], [4, 2]>>>;
type _7 = Expect<Equal<[4, 2], Add<[4, 2], [0]>>>;
type _8 = Expect<Equal<[4, 8], Add<[4, 2], [6]>>>;
type _9 = Expect<Equal<[5, 0], Add<[4, 2], [8]>>>;
type _omega = Expect<Equal<[1, 2, 6, 2], Add<[1, 3, 7], [1, 1, 2, 5]>>>;
}
export type Subtract<Minuend extends DigitTuple, Subtrahend extends DigitTuple, Difference extends DigitTuple = []> =
Subtrahend extends []
? TrimLeadingZeroes<[...Minuend, ...Difference]>
: Minuend extends []
? Fail<"Subtrahend larger than the minuend">
: [Minuend, Subtrahend] extends [
[...infer MButLast extends DigitTuple, infer MLast extends Digit],
[...infer SButLast extends DigitTuple, infer SLast extends Digit]
]
? Digit.Subtract<MLast, SLast> extends [...infer CarryDigitTuple extends DigitTuple, infer DifferenceDigit extends Digit]
? Subtract<MButLast, Tuple.Add<CarryDigitTuple, SButLast>, [DifferenceDigit, ...Difference]>
: Fail<"Unable to SubtractDigitTuple">
: Fail<"Unable to SubtractDigit">;
namespace TestSubtract {
type _0 = Expect<Equal<[1, 2, 3], Subtract<[1, 2, 3], []>>>;
type _1 = Expect<Equal<[1, 2, 1], Subtract<[1, 2, 3], [2]>>>;
type _3 = Expect<Equal<[1, 1, 8], Subtract<[1, 2, 3], [5]>>>;
type _4 = Expect<Equal<[1, 0, 8], Subtract<[1, 2, 3], [1, 5]>>>;
type _5 = Expect<Equal<[9, 8], Subtract<[1, 2, 3], [2, 5]>>>;
}
type MultiplyDigitByTuple<
Multiplier extends Digit,
Multiplicand extends DigitTuple,
Padding extends 0[] = [],
ACC extends DigitTuple = [0]
> =
Multiplicand extends [...infer MultiplicandButLast extends DigitTuple, infer MultiplicandLast extends Digit]
? Digit.Multiply<Multiplier, MultiplicandLast> extends infer Product extends DigitTuple
? MultiplicandButLast extends []
? Tuple.Add<[...Product, ...Padding], ACC>
: MultiplyDigitByTuple<Multiplier, MultiplicandButLast, [...Padding, 0], Tuple.Add<[...Product, ...Padding], ACC>>
: never
: never;
namespace TestMultiplyDigitByTuple {
type _0 = Expect<Equal<[0], MultiplyDigitByTuple<0, [0]>>>;
type _1 = Expect<Equal<[0], MultiplyDigitByTuple<0, [6]>>>;
type _2 = Expect<Equal<[0], MultiplyDigitByTuple<0, [6]>>>;
type _4 = Expect<Equal<[6], MultiplyDigitByTuple<1, [6]>>>;
type _5 = Expect<Equal<[6], MultiplyDigitByTuple<2, [3]>>>;
type _6 = Expect<Equal<[8, 1], MultiplyDigitByTuple<9, [9]>>>;
type _7 = Expect<Equal<[6, 0], MultiplyDigitByTuple<5, [1, 2]>>>;
type _8 = Expect<Equal<[3, 3, 7, 5], MultiplyDigitByTuple<3, [1, 1, 2, 5]>>>;
}
export type Multiply<
Multiplier extends DigitTuple,
Multiplicand extends WellFormedDigitTuple,
Padding extends 0[] = [],
ACC extends DigitTuple = [0]
> =
Multiplier extends [...infer MultiplierButLast extends DigitTuple, infer MultiplierLast extends Digit]
? MultiplyDigitByTuple<MultiplierLast, Multiplicand> extends infer Product extends DigitTuple
? MultiplierButLast extends []
? Tuple.Add<[...Product, ...Padding], ACC>
: Multiply<MultiplierButLast, Multiplicand, [...Padding, 0], Tuple.Add<[...Product, ...Padding], ACC>>
: never
: never;
namespace TestMultiply {
type _0 = Expect<Equal<[0], Multiply<[0], [0]>>>;
type _1 = Expect<Equal<[0], Multiply<[0], [6]>>>;
type _2 = Expect<Equal<[0], Multiply<[0], [6]>>>;
type _4 = Expect<Equal<[6], Multiply<[1], [6]>>>;
type _5 = Expect<Equal<[6], Multiply<[2], [3]>>>;
type _6 = Expect<Equal<[8, 1], Multiply<[9], [9]>>>;
type _7 = Expect<Equal<[6, 0], Multiply<[5], [1, 2]>>>;
type _8 = Expect<Equal<[3, 3, 7, 5], Multiply<[3], [1, 1, 2, 5]>>>;
type _9 = Expect<Equal<[4, 0, 8], Multiply<[1, 2], [3, 4]>>>;
type _10 = Expect<Equal<[3, 3, 7, 5], Multiply<[1, 1, 2, 5], [3]>>>;
}
type DOES_NOT_DIVIDE = Fail<"Does not divide">;
// Find the shortest sequence of digits starting from the left end of the dividend, that the divisor goes into at least once.
// Relies on the property that an empty digit tuple compares as less than a well-formed digit tuple.
type SplitPartialDividend<Dividend extends DigitTuple, Divisor extends DigitTuple, Partial extends DigitTuple = []> =
LessThan<Partial, Divisor> extends true
? Dividend extends [infer First extends Digit, ...infer ButFirst extends DigitTuple]
? SplitPartialDividend<ButFirst, Divisor, [...Partial, First]>
: DOES_NOT_DIVIDE
: [Partial, Dividend];
namespace TestSplitPartialDividend {
type _0 = Expect<IsFail<SplitPartialDividend<[], [3]>>>;
type _1 = Expect<IsFail<SplitPartialDividend<[1], [3]>>>;
type _2 = Expect<Equal<[[3], []], SplitPartialDividend<[3], [3]>>>;
type _3 = Expect<Equal<[[1, 3], []], SplitPartialDividend<[1, 3], [3]>>>;
}
// A simple form of division that repeatedly subtracts the divisor from the
// dividend, until the divisor is greater than the dividend.
// the number of subtractions becomes a DigitTuple of the quotiend,
// and the leftover divisor becomes the remainder.
//
// This fails for operations requiring large quotients, which we fix
// by building EuclideanDivision below that chunks a DigitTuple's
// dividend into sequences of digits that are just long enough to
// represent a number as large as or larger than the divisor.
type LinearDivideWithRemainder<Dividend extends DigitTuple, Divisor extends DigitTuple, Quotient extends WellFormedDigitTuple = [0]> =
GreaterThan<Divisor, Dividend> extends true
? [Quotient, Dividend] // Dividend is now the remainder
: Tuple.Subtract<Dividend, Divisor> extends infer Subtracted extends DigitTuple
? LinearDivideWithRemainder<Subtracted, Divisor, Tuple.Add<Quotient, [1]>>
: Fail<"Unable to SubtractDigitTuple">;
namespace TestLinearDivideWithRemainder {
type _0 = Expect<Equal<[[0], [1]], LinearDivideWithRemainder<[1], [2]>>>;
type _1 = Expect<Equal<[[3], [1]], LinearDivideWithRemainder<[7], [2]>>>;
type _2 = Expect<Equal<[[8], [1]], LinearDivideWithRemainder<[1, 7], [2]>>>;
type _3 = Expect<Equal<[[2, 2, 5], [0]], LinearDivideWithRemainder<[1, 1, 2, 5], [5]>>>;
}
type AsManyZeroesAs<T extends DigitTuple, P extends DigitTuple = []> =
T extends [Digit, ...infer Rest extends DigitTuple]
? AsManyZeroesAs<Rest, [0, ...P]>
: P;
namespace TestAsManyZeroesAs {
type _0 = Expect<Equal<[], AsManyZeroesAs<[]>>>;
type _1 = Expect<Equal<[0], AsManyZeroesAs<[0]>>>;
type _2 = Expect<Equal<[0], AsManyZeroesAs<[3]>>>;
type _3 = Expect<Equal<[0, 0, 0], AsManyZeroesAs<[1, 2, 3]>>>;
}
// EuclideanDivide<Dividend, Divisor> -> [Quotient, Remainder]
export type EuclideanDivide<Dividend extends DigitTuple, Divisor extends DigitTuple, Quotient extends DigitTuple = [0]> =
Divisor extends [0] | []
? Fail<"Divide by zero">
: SplitPartialDividend<Dividend, Divisor> extends [infer Partial extends DigitTuple, infer Rest extends DigitTuple]
? LinearDivideWithRemainder<Partial, Divisor> extends [infer PartialQuotient extends DigitTuple, infer PartialRemainder extends DigitTuple]
? [
Tuple.TrimLeadingZeroes<[...PartialRemainder, ...Rest]>,
Tuple.Add<[...PartialQuotient, ...AsManyZeroesAs<Rest>], Quotient>
] extends [infer NextDividend extends DigitTuple, infer NextQuotient extends DigitTuple]
? EuclideanDivide<NextDividend, Divisor, NextQuotient>
: Fail<"Unable to compute NextDividend and NextQuotient">
: Fail<"Unable to LinearDivideWithRemainder">
: SplitPartialDividend<Dividend, Divisor> extends DOES_NOT_DIVIDE
? [Quotient, Dividend]
: Fail<"Unable to SplitPartialDividend">;
namespace TestEuclideanDivide {
type _0 = Expect<Equal<[[0], [0]], EuclideanDivide<[0], [1]>>>;
type _1 = Expect<Equal<[[0], [0]], EuclideanDivide<[0], [1, 0, 0]>>>;
type _2 = Expect<Equal<[[0], [2]], EuclideanDivide<[2], [3]>>>;
type _3 = Expect<Equal<[[4], [0]], EuclideanDivide<[1, 2], [3]>>>;
type _4 = Expect<Equal<[[2, 2, 5], [0]], EuclideanDivide<[1, 1, 2, 5], [5]>>>;
type _5 = Expect<Equal<[[9], [0]], EuclideanDivide<[2, 2, 5], [2, 5]>>>;
type _6 = Expect<Equal<[[9, 0, 0, 9, 0, 0, 9], [0]], EuclideanDivide<[2, 2, 5, 2, 2, 5, 2, 2, 5], [2, 5]>>>;
type _7 = Expect<Equal<[[0], [0]], EuclideanDivide<[0], [1]>>>;
type _01 = Expect<Equal<[[9, 0], [2]], EuclideanDivide<[2, 2, 5, 2], [2, 5]>>>;
type _02 = EuclideanDivide<[2, 2, 5, 2, 2], [2, 5]>;
type _10 = Expect<IsFail<EuclideanDivide<[1], [0]>>>;
type _11 = Expect<IsFail<EuclideanDivide<[1], []>>>;
}
export type DivideEvenly<Dividend extends DigitTuple, Divisor extends DigitTuple> =
EuclideanDivide<Dividend, Divisor> extends [infer Quotient extends WellFormedDigitTuple, [0]]
? Quotient
: Fail<"Does not divide evenly">;
// See: https://raganwald.com/2015/12/20/an-es6-program-to-compute-fibonacci.html
export type Power<Base extends WellFormedDigitTuple, Exponent extends WellFormedDigitTuple> =
[Base, Exponent] extends [[0], [0]]
? Fail<"0^0"> // undefined
: Base extends [0]
? [0] // 0^n => 0
: Exponent extends [0]
? [1] // n^0 => 1
: Exponent extends [1]
? Base // degenerate: anything raised to 1 is itself
: EuclideanDivide<Exponent, [2]> extends [infer HalfExponentRoundedDown extends WellFormedDigitTuple, [infer Remainder extends 0 | 1]]
? Power<Base, HalfExponentRoundedDown> extends infer Halves extends WellFormedDigitTuple
? Remainder extends 0
? Multiply<Halves, Halves>
: Multiply<Multiply<Halves, Halves>, Base>
: Fail<"unable to compute halves">
: Fail<"unable to divide rounding down">;
namespace TestPower {
type _0 = Expect<IsFail<Power<[0], [0]>>>;
type _1 = Expect<Equal<[0], Power<[0], [4, 2]>>>;
type _2 = Expect<Equal<[1], Power<[6], [0]>>>;
type _3 = Expect<Equal<[1], Power<[1], [1]>>>;
type _4 = Expect<Equal<[2], Power<[2], [1]>>>;
type _5 = Expect<Equal<[4], Power<[2], [2]>>>;
type _6 = Expect<Equal<[8], Power<[2], [3]>>>;
type _7 = Expect<Equal<[1, 6], Power<[2], [4]>>>;
type _8 = Expect<Equal<[3, 2], Power<[2], [5]>>>;
}
// belongs here because it loosely related to Power
export type FactorExponent<Compound extends WellFormedDigitTuple, Prime extends WellFormedDigitTuple, Exponent extends WellFormedDigitTuple = [0]> =
DivideEvenly<Compound, Prime> extends infer Quotient extends WellFormedDigitTuple
? FactorExponent<Quotient, Prime, Add<Exponent, [1]>>
: Exponent;
namespace TestFactorExponent {
type _0 = Expect<Equal<[3], FactorExponent<[8], [2]>>>;
type _1 = Expect<Equal<[3], FactorExponent<[4, 0], [2]>>>;
type _2 = Expect<Equal<[2], FactorExponent<[3, 3, 8], [1, 3]>>>;
}
}
// ---------- exportable operations on numbers ----------
export type AsDigitTuple<T extends number> = Tuple.FromNumber<T>;
export type Compare<A extends number, B extends number> =
[Tuple.FromNumber<A>, Tuple.FromNumber<B>] extends [infer AT extends DigitTuple, infer BT extends DigitTuple]
? Tuple.Compare<AT, BT>
: never;
namespace TestCompare {
type _0 = Expect<Equal<"=", Compare<6, 6>>>;
type _1 = Expect<Equal<"<", Compare<6, 7>>>;
type _2 = Expect<Equal<">", Compare<8, 7>>>;
type _3 = Expect<Equal<"=", Compare<26, 26>>>;
type _4 = Expect<Equal<"<", Compare<26, 27>>>;
type _5 = Expect<Equal<">", Compare<81, 71>>>;
type _6 = Expect<Equal<"<", Compare<88, 111>>>;
type _7 = Expect<Equal<">", Compare<1125, 99>>>;
}
export type LessThan<A extends number, B extends number> =
Compare<A, B> extends infer Result extends Comparator
? Result extends "<" ? true : false
: never
namespace TestLessThan {
type _0 = Expect<LessThan<0, 1124>>;
type _1 = Expect<IsFail<LessThan<1, -1>>>;
type _2 = Expect<IsFail<LessThan<-1, 2>>>;
type _3 = Expect<Equal<false, LessThan<10000, 1124>>>;
}
export type Add<A extends number, B extends number> =
[Tuple.FromNumber<A>, Tuple.FromNumber<B>] extends [infer AT extends WellFormedDigitTuple, infer BT extends WellFormedDigitTuple]
? Tuple.Add<AT, BT> extends infer Sum extends WellFormedDigitTuple
? Tuple.AsNumber<Sum>
: never
: never;
namespace TestAdd {
type _0 = Expect<Equal<0, Add<0, 0>>>;
type _1 = Expect<Equal<1, Add<0, 1>>>;
type _2 = Expect<Equal<1, Add<1, 0>>>;
type _3 = Expect<Equal<2, Add<1, 1>>>;
type _4 = Expect<Equal<11125, Add<10000, 1125>>>;
}
export type Subtract<Minuend extends number, Subtrahend extends number> =
[Tuple.FromNumber<Minuend>, Tuple.FromNumber<Subtrahend>] extends [infer MT extends WellFormedDigitTuple, infer ST extends WellFormedDigitTuple]
? Tuple.Subtract<MT, ST> extends infer Difference extends WellFormedDigitTuple
? Tuple.AsNumber<Difference>
: never
: never;
namespace TestSubtract {
type _0 = Expect<Equal<123, Subtract<123, 0>>>;
type _1 = Expect<Equal<121, Subtract<123, 2>>>;
type _3 = Expect<Equal<118, Subtract<123, 5>>>;
type _4 = Expect<Equal<108, Subtract<123, 15>>>;
type _5 = Expect<Equal<98, Subtract<123, 25>>>;
}
export type Multiply<A extends number, B extends number> =
[Tuple.FromNumber<A>, Tuple.FromNumber<B>] extends [infer AT extends WellFormedDigitTuple, infer BT extends WellFormedDigitTuple]
? Tuple.Multiply<AT, BT> extends infer Product extends WellFormedDigitTuple
? Tuple.AsNumber<Product>
: never
: never;
namespace TestMultiply {
type _0 = Expect<Equal<0, Add<0, 0>>>;
type _1 = Expect<Equal<1, Add<0, 1>>>;
type _2 = Expect<Equal<1, Add<1, 0>>>;
type _3 = Expect<Equal<2, Add<1, 1>>>;
type _4 = Expect<Equal<11125, Add<10000, 1125>>>;
}
export type DivideEvenly<Dividend extends number, Divisor extends number> =
[Tuple.FromNumber<Dividend>, Tuple.FromNumber<Divisor>] extends [infer DividendT extends DigitTuple, infer DivisorT extends DigitTuple]
? Tuple.DivideEvenly<DividendT, DivisorT> extends infer Quotient extends WellFormedDigitTuple
? Tuple.AsNumber<Quotient>
: Fail<"does not divide evenly">
: Fail<"Unable to derive gigit tuples">;
namespace TestDivideEvenly {
type _0 = Expect<IsFail<DivideEvenly<0, 0>>>;
type _1 = Expect<IsFail<DivideEvenly<1, 0>>>;
type ___ = DivideEvenly<0, 1>
type _2 = Expect<Equal<0, DivideEvenly<0, 1>>>;
type _3 = Expect<Equal<0, DivideEvenly<0, 42>>>;
type _4 = Expect<IsFail<DivideEvenly<1, 2>>>;
type _5 = Expect<Equal<1, DivideEvenly<2, 2>>>;
type _6 = Expect<Equal<2, DivideEvenly<2, 1>>>;
type _7 = Expect<IsFail<DivideEvenly<3, 2>>>;
type _8 = Expect<IsFail<DivideEvenly<5, 2>>>;
type _9 = Expect<IsFail<DivideEvenly<5, 3>>>;
type _10 = DivideEvenly<1125, 3>;
}
export type Power<Base extends number, Exponent extends number> =
[Tuple.FromNumber<Base>, Tuple.FromNumber<Exponent>] extends [infer BaseT extends WellFormedDigitTuple, infer ExponentT extends WellFormedDigitTuple]
? Tuple.Power<BaseT, ExponentT> extends infer BaseToPowerOfExponent extends WellFormedDigitTuple
? Tuple.AsNumber<BaseToPowerOfExponent>
: never
: never;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment