Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

java.nio を使って簡単な HTTP サーバーを作ってみる: ノンブロッキングなHTTP サーバー

先日,LINE の Meetup in Tokyo #28 に参加してきました.そのときに,Netty を作っている Apple の方が話をしていたのですが,彼の話す ByteBufferChannelSelector などの単語がよくわからず,帰ってから気になって調べてみました.そこで,java.nio (New I/O)というパッケージが引っかかりました.どうやら,TCPUDP を用いた各種 I/O を扱っているライブラリのようでした.

ドキュメントなどを読んでみると,以前 HTTP サーバーを作ったときのように,java.nio を使った HTTP サーバーを作れそうだったので実際に作ってみました.Netty も nio をベースに作られています

今回の記事では,java.nio の主要な概念を解説すると同時に,その裏側にある「ノンブロッキング I/O (Non-blocking I/O)」についても簡単に整理をしたいと思います.そして,それらを利用して GET リクエストに対してレスポンスを返す簡単な HTTP サーバーを実装します.

ノンブロッキングは近年Web 業界でも注目の概念であり,私が作っている広告配信の RTB サーバーでも,ノンブロッキングを選択するかどうかでスループットとレイテンシに影響を与えることがあるくらい重要な概念です.もちろん,その分実装はより複雑になり,理解する必要のあることも多いですが.

なお,HTTP サーバーの方の実装は見よう見まねで適当に行ったものなので,間違っている部分や改善点がある場合は,ぜひ PR を送っていただけると嬉しく思います.また,HTTP サーバーの構築に関係のない概念やクラスなどについては一切説明を省いていますので,あらかじめご了承ください.

目次

java.nio とは?

java.nio (以下,nio と略記します) は,JDK 1.4 から導入されたより高機能な IO を提供する Java のパッケージです.通常の java.io と比べると複雑ですが,高機能な I/O を行うことができます.

java.io は,バイトストリーム (byte streams) や文字列ストリーム (character streams) を使用するストリーム指向の I/O でした.一方で java.nio は,チャネル (channels) とバッファ (buffers) という概念を用いて I/O を行います.read/write の際,常にチャネルにバッファを送ることでやり取りします.チャネルは,バッファに対して read/write を非同期で行うことのできるものです.

チャネルは1つのスレッドに対して複数立てることができます.スレッドの起動や切り替えは,OS にとってはなかなか負荷のかかる作業であり,それをできるだけ発生させないようにできる点でチャネルは優れています.後述するように,1つのスレッド内に生成されたチャネルは,セレクタ (selectors) によって監視・管理されています.

バッファは,read/write できるメモリブロックを表現したものです.データをある程度まとめて入れておくことのできる存在です.nio では,Buffer をラップしたオブジェクトを用いて,メモリブロックに対する操作を簡単に行うことができるようになっています.詳しくは後述します.

ブロッキング・ノンブロッキングとは?

「ノンブロッキング(non-blocking)」という言葉は「非同期(asynchronous)」という言葉と似たような文脈で用いられることが多く,海外のドキュメントを読んでいても意図的なのか無意識なのか,混同して使用している例が多々見受けられました.

また,システムコール側から理解しようと strace するなどして追ってはみたのですが,nio では sendto が呼び出されているようだということまでしかわかっておらず [*1],確信をもてませんでした.

よく言われる話として紹介しておくと,read あるいは writeシステムコールにノンブロッキング用のオプションをつけて実行すると,ノンブロッキングかつ同期の I/O を行うことができます.また,POSIXaio というシステムコールも存在しており,こちらは実行するとノンブロッキングかつ非同期な I/O を行うことができます.

詳しい解説は日本語でいくつか記事が書かれているようですので,そちらを参考にしていただくと雰囲気がつかめるかとは思います (この件はまた別の記事にしたいと思います).

nio 利用するにあたって,さしあたりブロッキング/ノンブロッキングのざっくりした理解をするならば,

  • ブロッキングでは,read/write をすべて完了するまで,スレッドは別の処理を行うことができない.
  • ノンブロッキングにすると,read/write をすべて完了していなくても,スレッドは次の処理に移っていくことができる.

の2点をおさえておけばいいと思います.nio は,1スレッド内で複数の処理をセレクタ・チャネルを用いて走らせることに重きを置いていますので,スレッドをブロックしてしまうとそれがスループットの低下にそのままつながってしまいます.それを回避するために,ノンブロッキングという処理待ちの要らない仕組みを導入したのだ,くらいの理解で初歩的なところは問題ないでしょう.[*2]

ノンブロッキング I/O を行うことによりスレッドの処理の待ちが発生しにくくなるため,大量のアクセスが一気に来た場合でもスループットを落とさずに対応することができます.1つのスレッドがより効率よく多くの処理をさばくことができるようになるため,メモリの使用量が全体的に減ります.これは大きな利点です.

HTTP サーバーを作る

前置きがかなり長くなってしまいましたが,一通り nio の概要とノンブロッキングについて理解したところで実際に HTTP サーバーを作っていきましょう.今回は,nio のうち次のクラスを利用して HTTP サーバーを作成します.

大まかな HTTP サーバーの構成

とても簡易的な HTTP サーバーは,次の手順を踏むことで実装できます.

  • TCP ソケットなどを通じて,HTTP リクエストをバイトストリームを経由して受け取る.
  • リクエストの中身をパースして,HTTP サーバー内部で取扱可能な形にする (Request クラスを作るなどして扱うことが多いです).
  • メソッドやパスをハンドルする.
  • ハンドルしたものを Response クラスに詰めるなどする.
  • HTTP レスポンスをバイトストリームを経由して返す.

さて,今回は /hello というパスに対して GET を行うと,「Hello, NioHttpServer!」という文字列を返すだけのシンプルな HTTP サーバーを作成します.また,実装の大体はこちらのスライドを参考に作っているので,ご覧になると処理の詳細がわかるかと思います.

ソースコード

github.com

ちなみに上記リポジトリには2つの HTTP サーバーが用意してあります.NioHttpServer というクラスが java.nio を使ったサーバーで,HttpServer というクラスは java.io を使ったサーバーです.2つの間で処理がどのように異なるかの比較にどうぞ.

実際に使用したクラスの説明

