TypeScriptで型レベルScheme
2024/01/02
TypeScriptの型システムでSchemeインタプリタを作りました。
できること
趣味のために作ったので実用性は全く考えていませんが、type-challengesをいくつか解くくらいはできます。
Reverse（難易度：Medium）
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 res = Scheme<Reverse<[1, "a", true, null, undefined]>>;
// ^? type res = [undefined, null, true, "a", 1]Slice（難易度：Extreme）
import type { Scheme } from "ts-type-level-scheme";
type Slice<
array extends unknown[],
start extends number,
end extends number
> = [
"begin",
[
"define",
["slice", "array", "start", "end"],
[
"define",
["iter", "rest", "result", "idx"],
[
"if",
["null?", "rest"],
"result",
[
"if",
["and", ["<=", "start", "idx"], ["<", "idx", "end"]],
[
"iter",
["cdr", "rest"],
["append", "result", ["list", ["car", "rest"]]],
["+", "idx", 1]
],
["iter", ["cdr", "rest"], "result", ["+", "idx", 1]]
]
]
],
["iter", "array", ["quote", []], 0]
],
["slice", ["quote", array], start, end]
];
type res = Scheme<Slice<[1, 2, 3, 4, 5], 2, 4>>;
// ^? type res = [3, 4]Sort（難易度：Extreme）
挿入ソートです。
import type { Scheme } from "ts-type-level-scheme";
type Sort<array extends unknown[], desc extends boolean = false> = [
"begin",
[
"define",
["sort", "array", "desc"],
[
"define",
["insert", "array", "val"],
[
"define",
["iter", "rest", "result"],
[
"cond",
[["null?", "rest"], ["append", "result", ["list", "val"]]],
[
[["if", "desc", ">", "<"], "val", ["car", "rest"]],
["append", ["append", "result", ["list", "val"]], "rest"]
],
[
"else",
[
"iter",
["cdr", "rest"],
["append", "result", ["list", ["car", "rest"]]]
]
]
]
],
["iter", "array", ["quote", []]]
],
[
"define",
["iter", "rest", "result"],
[
"if",
["null?", "rest"],
"result",
["iter", ["cdr", "rest"], ["insert", "result", ["car", "rest"]]]
]
],
["iter", "array", ["quote", []]]
],
["sort", ["quote", array], desc]
];
type res1 = Scheme<Sort<[]>>;
// ^? type res1 = []
type res2 = Scheme<Sort<[1]>>;
// ^? type res2 = [1]
type res3 = Scheme<Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>>;
// ^? type res3 = [2, 4, 5, 6, 6, 6, 7, 8, 9]
type res4 = Scheme<Sort<[3, 2, 1], true>>;
// ^? type res4 = [3, 2, 1]
type res5 = Scheme<Sort<[3, 2, 0, 1, 0, 0, 0], true>>;
// ^? type res5 = [3, 2, 1, 0, 0, 0, 0]このように
複雑な型演算であってもSchemeでお手軽に実現できます。
実行時エラー
コードがおかしい場合はそれなりにエラーが返ります。
import type { Scheme } from "ts-type-level-scheme";
type error1 = Scheme<"foo">;
// ^? type error1 = "Unbound variable: foo"
type error2 = Scheme<["begin", ["define", "a", 1], ["a"]]>;
// ^? type error2 = "Apply: unknown procedure type"
type error3 = Scheme<undefined>;
// ^? type error3 = "Eval: unknown expression type"
type error4 = Scheme<["cond"]>;
// ^? type error4 = "CondToIf: clauses are required"あくまでそれなりなので、変なエラーや型が返る場合もあります。しょうがないね。
良かった点
まず、自動フォーマットが良かったです。先程のコードはすべてPrettierがフォーマットした結果だったのですが、Schemeのコードとして見てもわりと読みやすいと思います。そのため、コーディングの体験は意外に良かったです。シンボルをいちいちダブルクォートして,を打つのは面倒でしたが。
次に、レキシカルスコープによるブロック構造のありがたみを（改めて）実感しました。ローカルな手続きをブロック内に定義できるのは、素の型パズルと比べるとだいぶ体験が良かったです。
制限
以下の特殊形式のみ使用できます。
quotedefineiflambdacondbegin
特に、set!、set-car!、set-cdr!といった、代入を行う特殊形式はサポートしていません。実装が大変そうだったのと、あまり必要になる感じがしなかったからです。
数値は、0を含む自然数のみ使用できます。TypeScriptの型で素数を求めたいで作ったやつを組み込みました。TypeScriptの型で全加算器から浮動小数点数，そして√2では、負の数や小数も作りましたが、そこまでは必要ないだろうと思って組み込みませんでした。
以下の基本手続きのみ使用できます。
+-*/remainder=<<=>>=andornull?conscarcdrlistappend
TS2589（Type instantiation is excessively deep and possibly infinite.）により、あまり重い計算はできません。
どのくらい重い計算ができるのかやってみます
フィボナッチ数を計算してみます。
import type { Scheme } from "ts-type-level-scheme";
type Fib<n extends number> = [
"begin",
[
"define",
["fib", "n"],
[
"define",
["iter", "a", "b", "cnt"],
[
"if",
["=", "cnt", 0],
"b",
["iter", ["+", "a", "b"], "a", ["-", "cnt", 1]]
]
],
["iter", 1, 0, "n"]
],
["fib", n]
];
type fib_19 = Scheme<Fib<19>>;
// ^? type fib_19 = 418119番目のフィボナッチ数までは求められますが、20番目を求めようとするとエラーになります。
カンですが、主に内部の数値表現がネックになっているっぽいので、2進表現や10進表現を実装すればもっと計算できるようになると思います。カンですが。
実装
SICP（計算機プログラムの構造と解釈）のやつを愚直に実装しただけなので、あまり書くことがありません。
それでも工夫が必要だったのは、環境の参照を実現する部分でした。例えば、クロージャは外側の環境への参照を保持する必要があります。しかし、TSの型システムには型への参照というものがありません（そらそう）。
したがって、すべての環境を配列として保持し、その添字を参照として扱うことにしました。この配列をevalとapplyで持ち回り、必要なときに参照することにしました。
これは代入操作を実装しなかった理由にも関係します。例えばset-cdr!を導入してしまうと、これを以下のように使うことで循環リストを作れてしまいます。
(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x)) ) ) (define (make-cycle x) (set-cdr! (last-pair x) x) x )出典：SICP（計算機プログラムの構造と解釈）、練習問題3.12および3.13
しかし前述の通り、内部的に参照を表現するのはちょっと面倒です。おそらくペアを保存するメモリみたいなものを自前で作ってeval、applyで持ち回ればいけると思うのですがヤバいです。
まぁ代入なんて無くてもプログラミングできるよねってことでサボりました。
感想
2023年12月31日16時くらいからやんわりと書き始め、2024年1月1日15時くらいに完成しました。evalを書きながら年を越したのは初めての体験でしたが、それなりにコードが動いて満足です。
毎度のことですが、TS2589の限界を突破したりエラーを抑制するために、kgtkrさんのハックやsusisuさんのハックを使わせていただきました。また、ビルドの設定周りでsusisu/typefuckを参考にさせていただきました。なんか記事のタイトルまで似てしまいましたが、これは偶然です。
あまり脳を使わずに書いたのでたぶんバグがあります。見つけたらissueとかで教えてもらえると嬉しいです。
ありがとうございました。
