オレオレ評価器 Evaluator を作って、プログラミング言語の仕組みを理解をしよう！（おおげさ）

何を思いついたのか、突然、評価器 Evaluator を作ってみているわけです。評価器を作ってみたいというひと向けの記事になりますので、それほどニーズのある記事ではないと思っています。ですので、内容に関しては割り引いて読んでいただきましたら幸いです。

前回までの話は、こちらからご確認ください。今回は、その続きになります。

ざっとおさらいすると、変数の無いオレオレ言語を作りたくて、挑戦してみるが挫折を繰り返し、ある日、評価器 Evaluator から作ればいいんじゃ無いかと思い立ち作り始めたという話。四則演算、制御文 if for、宣言、関数、変数の代わりとなるストリームまでを実装して、階乗、フィボナッチ数、FizzBuzzなどを動かしてみた。

で、今回はどんな話？（概要）

前回作った評価器 MemeEvaluator に今回は、制御文の拡張 return, break, continue の機能を追加実装して、その動作確認に、ネイピア数やら、円周率やらを計算してみるという。そんな話。

1. 関数の return を実装する

では、待望の return を実装します。（特に待っていないとは思うけど。しばらくぶりになりました。）

return を実装すると関数内のコードがキレイになります。if 文で分岐したり、インデントのネストが深くなるのを防ぐコードが書けるようになります。

return の実装は、なかなか綺麗な実装が難しくて（思いつかず）、試行錯誤のすえ、結局は泥臭く「グローバル変数g_statに状態フラグを立てる」という、、、まぁ、ちょっとプログラマ的には屈辱的なコードが一番簡潔になるという、、、なんだか納得のし難い実装に落ち着いております。

//  ["return:", bool, val ]
if ( Array.isArray( _ary ) && _ary.length == 3 && _ary[ 0 ] == 'return:' ) {
    if ( eval_array( _ary[1] ) == '-true' ) {
        g_rtn = eval_array( _ary[2] )
        g_stat = '#return'
        return g_rtn
    }
    return '#none' // 暫定対応中 todo Valueではなく Objectにして返すべき
}

で、関数呼び出しから帰ってきたところで回収

// return 回収
if ( g_stat == '#return' ) {
    g_stat = ''
    rtn.push( g_rtn )
    g_rtn = ''
}

とまぁ、泥臭く実装しました。

で、動作の確認は、前回も作った階乗 factorial を return 使って書き直してみます。

脳内パース前のオレオレ言語の構文 return 文は、必ず条件文 if とペアにすることにしました。
理由は、これまでのプログラミングの経験から、条件の無いreturnの方が頻度が少ないとの判断からです。無条件に return したい場合は、return 'rtn-value' if -true って書けばいいかなって。

return のみならず break, continue も同様な構文にしました。（脳内パースの話なので、特に気にせず先に進みましょう。）

return <value> if <bool>
↓
["return:", <bool>, <value> ]


break <value> if <bool>
↓
["break:", <bool>, <value> ]


continue <value> if <bool>
↓
["continue:", <bool>, <value> ]

例によって、脳内パース前のオレオレ言語のコードがこちら。

factorial : {
    n : arg
    return 1 if n <= 1
    n * factorial.( n - 1 )
}
for: 1 to 10 >>
    /co <- factorial.( it ).last
:for

短いので、特に質問は無いかと思っています。で、例によって、このコードを脳内でJSONにパースして実行します。
それでは、出来上がった MemeEvaluator の動作確認をしてみましょう。

See the Pen MemeEvaluator L6 - 1 by yamazaki.3104 (@yamazaki3104) on CodePen.

動いた？

階乗 factorial が動いたら、同様にフィボナッチ数の return 版も確認してみます。
もともと短い関数なので、return の威力は発揮されていない気もしますが、短いコードであっても、さらに短く見やすくなるのは、return の凄さだとも思います。

# フィボナッチ数の関数＆return版

fibonacci : {
    n : arg
    return n if n <= 1
    fibonacci.( n - 2 ) + fibonacci.( n - 1 )
}
for: 1 to 10 >>
    /co <- fibonacci.( it ).last
