..

Egg Language笔记

最近在重新看 Eloquent Javascript 的 Egg language，用 JS 实现一门叫做 Egg 的编程语言。为了跟深入学习 JS，我尝试往里面加了一些 JS 拥有的特性，如：异步、原型、执行上下文等。收获还挺多的，这里梳理记录下。

特别说明，这些特性的实现思路都是我自己思考的，跟 JS 的官方实现是否一致，还未验证过。

实现一门语言的必要基础

我做下来的体会是，要实现一门语言只要有些编程基础即可。可以绕过一大堆编译原理里的词法分析、文法分析等前置概念。等你觉得有意思，有点感性认识后，再回头啃这些概念倒是不迟。

这里推荐两篇入门材料：

  1. 怎样写一个解析器 – 王垠。王垠的这篇博客，思路清晰、非常的循序渐进，很适合入门。
  2. Project: A Programming Language，就是 Eloquent Javascript 这本书的第二个项目实践。英文书开源免费，网上也有中文翻译版卖。

任意实践上面两篇入门材料后，你基本能对词法上下文、闭包、环境、抽象语法树有概念。

下面的笔记，都是基于材料2的。最终完整的代码见：eloquent_javascript_code。

事件循环

原本 Egg Language 执行完代码后（也就是栈空了）就直接退出。根据 JS 事件循环的特点，就行改造即可。思考过程如下：

  1. 先只实现宏观任务队列，不去考虑微观任务队列；
  2. 原本的run函数，执行完毕就退出了，这里肯定要改成一个循环，那么什么时候退出呢？
  3. 当宏观任务队列不为空、或者有异步任务未 Ready 的时候，就一直待在循环里。但是，一直死循环也不行，我们可以先比较 hack 的每次 sleep 0.1 秒，然后去检查状态。

异步操作有很多，网络请求、定时器、读文件操作等等，我们这就只实现定时器这种异步操作。需要特别注意的是，需要了解宏观异步任务要经历：被创建、异步任务被执行、异步任务执行完毕（Ready状态）推入异步任务队列这三个过程。

  1. 首先，我们需要用一个变量作为计数器，表示未 Ready 的异步任务数量；
  2. 其次，我们需要一个数组，承载 Ready 的异步任务，这个其实就是那个宏任务队列。
  3. 程序一开始的时候，把程序包装成一个 Ready 的任务，推入任务队列，然后进入循环；

代码如下：

// 未完成的任务计数器
let unreadyAsyncTaskCount = 0;
// 宏任务队列
const MAJOR_TASK_QUEUE = [];

// sleep 是为了防止 egg 空转导致主机 cpu 占用过高。
// 这是个演示方法，真实的语言解析器肯定不会用这么低级
// 的方式。
function sleep(second) {
  return new Promise((resolve, reject) => {
    setTimeout(resolve, second * 1000);
  });
}

async function run(...args) {
  let env = Object.create(topEnv);
  let program = args.join('\n');

  MAJOR_TASK_QUEUE.push(() => evaluate(parse(program), env));

  while (MAJOR_TASK_QUEUE.length > 0 || unreadyAsyncTaskCount > 0) {
    if (MAJOR_TASK_QUEUE.length) {
      const task = MAJOR_TASK_QUEUE.shift();
      task();
      // 上面的 task 执行完毕，说明当前栈就空了。
    } else {
      await sleep(0.1);
    }
  }
}

接下来，再让我们实现 Egg 的 setTimeout 等函数

topEnv['setTimeout'] = function (ctx, callback, ms) {
  unreadyAsyncTaskCount = unreadyAsyncTaskCount + 1;
  return setTimeout(() => {
    // setTimeout 时间到了之后，task 就算 ready了
    // 然后把回调推入到 MAJOR_TASK_QUEUE
    unreadyAsyncTaskCount = unreadyAsyncTaskCount - 1;
    MAJOR_TASK_QUEUE.push(callback);
  }, ms);
};

topEnv['clearTimeout'] = function(ctx, timer) {
  // clear 了之后，回调也就不会被推入到 MAJOR_TASK_QUEUE。
  // 当然了，这里做得比较粗糙，没有对 timer 状态做检查
  unreadyAsyncTaskCount = unreadyAsyncTaskCount - 1;
  clearTimeout(timer)
};

topEnv['setInterval'] = function(ctx, callback, interval) {
  unreadyAsyncTaskCount = unreadyAsyncTaskCount + 1;
  return setInterval(() => {
    MAJOR_TASK_QUEUE.push(callback);
  }, interval);
};

topEnv['clearInterval'] = function (ctx, timer) {
  unreadyAsyncTaskCount = unreadyAsyncTaskCount - 1;
  clearInterval(timer);
};

这里，不要把 JS 的 setTimeout 系列函数跟 egg 的 setTimeout 系列函数搞混了。如果你觉得同名看起来太乱，可以给egg的加前缀。

然后，写段测试代码测试一下：

const run = require('../EggCompiler');

// support async api
run(
  'do(define(cb, fun(print("async print"))), setTimeout(cb, 1000), print("sync print"))'
);

run(
  `
  do(
    define(timer, 0),
    define(count, 0),
    define(cb, fun(
      do(
        print(count),
        set(count, +(count, 1)),
        if(>(count, 11), clearInterval(timer), true)
      )
    )),
    set(timer, setInterval(cb, 1000))
  )
  `
);