nio には,ここにあげるもの以外にも FileChannel などさまざまな API が提供されていますが,今回は必要最低限に絞ってまとめておきます.

  • Selector: 上述したように,複数チャネルを1つのスレッド下で扱えるようにします.セレクタは生成されたすべてのチャネルを管理しており,チャネルを利用する際はこのセレクタにアクセスして取得してから利用します.
  • ServerSocketChannel: クライアントからやってくる TCP を受け付けます.
  • SocketChannel: TCP ネットワークソケットを経由してデータの読み書きを行います.ServerSocketChannel だけだと読み書きができません.なので,ServerSocketChannel#socket を使って SocketChannel を取得してから read/write を行います.
  • ByteBuffer: チャネルに渡すバッファの正体です.指定した領域をヒープに確保して,チャネルに送ることで read/write することができます.java.io でいうところの,byte[] です.

Selector, ServerSocketChannel, SocketChannel

セレクタは,自身に複数のチャネルを登録できます.これによって,1つのスレッド内で複数チャネルの処理を実行することができます.セレクタはどのようなチャネルを登録しているかについて, SelectionKey をキーとして内部的に保持しており,登録したチャネルを取り出す際には SelectionKey をイテレートすることで取得できます.

スレッド,セレクタ,チャネルの関係性については次の図のように整理することができるでしょう.

f:id:yuk1tyd:20180309233545p:plain

Selector#open することによって,セレクタを生成することができます.この生成したセレクタに対してチャネルを登録することで,チャネルを取扱可能な状態にします.

ServerSocketChannel ならびに SocketChannel はチャネルを表現するクラスです.これらは SelectableChannel クラスを拡張しており,SelectableChannel#register を呼び出すことによって,セレクタにチャネルを登録できます.

またセレクタに登録する際には,そのチャネルの状態を保存しておきます.下記のような状態を保存することができます.

  • SelectionKey.OP_ACCEPT: チャネルがクライアントからの接続を受け入れ可能.
  • SelectionKey.OP_CONNECT: クライアント側として使用した場合に,クライアントがサーバー (のチャネル) に対して接続可能.
  • SelectionKey.OP_READ: そのサーバー (チャネル) が読み込み処理を行う準備ができている.
  • SelectionKey.OP_WRITE: そのサーバー (チャネル) が書き込み処理を行う準備ができている.

最後に, ServerSocketChannel#configureBlockingfalse にすることで,ノンブロッキング I/O を可能にします.

ServerSocketChannel serverSocketChannel = null;
try {
  serverSocketChannel = ServerSocketChannel.open();
  serverSocketChannel.socket().bind(inetSocketAddress);
  // false を設定することでノンブロッキングにします
  serverSocketChannel.configureBlocking(false);
  // チャネルへ状態を登録します
  serverSocketChannel.register(selector, SelectionKey.OP_ACCEPT);

  (...)
} catch (IOException err) {
  LOGGER.error(err.getMessage());
  err.printStackTrace();
} finally {
  try {
    destroy(serverSocketChannel);
  } catch (NioHttpServerException err) {
    (...)
  }
}

セレクタからチャネルを取り出す際には,セレクタが保持しているキーの一覧をイテレートして取り出します.Selector#selectedKeys を用いることで,保持しているキーの取り出しを行います.具体的には,次のように実装することができます.

try {
  while (selector.select() > 0) {
    for (Iterator iter = selector.selectedKeys().iterator(); iter.hasNext(); ) {
      SelectionKey key = (SelectionKey) iter.next();
      iter.remove();

      (...)
    }
  }
} catch (IOException err) {
  (...)
}

read/write についても,SocketChannel#read あるいは SocketChannel#write で行うことができます.java.io の場合は Socket クラスの InputStream や OutputStream を取得してから行いましたが, nio の場合は先の2つで処理が完結していまいます.なお,read/write には後述する ByteBuffer を使用します.コードの例は下記です.

ByteBuffer buf = ByteBuffer.allocate(1024);
socketChannel.read(buf);
buf.flip();

サンプルコードの置いてある GitHub 上では,read/write をこの箇所で行っています.ご覧いただくとさらに理解が進むかもしれません.

ここまででお分かりの通り,java.io で HTTP サーバーを実装する場合と大きく異なるのは ByteBuffer の存在です.java.io の場合は,プリミティブなバイト配列を InputStream/OutputStream に渡すことでやり取りを行っていましたが,nio では ByteBuffer を用いてやり取りを行います.ByteBuffer は触ってみて少し癖があると思ったので,次の節で簡単に解説を加えます.

ByteBuffer

通常の業務アプリケーションを作っている範囲内では,ByteBuffer を目にすることはほとんどないでしょう.実際,私も Netty のカンファレンスで聞くまでは知りもしませんでした.ByteBuffer低レベルな部分を少しいじることでプログラムを高速化したい場合に用いることがあるようです.

byte[] を使う java.io と何が違うか?という点についてですが,ByteBuffer はバッファ内のデータを前後させることができます.java.io のバッファストリームは読み込みが終わるまでデータの操作を行うことはできませんが,ByteBuffer は読み込み中であってもそのような操作に対して柔軟に対応できる点で異なります.[*3]

ByteBuffer は次の要素によって成り立っています.

  • capacity: バッファが格納可能なサイズの上限値です.
  • limit: バッファの書き込みモード時に使用するもので,どのくらいのデータを書き込み可能か,その上限を決定します.書き込みモードでは capacity と同値になります.
  • position: バッファがどの位置にいるかを示します.書き込みモードの場合は最初は0ですが,書き込みが起こると position は異動します.読み込みモードの場合,flip() を使ってモードの変更を行うと position は0にリセットされます.

ByteBuffer にはいくつかの操作が存在していて,それらを組み合わせることでバッファの位置を調整できます.今回使用したのは次の2つです.

  • ByteBuffer#flip: バッファのモードを,書き込みモードから読み込みモードに変更します.また,その際に position を0に戻し,limit を position と同じ位置に設定し直します.
  • ByteBuffer#clear: position を0にし,limit を capacity と同じ位置に設定します.

その他にも,

  • ByteBuffer#rewind: position を0にします.データを再度読み込み可能にします.
  • ByteBuffer#compact: データの追加書き込みを可能にします.

