近況 2020-06-30

 2020年6月30日 投稿 日記

今月の活動について (ジャッコ言語、競プロ、気になった記事の感想など)

ジャッコ言語

vain0x/languages at b0f4ff3e85e

  • 自作言語の萌芽
  • 基本的な機能の増強を行った
    • i64, usize, f64 などの数値型のリテラル記法、算術演算など
    • 構造体の定義、フィールドアクセスなど
    • 定数やグローバル変数の定義など
    • ほとんどC言語の対応する機能に置き換えているだけ
  • LSP の実装
    • picomet や hsp3-analyzer-mini と同様
    • パーサーを雑に書いたせいでクラッシュしまくるので、まだ実用的でない
  • 処理の責務を再検討した:
    • いまの実装では、構文木を辿って名前解決処理を行い、コード上の各識別子が何を (どの関数や変数を) 表しているかを決定した後に CPS 変換をしている
    • 名前解決の時点で関数や構造体が何個出現するか分かるし、i 番目の関数や構造体がどこで定義されて、どういう名前で、どういうパラメータやフィールドを持っていて、といった情報も分かる
    • なのに CPS 変換中にそれらの情報を収集していた
    • そのような作業を名前解決側に移動することで、CPS 変換の記述が軽くなった
    • 名前解決側単体で見ると必要以上の処理をしているようにみえる (収集した情報を使っていないようにみえる)
    • そういう分け方もあるようだった

hsp3-analyzer-mini

HSP3 の簡易 LSP 実装

スクリプトエディタのSDK機能のHSED_GETCARETPOSが無効になっていた不具合を修正

(HSP3.6β2を公開しました - おにたま(オニオンソフト)のおぼえがき より引用)

