Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

今日は Regex Festa の日です

技術

今日は Regex Festa の日です

Regex Festa に来ていますので、自分のためのメモを残しておきます。

挨拶

  • wi-fiとお手洗い、喫煙所の案内
  • Opt Technologies さんについて
  • QRコード読むとアンケートあります

いろいろな正規表現、いろいろなオートマトン / @sinya8282 さん

  • 正規表現は好きだが、難しい面も面白い面もある
    • 学部の頃は世界最速のgrepを書いてたりした
    • 院では学術よりな研究
  • Shibuya.pm#16 が正規表現オンリーなイベントだった
    • 東京素晴らしい！
    • 8年の時を経て復活
  • 正規言語の魅力
  • 正規表現は難しい
  • /(\D+|<\d+>)*[!?]/ pcrepattern のマニュアルに出ている
    • VM型の正規表現と相性が悪い( * の中に + があるから)
    • pcregrep で "a" x 23 をマッチさせると、失敗する
    • リソース不足になる (21世紀なのに23文字がだめなの・・・)
    • atomic group (?> ... ) を使うと解決
      • バックトラックを抑制する
      • 共通してマッチしない表現の和だと、使えるテクニック
  • (a?){22}a{22} 長さ22から44までの a の列にマッチ
    • pcregrep は "a" x 23 は失敗。 21 個なら大丈夫 (令和だぜ・・・？)
    • grep -E なら DFA 型なのでマッチできる
    • a? のマッチの仕方が複数あるため
    • a?? にすればマッチングできる。 ?? は最短一致を先に施行する
  • 正規表現技術入門 の 7 章を見て下さい
  • Tagged NFA (TNFA)
    • 有限個のカウンタを持つ
    • キャプチャを可能にする
    • むずいので論文読んで教えて
  • 透過性の判定は難しい
    • 正規表現が同じ文字列の集合を受理するのか
  • (a|b)* と (a|bb*a)*|a*b(b|aa*b)* は等しいのか
    • NFAにして考えると、aで終わる文字とbで終わる文字の結合だとわかる
    • オートマトンを介するしかない
  • 正規表現は難しい、オートマトンはかんたん
  • 公理を使って直接証明することはできる
  • 正規表現が重宝される理由
  • 1行で書けるからかんたんとは限らない
  • オートマトンはちょろい、かわいい
    • 様々な拡張モデルの提案
    • スタックやキューなど。後者はチューリング完全だが前者は違う
    • 受理、非受理だけでなく、受理する確率や、文字列など
      • weighted automata はかっこいい
  • オートマトンはFA
    • AFA～ZFAまで全部ある（略称が被っているものもある）
    • KFAとYFAは微妙にないと言えるかも。新しいオートマトンを作るチャンス
  • 語の組合せ論
    • 部分語の出現を数える
    • 部分語の出現回数がふさわしいような言語 $L^{=}$
  • 無限集合になるかどうかを判定できるか？
    • L^{=} \{ a, b, c \} は正規表現でも文脈自由でもない
    • L^{=} \{ ba, ba, a \} は \{ \epsilon, b, bb, bab, bbb, ... \} 無限集合
    • L^{=} \{ ba, ba, a, b \} は \{ \epsilon \} 無限集合
  • 2018年に語混合言語の無限性は決定可能であることを示した
  • constrained automata
  • オートマトンはちょろいのではなく奥が深い