:for

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

See the Pen MemeEvaluator level 6 - 2 by yamazaki.3104 (@yamazaki3104) on CodePen.

動いているかな？　確認できたら次に行ってみよう。

2. break, continue も続いて実装

このままの勢いで、繰り返し for: 文用の分岐 break と continue も一緒に実装してしまいます。なぜかというと、return も break も continue も似たような仕掛けで実装できるからです。

// ["break:", bool, val ]
if ( Array.isArray( _ary ) && _ary.length == 3 && _ary[ 0 ] == 'break:' ) {
    if ( eval_array( _ary[1] ) == '-true' ) {
        const r = eval_array( _ary[2] )
        g_stat = '#break'
        return r
    }
    return '#none' // 暫定対応中 todo Valueではなく Objectにして返すべき
}

//  ["continue:", bool, val ]
if ( Array.isArray( _ary ) && _ary.length == 3 && _ary[ 0 ] == 'continue:' ) {
    if ( eval_array( _ary[1] ) == '-true' ) {
        const r = eval_array( _ary[2] )
        g_stat = '#continue'
        return r
    }
    return '#none' // 暫定対応中 todo Valueではなく Objectにして返すべき
}

「暫定対応中」のコメントがまぶしいですが、return, break, continue の条件がヒットしなかった場合、処理を継続するのですが、その時に、そのことを計算結果として残すかどうか、微妙な判断を迫られていまして、「まぁ、残さない方が使いやすそうだぞ」ということで、こういう変な暫定対応になってます。暫定対応な理由は、真面目に実装するのが面倒だったらか、、、、と、後回しにしても面倒くささは３倍になって帰ってくるだけなんですけどね。🤗

発生した break, continue 回収しているコードがこちら。for 文の中ですね。

for ( const _it of clone ) {
    const r = eval_array( _it )

    if ( r == '#none' ) continue

    rtn.push( r ) // for 評価

    // break 回収
    if ( g_stat == '#break' ) {
        g_stat = ''

        pop_scope()
        return rtn  // for: を抜ける
    }

    // continue
    if ( g_stat == '#continue' ) {
        // 回収せずに for loop を続ける
        break
    }

    // return
    if ( g_stat == '#return' ) {
        // 回収せずに for loop を抜ける
        pop_scope()
        return rtn
    }
}
// continue 回収
if ( g_stat == '#continue' ) {
    g_stat = ''

    continue    // for: を繰り返す
}

では、break の動作確認から。

# break の動作確認

/co <- for: 1 to 30 >>
    it * 111
    break 777 if it >= 3
:for

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

See the Pen MemeEvaluator level 7 - 1 by yamazaki.3104 (@yamazaki3104) on CodePen.

777 が配列の最後に追加されて戻ってくるのがオレオレ言語の仕様通りです。
さて、break の動作が確認できたら、このまま続いて continue の動作確認に行きます。
テストコードは FizzBuzz にしました。 continue を使うとスッキリ書けますね。

/co <- for: 1 to 30 >>
    continue 'FizzBuzz' if it % 15 == 0
    continue 'Buzz'     if it %  5 == 0
    continue 'Fizz'     if it %  3 == 0
    it
:for

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

See the Pen MemeEvaluator level 7-2 by yamazaki.3104 (@yamazaki3104) on CodePen.

では、もっと実用的なコードでこれらの制御文の威力を試してみましょう。

まずは、素数判定から。参考にさせていただいたC++のコードがこちら（素数判定）
になります。

public static bool IsPrime(int num)
{
    if      ( num <  2     ) return false;
    else if ( num == 2     ) return true;   // 素数
    else if ( num % 2 == 0 ) return false;

    double sqrtNum = Math.Sqrt(num);
    for ( int i = 3; i <= sqrtNum; i += 2 ) {
        if ( num % i == 0 )
            return false;   // 素数ではない
    }
    return true;    // 素数
}

