【他言語版へのリンク記事】簡易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).
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
の他,cond
とlambda
が使用可能 - 組込関数:
atom
eq
cons
car
cdr
(内部でコンスセルを作成) - 真偽値は
t
(真)およびnil
(偽)=空リスト=null
- エラーチェックなし,モジュール化なし,ガーベジコレクションなし
"McCarthy's Original Lisp"の詳細についてはまとめ記事を参照.ダイナミックスコープということもあり,実行例ではlambda式をletrec
(Scheme)やlabels
(Common Lisp)などの代わりに使用しています.
#実装例
##ソースコード一式
//
// 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_read
→s_eval
→s_string
をまとめたs_rep
を定義.
#備考
##記事に関する補足
- 評価器のみの場合,約50行/1900バイトほど.Python版とほぼ同じかな.
##更新履歴
- 2020-11-05:Webブラウザによる実行例を追加
- 2020-09-11:
eq
の定義について,==
ではなく===
を使用(コメントより) - 2020-09-11:初版公開