などの操作があります.

また,ByteBuffer#allocateDirect メソッドを用いることにより,新しいメモリ領域をマシンネイティブに確保することもできる機能ももっています. [*4]

あとは,作成した ByteBuffer をチャネルの read/write に流し込むことでバッファへの read/write を行うことができます.こうして,HTTP リクエスト/レスポンスを返すことができるようになりました.

まとめ

ノンブロッキングを書こうとすると,それなりに理解するべき内容も多く学習コストも高いです.が,普段の Web フレームワークでは,フレームワーク側がその部分を隠蔽して操作しなくていいようにしているため,ほとんど意識することがないというのが実情です.私も Twitter 社が作っている Netty を基盤とした RPC フレームワークの Finagle を仕事上使っています.その際もやはり,ByteBuffer を目にすることはほとんどありません.

HTTP サーバーそのものは比較的簡単に作ることができ,ネットワークプログラミングの勉強のいい練習になるのでオススメです.今回はソースコードの解説をそこまでしませんでしたが,読んでみると, GET は案外単純な実装で実現できるのだ,ということがわかるかと思います.

今後の勉強の展望

  • AsynchronousSocketChannel のような非同期かつノンブロッキングな処理を扱えるクラスもあるみたいなので,時間を見つけて似たように HTTP サーバー作りたい.
  • Netty を触って,Netty に関する記事も書きたい.
  • ノンブロッキング時に呼び出されるシステムコールについても整理する.

*1:しかも TCP をやったつもりなので,このシステムコールが出るのはちょっとおかしい?

*2:興味がある方は上記の記事などをご覧いただくか,『詳解UNIXプログラミング』の該当のページを紐解くのもいいと思います.C 言語を使って実際にシステムコールを呼び出しながら実装を行うと,より理解が深まるかと思います.

詳解UNIXプログラミング 第3版

詳解UNIXプログラミング 第3版

*3:InputStream と OutputStream との比較を考えてみてください.

*4:ただ Netty の人曰く,より速度を向上させるためにマシンネイティブのメモリ領域を使うことをやりたいものの,ByteBuffer を用いるのはなかなかコストのかかる処理とのことです.allocateDirect が高コストなんですね.なので,sun.misc.Unsafe を使ってみたみたいです.

Rust の lang_item について

lang_item とは具体的には rustc の下記の箇所で設定されている言語固有のアイテムのことを指しています。また、#[lang = "<lang_item_name>"] アトリビュートを使用することで、その lang_item の実装を書き換えてしまうことができます。

lang_item の一覧: rust/lang_items.rs at 1ca100d0428985f916eea153886762bed3909771 · rust-lang/rust · GitHub

公式ドキュメントによると、rustc にはいくつかのカスタマイズ可能な機能があり、それを #[lang = "<lang_item_name>"] を使って関数にマーキングすることによって、その機能はこの関数によってカスタマイズ済みであるということを伝えるためのアトリビュートとのことです。

通常のプログラミング時にこの機能を使用することはほとんどないでしょう。Rust を使って Web サービスを作っている間や、Rust のライブラリを使ってコンパイラを作っている以上は、この機能を使用することはほぼないと思います。しかし、OS を作る際には話は別で、たとえば OS 用のプログラムのエントリポイントを変更したいなどの場合にこの機能を使用します。

代表例としては、先ほど紹介したリンクの中に startpanic_fmt というものがあります。start は、その名の通りエントリポイントの修正をかけることができます。イメージ的には main 関数の箇所を変えられるということです。panic_fmt は、Rust コード上で panic が発生した際にその挙動を制御することができます。

具体的な使用例に関するイメージがあまり湧いていませんが、サンプルコードを元に lang_item についての理解を深めていきましょう :) ちなみにこちらの公式ドキュメントから直接引っ張ってきています。

#![feature(lang_items, core_intrinsics)]
#![feature(start)]
#![no_std]
#![no_main]
use core::intrinsics;

extern crate libc;

#[no_mangle]
pub extern fn main(_argc: i32, _argv: *const *const u8) -> i32 {
    0
}

#[lang = "eh_personality"]
#[no_mangle]
pub extern fn rust_eh_personality() {
}

#[lang = "eh_unwind_resume"]
#[no_mangle]
pub extern fn rust_eh_unwind_resume() {
}

#[lang = "panic_fmt"]
#[no_mangle]
pub extern fn rust_begin_panic(_msg: core::fmt::Arguments,
                               _file: &'static str,
                               _line: u32,
                               _column: u32) -> ! {
    unsafe { intrinsics::abort() }
}

注目するのは #[lang = "panic_fmt"] のところで、こう指定することによって、実行中に panic が発生した際の挙動を書き換えることができます。

しかしちょっとわかりにくいと思うので、私が今作成中のもう1つのサンプルコードを元に挙動を確認してみましょう。

#![feature(lang_items)]
#![no_std]
#![no_main]

static HELLO: &[u8] = b"Hello, World!";

// linux
#[no_mangle]
pub extern "C" fn _start() -> ! {
    let vga_buffer = 0xb8000 as *const u8 as *mut u8;

    for (i, &byte) in HELLO.iter().enumerate() {
        unsafe {
            *vga_buffer.offset(i as isize * 2) = byte;
            *vga_buffer.offset(i as isize * 2 + 1) = 0xb;
        }
    }

    loop {}
}

#[lang = "panic_fmt"]
#[no_mangle]
pub extern "C" fn rust_begin_panic(
    _msg: core::fmt::Arguments,
    _file: &'static str,
    _line: u32,
    _column: u32,
) -> ! {
    loop {}
}

これは現在作成中の OS の元となるコードで、VGA テキストバッファを用いてスクリーン上にテキスト(通常は Hello, World! と出力されます)を出力するだけの簡単なプログラムです。このコードを実行すると次のようになります。

f:id:yuk1tyd:20180212120729p:plain

ちなみに余談ですが、冒頭で #![no_std] によって標準ライブラリをすべて削ぎ落としているので、println マクロは使用できません。

では、#[lang = "panic_fmt"] に出力内容を設定して、実際に _start() 関数の中で panic を起こしてみましょう。

#![feature(lang_items)]
#![no_std]
#![no_main]

