实现一个玩具 lisp 运行时与解析器

本文最后更新于:2022年6月21日 下午

前言

之前看元循环求值器一节中使用 lisp 实现了一个 lisp 的运行时,吾辈也尝试使用 ts 来实现它。首先,这里展示一张曾经在书中出现过的图,表示一个运行时的基本组成是由 eval 和 apply 组成(看起来很像太极就是了)。eval 负责执行一个表达式,在 lisp 中,所有的代码都是表达式,这没什么问题。apply 则负责执行一个函数,将计算实参列表,并创建一个新的闭包环境绑定到形参上。

循环求值器.excalidraw.svg

环境是一个有趣的话题,最初,吾辈了解到的是代换模型,即 (+ (+ 1 2) 3) 也可以被替换为 (+ 1 2 3)。后来,接触到修改变量后,每个函数就会绑定环境,然后动态获取某些值。

例如执行代码

(define (add x y)
  (+ x y))
(add 1 2)

环境模型.excalidraw.svg

实现运行时

最初,吾辈也尝试使用 cons 实现,但后来发现面向对象更适合做这种事情(抽象语法树有不同的类型)。

考虑到复杂度的问题,目前实现了以下几种 ast

  • primitive: 原始值,例如 number/boolean/string
  • variable: 变量,从当前环境中获取值
  • define: 在当前环境中定义新的值
  • set: 修改当前环境中指定的值
  • if: 条件判断,类似于三元表达式
  • cond: 条件判断,类似于 if/else-if/else
  • begin: 一系列表达式,结果为最后一个表达式的值
  • lambda: 函数,包含参数、函数体与定义时的环境,可以被 apply 执行
  • procedure: 一个需要执行的函数+参数

先定义基础的 ast 接口,其中 eval 是每种 ast 都必须实现的方法,apply 则仅在 lambda ast 中存在。

type AstType =
  | "primitive"
  | "variable"
  | "define"
  | "set"
  | "if"
  | "cond"
  | "begin"
  | "lambda"
  | "procedure";

export interface IAst {
  readonly type: AstType;
  eval(env: Env): any;
}

export interface IApplyAst {
  apply(args: any[]): any;
}

环境

然后实现 Env 环境变量,应该能够获取、新增、修改以及扩展为一个新的环境

export class Env {
  private readonly map = new Map<string, any>();
  constructor(private readonly prototype: Env | null = null) {}
  get(k: string): any {
    return this.map.has(k)
      ? this.map.get(k)
      : this.prototype !== null
      ? this.prototype.get(k)
      : null;
  }
  define(k: string, v: any) {
    if (this.map.has(k)) {
      throw new Error(`变量 ${k} 已定义`);
    }
    this.map.set(k, v);
  }
  set(k: string, v: any): any {
    if (this.map.has(k)) {
      this.map.set(k, v);
      return;
    }
    if (this.prototype === null) {
      throw new Error(`当前环境没有定义 ${k}`);
    }
    this.prototype.set(k, v);
  }
  extend(args: Record<string, any>) {
    const env = new Env(this);
    Object.entries(args).forEach(([k, v]) => {
      env.map.set(k, v);
    });
    return env;
  }
}

接下来我们分别实现每一个

原始值

原始值很简单,例如 1,2,3,4,5… 这样的数字,或 true/false 布尔值,亦或是 “hello world” 这种字符串,它们都是原始值,可以直接声明和使用,所以 ast 也仅仅是保存值,并且执行的时候返回而已。

export class PrimitiveAst implements IAst {
  readonly type: AstType = "primitive";
  readonly value;
  constructor(value: any) {}
  eval() {
    if (this.value === null) {
      return null;
    }
    if (!["string", "number", "boolean"].includes(typeof this.value)) {
      throw new Error("不支持的类型 " + typeof this.value);
    }
    return this.value;
  }
}

variable/define/set 环境

variable/define/set 都是在操作环境,分别是获取、新增和修改。

有两点需要注意的地方

  • variable 有点特殊,因为某些函数预先定义在语言中,例如 + - * / cons car cdr,它们不需要定义就可以使用(类似于浏览器的 native function),所以这里有一个仅在内部使用的 PrimitiveLambdaAst 类型,可以看到其中实现了 + > < = 这几个原生函数。
  • 环境应该保存指向上一个环境的索引,这里为了简单实现使用了引用复制。

