JSONでLISPの超循環評価器を定義してみた

すみません，半分くらいタイトル詐欺です．

* コメント文を区別するための記述以外は**文字列の配列構文のみ**を使用しています．
* もちろん，JSON記述をパースしただけでは**LISP評価器として動きません**．

なお，リファレンス実装としてNode.js（JavaScript）で実際に動くようにしています．他の言語でも動くようになったら追記するかも．
【追記】
* JSON記述からのS式生成（**Schemeインタプリタで実行可能**）について追加しました．
* [JSONライブラリ](https://github.com/kgabis/parson)を用いてC言語実装を行いました．
* Python3でも実装しました．

# 定義してみた目的

* ~~面白そうだったから~~．レキシカルスコープのラムダ式による超循環評価器を他の言語で実装・実行しやすくするため．

ダイナミックスコープのラムダ式による超循環評価器は，Paul Graham氏がCommon Lispで実装した["McCarthy's Original Lisp"（jmc.lisp）](http://paulgraham.com/lispcode.html)がリファレンス実装としておすすめです．[S式入出力部の実装を含めた他のプログラミング言語への移植も容易です．](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)

# JSON記述本体

下記のGitHubリポジトリに`mcelisp.json`というファイル名で公開しています．

https://github.com/ytaki0801/mcelisp.json

ですが，コメントとサンプルコードを除けば100行もないので，ここにベタ投下します．今後の修正等はリポジトリの方のみとなるかもしれませんが，バグとかありましたらお知らせ下さい．

```json: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",[]]]

     ]]
}
```

# 評価器の解説

[超循環評価器](https://en.wikipedia.org/wiki/Meta-circular_evaluator)としての最小構成（いわゆる[純LISP](https://ja.wikipedia.org/wiki/%E7%B4%94LISP)）を目指したことから，[Scheme](https://ja.wikipedia.org/wiki/Scheme)の次の構文・関数相当のみで実装することを想定しています．なお，ラムダ式はレキシカルスコープですが，大域環境は想定していません．すなわち，**Schemeでいう`define`の類はありません**．

* 基本構文：`lambda`（レキシカルスコープ），`quote`，`cond`
* 基本関数：`car`，`cdr`，`cons`，`eq?`，`pair?`

評価器自体はひとつのラムダ式として構成されており，eval/applyなどは[不動点コンビネータによる自己再帰](https://qiita.com/ytaki0801/items/596efbbcb07d38630bc9)や[引数共有による無名相互再帰](https://qiita.com/ytaki0801/items/df416412b8bee6212d92)を用いています．実行コードは，このラムダ式への直値適用を想定しています．

なお，必要な関数定義がそれほど多くないこともあり，不動点コンビネータは有名どころの[Y/Zコンビネータ](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF#Y%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF)等ではなく，Uコンビネータを主に使用しています（Zコンビネータをβ展開した非無名駆動型のラムダ式で，複数の引数に対応可能）．前節のJSON記述本体の最後の方に書かれているサンプルコードもUコンビネータで書かれており，次のSchemeコードと等価です．

```lisp
(((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行程度のためそのまま掲載します．

```js: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コードの最後のコメント文にある実行結果と異なることに御注意下さい．**

```sh:
$ 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](http://practical-scheme.net/gauche/)のJSONライブラリ＋[slib](https://people.csail.mit.edu/jaffer/SLIB.html)の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](https://github.com/kgabis/parson)』を用いたC言語実装も行いました．S式入出力だけでなく内部リスト（配列）構造もライブラリを用いているためC言語実装としては短いのですが，それでも150行弱ほどあるため，実際のコードは[公開リポジトリ](https://github.com/ytaki0801/mcelisp.json)を御参照下さい．

下記に実行例のみ示します．ちなみに，評価器としては普通に動くのですが，その評価器上で`mcelisp.json`を走らせるととても遅かったりします．大域環境ないからってメモリ解放サボってるからかなあ．

```sh
$ 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行程度ですのでそのまま掲載します．

```py: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']]
         
         )
```
```sh:
$ 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実装）