regex-applicative: 内部DSLとしての正規表現 / @igrep さん

  • 日本Haskellユーザーグループ をよろしく
  • 今日はHaskellについては話さない
  • regex-applicative
  • match :: RE s a -> [s] -> Maybe a
    • 完全一致のみ
    • マッチしたら Just しなければ Nothing
  • 連接は *>
    • sym 'a' *> sym 'b'
    • string "ab" と同じ
  • 選択は <|>
    • sym 'a' <|> sym 'b'
  • 繰り返しは、 many (0 回以上) と some (1 回以上)
  • optional オプショナル ? と同じ
  • マッチした値を Haskell の値に割り当てる
    • digit 数値
    • many digit 数値のリスト
  • 正規表現内で計算
    • sum <$> many digit
  • string "http" *> optional (sym 's') *> string "://"
    • some (psym (`elem` ['a'..'z'] ++ "."))
    • psym は関数が芯になるような文字はマッチする
  • マッチ結果を構造体にマッチできる
    • data Origin = Origin { ... } を定義
    • Origin <$> scheme <*> host <*> (prot <|> pure 80) (この例はschemeが正しく取れてないので注意)
    • <$> と <*> で組み立てられる
  • メリット
    • コンパイラによる型チェック
    • 文字列以外の扱いが得意
  • デメリット
    • コードが長い
    • 速度も速くない
    • String 以外にはマッチできない
  • 仕組み
    • 継続渡しで作られたNFA
    • バックトラック
  • 正規表現の分類 - DFA型とVM型
  • regex-applicative は
    • NFA をそのまま使っている
    • 文字を受け取って次の状態を渡すリストとして表す
    • s -> [Thread s r] の実行に失敗したらバックトラックする
    • findLongestPrefix 関数のような実装に役に立っている
  • 比較
    • パーサコンビネータは Applicative ベースなので似ている
      • バックトラックをするかしないかが違う
    • パーサコンビネータは部分一致できないが、部分一致できるようにするライブラリもある
    • regex-applicative は部分文字列へのマッチがかんたん

Emacsと正規表現 / @tadsan さん

  • PHPには複数の正規表現エンジンがある
  • ereg (POSIX ERE、廃止), preg (PCRE), mb_ereg (鬼車)
  • 現状のPHPにはリテラルがない
    • バックスラッシュを一文字にマッチするには \\\\
  • preg ではデリミタを変更できる
    • '@ ... @i' など。後ろはパターン
    • 正規表現と競合しないものがいい
  • 内部的には正規表現結果はキャッシュしている
  • Emacsのエディタの検索機能
    • Emacsの正規表現はNFA
    • グループなど \ の前置が必要
    • [:space:] など癖がある
  • Lispでは foo-bar は1つのシンボルだが、C言語では減算
    • syntax table で変更できる
    • 逆に言うと正規表現の結果は、バッファの syntax table の値で変わる
  • 文脈によってエスケープの違いがある
    • \\ と "\\\\" みたいな
  • emacsのメジャーモードを書くには、大量にエスケープを書く必要がある
    • 読みにくい
    • rx という DSL がある (group "regexp") (repeat n m pattern) など
  • re-builder で色付けができる

ヘルプシステムで正規表現を使う / @masui さん

  • Scrapbox
    • 簡単に使える wiki
    • 正規表現を展開してヘルプシステムに使う
  • ヘルプシステムは情報が見つからないので誰も使わない
    • なぜか正規表現で解決できる
    • コールセンターに電話してしまう。3年でやめる
    • 一兆三千億円規模。書籍と同じ
  • データを網羅的に生成、それからフィルタリング
    • Generate & Test
    • 網羅してから合うものを選ぶ
  • 正規表現展開ライブラリ
    • (a|b)+ を a, ab, b, ... と展開したり
    • ユーザの質問を正規表現で書いて、展開したものであいまい検索を実行する
    • (時計|時刻)を(1?[0-9])時に(設定|セット)する
    • 回答だけではなく、実行もしてしまう
  • あいまい検索はちょろいオートマトンで実装
  • Git Help
    • 難しい git コマンドをかんたんに実行できる
    • ある文字列が初めて出現したバージョンの出し方とか
    • gitはなんでもできるが誰もそんなことは知らない（難しすぎる）
    • IME的に実装。コマンドを打つとコマンド一覧の窓が出て、実行可能
  • Helpfeel
    • ヘルプページ向けのサービス
  • GitHelp は論文投稿したがリジェクト
    • Gitを使ってないらしくリジェクト
  • http://masui.org に資料あります

