Open22
TypeScript で Lisp 処理系を作ってみる（Make a Lisp）
プログラミングをするパンダいくつかのブログを読むとと、Lisp の処理系の作り方を学ぶには Make a Lisp という学習用の Lisp 方言を実装するレポジトリを参考にするといいとのこと
これを TypeScript で実装してみる
環境構築が面倒なので Deno でやってみる
プログラミングをするパンダガイドを上から読んでいく
プログラミングをするパンダstep 0
Deno でコマンドラインから値を取るにはこれを使う
プログラミングをするパンダreadline を使わないといけなかった
async function main() {
for await (const line of readline(Deno.stdin)) {
const input = new TextDecoder().decode(line)
if (input == null) {
break;
}
if (input === "") {
continue;
}
console.log(rep(input))
}
}
await main()
参考
プログラミングをするパンダこれも間違ってた。Lisp 処理系に集中したいので結局ChatGPTに「deno で repl を作りたいです。一番シンプルな作り方は何？」と聞いた。これでテスト通った
async function main() {
const reader = Deno.stdin.readable.getReader();
const decoder = new TextDecoder();
while(true) {
await Deno.stdout.write(new TextEncoder().encode("user> "))
const {value, done} = await reader.read()
if (done || !value) {
break
}
const input = decoder.decode(value).trim()
if (input == null) {
break;
}
if (input === "") {
continue;
}
console.log(rep(input))
}
}
await main()
step1
途中までできた
class Reader {
position: number = 0
constructor(private readonly tokens: string[]) {
}
next() {
const current = this.tokens[this.position]
this.position += 1
return current
}
peek() {
return this.tokens[this.position]
}
}
export function read_str(val: string) {
const tokens = tokenize(val)
const reader = new Reader(tokens)
return read_form(reader)
}
const regexp = /[\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"?|;.*|[^\s\[\]{}('"`,;)]*)/g
function tokenize(val: string): string[] {
const tokens: string[] = []
for (const match of val.matchAll(regexp)) {
const token = match[1]
if (token === '') {
continue
}
tokens.push(token)
}
return tokens
}
// token に応じて処理を変える
function read_form(reader: Reader) {
const currentToken = reader.peek()
switch (currentToken) {
case '(':
reader.next()
return read_list(reader)
default:
reader.next()
return read_atom(reader)
}
}
// list の中身を読み取る
function read_list(reader: Reader) {
const list = []
while (true) {
const nextToken = read_form(reader)
if (nextToken === ')') {
break
}
list.push(nextToken)
}
return list
}
const isNumberString = (val: string) => !isNaN(Number(val))
// 型を決定する
function read_atom(reader: Reader) {
const currentToken = reader.peek()
const isNumber = isNumberString(currentToken)
if (isNumber) {
return parseInt(currentToken, 10)
}
return currentToken
}
テスト結果はこれ
TEST RESULTS (for ../tests/step1_read_print.mal):
12: soft failing tests
41: failing tests
67: passing tests
120: total tests
Deferrable で説明されていることも実装しないと、テストは全部通らないとのこと
プログラミングをするパンダstep1、もうちょっと対応した。
TEST RESULTS (for ../tests/step1_read_print.mal):
1: soft failing tests
35: failing tests
84: passing tests
120: total tests
よく見たら後から対応するのでいいものだけがテスト失敗してたので、次のステップに進む。
Deferrable の指示文を読んだけど、本文と異なって抽象度が高く、直ぐに実装できなそうなので一旦スキップ
プログラミングをするパンダstep 2。
(+ 2 3) -> 5
(+ 2 (* 3 4)) -> 14
これが動くようになった
deferrable のテストはスキップした。
Skipping deferrable and optional tests
TEST RESULTS (for ../tests/step2_eval.mal):
0: soft failing tests
0: failing tests
9: passing tests
9: total tests
ts で実装しているので、あえてphpの実装を見ながら真似して実装したところがある。
これは学習用なので一旦通して実装して、参考実装ほど綺麗なものではないが、また一からやればいい
このまま実装を続けると、どこかで詰まるところが出てきそう。その時は全部消してやり直すのもアリ
プログラミングをするパンダcheatsheet もあるし
process の中に疑似コードはあるものの、これだけだと実装は難しい
プログラミングをするパンダdiff -u ../process/step2_eval.txt ../process/step3_env.txt
diff みると結構何やるかわかりやすい
プログラミングをするパンダガイド読んで実装するより、diff 読んでからちょい実装して guide 読みにいく方が良さそう
プログラミングをするパンダstep3 終わった。ちょっとコツ見つけてきたかも。続きは明日やる
TEST RESULTS (for ../tests/step3_env.mal):
0: soft failing tests
0: failing tests
27: passing tests
27: total tests
step 4。do, if, fn* を実装
テストファースト
TEST RESULTS (for ../tests/step4_if_fn_do.mal):
0: soft failing tests
79: failing tests
8: passing tests
87: total tests
do を実装
TEST RESULTS (for ../tests/step4_if_fn_do.mal):
0: soft failing tests
77: failing tests
10: passing tests
87: total tests
if を実装
TEST RESULTS (for ../tests/step4_if_fn_do.mal):
0: soft failing tests
70: failing tests
17: passing tests
87: total tests
fn*はうまくいってない
ns を実装
TEST RESULTS (for ../tests/step4_if_fn_do.mal):
0: soft failing tests
45: failing tests
42: passing tests
87: total tests
もうちょっと実装した
けど正解見ずにできるのはここまでかも
TEST RESULTS (for ../tests/step4_if_fn_do.mal):
0: soft failing tests
34: failing tests
53: passing tests
87: total tests
ここからはstep1から8まで、guide と TSの実装を見ながら写経する
プログラミングをするパンダstep 0
function readMal(val) {
return val
}
function evalMal(val) {
return val
}
function printMal(val) {
return val
}
function rep(val: string) {
return printMal(evalMal(readMal(val)))
}
async function main() {
const reader = Deno.stdin.readable.getReader();
const decoder = new TextDecoder();
while(true) {
await Deno.stdout.write(new TextEncoder().encode("user> "))
const {value, done} = await reader.read()
if (done || !value) {
break
}
const input = decoder.decode(value).trim()
if (input == null) {
break;
}
if (input === "") {
continue;
}
try {
let output = rep(input);
// ANSIエスケープシーケンスを除去するための正規表現
const ansiEscapeRegex = /\x1b\[[0-9;]*m/g;
// 出力からANSIエスケープシーケンスを除去
output = output.toString().replace(ansiEscapeRegex, "");
console.log(output)
} catch (e) {
console.error(e.message)
}
}
}
await main()
TEST RESULTS (for ../tests/step0_repl.mal):
0: soft failing tests
0: failing tests
24: passing tests
24: total tests
In non-lisp languages, this step (called "lexing and parsing") can be one of the most complicated parts of the compiler/interpreter. In Lisp, the data structure that you want in memory is basically represented directly in the code that the programmer writes (homoiconicity).
これがLISPの大きな特徴。プログラマがデータ構造を書く
プログラミングをするパンダ型定義良くなった
Node はやっぱり 値と meta 情報を持たせる作りにするのが良い
export const MalNode = {
List: 'list',
Number: 'number',
String: 'string',
Symbol: 'symbol',
} as const
export type MalType = MalList | MalNumber | MalString | MalSymbol
export class MalList {
type = MalNode.List
constructor(public readonly value: MalType[]) {
}
}
export class MalNumber {
type = MalNode.Number
constructor(public readonly value: number) {
}
}
export class MalString {
type = MalNode.String
constructor(public readonly value: string) {
}
}
export class MalSymbol {
type = MalNode.Symbol
value: symbol
constructor(val: string) {
this.value = Symbol.for(val)
}
static get(key: symbol): string {
return Symbol.keyFor(key) || '' // TODO: なければ例外を投げる
}
}
やり直し step1 テスト
TEST RESULTS (for ../tests/step1_read_print.mal):
0: soft failing tests
0: failing tests
24: passing tests
24: total tests
データ型をちゃんと設定するだけでとてもスムーズになった
作り直してるからそれぞれの関数が何してるか理解も深まってる
プログラミングをするパンダdeferrable は相変わらずスキップ
最後にやる
プログラミングをするパンダstep2 通った
変えたところ
const replEnv = {
'+': (a: MalNumber, b: MalNumber) => new MalNumber(a.value + b.value),
'-': (a: MalNumber, b: MalNumber) => new MalNumber(a.value - b.value),
'*': (a: MalNumber, b: MalNumber) => new MalNumber(a.value * b.value),
'/': (a: MalNumber, b: MalNumber) => new MalNumber(a.value / b.value),
}
if (isList) {
const fn = evalMal(ast.value[0], env)
const args = ast.value.slice(1).map((node: MalType) => evalMal(node, env))
return fn(...args)
}
この辺り
プログラミングをするパンダlet* に手こずってしまった。前回はすっと書けたのに。
MalSymbol に symbol を使ってから書き方間違えててしょうもないバグを混入させてしまっていた
MalSymbol は string だけで表現するようにする
TEST RESULTS (for ../tests/step3_env.mal):
0: soft failing tests
0: failing tests
27: passing tests
27: total tests
function evalMal(ast: MalType, env: Env) {
switch (ast.type) {
case MalNode.Symbol:
const symbol = ast.value
const value = env.get(symbol)
if (!value) {
throw new Error(`${symbol} not found`)
}
return value
}
const isList = ast.type === MalNode.List
if (!isList) {
return ast
}
if (ast.value.length === 0) {
return ast
}
const first = ast.value[0]
if (first.type === MalNode.Symbol) {
switch (first.value) {
case "def!": {
const [, key, value] = ast.value
if (key.type !== MalNode.Symbol) {
throw new Error(`unexpected token type: ${key.type}, expected: symbol`)
}
return env.set(key.value, evalMal(value, env))
}
case "let*": {
const letEnv = new Env(env)
// (let* ((var1, expr1) (var2, expr2)) (expr)) という入力があるので、key は 0, 2, 4, ... というインデックスにある
const letList = ast.value[1]
if (letList.type !== MalNode.List) {
throw new Error ("let* first argument must be a list")
}
for (let i = 0; i < letList.value.length; i+=2) {
const key = letList.value[i]
const value = letList.value[i+1]
if (key.type !== MalNode.Symbol) {
throw new Error ("let* binding key must be a string")
}
letEnv.set(key.value, evalMal(value, letEnv))
}
// ast.value[2] から先の式は、let で定義した変数が使える
return evalMal(ast.value[2], letEnv)
}
}
}
// apply
const fn = evalMal(ast.value[0], env)
const args = ast.value.slice(1).map((node: MalType) => evalMal(node, env))
return fn.value(...args)
}