けいぞうのメモ帳

言語設計のお勉強

QUIC追っかけ日記01

QUIC QUIC追っかけ日記

QUICについて

Googleが主導しているHTTP+TLS+TCPに変わる新たなプロトコル。
アップグレードされたHTTPにたいしてそのTLS+TCPの部分を効率よく通信するために策定されている。 まだインターネットドラフト段階で、

https://tools.ietf.org/html/draft-ietf-quic-transport-00　がJune 1, 2017まで議論される様子。
このrevisionから更新を追いかけていきつつQUICについて記述する。

公開して、意図を訂正してもらう目的が大きいため、なんらかの参照にするのは望ましくない。

改善点

よく取り上げられる順番で書いていく。

Head of Line blocking (HOL blocking)

Head-of-line blocking - Wikipedia

Head of Line Blocking - High Performance Web 2015 - Qiita

HTTP/1.X or TCPの通信は並列化されていないため、複数のストリームを一つのコネクションを用いて流す場合、
直列に送信するため先行するストリームが重かったり、輻輳が発生したりすると、送信時間や再送時間分だけ後続のストリームが 到達する時間が遅くなる。

HTTP1.1のRFCの邦訳

https://triple-underscore.github.io/RFC7230-ja.html#section-6.4

によると、

複数接続は、概して， “head-of-line blocking” 問題 — ［ サーバ側に重い処理を要したり, 巨大なペイロードを持つ ］ような要請が、同じ接続上の後続の要請を阻むこと — を避けるために利用される。 しかしながら、接続のそれぞれは，サーバリソースを消費する。 更には、複数の接続が利用された場合，混雑したネットワークに，望ましくない副作用をもたらし得る。

とあるため、HTTP1.1においてもTCPのコネクションを複数接続させることでHead of Line Blockingを避ける場合もある。 ただし、そういった場合にはTCPのコネクションを複数もつリソースだけ余分なリソースが消費される。増やしすぎるとTCPのコネクションのリソース消費と並列化による高速化が釣り合わなくなるため、 TCPのコネクションをむやみに増やせばいいというものではない。例えば、chromeは6本の固定値である。

HTTP/2そしてQUICにおいては一つのコネクション上でストリームが並列に送信され、輻輳制御もストリームごとに行われるため、Head of Line Blockingがそれぞれのレイヤで発生しなくなる。 HTTP/2 over QUICを用いれば、上記の理由によるHead of Line Blockingは発生しなくなる。

TLS + TCP

TCPでスリーウェイハンドシェイク、TLSでセッション鍵交換を行ってから、HTTP/2 over TLS over TCPの通信が行われる。
これを冗長とし0RTT つまり要求してすぐに通信が始まるようにQUICは設計される予定だ。 ID 0のストリームでコネクション要求とTLS接続に用いる情報、clientのQUIC versionをサーバに渡し、サーバのQUIC versionの比較とデータの送受信を始める。

QUIC Wire Layout Specification - Google ドキュメント

FEC

前方誤り訂正を用いて、一割程度の損失があった場合でも回復できるようにしていたらしい。

QUICはXORベースのFECをやめるらしい - あすのかぜ

QUIC FEC v1 - Google ドキュメント

chrome-devとyoutubeを用いた検証では芳しくない結果が出たためFECの仕様を改めて決める。

rust langでturing machineもどき

github.com

rustの線形型やリージョン推論をすごいすごい言っていたりするのにコードを書いていないのは良くないので、 rust langの練習用にチューリングマシンエミュレータのようなものを作った。

あまり説明する気のない説明

状態Sと、記号と空白記号の集合Lをenumを使った代数的データ構造で定義し、
関数stepをs ∈ Sとテープ上の l ∈ Lによって状態を遷移させる遷移関数とする。sとlはmatch syntaxで判別する。
テープは構造体で表し、Vectorと現在の参照位置をusizeで持った。

enum L {
    Blank,
    X,
    One,
    Zero,
}


let mut tape = [L::Blank, L::One, L::Zero, L::Zero, L::One, L::Blank ];

これは 1001 を表す

{0,1}で表される単語wとその反転reverse w = w'が並んでいるww'なテープを得たときのみState::start()がtrueを返す。 雰囲気はテストコードを見て感じ取って欲しい。

$cargo test
or 
$cargo run

で9つのテストコードかmain関数が走るようになっている。

ちょっと大変だったこと

テープの表現は

struct State<'a> {
    tape: &'a mut Vec<L>,
    ptr: usize,
}