正規表現の等価性判定について / @make_now_just さん

  • 正規表現の等価性は判定可能で、そのアルゴリズムの話
  • 例えば、Base64にマッチする正規表現は複雑
    • 文字列長が4の倍数と末尾の = の扱い
    • 2つの正規表現に分けたものと、等しいかチェック
  • 正規表現はDFAにでき、DFAを最小化できる。それが同型かを判定可能
    • 効率が悪い
  • 効率の良いアルゴリズム
    • DFAにはする
    • 初期状態からアルファベットのすべての文字について遷移させる
    • 受理状態がどこかで食い違ったら別
    • 割と普通の幅優先探索になる
    • 対応する状態を色付けして分類していく
    • すべての分類が一致すれば完了
  • 単純でDFAの最小化より効率的。DFAを作る時点でコストは大きい
  • NFAで判定する方法はどうか
    • NFAへの変換は楽なのでいい
    • 本当は正規表現のまま比べたいのでは
  • 正規表現の微分で判定する
  • 文脈自由言語の等価性は決定不能であることは知られている
  • 論文では、NFAを使ったものが一番早いそう

ミニマルな正規表現エンジンをScalaで実装してみた / @kmizu さん

  • 正規表現エンジンを自作する方法
  • アルファベット、空列、連接、和、Kleene閉包、e? e+
  • 実装は教科書的
  • ASTとNFA、NFAState、DFAなどを定義
  • パーザはASTを作る
    • 脱糖もする e? は e| 、 e+ は ee*
  • 正規表現を教科書的にNFAにする
    • 変換規則に沿って変換するだけ
  • NFAをDFAにする
    • 部分集合構成法
    • NFAの状態の集合のサブセットをDFAの状態にする
  • 300行未満で書けるので、みなさんも書きましょう

その正規表現エンジン、インタプリタで満足(satisfy)してる？！ / @blackenedgold さん

  • SATySFi
    • TeXを倒すためのもの
    • 日本語が扱えてPDFが出力される
  • ML風の関数定義、バックスラッシュのコマンド
  • インタプリタとコンパイラ
  • (第一)二村射影
  • 多段階計算
    • ステージ0でステージ1で実行されるプログラムを生成する
    • ステージ1でプログラムを実行する
  • &42 は次のステージで 42 になる。 &int 型
  • SATySFi には差ショートサーキットする論理 or and がない
  • マクロっぽいが、式から式の変換しかできない
    • eval には制約が入っている
    • 生成されたコードはコンパイルエラーにならないように型がつく
  • インタプリタの実装はDFAベースよりかんたん
  • 命令列をリストで書く (εと連接が何もしなくても手に入る)
  • SATySFiは文字がないので、文字列を文字代わりにする
  • 強欲マッチ(バックトラックは実装しない)なので、かんたん
  • これをコンパイルするのは & と ~ を適切に入れるだけ
  • コンパイルにすると、静的(stage 0)でエラーを検出できる
    • 組版で後半のページでエラーが出ると、前のページの生成が無駄になる
  • コンパイルだと正規表現は静的に与えなければならない

l3regex: TeX で実装された正規表現エンジン / @wtsnjp さん

  • l3regexの3つのポイント
    • 将来性がある
    • 実装がすごい(TeXで実装されている)
    • 実用性がすごい
  • LaTeX3プロジェクトなので将来性がある
    • LaTeX2eの光景
    • 1990 年代から作られている
  • 実装がすごい
    • TeXは名前空間がない、展開制御がない、副作用がいっぱい
    • 字句解析にチューリングマシンが必要となる言語
    • NFAベース(らしい)
    • TeXで実装するとあらゆる環境で動くので
  • 実用性 - 普通のライブラリ
    • バックスラッシュが蔵試食したりしない
    • TeX Live, MiKTeXなどでも導入される
  • 滅ぼされる言語かもしれないが、来週提出の論文には使える！

正規表現苦手なんです / @5mingame さん

