変数の無いオレオレ言語を作りたくて、オレオレ→Meme とか命名するくらい頭がわるいワシが評価器 Evaluator を実装してみた話

# プログラマなら誰しも「言語を作ってみたい」って思うよね

「[変数]の無いプログラミング言語のほうが、バグりにくく、生産的で、かつ、マルチスレッドにしやすい」という持論を証明するには、[変数]の無いプログラミング言語を自分で作るしかないよねー。なぜならば[変数]の無いプログラミング言語なんてみたことも聞いたこともないからー、と言語の作成を試みては挫折し、再び試みては挫折するをすでに複数回繰り返しているのだが、ある時、「あー、後ろから作らないから挫折するんじゃ？」と思ったのが、この記事を書こうと思ったきっかけ。

なので、理想とする言語が脳内にあるのだけど、どこから作ったらいいのか迷ってるひと向け（そんなひとは少ないとは思うぞ）

# めんどくさいParser（[字句解析]と[構文解析]）は後回し

一般的に、オレオレ言語は、妄想から始まると思うわけです。ある程度、構文を妄想して、パーサーをゴリゴリ作って、[構文木]がある程度できたら、さぁ、評価してみっか！オラ！オラ！オラ！！！、、、、ぐはぁ（吐血）ってな具合に。自分がそうでしたから。

コードを妄想して、[字句解析]器を作って、トークンにバラして、[構文解析]器を作って、[構文木]を作って、ってところまででかなりのエネルギー（ほぼ９割）を消費してしまうわけで、[構文木]ができはじめた頃にはもう、[評価器]をデバッグできる気力なんぞ使い果たしているわけです。

でもね、大事なのは[評価器]であって、[構文木]ができても評価できなければ、絵に描いた餅、オレオレ言語は名乗れないとも思うわけです。

で、再び気力が溜まるのを待つのもありではあるのだけど、やはり手戻りが大きいってのは時間がかかるし手段が間違っている気がしていたわけです。で、で、冒頭の話になる。
要するに、パーサーなんてあとで作ればいいやん。まずは[評価器]からだよね。と。

# 0. 脳内で[構文木]にパースする

[構文木]は、まぁ、がんばって自作しなくても、[JSON]で十分すぎるわけで、ありがたく使わせてもらうのが吉。

    123 + 456
    ↓
    ["+", "123", "456" ]

こんな感じ。さらに優先順位を [ ] であらわして、先頭はコマンド（命令）ってことにする。先頭以外はコマンドの引数ね。

    123 + 456 * 789
    ↓
    ["+", "123", ["*", "456", "789" ] ]


それで、プログラミング言語っぽく、コンソールへの出力命令'<-'も作って。文字列はまぁ、よく見る形であらわします。

    /co <- 'Hello'
    ↓
    ["<-", "/co", "'Hello'" ]

まぁ、界隈で有名な[S式]っぽく [JSON]で表記すれば、簡易な[構文木]はできちゃいます、ってことがここでは言いたい。[S式]すげー！！[JSON]もすげー！！！

[構文木]:https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E6%9C%A8

[構文解析]:https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90

[字句解析]:https://ja.wikipedia.org/wiki/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90

[評価器]:https://ja.wikipedia.org/wiki/Eval

[S式]:https://ja.wikipedia.org/wiki/S%E5%BC%8F

[JSON]:https://ja.wikipedia.org/wiki/JavaScript_Object_Notation

# 1. 最初の実装は四則演算から

最初の実装がこちら。

まず、入力（[JSON]）と出力(コンソール出力`/co`、エラー出力`/err`、戻り値の表示（主にデバッグ用途）)の機能を、HTMLタグというかテキストボックスを[Aceエディター]で無駄に豪華に作りまして、あいだに（親切に）再評価可能なボタンを作りました。
「こんなのが動くの？」「まじで？」と思った方は、テキストエディタの [JSON] を好きなように編集して、ボタンを押してみてください。エラー！ってなるから。よくできているでしょ。

[Aceエディター]:https://ace.c9.io/

そんな感じで、50行目くらいまで、HTMLとの格闘がありまして、そこからが[評価器]本体であります。

```js
const initialize_and_go = () =>         // 初期化とインタプリタの実行
{
    // 初期化
    g_co  = [ ]
    g_err = [ ]
...
```
この[関数] initialize_and_go() を呼ぶと、初期化して、評価して、結果を表示します。ボタンのクリックイベントはここにつながっています。

[評価器]本体はこれ→ eval_array() もうちょっと違う名前がよかったかも🤔。

```js
rtn_code = eval_array( JSON.parse( in_edt.getValue() ) )
```

