Repository: syuilo/aiscript
Pull request #135 (2021-08-05 12:31:44)

[enhance] 中置演算子式評価時の演算子優先度評価の実装
<!-- ℹ お読みください
PRありがとうございます！ PRを作成する前に、以下をご確認ください:
- 可能であればタイトルに、以下で示すようなPRの種類が分かるキーワードをプリフィクスしてください。
  - fix / refactor / feat / enhance / perf / chore
  - また、PRの粒度が適切であることを確認してください。ひとつのPRに複数の種類の変更や関心を含めることは避けてください。
- このPRによって解決されるIssueがある場合は、そのIssueへの参照を本文内に含めてください。
- CHANGELOG.mdに変更点を追記してください。リファクタリングなど、利用者に影響を与えない変更についてはこの限りではありません。
- この変更により新たに作成、もしくは更新すべきドキュメントがないか確認してください。
- 機能追加やバグ修正をした場合は、可能であればテストケースを追加してください。
- テスト、Lintが通っていることを予め確認してください。
  - `npm run test`、`npm run lint`でぞれぞれ実施可能です
- `npm run api`を実行してAPIレポートを更新し、差分がある場合はコミットしてください。
ご協力ありがとうございます🤗
-->
<!-- ℹ README
Thank you for your PR! Before creating a PR, please check the following:
- If possible, prefix the title with a keyword that identifies the type of this PR, as shown below.
  - fix / refactor / feat / enhance / perf / chore
  - Also, make sure that the granularity of this PR is appropriate. Please do not include more than one type of change or interest in a single PR.
- If there is an Issue which will be resolved by this PR, please include a reference to the Issue in the text.
- Please add the summary of the changes to CHANGELOG.md. However, this is not necessary for changes that do not affect the users, such as refactoring.
- Check if there are any documents that need to be created or updated due to this change.
- If you have added a feature or fixed a bug, please add a test case if possible.
- Please make sure that tests and Lint are passed in advance.
  - You can run it with `npm run test` and `npm run lint`.
- Run `npm run api` to update the API report and commit it if there are any diffs.
Thanks for your cooperation 🤗
-->

# What
<!-- このPRで何をしたのか？ どう変わるのか？ -->
<!-- What did you do with this PR? How will it change things? -->
中置演算子式 (Infix) の演算子の優先度評価を実装した
優先度を評価し、木を作ることでネストする関数呼び出しに書き換えることで実現

# Why
<!-- なぜそうするのか？ どういう意図なのか？ 何が困っているのか？ -->
<!-- Why do you do it? What are your intentions? What is the problem? -->
中置演算子式導入時に未実装であった優先度評価を実装した
より直感的に AiScript のコーディングが可能になると考えられる