env.excalidraw.svg

class PrimitiveLambdaAst implements IAst, IApplyAst {
  readonly type: AstType = "lambda";
  constructor(readonly name: string) {}
  eval(env: Env) {
    return this;
  }
  static readonly symbols = ["+", ">", "<", "="];
  apply(args: any[]) {
    if (this.name === "+") {
      return args.reduce((r, i) => r + i, 0);
    }
    if (this.name === ">") {
      return args[0] > args[1];
    }
    if (this.name === "<") {
      return args[0] < args[1];
    }
    if (this.name === "=") {
      return args[0] === args[1];
    }
    throw new Error("不支持的 api " + this.name);
  }
}

export class VariableAst implements IAst {
  readonly type: AstType = "variable";
  constructor(readonly name: string) {}
  eval(env: Env) {
    const res = env.get(this.name);
    if (res === null) {
      if (PrimitiveLambdaAst.symbols.includes(this.name)) {
        return new PrimitiveLambdaAst(this.name).eval(env);
      }
      throw new Error("变量未定义 " + this.name);
    }
    return res;
  }
}

export class DefineAst implements IAst {
  readonly type: AstType = "define";
  constructor(readonly name: string, readonly value: IAst) {}
  eval(env: Env) {
    if (env.get(this.name)) {
      throw new Error(`变量 ${this.name} 已存在,不能重复定义`);
    }
    return env.define(this.name, this.value.eval(env));
  }
}
export class SetAst implements IAst {
  readonly type: AstType = "set";
  constructor(readonly name: string, readonly value: IAst) {}
  eval(env: Env) {
    if (env.get(this.name) === null) {
      throw new Error(`变量 ${this.name} 不存在,不能设置值`);
    }
    return env.set(this.name, this.value.eval(env));
  }
}

if/cond 条件判断

条件分支的 ast 很简单,许多语言中都有这种功能。

条件判断.excalidraw.svg

if/cond 可以相互替代,所以可以仅实现一种,然后替换另一种即可,这里由于比较简单所以实现了两种。

export class IfAst implements IAst {
  readonly type: AstType = "if";
  constructor(
    readonly predict: IAst,
    readonly left: IAst,
    readonly right: IAst
  ) {}
  eval(env: Env) {
    return this.predict.eval(env) ? this.left.eval(env) : this.right.eval(env);
  }
}

export class CondAst implements IAst {
  readonly type: AstType = "cond";
  constructor(
    readonly clauses: [predict: IAst, value: IAst][],
    readonly defaultValue: IAst | null
  ) {}
  eval(env: Env) {
    const findClause = this.clauses.find((item) => item[0].eval(env));
    return findClause
      ? findClause[1].eval(env)
      : this.defaultValue
      ? this.defaultValue.eval(env)
      : null;
  }
}

sequence/procedure

sequence 表示一系列表达式,全部执行并返回最后一个的结果。例如以下代码应该返回 3

(begin
  (define (add x y) (+ x y))
  (define a 1)
  (define b 2)
  (add a b))
export class SequenceAst implements IAst {
  readonly type: AstType = "begin";
  constructor(readonly exps: IAst[]) {}
  eval(env: Env) {
    return this.exps.reduce((_, exp) => exp.eval(env), null);
  }
}

lambda/procedure

procedure/lambda 是最有趣的一部分,前者负责定义一个函数,后者则负责具体的调用。lambda ast 执行仅绑定了环境,并未真的执行。apply 则才会开辟一个新的环境,并将参数绑定新的环境上,然后执行函数体的代码。procedure 则计算一个表达式,表达式包含函数部分与参数部分,它会分别计算两者并最后应用 lambda ast 的 apply 方法。

考虑以下代码如何执行

(((lambda (x) (lambda (y) (+ x y))) 1) 2)

分为几步看

  1. (lambda (x) (lambda (y) (+ x y))) 创建一个函数,它返回一个新的函数
  2. ((lambda (x) (lambda (y) (+ x y))) 1) 应用了上面的函数,创建了一个新的环境,x 被绑定为 1,返回了一个新的函数,可以被认为转换为了表达式 (lambda (y) (+ 1 y))
  3. 应用返回的函数,创建新的环境,将 y 绑定到 2
  4. 是一个原生函数 +,直接得到结果 3

