Hone logo
Hone
Problems

Type-Level Arithmetic Interpreter

This challenge asks you to build a rudimentary arithmetic interpreter that operates entirely at the TypeScript type level. You'll leverage advanced TypeScript features like conditional types, mapped types, and infer to represent and manipulate numbers and basic arithmetic operations as types. This is a fantastic exercise for understanding the expressive power of TypeScript's type system.

Problem Description

Your task is to create a set of TypeScript types that can represent and evaluate simple arithmetic expressions. You need to define types that can:

  1. Represent Numbers: Create a way to represent non-negative integers (e.g., 0, 1, 2, ...).
  2. Represent Arithmetic Operations: Define types for addition, subtraction, and multiplication.
  3. Evaluate Expressions: Create a type that takes a representation of an arithmetic expression and returns the type representing its evaluated result.

Key Requirements:

  • Number Representation: Numbers should be represented in a way that allows for arithmetic operations. A common approach is using a tuple of a specific length, where the length corresponds to the number. For instance, type Zero = []; type One = [any]; type Two = [any, any];
  • Operation Types: Define generic types for Add, Subtract, and Multiply. These types should accept two "number" types as parameters and resolve to a new "number" type representing the result.
  • Expression Type: Design a type Evaluate<Expression> that can recursively interpret a structured expression type. The Expression type should be able to represent either a literal number or an operation applied to other expressions.
  • Non-negative Integers: Your interpreter should handle non-negative integers. Subtraction resulting in a negative number is an edge case to consider.

Expected Behavior:

The Evaluate type should take an expression and return a type that represents the numerical result. For example, if you define type MyExpression = Add<One, Two>;, then Evaluate<MyExpression> should resolve to a type representing the number 3.

Edge Cases:

  • Subtraction resulting in negative numbers: How will you handle Subtract<One, Two>? You might choose to represent negative numbers as a distinct type or have subtraction yield a specific error type if the result is negative. For this challenge, let's aim to gracefully handle it by representing the result of subtraction that would be negative as Never or a custom NegativeResult type.
  • Zero: Ensure operations involving zero are correctly handled.
  • Large Numbers: While technically possible, the type system can become slow and hit recursion limits with very large numbers. Focus on correctness for small to moderate numbers.

Examples

Example 1: Representing and evaluating a simple addition.

// Define number types
type Zero = [];
type One = [any];
type Two = [any, any];
type Three = [any, any, any];

// Define operations
type Add<A, B> = [...A, ...B]; // Concatenating tuples represents addition

// Define expression structure
type Expression = { type: 'literal', value: number } | { type: 'add', left: Expression, right: Expression };

// Define the interpreter
type Evaluate<E> =
  E extends { type: 'literal', value: infer V } ? V extends number ? TupleFromNumber<V> : never // Helper to convert number to tuple
  : E extends { type: 'add', left: infer L, right: infer R } ? Add<Evaluate<L>, Evaluate<R>>
  : never;

// Helper to convert a number literal to a tuple (for evaluation)
// You'll need to implement this!
type TupleFromNumber<N extends number, Acc extends any[] = []> =
  Acc['length'] extends N ? Acc : TupleFromNumber<N, [...Acc, any]>;

// Example usage (this part is conceptual, as TS doesn't execute types directly)
type Num1 = TupleFromNumber<1>; // Represents 'One'
type Num2 = TupleFromNumber<2>; // Represents 'Two'

type AddExpr = { type: 'add', left: { type: 'literal', value: 1 }, right: { type: 'literal', value: 2 } };
type ResultTuple = Evaluate<AddExpr>; // Should resolve to a tuple of length 3

// How to assert the length at the type level (for verification)
type IsLengthThree<T> = T extends [any, any, any] ? true : false;
type Verification = IsLengthThree<ResultTuple>; // Should be `true`

Explanation:

This example demonstrates how to define number representations (via tuples), an Add operation (tuple concatenation), and an Evaluate type that can interpret a structured expression. The TupleFromNumber helper is crucial for bridging the gap between number literals and our tuple-based number representation. The final Verification type shows how you might check the result.

Example 2: Handling subtraction.

// Assuming number types and Add are defined as above
type Zero = [];
type One = [any];
type Two = [any, any];

// A type to represent negative results (or use Never)
type NegativeResult = { __negative: true }; // Or simply use `never`

// Subtraction - more complex. Need to ensure we don't go below zero.
// This is a simplified approach; a full implementation would be more involved.
type Subtract<A extends any[], B extends any[]> =
  B extends [infer _, ...infer RestB]
    ? A extends [infer _, ...infer RestA]
      ? Subtract<RestA, RestB>
      : NegativeResult // B is longer than A, result would be negative
    : A; // B is exhausted, A is the remaining length