# Additional info (optional)
<!-- テスト観点など -->
<!-- Test perspective, etc -->
この PR では優先度や関数への置き換えをインタプリタで行っているが、将来的には意味解析などの段階で行うようにしたい (#124)

codecov[bot]: # [Codecov](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo) Report
> Merging [#135](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo) (340aea8) into [master](https://codecov.io/gh/syuilo/aiscript/commit/3e819595fccd92747776578d3ee9086ffc8a1ac5?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo) (3e81959) will **increase** coverage by `0.67%`.
> The diff coverage is `98.71%`.

[![Impacted file tree graph](https://codecov.io/gh/syuilo/aiscript/pull/135/graphs/tree.svg?width=650&height=150&src=pr&token=R6IQZ3QJOL&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo)](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo)

```diff
@@            Coverage Diff             @@
##           master     #135      +/-   ##
==========================================
+ Coverage   70.94%   71.62%   +0.67%     
==========================================
  Files          15       16       +1     
  Lines        2024     2072      +48     
  Branches      301      304       +3     
==========================================
+ Hits         1436     1484      +48     
  Misses        586      586              
  Partials        2        2              
```


| [Impacted Files](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo) | Coverage Δ | |
|---|---|---|
| [src/node.ts](https://codecov.io/gh/syuilo/aiscript/pull/135/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo#diff-c3JjL25vZGUudHM=) | `0.00% <0.00%> (ø)` | |
| [src/interpreter/index.ts](https://codecov.io/gh/syuilo/aiscript/pull/135/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo#diff-c3JjL2ludGVycHJldGVyL2luZGV4LnRz) | `93.00% <100.00%> (-0.36%)` | :arrow_down: |
| [src/interpreter/infix-to-fncall.ts](https://codecov.io/gh/syuilo/aiscript/pull/135/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo#diff-c3JjL2ludGVycHJldGVyL2luZml4LXRvLWZuY2FsbC50cw==) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo). Last update [3e81959...340aea8](https://codecov.io/gh/syuilo/aiscript/pull/135?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=syuilo).

marihachi: 特に意図がなければ、関数名は動詞から始まるほうが良さそう
syuilo: どの演算子がどういう優先度かっていうの暗記するの大変そうだなと思った
cwd-k2: 優先度は相対的なものだから「AよりもBが優先される」程度のものでしかないよ
cwd-k2: 優先度の振り方は大まかに
四則演算＞比較＞論理演算
で四則演算・論理演算はどちらも
積＞和
になってるので他の言語と言語と言語とそう大差ない
marihachi: 優先度の違う演算子が式に出てきたら、括弧で明示しないといけないことにするとか
cwd-k2: 単にタイプ数が増えるだけだと思うんだけど
現時点で括る括らないはオプショナルなのでガイドライン的に優先度を示すので十分な気がする

ルールとして括弧を強制するほどのものかなあ
嫌なら明示してねってのが筋が通ってる気がするんだけど

そのルールにするならやるけど
cwd-k2: 方針を決めるならばアンケートとった方がいいかも
syuilo: > ルールとして括弧を強制するほどのものかなあ

優先度について知らない人が括弧が無い計算式を見たら意図が把握できなくなりそう

まあ私がイレギュラーなだけかもしれないんで無視してもらってもOK

Patch:
diff --git a/src/interpreter/index.ts b/src/interpreter/index.ts
index aecf114..76be98b 100644
--- a/src/interpreter/index.ts
+++ b/src/interpreter/index.ts
@@ -9,6 +9,7 @@ import { std } from './lib/std';
 import { assertNumber, assertString, assertFunction, assertBoolean, assertObject, assertArray, eq } from './util';
 import { Value, NULL, RETURN, unWrapRet, FN_NATIVE, BOOL, NUM, STR, ARR, OBJ, FN, VFn, BREAK, CONTINUE } from './value';
 import { Node, NNs } from '../node';
+import { infixToFnCall } from './infix-to-fncall';
 
 export class AiScript {
 	private vars: Record<string, Value>;
@@ -419,35 +420,7 @@ export class AiScript {
 			}
 
 			case 'infix': {
-				// TODO: 優先順位とか結合性をきちんと考える
-				let val = await this._eval(node.operands[0], scope);
-				for (let i = 0; i < node.operators.length; i++) {
-					const narg = await this._eval(node.operands[i+1], scope);
-					const func = await this._eval(node.operators[i], scope);
-					assertFunction(func);
-					val = await this._fn(func, [val, narg]);
-				}
-				return val;
-			}
-
-			case 'operator': {
-				// TODO: 優先順位とか結合性をきちんと考える
-				switch (node.op) {
-					case '+': return scope.get('Core:add');
-					case '-': return scope.get('Core:sub');
-					case '*': return scope.get('Core:mul');
-					case '/': return scope.get('Core:div');
-					case '%': return scope.get('Core:mod');
-					case '=': return scope.get('Core:eq');
-					case '!=': return scope.get('Core:neq');
-					case '&': return scope.get('Core:and');
-					case '|': return scope.get('Core:or');
-					case '<': return scope.get('Core:lt');
-					case '>': return scope.get('Core:gt');
-					case '<=': return scope.get('Core:lteq');
-					case '>=': return scope.get('Core:gteq');
-					default: throw new AiScriptError(`No such operator: ${node.op}.`);
-				}
+				return this._eval(infixToFnCall(node), scope);
 			}
 
 			case 'return': {
diff --git a/src/interpreter/infix-to-fncall.ts b/src/interpreter/infix-to-fncall.ts
new file mode 100644
index 0000000..0f820b3
--- /dev/null
+++ b/src/interpreter/infix-to-fncall.ts
@@ -0,0 +1,112 @@
+import { AiScriptError } from './error';
+import { Node, NInfix, NOperator, NCall, Loc } from '../node';
+
+type OperatorInfo = {
+	func: string; // 対応する関数
+	loc?: Loc;
+	prec: number; // 優先度（高いほど優先して計算される値）
+};
+
+/**
+ * 中置演算子式を表す木
+ * 1 + 3 ならば次のようなイメージ
+ * ```
+ *   (+)
+ * (1) (3)
+ * ```
+ */
+type InfixTree = Node | {
+	type: 'infixtree';
+	opInfo: OperatorInfo;
+	lchild: InfixTree;
+	rchild: InfixTree;
+};
+
+function makeOperatorInfo(operator: NOperator): OperatorInfo {
+	switch (operator.op) {
+		case '+': return { func: 'Core:add', prec: 6, loc: operator.loc };
+		case '-': return { func: 'Core:sub', prec: 6, loc: operator.loc };
+		case '*': return { func: 'Core:mul', prec: 7, loc: operator.loc };
+		case '/': return { func: 'Core:div', prec: 7, loc: operator.loc };
+		case '%': return { func: 'Core:mod', prec: 7, loc: operator.loc };
+		case '=': return { func: 'Core:eq', prec: 4, loc: operator.loc };
+		case '!=': return { func: 'Core:neq', prec: 4, loc: operator.loc };
+		case '&': return { func: 'Core:and', prec: 3, loc: operator.loc };
+		case '|': return { func: 'Core:or', prec: 2, loc: operator.loc };
+		case '<': return { func: 'Core:lt', prec: 4, loc: operator.loc };
+		case '>': return { func: 'Core:gt', prec: 4, loc: operator.loc };
+		case '<=': return { func: 'Core:lteq', prec: 4, loc: operator.loc };
+		case '>=': return { func: 'Core:gteq', prec: 4, loc: operator.loc };
+		default: throw new AiScriptError(`No such operator: ${operator.op}.`);
+	}
+}
+
+function makeInfixTree(opInfo: OperatorInfo, lchild: InfixTree, rchild: InfixTree): InfixTree {
+	return { opInfo, lchild, rchild, type: 'infixtree' };
+}
+
+/**
+ * 現在の中置演算子式を表す木に新たな演算子と項を追加した木を構築する
+ *
+ * - 新しい演算子の優先度が現在見ている式の演算子の優先度 **以下** である場合は、現在見ている木は新しい演算子の左側の子になる。
+ * 1 + 3 - 4 = (1 + 3) - 4 ならば
+ * ```
+ *       (-)
+ *   (+)     (4)
+ * (1) (3)
+ * ```
+ *
+ * - 新しい演算子の優先度が現在見ている式の演算子の優先度より大きい場合は、右側の子と結合する。
+ * 1 + 3 * 4 = 1 + (3 * 4) ならば
+ * ```
+ *       (+)
+ *   (1)     (*)
+ *         (3) (4)
+ * ```
+ *
+ * - TODO: 左結合性の場合しか考えていない（結合性によって優先度が同じ場合の振る舞いが変わりそう）
+ * - NOTE: 右結合性の演算子としては代入演算子などが挙げられる
+ * - NOTE: 比較の演算子などは非結合性とされる
+ */
+function insert(tree: InfixTree, nextOpInfo: OperatorInfo, nextTree: InfixTree): InfixTree {
+	if (tree.type !== 'infixtree') {
+		return makeInfixTree(nextOpInfo, tree, nextTree);
+	} else if (tree.opInfo.prec >= nextOpInfo.prec) {
+		return makeInfixTree(nextOpInfo, tree, nextTree);
+	} else {
+		const { opInfo, lchild, rchild } = tree;
+		return makeInfixTree(opInfo, lchild, insert(rchild, nextOpInfo, nextTree));
+	}
+}
+
+/**
+ * 中置演算子式を表す木を対応する関数呼び出しの構造体に変換する
+ */
+function ascall(tree: InfixTree): Node {
+	if (tree.type !== 'infixtree') {
+		return tree;
+	} else {
+		return {
+			type: 'call',
+			loc: tree.opInfo.loc,
+			name: tree.opInfo.func,
+			args: [ ascall(tree.lchild), ascall(tree.rchild) ],
+		} as NCall;
+	}
+}
+
+/**
+ * NInfix を関数呼び出し形式に変換する
+ */
+export function infixToFnCall(node: NInfix): Node {
+	const infos = node.operators.map(makeOperatorInfo);
+	const nodes = node.operands;
+
+	let tree = makeInfixTree(infos[0], nodes[0], nodes[1]);
+
+	for (let i = 1; i < infos.length; i++) {
+		tree = insert(tree, infos[i], nodes[i + 1]);
+	}
+
+	return ascall(tree);
+}
diff --git a/src/node.ts b/src/node.ts
index 57e3eb2..af24576 100644
--- a/src/node.ts
+++ b/src/node.ts
@@ -226,7 +226,7 @@ export type NInfix = {
 	type: 'infix'; // 中置演算子式
 	loc?: Loc; // コード位置
 	operands: Node[]; // 項
-	operators: Node[]; // 演算子
+	operators: NOperator[]; // 演算子
 };
 
 export type NOperator = {


Test patch:
diff --git a/test/index.ts b/test/index.ts
index 49472b3..4bde4e9 100644
--- a/test/index.ts
+++ b/test/index.ts
@@ -116,6 +116,13 @@ describe('ops', () => {
 		eq(await exe('<: (0 <= 1)'), BOOL(true));
 	});
 
+	it('precedence', async () => {
+		eq(await exe('<: 1 + 2 * 3 + 4'), NUM(11));
+		eq(await exe('<: 1 + 4 / 4 + 1'), NUM(3));
+		eq(await exe('<: 1 + 1 = 2 & 2 * 2 = 4'), BOOL(true));
+		eq(await exe('<: (1 + 1) * 2'), NUM(4));
+	});
+
 });
 
 describe('Infix expression', () => {
@@ -164,7 +171,7 @@ describe('Infix expression', () => {
 	it('disallow line break', async () => {
 		try {
 			await exe(`
-			<: 1 + 
+			<: 1 +
 			1 + 1
 			`);
 		} catch (e) {