函数.excalidraw.svg

export class LambdaAst implements IAst, IApplyAst {
  readonly type: AstType = "lambda";
  constructor(
    readonly args: string[],
    readonly body: IAst,
    readonly restArgs: boolean
  ) {}
  env!: Env;
  eval(env: Env) {
    // 绑定环境,然后什么都不做
    this.env = env;
    return this;
  }
  apply(args: any[]) {
    return this.body.eval(this.env.extend(this.pairArgs(this.args, args)));
  }
  private pairArgs(argNames: string[], args: any[]): Record<string, any> {
    return argNames.reduce((r, k, i) => {
      if (i === argNames.length - 1 && this.restArgs) {
        r[k] = args.slice(i);
      } else {
        r[k] = args[i];
      }
      return r;
    }, {} as Record<string, any>);
  }
}
export class ProcedureAst implements IAst {
  readonly type: AstType = "procedure";
  constructor(readonly operator: IAst, readonly operands: IAst[]) {}
  eval(env: Env) {
    return applyLisp(
      this.operator.eval(env),
      this.operands.map((ast) => ast.eval(env))
    );
  }
}

统一入口

然后,统一的入口 evalLisp/applyLisp 就很简单了

/**
 * 计算 lisp 表达式
 */
export function evalLisp(ast: IAst, env: Env = new Env()): any {
  return ast.eval(env);
}
/**
 * 执行一个 lisp 函数
 */
export function applyLisp(ast: IAst & IApplyAst, args: any[]): any {
  return ast.apply(args);
}

验证一下