スクリプトエディタからも hsp3-analyzer-mini を使えるように LSP クライアントをせっせと作ってるけど、どうせ他の LSP サーバを使う機会はまずないんだから DLL (#uselib) でいいのでは……？ (Twitter @vain0x)

  • VSCode だけでなくスクリプトエディタからも hsp3-analyzer-mini を使えるように、スクリプトエディタ向けの LSP クライアントを作ろうとしていた
  • スクリプトエディタのカーソル位置を取得する API が HSP3.5 では機能していなかったので頓挫していたが、HSP3.6β2 版では修正してもらえたようなので作業を開始した
  • LSP クライアントとサーバーの通信は JSON 形式なので HSP だと実装がめんどくさい
  • よく考えると「スクリプトエディタ向けの LSP クライアントを実装する」のではなく、hsp3-analyzer-mini の DLL 版を作って #uselib/#func で直接呼ぶような実装の方が簡単だった
  • いまのところ実装はこんな感じ: hsed3-ext
  • まだ hover しか動かないから役には立たない
  • 他の機能 (入力補完とか) はスクリプトエディタ側での表示をがんばる必要がある

というか、

hsed 向けのクライアントを作るよりエディタ自体を作った方がいい気がしてきた。Footy2 開発終了してるっぽいし Linux 版もいるし (Twitter @vain0x)

ちなみに実際に作るとしたら WebView の上で monaco-editor を動かす方法が有力

競技プログラミング

AtCoder:

その他:

  • よるかつ (夜21時ごろに AtCoder Problems で有志が開いてくれている ABC レベルのバーチャルコンテスト) に何度か参加した
  • 第三回PASTに参加して上級を獲得した

PAST 3、M完 88点で上級だった (Twitter @vain0x)

競プロのライブラリ整備

PAST に出た将棋盤を使う問題の実装に手間取ったのでライブラリを整備した

ついでに C# の方も新しくした。C# 7 の式本体 (メソッドやプロパティの本体をラムダ式に似た構文で書ける機能) や、タプル (Rust のようなタプル記法が使える機能) のおかげでコードがガリガリ減った

気になった他人の記事など

SPA のルーティング

この記事を読んだ: SPAのルータについて自分なりのまとめ (2019年後半の記事)

  • 以前にウェブアプリを作ったときクライアントサイドでのルーティングの実装がめんどうだった印象がある
  • ログインしていない状態でログイン必須のページに来たら /login にリダイレクトするとか、
  • 逆にログイン済みの状態で /login に来たら /home にリダイレクトするとか
  • それから Slack みたいなログイン時もメールで認証する方式だったのでマジックリンクから来たらログイン状態にしてリダイレクトするとか……

react-router:

  • React を使うのであれば react-router というライブラリが有名だが、どうもしっくりこなかった
  • そもそもルーティングは UI の仕事ではないので、UI ライブラリである React とは切り離して考えるべきだった
  • 結局、URL のパス部分 (/login とか) に関して条件分岐して処理を分岐するという、文章にすると当然のような地味な実装に落ち着いた

リダイレクト:

  • リダイレクトするときは URL を書き換えるために history という API を使う必要がある
  • 雑に書き換えると戻るボタンを押したときに戻れない (再びリダイレクトされてしまう) とか戻りすぎてしまうとかがある

現在の意見:

  • アクセスされたのがログインが必須のページか否か、アクセスしてきたユーザーがログイン済みかどうか、というのをサーバーサイドで見てリダイレクトしてやれば解決しそうな気がした
  • つまりログイン不要のページは従来通り Express.js で実装して、ログイン後だけ SPA として実装する
  • パスの相互変換とかは上記の記事を参照。クライアントサイドのリダイレクトが減ってやりやすくなるはず

四分木のモートン順序

この記事を読んだ: 【四分木】HSPで大量の当たり判定を検出する【モートン順序】

元の課題:

  • 数百〜数千個のオブジェクトの衝突判定をまともに実装すると時間がかかりすぎてフレーム落ちし、カクカクになる
  • HSP に限らず C++ でも数が増えるときつい

解決策:

  • オブジェクトの位置をいくつかの区画に分割して、離れた区画にあるオブジェクト同士の衝突判定を省略することで高速化する
  • どのオブジェクトがどの区画にいるか、などの情報を四分木で管理する (詳細は上記記事)
  • 四分木の操作としてモートン順序を利用すると簡潔かつ高速な実装になるらしい

感想:

  • 上記の記事のコードはオブジェクト数 500 なら 60 FPS 出るが、1500 個ぐらいに増やすとさすがにカクカクになるっぽかった (そもそも描画だけできついかも？)
  • ジャグ配列 (配列の各要素が配列であるという、二重の構造の配列) をモジュール変数を使って実装していて、正直遅そうだった
  • この要素数なら二次元配列で実装した方が速そう、なので試そうかと思って実装を手直ししていたが、(四分木ではなく) 総当りによる衝突判定を2次元配列による実装に書き換えても高速化がみられなかったのでダメそうな予感がある (なので四分木版はまだ実装していない)
  • モートン順序を競プロに活かせるかもしれないと思ったが、よくみると BIT (binary indexed tree) の2次元への自然な拡張だった
    • 面白いけど役立てる機会はなさそう

整数のパース

この記事を読んだ: atoi関数のかしこい実装

  • 絶対値をパースした後に、最初に - がついていたら -1 倍する、という実装だと最小値をうまくパースできない
  • 例えば符号付き32ビット整数では、負の最小値 -2^31 の絶対値である 2^31 を表現できない
  • 逆に、「絶対値の負」をパースしてから、最初に - がついていなかったら -1 倍する、という実装なら通る

自動生成されたコードや他人のコードをコミットするときの設定

.gitattributes に linguist-generated や linguist-vendored を指定すると、そういう意図をツールに理解してもらえる

気になったことなど

コードフォーマッターはフォーマットする前のソースコードになるべく依存しないでほしい話

コードフォーマットは (AST, コメント, 空行) から決定的に定まってほしい。フォーマットする前のレイアウトによって結果が変わると、書き方によって一貫性がなくなったり、ある程度は手動でフォーマットしないといけない。rustfmt の挙動は理想に近くて快適 (Twitter @vain0x)

例えば、次のような関数呼び出しの式を1行で書くのか複数行に分割して書くのか、みたいなのはフォーマッターが独断で決めて書き手の気分や感覚に依存しない方が全体として一貫性が高くなる

    // 一行で書く
    call_some_function(another_function(), yet_another_function());

    // 分けて書く
    call_some_function(
        another_function(),
        yet_another_function(),
    );

ただしコメントを勝手に消すのはまずい。それから、空行をつかってグループ分けするのは一般的なので、そこも残すことになる。例えば次のコードは文の羅列だが、最初のブロックは「入力を読む」、次のブロックは「計算する」、最後のブロックは「出力する」という意味上のまとまりがあるので、空行を消されると困る。(しかし関数に分けるほどではない。)

    let (input_path, output_path) = parse_args(args);
    let csv_text = read_from_file(input_path);

    let data = parse_csv(csv_text);
    let statistics = analyze_data(data);
    let json_text = serialize_to_json(statistics);

    print_to_file(output_path, json_text);
  • もしかしたら気づいていないだけで、他にも維持しなければいけない要素があるかもしれない
  • 何にせよ、ここでいいたいのは書き手によるフォーマットへの裁量を可能なかぎり少なくした方がよいということ
  • 注意: rustfmt は「(AST, コメント, 空行) から決定的に定まる」わけではないし、そういう設計方針で作られているわけではない

競プロ界隈でのビッグオー記法の誤用の原因の推測

ビッグオー記法が誤用されがちなのは正しい定義が理解されていないからというより用途に適してないからな気がするし、「O(10^5)」とかの背景にある気持ちを記述できるノテーションが発明されてほしい (Twitter @vain0x)

状況:

  • 競プロ界隈ではたまーにビッグオー記法が誤用される
  • たまにみられるだけで、誤用が蔓延しているわけではない
  • 定義を理解していなくて間違った使い方をしてしまう人がいる、という話ではない
    • 間違ったことを言う人がいるのはどの界隈・どの概念についても同じ
    • 間違ったことを言う人が多すぎるわけでもない
  • 数学的なビッグオー記法の意義・定義を理解した上でなお「誤用」用法が使われることがあるのが気になる

例 (創作):

  • 「N≤10^5 の制約下で、長さ N の配列から1つの要素を線形探索するのは O(N) 時間かかる」(正しい)
  • 「要するに O(N) = O(10^5) だから間に合う」(おかしい)

どこがおかしいか:

  • O(10^5) = O(1) は O(N) ではない (等号が成立しない)
  • 最悪計算量が O(N) で N≤10^5 であっても定数倍や定数項が巨大だと間に合わない (評価が荒い)

原因の推測:

  • この例のような文脈では上限の評価がしたいだけで、計算量の漸近解析 (極限的な振る舞いの観察) はしていない
    • N→∞ での振る舞いや、N を動かしたときに線形探索の時間計算量がどのように変化するか、といったことは本題でない
    • N≤10^5 の範囲における時間計算量の上限が重要
  • X(N) = X(10^5) になるような使いやすいノテーションがあればなあ、という話

メタ型変数の束縛に RefCell を除去できなかった話

型推論の単一化中に、メタ変数が指す型への参照を受け渡しながら (型環境の共有参照をとる)、メタ変数に型を束縛する (型環境の排他参照を取る) ところで詰まってる (Twitter @vain0x)

  • 実装はジャッコ言語のコードベースを参照
  • 関数や変数の型をすべて RefCell で包む雑な実装をしていた
  • データの持ち方を改善して不要な RefCell を除去する作業をした
  • ジャッコ言語は Rust のように関数 (fn) の引数や返り値の型注釈が必須なので、型推論にかけるまでもなく関数の型が確定する
  • 型推論中に関数の型の排他参照 (&mut Ty) を借用する必要はない
  • このように排他参照を取る必要のないデータと、型推論中に書き込む必要があるデータに分けておき、前者を共有参照 (&T) で持つようにすればだいたいの RefCell を消せた
  • ただメタ型変数だけは消せなかった、残念、という話

HSP3 のコードの一部をユニットテストした話

HSP でユニットテストを書く方法が分かりつつある (Twitter @vain0x)

hsp3-ginger/mod_hsed_docs_test.hsp at 2dea333

  • ユニットテストを行うためには依存関係を排除しなければいけない
  • 例えば上のモジュールは、「スクリプトエディタのタブのリストや、各タブで開かれているファイルを監視して、ファイルが開かれたり閉じられたりしたことを検出する」という機能
  • スクリプトエディタを実際に起動してテストするようなコードを書くのはめんどくさい
  • 入力・処理・出力を分割する
    • 入力: スクリプトエディタから得られる情報 (いまどのようなタブが開かれていて、各タブはどのファイルを開いているか) を配列や文字列としてモジュールに渡せるようにしておく
    • 処理: 渡されたデータを使って、モジュールの中で計算処理をする。ここではスクリプトエディタにアクセスする必要がない
    • 出力: 計算結果をモジュールの中の変数に記録したり、配列や文字列として外部に渡す
  • スクリプトエディタから情報を取得する部分や、計算結果を実際に使用する部分はテストできないが、中間の計算処理はテスト可能になる
  • ちなみに「必要なデータを自発的に探させるのではなく、すべて外部から手渡しする」手法をデータポンプというらしい (参考: マイクロサービス、WebAPI、設計の初歩的なメモ)

その他

構文解析の結果をどう持つか

構文解析の結果をデータ構造で持たず、構文解析中に起こすアクションを渡せるようにして必要なだけパーサを実行する案 (LL(1) だからバックトラックとかは起こらないし速いのでは？) (Twitter @vain0x)

  • ジャッコ言語では構文解析の結果として構文木を組み立てている
  • 構文木を辿って前述の名前解決などの解析を行う
  • 解析結果と構文木の特定のノードの関連付けをどう表現するか
  • いまのところ、構文木に追加のフィールドを配置して、そこに書き込むようにしている
    • dirty な方法という感じがある
  • 他の方法として、構文木のノードに ID を振って HashMap<ID, T> みたいな外部のマップを持つという方法もある
    • 構文木のノードに ID を振るのがめんどくさいし、依然として dirty 感は否めない
  • あるいは、構文木を共有参照 &Tree でつかんでしまえば、ノードへのポインタが移動しないので HashMap<*const Expr, T> のような外部のマップを持てる
    • 構文木を書き換えるときは情報を捨てればよいので、構文木を書き換えられないことは問題にあたらない
  • パースイベントをリストとして持って、それへのインデックスを使って割り当てるという案もある
    • パースイベントとは「ノード n を生成した」「トークン t を読み進めた」など
    • 構文木とパースイベントを両方持つと情報が重複するので微妙
    • かといってパースイベントから構文木を復元するのは楽ではない
  • 悩み中

HSP3 の拡張プラグイン

hsp3-ginger/hsp3-vartype-int64 at ecb9a19eb1e60a

  • HSP に int64 型を追加する拡張プラグインを作った
  • いまプラグインを作ったらどういう感じになるのか気になったため

GitHub actions scheduled jobs

submissions/submissions-sync-workflow.yml at 7987726a6f · vain0x/submissions

  • 以前に AtCoder への提出を Git リポジトリにコミットしていくツール (submissions-sync) を作った
  • GitHub Actions のスケジュールジョブでこれを実行して GitHub にプッシュさせることで、自動的に提出が GitHub にバックアップする仕組みを用意した
  • 現在試験運用中

関連記事