正規表現のlook behindで量指定子を使いたい / @hachi8833 さん

  • (?<=...) (?=)
    • look behind に長さが違う (...|...) や ? {1, 2} .+ .* を書くことができない
    • 長さが変わってはいけない
  • ? {1, 2} がだめなのはなっとくいかない
    • (a|b) のように長さが変わらないのはいい
    • {3} とかも
  • .NET Framework の正規表現ではフルで使える
    • 最強の正規表現エンジン
    • ドキュメントも充実
  • V8 の正規表現エンジンもいける
    • 昔のJSは look behind 自体がなかった
    • 文字クラスも使えるように？
  • PCRE と Onigmo も頑張ってほしい

とある機械の右方跳躍 / @sinya8282 さん

  • 世界で知っている人10人もいない
  • right one-way-jumping automata
    • 日本語訳は shinya さんが勝手につけたもの
    • 文字列を読むときに、1文字ずつではなく飛び越える
    • 秋田大の学生が考えたもの
  • (b|a)* の DFA を右方跳躍オートマトンとして扱うと、 a と b の出現回数が同じものを受理する
  • 例えば、 baaabb は ba で計算が終わるはず
  • 「optさんが素晴らしい酎ハイを用意してくれたのでちょっと酔ってる」
  • 右方跳躍では、遷移可能な文字で一番近い文字に飛ぶ
    • 一番右まで行くと左から戻ってくる
  • 「与えられた右方跳躍オートマトンAがDFAのとき、Aの受理する文字列の集合が正規言語になるかどうか、のアルゴリズムが存在するか」は未解決

結局rustの標準入出力はどう書けばいいの？

技術

現状。 StdoutLock は LineWriter を噛んでるので、 BufWriter の意味があるのか謎。ベンチマーク取らねば。

use std::io::{self, BufRead, BufWriter, Write};

fn main() {
    let stdio = io::stdin();
    let mut input = stdio.lock();

    let stdout = io::stdout();
    let mut output = BufWriter::new(stdout.lock());

    let mut line = String::new();
    while input.read_line(&mut line).unwrap() > 0 {
        let _ = writeln!(output, "{}", line);
        line.clear();
    }
}

↑のコードは以下を参考に勘で書いている。

【追記】WSL上での雑なベンチ

BufWriter の意味はありそう。以下がない場合。

$ time yes | head -n 1000000 | ./target/release/bench > /dev/null

real    0m4.102s
user    0m1.250s
sys     0m2.906s

BufWriter 噛ませた場合。 42 倍くらい違う。

$ time yes | head -n 1000000 | ./target/release/bench > /dev/null

real    0m0.098s
user    0m0.063s
sys     0m0.047s

さらに、 writeln! マクロを使わずに、

        let _ = output.write(line.as_bytes());
        let _ = output.write(b"\n");

とかやると、もうちょい早い。

$ time yes | head -n 1000000 | ./target/release/bench > /dev/null

real    0m0.073s
user    0m0.031s
sys     0m0.063s

emacsで自動改行して欲しくない

技術

特に端末へコピペとかするときに、本当に迷惑なので。