describe("basic", () => {
  const primitiveAdd = new VariableAst("+");
  const primitiveMore = new VariableAst(">");
  const primitiveLess = new VariableAst("<");
  const primitiveEq = new VariableAst("=");
  it("primitive", () => {
    expect(evalLisp(new PrimitiveAst(1))).toBe(1);
    expect(evalLisp(new PrimitiveAst(false))).toBe(false);
    expect(evalLisp(new PrimitiveAst("hello"))).toBe("hello");
    expect(() => evalLisp(new PrimitiveAst([1, 2]))).toThrowError();
  });
  it("variable", () => {
    expect(
      evalLisp(new VariableAst("name"), new Env().extend({ name: "liuli" }))
    ).toBe("liuli");
    expect(() => evalLisp(new VariableAst("name"))).toThrowError();
  });
  describe("if", () => {
    it("basic", () => {
      expect(
        evalLisp(
          new IfAst(
            new PrimitiveAst(true),
            new PrimitiveAst(true),
            new PrimitiveAst(false)
          )
        )
      ).toBe(true);
      expect(
        evalLisp(
          new IfAst(
            new PrimitiveAst(false),
            new PrimitiveAst(true),
            new PrimitiveAst(false)
          )
        )
      ).toBe(false);
    });
    it("variable", () => {
      expect(
        evalLisp(
          new IfAst(
            new VariableAst("hasName"),
            new PrimitiveAst(true),
            new PrimitiveAst(false)
          ),
          new Env().extend({
            hasName: true,
          })
        )
      ).toBe(true);
    });
    it("expression", () => {});
  });
  it("cond", () => {
    const cond = new CondAst(
      [
        [new PrimitiveAst(false), new PrimitiveAst(1)],
        [new VariableAst("x"), new PrimitiveAst(2)],
        [
          new ProcedureAst(primitiveEq, [
            new VariableAst("y"),
            new PrimitiveAst(3),
          ]),
          new PrimitiveAst(3),
        ],
      ],
      new PrimitiveAst(0)
    );
    expect(evalLisp(cond, new Env().extend({ x: true, y: 3 }))).toBe(2);
    expect(evalLisp(cond, new Env().extend({ x: false, y: 3 }))).toBe(3);
    expect(evalLisp(cond, new Env().extend({ x: false, y: 0 }))).toBe(0);
  });
  describe("define", () => {
    it("basic", () => {
      const env = new Env();
      evalLisp(new DefineAst("name", new PrimitiveAst("liuli")), env);
      expect(evalLisp(new VariableAst("name"), env)).toBe("liuli");
    });
    it("repeated define", () => {
      expect(() =>
        evalLisp(
          new SequenceAst([
            new DefineAst("name", new PrimitiveAst("liuli")),
            new DefineAst("name", new PrimitiveAst("liuli")),
          ])
        )
      ).toThrowError();
    });
  });
  describe("set", () => {
    it("basic", () => {
      const res = evalLisp(
        new SequenceAst([
          new DefineAst("name", new PrimitiveAst("liuli")),
          new SetAst("name", new PrimitiveAst("li")),
          new VariableAst("name"),
        ])
      );
      expect(res).toBe("li");
    });
    it("error set", () => {
      expect(() =>
        evalLisp(new SetAst("name", new PrimitiveAst("li")))
      ).toThrowError();
    });
  });
  it("sequence", () => {
    const res = evalLisp(
      new SequenceAst([
        new DefineAst("name", new PrimitiveAst("liuli")),
        new VariableAst("name"),
      ])
    );
    expect(res).toBe("liuli");
  });
  it("lambda", () => {
    const fn = new LambdaAst([], new PrimitiveAst(1), false);
    expect(applyLisp(evalLisp(fn), [])).toBe(1);
    expect(evalLisp(new ProcedureAst(fn, []))).toBe(1);
  });
  describe("procedure", () => {
    it("primitive", () => {
      expect(applyLisp(evalLisp(primitiveAdd), [1, 2])).toBe(3);
      expect(applyLisp(evalLisp(primitiveMore), [1, 2])).toBe(false);
      expect(applyLisp(evalLisp(primitiveLess), [1, 2])).toBe(true);
    });
    it("wrap", () => {
      const add = new LambdaAst(
        ["x", "y"],
        new ProcedureAst(primitiveAdd, [
          new VariableAst("x"),
          new VariableAst("y"),
        ]),
        false
      );
      expect(applyLisp(evalLisp(add), [1, 2])).toBe(3);
      expect(
        evalLisp(
          new ProcedureAst(add, [new PrimitiveAst(1), new PrimitiveAst(2)])
        )
      ).toBe(3);
    });
    it("close", () => {
      const closeFn = new LambdaAst(
        ["x"],
        new ProcedureAst(primitiveAdd, [
          new VariableAst("x"),
          new VariableAst("y"),
        ]),
        false
      );
      expect(
        applyLisp(evalLisp(closeFn, new Env().extend({ y: 1 })), [1])
      ).toBe(2);
      const ast = new SequenceAst([
        new DefineAst("x", new PrimitiveAst(1)),
        new DefineAst("y", new VariableAst("x")),
        new ProcedureAst(closeFn, [new PrimitiveAst(2)]),
      ]);
      expect(evalLisp(ast)).toBe(3);
    });
    it("basic", () => {
      const returnSelf = new LambdaAst(["x"], new VariableAst("x"), false);
      expect(applyLisp(evalLisp(returnSelf), [1])).toBe(1);
    });
    it("restArgs", () => {
      const lambda = new LambdaAst(
        ["numbers"],
        new VariableAst("numbers"),
        true
      );
      console.log(applyLisp(evalLisp(lambda), [1, 2]));
      // expect(applyLisp(evalLisp(lambda, {}), [1, 2])).toBe(1)
    });
    describe("cons", () => {
      const cons = new LambdaAst(
        ["car", "cdr"],
        new LambdaAst(
          ["action"],
          new CondAst(
            [
              [
                new ProcedureAst(primitiveEq, [
                  new VariableAst("action"),
                  new PrimitiveAst("car"),
                ]),
                new VariableAst("car"),
              ],
              [
                new ProcedureAst(primitiveEq, [
                  new VariableAst("action"),
                  new PrimitiveAst("cdr"),
                ]),
                new VariableAst("cdr"),
              ],
              [
                new ProcedureAst(primitiveEq, [
                  new VariableAst("action"),
                  new PrimitiveAst("setCar"),
                ]),
                new LambdaAst(
                  ["val"],
                  new SetAst("car", new VariableAst("val")),
                  false
                ),
              ],
              [
                new ProcedureAst(primitiveEq, [
                  new VariableAst("action"),
                  new PrimitiveAst("setCdr"),
                ]),
                new LambdaAst(
                  ["val"],
                  new SetAst("cdr", new VariableAst("val")),
                  false
                ),
              ],
            ],
            new PrimitiveAst("error")
          ),
          false
        ),
        false
      );
      it("basic", () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2]);
        expect(applyLisp(numbers, ["car"])).toBe(1);
        expect(applyLisp(numbers, ["cdr"])).toBe(2);
      });
      const car = new LambdaAst(
        ["cons"],
        new ProcedureAst(new VariableAst("cons"), [new PrimitiveAst("car")]),
        false
      );
      const cdr = new LambdaAst(
        ["cons"],
        new ProcedureAst(new VariableAst("cons"), [new PrimitiveAst("cdr")]),
        false
      );

      it("car/cdr", () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2]);
        expect(applyLisp(evalLisp(car), [numbers])).toBe(1);
        expect(applyLisp(evalLisp(cdr), [numbers])).toBe(2);
      });
      const setCar = new LambdaAst(
        ["cons", "val"],
        new ProcedureAst(
          new ProcedureAst(new VariableAst("cons"), [
            new PrimitiveAst("setCar"),
          ]),
          [new VariableAst("val")]
        ),
        false
      );
      const setCdr = new LambdaAst(
        ["cons", "val"],
        new ProcedureAst(
          new ProcedureAst(new VariableAst("cons"), [
            new PrimitiveAst("setCdr"),
          ]),
          [new VariableAst("val")]
        ),
        false
      );
      it("set", () => {
        const numbers = applyLisp(evalLisp(cons), [1, 2]);
        applyLisp(evalLisp(setCar), [numbers, 11]);
        expect(applyLisp(evalLisp(car), [numbers])).toBe(11);
        applyLisp(evalLisp(setCdr), [numbers, 12]);
        expect(applyLisp(evalLisp(cdr), [numbers])).toBe(12);
      });
    });
  });
});