static HELLO: &[u8] = b"Hello, World!";
static PANIC: &[u8] = b"Panic has been occurred!";

// linux
#[no_mangle]
pub extern "C" fn _start() -> ! {
    panic!("Panic!");

    loop {}
}

#[lang = "panic_fmt"]
#[no_mangle]
pub extern "C" fn rust_begin_panic(
    _msg: core::fmt::Arguments,
    _file: &'static str,
    _line: u32,
    _column: u32,
) -> ! {
    let vga_buf = 0xb8000 as *const u8 as *mut u8;

    for (i, &byte) in PANIC.iter().enumerate() {
        unsafe {
            *vga_buf.offset(i as isize * 2) = byte;
            *vga_buf.offset(i as isize * 2 + 1) = 0xc;
        }
    }

    loop {}
}

panic の部分には、0xc (明るめの赤) によって、「Panic has been occurred!」という文字列を表示することにしました。結果、

f:id:yuk1tyd:20180212121035p:plain

正しく書き換えが行われたことがわかります。

まとめ

  • lang_item は Rust 固有のアイテムのことで、コンパイラが特別視する要素のこと。
  • lang アトリビュートを用いることで、lang_item 内のさまざまな要素を書き換えることができる。
  • no_std と組み合わせて使用するのが(たぶん)代表的な使い方。

参考

Rust の no_std について

詳しいところはドキュメントを読みましょう事案なのですが、今作っているプログラムで次のような文言がはじめて出てきて、どういうことか整理しておきたいのでメモ程度に残しておきます。

出てきたアトリビュートは下記です:

  • #![no_std]

以下、あいまいな理解の元、ドキュメントを読んだメモ程度に記事を書くので、間違っている点などはご指摘ください。ちなみに利用環境は Rust の nightly であることを前提としています。no_std は stable ビルドでも動きます。

no_std は Rust の標準ライブラリを OFF にしてくれる?

公式のチュートリアルによれば、

Rustの標準ライブラリは多くの便利な機能を提供している一方で、 スレッド、ネットワーク、ヒープアロケーション、その他の多くの機能をホストシステムが提供していることを前提としています。 一方で、それらの機能を提供していないシステムも存在します。しかし、Rustはそれらの上でも利用することができます! それは、Rustに標準ライブラリを利用しないということを #![no_std] アトリビュートを利用して伝えることで可能となります。

ということです。クレートのトップに no_std をつけることによって、Rust 標準のライブラリを完全に OFF にしてくれるようです。具体的には、下記はコンパイルエラーになります。

#![no_std]
fn main() {
    println!("Hello, World!")
}

結果は、次のように println マクロが見つからないと怒られて終了します。標準ライブラリをすべて落としているので、当然の挙動ではあります。

error: cannot find macro `println!` in this scope
 --> src/main.rs:3:5
  |
3 |     println!("Hello, World!")
  |     ^^^^^^^

error: aborting due to previous error

どういった文脈で使用したか?

具体的には OS を作成する際に、スクリーン上に文字列を表示するまでの段階で使用することになりました。通常 OS を作成する際には VGA (の、Text Buffer) を用いてスクリーン上に文字列を表示するようです。そこに stdout などを使ってしまう Rust の println マクロなどの標準ライブラリは必要がないので読み込まないようにしておくといったところでしょうか。

あとは、組み込みOSなどの文脈で使用することも考えられます。

次回は lang_items ならびに no_mangle などのアトリビュートの話を書く予定です。このあたり、結構日本語文献も少ないですし、自分の知見のためにもしっかり書いておきたいですね。

『言語実装パターン』を読んだ

ANTLR 作者による本で、中身は後半から ANTLR を使った実装でした。ただ、ANTLR を使用する・しないに限らず、解説を読むだけでもインタプリタ制作に詳しくなることができる一冊かなと思います。要するに、何か特定のツールや言語に限らない広く使える知識を習得できるということです。

また、中身は Java で実装されていますので、他のコンパイラ本のようにがんばって C 言語を読む必要もありません。ただ、実装がちょっと古いように感じたので、適宜最近の Java の実装に置き換えて考えてみるといいかなと思います。

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

読んだ動機

  • 以前、スクリプト言語Lispインタプリタなどを作ったことがあったが、理論的な背景についてより深く体系的に勉強したいと思ったから。
  • ただ、コンパイラの教科書はまだちょっと難しかった…と思っていた矢先に、 Java による実装例が豊富な本書が目に止まったから。

読後の感想

  • インタプリタの実装について一通り、しかも手軽に学ぶことができる: ただのスクリプト言語インタプリタではなくて、一応バイトコード出力くらいまで取り扱ってくれます。ただ、AST を作って、それがどの木かを判別するくらいまでしかしていなくて、いわゆる eval (評価フェーズ) は取り扱っていません。
  • ANTLR について知りたい際にはもってこい: ANTLR のサンプルコードがたくさん載っているので、ANTLR 入門にもとてもよいと思います。
  • コードがちょっと微妙…: 私があまり、フィールドを使った再代入などが好きではないという好みの問題かもしれませんが、もう少し Effective Java に載っているようなアンチパターン的な実装を減らしてほしかったかなと思いました。もっとも、作者もアンチパターンをしていることはわかっているようです。あえてそうしている的な説明がきちんと本の中でなされているので、そこは好感のもてるところではあるのですが。ちなみに LL(1) パーサに関しては Scala でちょっと書き直してみました (動作未確認) 。ただ、あまりに辛くて途中で挫折しましたorz

ちなみに、言語実装に関する基本的な話のみを知りたいとしたら、本書は1章を読んで閉じるのもありです。長いので、サラっと読んだだけの章は1行くらいでメモを残しておきます。

読書メモ

1章

言語実装に関する基本的な知識が詰め込まれています。1章を読んで本を閉じてもかまわないくらいよくまとまっていると思いました。

  • 言語は reader, generator, translator, interpreter によってできています。reader はテキスト読み取り、generator は内部データ構造を走査して出力を書き出し、translator はテキストを読んで同じ言語・別言語の形式に沿って出力を書き出す、最後にインタプリタは命令を読み込んで解読し、それを実行するものです。
  • reader→構文解析、generator→木構築、translator→スコープ作成、interpreterバイトコード出力といったくくり?
  • Java コンパイラが生成する .class ファイルの中には、記号表と抽象構文木が直列化された状態で格納されています。
  • FindBugsBCEL を使うことにより、 .class ファイルを読み取る方式を取っています。