[評価器]のなかでは

 + 配列かどうかのチェックをして、配列でなければオブジェクトの種類（ここでは、数値か文字列かシンボルか）を確認し値に変換して返す
 + 配列ならば、先頭のコマンドで分岐して、コマンドごとに各々実行する
 + コマンド以外の場合は１つずつ評価（再帰）する

それが140行目付近まで。100行ほど。

その実装がこちら👇（こんな感じのオレオレ言語を脳内でパースして入力します。）

```
    /co <- 12345
    /co <- 'MeMe'
    /co <- 777 + 222
    /co <- 5 - 3
    /co <- 123 * 456
    /co <- ( 5 - 3 ) * 4

    /co <- 2 <= 1
    /co <- 56000 + 88 == 123 * 456
    /co <- 'Me' + 'Me' == 'MeMe'
```
↓（オレオレ言語を脳内で[JSON]にパースして入力する）
<p class="codepen" data-height="500" data-theme-id="0" data-default-tab="result" data-user="yamazaki3104" data-slug-hash="PgoGJo" style="height: 500px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="MemeEvaluator L1">
  <span>See the Pen <a href="https://codepen.io/yamazaki3104/pen/PgoGJo/">
  MemeEvaluator L1</a> by yamazaki.3104 (<a href="https://codepen.io/yamazaki3104">@yamazaki3104</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>

# 2. 制御文 if, for を実装して [FizzBuzz] を動かす

さて、四則演算やコンソール出力が確認できたら、次は制御文です。
具体的には、条件文の if 文と、繰り返しの for 文。
脳内パース前のコードはスルーで。[JSON]の[構文木]の方は

 + ["if:", [ bool ], [ then ], [ else ] ]
 + ["for:", "from", "to", "step", [ ... ] ]

としました。
if文の脳内パース

    ( 条件式 ?? ... !! ... )
    または
    if: 条件式 ?? ... !! ... :if 
    ↓
    ["if:", [ 条件式 ], [ ... ], [ ... ] ]

実装はこのあたり

```JS
    // ['if:', bool, then, else  ]
    if ( _ary.length == 4 && tokn == 'if:' ) {
        if ( eval_array( _ary[1] ) == '-true' ) return eval_array( _ary[2] )   // then
        else                                    return eval_array( _ary[3] )   // else
    }

```

for文の脳内パース

    ( 0 to 10 >> ... )
    または
    for: 0 to 10 >> ... :for
    ↓
    ["for:", "0", "10", "1", [ it ... ] ]

実装はこのあたり

```JS
    // ['for:', from, to, step, do ]
    if ( _ary.length == 5 && tokn == 'for:' ) {
        let rtn = []
        const from = eval_array( _ary[1] )
        const to   = eval_array( _ary[2] )
        const step = eval_array( _ary[3] )
        for ( let i = from ; i < to ; i += step ) {
            g_it = i
            rtn.push( eval_array( _ary[4] ) ) // 評価
        }
        return rtn
    }
```

そうそう、オレオレ言語の for文の中では、`it`というシンボルが参照できます。内容はループの値です。 実装はこんな👇

```JS
        if ( _ary == 'it' ) return g_it    // it -> value
```

なんと、これだけで、「[FizzBuzz] が実行できる」というのですから、びっくりだよね（念の為、同意を求めてみる）。
詳しくは、実装をご覧ください。

[FizzBuzz]:https://ja.wikipedia.org/wiki/Fizz_Buzz

```
--- FizzBuzz

for: 1 to 100 >>
    /co <-
        ( it % 3 == 0
        ?? ( it % 5 == 0 ?? 'FizzBuzz' !! 'Fizz' )
        !! ( it % 5 == 0 ?? 'Buzz'     !! it     )
        )
:for
```
↓（オレオレ言語を脳内で[JSON]にパースして入力する）
<p class="codepen" data-height="500" data-theme-id="0" data-default-tab="result" data-user="yamazaki3104" data-slug-hash="gyOwgV" style="height: 500px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="MemeEvaluator L2">

# 3. 宣言 define を実装

さて、どんどん行きます。[FizzBuzz] が動いて調子に乗ってきたので、次は、宣言に行きましょう。
脳内パースの方はこういう表記にしました。宣言にはコロン':'を使います。

    a : 123
    b : 456
    /co <- a + b
    ↓
    [ [":", "a", "123" ],
      [":", "b", "456" ],
      ["<-", "/co", ["+", "a", "b" ] ]
    ]

で、もちろん、「[変数]」ではなく、「[定数]」の宣言な訳です（まぁ、ここでは、どーでもいいことですね）。

このあたりから「環境」という言葉が出てきます。宣言したモノを覚えておくためのエリアです。ここでも先人の智慧、配列というか連想配列を実装に使わせていただいて。こんな感じ👇

```JS
const push_scope = () =>        // あたらしい作業エリアを先頭に追加
{
    symbol_scope.unshift( [] )
}

const pop_scope = () =>         // 先頭の作業エリアを削除
{
    symbol_scope.shift()
}
```
なんで、わざわざ unshift()/shift() するのかというと、ローカルな作業エリア、いわゆる[スコープ]を作っています。宣言の効力が発揮される範囲のことですね。グローバルスコープだけでもプログラムは書けますが、ローカルスコープがあるといろいろ便利でしょ。ってか、大きなコードを書くには必須ですよね。だって、そんなにたくさんのことを一度に覚えていられないではないですか。

そして、確保したエリアに値を登録するだけ。

[スコープ]:https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%97

```JS
const set_symbol = ( _smbl, _val ) =>
{
    const ss = symbol_scope[ 0 ]
    if ( _smbl in ss ) return put_err( 'OVERLOAD DEFINE: ' + _smbl + ': ' + _val ) // 多重定義エラー
    else               return ss[ _smbl ] = _val
}
```

さて、固い話はこのくらいにして、実際の動きを見てみましょう。[FizzBuzz]の変形版です。

```
定数を宣言できるだけで、できることの幅がグッと広がる

--- FizzBuzz 定数宣言を使う版

    for: 1 to 100 >>
        a : ( it % 3 == 0 ?? 'Fizz' !! '' ) + ( it % 5 == 0 ?? 'Buzz' !! '' )
        /co <- ( a == '' ?? it !! a )
    :for
```
↓（オレオレ言語を脳内で[JSON]にパースして入力する）
<p class="codepen" data-height="500" data-theme-id="0" data-default-tab="result" data-user="yamazaki3104" data-slug-hash="gyOMNE" style="height: 500px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="MemeEvaluator L3">

# 4. [関数] function: を実装

さて、[定数]が宣言できたら、勢いで、[関数]宣言も実装しちゃいましょう。
脳内パースの方はこういう表記にしました。[関数]には { } を使います。

    f : { arg ... }
    または
    f : function: arg ... :function
    ↓
    [":", "f", ["function:", ... ] ]

[関数]といっても、[定数]と同じように、連想配列に入れておくだけなので簡単なんですが。入れるのは値ではなく、[関数]なのでここでは評価する前の [JSON] をそのまま登録しちゃいます。Javascriptって便利ですよね。
[定数]と同じく、[スコープ]を作って。ってか、拡張すればおっけー。

```JS
const push_scope = () =>        // あたらしい作業エリアを先頭に追加
{
    symbol_scope.unshift( [] )
    func_scope.unshift( [] )
}

const pop_scope = () =>         // 先頭の作業エリアを削除
{
    symbol_scope.shift()
    func_scope.shift()
}
```

こんな感じで登録。

```JS
const set_function = ( _func_ary ) =>   // [関数]の登録
{
    const fs = func_scope[ 0 ]
    const func_no = '#func' + Object.keys(fs).length
    fs[ func_no ] = _func_ary

    return func_no
}
```
ちなみに、オレオレ言語の[関数]呼び出しは、こんなです。

    func : { arg ... }  --- 関数宣言
    func.( arg )        --- 関数の呼び出し

ドット'.'が入っているけど、このほうが評価しやすいって、独自判断（経験則）です（ぉぃ）
実装はこのあたり。

```JS
    if ( typeof v1 == 'string' && v1.slice( 0, 5 ) == '#func' ) { // ['.', #func, arg ]
        push_scope()

        set_symbol( 'arg', eval_array( _ary[2] ) )      // 引数を評価して arg に載せる
        const rtn = eval_array( get_function( v1 ) )    // 関数呼び出し

        pop_scope()
        return rtn
    }
```
あ、引数は arg というシンボルで決め打ちで渡しています。
そうそう、ついでってなわけではないけど、宣言機能が実装されているので、for 文の`it`も、引数の`arg`もシンボルとして宣言されたように作り変え、あるべき姿に近づけます。

勢いで脱線すると、オレオレ言語では、引数も戻り値も配列になります（実装がラクなので）。で、関数の戻り値をそのまま四則演算する時は、ホントは返ってきた配列の最後の値を取ってきてから演算するように記述しないといけないのですが、ちょっとそれを毎度書いていたらキリがないので、四則演算の場合は勝手に最後の値を取ってくる仕様にしました。なので、四則演算ではない命令（ここではpush `<-` ）は、明示的に最後の値を取ってこないと配列のまま渡されます（その方が、使いやすいという判断です）。四則演算には`.last`が無いのに（付けてもいいけど）、push `<-` するときは`.last`を付けているのは、このような理由なんです（この👇書き方の話ね）。

```
    /co <- factorial.( 3 ).last
```
`.last`を取ると、戻り値の配列がそのまま表示されるようになります。気になる人は👇で実際に編集して（付けたり外したりして）、実行ボタンを押して、結果を確認してみるとよいと思います。

で、作った[評価器]で評価してみるのは、定番の階乗 factorial と、[フィボナッチ数]。

[フィボナッチ数]:https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

```
--- 関数といえば階乗 factorial ですよね

    factorial : {
        n : arg
        ( n <= 1
        ?? 1
        !! n * factorial.( n - 1 )
        )
    }
    /co <- factorial.( 3 ).last
    /co <- factorial.( 5 ).last


--- フィボナッチ数も関数で実装できます（再帰版）、めっちゃ遅いけど、、、

    fibonacci : {
        n : arg
        ( n <= 1
        ?? n
        !! fibonacci.( n - 2 ) + fibonacci.( n - 1 )
        )
    }
    for: 1 to 10 >>
        /co <- fibonacci.( it ).last
    :for
```
↓（オレオレ言語を脳内で[JSON]にパースして入力する）
<p class="codepen" data-height="500" data-theme-id="0" data-default-tab="result" data-user="yamazaki3104" data-slug-hash="aMrEaO" style="height: 265px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="MemeEvaluator L4">

# 5. [ストリーム] stream: を実装

さて、最後は、かなり息切れ感がありますが、[変数]、、、、じゃなくて[ストリーム]を実装します。
[ストリーム]といっても、ここでも、配列を使って実装するのですが。ここまで出来ればプログラミング言語と名乗れるのではないでしょうか（名乗れるといいなぁ、名乗れるんじゃないかな、多分、、、きっと、みんな優しいからさ）。
例によって、[ストリーム]の脳内パースはこんなです。[関数]とほぼほぼ一緒。

    s : [ ... ]
    または
    s : stream: ... :stream
    ↓
    [":", "s", ["stream:", [ ... ] ] ]

「変数なんで飾りです。[ストリーム]があれば、[変数]なんて無くてもコードが書けます！」って言いたい、、、けど、それはまた今度。
[ストリーム]があれば、フィボナッチ数も、再帰せずにすんなり高速に計算できます！

実装は、[関数]の時とほとんど同じなので、特に説明しませんけど（ってか、疲れた）、 `/co` と `/err` を[ストリーム]として作りなおします。やっと本来のあるべき姿になれたってことで。


[変数]:https://ja.wikipedia.org/wiki/%E5%A4%89%E6%95%B0_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)

[定数]:https://ja.wikipedia.org/wiki/%E5%AE%9A%E6%95%B0

[関数]:https://ja.wikipedia.org/wiki/%E9%96%A2%E6%95%B0

[ストリーム]:https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%83%AA%E3%83%BC%E3%83%A0_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)