解析代码为 ast

上面实现了执行 lisp ast 的功能,但如何将 lisp 代码解析为这种 ast 还没有实现,下面就来完成这一步。

解析代码为字符流

简单的处理为一个 token 数组很简单

/**
 * 解析代码为 token 数组(一维)
 * @param code
 * @returns
 */
export function tokenize(code: string): string[] {
  return code
    .replaceAll("(", " ( ")
    .replaceAll(")", " ) ")
    .split(" ")
    .map((i) => i.trim())
    .filter((i) => i.length !== 0);
}

将字符流结构化

但我们需要结构化的,所以还需要做一次转换

基本思路是每次处理一个字符

  1. 如果是 (,则添加一个临时数组存储之后的值,直到遇到 ) 为止
  2. 如果是 ),则将当前的临时数组合并到上一个临时数组
  3. 如果是其他字符,则将之追加到当前临时数组中
  4. 如果到了结尾,则返回当前的数组
  5. 初始数组是 [[]],最后返回 res[0][0]

这是一个基本的流程图

image.jpg

下面是解析代码 (begin (define x 1) (define y 2) (+ x y)) 的 tokens 流程中数组的状态

step code arr
init [[]]
1 ( [[], []]
2 begin [[], [begin]]
3 ( [[], [begin], []]
4 define [[], [begin], [define]]
5 define [[], [begin], [define]]
6 x [[], [begin], [define, x]]
7 1 [[], [begin], [define, x, 1]]
8 ) [[], [begin, [define, x, 1]]]
9 ( [[], [begin, [define, x, 1]], []]
10 define [[], [begin, [define, x, 1]], [define]]
11 y [[], [begin, [define, x, 1]], [define, y]]
12 2 [[], [begin, [define, x, 1]], [define, y, 2]]
13 ) [[], [begin, [define, x, 1], [define, y, 2]]]
14 ( [[], [begin, [define, x, 1], [define, y, 2]], []]
15 + [[], [begin, [define, x, 1], [define, y, 2]], [+]]
16 x [[], [begin, [define, x, 1], [define, y, 2]], [+, x]]
17 y [[], [begin, [define, x, 1], [define, y, 2]], [+, x, y]]
18 ) [[], [begin, [define, x, 1], [define, y, 2], [+, x, y]]]
19 ) [[[begin, [define, x, 1], [define, y, 2], [+, x, y]]]]

具体实现

/**
 * 解析代码为 token 数组(一维)
 * @param code
 * @returns
 */
