JavaScriptでおもちゃのLispを作ろう（１）〜リーダ編〜

こんなものは数え切れないくらい既に沢山あると思いますが、JavaScriptでおもちゃのLispを作り始めたので日記として書いておきます。普段は会社では仕事でC++を使ってプログラムを書いていますが、趣味のプログラミングというのは、やっぱりおもちゃのような楽しめるものがいいですよね。おもちゃは、特に意味がなくても自分が楽しめればよいのです。始めたばかりの自分のブログで、アクセスがほとんどない状況で、こんなことを書いて意味がなくても、自分が楽しめればよいのです。仕事のプログラムだけでは、息が詰まってしまい楽しくありません。仕事でプログラムを書いて、息抜きにまたプログラムを書くというのは、プログラムを楽しいと思わない人から見たらちょっと変だと感じられるかも知れませんが、プログラミングが好きという人は多分皆同じようなものと思います。

どんなものができるかは、気まぐれで変わっていくかも知れませんが、今の時点では、超小型/軽量なLispであり、HTML5のCanvasを使ってお絵描きくらいはできるようなものを目指します。

今日は、Lispが対象とするデータ構造とそのデータ構造を外部表現から生成するためのリーダ関数を実装します。

何はともあれ、シンボルの実装

コンスセル(cons cell)を定義する前に、まずはシンボルを定義しましょう。シンボルは名前と値を持ちます。名前は文字列で、値は任意のLispオブジェクトです。シンボルの文字列表現もtoStringで作っておきましょう。

function Symbol(name, value) {
  this.name = name;
  this.value = value;
}

Symbol.prototype.toString: function () {
  return this.name;
};

シンボル表は、キーがシンボル名で値がシンボルそのものであるようなハッシュ表にします。このハッシュ表はJavaScriptのオブジェクトそのものです。

var symtbl = {};

グローバル関数にグローバル変数のように定義していますが、後でクロージャにする予定ですので、グローバルコードへのシンボル汚染は心配しなくてよいです。

次に、シンボルをシンボル表に登録するintern関数を下記のように実装します。引数のsymには文字列が与えられることを想定していますが、念のためString関数で文字列に変換しています。

function intern(sym) {
  sym = String(sym);
  var v = symtbl[sym];
  if (!v) {
    v = new Symbol(sym, true);
    symtbl[sym] = v;
  }
  return v;
}

とりあえず、すぐに必要となる最低限必要なシンボルを登録しておきます。

var T               = intern("t");
var NIL             = intern("nil");
var QUOTE           = intern("quote");

シンボルの値を求める関数と値をセットする関数を実装します。

function getValue(sym) {
  var v = symtbl[sym];
  return v && v.value;
}
function setValue(sym, value) {
  if (symbolp(sym) && sym !== T && sym !== NIL) {
    sym.value = value;
    return value;
  }
}
function symbolp(exp) { 
  return exp instanceof Symbol; 
}

以上がシンボルに関する基本的な操作です。

セル(cons cell)の構造

セルはcarとcdrがありますので、以下のように定義します。引数を省略したときはNILが入るようにします。

function Cell(car, cdr) {
  this.car = (car === undefined) ? NIL : car;
  this.cdr = (cdr === undefined) ? NIL : cdr;
}
Cell.prototype.toString = function () {
  return "(" + this.car + " . " + this.cdr + ")";
};

このCellを使って、car, cdr, consの基本関数は以下のように書けます。

function car(exp) {
  return (exp === NIL) ? NIL : exp.car;
}
function cdr(exp) {
  return (exp === NIL) ? NIL : exp.cdr;
}
function cons(x, y) {
  return new Cell(x, y);
}

caar, cadr, cdar, cddr なども作っておきましょう。

function caar(exp) { return car(car(exp)); }
function cadr(exp) { return car(cdr(exp)); }
function cdar(exp) { return cdr(car(exp)); }
function cddr(exp) { return cdr(cdr(exp)); }

Lispが扱うデータ構造はこれだけです。数値や文字列および配列はJavaScriptのデータそのものを使うことにします。

リーダ関数

Lispが扱うデータ構造の外部表現は、いわゆるカッコ表現（正確にはＳ式）ですが、その外部表現を読み込んで内部のデータ構造に変換するのがリーダ関数になります。JavaScriptには標準ではI/O関数が定義されていないので、文字列でＳ式を与えることにます。

入力文字列をinp、現在の読み込み位置をpos、スペース文字をspaces、10進文字をdigitsとします。

var inp;
var pos;
var spaces = " \n\t\r\f";
var digits = "0123456789";

ここでもそれぞれの変数や関数は後にクロージャにしますので、グローバル変数のように記述していきますが、実際にはローカル変数になります。

/*
 * 引数cが空白文字のときtrue, それ以外のときfalseを返す。
 */
function isSpace(c) {
  return c && spaces.indexOf(c) >= 0;
}
/*
 * 引数cが10進文字時のときtrue, それ以外のときfalseを返す。
 */
function isDigit(c) {
  return c && digits.indexOf(c) >= 0;
}
/*
 * 引数cが区切り文字のときtrue, それ以外のときfalseを返す。
 */
function isDelim(c) {
  if (!c) {
    return true;
  } else {
    switch (c) {
      case '\0': case '\r': case '\t': case '\f':
      case ' ':  case '"':  case '#':  case '\'':
      case '(':  case ')':  case ',':  case ';':
        return true;
      default:
        return false;
    }
  }
}
/*
 * 空白文字とコメント行を読み飛ばす。
 */
function skipSpace() {
  var c;
  while (true) {
    while (isSpace(c = peek())) {
      inpc();
    }
    if (!c) {
      return c;
    } else if ((c = peek()) == ';') {
        // skip comment
      while (peek() != '\n') {
        if (!inpc()) {
          return null;
        }
      }
    } else {
      return c;
    }
  }
}
/*
 * 入力文字列から1文字を読み込み、ポインタを進める。
 */
function inpc() {
  return inp.charAt(pos++);
}
/*
 * inp()と同様であるが、ポインタは進めない。
 */
function peek() {
  return inp.charAt(pos);
}

これらを使って、１つのトークンを読み込む関数readToken()は以下のように実装します。

function readToken() {
  if (!skipSpace()) {
    return;
  }
  var ch = inpc();
  if (!isDelim(ch)) {
    var arr = [ ch ];
    while (!isDelim(peek())) {
      arr.push(inpc());
    }
    return arr.join("");
  } else {
    return ch;
  }
}

Ｓ式を読み込むトップレベルの関数readExp()は以下のようになります。ここでは、大体の構造のみで、後で配列とか文字とか機能を追加します。

function readExp() {
  var token = readToken();
  if (!token) {
    return null;
  }
  switch (token) {
    case '(': return readList();
    case '"': return readString();
    case "'": return cons(QUOTE, readExp());
    default:
      var c = token.charAt(0);
      if (isDigit(c) || c === '-' || c === '+' || c === '.') {
        var rv = Number(token);
        return isNaN(rv) ? intern(token) : rv;
      } else {
        return intern(token);
      }
  }
}

ちょっと長くなってきたので、readList()、readString()の実装は次回に回します。

次回は、リーダ機能の残りと、リーダと反対の機能であるＳ式を文字列として出力するプリンタ機能を実装します。