Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@junjis0203

作って理解JavaScript：JOKE開発記その3 - 演算

Last updated at Posted at 2020-05-31

今回のスコープ

開発記その2で予告したように演算機能を実装します。具体的には

  • 算術演算
  • 代入演算子
  • インクリメント／デクリメント。ただし後置のみ1

これだけだと簡単にできてしまうので比較演算・論理演算も実装しようかなと思いましたが、短絡評価のためには条件分岐を実装しないといけないのでステップ4以降で作ることにしました。
というわけで今回のテストプログラムは以下の2つとなります。

step/step0003_01.js
// いわゆる算術演算。優先順位とか結合規則も確認
console.log(1 + 2);
console.log(-1 - 2 - 3);
console.log(1 + 2 * 3);
console.log((1 + 2) * 3);
console.log(1.5 / 2);
console.log(5 % 3);
step/step0003_02.js
// インクリメントと代入演算子
let a = 0;
console.log(a++);
console.log(a);

a += 2;
console.log(a);

ステップ3時点の（以下で説明していく）コードは以下にあります。
https://github.com/junjis0203/joke/tree/step0003

演算機能の仕様と実装

数値解析

ステップ2時点では数値リテラルをサポートしていなかったのでまずはそこからです。
整数だけでいいやと思うものの、JavaScriptでは5 / 2が2ではなく2.5になるので演算で出るものをリテラルで書けないのは駄目だろうと浮動小数点数もサポート…、というかよく思うとJavaScriptには浮動小数点数しかありませんでした。

仕様に沿って実装、と言いつついくつか手抜きしています。

  • 16進数表記等はサポートしない（単に当面使うつもりがないのでコード量を減らすため）
  • .5や12.のように小数点の前や後に数値がないものも未サポート（自分があまりそう書かないため）

指数表記は書いた後で「別に要らないか」と思いましたが、実装してしまったので残してあります(笑)
また、先にリンクした仕様だと「3inみたいなのは即エラーにして、3とinという2つのトークンにしてはいけない」と書かれていますが、ここについても今のところ「ちゃんと（見つけたら即刻）」エラーにはしていません。

算術演算の実装

バックトラックの導入

BNFの段階で演算子の優先順位は適切なものになっているので淡々と実装すればOK。
と思っていたらステップ2の代入（以下のBNF）を構文解析する際に

AssignmentExpression :
    ConditionalExpression
    LeftHandSideExpression = AssignmentExpression

手抜きしたつけが早速回ってきましたｗ