で、このコードをまずは試しに、if と break を使って実装してみます。ループの終了条件に break を使っています。
平方根 Math.Sqrt() はまだ未実装（っていうか実数はまだ未確認な状態）なので、二乗** 2を使った都度判定に変えています。（平方根と、都度二乗するのは、どちらが早いかはわからないです。興味があるひとは自力で計測してみると理解が深まることでしょう。多分、大きな数になるとループが多くなるので差が出るよね）

is_prime : {
    n : arg
    if: n < 2 ?? -false                 # 素数ではない
    !!
        if: n == 2 ?? -true             # 素数
        !!
            if: n % 2 == 0 ?? -false    # 素数ではない
            !!
                for: 3 to n step 2 >>
                    break -true  if n < it ** 2     # 素数
                    break -false if n % it == 0     # 素数ではない
                :for
            :if
        :if
    :if
}
for: 1 to 100 >>
    if: is_prime.( it ).last ?? /co <- it !! '' :if
:for

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

See the Pen MemeEvaluator level 7-3 by yamazaki.3104 (@yamazaki3104) on CodePen.

なんといいますか、「書いてはいけないお手本」のような、見事な「インデント」になりました。
このコードは反面教師ですので、お気をつけください。
インデントが高い山の形になるコードはメンテしにくく、バグりやすいので、プロなプログラマの方々は書いてはいけません。
このようなインデントの山を見かけたら、リファクタリングしましょう。

return を使うとこのようになります。（もともとのサンプルコードは return で書かれていました。）
だいぶスッキリと平らなインデントになりましたね。return の威力が発揮されたでしょうか。

is_prime : {
    n : arg
    return -false if n <  2             # 素数ではない
    return -true  if n == 2             # 素数
    return -false if n % 2 == 0         # 素数ではない

    for: 3 to n step 2 >>
        return -true  if n < it ** 2    # 素数
        return -false if n % it == 0    # 素数ではない
    :for
}
for: 1 to 100 >>
    if: is_prime.( it ).last ?? /co <- it !! '' :if
:for

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

See the Pen MemeEvaluator level 7-4 by yamazaki.3104 (@yamazaki3104) on CodePen.

素数判定できましたね。いやぁ、ここまで来ると、どんなアルゴリズムでも実装できそうな気分になってくるから怖いです。この勢いで、「エラトステネスの篩」に行っても面白いですが、

一度、冷静になりましょう。

ここまでは、整数の範囲での実装と評価でした。次は、実数にチャレンジします。

それでは、return 版 factorial を使って、ネイピア数 e を求めちゃいましょう。

3. ネイピア数 e を計算してみる

いやぁ、いよいよ実数ですよ「実数」。浮動小数点演算です。きゃー。

しかも、数学と言えば「テイラー展開」です（そんなことはありません😊）。
プログラミングでご飯が食べられるような大人になった今でも、きちんと理解できているとは言い難い謎なアルゴリズム「テイラー展開」ですが、なんと、こんな簡単なアルゴリズム（四則演算の繰り返し）で、

ネイピア数 e = 2.71828182846

が求められるというのですから、驚き以外の何者でもありません！数学すげー！！テイラー展開すげー！！

では、その実装をみてみましょう。前半は factorial です。そのままです。後半がネイピア数のアルゴリズム。本当は無限回繰り返す必要があるそうですが、PCの精度であれば15回くらいで十分とのことです（その理由は各自で調べてみてください（おい））。

# テイラー展開によってネイピア数 e を求める。

factorial : {
    n : arg
    return 1 if n <= 1
    n * factorial.( n - 1 )
}

e : [ 1 ]
for: 1 to 15 >>
    e <- e + 1 / factorial.( it )
:for
/co <- e.last

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

See the Pen MemeEvaluator level 7-5 by yamazaki.3104 (@yamazaki3104) on CodePen.

ググるとネイピア数は

e = 2.71828182846

って出るようですが、iPhone の電卓アプリでは

e = 2.718281828459045

と表示されます。なので、今回コードの15回繰り返した答え「2.718281828458995」がどのくらいの精度になったかわかるでしょう。