と書いている。
Vectorで無限長のテープの表現、ptrで今の参照位置だ。変数名ptrなのにvalueなのが気持ち悪いとか言わないで欲しい。 しばらくの間は

struct State<'a> {
    tape: &'a Vec<L>,
    ptr: usize,
}

としていたのだけれど、これだと

impl<a'> State<'a>{

  fn assign(&mut self, n : usize, v : L) {
     let ref mut tape = self.tape;
      tape[n] =  v;
  }

}

のような関数はコンパイルエラー。なぜかというと、selfはmutableでborrowingしているのにVectorはimmutableになって変更できないため。
構造体内の参照はmutable or immutableを選べるとはしらなかった。 あとlet ref mut tape = sefl.tape.clone()でvectorの参照をclone()してくれると思って書いていたら値も丸ごとcloneしていた。

fn f(v : &mut Vec<usize>){                                  
    let mut vec = v.clone();                                
    vec[1] = 1;                                             
}

fn main() {
    let mut vec : Vec<usize> = vec![0,0,0,0];
    f(&mut vec);
    for v in &vec {
    println!("{}", v);
    }
}

--出力
0
0
0
0

次のお題

マークアップ言語パーサを書く。

mrbox -- mruby binary manager -- を改めて紹介する

mruby advent calendarで書いたmrubyのバイナリを管理するmruby-cli wareがとりあえず困らない程度に実装出来たのでご紹介します。

mruby

以前書いた記事を参照ください。mruby1.0.0だか1.1.0の頃の話ですが変わったところはないと思います。

keizobookman.hatenablog.com

動機

mrubyを使って開発をしているときに、必要なgemを組み込んだmrubyの実行バイナリが必要になります。 しかし、mrubyのライブラリはstatic linkでgemを加えたいときは毎回リビルドが必要になります。 さらに、開発・テスト・本番で組み込みたいgemが違う場合は結構あり、それを手元でよしなにする方法がありませんでした。

mrbox

github.com

そこで実装したのがmrboxです。mruby sandboxの略のつもりで名前をつけました。"えむるぼっくす"か"えむるおーえっくす"かは各自好きに読んでください。
MacとArch Linuxを移動しながら開発していたのでそれらでの挙動はある程度保証できます。Windowsはビルドが出来なかったのでまだサポートしていません。
手持ちのWindows機は開発環境が整っていないのでv1.5とかv2.0とかでの対応になるでしょう。

mrboxを実行するとhelpが出力されます。

$mrbox 
Usage: mrbox [mrbox options] [command] [mrbox options] -- [mruby option]
Author:Kouichi Nakanishi(keizo042)
mruby binary sandbox manager.

example:
---

$mrbox build --name hello
$mrbox mruby --name hello -- -e 'puts "Hello mrbox World!"'

---

At first, you must execute 'mrbox setup'. 
by default, it use default mruby repository.
if you specifiy option '--name', download mruby repo into local  and manage it as this name.

options
--file (-f)     ---   using specific mruby's build_config.rb
--name (-n)     ---   nameing mruby binary, it use when build,clean,mruby.mirb,mrbc

subcommands:
build -- build mruby binary.
clean -- clean up mruby repo
help -- print help and version
init -- intialize local mrbox sandbox
show -- show your named mruby binaries
setup -- setup global mrbox's mruby sandbox
update -- update mruby repo
mruby -- use mruby
mirb -- use mirb
mrbc -- use mrbc
mruby_strip -- use mruby-strip
edit -- edit build_config.rb
config -- config mrbox

使い方は上記のexampleにあるように、--nameでインストールするmrubyにネームタグをつけて、
--fileで使用するbuild_config.rbを指定します。
実行するときは、--nameでつけたネームタグを用いてそのmrubyリポジトリを呼び出しbuild,update,executeなどを行います。
オプションは -- で区切られ、--以前はmrbox, -- よりあとは実行するバイナリに渡されます。

mrbox setupコマンドはデフォルトのmrubyレポジトリを落としてくるなどの環境のイニシャライズで、
~/,mrboxディレクトリになんやかんやを用意するコマンドです。
今はディレクトリを掘っているだけですが、今後の機能拡張に伴いいろいろぶち込むことを想定しています。

$mrbox setup
$mrbox build --name hello
$mrbox mruby --name hello -- -e 'puts "Hello mrbox World!"'

一度buildしたプロジェクトのbuild_config.rbはもう一度build --name helloなどをするか

$mrbox edit --name hello

