# Japan言語なるものを設計した

[KMC](https://www.kmc.gr.jp/)のhatsusatoです。
この記事は[KMC Advent Calendar 2021](https://adventar.org/calendars/6895)の20日目の記事です。

## TL;DR
**J**son **A**s a **P**rogramming language **A**nd object **N**otation[^japan]
構文がJSONそのものになっている純粋関数型プログラミング言語です。

{
  "let": [
    {
      // 階乗を計算する関数factorialを定義
      "function": {"factorial": 0},
      "": {
        "let": {"n": "factorial"},
        "": {
          "if": {"<": [0, "n"]},
          "then": {
            "let": {"n-1": {"-": ["n", 1]}},
            "": {"*": ["n", {"factorial": "n-1"}]}
          },
          "else": 1
        }
      }
    }
  ],
  "": {
    // 120を出力
    "print": {"factorial": 5}
  }
}

LispはS式でできているのがえらい[^sexp]ので、そのS式をJSONで置き換えた言語は作れないだろうかと考えました。多分どこかで誰かが考えたことのあるアイデアだろうと思いますが、言語設計は十人十色なので、気にせず言語仕様を紹介しようと思います。

[TOC]

# Syntax
任意のJSON文字列がJapan言語として評価できます[^well-defined]が、ちゃんとした計算を行うには、Japan言語に合わせたJSONを構築してやる必要があります。

## object
- objectはそのobjectがもつキー(の集合)によって、マクロ展開・関数呼び出し・辞書へと分類される。
- objectが評価された環境において、対応するキーをもつマクロ・関数が定義されていれば、それぞれマクロ展開・関数呼び出しとして評価される。
- マクロ展開においては、objectがもつ各値を評価せずにそのまま展開される。
- 関数呼び出しにおいては、まずobjectがもつ値を評価したのちに、その値が引数として関数へ引き渡される。
- 詳細は後述。
- マクロ展開でも関数呼び出しでもないobjectは辞書として評価される。
- 辞書としてのobjectは、そのobjectがもつすべての値を(再帰的に)評価した結果でそれぞれの元の値を置き換えたobjectとして解釈される。
- 疑似コード: `eval({k1: v1, k2: v2}) = {k1: eval(v1), k2: eval(v2)}`

## array
- arrayの各要素を(再帰的に)評価した結果を元の順で並べたarrayとして解釈される。
- 疑似コード: `eval([v1, v2, v3]) = [eval(v1), eval(v2), eval(v3)]`

## string
- 基本的に変数名として解釈される。
- ただし、string中に含まれる`.`は特別な意味をもつ。
- `.`以外の文字は、JSONとして許される限り、好きなものを変数名に用いることができる。
- `""`も有効な変数名として解釈される。
- stringの先頭に`.`が現れるときは、先頭から`.`を1つ除いた文字列のリテラルとして解釈される。
- 例: `".abc"`は長さ3の文字列`abc`を意味する。
- 例: `".."`は長さ1の文字列`.`を意味する。
- 例: `"."`は長さ0の空文字列を意味する。
- string中の先頭以外に`.`が含まれるときは、JavaScriptにおけるobjectのプロパティアクセスと同様に評価する。
- 例: `x`の評価結果が`{"a": 1, "b": 2}`のとき、`x.a`は`x`のキー`a`に対応する値`1`へと評価される。
- `.`の右辺は変数名ではなく字句通りに解釈される。
- `x`が`a`を含まないときは`null`へと評価される。
- `x`がobjectでないとき、`x.a`は`null`へと評価される。
- もちろん`.`は左結合。

## number, boolean, null
- そのまま字句通りの値として解釈される。

# Semantics

## `let`マクロ
`"let"`と`""`をキーにもつobject。

{
  "let": {"x": 1},
  "": "x"
}

### `let`マクロによるローカル変数の導入
- `"let"`キーの値がobjectのとき、そのobjectの各キーを変数名として環境に導入した上で`""`キーの値を評価する。

  // 疑似コードによる評価の流れ
    eval({"let": {k: v1}, "": x}, {k: v2})
  = eval(x, {k: eval(v1, {k: v2})})

- `eval`の第2引数が環境を表すとする。
- 環境に導入される変数`k`の値としては、この`let`マクロの外側の環境`{k: v2}`のもとでの評価値`eval(v1, {k: v2})`を用いる。
- 外側の環境の同名の変数は隠蔽される。
- この更新された新しい環境のもとで`""`キーの値`x`を評価し、その結果がこの`let`マクロ全体の評価結果となる。
- `""`キーの値の中に含まれるstringが表す変数名は、この`let`マクロによって導入された環境の値を参照する。
- 環境にない文字列を参照すると`null`へと評価される。

{ // 環境: {}
  "let": {
    "x": 1,
    "y": 2,
    "z": "x" // null
  },
  "": { // 環境: {"x": 1, "y": 2, "z": null}
    "let": {
      "x": "y", // 2
      "y": { // 環境: {"x": 1, "y": 2, "z": null}
        "let": {
          "y": "x" // 1
        },
        "": [ // 環境: {"x": 1, "y": 1, "z": null}
          "x", // 1
          "y", // 1
          "z"  // null
        ]
      }
    },
    "": [ // 環境: {"x": 2, "y": [1, 1, null], "z": null}
      "x", // 2
      "y", // [1, 1, null]
      "z"  // null
    ]
  }
} // [2, [1, 1, null], null]

### `let`マクロによる関数定義・マクロ定義の導入
- `"let"`キーの値がarrayのとき、array中の各要素を関数定義objectまたはマクロ定義objectとして解釈して環境に導入した上で、`""`キーの値を評価する。
- 関数定義object・マクロ定義objectについては後述。
- array中の関数定義objectでもマクロ定義objectでもない値は無視される。
- 関数定義objectの`"function"`キーおよびマクロ定義objectの`"macro"`キーの値はobjectでなくてはならず、そうでない定義は無視される。
- `let`マクロによって導入される関数定義・マクロ定義の名前(正確には後述するシグネチャ)が環境中のものと競合するとき、既存の定義は隠蔽される。
- 名前の検索の際に用いられる名前空間は関数定義とマクロ定義とで共有される。
- `"let"`キーの値がobjectでもarrayでもないとき、`"let"`キーの値は無視してそのまま`""`キーの値を評価する。

{
  "let": [
    { // 関数incrementを環境に登録
      "function": {"increment": null},
      "": {"+": ["increment", 1]}
    },
    { // マクロtwiceを環境に登録
      "macro": {"twice": null},
      "": ["twice", "twice"]
    }
  ],
  "": {"twice": {"increment": 1}}
}

### 関数定義object
`"function"`と`""`をキーにもつobject。
- 下の例は、引数に`1`を足す`increment`関数の定義と、`increment`関数への実引数として`2`を渡した呼び出しである。

{
  "let": [
    { // 関数定義
      "function": {"increment": null},
      "": {"+": ["increment", 1]}
    }  
  ],
  "": { // 関数呼び出し
    "increment": 2
  } // 3
}

#### 関数定義
- 関数定義の`"function"`キーの値はobjectである必要があり、このobjectのキーが関数のシグネチャとなる。
- キーのみが意味をもち、対応する値の方は無視される。
- TODO: この値の活用方法を考える
- docstringとか？型アノテーションとか？
- 複数のキーをシグネチャにもつ関数も定義することができる。
- 関数定義の`""`キーの値の中では、シグネチャのキー(上の例では`increment`)が変数名として参照でき、この変数に関数呼び出し時の実引数が束縛される。
- 関数定義の`""`キーの値の中では、シグネチャのキー以外の自由な変数名は、関数定義時の環境における値を参照する。
- 要するにレキシカルスコープということ。
- 関数呼び出し時の環境における値は、実引数に含めない限り用いることはできない。
- もちろん、中で`let`マクロによって導入される束縛変数は、外の環境ではなくその場で束縛した値を参照する。

#### 関数呼び出し
- 関数呼び出しobjectは、環境中に登録されている関数定義のシグネチャと一致するキーをもつobjectである。
- シグネチャ中のキーが集合として一致する必要がある。
- 関数呼び出しobjectは次の順序で評価される：
1. 実引数を呼び出し時の環境において評価する。
2. 関数定義時の環境にシグネチャキーを変数名として追加し、その値として1.での実引数の評価結果を用いる。
3. 更新された関数定義時の環境において、関数定義の`""`キーの値を評価する。
- 変数の環境は定義時のものを用いるが、関数定義・マクロ定義の環境は呼び出し時のものを用いる。
- したがって、再帰呼び出しも可能。

  // 疑似コードによる評価の流れ
    eval({
      "let": [
        {"function": {f: null}, "": body}
      ],
      "": {
        "let": {k: v2},
        "": {f: arg}
      }
    }, {k: v1})
  = eval({
      "let": {k: v2},
      "": {f: arg}
    }, {k: v1} with (f, body, {k: v1})) // 関数定義時の環境を記憶(レキシカルスコープ)
  = eval({f: arg}, {k: v2} with (f, body, {k: v1}))
  = eval({
      "let": {
        f: eval(arg, {k: v2} with (f, body, {k: v1})) // argは呼び出されたときの環境で評価
      },
      "": body
    }, {k: v1} with (f, body, {k: v1})) // bodyは定義されたときの環境で評価

### マクロ定義object
`"macro"`と`""`をキーにもつobject。
- 下の例は、`"twice"`キーの値を2つもつarrayへと展開するマクロ定義と、そのマクロを用いた`1`を2つもつarrayの構成を表している。
- シンプルな例にしようとするとつまらない例になってしまうがやむを得ない。

{
  "let": [
    { // マクロ定義
      "macro": {"twice": null},
      "": ["twice", "twice"]
    }
  ],
  "": { // マクロ展開
    "twice": 1
  } // [1, 1]
}

#### マクロ定義
- マクロ定義の`"macro"`キーの値はobjectである必要があり、このobjectのキーがマクロのシグネチャとなる。
- キーのみが意味を持ち、対応する値の方は無視される。
- マクロ定義の`""`キーの値の中では、シグネチャのキーが変数名として参照でき、この変数の位置にマクロに引き渡された値が埋め込まれる。
- マクロ定義の`""`キーの値の中では、シグネチャのキー以外の自由な変数名は、マクロ定義時の環境における値を参照する。
- もちろん、中で`let`マクロによって導入される束縛変数は、外の環境ではなくその場で束縛した値を参照する。

#### マクロ展開
- マクロ展開objectは、環境中に登録されているマクロ定義のシグネチャと一致するキーをもつobjectである。
- マクロ展開objectは次の順序で評価される：
1. マクロ展開の引数の値は評価せずにJSONの構造を保ったまま保持する。
- 後述の`quote`マクロの挙動。
2. マクロ定義時の環境にシグネチャキーを変数名として追加し、その値として1.で保持したマクロ引数のJSONを用いる。
3. 更新されたマクロ定義時の環境において、マクロ定義の`""`キーの値を評価する。
- 変数の環境は定義時のものを用いるが、関数定義・マクロ定義の環境は呼び出し時のものを用いる。

  // 疑似コードによる評価の流れ
    eval({
      "let": [
        {"macro": {m: null}, "": body}
      ],
      "": {
        "let": {k: v2},
        "": {m: arg}
      }
    }, {k: v1})
  = eval({
      "let": {k: v2},
      "": {m: arg}
    }, {k: v1} with (m, body, {k: v1})) // マクロ定義時の環境を記憶
  = eval({m: arg}, {k: v2} with (m, body, {k: v1}))
  = eval({
    "let": {
      m: eval({"quote": arg}, {k: v2} with (m, body, {k: v1}))
    },
    "": body
  }, {k: v1} with (m, body, {k: v1}))

- 要するに、関数呼び出しの引数を`quote`で囲んだだけの仕様。

## `if`マクロ
`"if"`, `"then"`, `"else"`の3つをキーにもつobject。

{
  "if": ".",
  "then": 1,
  "else": 0
} // 0

- まず`"if"`キーの値のみを評価し、その値が`false`, `0` (`-0`), `NaN`, 空文字列, `null`のとき**偽**、それ以外のときに**真**とする。
- つまり、JavaScriptにおける真偽値の評価と同様
- `"if"`キーの値の評価結果が**真**のとき、`"then"`キーの値のみを評価し、その結果を`if`マクロ全体の評価結果とする。
- `"if"`キーの値の評価結果が**偽**のとき、`"else"`キーの値のみを評価し、その結果を`if`マクロ全体の評価結果とする。

## `quote`マクロ
`"quote"`のみをキーにもつobject。

{
  "quote": {"if": null, "then": 1, "else": "x"}
}

- `quote`マクロは引数のJSONの構造をそのままの値として扱えるようにする。
- 引数がobjectの場合、通常であれば関数呼び出しやマクロ展開として評価されてしまうようなシグネチャであっても、辞書として扱えるようにする。
- 引数がobjectやarrayの場合、その内側のobjectやarrayの構造も保存する。
- 引数がstringの場合、変数参照ではなく先頭に`.`を付加したstringとして解釈される。
- それ以外のプリミティブの場合は元の意味と同じである。

{
  "let": {
    "q": {
      "quote": {"if": null, "then": "x", "else": 0}
    }
  },
  "": ["q.if", "q.then", "q.else"] // [null, "x", 0]
}

## その他の組み込みマクロ
現在のところは未定だが、今後もう少し追加する可能性はある。
特に`quote`の逆操作として`eval`マクロがあってもよい気はするが、マクロ処理の仕様そのものをもう少し煮詰めたあとで考えたい。

## 組み込み関数
- デフォルトで提供される関数。
- まだ処理系を実装できていないので、どの程度潤沢に組み込みを提供すべきなのかは、この言語をもう少し使ってみてから判断したい。
- 組み込み関数の候補:
- 四則演算: `+`, `-`, `*`, `/`
- 比較演算: `<`, `>`, `<=`, `>=`, `==`, `!=`
- 論理演算: `&&`, `||`, `!`
- プロパティアクセス: `length`, `at`
- 入出力: `read`, `write`, `print`
- 文字列処理, iterable処理, etc.
- 元がJSONなので、JavaScriptにあるようなメソッドが使えるとよさそう。

# 処理系の実装
- 現在のところは仕様の調整に手間取って実装できていませんが、これから実装して少し遊んでみたいと思っています。
- せっかくマクロを導入しているので、マクロの仕様調整も兼ねて、マクロの表現力を確かめたいところ。
- Lispの発想がもとにあるので、せっかくなのでmeta-circular evaluator[^mce]をJapan言語で実装したりしてみたい。
- KMCにはesolang[^esolang]好きが一定数いるので、そういった人々にも遊んでもらえるかもしれない。
- esolang好きからすると平凡で物足りないかもしれませんが。
- 上記の言語仕様の説明では、任意のJSONをJapan言語としても一応評価できるように、通常ならコンパイルエラーとでもするべきところをとりあえず`null`を返したり無視したりしているので、そういったところで処理系が警告を出すなり例外を出すなりするようなオプションは提供するべきでしょう。
- TODO: 処理系を実装したらここへリンクする。

# まとめ
- ちょっとした思いつきでJSONのS式に対するLispに相当するような言語Japanを設計してみました。かなりシンプルになっているとは思うのですが、ちゃんと仕様を書こうと思うと大変ですね。記事というよりドキュメントになってしまったけれど、考えを整理したり参照しながら処理系を実装するにはよいかもしれません。
- 正直、マクロ周りの仕様はまだ不十分だと思います。とりあえずシンプルな方へ倒して設計しましたが、使いやすくするためにはもう少し修正が必要なはずです。
- TODO: 健全なマクロにするためには仕様をどのように変更すればよいかを考える。

[^japan]: 知人に名前をつけてもらいました。プログラミング言語としてのJSONというニュアンスが入っていて、略語としても面白いです。
[^sexp]: すなわち、プログラム中で扱われるデータ構造であるS式がプログラムのコードのデータ構造としても採用され一致しているところがえらいということ。これによって、マクロの威力が存分に発揮される。
[^well-defined]: 本来ならwell-definedにならないようなところで無理やり値を定めているだけなので、ちょっと強弁かもしれません。
[^mce]: ざっくり言うと自分自身の言語で実装したインタプリタのこと。Japan言語はソースコードがJSONなので、Japan言語の中でコードをデータとして直接計算できる。Lispでの話は[SICP(計算機プログラムの構造と解釈)](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-26.html)を参照。
[^esolang]: 難解プログラミング言語(Esoteric programming language)のこと。Brainf\*\*kなどが有名か。KMC内では一時期Pietが流行っていました。[esolangコードゴルフ大会](https://blog.kmc.gr.jp/entry/2019/04/08/180000)が開かれたりもしています。