10
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

簡易LISP処理系の実装例(JavaScript版)

Last updated at Posted at 2020-09-11

【他言語版へのリンク記事】簡易LISP処理系の実装例【各言語版まとめ】

この記事は,下記拙作記事のJavaScript版を抜粋・修正したものを利用した,簡易LISP処理系("McCarthy's Original Lisp")の実装例をまとめたものです.

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

#処理系の概要

【2020/11/05追記】https://ytaki0801.github.io/jmclisp.htmlのWebブラウザによる実行例は次の通り.Chrome 86 (Windows/Android),Safari 14 (iOS)にて確認(画像はiPod touchのSafari).
jmclisp.js_iPodtouch.png
Node.js 10.21での実行例は次の通り.

$ 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"をベースにした評価器
  • 数字を含むアトムは全てシンボルとし,変数の値とする場合はquote')を使用
  • 構文としてquoteの他,condlambdaが使用可能
  • 組込関数:atom eq cons car cdr(内部でコンスセルを作成)
  • 真偽値はt(真)およびnil(偽)=空リスト=null
  • エラーチェックなし,モジュール化なし,ガーベジコレクションなし

"McCarthy's Original Lisp"の詳細についてはまとめ記事を参照.ダイナミックスコープということもあり,実行例では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
    先の記事より,ほぼそのまま抜粋.

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

  • S式出力:s_string
    S式出力部は新規に作成.内部ではnullである空リストは()を,真偽値はt nilを出力するよう設定.

  • 評価器:s_eval+ユーティリティ関数
    "McCarthy's Original Lisp"をベースにs_eval関数およびユーティリティ関数を作成.

  • REP (no Loop):s_rep
    s_reads_evals_stringをまとめたs_repを定義.

#備考

##記事に関する補足

  • 評価器のみの場合,約50行/1900バイトほど.Python版とほぼ同じかな.

##更新履歴

  • 2020-11-05:Webブラウザによる実行例を追加
  • 2020-09-11:eqの定義について,==ではなく===を使用(コメントより)
  • 2020-09-11:初版公開
10
9
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
10
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?