とすることで編集が可能です。
mrbox edit helloでも編集出来るようにもしようと考えています。

TODO

  • stdin/out/errの取り回し
  • bovi/mgem対応
  • gembox対応
  • mrbox configコマンド実装
  • mrbox initコマンド実装
  • mrbox cleanをmrbox rmにrenameして改めてmrbox cleanを実装
  • サブコマンドオプション整備
  • Windows対応

bovi/mgemを呼び出してmgem configのbuild_config.rbを用いることや、mruby-onig-regexpの関係でビルドから外しているWindowsビルド整備や、
internalで呼び出しているrm -rf などをmrubyに移植したり(mruby-fileutilsの整備が必要)、gitコマンドを叩いているところをmruby-gitとしてexportしたりなどを考えています。

とりあえず困っていたmrubyバイナリの管理は解消されていい感じになりました。
mruby advent calendarの記事でも宣言したように2019/1/31をめどにv1.0.0をリリースし破壊的変更を控えるようにします。
それまではインターフェースをガンガン破壊的に変更していくつもりなので人柱力が高いひとのご協力をお願いします。

mrubyの実行バイナリをbuild_config.rbごとにswitchしたい話

このエントリーはmruby Advent Calendar 2016 - Qiita の7日目として書かれました。

昨日はyharaさんの 細かすぎて見つからなかったmrubyの非互換 - NaCl非公式ブログ でした。 細かいところを詰めていく技術はぜひ見習いたいものです。

あらすじ

mrubyはライブラリであるmrbgemをstatic linkして使うため新しいgemを使うたびにリビルドが必要になります。
僕は普段、作業ディレクトリごとにmrubyのrepoを拾って来て作業しているのですが、少々かったるいもので、 開発中にbuild_config.rbが異なるmrubyバイナリを自由に変更できないかなーと思うときがありました。
例えば

  • mruby-mtestを組み込んでいる or いない。
  • mruby-json or mruby-iijson or mruby-pjson 違い
  • 正規表現ライブラリ違い

あたりです。 なのでmrubyバイナリを管理するCLIを実装しています。 Goで書くか迷ったのですが、言語のエコシステムはその言語で作りたい点からmruby-cliを用いています。

github.com

まだ全然動かない。ごめんね。 今週末には動くようにしておくので...

用例

$mrbox --name sample --file build_config.rb build 
$mrbox -n sample mruby sample.rb

とするとbuild済みmrubyバイナリを呼び出してsample.rbを実行するようにする予定です。

雑記

rubyで言えばbundler、仕組みはhaskellのstackを大いに参考しています。 haskellのstackはコンパイラのインストールもマネージャーの方で管理しているのでそのへんの参考とします。

コマンドの実行時にmrubyバイナリを指定する方法はどうしようかとか、名前がダサいから絶対に変えようとか、
mrbenvって名前をつけたかったけどrbenvとサブコマンドを揃える気はさらさらないから候補から外したとか
色々ありますが、来年1/31日をめどにv1.0.0にするつもりなのでその日までは破壊的な変更があってもお目こぼしください。

なにかご意見がありましたらブコメ、github issue、ツイッターあたりに書いておいていただけると読みやすくて助かります。