```
いよいよ変数の代わりになる stream の実装が追加されてます。
stream といってもここでは配列 Array を使って簡略実装しているのですが。

--- フィボナッチ数列 fibonacci を再帰ではなくループで書く

    fib0: [ 0 ]
    fib1: [ 1 ]
    for: 1 to 30 >>
        a0 : fib0.last
        a1 : fib1.last
        fib0 <- a1
        fib1 <- a0 + a1
    :for
    /co <- fib1

--- １つのストリームに値をペアで入れていくスタイルのフィボナッチ数列

    fib: [ ( 0 1 ) ]
    for: 1 to 30 >>
        a : fib.last
        /co <- a.1
        fib <- ( a.1  ( a.0 + a.1 ) )
    :for
```
↓（オレオレ言語を脳内で[JSON]にパースする）
<p class="codepen" data-height="500" data-theme-id="0" data-default-tab="result" data-user="yamazaki3104" data-slug-hash="VNZeYg" style="height: 500px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="MemeEvaluator L5">
<script async src="https://static.codepen.io/assets/embed/ei.js"></script>

# まとめ

と、ここまで、かけ足できましたが、[JSON] や Javascript の力を借りると、短いコードで[評価器] Evaluator らしきものが書けると、言えるのではないでしょうか。

あと、足りていないのは、例外とか、return や break も欲しいかな。そのあたりまで動いたら、パーサーを作りましょう。

オレオレ言語の構築に興味がある方は、是非とも、コードをみてみてください。コードを見るには「HTML」のボタンを押すと見られます。みなさまのオレオレ言語生活の一助になれば幸いです。

ではでは。

# 追記
続きを書きました。ご興味がありましたらご覧くださいませー。
https://qiita.com/yamazaki3104/items/663aa2a7b97bc5f60a6e