init.el をイジる。まず、 (setq indent-line-function 'insert-tab) なんて記述があったので削除（誰がなんのために入れたんだ？）。

次に、 (electric-indent-mode 0) を追加。

これでほとんどのモードで直ったのだけど、 markdown-mode だけは駄目だったので、ダメ押しの (setq markdown-indent-on-enter nil) を追加。 RET 押下時の indent-and-new-item の呼び出しを抑制できるらしい（勝手にそんなことしないで）。

メジャーモードによって挙動を上書きできるようなので、おかしなメジャーモードがあったら設定などを見直して対応していくしかなさそう。

今日はRustのLT会 Shinjuku.rs #6 @FORCIAの日です

技術

ブログ枠で RustのLT会 Shinjuku.rs #6 @FORCIA に来ています。ブログ枠が何をすればいいのかあまりわかってませんが、とりあえずブログにメモを残しておきます。

開会

  • 会場、懇親会はフォルシア株式会社さんが提供(ありがとうございます！)
  • 次回 11/19 で一周年

Rust初心者がRay Tracer書いてみた / keisukefukudaさん

  • 前回も初心者、相変わらず初心者
  • Ray Tracer は楽しいので、新しい言語を練習するときに良い
  • Ray Tracing とは？
    • 3Dのオブジェクトを平面に描画する
    • ちゃんと計算する
    • オフラインで時間をかけて
    • アルゴリズム、プログラムは以外に簡単。コアのロジックは数行
    • 線形代数は知っている必要がある
  • なぜ Ray Tracing ？
    • 最初のプログラムが複雑だと無理
    • 数値をはけばいいだけ
    • こり始めるといくらでもこれる
    • 絵が出るので楽しい
  • Ray Tracing in One Weekend
    • C++のコードをrustで写経する
    • 3次元ベクトルを定義し、内積などのメソッドを定義
  • ハマりどころ
    • 演算子オーバロード。C++だと簡単
      • std::ops::Add トレイトを実装
      • + だが、参照を取らなければならない
    • 添字演算子
      • std::ops::Index トレイトを実装
      • c++ の const / non-const の実装の分け方がわからない
  • 今後の展望
    • 特殊な Ray Tracer 、 SIMD 化、 WASM で動かす

ネタが無いので盛り上がるプログラムを作った / てくのたのしーさん

  • タイトルを100倍にすると盛り上がる
  • Filmarks さんから映画タイトルをスクレイピング
  • scraper reqwest クレートを利用
  • 8万5千タイトル
  • うち、数字っぽいもの 6500タイトル
    • 漢数字は未対応
  • 第5位「Tokyo 200100/1000/2100 2200:3200-2200:4100」
  • 第4位「貞子300D 200」次元の暴力
    • 次元系は他にたくさんある
  • 第3位「青鬼 ver.200.0」
  • 第2位「裁判長！ここは懲役400年でどうすか」
  • 第1位「永遠の0」 0には何をかけても0でした
  • まとめ
    • 6,000 タイトルに目を通すのは大変
    • ネタがないのにLTに申し込んではいけない
  • 番外編: マイナス2100度、5200Hzのラヴソング
  • Q). このプログラムはどこかに公開されますか
    • A). PR投げつけられそうで怖いが、公開します

最近お仕事で使ったcrateの話 / yukiさん

  • crateとは？
    • rustは標準ライブラリが少なめで、それを補完するもの
  • Rust をどこで使った？ → ツール
    • 普段から Scala / Rust / C++ で作る
    • Scala はコンパイル遅い、Macでも動く、小さいと所有権とかではまらない
    • ツールはメンテ不要なので、導入しやすい
  • ansi_term
    • 修飾付きの文字を表示できるクレート
    • 斜体、256色
  • itertools
    • Scala にあるけど rust になかったやつ
    • イテレータに機能を追加するもの
    • chunks 決められた個数ずつに分割する
    • enumerate 添字をつける
    • cartesian_product デカルト積
  • scraper reqwest
    • reqwest で HTML を拾って、 scraper で解析
  • chrono
  • 10/26 Rust Tokyo があるので来てね
  • Q). itertools は並列実行は？
    • A). ぱっと見なさそうだったが、あるかも
  • Q). Jst は自分で定義しないと駄目？
    • A). FixedOffset でおーけー
  • Q). 誰かがメンテしているタイムゾーンは？
    • A). なさそう
  • Q). タイムゾーンは相互変換できるから木にしなくていいのでは？
    • A). はい
  • Q). DateTime<Local> と DateTime<Jst> の相互変換は？
    • A). 無理
  • Q). クレートはどう探しますか？
    • A). Awesome Rust を探す。更新が1年以内ならO.K.