GitHub - qtkmz/mrb: command line tool for mruby とか [GitHub - bovi/mgem: A program to manage GEMs in mruby にpull requestしてしまうのも一つの形だと思うので、そのへんも含めてご意見ください。

明日のmruby アドベントカレンダーの方は絶賛募集中です

http://qiita.com/advent-calendar/2016/mruby

pi calclusを学ぶにあたって参照したドキュメントとその紹介その一

動機

ぼくはgopherなのでgorutine/channelを用いたプログラミングが好きだ。
ついでに非同期、並行プログラミングも好ましいもので、haskellやrustなんかの手法を知ってにやにやしている。
それらにともなって背景とされるhoareのCSPとその拡張のpi calclusについて調べて遊んでいる。
なんか寄り道をしてタネンバウムの分散システム本をなめたりTaPL再読なんかもしているが、
それはそれとして様々なドキュメントを参照した。
それぞれを紹介することで自分への理解度を試したいと思う。
言ってしまえば、ぼくの愚痴であり、自習ノートである。
ついては、ぼくの紹介が不十分であったり間違っていたりした場合には、
ブクマコメやツイッターなどでdisっていただけるとぼくの勉強の一助となってありがたい。 ついでに、間違った情報を界隈に広めずに済む利点がある。ご協力いただける方々には感謝を捧げたい。

以下紹介

初歩の理解のために

和訳版TaPL監修やmini-camlのsumii先生(たぶん)のところのWebにあるπ計算の紹介記事。
true/falseの定義や再帰的な処理に関しての記述を簡単に書いてある。
十全な学習にはならないが導入としてわかりやすい。
encoding: ISO-2022-JPじゃないと読めないため要注意

大学の諸先生方には口を酸っぱくして「wikipediaは参考にするな」と教えられたが
それはそれとして和訳本が見つからず、一単語しか知らない時にwikipediaのreferenceとlinkを参考にするのは大変手っ取り早い。 後に述べるMilnerの原論文のsummary的なものに仕上がっている。また、応用についてのrefをたやすく得ることができる。
spi calculus, ambient calclus, Calculi of Sequential Process, Algebra of Sequential System などだ。

pi calculusはCSPの拡張だからprocess algebraの歴史をさらっておくと理解が進むような気がする。 process algebraのサーベイ論文を読むことにした。
意味論の登場からbetri netにつながり、CCSやCSP、ASPへの経緯。またpi calclusへの拡張のモチベーションが分かるような気がする。

大本命、pi calculusの原論文。この後何回かの拡張(チャネルの可変引数とか)がされているため、後発の資料に書いてある定義と異なる部分が多々ある。
あと、記法に関しても多くの方言が存在するようだ。
part 1とpart 2で構成されていてpart 1は最小のにgrammer(と僅かなsyntax sugar)と等価性、双模倣性に関する簡単な記述と数多くの具体例(encoding to lambda calculus, tupple etcetc)、
part 2は等価性と双模倣性の関係や、強い双模倣性と弱い双模倣性に関する詳しい記述がある。
双模倣性は余再帰を用いてよしなにするらしいという点とTaPL21章に詳しいと聴くがちゃんと読んでいない。

大学の図書館にあったので借りて読んでみた。日本語で書いてあり、大変わかりやすく、前提なしでも程度理解できる。 食事する哲学者の例えを用いていたりJCSPを用いて実装からCSPを用いた並列と検証について記述している。
Javaが読めなかったので半分くらいしか読んでないが、実用における用途は大体書いてあってちょっと知りたいだけなら これよんでおしまいで十分のようだ。

next step

可変長の引数を取るプロセスへの拡張。 Milnerの原論文でプロセスに多変数を束縛する構文が備えられていた。
複数の経路を受け取ることもできるわけだし、この構文がそのまま可変長引数に当たると思うので何故わざわざ拡張しなくてはいけないか。
自分の理解は
間違っている事に気がついたのであとで書き直す

単純な型付きpi calculusについてのスライド。形式的定義が書いてあるので、どのような定義が与えられるのか参考にした。 このあたりで一度TaPLを読み返し単純型付きラムダ計算との比較などをすると面白い。

conclusion

pi calculus、ひいてはCSPさらにはプロセス代数にまつわるドキュメントを参照として並べた。大変お粗末なものである。
形式的な定義を理解しその意味を知ることはより良い並行性、非同期性の手法を考えるのに意味があるんじゃないかなと思う。
pi calculus特有の型システムの存在しているのかだとかASPやspi calculusにanbient calculus
あまり関係ないがbetri netやactor modelなどの比較ドキュメントなども知りたいので探していきたいと思う。
プロセス間の通信経路を持つ（そのような抽象化がされている）言語でregion infferenceは使えるのかとかgorutineのGC実装にどれくらいCSPの影響あるのかなども気になるところだ。
multithread programmingにおけるGCが使えるような気がするからgorutineでのGCはそんなにプロセス代数を背景にしていないような気もする。 グリーンスレッドに関する研究開発はそれは昔からあったであろうし。
線形型をpi calculusに落としこんだらメモリ開放もよしなにできるとかないだろうか。

こんなアホなことやってないで、留年生らしく単位とって進級しろと怒る学友の姿が目に浮かびすぎてつらい。
だいがくおもんないなぁ

appendix

コレも読んどけ
* Type and Programming language
邦訳"型システム入門" 通称TaPL ある程度の予備知識として単純型付きラムダ計算についての理解があるとpi calculusの動機についてインフォーマルな理解ができると思う。
5,6章辺りまで、深く追いかけたとしても10章まで読めばpi calculusへの導入としては十分に思える。

  • Advanced Topic in Type and Programming language
    上記"型システム入門"の発展版 多分通称はATTaPL
    ただし僕の周りにこれを読んだことがある人がいないのでなんて呼ばれているかは分からない。