export function tokenize(code: string): string[] {
  return code
    .replaceAll("(", " ( ")
    .replaceAll(")", " ) ")
    .split(" ")
    .map((i) => i.trim())
    .filter((i) => i.length !== 0);
}

type DeepArray<T> = (T | DeepArray<T>)[];

/**
 * 将平铺的 tokens 结构化,包含层次关系(使用多维数组)
 * @param tokens
 * @returns
 */
export function structTokens(tokens: string[]): DeepArray<string> {
  function iter(i: number, curr: DeepArray<string>): DeepArray<string> {
    if (i === tokens.length) {
      return curr;
    }
    if (tokens[i] === "(") {
      curr.push([]);
      return iter(i + 1, curr);
    }
    if (tokens[i] === ")") {
      const sub = curr.pop()!;
      (curr[curr.length - 1] as DeepArray<string>).push(sub);
      return iter(i + 1, curr);
    }
    (curr[curr.length - 1] as DeepArray<string>).push(tokens[i]);
    return iter(i + 1, curr);
  }
  return iter(0, [[]])[0][0] as DeepArray<string>;
}

/**
 * 解析 lisp 代码为 ast
 * @param code
 */
export function parseLisp(code: string): IAst {
  const map: Partial<Record<AstType, (token: string[]) => IAst>> = {
    define(token) {
      const name = token[1];
      if (Array.isArray(name)) {
        return new DefineAst(
          name[0],
          new LambdaAst(
            name.slice(1) as unknown as string[],
            readFromToken(token[2]),
            false
          )
        );
      }
      return new DefineAst(name, readFromToken(token[2]));
    },
    set(token) {
      const name = token[1];
      return new SetAst(name, readFromToken(token[2]));
    },
    begin(token) {
      return new SequenceAst(token.slice(1).map(readFromToken));
    },
    if(token) {
      return new IfAst(
        readFromToken(token[1]),
        readFromToken(token[2]),
        readFromToken(token[3])
      );
    },
    cond(token) {
      if (token[token.length - 1][0] === "else") {
        return new CondAst(
          token
            .slice(1, token.length - 1)
            .map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          readFromToken(token[token.length - 1][1])
        );
      } else {
        return new CondAst(
          token.slice(1).map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          null
        );
      }
    },
    lambda(token) {
      return new LambdaAst(
        token[1] as unknown as string[],
        readFromToken(token[2]),
        false
      );
    },
  };
  function readFromToken(token: string | string[]): IAst {
    if (Array.isArray(token)) {
      const op = token[0];
      const parse = map[op as AstType];
      return parse
        ? parse(token)
        : new ProcedureAst(
            readFromToken(token[0]),
            token.slice(1).map(readFromToken)
          );
    }
    if (typeof token !== "string") {
      throw new Error("不支持的 token 类型 " + typeof token);
    }
    return atom(token);
  }
  function atom(token: string): IAst {
    if (/^\d$/.test(token)) {
      return new PrimitiveAst(Number.parseInt(token));
    }
    if (/^([0-9]{1,}[.][0-9]*)$/.test(token)) {
      return new PrimitiveAst(Number.parseFloat(token));
    }
    if (/^".*"$/.test(token)) {
      return new PrimitiveAst(token.slice(1, token.length - 1));
    }
    if (["true", "false"].includes(token)) {
      return new PrimitiveAst(token === "true");
    }
    return new VariableAst(token);
  }
  return readFromToken(structTokens(tokenize(code)) as any);
}

转换为 ast

最终,我们将结构化的 token 转换为 ast

/**
 * 解析 lisp 代码为 ast
 * @param code
 */
