けいぞうのメモ帳

言語設計のお勉強

一人ソフトウェアの基礎勉強会 草案

経緯

やり方

  • twitterハッシュタグ #self_taught_sf に色々書いていく。
  • ある程度まとまったらtogetterにでもまとめる
  • 作ったものはブログにまとめる

以下なんか合ったらリンクを貼る

haskellでbinaryにread&write

binary packageのGet/Put Monadを使いBinary classにgetとputを実装することでData.ByteString.Lazy.Internal.ByteStringとデータ構造を変換する事ができる。

ネットワークプロトコルフォーマットパーサの実装の参考として、http2 packageを覗いた。 unsafeperfomeIOを使ってWord8をPtr aとして扱っていた。おそらくこれは高速化のためだと思うのでベンチマークをあとで取ることにする。

gistaa91f312fdf7acb5c8a0e58a558ca8eb

haskellでUDP

間違えてTCPのサンプルを置いていたから修正した。

UDP

user datagram protocol.

https://www.ietf.org/rfc/rfc768.txt

HeaderのadressはIPv6時にはちゃんと128bitに変わる。

haskell network

Network.Socket.ByteString

俗に言うhaskellで書くC言語のコードである。 simpleにTCPでつなげるなら、networkのNetwork.Socket.ByteStringのサンプルが良い。

UDP

[Haskell-cafe] UDP client/server

をforkしないコードにして置いた。

stackでbuildできるようにした

gistb09bbfd263b61fa180256d14c41810e6

QUIC追っかけ日記01

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

次のお題

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