可以自己运行下 node tests/test-async-api.js 看下结果。

那么如何实现微任务队列呢？其实也很简单。首先，微任务没有等待ready的过程，所以直接插入微任务队列就好了；其次，只要知道微任务的执行优先级高于宏任务就可以了。

更具体的代码见这两个commit：egg language support async operator 跟 egg language support micro task queue

原型链

原型链的实现，基本没有什么难点。我这里只实现了最基本的 objectCreate 方法。其实回头想想，实现 getPrototypeOf/setPrototypeOf 应该会更好一点。

实现原型链的关键是，要让对象有一个引用指向其原型，这里采用 prototypeRef 这个 Symbol。当然，也可以用一个全局的 WeakMap，这样实现起来封装得更好，不会被 Egg 的使用者绕过 API 直接修改。

详见commit：egg language, support object and prototype chain

执行上下文

在实现完原型后，我想实现 new 跟 instanceof 这两个语法糖，然后演示一下 egg 的继承。但是，我突然发现我漏了this。所以决定先把执行上下文机制给建立起来。 我感觉执行上下文机制的实现过程还是比较吃力的，所以这里就多啰嗦一些。

我的思考过程：

  1. 执行上下文肯定是一个运行时的概念，所以应从 evaluate 函数入手；
  2. this，本质上可以视作一个特殊的变量，既然是变量，那只要执行前注入到 localEnv 就好了；
  3. 现在已经知道在哪里注入执行上下文了，那么这个执行上下文哪里来呢？
  4. 突然想起 python 的 method 声明方式，第一个参数始终是 self，因此我感觉执行上下文应该在 apply 的时候，作为第一个参数注入进来。

上面是比较顺利的思考过程，再接下来我就陷入一个困境当中。我们在 JS 中，我们能感受到执行上下文的存在的场景有两个：

  1. a.f() 这种调用；
  2. var b = a.bind(c) 这种绑定上下文的操作；

我被前一种场景给难住了，一时不知道怎么实现，因为我一直想通过我前面实现的 objectGet 来实现 a.f() 这种调用，但是实际上 objectGet 只相当于 a.f，而不能做到 a.f()。

又过了一天后，重新回来面对这个问题的时候，我决定先跳过 a.f() 这种调用，我相信，只要上下文绑定能实现，那么 a.f() 这种调用也就迎刃而解了。所以，我决定先实现一个 bind 函数。

bind函数很快实现出来了，接受两个参数，fn 跟 context，代码如下：

topEnv['bind'] = function (fn, context) {
  return function (_, ...args) { // _ 这是原来注入的contenxt，摒弃不要了
    return fn(context, ...args);
  }
};

这其中出了一些问题。我没有意识到 topEnv 里的这些内建函数，本质上跟 specialForm 里的 fun 的返回值是等价的，所以这些内建函数的第一个参数也都是一个执行上下文——它们被执行时的上下文，所以代码变成：

topEnv['bind'] = function (ctx, fn, context) { // ctx是bind函数的执行上下文，context是要绑定给fn的执行下文
  return function (_, ...args) {
    return fn(context, ...args);
  }
};

下一段egg代码测试一下结果：

run(`
  do(
    define(display, fun(print(objectGet(this, "name")))),
  
    define(obj1, objectCreate(null)),
    objectSet(obj1, "name", "kafka"),
  
    define(obj2, objectCreate(null)),
    objectSet(obj2, "name", "kk"),
  
    define(obj1Display, bind(display, obj1)),
    define(obj2Display, bind(display, obj2)),
  
    obj1Display(),
    obj2Display(),
  )
`);    // --> kafka\nkk

非常完美！

实现完bind之后，发现 a.f() 这样调用就简单很多。首先，需要再次说明 a.f() 其实是两个动作，我想起之前玩es6的Proxy的时候，a.f() 这样的调用会触发两个 Proxy：getter、apply。所以，我再不执着于怎么用 objectGet 来实现，我决定新增一个内建函数叫 objectGetApply 来实现。代码如下：

topEnv['objectGetApply'] = function (ctx, obj, key, ...args) {
  const fn = obj[key];    // 函数所在的obj就是函数的执行上下文
  return fn(obj, ...args);
};

代码详见这个commit：egg language, support execute context

在写笔记的时候，我突然意识到，类似 fn.bind(ctxA).bind(ctxB) 这样的结果是什么？ 我期望的是ctxB 绑定到 fn 上。可事实是，这种期望即办不到也不合理，想想为什么？

2024年后记

2024年，从草稿箱里把这篇笔记拿出来重新发表的时候，暂时已经没有精力对内容、代码做细致的整理了。回想起当初自己扩展 Egg Language 的初心，就是为了深入理解 JS。我相信当时的目标已经达成了。

尝试语言自举是一种很好的深入理解一门语言的方式。更抽象的说，就是实现一个玩具 Demo，可以让自己很好的理解一个事物。

如果你依然对 Egg Language 感兴趣，依然想深入理解 JS 的语法，我建议你可以试试通过 TypeScript，更加模块化的实现整个过程。已经可以实现更多更新的功能，甚至是 ES 草案里的功能。