JavaScript の ES2015 を使ったら Lisp を 100 行未満で実装できた

概要

Python を使って 100行前後で簡易 lisp インタプリタを実装するという記事があったので、JavaScriptでマネしたら、同じくらいの長さで書けた

• 参考資料
  • ((Pythonで) 書く (Lisp) インタプリタ) : 90行 で実装
    • オリジナル（英語）
  • ((Pythonで) 書く ((さらに良い) Lisp) インタプリタ): 300行で実装
    • オリジナル（英語）
  • オリジナルは改訂されているので、日本語訳は若干内容が古い
    • 外部仕様の違いはないので、英語に拒否感があるなら日本語訳でもよい

私の実装は、上記の 90行の実装をベースにする。それに加え 300行で取り込まれたいくつかの機能のうち、末尾最適化のみをバックポートした。あと、アルゴリズムは同じだが、忠実なポートではないので思わぬバグがないとも限らない。

以下、私の実装での動作結果。当たり前の結果だけど、JavaScript上で動くという意味でデモ:

(define area (lambda (r) (* 3.141592653 (* r r)))) ; undefined
(area 3) ; 28.274333877
(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1)))))) ; undefined
(fact 10) ; 3628800

---

以降ざっくり説明。ここから先は、参考資料をさっと読んでから進むことをおすすめする

---

01. 構文解析（トークナイズ＆構文木構築）

atom
与えられたトークンが、シンボル（例：変数名）であるか、数字なのかを判定する関数を用意しよう。後述する構文木作成時にこれを使うことで、本 LISP は数字を扱えるようになる:

function atom (token) {
  const fn = token.includes('.') ? parseFloat : x => parseInt(x, 10);
  const val = fn(token);
  return isNaN(val) ? token : val;
};

['1', '1.3', 'x', 'y10', '2x'].map(atom);
// -> [ 1, 1.3, 'x', 'y10', 2 ]

'2x' という不正な文字列を 2 としてしまうという、若干微妙な挙動もするが、概ねうまくいっていることがわかる。正規表現を使えばすぐに改良できると思う。

トークナイズ
括弧の両端にスペースをくっつけてあげて、空白文字でスプリットしてあげれば十分

function tokenize (str) {
  return str.replace(/\(/g, ' ( ').replace(/\)/g, ' ) ').replace(/\n/g, ' ')
    .split(' ').filter(x => x !== '');
}

tokenize('(+ x 10 \n(* y 3))')
// -> [ '(', '+', 'x', '10', '(', '*', 'y', '3', ')', ')' ]

構文木の構築
構文木は、Arrayで実装しよう

左括弧が見つかるたびに、一つ深く潜るための Array を生成。右括弧が見つかない間はその Array に突っ込む。右括弧が見つかれば、一つ浮き上がるために Array を閉じる。再帰的な構造をとることに注意。あと、引数 tokens を破壊的に操作することにも注意（再帰先でも破壊的に操作する）。先述の atom関数を、要素を木に追加する際に付与することで、シンボル＝ string, 数字 = number という二種類の型で木が構築される。

function readFrom (tokens) {
  if (tokens.length === 0) throw Error('unexpected EOF while reading');
  const token = tokens.shift();
  if (token === '(') {
    const L = [];
    while (tokens[0] !== ')') L.push(readFrom(tokens));
    tokens.shift(); // pop off )
    return L;
  } else if (token === ')') {
    throw Error('unexpected )');
  }
  return atom(token);
}

readFrom(tokenize('(+ x 10 \n(* y 3))'));
// -> [ '+', 'x', 10, [ '*', 'y', 3 ] ]

02. 環境とグローバル環境

環境と呼ばれるものを実装しよう。JavaScriptらしく、シンボル定義を保持する Map を関数スコープに保持するクロージャで実装する。簡便のため、環境構成時にまとめてシンボルを定義できるようにする。与えられたシンボルを解決するための get、 シンボルを定義するための set、定義済みのシンボルを更新するための upd を持たせる。

function createEnv (outer, names, values) {
  const dict = new Map();
  names.forEach((p, i) => dict.set(p, values[i]));
  return {
    set: (key, val) => dict.set(key, val) && null,
    get: key => dict.has(key) ? dict.get(key) : outer.get(key),
    upd: (key, val) => dict.has(key) ? (dict.set(key, val) && null) : outer.upd(key, val),
  };
}

グローバル環境を作って、+, *, =, などの演算子を定義する:

function globalEnv () {
  const env = createEnv(null, [], []);
  env.set('+', xs => xs.reduce((acc, x) => acc + x, 0));
  // (略)
  return env;
}

globalEnv().get('+')([100, 10, 1]); // -> 111

03. eval

構文木と環境がセットアップ出来たら、あとはエバってあげれば終わり。与えられた expression は以下のいづれかである。どのように構文木をリダクションすればよいのかはほぼ自明。

• 単一のシンボル (例: 'x', 'y', 内部表現: string)
• 定数 (例: 10, 12.1, 内部表現: number)
• スペシャルフォーム(例: define, lamdba, 内部表現: Array)
• 関数適用(例: ['+' 1 2], 内部表現 Array)

スペシャルフォームの lambda が少しややこしい。lambda は、新たに環境を作り、その環境下で与えられた expression を eval する関数を返すためのものだ。 lambda のスペシャルフォームの時は、単純にユーザ定義関数であることを知らせるフラグと環境を構築するための情報を保持した Object を返すようにして、関数適用時に、実際の環境構築をするようにする:

