Refactoring for v5.0.2.0

[kmyk-jikka]

Refactoring for v5.0.2.0

[kmyk]

「関数 f は単調なので min { f(x) | x in [0, n) /\ f(x) >= a } (O(n)) は binsearch [0, n) (fun x -> f(x) >= a) (O(log n)) に最適化できますね」 とかをやっていく必要があり、この「関数 f は単調である」みたいな情報を素朴に型として表現しようとしていた (自然な発想) のですが、やめた方がいい気がしてきたんだよね。普通に annotation でよいはず。なぜなら、依存型はとってもしんどいので

[kmyk]

現状の実装の処理の流れ (Debug.hs):

1. Python コードの字句解析
2. Python コードの構文解析
3. Python AST の α 変換
4. Python AST に型変数を挿入し型付き Python AST に変換
5. 型付き Python AST の型推論
6. 型付き Python AST を ML AST に変換
7. ML AST 上で最適化 (無用変数削除)
8. ML AST 上で最適化 (演算子強度低減)
9. ML AST を SSA 形式ぽい形へ簡略化
10. ML AST から C++ AST へ変換
11. C++ AST からコード生成

[kmyk]

v5.0.2.0 表層言語 暫定仕様 docs/language.md

[kmyk]

エラー報告のことは考えてたけどエラー回復のことを考えてなかったね。回復は経験値が 0 なので困ったな

[kmyk]

コードの位置情報を AST の全頂点に付けるのはしんどすぎるが、ではどこに付けるのがいいのだろう。変数だけ？

[cannorin]

位置情報は基本的にASTの全頂点に付けるべき．私はよく

type WithInfo<'info, 'a> = {
  info: 'info
  value: 'a
}

type UntypedAst<'info> =
  | Var of string
  | App of UntypedAstWithInfo<'info> * UntypedAstWithInfo<'info>
  | Abs of string * UntypedAstWithInfo<'info>
and UntypedAstWithInfo<'info> = WithInfo<'info, UntypedAst<'info>>

みたいなことをやっています

↑これは Haskell なら型クラスとか使っていい感じに出来たりしないかな？ Haskell で真面目なコンパイラ書いたことないからわからん．

[cannorin]

一応，Python そのものではなく .pyc をパースするという方法もなくはないと思う

まぁ今の場合は Python のサブセットを表層言語にしたいっていうモチベなわけだし（そうだよね？）このままでいいか

[cannorin]

エラー回復については基本的なことは https://www.tutorialspoint.com/compiler_design/compiler_design_error_recovery.htm に載っている．Panic Mode は素朴すぎるのでナシとすると，Statement Mode が一番ラクと思う．

[cannorin]

実装上は，実質は lexical error と syntactical error しか問題にならない（semantic error / logical error のエラー回復はわりと自明なので）．AST の前にコードブロックとかのレベルでのゆるい parse tree を用意しておいて，parse tree -> AST の変換時にどこかの場所でエラーが起こってもそこを放っておいたまま違う場所の変換を試行できるようにするのがラクかなぁ（Lexer/Parser とどう連携するのがベストかはよくわからない）．

↑これ Lexer/Parser 側でいい感じにやってくれる機能が備わってたりしないんだろうか

[kmyk]

@cannorin ありがとう。助かります

位置情報は基本的にASTの全頂点に付けるべき．

ここで言う AST は表層言語のもののみを指すという理解であってますか？
ところで内部的には λ 項だったり最終的には C++ AST もありますが、そのようなものへの位置情報についておすすめはありますか？

↑これは Haskell なら型クラスとか使っていい感じに出来たりしないかな？ Haskell で真面目なコンパイラ書いたことないからわからん．

この方式は以前に教えてもらったからすでに使わせてもらってます: Pos.hs Expr.hs

一応，Python そのものではなく .pyc をパースするという方法もなくはないと思う

まぁ今の場合は Python のサブセットを表層言語にしたいっていうモチベなわけだし（そうだよね？）このままでいいか

.pyc をパースするのはありではあります。Python サブセットのひとつである RPython の処理系はそうしてたはず (言われるまで忘れてたけど)。
同様に ast.parse の結果を借りるのも選択肢に入るはず。

しかし、拡張性のためにそういう密結合は避けた方がいいと思ってます。今回は Python の厳密なサブセットであることに本質的な意味はない (ユーザにとって理解しやすいからそうなってる) だけなので、利便性が上まわるなら気軽に非互換機能を足せるようになっていてほしい。たとえば「切り上げ除算 2 項演算子」とかは使えてほしい。

AST の前にコードブロックとかのレベルでのゆるい parse tree を用意しておいて，parse tree -> AST の変換時にどこかの場所でエラーが起こってもそこを放っておいたまま違う場所の変換を試行できるようにするのがラクかなぁ（Lexer/Parser とどう連携するのがベストかはよくわからない）．

コードブロックのレベルでの parse tree を作るのがかしこそう。採用です。ありがとう。
Parser にもそういう機能があったりなかったりすると思うけど、かなり複雑になってしんどそうだし、単純な方法でできるなら単純な方法ですませることにします。

[cannorin]

ここで言う AST は表層言語のもののみを指すという理解であってますか？

型検査エラーなどをいい感じに出したかったら内部表現にも付ける必要が出てきます．

ところで内部的には λ 項だったり最終的には C++ AST もありますが、そのようなものへの位置情報についておすすめはありますか？

これに関しては元のコードの位置情報を泥臭く伝播させていくしかないと思います．実行時エラーもいい感じにしたい（かつ生成対象の言語がコード自動生成を意識してコードの位置情報をメタデータとして持っておく機能を備えている）ならば全ての段階において位置情報をもたせておく必要がありますね．