export function parseLisp(code: string): IAst {
  const map: Partial<Record<AstType, (token: string[]) => IAst>> = {
    define(token) {
      const name = token[1];
      if (Array.isArray(name)) {
        return new DefineAst(
          name[0],
          new LambdaAst(
            name.slice(1) as unknown as string[],
            readFromToken(token[2]),
            false
          )
        );
      }
      return new DefineAst(name, readFromToken(token[2]));
    },
    set(token) {
      const name = token[1];
      return new SetAst(name, readFromToken(token[2]));
    },
    begin(token) {
      return new SequenceAst(token.slice(1).map(readFromToken));
    },
    if(token) {
      return new IfAst(
        readFromToken(token[1]),
        readFromToken(token[2]),
        readFromToken(token[3])
      );
    },
    cond(token) {
      if (token[token.length - 1][0] === "else") {
        return new CondAst(
          token
            .slice(1, token.length - 1)
            .map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          readFromToken(token[token.length - 1][1])
        );
      } else {
        return new CondAst(
          token.slice(1).map(([p, v]) => [readFromToken(p), readFromToken(v)]),
          null
        );
      }
    },
    lambda(token) {
      return new LambdaAst(
        token[1] as unknown as string[],
        readFromToken(token[2]),
        false
      );
    },
  };
  function readFromToken(token: string | string[]): IAst {
    if (Array.isArray(token)) {
      const op = token[0];
      const parse = map[op as AstType];
      return parse
        ? parse(token)
        : new ProcedureAst(
            readFromToken(token[0]),
            token.slice(1).map(readFromToken)
          );
    }
    if (typeof token !== "string") {
      throw new Error("不支持的 token 类型 " + typeof token);
    }
    return atom(token);
  }
  function atom(token: string): IAst {
    if (/^\d$/.test(token)) {
      return new PrimitiveAst(Number.parseInt(token));
    }
    if (/^([0-9]{1,}[.][0-9]*)$/.test(token)) {
      return new PrimitiveAst(Number.parseFloat(token));
    }
    if (/^".*"$/.test(token)) {
      return new PrimitiveAst(token.slice(1, token.length - 1));
    }
    if (["true", "false"].includes(token)) {
      return new PrimitiveAst(token === "true");
    }
    return new VariableAst(token);
  }
  return readFromToken(structTokens(tokenize(code)) as any);
}

我们可以验证它的正确性

expect(evalLisp(parseLisp('"liuli"'))).toBe("liuli");
expect(evalLisp(parseLisp("(+ 1 2)"))).toBe(3);
expect(evalLisp(parseLisp("(+ 1.1 3.3)"))).toBe(4.4);
expect(evalLisp(parseLisp("true"))).toBe(true);
expect(evalLisp(parseLisp("(begin (define x 1) (define y 2) (+ x y))"))).toBe(
  3
);
expect(evalLisp(parseLisp("(if true 0 1)"))).toBe(0);
expect(evalLisp(parseLisp("(if false 0 1)"))).toBe(1);
expect(evalLisp(parseLisp("(cond (false 0) (false 1))"))).toBe(null);
expect(evalLisp(parseLisp("(cond (false 0) (false 1) (else 2))"))).toBe(2);
expect(evalLisp(parseLisp("(cond (false 0) (true 1) (else 2))"))).toBe(1);
expect(evalLisp(parseLisp("((lambda (x y) (+ x y)) 1 2)"))).toBe(3);
expect(
  evalLisp(parseLisp("(begin (define (add x y) (+ x y)) (add 1 2))"))
).toBe(3);
expect(evalLisp(parseLisp("(begin 1 2)"))).toBe(2);
expect(evalLisp(parseLisp("(begin (define x 1) (set x 2) x)"))).toBe(2);
expect(
  evalLisp(
    parseLisp(`
      (
        begin
        (define (cons a b) (
          lambda (action) (
            cond
            ((= action "car") a)
            ((= action "cdr") b)
          )
        ))
        (define (car cons) (cons "car"))
        (define (cdr cons) (cons "cdr"))
        (define v (cons 1 2))
        (+ (car v) (cdr v))
      )
    `)
  )
).toBe(3);

结语

在上面,吾辈实现了 lisp 的玩具运行时和解析器,虽然还不支持许多 lisp 的功能(例如 ' 引用功能),但核心的功能已经实现了,它可以完成一些基本的数值逻辑运算了。另一种有趣的思路是编译器,它不直接运行 lisp 代码,而是将 lisp 代码编译为一种其他可以运行的代码,例如将 lisp 代码编译为汇编代码执行,或者更有趣的方法是 – 编译为 js,就像 ts 做的一样,那样它就可以与 js 互操作了。


实现一个玩具 lisp 运行时与解析器
https://blog.rxliuli.com/p/76673453498244cfbe34027678d75f67/
作者
rxliuli
发布于
2022年6月16日
许可协议