すみません，半分くらいタイトル詐欺です．
- コメント文を区別するための記述以外は文字列の配列構文のみを使用しています．
- もちろん，JSON記述をパースしただけではLISP評価器として動きません．
なお，リファレンス実装としてNode.js（JavaScript）で実際に動くようにしています．他の言語でも動くようになったら追記するかも．
【追記】
- JSON記述からのS式生成（Schemeインタプリタで実行可能）について追加しました．
- JSONライブラリを用いてC言語実装を行いました．
- Python3でも実装しました．
定義してみた目的
-
面白そうだったから．レキシカルスコープのラムダ式による超循環評価器を他の言語で実装・実行しやすくするため．
ダイナミックスコープのラムダ式による超循環評価器は，Paul Graham氏がCommon Lispで実装した"McCarthy's Original Lisp"（jmc.lisp）がリファレンス実装としておすすめです．S式入出力部の実装を含めた他のプログラミング言語への移植も容易です．
JSON記述本体
下記のGitHubリポジトリにmcelisp.jsonというファイル名で公開しています．
ですが，コメントとサンプルコードを除けば100行もないので，ここにベタ投下します．今後の修正等はリポジトリの方のみとなるかもしれませんが，バグとかありましたらお知らせ下さい．
mcelisp.json
{
"comments": [
"Meta-Circular Evaluator of LISP in JSON",
"This code is licensed under CC0.",
"https://creativecommons.org/publicdomain/zero/1.0/",
"Descriptions of each lambda expressions:",
"[0] bootstrap env, with initial env as a plist",
"[1] EVL: eval 'quote', 'cond' and 'lambda' and call apply",
"[2] APY: apply 'car', 'cdr', 'cons', 'eq?', 'pair?' and closure",
"[3] APD: utility function to append two lists",
"[4] PLS: utility function to make a plist for local env",
"[5] GVP: utility function to get a value from plist",
"[6] ECD: utility function to eval cond-ret lists",
"[7] EAG: utility function to eval args",
"[8] S: sample code to return the following",
"[ [ 'O' ], ",
" [ 'O', 'O' ], ",
" [ 'O', 'O', 'O' ], ",
" [ 'O', 'O', 'O', 'O' ], ",
" [ 'O', 'O', 'O', 'O', 'O' ] ]",
"Note that list structure is not conscells but linked list",
"and lexical scope is supposed in lambda expressions."
],
"mcelisp":
[["lambda",["EVL","APY","APD","PLS","GVP","ECD","EAG","S"],
["EVL","S",
["quote",
["car","car","cdr","cdr","cons","cons","eq?","eq?","pair?","pair?"]],
"APD","PLS","GVP","ECD","EAG","APY"]],
[["lambda",["U"],["U","U"]],
["lambda",["U"],
["lambda",["S","E","APD","PLS","GVP","ECD","EAG","APY"],
["cond",
[["pair?","S"],
["cond",
[["eq?",["car","S"],["quote","quote"]],
["car",["cdr","S"]]],
[["eq?",["car","S"],["quote","cond"]],
["ECD",["cdr","S"],"E",
"U","APD","PLS","GVP","ECD","EAG","APY"]],
[["eq?",["car","S"],["quote","lambda"]],
["APD","S",["cons","E",["quote",[]]]]],
["else",["APY",[["U","U"],["car","S"],"E",
"APD","PLS","GVP","ECD","EAG","APY"],
["EAG",["cdr","S"],"E",
"U","APD","PLS","GVP","ECD","EAG","APY"],
"U","APD","PLS","GVP","ECD","EAG","APY"]]]],
["else",["GVP","S","E"]]]]]],
["lambda",["F","A","U","APD","PLS","GVP","ECD","EAG","APY"],
["cond",
[["pair?","F"],
[["U","U"],["car",["cdr",["cdr","F"]]],
["APD",["PLS",["car",["cdr","F"]],"A"],
["car",["cdr",["cdr",["cdr","F"]]]]],
"APD","PLS","GVP","ECD","EAG","APY"]],
[["eq?","F",["quote","car"]],["car",["car","A"]]],
[["eq?","F",["quote","cdr"]],["cdr",["car","A"]]],
[["eq?","F",["quote","cons"]],
["cons",["car","A"],["car",["cdr","A"]]]],
[["eq?","F",["quote","eq?"]],
["eq?",["car","A"],["car",["cdr","A"]]]],
[["eq?","F",["quote","pair?"]],["pair?",["car","A"]]]]],
[["lambda",["U"],["U","U"]],
["lambda",["U"],
["lambda",["A","B"],
["cond",
[["eq?","A",["quote",[]]],"B"],
["else",["cons",["car","A"],[["U","U"],["cdr","A"],"B"]]]]]]],
[["lambda",["U"],["U","U"]],
["lambda",["U"],
["lambda",["A","B"],
["cond",
[["eq?","A",["quote",[]]],["quote",[]]],
[["eq?","B",["quote",[]]],["quote",[]]],
["else", ["cons",["car","A"],
["cons",["car","B"],
[["U","U"],["cdr","A"],["cdr","B"]]]]]]]]],
[["lambda",["U"],["U","U"]],
["lambda",["U"],
["lambda",["K","V"],
["cond",
[["eq?","V",["quote",[]]],["quote",[]]],
[["eq?","K",["car","V"]],["car",["cdr","V"]]],
["else",[["U","U"],"K",["cdr",["cdr","V"]]]]]]]],
[["lambda",["M"],["M","M"]],
["lambda",["M"],
["lambda",["P","E","U","APD","PLS","GVP","ECD","EAG","APY"],
["cond",
[["eq?","P",["quote",[]]], ["quote",[]]],
[["eq?",["car",["car","P"]],["quote","else"]],
[["U","U"],["car",["cdr",["car","P"]]],"E",
"APD","PLS","GVP","ECD","EAG","APY"]],
[[["U","U"],["car",["car","P"]],"E",
"APD","PLS","GVP","ECD","EAG","APY"],
[["U","U"],["car",["cdr",["car","P"]]],"E",
"APD","PLS","GVP","ECD","EAG","APY"]],
["else",[["M","M"],["cdr","P"],"E",
"U","APD","PLS","GVP","ECD","EAG","APY"]]]]]],
[["lambda",["M"],["M","M"]],
["lambda",["M"],
["lambda",["A","E","U","APD","PLS","GVP","ECD","EAG","APY"],
["cond",
[["eq?","A",["quote",[]]],["quote",[]]],
["else",["cons",[["U","U"],["car","A"],"E",
"APD","PLS","GVP","ECD","EAG","APY"],
[["M","M"],["cdr","A"],"E",
"U","APD","PLS","GVP","ECD","EAG","APY"]]]]]]],
["quote",
[[["lambda",["U"],["U","U"]],
["lambda",["U"],
["lambda",["X","R"],
["cond",
[["eq?","X",["quote",[]]],"R"],
["else",[["U","U"],["cdr","X"],["cons","X","R"]]]]]]],
["quote",["O","O","O","O","O"]],
["quote",[]]]
]]
}
評価器の解説
超循環評価器としての最小構成（いわゆる純LISP）を目指したことから，Schemeの次の構文・関数相当のみで実装することを想定しています．なお，ラムダ式はレキシカルスコープですが，大域環境は想定していません．すなわち，Schemeでいうdefineの類はありません．
- 基本構文：
lambda（レキシカルスコープ），quote，cond - 基本関数：
car，cdr，cons，eq?，pair?
評価器自体はひとつのラムダ式として構成されており，eval/applyなどは不動点コンビネータによる自己再帰や引数共有による無名相互再帰を用いています．実行コードは，このラムダ式への直値適用を想定しています．
なお，必要な関数定義がそれほど多くないこともあり，不動点コンビネータは有名どころのY/Zコンビネータ等ではなく，Uコンビネータを主に使用しています（Zコンビネータをβ展開した非無名駆動型のラムダ式で，複数の引数に対応可能）．前節のJSON記述本体の最後の方に書かれているサンプルコードもUコンビネータで書かれており，次のSchemeコードと等価です．
(((lambda (U) (U U))
(lambda (U)
(lambda (X R)
(cond ((eq? X (quote ())) R)
(else ((U U) (cdr X) (cons X R)))))))
(quote (O O O O O))
(quote ()))
また，JSONとS式の仕様の違いから，リスト構造はコンスセルではなく連結リストを想定しています．このため，consはCDR部にリスト（配列）しか指定できず，局所環境は属性リスト（名前と値が交互に並ぶ連結リスト）で構成されています．
JavaScriptによるリファレンス実装
先のGitHubリポジトリでも公開していますが，こちらも本体は50行程度のためそのまま掲載します．
mcelisp-json-node.js(Node.js10.24)
////
//// Meta-Circular Evaluator of LISP in JavaScript,
//// a reference implementation of mcelisp.json
////
//// This code is licensed under CC0.
//// https://creativecommons.org/publicdomain/zero/1.0/
////
((EVL,APY,APD,PLS,GVP,ECD,EAG,S)=> // bootstrap env
EVL(S, ['car','car','cdr','cdr','cons','cons',
'eq?','eq?','pair?','pair?'],
APD,PLS,GVP,ECD,EAG,APY))(
(U=>U(U))(U=>(S,E,APD,PLS,GVP,ECD,EAG,APY)=> // EVL
typeof(S) == 'string' ? GVP(S,E) :
S[0] == 'quote' ? S[1] :
S[0] == 'cond' ? ECD(S.slice(1),E,U,APD,PLS,GVP,ECD,EAG,APY) :
S[0] == 'lambda' ? APD(S,[E]) :
APY(U(U)(S[0],E,APD,PLS,GVP,ECD,EAG,APY),
EAG(S.slice(1),E,U,APD,PLS,GVP,ECD,EAG,APY),
U,APD,PLS,GVP,ECD,EAG,APY)),
((F,A,U,APD,PLS,GVP,ECD,EAG,APY)=> // APY
typeof(F) == 'string' ?
F == 'car' ? A[0][0] :
F == 'cdr' ? A[0].slice(1) :
F == 'cons' ? [A[0]].concat(A[1]) :
F == 'eq?' ? (A[0] == A[1] || (A[0].length == 0 && A[1].length == 0)) :
F == 'pair?' ? Array.isArray(A[0]) : [] :
U(U)(F[2],APD(PLS(F[1],A),F[3]),APD,PLS,GVP,ECD,EAG,APY)),
(U=>U(U))(U=>(A,B)=> // APD
A.length == 0 ? B :
[A[0]].concat(U(U)(A.slice(1),B))),
(U=>U(U))(U=>(A,B)=> // PLS
A.length == 0 ? [] :
B.length == 0 ? [] :
[A[0],B[0]].concat(U(U)(A.slice(1),B.slice(1)))),
(U=>U(U))(U=>(K,V)=> // GVP
V.length == 0 ? [] :
K == V[0] ? V[1] :
U(U)(K,V.slice(2))),
(M=>M(M))(M=>(P,E,U,APD,PLS,GVP,ECD,EAG,APY)=> // ECD
P.length == 0 ? [] :
P[0][0] == 'else' ?
U(U)(P[0][1],E,APD,PLS,GVP,ECD,EAG,APY) :
U(U)(P[0][0],E,APD,PLS,GVP,ECD,EAG,APY) ?
U(U)(P[0][1],E,APD,PLS,GVP,ECD,EAG,APY) :
M(M)(P.slice(1),E,U,APD,PLS,GVP,ECD,EAG,APY)),
(M=>M(M))(M=>(A,E,U,APD,PLS,GVP,ECD,EAG,APY)=> // EAG
A.length == 0 ? [] :
[U(U)(A[0],E,APD,PLS,GVP,ECD,EAG,APY)].concat(
M(M)(A.slice(1),E,U,APD,PLS,GVP,ECD,EAG,APY))),
require("./mcelisp.json")["mcelisp"]
// [[["lambda",["U"],["U","U"]],
// ["lambda",["U"],
// ["lambda",["X","R"],
// ["cond",
// [["eq?","X",["quote",[]]],"R"],
// ["else",[["U","U"],["cdr","X"],["cons","X","R"]]]]]]],
// ["quote",["A","A","A","A","A"]],
// ["quote",[]]]
//
// => [ [ 'A' ],
// [ 'A', 'A' ],
// [ 'A', 'A', 'A' ],
// [ 'A', 'A', 'A', 'A' ],
// [ 'A', 'A', 'A', 'A', 'A' ] ]
)
実行例は次の通り．上記JavaScriptコードの最後のコメント文にある実行結果と異なることに御注意下さい．
$ nodejs
> .load mcelisp-json-node.js
（読み込み時の出力表示は省略）
[ [ 'O' ],
[ 'O', 'O' ],
[ 'O', 'O', 'O' ],
[ 'O', 'O', 'O', 'O' ],
[ 'O', 'O', 'O', 'O', 'O' ] ]
>
mcelisp.jsonのS式への変換
GaucheのJSONライブラリ＋slibのpretty-printでS式を生成するSchemeプログラムをリポジトリに追加しました．これを用いることで，下記の通りmcelisp.jsonをSchemeインタプリタで超循環評価器として動かすことができます．
$ ./JSON-to-S-Gauche.scm mcelisp.json mcelisp | chibi-scheme
> ((O) (O O) (O O O) (O O O O) (O O O O O))
> $
C言語（＋JSONライブラリ）による実装
JSONライブラリ『parson』を用いたC言語実装も行いました．S式入出力だけでなく内部リスト（配列）構造もライブラリを用いているためC言語実装としては短いのですが，それでも150行弱ほどあるため，実際のコードは公開リポジトリを御参照下さい．
下記に実行例のみ示します．ちなみに，評価器としては普通に動くのですが，その評価器上でmcelisp.jsonを走らせるととても遅かったりします．大域環境ないからってメモリ解放サボってるからかなあ．
$ cc -DEVAL -o mcelisp-json mcelisp-json.c parson.c
$ time ./mcelisp-json
[["A"],["A","A"],["A","A","A"],["A","A","A","A"],["A","A","A","A","A"]]
real 0m0.004s
user 0m0.004s
sys 0m0.000s
$ cc -o mcelisp-json mcelisp-json.c parson.c
$ time ./mcelisp-json
[["O"],["O","O"],["O","O","O"],["O","O","O","O"],["O","O","O","O","O"]]
real 0m5.923s
user 0m4.157s
sys 0m1.749s
$
Python 3による実装
Python 3でも実装しました．JavaScript版と同じく本体は50行程度ですのでそのまま掲載します．
Python3
#
# Meta-Circular Evaluator of LISP in Python 3,
# a reference implementation of mcelisp.json
#
# This code is licensed under CC0.
# https://creativecommons.org/publicdomain/zero/1.0/
#
(lambda EVL,APY,PLS,GVP,ECD,EAG,S:
EVL(S,['car','car','cdr','cdr','cons','cons','eq?','eq?','pair?','pair?'],
PLS,GVP,ECD,EAG,APY))(
(lambda U: U(U))( # EVL
lambda U: lambda S,E,PLS,GVP,ECD,EAG,APY:
GVP(S,E) if isinstance(S,str) else
S[1] if S[0] == 'quote' else
ECD(S[1:],E,U,PLS,GVP,ECD,EAG,APY) if S[0] == 'cond' else
S+[E] if S[0] == 'lambda' else
APY(U(U)(S[0],E,PLS,GVP,ECD,EAG,APY),
EAG(S[1:],E,U,PLS,GVP,ECD,EAG,APY),
U,PLS,GVP,ECD,EAG,APY)),
(lambda F,A,U,PLS,GVP,ECD,EAG,APY: # APY
U(U)(F[2],PLS(F[1],A)+F[3],PLS,GVP,ECD,EAG,APY)
if isinstance(F, list) else
A[0][0] if F == 'car' else
A[0][1:] if F == 'cdr' else
[A[0]]+A[1] if F == 'cons' else
(A[0] == A[1]) or (A[0] == [] and A[0] == []) if F == 'eq?' else
isinstance(A[0], list) if F == 'pair?' else []),
(lambda U: U(U))( # PLS
lambda U: lambda A,B:
[] if (A == [] or B == []) else
[A[0],B[0]] + U(U)(A[1:], B[1:])),
(lambda U: U(U))( # GVP
lambda U: lambda K,V:
[] if V == [] else V[1] if K == V[0] else U(U)(K,V[2:])),
(lambda M: M(M))( # ECD
lambda M: lambda P,E,U,PLS,GVP,ECD,EAG,APY:
[] if P == [] else
U(U)(P[0][1],E,PLS,GVP,ECD,EAG,APY)
if P[0][0] == 'else' or U(U)(P[0][0],E,PLS,GVP,ECD,EAG,APY) else
M(M)(P[1:],E,U,PLS,GVP,ECD,EAG,APY)),
(lambda M: M(M))( # EAG
lambda M: lambda A,E,U,PLS,GVP,ECD,EAG,APY:
[] if A == [] else
[U(U)(A[0],E,PLS,GVP,ECD,EAG,APY)]
+ M(M)(A[1:],E,U,PLS,GVP,ECD,EAG,APY)),
__import__('json').load(open('mcelisp.json'))['mcelisp']
# [[["lambda",["U"],["U","U"]],
# ["lambda",["U"],
# ["lambda",["X","R"],
# ["cond",
# [["eq?","X",["quote",[]]],"R"],
# ["else",[["U","U"],["cdr","X"],["cons","X","R"]]]]]]],
# ["quote",["A","A","A","A","A"]],
# ["quote",[]]]
#
# => [['A'], ['A', 'A'], ['A', 'A', 'A'], ['A', 'A', 'A', 'A'], ['A', 'A', 'A', 'A', 'A']]
)
$ python3 -q -i < mcelisp-json-python3.py
>>> ... ... ... ... ... ... ... >>> ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... [['O'], ['O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O', 'O'], ['O', 'O', 'O', 'O', 'O']]
>>>
$
備考
記事に関する補足
- 今回初めて，JSONに正式なコメント記述方法がないことを知りました…（恥）．
更新履歴
- 2021-07-20：Python3版実装について追記，S式生成の記述変更
- 2021-07-19：C言語実装について追記，Schemeコード生成の記述変更
- 2021-07-19：
mcelisp-json-pp.scmについて追記 - 2021-07-18：初版公開（
mcelisp.json，JavaScript実装）