簡易LISP処理系の実装例（JavaScript版）

【他言語版へのリンク記事】[簡易LISP処理系の実装例【各言語版まとめ】](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)

この記事は，下記拙作記事のJavaScript版を抜粋・修正したものを利用した，簡易LISP処理系（["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)）の実装例をまとめたものです．

* [『括弧文字列』簡易パーサ実装例まとめ](https://qiita.com/ytaki0801/items/b8d7d4c778fe98966ce5)
* [リスト処理関数（cons,car,cdr,eq,atom）実装例まとめ](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)

最低限の機能をもったLISP処理系の実装の場合，本体である評価器（eval）実装はとても簡単であり，むしろ，字句・構文解析を行うS式入出力やリスト処理実装の方が開発言語ごとの手間が多く，それが敷居になっている人向けにまとめています．

#処理系の概要

**【2020/11/05追記】**[`https://ytaki0801.github.io/jmclisp.html`](https://ytaki0801.github.io/jmclisp.html)のWebブラウザによる実行例は次の通り．Chrome 86 (Windows/Android)，Safari 14 (iOS)にて確認（画像はiPod touchのSafari）．
![jmclisp.js_iPodtouch.png](https://raw.githubusercontent.com/ytaki0801/Samples/master/jmclisp.js_iPodtouch.PNG)
Node.js 10.21での実行例は次の通り．

```shell
$ nodejs
> .load jmclisp.js
（ファイル読み込み時の表示はカット）
> s_rep("(car (cdr '(10 20 30)))")
'20'
> s_rep("((lambda (x) (car (cdr x))) '(abc def ghi))")
'def'
> s_rep("((lambda (f x y) (f x (f y '()))) 'cons '10 '20)")
'(10 20)'
> s_rep("((lambda (f x y) (f x (f y '()))) \
...       '(lambda (x y) (cons x (cons y '()))) \
...       '10 '20)")
'(10 (20 ()))'
> s_rep("((lambda (assoc k v) (assoc k v)) \
...      '(lambda (k v) \
.....       (cond ((eq v '()) nil) \
.......           ((eq (car (car v)) k) \
.........          (car v)) \
.......           ('t (assoc k (cdr v))))) \
...      'Orange \
...      '((Apple . 120) (Orange . 210) (Lemon . 180)))")
'(Orange . 210)'
```

実装内容は次の通り．

* ["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースにした評価器
* 数字を含むアトムは全てシンボルとし，変数の値とする場合は`quote`（`'`）を使用
* 構文として`quote`の他，`cond`と`lambda`が使用可能
* 組込関数：`atom` `eq` `cons` `car` `cdr`（内部でコンスセルを作成）
* 真偽値は`t`（真）および`nil`（偽）＝空リスト＝`null`
* エラーチェックなし，モジュール化なし，ガーベジコレクションなし

"McCarthy's Original Lisp"の詳細については[まとめ記事](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)を参照．ダイナミックスコープということもあり，実行例ではlambda式を`letrec`（Scheme）や`labels`（Common Lisp）などの代わりに使用しています．

#実装例

##ソースコード一式

```jmclisp.js
//
// JMC Lisp: defined in McCarthy's 1960 paper,
// with S-expression input/output and basic list processing
//


// basic list processing: cons, car, cdr, eq, atom
function cons(x, y) { return Object.freeze([x, y]); }
function car(s) { return s[0]; }
function cdr(s) { return s[1]; }
function eq(s1, s2) { return s1 === s2; }
function atom(s) { return typeof s == 'string' || eq(s, null) || eq(s, true) || eq(s, false); }


// S-expression input: s_read

function s_lex(s) {
  s = s.replace(/(\(|\)|\'|\,)/g, ' $1 ');
  return s.split(/\s+/).filter(x => x != '');
}

function s_syn(s) {
  function quote(x, s) {
    if (s.length != 0 && s.slice(-1)[0] == '\'') {
      s.pop();
      return cons("quote", cons(x, null));
    } else {
      return x
    }
  }
  var t = s.pop();
  if (t == ')') {
    var r = null;
    while (s.slice(-1)[0] != '(') {
      if (s.slice(-1)[0] == '.') {
        s.pop();
        r = cons(s_syn(s), car(r));
      } else {
        r = cons(s_syn(s), r);
      }
    }
    s.pop();
    return quote(r, s);
  } else {
    return quote(t, s);
  }
}

function s_read(s) { return s_syn(s_lex(s)); }


// S-expression output: s_string

function s_strcons(s) {
  var sa_r = s_string(car(s));
  var sd = cdr(s);
  if (eq(sd, null)) {
    return sa_r;
  } else if (atom(sd)) {
    return sa_r + ' . ' + sd;
  } else {
    return sa_r + ' ' + s_strcons(sd);
  }
}

function s_string(s) {
  if      (eq(s, null))  return '()';
  else if (eq(s, true))  return 't';
  else if (eq(s, false)) return 'nil';
  else if (atom(s))
    return s;
  else
    return '(' + s_strcons(s) + ')';
}


// JMC Lisp evaluator: s_eval

function caar(x) { return car(car(x)); }
function cadr(x) { return car(cdr(x)); }
function cadar(x) { return car(cdr(car(x))); }
function caddr(x) { return car(cdr(cdr(x))); }
function caddar(x) { return car(cdr(cdr(car(x)))); }

function s_null(x) { return eq(x, null); }

function s_append(x, y) {
  if (s_null(x)) return y;
  else return cons(car(x), s_append(cdr(x), y));
}

function s_list(x, y) { return cons(x, cons(y, null)); }

function s_pair(x, y) {
  if (s_null(x) && s_null(y)) return null;
  else if (!atom(x) && !atom(y))
    return cons(s_list(car(x), car(y)), s_pair(cdr(x), cdr(y)));
}

function s_assoc(x, y) {
  if (eq(caar(y), x)) return cadar(y);
  else return s_assoc(x, cdr(y));
}

function s_eval(e, a) {
  if      (eq(e, "t"))   return true;
  else if (eq(e, "nil")) return false
  else if (atom(e)) return s_assoc(e, a);
  else if (atom(car(e))) {
    if      (eq(car(e), "quote")) return cadr(e);
    else if (eq(car(e), "atom"))  return atom(s_eval(cadr(e), a));
    else if (eq(car(e), "eq"))    return eq(  s_eval(cadr(e), a),
                                              s_eval(caddr(e), a));
    else if (eq(car(e), "car"))   return car( s_eval(cadr(e), a));
    else if (eq(car(e), "cdr"))   return cdr( s_eval(cadr(e), a));
    else if (eq(car(e), "cons"))  return cons(s_eval(cadr(e), a),
                                             s_eval(caddr(e), a));
    else if (eq(car(e), "cond"))  return evcon(cdr(e), a);
    else return s_eval(cons(s_assoc(car(e), a), cdr(e)), a);
  } else if (eq(caar(e), "lambda"))
      return s_eval(caddar(e),
                    s_append(s_pair(cadar(e), evlis(cdr(e), a)), a));
  else console.log("Error");
}

function evcon(c, a) {
  if (s_eval(caar(c), a)) return s_eval(cadar(c), a);
  else return evcon(cdr(c), a);
}

function evlis(m, a) {
  if (s_null(m)) return null;
  else return cons(s_eval(car(m), a), evlis(cdr(m), a));
}


// REP (no Loop): s_rep
function s_rep(e) { return s_string(s_eval(s_read(e), s_read("()"))); }

```

##解説

* リスト処理：`cons` `car` `cdr` `eq` `atom`
[先の記事](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)より，ほぼそのまま抜粋．

* S式入力：`s_read`
[先の記事](https://qiita.com/ytaki0801/items/b8d7d4c778fe98966ce5)から，字句解析部を`()`および`'`の識別に変更（`s_lex`），抽象構文木生成部をドット対とクォート記号対応としつつ，リスト処理関数でコンスセルによる構文木を生成するよう変更（`s_syn`），それらをまとめたS式入力関数`s_read`を定義．

* S式出力：`s_string`
S式出力部は新規に作成．内部では`null`である空リストは`()`を，真偽値は`t` `nil`を出力するよう設定．

* 評価器：`s_eval`＋ユーティリティ関数
["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースに`s_eval`関数およびユーティリティ関数を作成．

* REP (no Loop)：`s_rep`
`s_read`→`s_eval`→`s_string`をまとめた`s_rep`を定義．

#備考

##記事に関する補足
* 評価器のみの場合，約50行／1900バイトほど．Python版とほぼ同じかな．

##更新履歴
* 2020-11-05：Webブラウザによる実行例を追加
* 2020-09-11：`eq`の定義について，`==`ではなく`===`を使用（コメントより）
* 2020-09-11：初版公開