Rustで10日でwebサービスつくった話 / ryusukefudaさん

  • 開発合宿で、未使用の技術でプロダクトを作っている
    • 去年は Go + Vue.js → プロダクトをリリース
    • 今年は Rust + web component を 4 名で
  • フレームワーク選定
    • actix-web VS rocket
    • HTTP2 のためにactix-web
  • DB選定
    • 使えるもの。MySQL
  • フロントバックエンドの通信
  • 他、 マイグレーションに diesel 、パッケージ管理に cargo
    • 選択肢がない
    • KVSはRedis
    • docker-compose で環境構築
  • 辛かったこと
    • 詰まる。詰まったときに救いがない
    • actix-web の API が苦しい。型指定など
    • actix と actix-web の棲み分けが不明
    • 通信処理。 future を使ったが、 tokio ？
    • Ruby/Goなら瞬殺できる実装を3hかかって性格が歪んだり
  • actix-cors actix-session actix-redis などを利用
  • 良かったこと
  • フロントの担当者は、WYSIWYG部分を作っていた
  • 予告: 次回はデプロイ編
    • デプロイに 50 分かかっている。ビルドが時間かかりすぎ
    • Cargo.toml をいじると時間がかかる
  • Q). 10日でfutureまで理解できるもの？？
    • A). 人間にはちょっと早い。コンパイルを通す作戦に出た。途中から理解を辞めた
  • Q). デプロイ時間がGoだと？
    • A). 5分か10分。Rustはキャッシュ使っても35分。安いプランなので。
      • ローカルの Docker for Mac で --release ビルドで6分くらい

What is std::sync::atomicについて / matsu7874

  • シングルスレッドではデータの更新は問題がない
  • マルチスレッドでは、書いている途中に読まれると、何が読まれるのか不明
  • 不可分にする、または、操作する数を 1 つにする
  • Atomic とは？
    • 書き込み途中に読まれない、読み込み途中に書かれない
  • std::sync::atomic Atomic型を提供する
    • Sync トレイトが実装されており、スレッド間共有が可能
    • Arc でラップして使う
  • Atomic 以外の方法
    • Mutex、 RWLock
    • 速度は "perormace comparison of mutex rwlock and atomic types in rust" というスライドを参照
    • Atomic が爆速
  • AtomicUsize 同士の比較をしたい
    • std::cmp::PartialEq トレイトを impl する必要がある
    • 自分で定義したトレイトまたは型しか impl できない
  • newtype パターンを使えば良い
    • struct Bar(Foo)
  • まとめ
    • スレッドでデータ共有するのであれば、専用の型が必要
    • Atomic が高速
    • new type パターンは便利

WebSocketで人生アガります / 宇宙ツイッタラーXさん

  • 最終的にはビットコインで人生がアガる予定（ライブコーディング）
  • main 関数を作る
  • bitFlyer API に rust サンプルがあるが、コンパイル通らない
  • struct Client
  • ws クレートの Handler トレイトを実装
  • on_open on_message を実装
  • connect 関数を利用。 Client 型で Sender 型を受け取って利用
  • 取引情報が欲しいので、 bord というチャネルを使う
  • on_open で "lightning_board_BTC_JPY" チャネルを "subscribe" するメッセージを send する
  • on_message は Message::Text を受け取った場合のみ定義する
  • 「皆さん、日常的にデシリアライズくらい毎日やってるわって感じでしょう」
  • serde::Deserialize で JSON をパース
    • JSONからコードを自動生成するサイトがあるらしい
  • 変なJSONも来ていてエラー
    • 「怒りの unwrap をしていたけど辞めましょう」
    • デシリアライズに成功したときのみ表示 → 成功
  • まとめ
    • リアルタイム取引は早いのがいい、 C++ は無理でしょう、 rust は適している

rustのcombineで入力されたトークンによる場合分け

技術

combine を使ったときに、例えば識別子のパース時に予約語を弾く方法。

最初は and_then を使うのかと思ったのだけど、 エラーの型指定がえらく面倒 だったので諦め。というか、なんか絶対違うだろうと思って別の方法を模索。

Parser のドキュメントに以下の例がある。これだ。

digit()
    .then(|d| {
        if d == '9' {
            value(9).left()
        }
        else {
            unexpected_any(d).message("Not a nine").right()
        }
    })

ということで、 then を使うと Parser を返す処理を書けるので、ここで unexpected_any を使って失敗させてやればよい。