function lEval (_x, _env) {
  let [x, env] = [_x, _env];
  for (;;) {
    if (typeof x === 'string') { // symbol
      return env.get(x);
    } else if (typeof x === 'number') { // number
      return x;
    } else if (x[0] === 'quote') {
      return x.slice(1);
    } else if (x[0] === 'if') {
      const [, test, conseq, alt] = x;
      x = lEval(test, env) ? conseq : alt; // tail call
    } else if (x[0] === 'set!') {
      const [, name, exp] = x;
      env.upd(name, lEval(exp, env));
      return;
    } else if (x[0] === 'define') {
      const [, name, exp] = x;
      env.set(name, lEval(exp, env));
      return;
    } else if (x[0] === 'begin') {
      x.slice(1, x.length - 1).map(ex => lEval(ex, env));
      x = x[x.length - 1]; // tail call
    } else if (x[0] === 'lambda') {
      const [, params, exp] = x;
      return { env, isUDF: true, params, exp };
    } else { // apply function
      const [op, ...args] = x.map(ex => lEval(ex, env));
      if (isProcedure(op)) { // tail call
        x = op.exp;
        env = createEnv(op.env, op.params, args);
      } else {
        return op(args);
      }
    }
  }
}

04. ユーザインターフェース

JavaScript なので文字列をプリントすればよくて、REPLは不要と判断:

function myEval (str, env = globalEnv()) {
  const result = lEval(readFrom(tokenize(str)), env);
  console.log(`${str} ; ${JSON.stringify(result)}`);
};

myEval('(+ 1 2 (+ 3 4))'); // (+ 1 2 (+ 3 4)) ; 10

まとめて評価したい場合はこんな感じ

const env = globalEnv();
const inputs = `
(define area (lambda (r) (* 3.141592653 (* r r))))
(area 3)
(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))
(fact 10)
`;
inputs.split('\n').filter(d => d !== '').forEach(s => myEval(s, env));

/* 以下が出力される
(define area (lambda (r) (* 3.141592653 (* r r)))) ; undefined
(area 3) ; 28.274333877
(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1)))))) ; undefined
(fact 10) ; 3628800
*/

05. 感想と反省

• 表示関数をさぼって JSON.stringify で代用させたため、リストの表示が汚い
• REPLの実装とかをさぼったので、まじめにやったら 150 行くらいになっちゃうかも
• 末尾最適化について心底理解できたのは収穫

06. コード全体

main.js

function atom (token) {
  const fn = token.includes('.') ? parseFloat : x => parseInt(x, 10);
  const val = fn(token);
  return isNaN(val) ? token : val;
};

function tokenize (str) {
  return str.replace(/\(/g, ' ( ').replace(/\)/g, ' ) ').replace(/\n/g, ' ')
    .split(' ').filter(x => x !== '');
}

function readFrom (tokens) {
  if (tokens.length === 0) throw Error('unexpected EOF while reading');
  const token = tokens.shift();
  if (token === '(') {
    const L = [];
    while (tokens[0] !== ')') L.push(readFrom(tokens));
    tokens.shift(); // pop off )
    return L;
  } else if (token === ')') {
    throw Error('unexpected )');
  }
  return atom(token);
}

function createEnv (outer, names, values) {
  const dict = new Map();
  names.forEach((p, i) => dict.set(p, values[i]));
  return {
    set: (key, val) => dict.set(key, val) && null,
    get: key => dict.has(key) ? dict.get(key) : outer.get(key),
    upd: (key, val) => dict.has(key) ? (dict.set(key, val) && null) : outer.upd(key, val),
  };
}

function lEval (_x, _env) {
  let [x, env] = [_x, _env];
  for (;;) {
    if (typeof x === 'string') { // symbol
      return env.get(x);
    } else if (typeof x === 'number') { // number
      return x;
    } else if (x[0] === 'quote') {
      return x.slice(1);
    } else if (x[0] === 'if') {
      const [, test, conseq, alt] = x;
      x = lEval(test, env) ? conseq : alt; // tail call
    } else if (x[0] === 'set!') {
      const [, name, exp] = x;
      env.upd(name, lEval(exp, env));
      return;
    } else if (x[0] === 'define') {
      const [, name, exp] = x;
      env.set(name, lEval(exp, env));
      return;
    } else if (x[0] === 'begin') {
      x.slice(1, x.length - 1).map(ex => lEval(ex, env));
      x = x[x.length - 1]; // tail call
    } else if (x[0] === 'lambda') {
      const [, params, exp] = x;
      return { env, isUDF: true, params, exp };
    } else { // apply function
      const [op, ...args] = x.map(ex => lEval(ex, env));
      if (op.isUDF) { // tail call
        x = op.exp;
        env = createEnv(op.env, op.params, args);
      } else {
        return op(args);
      }
    }
  }
}

function globalEnv () {
  const env = createEnv(null, [], []);
  env.set('+', xs => xs.reduce((acc, x) => acc + x, 0));
  env.set('-', xs => xs.reduce((acc, x) => acc - x));
  env.set('*', xs => xs.reduce((acc, x) => acc * x, 1));
  env.set('=', xs => xs.every(x => x === xs[0]));
  env.set('<', ([a, b]) => a < b);
  env.set('cons', ([x, y]) => [x, y]);
  env.set('car', xs => xs[0][0]);
  env.set('cdr', xs => xs[0][1]);
  return env;
}

function myEval (str, env = globalEnv()) {
  const result = lEval(readFrom(tokenize(str)), env);
  console.log(`${str} ; ${JSON.stringify(result)}`);
};

// main
const env = globalEnv();
const inputs = `
(define area (lambda (r) (* 3.141592653 (* r r))))
(area 3)
(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))
(fact 10)
`;
inputs.split('\n').filter(d => d !== '').forEach(s => myEval(s, env));