2章

よく聞く LL(1) ならびに LL(k) 構文解析に関する話です。本当にコンパイラを作る上でよく見る手法が掲載されています。

  • LL : 1個目の L は「左から右に入力を読み取る」ことを指していて、2個めの L は「左から右の子ノードの順で構文木の階層を下る」ことを指します。後述するように、プログラムの1つ1つの句は、最終的には一度木構造に直して、それから解釈を開始するので、子ノードという表現になります。
  • 句の構造を理解して、木を作成するまでが構文解析の仕事: たとえば、次のようなコードがあった場合、下記のように木を作ります。これさえ覚えておけば、あとは Token を生成するだけで一通りインタプリタの基礎は出来上がります。
if (x < 0) x = 0;
  ^^^^^^^     ^^
  式(expr)   式(expr)
            ^^^^
            代入(assign)
^^^^^^^^^^^^^^^
if 文 (ifstat)
^^^^^^^^^^^^^^^^
文 (stat): セミコロンまで
  • 先読み集合: 特定の構文候補の先頭になることができる字句の集合のことをいいます。計算方法は2種類あり、FIRST と FOLLOW と呼ばれているようです。しかし、実際は「この構文候補ではじまるすべての句に対して、どの字句ならその句を開始できるか?」を考えるとより簡単に先読み集合を計算できます。

3章

LL ではシンプルすぎて、たとえば C++ といった高度で複雑な文法をもつ言語の構文解析には対応できないので、それに対応するための手法がいくつか紹介されています。後戻り構文解析器、メモ化構文解析器、述語制御構文解析器の3つが紹介されていました(正直消化不良)。

4章

いわゆる AST (抽象構文木) を作るフェーズです。昔作って遊んだ経験もあいまって、この辺の理解は少し深まった気がします。

  • 改めて、なぜ木を使って文を認識するのかの話。多くの言語には、部分句と入れ子構造が存在しており、それを表現するのに木の方が、他のアルゴリズムに比べて都合がいいからとのことです。
  • AST は次のようにノードを作っていくことで、最終的に木として扱えるようにします。Scala だと、case class を始めとする代数データ型 + パターンマッチングをすることで本当にスッキリ書けそうだなと思いました(下記の実装は Scala によるものです)。Rust だったら enum かな。
sealed trait AST

sealed trait ExprNode extends AST

case class AddNode(evalType: DataType) extends ExprNode

case class MultNode(evalType: DataType) extends ExprNode

case class IntNode(evalType: DataType) extends ExprNode
  • その他、さまざまな構文木の構築手法について解説がされています。

5章

木の走査について。Visitor パターンを使って、再帰的に処理していくのが一般的みたいですね。なお、このあたりまでは、基本的にパーサーコンビネータのライブラリを使うことで、そちらに処理を任せてしまうので、普段意識をすることはあまりないかなと思いました。もちろん、中身をブラックボックス化せず、内部的な処理を理解しながら利用することは、デバッグ精度の向上にもつながりますしとても重要なことです。

6章

ここからが結構おもしろかったです。まずは、スコープの作り方。

  • まず、Symbol と Type という概念を導入します。Type は後続の章で出てくるので後述しますが、型を表します。Symbol は、それがメソッドであることを示したり、変数であることを示したり、クラスであることなどを示します。
  • さらに、各 Symbol は Scope の中にまとめられます。実装としては下記のようになるはず。
trait Scope {

  /**
    * 名前を取得します
    */
  def name(): String

  /**
    * 他のスコープの中で入れ子状態かどうか
    * @return [[Scope]]
    */
  def enclosingScope(): Scope

  /**
    * シンボルをスコープの中で定義します。
    * @param symbol [[Symbol]]
    */
  def define(symbol: Symbol): Unit

  /**
    * スコープの中で、引数として与えられたスコープ名を検索します。
    * @param name スコープ名
    * @return 検索結果の [[Symbol]]
    */
  def resolve(name: String): Symbol
}
  • スコープは、スコープスタックにまとめられて順繰りに取り出されるようにして判定が行われていきます。コード上のスコープは、このようなシンプルな仕組みで表現されているのですね。
  • プログラムでは結構入れ子スコープになるのですが、入れ子も木で表現されます(スコープ木)。たとえば MethodSymbol は、さらに内部に自身の LocalScope を保持しており、その LocalScope はさらに、自分自身の中にどのようなシンボルを持っているかを保持しています。
trait Symbol

case class MethodSymbol(name: String, orderedArgs: List[String], scope: LocalScope) extends Symbol

// エトセトラ。変数のシンボルなども続きます。

trait Scope

case class GlobalScope(symbols: List[Symbol]) extends Scope

case class LocalScope(symbols: List[Symbol]) extends Scope

7章

クラスや構造体のスコープ木の構築に関してでした。基本線は6章とそこまで変わりません。クラスの場合は、継承も表現する必要があるのですが、継承もきちんと表現できていました。すごいですね。

8章

ついに型をつけます。型計算と呼ばれる物を使って、型安全性やポリモフィズムを実現します。また、暗黙の型変換(int → double とか)に関する解説もあります。このあたりから、結構ハードに ANTLR が登場してきます。

9章

これまでの章で解説された実装をすべてつなげて、インタプリタの実装を行います。総集編ですね。

10章

9章の実装で一通りインタプリタは作成できるのですが、それだけだと速度が遅く、とくにプログラミング言語を作る際にはとても使い物にならないそうです。そこで、バイトコードを直接解釈できるバイトコードインタプリタの作成に取り掛かります。

11章, 12章

Wiki から HTML に変換したり、あるいは Java のクラスを、テーブルを作成してくれる SQL に変換したりするサンプルが掲載されています。

今後

有限状態オートマトンの理解を進めたいのと、それを使った関数型による Lexer の実装をしてみたいですね。そこさえクリアできれば、この本に載っている話のほとんどを関数型プログラミングで実装できるかなと思いました。実際、再帰を非常によく使う話ですし、代数データ型とパターンマッチングでかなりスッキリさせられるはずなので…。

