LoginSignup
16

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-04-03

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

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

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

めんどくさいParser(字句解析構文解析)は後回し

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

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

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

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

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

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

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

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

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

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

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

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

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

最初の実装がこちら。

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

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

const initialize_and_go = () =>         // 初期化とインタプリタの実行
{
    // 初期化
    g_co  = [ ]
    g_err = [ ]
...

この関数 initialize_and_go() を呼ぶと、初期化して、評価して、結果を表示します。ボタンのクリックイベントはここにつながっています。

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

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

評価器のなかでは

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

それが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にパースして入力する)


See the Pen
MemeEvaluator L1
by yamazaki.3104 (@yamazaki3104)
on CodePen.

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

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

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

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

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

実装はこのあたり

    // ['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 ... ] ]

実装はこのあたり

    // ['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というシンボルが参照できます。内容はループの値です。 実装はこんな👇

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

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

--- FizzBuzz

for: 1 to 100 >>
    /co <-
        ( it % 3 == 0
        ?? ( it % 5 == 0 ?? 'FizzBuzz' !! 'Fizz' )
        !! ( it % 5 == 0 ?? 'Buzz'     !! it     )
        )
:for

↓(オレオレ言語を脳内でJSONにパースして入力する)

3. 宣言 define を実装

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

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

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

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

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

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

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

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

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にパースして入力する)

4. 関数 function: を実装

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

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

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

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

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

こんな感じで登録。

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 )        --- 関数の呼び出し

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

    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 と、フィボナッチ数

--- 関数といえば階乗 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にパースして入力する)

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

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

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

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

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

いよいよ変数の代わりになる 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

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

    fib: [ ( 0 1 ) ]
    for: 1 to 30 >>
        a : fib.last
        /co <- a.1
        fib <- ( a.1  ( a.0 + a.1 ) )
    :for

↓(オレオレ言語を脳内でJSONにパースする)


まとめ

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

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

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

ではでは。

追記

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16