今月の活動 (コンパイラの教科書、hsp3-debug-window-adapterの更新、ドキュメント、読んだ記事など)
- 前回 (2022-05-31) https://vain0x.github.io/blog/2022-05-31/diary/
ミローネ言語
しばらく休み
- 読み取り専用なポインタと読み書き可能なポインタの間の部分型関係を型システムで扱えないこと、所有型を使ってエフェクトを追跡することの冗長さなどの課題を感じている
- 借用検査や (いま流行りの) 代数的エフェクトも検討したほうがよいかもしれない
コンパイラの教科書
- コンパイラの教科書をちゃんと読んだことがないので、よさそうなやつを読んでいる
- 構文解析のところまで読んだ
- 正規表現から非決定的有限オートマトン(NFA)を作ってシミュレーションするやつを実際にやったことがなかったので、やってみた
- LR(0)は前にやった (2019-09-30) が、LR(1)は試してなかったので、やってみた
- 本に書いてある構文が、本に書いてある通りのLR(1)ではパースできない気がした
- 手書きのパーサでパースできたので続きはそれでやっていく
- LRで生成されるDFAの使われかたがおもしろい
- 普通のDFAは開始状態からスタートして、入力を受け取りながら遷移を繰り返し、受理状態に辿りついて終了する
- LRのDFAは、途中の状態にドロップして、入力を受け取りながら遷移を繰り返し、その途中で再帰的にDFAに出入りする
- 複数のオートマトンを非決定的に融合したものだと思うとよいのかもしれない
- 本の後半ではx64のアセンブリを生成するっぽい
- ミローネ言語の実装にフィードバックできるかもしれない
構文解析
- コンパイラの教科書は構文解析の占める割合が多すぎるという意見がある
- オートマトンを使った字句解析やLR構文解析の話を詳しく書きがち
- 一方、構文解析を題材としてオートマトンを学ぶことを目的として、こういう構成になっているという意見もある
現実の処理系のパーサ
現実の言語処理系はパーサをどうやって実装しているかを調査したブログ記事を読んだ:
Parser generators vs. handwritten parsers: surveying major language implementations in 2021 | notes.eatonphil.com (公開日 2021-08-21)
- 調査結果として、パーサジェネレータを使っている処理系もあれば、手書きの処理系もあるようだ
- データベースエンジンによるSQLのパーサや、動的言語の処理系はパーサジェネレータを使いがちな印象がある
- 静的言語の処理系はパーサを手書きしがちな印象がある
筆者の意見
- 構文を適切に設計すれば、手書き再帰下降パーサは楽に書ける
- 構文の適切な設計に関する知見がこの十数年で溜まった
- 非終端記号の並びで始まる構文 (
T f() {}) とか、中置の記号が左辺に影響を与える構文 (() => T) とかは、パースしにくい
- 非終端記号の並びで始まる構文 (
let 名前 = ...やfn 名前() ...のようにキーワードから始めるとよい- ほとんどの部分は、1トークンの先読みでパースできる
- 数式の部分だけ左再帰をループで書くテクニックを使う
- LL(1)の手書きパーサはデバッグしやすい
- パーサコンビネータやパーサジェネレータのデバッグは内部の仕組みが分かっていないとつらい (印象)
- 性能がよいこと、エラー回復がしやすいことなどの利点もある (印象)
- 欠点もある
- 無限ループや無限再帰に陥りがち
- 適当に上限つきのカウンタを回すというワークアラウンドがある
- スタックオーバーフローのリスクがある
- カウンタを使って再帰深度を制限するというワークアラウンドはありうる
- メモリを無限に消費するタイプの不具合がLinux上で発生するとシステムが不安定になる
- earlyoomを使うと緩和できる
- 無限ループや無限再帰に陥りがち
パーサの実装のような単純作業を自動化してこそのプログラミングという気もする
CoWによるディープコピー
- 可変な参照のエイリアスによる、対象が「いつのまにか書き換わっている」ような挙動は理解しづらい
- Copy-on-Writeを使って参照のコピーをディープコピーであるかのようにみせるセマンティクスは分かりやすい
- 次にスクリプト言語っぽいものを作るときはそういうふうにしてみたい
hsp3-debug-window-adapterの更新
- v0.5.0 をリリースした
- 開発者用のドキュメントを書いた
knowbugのドキュメント
- knowbugのドキュメントを書こうとしている: 開発者向けのドキュメントを書く #110
- 前提知識が多い
開発用のスクリプトがpwsh用になっている
- gingerプロジェクトではshを使っているものが多い
- shというかbashのPOSIX互換モード
- Windows上なのでGitについてくるGit Bashを使う
- どちらかに揃えたい
- shのほうがよく使われているし、Dockerやサーバ環境でよく使うし、学ぶ価値は高い
- pwshのほうが仕様が正気で学びやすい
- .NETのライブラリを呼べるので応用もしやすい
うまく手離れさせたい
- knowbugはアクティブに開発されていないし、メンテナンスもあまりできていない
- knowbugに代わるデバッガを作る人が現れてほしい
- デバッガ作成のチュートリアルのようなものを書くとよいかもしれない
- gingerのほう (VSCode用のツール、UTF-8版の開発ツール、静的解析ツール等) も誰かやらんかなと思っている
- language-hsp3は順調に開発されているようだが、それ以外は全く足りていない
読んだ記事など
What it feels like when Rust saves your bacon | Baby Steps (公開日 2022-06-15)
- 借用検査のおかげで全く想定していなかったメモリ関連の不具合を検出できたという話
Safety features of the Hare programming language (公開日 2022-06-21)
- Hareの安全性のための機能を解説する公式のブログ記事
- Hareの型システムは健全ではない。抽象化を破壊する操作が許可されている
- しかし既定の挙動を安全になるようにしていて、安全でない操作は明示的に行うようになっている
- 記事の最後のほうに「全く安全でない言語」と「安全な言語」という極端な分けかたで論じられることへの反発に触れている
- Cの問題は安全性を担保する機能がないことでなく、安全でない操作があまりにも容易に入り込むことなため
ドキュメントに固執せよ - gfnweb (公開日 2022-06-18)
- ドキュメントを書くことの重要性と書くための指針などが書かれたエモい記事
- 前述のドキュメントを書き始めたのは主にこれの影響
- 書くのは非常に難しく、先が長い
- ドキュメントに対する軽量な形式手法がほしい
火と氷の踊り (リズムゲーム)
“A Dance of Fire and Ice” というリズムゲームがおもしろい
- マス目の上をリズミカルに移動していくゲーム
- マスの配置がリズムを表現している
- 移動方向に対する偏角とビートの間隔が対応している
- 180度が4分。直線上を動くときは4分のリズムで叩き続ける
- 90度に曲がるときは8分のリズムになり、120度は3拍子のリズムになる
- 6面のボスでつまづいている