『Emacs実践入門』を読んだ

Emacs実践入門』をひととおり読んでみました。仕事で Emacs を使うことがだんだん増えてきており、いつかちゃんと勉強したいなと思っていたので、年末年始でいろいろ設定してみました。

[改訂新版]Emacs実践入門―思考を直感的にコード化し、開発を加速する (WEB+DB PRESS plus)

[改訂新版]Emacs実践入門―思考を直感的にコード化し、開発を加速する (WEB+DB PRESS plus)

読後の感想

  • とりあえず Emacs をハードに使って開発する基盤ができあがる: 本書の内容にそって init.el を書き換えていくだけで、開発に必要な設定が一通りできあがります。Emacs 使いならある程度共通してやっている設定や、 git の設定、各言語固有の設定までその内容は多岐に渡ります。
  • それぞれの項目の深掘りはあまりない: 入門者向けなので仕方ありませんが、記載されている Elisp の解説やなぜそのような機能が実装されているのかといった深掘りするような話はありません。本当に必要最低限載っています。

読後の私の Emacs の状況はこんな感じになりました。

f:id:yuk1tyd:20180101171643p:plain

読書メモ

1章

Emacs の紹介です。

2章

インストールの仕方など。

3章

Emacs の特徴でもあるキーバインドについてです。頻出するキーバインドについてはひととおり押さえてあります。

4章

Emacs のカスタマイズが始まります。具体的には次のような話です。

  • オススメのディレクトリ設定は、 .emacs.d 以下に init.el を置いて、さらに conf, elisp, elpa, public_repos, etc, info ディレクトリを作成する方法みたいです。他の GitHub 上の dotfiles/.emacs.d も見てみたのですが、結構この構成に則っていることが多くわりとスタンダードな方法なのでしょう。
  • require 関数は、拡張機能を最初から全部読み込みたい際に使用し、autoload 関数はコマンドを登録だけしておき、実行時に読み込みたい際に使用します。

5章