ステップ2のparser.js抜粋
function AssignmentExpression(scanner) {
    // currently, ConditionalExpression equals to LeftHandSideExpression
    // this code must be modified when support various operator
    let node = LeftHandSideExpression(scanner);

厄介（手抜きした理由）なのは途中にある「=」によりConditionalExpressionなのか、（ConditionalExpressionの一部である）LeftHandSideExpression なのかが変わる点です。
これに対応するためにバックトラックを実装しました。つまり、

  1. Scannerの状態を保存（カプセル化していますが実体は現在のポインタを返しているだけです）
  2. まずConditionalExpressionとして解析
  3. 「=」がなければOK
  4. 「=」があったらScannerの状態をリストアしてLeftHandSideExpressionとして解析

演算子の結合規則と再帰下降パーサ

足し算（と引き算）に対応するBNFは以下の通りです。

AdditiveExpression :
   AdditiveExpression + MultiplicativeExpression
   AdditiveExpression - MultiplicativeExpression

これを「素直に」関数で書くともちろん無限再帰になってしまい死にます。
というわけでループの形に書き換える必要があります。

parser.js抜粋
function AdditiveExpression(scanner) {
    let node = MultiplicativeExpression(scanner);
    while (checkCharToken(scanner.token, '+') || checkCharToken(scanner.token, '-')) {
        const operator = scanner.token.char;
        scanner.next();
        const right = MultiplicativeExpression(scanner);
        node = {
            type: Node.BINARY_OPERATOR,
            operator,
            left: node,
            right,
            srcInfo: node.srcInfo
        };
    }
    return node;
}

なお、

AdditiveExpression :
    MultiplicativeExpression + AdditiveExpression
    MultiplicativeExpression - AdditiveExpression

とすれば無限再帰にはならない！解決！とはなりません。
こうしてしまうと引き算が右結合になってしまいます。具体的には1 - 2 - 3が1 - (2 - 3)となってしまい答えが2になってしまいます。

というかステップ1以前に四則演算パーサ作って構文解析処理について理解を深めていたときに上記のボケを経験していたので今回は引っかかりませんでした(笑)

カッコの処理

掛け算よりも足し算が先に計算されるようにというカッコですが仕様の該当箇所を見てみると地味にめんどくさい書き方がされています。

CoverParenthesizedExpressionAndArrowParameterList :
    ( Expression )
    ( )
    ( ... BindingIdentifier )
    ( Expression , ... BindingIdentifier )

ただしその下に補足（Supplemental Syntax）があって、

When processing the production

    PrimaryExpression : CoverParenthesizedExpressionAndArrowParameterList

the interpretation of CoverParenthesizedExpressionAndArrowParameterList is refined using the following grammar:

    ParenthesizedExpression :
        ( Expression )

「production」が何のことを言ってるのかは気になりますがとりあえずParenthesizedExpressionということで処理をするようにしました。
アロー関数は前処理とかされるのですかね（アロー関数の仕様はまだ見ていない）

インクリメントの処理

構文解析

インクリメント仕様の中の以下の記述、

It is an early Reference Error if IsValidSimpleAssignmentTarget of LeftHandSideExpression is false.

ステップ2でも出てきましたが素のLeftHandSideExpressionは関数呼び出し等も含むために別途「代入操作ができるものか」がIsValidSimpleAssignmentTarget として定義されています。ちゃんとやるにはノードに付加情報として設定（して必要に応じて伝播）すべきでしょうがひとまず「ノードタイプが変数参照（IDENTIFIER_REFERENCE）」の場合はOKとしました2。

実行コードへの「展開」

普通のCPUならインクリメント／デクリメントは専用の命令が用意されています3。
それを踏まえてJOKEでは以下のようにしています。いやネイティブCPUのコードを吐けるようにしようとか考えてはいませんが。

  • 構文解析の段階（ノード出力）では「インクリメント」という情報を残す
  • 今からプログラムを実行させるVMはインクリメント命令がないので、実行コード生成（Assembler）で「インクリメントを実装する」命令列を作る4

初めに書いたようにインクリメントは後置しかサポートしていませんが、後置の「式の結果は足す前の値」に対応するための「実装命令列」は意外とめんどくさいですね。ある意味性能求めてない「興味に従って書いてみている」ことで得られた知見な気がします。

なお、代入演算子の方は構文解析時点で書き換えており一貫性がないなーと思うのですが、こちらは代入演算子用にノードタイプを増やしたくはなかったのでいいかなと思ってます。

言語仕様以外の改造

言語仕様の追加が少ないからというわけだったりわけじゃなかったりといろいろ今後の開発に役立ちそうな機能を実装しました。

REPL

ステップ2まではテストコードを少し書き換えて動作（不適切な記述が正しくエラーになるのかも含む）確認をしていたのですが、演算が出てくるといろいろなパターンを都度書き換えて実行するのもめんどうになってきたのでREPL（nodeやらpythonやらでソースファイルを指定しないと出てくる対話環境のあれ）を実装しました。
ただし、普通REPLというと入力した式の結果を表示するということを行いますが、そのためにはVMでのコード実行時に最後の一文だけはpopしない（POP命令を入れない）のような「REPL用の変更」を入れる必要があります（CPythonはそこら辺切り替えてたはず）。主目的は構文解析結果とかのダンプを見ることなのでREPL用の改造は入れませんでした（表示のためには自分でconsole.logを書く必要があります）

REPLのための入力処理はNode.jsのReadlineモジュールのexampleほぼそのままです。
あと、初めは「同じ名前の変数が2つ定義できる不具合」があり、簡単REPLだからいいかなとも思ったのですが、グローバルスコープの有効範囲を変える等して直しました。

-eオプション

というわけでREPLを作ったのですが、今度は「毎回コード片を入力するのがめんどくさい」ということになりました5。
そう、顧客が本当に欲しかったのは-eオプション（コマンドラインでコード片を指定できる機能）だったのですｗ

まじめに「-eが複数指定された場合」とかを対応すると手間がかかりますが、「簡単実装」であれば変更箇所も少なく実装が行えました。

タイプ等の定数化

前々から気にはしていたのですが、トークンタイプ等が文字列なので、まあスペルミスが起こる危険があるわけです（あった）
というわけでIDEで補完が効くように定数として定義するようにしました。

ただ、

import * as Token from './token.js';

と書くと「エクスポートされている名前をプロパティとして持つオブジェクト」が作られる、つまり、Token.NO_SUCH_TYPEと書いてもその時点で「そのような名前はない」エラーは起こらずundefinedが返されてしまうようでした。まあ補完性能は上がったのでいいかなと思います6。

プリプロセッサライク関数内関数

上の「タイプ等の定数化」と合わせて「ソースコードの行番号を実行コードまで受け渡す」処理も入れたのですが（実行時エラーのときにソース行を示すため）、その際、「Nodeオブジェクトのプロパティとして入れてあるソース情報をInstructionオブジェクトにコピーする処理」は大量のコードコピペが発生するのでどうにかできないかな、見出しのようにプリプロセッサ的なことできないかな、JavaScriptでは無理か、と思ったのですが、限定された状況なら関数内関数を使って実現できました。

assembler.js抜粋
function assembleNode(node, insns) {
    // shorten name
    const N = Node;
    const I = Instruction;

    // define function like preprocessor to reduce redundant code
    function makeInstruction(command, args) {
        insns.push({command, ...args, srcInfo: node.srcInfo});
    }

    switch (node.type) {
    case N.IDENTIFIER_REFERENCE:
        makeInstruction(I.PUSH, {operand: node.identifier});
        makeInstruction(I.LOOKUP);
        break;

ステップ2の実装と見比べるとpushを毎回書いていたのもなくなり（隠蔽され）いい感じです。

ステップ2でのassembler.js対応部分
function assembleNode(node, insns) {
    switch (node.type) {
    case 'IDENTIFIER_REFERENCE':
        insns.push({command: 'PUSH', operand: node.identifier})
        insns.push({command: 'LOOKUP'});
        break;

実行時エラー

さてというわけで実行コードにまでソースコードの情報が渡せたのでそれを使う話です。
例えば指定された変数があるか探すlookupObjectですがこの関数に「この関数自体の処理に必要ではない」ソース情報は渡したくないわけです。

というわけで実行コードを取り出して一つずつ実行する（関数を呼び出す）箇所でcatchしてソース情報を付け加えることにしました。

vm.js抜粋
function vmMain(insns, stack, scopes) {
    let ptr = 0;
    while (ptr != insns.length) {
        const insn = insns[ptr++];
        try {
            executeInsn(insn, stack, scopes);
        } catch (e) {
            // add srcInfo to message
            e.message += `: ${insn.srcInfo}`;
            throw e;
        }
    }
}

例外捕まえてメッセージ書き換えていいのかというのは気になるのですが動くからOK(笑)
なお、動作確認直後に「よく思うとエラー（例外）の起きた行情報ってのはスタックトレースで出るよな」と気づいたのですが、スタックトレースはES仕様にはないのでともかく当面「ソースのどこでエラーが起きているかわかればよし（現場猫略）」としました。

エラーの区別

開発記その2にも書いていた「処理系エラー」と「動かしているプログラムのエラー」が区別できない問題、（遠い将来にセルフホスティングすることも見据えて）あまり奇抜な区別方法は導入したくなかったので開発記その2に書いた通りにエラーメッセージに[JOKE]と入れるだけにしました。

それだけだと芸がなさすぎるので例外をキャッチした側で「プログラムのエラー」と「処理系のエラー」を区別して出力するようにしました。

joke.js（ルートの方）抜粋
function printError(e) {
    if (e.message.startsWith('[JOKE]')) {
        // program's bug. show only message
        console.error(`${e.name}: ${e.message}`);
    } else {
        // JOKE's bug. show stack trace
        console.error(e);
    }
}

function runScript(sourceFile, data) {
    try {
        const joke = new JokeEngine(debug);
        joke.run(sourceFile, data);
    } catch (e) {
        printError(e);
    }
}

今後の予定

以上、ステップ3の演算機能、と各種開発を便利にするための機能について説明してきました。言語仕様以外で結構改造しましたがエンバグしていないかはテストがちゃんと通るかで確認しました。テスト書くの大事ですね。7

さてともかく演算機能ができたので次はようやく関数定義と呼び出しです。RubyやPythonのコード読んだ経験も含めて「こんな感じにやればいいかな」という考えはあるのですがそれ通りにいくかはまだわかりません。

  1. 前置が難しいわけではないですが私があまり使わないので実装する動機がないのです。 ↩

  2. ステップ1でconsole.logのためにプロパティ参照を先行して実装したのでそちらも書いてはありますが多分ちゃんと動かないと思います。 ↩

  3. と書いてて変数がレジスタに対応してない＆RISCなCPUだと読み込み、演算、書き込みがいるなぁと思ったりもしますが。 ↩

  4. オレオレVMなので命令セットにインクリメントを入れればいいだけですが、今回はこっちでやってみたという話になります。 ↩

  5. node等のようにREPLを一度終了しても履歴がたどれるようにするのはこれまた実装するのがめんどくさいので。 ↩

  6. *でインポートするのではなく一つずつ名前を書けばいいわけですがそうするとタイプを増やすごとに書き換える箇所が増えて「メンテナンス性が悪い」ことになってしまいます。 ↩

  7. なおテストを書いていないところが変なことになっている可能性はある。 ↩

1
0
0

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
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?