// Expression type for subtraction
type SubtractExpression = { type: 'subtract', left: Expression, right: Expression };

// Update Evaluate for subtraction
type Evaluate<E> =
  E extends { type: 'literal', value: infer V } ? TupleFromNumber<V> // Assuming TupleFromNumber is implemented
  : E extends { type: 'add', left: infer L, right: infer R } ? Add<Evaluate<L>, Evaluate<R>>
  : E extends { type: 'subtract', left: infer L, right: infer R } ? Subtract<Evaluate<L>, Evaluate<R>>
  : never;

// Example usage
type SubExpr = { type: 'subtract', left: { type: 'literal', value: 2 }, right: { type: 'literal', value: 1 } };
type SubResultTuple = Evaluate<SubExpr>; // Should resolve to a tuple of length 1

type NegExpr = { type: 'subtract', left: { type: 'literal', value: 1 }, right: { type: 'literal', value: 2 } };
type NegResultTuple = Evaluate<NegExpr>; // Should resolve to `NegativeResult` (or `never`)

type IsLengthOne<T> = T extends [any] ? true : false;
type IsNegative<T> = T extends NegativeResult ? true : false;

type VerifySub = IsLengthOne<SubResultTuple>; // Should be `true`
type VerifyNeg = IsNegative<NegResultTuple>; // Should be `true`

Explanation:

This example introduces the Subtract operation. The type-level subtraction is tricky. A common approach is to "peel off" elements from both number-representation tuples. If one tuple runs out before the other, you know the result. We define NegativeResult to handle cases where the subtraction would yield a negative number.

Example 3: Implementing Multiplication.

// Assuming number types and operations are defined

// Multiplication is usually implemented via repeated addition
// Multiply<A, B> means Add<A, Add<A, ... B times>>
// This is where recursion and potentially mapped types become very useful.
// This can get complex quickly! A common way is to generate a tuple of the second
// number's length, and for each element in that tuple, add the first number.

type Multiply<A extends any[], B extends any[]> =
  B extends [infer _, ...infer RestB]
    ? Add<A, Multiply<A, RestB>> // Recursively add A, B times
    : Zero; // Base case: when B is empty, the result is Zero

// Update Evaluate to include multiplication
type Evaluate<E> =
  E extends { type: 'literal', value: infer V } ? TupleFromNumber<V>
  : E extends { type: 'add', left: infer L, right: infer R } ? Add<Evaluate<L>, Evaluate<R>>
  : E extends { type: 'subtract', left: infer L, right: infer R } ? Subtract<Evaluate<L>, Evaluate<R>>
  : E extends { type: 'multiply', left: infer L, right: infer R } ? Multiply<Evaluate<L>, Evaluate<R>>
  : never;


// Expression type for multiplication
type MultiplyExpression = { type: 'multiply', left: Expression, right: Expression };

// Example usage
type MultExpr = { type: 'multiply', left: { type: 'literal', value: 2 }, right: { type: 'literal', value: 3 } };
type MultResultTuple = Evaluate<MultExpr>; // Should resolve to a tuple of length 6

type IsLengthSix<T> = T extends [any, any, any, any, any, any] ? true : false;
type VerifyMult = IsLengthSix<MultResultTuple>; // Should be `true`

Explanation:

Multiplication at the type level is often achieved by repeatedly applying addition. Multiply<A, B> can be seen as adding A to itself B times. This requires a recursive definition within the Multiply type itself.

Constraints

  • Number Range: Your interpreter should correctly handle non-negative integers from 0 up to 12. Exceeding this limit might lead to TypeScript's recursion depth limits and slow compile times.
  • Expression Structure: Expressions will adhere to the defined JSON-like structure (e.g., literal, add, subtract, multiply). No malformed expressions will be provided.
  • Performance: While type-level computation is inherently slower than runtime computation, your types should resolve within a reasonable time for the given number range. Excessive reliance on deeply nested, non-terminating recursion will be penalized.
  • Type Safety: All operations must be strictly type-checked by TypeScript.

Notes

  • This challenge heavily relies on advanced TypeScript features such as conditional types (extends), inference (infer), and variadic tuple types (...).
  • Consider how you will convert a raw number literal (like 2) into your tuple-based representation and vice versa, especially within the Evaluate type. You'll likely need helper types for this.
  • The core of the problem lies in designing the recursive Evaluate type and ensuring your arithmetic operation types correctly manipulate the chosen number representation.
  • Think about how you can verify the results of your type-level computation. You might need additional helper types to assert the length of the resulting tuple or check for specific negative result types.
  • For subtraction, deciding on a clear representation for negative results (e.g., never, a custom marker type) is important. For this challenge, aiming for never or a specific NegativeResult type is acceptable.
Loading editor...
typescript