より細かい Emacs 本体の設定がはじまります。設定は多岐に渡りますが、私は次の設定を再設定してみました。

  • 文字コードの設定: (prefer-encoding-system 'utf-8)
  • 行番号を常に表示: (global-linum-mode t)
  • 対応する括弧のハイライト: (setq show-paren-delay 0)(show-paren-mode t)
  • バックアップを1箇所に集めるようにした: (add-to-list 'backup-directory-alist `(cons "." "~/.emacs.d/backups/"))(setq auto-save-file-name-transforms `((".*" ,(expand-file-name "~/.emacs.d/backups/") t)))
    • /.emacs.d/backups にバックアップファイルを集めてくれるようになります。バックアップファイルは必要なのですが、毎回そのファイルのディレクトリに作成されてしまって git を使った管理をしていてとても邪魔に感じていたので、非常に助かる設定でした。
  • ファイルの自動更新: (global-auto-revert-mode t)

6章

パッケージの管理に関する章です。ある特定の言語にとらわれない汎用的な設定がメインです。

  • パッケージをインストールするには、elpa などの設定を済ませた後に M-x package-install することでインストールできます。
  • ただし、インストールしたパッケージはすぐには反映されないので、M-x package-initialize します。
  • undo-tree など便利なパッケージがいくつか紹介されていて、ひとまず私も何個か入れてみました。

7章

開発時に使用するパッケージの紹介で、magit など便利なパッケージがいくつか紹介されています。Web 開発に特化している感じですね。RSpec との連携ができるとは知りませんでした。

今後

Lisp で設定ファイルを書けるのはやはり楽しいので、Emacs Lisp 関係の本も読んでみたいかもしれない。C 言語用の設定をやっと真面目に整えたので、C 言語ライフがちょっとはかどりそうです。

若手のエンジニアが SI から Web 系に転職した話

この記事は退職者その2 Advent Calendar 2017 23日目の記事です。転職して1ヶ月半くらい経ったので、転職時の話と実際の業務状況などを簡単に書いておきます。若手で、テックに強い興味があり、なおかつ SI から Web 系への転職を考えている方への参考になればと思います。

書いてる人

最初に簡単に私のプロフィールを書いておきます。

  • 前職は金融業界の SI で、債券・デリバティブリスク管理を行う計算機を作る仕事をしていました。
  • 現在は、いわゆるアドテクの RTB を作るお仕事をしています。
  • 学生時代は Web マーケティングとか Web デザインのアルバイトをしていました。
  • 就活時は戦略コンサルや IT コンサルを受けていました。
  • 文系卒で、就職して初めてプログラミングをしました。
  • 社会人3年目の後半での転職です。

動機

理由は下記3点です。

  • 金融業界xSIでは、使える技術の幅に限界があったから。
  • 受託開発があまりしたくなかったから。
  • アドテクしたかったから: カンファレンスで聞いておもしろそうだなと思ってしまったから。

よくある転職理由かとは思いますが、私もご多分に漏れず、です。

ただ、前職は職場環境としては非常にいいものだったと思っていて、労働時間が異様に長いとか、人間関係をこじらせたとか、そういう理由で転職したというわけではないです。

外資投資銀行出身者や外資系コンサル出身者が多い職場で、そういった人たちの仕事ぶりを社会人最初の3年間でみっちり見ることができたというのは、今後の人生にとてもいい影響を与えてくれるものと確信しています。

転職先探しや実際に決まるまで

準備

探し始めたのは去年の12月くらいからでした。ただ、SI 出身者が Web 系に移るには、やはりそれ相応にコードが書けるということは証明する必要があると思ったので、最新のツールを色々触ってみるところからスタートしました。だいたい半年くらいは準備期間として使いました。

具体的には、自分の手元で作ったアプリケーションを GitHub に適当に公開しました。目的は、面接を受ける際に「技術に興味があって、最新情報も割と追っていますよ」ということをアピールするためでした。面接時の話題作りには役立ってくれたとは思います。

実際にいくつか面接を受ける

  • 技術系の話はそこまで深掘りはされなかった: 履歴書に「専門家感」を出すアピールをしていなかったからだとは思いますが、テック系の話はそこまで深掘りされませんでした。突っ込んだ話で強いて言うなら、パフォーマンスチューニングの話を書いていたので、具体的にどのような手順を踏んでチューニングしていたか、という話くらいでした。 Rust が好きだったので Rust の話はこちらからたくさんしましたが。
  • 実技試験は受けた限りではなかった: なかったです。してもいいと思うけど。
  • チーム内でどのような役割を担っていたか、とか問題解決法とかをよく聞かれた: 仕事に対する姿勢ですね。主体性を発揮しているか、や問題解決をきちんとできる人か、というのをむしろ強く見られていたように感じました。当然ですが事業会社なので、仕事は自分で見つけなければなりません。それができるかどうかを見られていたように思います。
  • GitHub で公開していたコードは自分で勉強する人アピールのネタにはなった: 「ご自身で結構いろいろな技術を触られているんですね」という話はよくされました。が、そこまで中身はまともに見ていなかったように思います。GitHub で公開しているコードに関する質問は受けませんでした。
  • コーディング力については若いこともありポテンシャル重視: 私がまだ若いこともあり、そこまで技術面は期待されていなかったのかなと思いました。入ってから伸ばしてくれればいいや、くらいのスタンスだったように思います。

今の職場への決め手

  • 技術へのリスペクトが感じられた: 技術には、それ相応に長い歴史があり、それを「たかが技術」と片付けることはできないと思っていました。技術に対する強いリスペクトのある職場がいいなと思っていたので、それが感じられた今の職場にしました。
  • 自己の能力を伸ばすことへの惜しみない投資がある: 書籍補助や図書館制度を福利厚生として利用できます。エンジニアの自身の知的探究や自己能力の向上に対して、きちんと投資されている環境だなと思いました。また、大学の研究室のような制度があり、業務時間の何割かをそれに割くことができます。
  • 自分より年齢の高いエンジニアが多い: 30代前半〜後半くらいのエンジニアがとても多いように見えました。そういった人でもバリバリコードを書いていると聞きました。
  • マネジメント層が魅力的: やはり手練な人が多いですね。そして、人の成長とか、人が何考えてるかについて、きちんと興味を持ってくれている人が多いなと思いました。上の人に魅力を感じて入ることを決めました。

内定後

  • 年収とか: 今の額くらいで十分かなという思いがあったので、こちらから強く「上げてくれ」という要求はしませんでした。実際はちょっと上がりました。正直エンジニアの技術力は数値化が難しいものなので、「上げてくれ」アピールはたくさんしてもいいと思います。きっと、言った値段が自分の市場価値です。ちょっと鯖読んで釣り上げても、あとから実力を追いつかせればいいのです(暴論)。
  • 退職を告げる順序: まず、直属の上司 (外資系だったので、日系だとどうなのかはわかりませんが) 、そのあとマネージングディレクター、最後にシニア相当の人、という順序です。必ず役職が下の偉い人から伝えるようにしましょう。飛ばしてはいけません。
  • 入社までの期間: 2ヶ月あったので、自宅で Scala の勉強をたくさんしました。手始めにスクリプト言語インタプリタ作りました。あとは、Web 系でどういう技術が使われているかを一応調べて、手元で動かしてみるなどしました。これは入社後、すぐにキャッチアップができて非常に役立ちました。

転職後

変わったこと

  • 10時出勤になった: 9時出勤から10時出勤になりました。
  • Excelを全然使わなくなった: SI からすると衝撃的かと思います。本当に使わなくなります。
  • メール中心からSlack中心の生活へ: コミュニケーションツールが変わっただけで、とくに感想はありませんが一応。
  • Windows から Mac になった: 使用OSは選べます。WindowsMac か、だけみたいですが。
  • SVN から GitHub に変わった: Git の操作はある程度 GitHub で慣れていたものの、チーム開発の経験はなかったので最初とても苦労しました。今でもマージが怖いです。
  • Java から Scala を使うように変わった: 言語は Rust 使える、以外だったらどれも一緒と思って転職活動をしていたのであまり興味がありませんでしたが、Java から Scala に使用言語が変わりました。ただ、そこまで関数型してません。
  • 技術選択の幅が広がった: さっそく Vue.js でフロントエンド開発をするなど、自分でライブラリを選んで使うことができるようになりました。また、使用言語も技術検証をきちんと行えばなんでも使っていいようで、将来は Rust でガンガン書きたいなと個人的には思っています。
  • ウォーターフォールからアジャイルスクラム)に変わった: 「テスター」という言葉を一切聞かなくなりました。リリース期間が圧倒的に短くなったのと、リリース後にすぐに効果が出ているか出ていないかわかるといった、スピード感の違いも感じています。
  • オンプレからクラウド: AWS は触ったことがなかったので、最初全然わかりませんでした。今も勉強中です。

そもそもの転職の動機が、「もっとたくさんの技術を使いたい」「受託やだ!」だったので、そういった点では転職前の不満は解消されているようです。

変わらないこと

  • 仕事の基本みたいなところ: 重視される価値観は、そこまで変わりありません。自分の立てた見積もりと実際に作業した見積もりに乖離がないことなど。

転職してみての感想

  • 何かが劇的に変わることを期待して転職しないほうがいい: 転職後も、結局は日常が続きます。使える技術を選ぶのも、それを使えるようにするのも、高い評価を得るのも、結局は自分から働きかけないことには達成できません。職場が、環境が自分を変えてくれるだろう、というのは期待しないほうがいいとは思いました。転職は、自身の不満にとっての銀の弾丸にはなりえません。
  • 想像以上に主体性を求められる: SI だと、要件もテストも全部他の人がやってくれていたのですが、Web系はそうはいきません。要件を詰めるのも、テストコードを書くのも、ビルドを回すのも、全部自分でやらなければいけません。また、サービスを生む立場なので、そもそもどういう要件がいいか、から考え始めなければいけません。SI とは状況が全然違います。
  • 仕事の本質的なところは変わらない: コンサルティングファーム仕込みの問題解決力とかプレゼンテーション力とか、SI で培った資料作りとか、ドキュメントづくりとか、そういった基本姿勢やスキルは Web 系でもいかせます。

これからも、たくさんの技術を使うことを楽しみつつ、よりよいプロダクトを作ることに集中して仕事していきたいなと思っています。個人的には、テックリードという言葉にとても興味があるので、そちらの方面に向かっていけたらいいですね。

nix によるシステムプログラミング

これは、Rustその2 Advent Calendar 2017 23日目の記事です。

Rust はシステムプログラミング言語なので当然ですが、システムプログラミングができます。が、この話題に関して探してみると思った以上に日本語文献が少ないなと思ったので、今後の Rust の普及のためにもシステムプログラミング観点からの記事を残しておきます。[*1]

ご存知の方も多いかとは思いますが、改めて、今回は nix というライブラリを使って、 システムコールforkwaitexec を呼び出す簡単なプログラムを書きます。

更新情報

  • 2021-06-06: nix のバージョン 0.19.0 より fork は unsafe 関数となっていることを確認しました。せっかくなので、現時点のバージョンである 0.21.0 を使用し、改めて fork-exec のコード部分を書き換えておきました。

Rust で UNIX システムプログラミングをする

システムコールするには libc などといった手段がありますが、今回はそれを nix というライブラリを使って書いていきます。

github.com

nix は、 unsafe なシステムコール API を提供する libc に対して、 safety なシステムコール API を提供する、libc をラップしたライブラリです。nix を用いる利点としては、下記のように libc だと unsafe な API を提供しているものを、nix の unsafe でない API を用いてシステムプログラミングをすることができる、といったところでしょうか。

// libc api (unsafe, requires handling return code/errno)
pub unsafe extern fn gethostname(name: *mut c_char, len: size_t) -> c_int;

// nix api (returns a nix::Result<CStr>)
pub fn gethostname<'a>(buffer: &'a mut [u8]) -> Result<&'a CStr>;

