ts-type-level-scheme

Type-level Scheme interpreter in TypeScript.

Playground

import type { Scheme } from "ts-type-level-scheme";

type Reverse<array extends unknown[]> = [
  "begin",

  [
    "define",
    ["reverse", "rest", "result"],

    [
      "if",
      ["null?", "rest"],
      "result",
      ["reverse", ["cdr", "rest"], ["cons", ["car", "rest"], "result"]]
    ]
  ],

  ["reverse", ["quote", array], ["quote", []]]
];

type reversed = Scheme<Reverse<[1, "a", true, null, undefined]>>;
//   ^? type reversed = [undefined, null, true, "a", 1]

import type { Scheme } from "ts-type-level-scheme";

type Fib<n extends number> = [
  "begin",

  [
    "define",
    ["fib", "n"],

    [
      "cond",
      [["=", "n", 0], 0],
      [["=", "n", 1], 1],
      ["else", ["+", ["fib", ["-", "n", 1]], ["fib", ["-", "n", 2]]]]
    ]
  ],

  ["fib", n]
];

type fib_0 = Scheme<Fib<0>>;
//   ^? type fib_0 = 0
type fib_1 = Scheme<Fib<1>>;
//   ^? type fib_1 = 1
type fib_2 = Scheme<Fib<2>>;
//   ^? type fib_2 = 1
type fib_3 = Scheme<Fib<3>>;
//   ^? type fib_3 = 2
type fib_4 = Scheme<Fib<4>>;
//   ^? type fib_4 = 3
type fib_5 = Scheme<Fib<5>>;
//   ^? type fib_5 = 5
type fib_6 = Scheme<Fib<6>>;
//   ^? type fib_6 = 8

more examples

Limitations

• set!, set-car!, and set-cdr! are not implemented.
• Only the following special forms are available:
  • quote
  • define
  • if
  • lambda
  • cond
  • begin
• Only natural numbers including zero are supported for numbers.
• Due to the limitation of tsc, heavy computation will result in TS2589 error.
• Only the following primitive procedures can be used:
  • +
  • -
  • *
  • /
  • remainder
  • =
  • <
  • <=
  • >
  • >=
  • and
  • or
  • null?
  • cons
  • car
  • cdr
  • list
  • append

License

MIT