ちょっとこのコードを見てぎょっとするのは left() と right() だが、これは if で分岐するパーサの戻り値が違うため。 rust ではよくみるやつだが、 combine のパーサコンビネータは Parser トレイトを持つメソッドごとの独自の型 Value<I, T> や Unexpected<I, T> を返す。ということで Either にまとめれば型を混ぜて1つにできてハッピーなのだが、次に、どっちを left にしてどっちを right にするのがいいのかという疑問が出てくる。

正解は実はどちらでもよくて、これはエラーを表す Either ではないので、 right が正常処理というような意味はない。どちらでもいいから、入っているパーサーを実行するだけである。実際、 Either の Parser トレイトの実装を見ると以下のようになっている。

impl<L, R> Parser for Either<L, R>
where
    L: Parser,
    R: Parser<Input = L::Input, Output = L::Output>,
{
    ..snip..
    fn parse_lazy(&mut self, input: &mut Self::Input) -> ConsumedResult<Self::Output, Self::Input> {
        match *self {
            Either::Left(ref mut x) => x.parse_lazy(input),
            Either::Right(ref mut x) => x.parse_lazy(input),
        }
    }
    ..snip..
}

R: Parser<Input = L::Input, Output = L::Output> の制約は、2つのパーサの入出力が揃っていないとまずいことを表す。

rust の publicsuffix は遅過ぎる

技術

rust で Public Suffix List を扱うクレートの速度が遅過ぎるので、パッチを書いた。最右部のラベル ( .jp .com など) でルールを区分けして、後は愚直に線形探索という方法だったので、そりゃあ遅すぎるよねって感じ。

github.com

実は Perl の Domain::PublicSuffix でも速度の問題にあたって書き直したことがあるのだけど、このときはドメインのバリデーションが重過ぎるのが原因で、 このコミット で解消されている 1 。 rust の publicsuffix でも バリデーション は比較的重いので、この点も改善できるのかもしれない。

ところで、今回の PR で一箇所気に入らないのが この部分 。ツリーを構築しながら潜るのに current 変数を子のノードを指すよう更新したいのだけど、子のノードを作るために可変参照が必要なので別の変数 cur に所有権を移してからじゃないと更新できない。ここをもうちょっとスマートに書く方法はないんだろうか。

  1. このコミットを自分で作ったわけではなくて、自分たちでスクラッチから書いたバージョンではバリデーションを外すなどした、という話。↩

今日は Roppongi.rs #1 の日です

技術

職場から近いので Roppoingi.rs に来ました。自分のためにメモを残しておきます。ハッシュタグは #roppongirs 。

Rustがいかにエンジニアの脳を楽にさせているかをC++初心者が語る〜関数篇〜 / @natsu_no_yuki さん

  • C++歴15年の初心者
    • rvalue reference, template特殊化などが使えるのは初心者らしい
    • rust歴は3日
  • プログラミングの歴史からrustの良さを考える
  • C言語: メモリ管理を何もしてくれない
    • プログラマが明示的にメモリを確保したり・・・ (C、C++のことです)
  • C++ と rust の比較
  • C++で関数呼び出しをすると、コピーされてコンストラクタが二回呼ばれる例
    • スタックにローカル変数、戻り先アドレス、引数を積む
    • 引数を積むために2回インスタンスが作られるので、無駄
    • よって、参照渡しをする
  • C++で関数の戻り値で二度コンストラクタが呼ばれる例
    • （処理系によるが）EAXレジスタへコピーする。よってコンストラクタが二回呼ばれる
    • 戻り値を参照にする → 開放されたメモリを参照してしまう
    • スタックに実体があるが、関数から戻るときに破棄されてしまう
    • コンパイルが通ってしまう。 C++ では気が付きにくいバグ
    • ヒープにデータを作る (演算子 new で作る) → 問題ない
    • bad_alloc exception メモリ不足。開放しなければならない ( delete )
  • delete をどうするか
    • 同じレイヤで開放するのが鉄則
    • destroyedXxx のような名前の関数を用意する
    • C++ を書いているひとは、この問題とずっと戦っている
  • rust の場合は、普通に返すだけで所有権が移るので問題ない
    • 脳が嬉しい → Rust いいね