libc 側は unsafe により関数を呼び出しており、さらに返り値も c_int と C ライクです。一方で、 nix 側は unsafe がついていることもなく、また返り値も Result になっており、より Rust な書き方を後続処理でできるように配慮された作りです。この点もまた、nix を利用するモチベーションだと言えるでしょう。

nix で fork -> wait までを実装してみる

実際の実装例を見てみましょう。ここでは、

  1. プロセスを fork
  2. 子プロセスで新しいプログラムを exec
  3. 親プロセスは子プロセスを wait
  4. プログラムの実行結果を出力
  5. 正常に終了した場合は完了メッセージを出し、失敗した場合はその旨をメッセージに出す

という、よくある「プログラムを実行して結果を待つ」操作を実行できるサンプルを作ります[*2]。

実行結果:

./sample /bin/echo OK
OK
exit!: pid=Pid(52366), status=0

第1引数に実行したいプログラムのあるディレクトリを指定し、第2引数にそのプログラムが必要とする引数を与えます。 このサンプルでは、第1引数で echo コマンドを呼び出して、第2引数で渡された文字列をコンソールに出力しています。

サンプルコード

Cargo.toml

[dependencies]
nix = "0.21.0"

main.rs

use nix::sys::wait::*;
use nix::unistd::{execve, fork, ForkResult};
use std::env;
use std::ffi::CString;

fn main() {
    // a) fork
    match unsafe { fork() }.expect("fork failed") {
        ForkResult::Parent { child } => {
            // b) waitpid
            match waitpid(child, None).expect("wait_pid failed") {
                WaitStatus::Exited(pid, status) => {
                    println!("exit!: pid={:?}, status={:?}", pid, status)
                }
                WaitStatus::Signaled(pid, status, _) => {
                    println!("signal!: pid={:?}, status={:?}", pid, status)
                }
                _ => println!("abnormal exit!"),
            }
        }
        ForkResult::Child => {
            // 引数の値を取得する。
            let args: Vec<String> = env::args().collect();
            let dir = CString::new(args[1].to_string()).unwrap();
            let arg = CString::new(args[2].to_string()).unwrap();

            // c) execv
            execv(&dir, &[dir.clone(), arg]).expect("execution failed.");
        }
    }
}

簡単な解説

a) fork

fork(2) によって、カーネルにプロセスを複製させ、プロセスを2つに分裂させます。元から存在しているプロセスが「親プロセス」で、複製して作られたほうが「子プロセス」ですね。nixfork の rustdoc にも、今説明した挙動についてとても詳しく載っておりますので、そちらもぜひご覧ください。

さて、 nixfork ですが、きちんと Result 型で返ってきます。今回は面倒なので expect でエラーハンドリングをしていますが、パターンマッチで書くこともできます。

Result の中の ForkResult は次のような enum です:

#[derive(Clone, Copy)]
pub enum ForkResult {
    Parent { child: Pid },
    Child,
}

したがって、後続でパターンマッチングを行うことができます。ForkResult::Parent が親で、ForkResult::Child が子です。

b) waitpid

親プロセスの方は、子プロセスが処理を完了するまで待ちます。これを wait(2) によって実現しています。

waitpid の第2引数には、ブロックを防いだり、どのプロセスを待つかを制御するなどのオプションを設定することも可能ですが、今回は単純なサンプルですのでそこに関してはスルーして None を定義しています。

WaitStatus は、 wait/waitpid すると返ってくる enum です。つまり、パターンマッチできます。今回は、正常終了したかシグナルを捕捉したもののみを取り扱いました。

その他のステータスについては、ソースコード内のコメントにかなり詳しく載っており親切ですのでそちらをご覧ください:

c) execv

execv(3) は、これもまたシステムコールの1つで、自プロセスを新しいプログラムで上書きする機能を持っています。プログラムの実行時に使用する常套手段です。今回は子プロセスに処理を実行させるので、子プロセス内で execv しています。

まとめ

  • libc でもシステムプログラミングはできますが、nix を使うとより Rust らしいシステムプログラミングができます。
  • nix の rustdoc はとても丁寧に書かれており、API を使いこなしながら rustdoc にも目を通すと、それだけで結構システムプログラミングの勉強になります。

こちらもご覧ください

  • nix crate - Qiita: 17日目にも同様の話題を書いておられますので、そちらもぜひご覧ください。かぶってしまい申し訳ありません。

*1:なお、この記事では、ある程度 システムコールなどのシステムプログラミングに関する知識があることを前提にして書いておりますので、あらかじめご了承ください。そこまで難しい話は書いていないので、「そういうこともできるのか」くらいのスタンスでお読みいただければ幸いです。

*2:Mac OS X かつ Rust のバージョンは最新の nightly です。