すごいですね。

で、MemeEvaluator の実数の対応ですが、実は、四則演算に割り算/を追加したくらいで、特にあらたに「実数クラス」やら「オブジェクト」やらは追加していないです。（タイプセーフな言語を目指すなら、ここでしっかり「実数タイプ」を実装しておいたほうがよいとは思いますが）
ここでは、Javascript の恩恵におんぶにだっこで行きます。いやぁ、らくちん。

4. 平方根 sqrt を計算してみる

ネイピア数 e で味をしめたので、次は平方根 sqrt に行きます。

こちらは、有名なNewton法で。こっちの方が数学的には歴史があるのでしょうか、よくわからないです。（バカなの？？否定はしません。否定しろよ。）

何がすごいって、四則演算を繰り返すだけで平方根が計算できるってことと、20回も繰り返さなくても、PCで使えるくらいの精度が出せるってこと。びっくりだよ。Newton法すげー！！

# Newton法による平方根の計算

sqrt : {
    x : [ arg / 2 ]
    for: 1 to 20 >>
        n : ( x + arg / x ) / 2
        break n if x == n
        x <- n
    :for.last
}
for: 2 to 10 >>
    /co <- sqrt.( it ).last
:for

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

See the Pen MemeEvaluator level 7-6 by yamazaki.3104 (@yamazaki3104) on CodePen.

Newton法すごいよね。

ちなみに、:for の後ろに .last が付いているのは、for は配列を返す仕様にしたので配列の最後の値を取り出しています。

5. 円周率（フーリエ級数）を計算してみる

で、平方根が計算できるようになると、円周率が計算できるようになります。「フーリエ級数」で。しかも短い！　これまたびっくりですよ。

# フーリエ級数

f : [ 0 ]
for: 1 to 1000 >>
    f <- f + ( 1 / it * it )
:for
/co <- sqrt.( f * 6 )

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

See the Pen MemeEvaluator level 7-7 by yamazaki.3104 (@yamazaki3104) on CodePen.

ググると、

円周率 π＝3.14159265359

フーリエ級数で1000回繰り返しても、

3.1406380562059946

と、小数点以下第二位までしか計算できていないですね。なかなか手強いです。
でも、逆に考えると、1000回程度の四則演算で、円周率が計算できるなんて、すごいですよね。

でも、人類の挑戦はまだまだこの程度では終わらないようです。

ガウス＝ルジャンドルのアルゴリズム

# ガウス＝ルジャンドルのアルゴリズム

a : [ 1 ]
b : [ 1 / sqrt.( 2 ).last ]
t : [ 1 / 4 ]
p : [ 1 ]

for: 1 to 3 >>
    A : a.last
    B : b.last
    a <- ( A + B ) / 2
    b <- sqrt.( A * B ).last
    t <- t - p * ( A - a ) ** 2
    p <- 2 * p
    /co <- ( a + b ) ** 2 / ( 4 * t )
:for

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

See the Pen MemeEvaluator level 7 - 8 by yamazaki.3104 (@yamazaki3104) on CodePen.

π きたー！

もう、ほんとすごいです。
このアルゴリズムをたった３回の繰り返すだけで、ここまでの精度を出すのですから、、、、もうね。

ぐうの音も出ないです。人類に完敗。人類に乾杯。

まとめ

return, break, continue を実装してみた結果、ネイピア数や平方根、円周率など手計算ではなかなか大変な計算ができるようになりました。プログラミング言語にひとつ近づけたのではないでしょうか。

今回はこのくらいにして、次は、例外をサポートしたら、パーサーを作りましょう。
ところで、例外のサンプルコードって、なに？？　そんなのある？？

おまけ

と、ここまで書いて、Javascript のべき乗演算子**で平方根が計算できることを知りました。ぁぅぁぅ。
べき乗演算子**はすでに実装したので、何もしなくても動くかも、、、と思って書いてみたコードがこちら👇

See the Pen MemeEvaluator level 7-9 by yamazaki.3104 (@yamazaki3104) on CodePen.

動くし、、、乙。