なぜBlockchainはRustを選ぶのか / @jkcomment さん

  • Blockchain の話は多いけど、細かい話はしない
  • rust について
  • なぜ rust の知名度が低いのか
    • OSSプロジェクト、サービスが少ない
    • goは k8s とか。 rust の場合は、 Rust が一番
    • システム系はC言語一強
    • 学習コストが高い、難しそう
  • Blockchainのプロジェクトでは、rustの採用率が高い
  • Blockchainとは？
    • P2Pで動作する分散型大腸システム。ブロックを一定時間ごとに生成してチェーンに。ハッシュで暗号化
    • bitcoin, Polkadot, libra
    • C++: bitcoin, EOS, zilliqa / Go: Ethereum Klaytn Quorum
    • rust: Ethereum(Parity), Polkadot(Substrate) ..他多数
  • なぜrust？
    • 特に理由はない
    • blockchain そのものは、言語はなんでもよい
    • rust のプロジェクトも、理由は明確にしてない
  • それでも理由を考えてみると
      1. 性能
      1. Blockchain に必要なモジュールが用意されている
      2. Networking(P2P), Cryptography, Consensus, Storage などに関する処理が必要
  • P2P (Peer to Peer)
    • 対等なやり取り。オーバレイネットワーク。実現するために必要な機能が多い
    • Transport, Discovery, Peer Routing, NAT超え
    • libp2p
      • すべてのPJが採用しているわけでもないが、多くのPJで採用
      • もともとrustが一番いい実装だったが、今はgo
  • Cryptography / 791 crateも登録されている
  • wasm / WebAssembly
    • VMではなくwasmを使う流れになってきている
    • go/C# はランタイムが大きすぎ、 C/C++ はめんどう
    • rust は楽でバイナリも小さい。安全。
  • Substrate
    • Parity社が開発した Blockchain Framework (wordpress的なもの)
    • 簡単に独自の Blockchain が作れる
    • Substrate ベースのプロジェクトは増えている (zero-chain, Plasm, Edgeware, shasper, ChainX ...)
  • rust の悪い使い方
    • Substrate ... マクロ使い過ぎ、トレイト地獄、 match 地獄
    • マクロは展開後のコードでエラーが起きるのでわかりにくい
  • rustの使いみち
    • OSが作れる
    • Webアプリケーションも作れる (Rocket, Iron, actix-web)
    • フロントエンド開発 feat wasm
  • rustがいいと思う理由
    • (個人的に) OOPが好きじゃない
    • 速さ、堅牢さは正義
  • rustで苦労した点
  • まとめ
    • ものづくりは楽しむべき。rustで楽しむ、Blockchainも楽しい

(LT) rustで実装されたLibra Move言語とは

  • Libra : FB の金融プラットフォーム。2019年6月
    • BFTモデルの Libra Blockchain が基盤
    • 組んでいるメンバーが強い
  • Move : Libra 上でスマートコントラクトを書く言語
    • 安全とセキュリティを重視
  • バイトコードを利用 : bytecode verifier でチェックするので安全
  • アセットをオープンシステムに乗せるの難しさ
    • Scarcity / 生み出せない、複製できない
    • Access control / 所有者のみがコントロールできる
  • block chain言語の問題
    • 資産をInteger で表現、型がない、エラーハンドリング
    • Scarcityの責任が開発者に
    • Access control が柔軟じゃない
  • Move での解決策
    • first-class assets: integer 以外を利用、コピーと履きを明示 ( copy/move )
    • flexibility: modules/resources/proceture (クラス、オブジェクト、メソッド)
    • safety : bytecode verifier
    • verifiability
      • 動的ディスパッチの禁止（コールグラフがたんじゅん、解析がしやすい）
      • mutability の制限 (value の変更はrefernce 経由のみ。所有権システムを利用)
      • モジュール化
  • 開発のエコシステムはまだこれから
    • Libra Blockchain へデプロイはできない
    • ドキュメントや開発ツールがない。
    • Collection や Generics は今はない