エンジニアと思われるものの備忘録

しがない学生の備忘録です

【論文読み】Fast key-value stores: An idea whose time has come and gone

http://pages.cs.wisc.edu/~rgrandl/papers/link.pdf

上記の論文を読んだ.これからもちょくちょく論文読んでまとめるみたいなのやっていきたい

問題

現代のWebアプリにおけるIn-memory KVS,要はRedisやMemcachedはアプリケーションからロジックを切り離しステートレスにするために活躍している. だけど,シンプルなAPIゆえに,複雑なデータの格納や読み込み がやり辛いしネットワークレイテンシがでかくなる,読み込んだ後もアプリ側でバイナリデータをプログラム上のオブジェクトにマッピング((Un)marshaling)しなきゃいけなくてこいつはかなり時間がかかるといった問題があった.

関連研究

論文ではこういったネットワーク越しに存在するKVSを RInK(Remote In memory Key-value) として呼称している. RInKのパフォーマンス改善はいくつか事例があるが,単純にRDMAを使ってパフォーマンス改善をする手法や,アプリケーションサーバと同じサーバにKVSを立てるなどが挙がっている.しかし,これらは上記の(Un)marshlingを改善しようとはしてない.

解決方法

LInK(Linked In memory Key-value) と筆者は名付けている手法を提案している.こいつは単純にアプリケーションにKVSを埋め込む. データへのアクセスはライブラリが抽象化するけど基本的にメモリ内にアプリケーションのオブジェクトそのまま格納するので上記の(Un)marshalingがボトルネックじゃなくなる.

じゃあスケールアウトというかKeyの分散はどうするかというとReshardingは普通にサポートするっぽい(具体的なアルゴリズムは書いてない). まぁこれでネットワークと(Un)marshlingのレイテンシは解決できたねとのこと

まとめ

面白かったけど試験的な論文なのか(筆者はGoogleスタンフォードの人)分散KVSとして重要な耐久性やデータの一貫性とかについては「この論文では触れない」としている. 確かにアプリに埋め込めばそりゃ速くなるだろうけど当然アプリケーションとしてはステートフルになるし, ライブラリの開発とかはプログラミング言語依存になるしでまだ解決しなきゃいけない問題は多そう.

でも,これがもう少しいい感じに使えるようになったらWebのアプリはもっと爆速になるのはロマンがある.

Vagrantで仮想的なWANみたいなのを作る

研究の検証用環境として以下のような環境をVMのみで一つのホストPC上に構築したかった. Vagrantで一応できたので手順とかをメモしておく.

f:id:kk_river108:20190502181820p:plain

ストーリー

それぞれ 192.168.10.100 (Node A) と 172.168.10.100 (Node B) のVMはネットワークのセグメントが異なるので直接アクセスできない. Node AがNode Bにアクセスしたい場合はNode BのGlobal IPを指定してアクセスするようにさせる.

Node Aは100.100.100.100にNATで変換され,Node Bは100.100.100.200に変更されるとする.

Node AがNode BのGlobal IPである100.100.100.200にパケットを投げるとデフォルトゲートウェイを介してRouter VMに届き,Router VMiptablesを用いてパケットの送信元,宛先IPを変換することでNode Bにパケットを転送したい.

Vagrantfile

まず各VMの設定をVagrantfileに書いておく

# -*- mode: ruby -*-
# vi: set ft=ruby :

Vagrant.configure("2") do |config|
  # The most common configuration options are documented and commented below.
  # For a complete reference, please see the online documentation at
  # https://docs.vagrantup.com.

  # Every Vagrant development environment requires a box. You can search for
  # boxes at https://vagrantcloud.com/search.
  config.vm.box = "bento/ubuntu-18.04"

  # Network A
  config.vm.define :proxyA do |proxyA|
      proxyA.vm.hostname = "proxyA"
      proxyA.vm.network :private_network, ip: "192.168.10.100", virtual__intnet: "intnetA"
  end

  config.vm.define :peerA do |peerA|
      peerA.vm.hostname = "peerA"
      peerA.vm.network :private_network, ip: "192.168.10.101", virtual__intnet: "intnetA"
  end

  # Internal router
  config.vm.define "router" do |router|
    router.vm.hostname = "router"
    router.vm.network :private_network, ip: "192.168.10.10", virtua__intnet: "intnetA"
    router.vm.network :private_network, ip: "172.168.10.10", virtua__intnet: "intnetB"
  end  
  
  # Network B
  config.vm.define :proxyB do |proxyB|
      proxyB.vm.hostname = "proxyB"
      proxyB.vm.network :private_network, ip: "172.168.10.100", virtual__intnet: "intnetB"
  end

  config.vm.define :peerB do |peerB|
      peerB.vm.hostname = "peerB"
      peerB.vm.network :private_network, ip: "172.168.10.101", virtual__intnet: "intnetB"
  end
  
end

名前は変わっているが Proxy A, Proxy BがそれぞれNode A, Node Bにあたる. 今回はPeer* のマシンは関係ないので無視

各Nodeでデフォルトゲートウェイを設定

VMを立ち上げたら vagrant ssh で各NodeのVMにログインしてデフォルトゲートウェイを設定しておく

# Node A
sudo route add default gw 192.168.10.10 dev eth1

# Node B
sudo route add default gw 172.168.10.10 dev eth1

各NodeのVMには上記のVagrantfileで割り当てた静的なIPがeth1に割り当てられているはずなのでそれに合わせてデフォルトゲートウェイを設定する 設定した後に 各NodeのVMから ping 100.100.100.200 のような存在しない,アクセスできないはずのアドレスにpingを打ち,

Router側で sudo tcpdump -i any icmp と叩くことで各VMからのpingを観測できるはず

Router VM上でiptablesを設定する

まずパケットの転送を許可する設定を行う

vi /etc/sysctl.conf

でファイルを開き

#net.ipv4.ip_forward=1

コメントアウトを外す. その後に sudo sysctl -p で有効化する.これでVMを再起動してもパケットの転送設定はOnのまま

次に iptables に変換テーブルを追加する

sudo iptables -t nat -A PREROUTING -d 100.100.100.200 -i eth1 -j DNAT --to-destination 172.168.10.100
sudo iptables -t nat -A POSTROUTING -o eth1 -s 192.168.10.100  -j MASQUERADE
sudo iptables -t nat -A PREROUTING -d 100.100.100.100 -i eth2 -j DNAT --to-destination 192.168.10.100
sudo iptables -t nat -A POSTROUTING -o eth2 -s 172.168.10.100  -j MASQUERADE

1行目はeth1に流れてくる100.100.100.200が宛先となっているパケットを172.168.10.100に変換する. 2行目はNode Aへの返信のパケットを逆変換して届けるための設定 3, 4行目はそれぞれNode Bからのパケット用に書き換えたもの.

これで上記の図のパケット転送がうまくいくはず

ドラゴンクエストXを支える技術を読んで 〜普通のソフトウェアエンジニアから見た視点〜

ドラゴンクエストXを支える技術」を読みました

www.amazon.co.jp

読んだ感想

非常に面白い本でした.オンラインゲームのプログラミングに関わったことがない人でも参考になる知見が沢山詰まっています. 本書はドラゴンクエストXにおける元テクニカルディレクター,現プロデューサーの青山さんが執筆しています.

元々,Web+DB Pressで連載されたものをリライトしたものです. 折角なので普段はWeb系の開発に携わっている & ドラゴンクエストXの一般ユーザーとして面白かったところをいくつかピックアップしようと思います.

前提知識

まず読者である僕が持っている知識について書いておきます. なぜそんなことを書くかというと,僕が面白いと言ってもそれはある程度プログラミング等の開発知識があるから面白いと思えたことも多々あると考えているからです.プログラミングに一切関わりがないドラクエXユーザーが抱く感想とはまた違うかもしれないということ予め伝えておきます.

  • プログラミング: 普段はWeb関係の開発に従事しています. ドラクエXで言うなら冒険者の広場やお出かけ便利ツールの開発がこれに当たります.
  • コンピュータに関する知識: 大学院で専攻している内容でもあるので基礎的なものは大丈夫だと思います.ドラクエXではメモリの最適化,グラフィック処理,移動干渉やトランザクション処理のロジック全般がこれに当たります.
  • ネットワークに関する知識: 所謂TCP/IPレベルのネットワークや負荷分散などのノウハウについては研究している分野でもあるのでほぼ大丈夫でした.

と,こんな感じの人が読んだらどういう感想やどこが面白いと思ったのかというのを書いていきます. 順番としては本書の章立てに従っていきます.

メモリの最適化を意識したコーディング

コンピュータにおけるプログラムの実行は基本的にメモリとCPUが肝です. プログラムを実行する際にはWindowsで言えば .exe ファイル,所謂実行形式のファイルをOSがメモリに領域を確保して,展開し,CPUがメモリに展開された命令を一つずつ実行するというフローになっています. これは当然オンラインゲームでも同じです.PCやSwitch, WiiUなどのメモリ上でドラクエXのクライアントが展開され実行されているわけです. 勿論重要なプログラムはインターネット上にあるドラクエXの心臓部でもあるゲームサーバで実行されているわけですが.

ここで問題になるのがメモリには限界があるということです.オンラインゲームはどんどんアップデートを重ねてそのプログラムの大きさは非常に大きいものになっていきます.しかし,メモリには容量の限界があるため例えば20GBもあるプログラムは大抵の家庭用PCでは満足に動かないと思います.

本書でも再三言われていますが,ドラクエXではそんなメモリの容量を事細かに気にしながらプログラミングをしています. コラムでは構造体のメモリアラインメントに関する知識に関しても触れていました.

例えば多くのCPUで要求される構造体(size_t)のアライメントは 32bit環境では 4byte, 64bit環境では 8byte だったりします. 次の擬似コードではメンバ変数のサイズの合計は6byte(int: 4byte, char: 1byte)です.

struct Hoge {
    int A;
    char B;
    char C;
}

このコード自体はエラーなどはないのですが,アラインメントされていない場合は環境(CPUやメモリ)によっては構造体のサイズが変わってしまうかもしれないのです. そこで次のように明示的に確保される容量を示します(本書とは違うように書いてます)

struct Hoge {
    Size32int A;
    Size8char B;
    Size8char C;
    Size16bits padding; 
}

ここまでのレベルで最適化を意識することはほぼないので読んでて非常に新鮮でした.

使用するプログラミング言語

ドラクエXではC++Luaが主な開発言語として使用されているようです. ゲームならまぁC++だろうなというのは思いましたがLuaが使用されているのは以外でした.

Luaは高負荷にはならないクライアント側のちょっとした処理をPDCAのサイクルを早く回すために用いられているようです. ただ,LuaC++の連携は具体的にどうやってやっているかはちょっとわかりません(RPCなのかC++からLuaを直接呼び出しているのかそのまた逆か).

大規模プロジェクトならではのビルド環境

ビルドというものはプログラミング言語でかかれたファイル群を実行可能な一つのファイルにコンパイルすることを指しています. 往々にして大きなプログラムになるほどこのビルドには時間がかかるものです. 例えば有名なコンパイラである LLVM というOSSは自分のPCでビルドしようとすると2, 3時間かかったりします. ソースコードを修正するたびにそんなに時間がかかっていたら生産性も下がってしまいますよね. ビルドを自動化したり高速化するのもプログラマ界隈では重要なミッションです.

ドラクエXでは distcc という分散コンパイラというものを使っています.大体インターネットでコンパイラと調べると一つのPC上で処理が完結するものが殆どですが,distccは複数のPCで分散してコンパイルを行うことで高速化を図るというものです.プロダクション環境で使っている例を初めて見たので感動でした.もしかしたら色々なところで使われているのかもしれませんがあまり話題にならないのとオープンにしていない可能性もあります.

また自動ビルドによってテストを一定間隔で実行して報告するような仕組みも作っているようです.これは似たような事例が ゼルダの伝説 ブレスオブザワイルド の開発の話でも上がっていましたね.大きいプロジェクトですとこういった仕組みの構築が開発の生産性向上に繋がりやすいのでしょう.

小さいプロジェクトとかだとMakeだけとかでもいいですけど何万行とかのコードベースなってくると色々な工夫が必要になってくるって感じはよくわかります.

厳密なバージョン管理とPDCAの回し方

コードベースが巨大になるにつれて1コミットが思わぬバグを生んだりするっていうのはまぁよくあることです. どうやらドラクエXの開発でも実際にそういうことがあったらしく原因や改善策について触れています. 特にリリースしたバージョンのコードベースに変更を加える際には小さい変更でも必ずテクニカルディレクターのレビューを通してからじゃないとマージされないそうです.

ちなみに,バージョン管理にはSVNを使ってるらしいです.Gitでも良かったそうですが使い慣れてるほうにした模様. コードベースが巨大になるとブランチのチェックアウトにもかなり時間がかかるそうでそれは体験したことないので興味深いです.

PDCAは基本的に最近のWeb開発とあまり変わらないようです.ただ,ゲームなのでドッグフーディングに費やす時間はとても多いように文面から感じました. そこからリリースまでに何回もFixを重ねてリリースブランチとするみたいな感じらしいです.

クライアントとサーバそれぞれのメモリ管理

クライアント側

クライアント側は基本的にグラフィック周りがボトルネックになる模様. 例えば,フィールドを散策してモンスターが画面に写ったり消えたりするたびに

// モンスターをメモリに確保
Monster *m = (Monster *)malloc(sizeof(Monster));

// なんか処理(バトルだったり話しかけたり)

// モンスターをメモリから解放
free(m);

みたいな処理が行われるわけです.こういうことを繰り返しているとメモリの断片化ということが起こってメモリが中途半端に開いてる箇所が沢山増えてしまう. そうすると効率的にメモリを使えなくて処理が遅くなったりしちゃうわけですね.

ドラクエXではこのメモリの断片化を防ぐために解放したメモリ領域を適切に再利用することで解決しています.

この問題を読んでいる時にドルボードのブースト機能を思い出しました. いつだったかりっきーが「ドルボードの高速化は技術的に非常に難しい問題」というようなことを言っていたと思います.

これは後述されるグラフィックの処理と移動干渉の問題も絡んでいると思いますが,基本的にユーザーが移動するたびにユーザーの位置や視点から画面に映るオブジェクトを算出しメモリに確保したりしなきゃいけません.これは非常に計算量の大きい問題なのでそれがドルボードの加速によってより短いスパンで行われると描画演算が追いつかないみたいな問題があったのかもしれません(移動してるけど風景が何もないみたいな).

常時高速化だとクライアント側の負荷も相当になるので一時的なブースト機能ということで実装されたのでしょう(あくまで憶測です)

もう一つクライアント側ではプログラムオーバーレイという技術を使ってメモリの節約を図っています. 一見小難しい言葉ですが要は「普段使わないプログラムは読み込まないで必要になったら読み込む」ということです.

本書の例では住宅村や魔法の迷宮などのインスタンスオブジェクトが挙げられていました.メギストリスで討伐を買うために並んでいるときに住宅村のプログラムをメモリに読み込む必要はありませんからね.

サーバ側のメモリ管理

サーバ側は基本的にコアロジックが集約されているので速度が重視されるものが多いです. そのためメモリのスワップアウトはなるべく防ぎたいというのがドラクエXの開発側の意見です.

スワップアウトというのはプロセスに割り当てられたメモリ領域をオーバーした場合は足りない部分はHDDやSSDの記憶領域を利用させてもらうことでメモリ不足を解決するわけです.

メモリが足りてるならいいじゃないかと思うかもしれませんが問題は速度です.

一般的なメモリの読み込み速度は 10GB/sSSD, HDDは最速で 100MB/s となっています. SSDですらメモリの100倍遅いです.

というわけでサーバプロセスがサーバのメモリを食い尽くしてしまわないように各サーバで適切にプロセスを割り当てて稼働させているようです.

サーバ側で動くゲームプロセスにおける工夫

サーバプロセスはシングルスレッドで動く

シングルスレッドは文字通りCPUから割り当てられるスレッドが一つということです. 一般的にプログラムはマルチスレッドで処理した方が高速になります(マルチスレッドの高速化手法については非常に説明が大変なので割愛). しかし,マルチスレッドは排他制御を必然的に組み込まなくてはならなくなり,デバッグが大変になります.

コードベースが巨大になるとどこがバグの原因なのか突き止めるのはもっと大変になります.そういった点を考慮してドラクエXではシングルスレッドで実装したそうです.

ゲームDB

ドラクエXのイベントでも度々開発者の方々が口にするDB(データベース),ドラクエXのデータの全てが詰まっているDBは単一障害点として非常に慎重に扱わなければなりません.

Oracle Exadata

ドラクエXではバックエンドのDBとしてOracle Exadataが使われています.なんかのイベントでよーすぴが言っていたように 銀行で使うようなDB の通りエグい検索速度,容量,そしてお値段(調べるとわかりますが数千万円は軽く越えます).

大規模なWebシステムで使うクラウドベンダが提供しているDBを一ヶ月利用しても高くて10万ちょい,一年で100万ぐらいと考えるとその規模の大きさがわかります.

Exadataには基本的にプレイヤーの情報全てが入っていると考えていいでしょう(持ち物,ステータス,ストーリーの進行状況etc...).

個人的に一番すごいなと思ったのが旅人バザーにおけるDBの使い方です.

旅人バザーはユーザーが出品した商品を他のユーザーが買うことができるシステムです.ドラクエXの経済は基本的にこれを基準に回っており,現実世界の経済と何ら変わりはありません.しかし,問題になるのがトランザクション管理です.

トランザクションというのは例えば

  1. AさんがBさんの商品を1000ゴールドで購入
  2. Aさんが1000ゴールド消費し商品を獲得
  3. Bさんが1000ゴールド獲得

というような一連の取引を指します.銀行のシステムなどでよく使われる言葉です. インターネットの世界では何があるかわからないので手順2と3の間で回線が切れてしまう可能性もあります.

そうした場合Aさんが1000ゴールド消費したにもかかわらずBさんは何も得ていないことになってしまい不整合が発生します. そのためにもDBやプログラムでこのトランザクションを途中で失敗したら状態を戻して0から取引をやり直す というような処理にしてあげなくてはなりません.

こういうった処理は非常に厳密にやらなくてはならないので大変です.

更に旅人バザーは全サーバ共通となっているので全ユーザが日夜取引を行うことでその負荷は最早現実世界の銀行システムと何ら変わらないのではないのでしょうか. 驚くべきはこういったシステムを銀行システムの開発者でもないオンライゲーム開発者がやっているということです.

同じ開発者からして,その大変さは推して図るべしとでもいいましょうか.とにかく凄いです.

Kyoto Tycoon

Kyoto TycoonはインメモリKVSというものです. 立ち位置としては毎回DBのアクセスするのは負荷がかかるので読み込み頻度が高く,更新されにくいデータなどはこちらに保存しておいて読み込ませることで,負荷の分散と読み込みの高速化を図っているという感じです.

TycoonとExadataが上手く協力して落ちないシステムを構築しているわけですね.

この章ではアイテム情報テーブルの構造なども書かれていますがそれは読んで確かめてみてください(書くのがだるい).

まとめ

僕が技術的に面白いなと思ったことをさらっと触れてみました. 移動干渉については少し濃密すぎるしどう考えても簡単にかけないので省きました.ぜひ買って読んでみてください.

プログラマの視点から見てもユーザーの視点から見ても本当に面白い本でした

というわけで安西先生!バトマスは天下無双が強化されて非常に楽しいです.ただ,はやぶさ斬り も強化してくださいお願いします

【Tensorflow with Keras】 Warning on loading model

妙にハマったのでメモ

Kerasでweightを保存してロードしようとした

Save

model.save_weights("model.hdf5", save_format="h5")

Load

model.load_weights("model.hdf5")

これでロード時にWarinigが出た

2019-03-28 03:56:35.810375: W tensorflow/core/util/tensor_slice_reader.cc:95] Could not open model.hdf5: Data loss: not an sstable (bad magic number): perhaps your file is in a different file format and you need to use a different restore operator?

ちゃんと保存したはずなのにフォーマットが違うと怒られる

調べてみると次のようなissueが上がっていた

github.com

上記の処理は Tensorflow-gpu 1.12 で行なっていたがこのバージョンでもまだ修正されていなかったらしい

なので拡張子を hdf5 => h5 に修正したらうまくいった.

普通にファイル読み込んでヘッダ確認する実装にすればいいじゃんと思ったけどなんでそうしなかったんだろう・・・

【自分用まとめ】Google Developers ML Summit

Google Developers ML Summitに忍び込んできたので一応まとめる

Keynote

Edge TPU

  • 250画像/sec をシステムで処理してる
  • 60%のコストカットに成功

MLKit

  • ビジネスはわかるけどMLはわからないとかのためにある
  • 機械学習全部はできないけど色々やりた人向け
  • Disney e-shop Auto-ML使ってレコメンドの改善を行なっている

30分でわかる機械学習

  • 理研が猫の小脳ぐらいをスパコン使ってようやく再現できたくらい
  • 機械学習とはデータから賢さを得る技術
  • 既存のデータから特徴量抽出するのもあり
  • 機械学習は絶対どこかで間違える.
  • あくまで人間の生産性を高めるためのサポータ的な立ち位置が重要かもしれない
  • Tensorflow playground 入門として良さそう

Tensorflow 2.0

  • OpenImages dataset 50万ぐらい
  • Cloud AI Platform <= カスタムモデルの開発効率化(これよさそう)

ここまで書いて,疲れたのでもういいかなってなった. 技術的に超絶深いところに突っ込んだ話はあんまりなかった気がするしあとでスライドも公表されそう(知らないけど)なのでまあいいかなって.

Tensorflow 2.0はMirrored Strategyが個人的に一番気になる.どれだけ分散学習のコードが抽象化されて実装しやすくなっているかはDeveloperとして非常に興味深い

また,2.0では既存のモジュールに破壊的変更が加わるので既存のコードはどうなるのだろうと思ったら,ちゃんとコードを書き換えるツールを用意してくれるっぽい. さすがGoogle www.tensorflow.org

午後のCode Lab

午後のハンズオンではTensorflowのセッションに参加してきた. 基本的にTensorflowやNNの理論は嫌っていうほど触れてきたのでわかっていたつもりだったがやはりDeveloper Advocateによる説明は格段にわかりやすかった

ハンズオンでやったコードは以下のリンクにある. 本当に機械学習に触れたことないプログラマでもここからやればNNやTensorflowのコーディングの基礎はほぼ大丈夫なのではないだろうか.

Codelabs from #GoogleMLSummit – Laurence Moroney – Medium

基礎的な一次関数の重みを更新していくNNからCNNの実装までをkerasを用いて行う.

Colabは何回か使ったがこのクオリティを無料で使えるのはすごいと思う. Tensorflow playgroundもそうだがGoogleが儲かるお陰でこのシステムを無料で使えるというのはインターネット広告様様である.

まとめ

  • Tensorflow 2.0 早く正式リリースしてほしい
  • Cloud ML Engine ちゃんと調査して使おう
  • ユースケースやモデルが既存のもので簡単そうならML Kitでモデルを探して使ってみればよさそう.なくてもカスタムモデルデプロイできるらしい
  • Google公式がkerasがんがん使えみたいなオーラを感じたので存分に抽象化されたモジュールで楽しよう
  • GoogleがTensorflowやその他エコシステムをオープンにするのは他のDeveloperにもっと機械学習のプロダクトを作ってほしいから. Let's Machine Learning.
  • 弁当美味しかったです.

Pythonで型検査しようぜ

やりたいこと

  • Pythonのコードを書く際に型注釈と型検査を用いることで,実行前にバグなりそうなエラーを潰す
  • 他の人が読むとき処理を追いやすいコードを書く
  • 型の重要性を知ってもらう

背景

今はPythonでgRPCのapi書いたり, 機械学習のコードをぶん回したりしてるのでPython漬けの生活です.

「退屈なことはPythonにやらせよう」

なんて言われるぐらいには書きやすいPythonですが,しかし,書きやすさと読みやすさ, 安全性が比例するとは限りません.

OSSやプロダクトにおけるコードというのは書くことより読まれることの方が圧倒的に多いです. それなら多少の利便性は犠牲にしてもシンプルな文法や安全な規則で読みやすさや実行の安全性を担保するべきです.

その結果としてGoやRust, 少し異なりますがTypescriptなどが現在流行っているとも思っています.

例として次のようなPythonのコードを見てみます.

name = "hoge"

print(name)

name = 1

print(name)

こういうコードは割とよくあります.完全にnameが意味することが変わっています. 上記は1個目の代入文と2個目の代入文が近いのですぐに意味が書き換わっていることがわかりますが,プロダクトのコードだったら二つの代入文の間にたくさんの処理が挟まったり,関数内の副作用で書き換わる可能性もあります.

ではもう一つ例をみてみます

class A:
    def name(self):
        print("A")

class B:
    def name(self):
        print("B")


a = A()
a.name()

a = B()
a.name()

このコードが動くということがどれだけ恐怖なのかはGoのような静的型付け言語を書く人ならよく理解できるのではないでしょうか.

これはpythonrubyのような動的型付け言語でよくある問題です. こういった型の束縛を無視したコードは絶対に潰すべきです.

今回は可読性と実行時の安全性を担保するためにPythonにおける静的型検査と型注釈の導入について述べようと思います.

型とは

まずプログラミング言語における型とは一体なんでしょうか.

そもそもプログラムが扱う値というものはコンピュータから見ればただのメモリやハード上のバイト値です.

型はそのメモリ上に連続するバイトの塊の解釈の仕方を変えることで人間に扱いやすくするものという認識です.

0x01 => int: 1, char: 'a'

このような感じですね. 型というものがあるおかげで私たちはプログラムでより複雑かつ抽象的なロジックを記述できるようになりました.

型安全

型は現代の高級プログラミング言語における式評価において重要な意味を持ちます.

一つ例をあげてみます

#include <stdio.h>
#include <string.h>
int main(void) {
    int i = 1;
    char c = 'a';
    
    // int + char = ?
    printf("result = %d\n", i + c);

    // segmentation fault
    strlen(i);
}

このcのプログラムをコンパイルして実行してみます.

type_checker git:(feature/mypy) ✗ gcc type.c                                                                                                       
type.c:11:12: warning: incompatible integer to pointer conversion passing 'int' to parameter of type 'const char *' [-Wint-conversion]
    strlen(i);
           ^
/usr/include/string.h:82:28: note: passing argument to parameter '__s' here
size_t   strlen(const char *__s);
                            ^
1 warning generated.
type_checker git:(feature/mypy) ✗ ./a.out 
result = 98
zsh: segmentation fault  ./a.out

コンパイル自体はwarningが出ていましたが, 成功しています. しかし, 実行は途中でセグフォッています

まず, int + charの足し算が成立してしまうこと自体結構アレですね.

セグフォの原因はstrlenに渡したiがint型なのでstrlenではcharのポインタだと思っていてそのポインタ(おそらく 0x01)にアクセスしようとしたら当然権限外なので落ちたわけですね.

c言語はこのように暗黙の型変換や型における意味論の未定義動作から型安全な言語はありません. 型とはプログラミング言語の構文規則上は大丈夫でも, 式の意味を正しく評価するために存在しているわけです.

なんでもありにすると開発者も大変ですからね.

Pythonにおける型安全

ではPythonにおける型はどうなのでしょうか

Python は実行時に型の代入, 評価を行う動的型付け言語です.

最初に挙げたコードが動いてしまうことから不安はありますが, 次のようなコードはしっかり落ちます

Python 3.7.1 (default, Dec 14 2018, 13:28:58)
[Clang 4.0.1 (tags/RELEASE_401/final)] :: Anaconda, Inc. on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 + "hoge"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'

なのでpythonも変数の型束縛がないことを除けば, ほぼ型安全な言語だと言えます.

中間まとめ

ここで一旦今までのことをまとめてみます

  • 型はプログラムが構文的に正しくても式の意味が正しいかをチェックするための重要な要素(式における型の評価規則を定義したものを意味論という)
  • C言語のような言語は型安全ではない.
  • pythonは変数の束縛がないので若干怪しい部分もあるがほぼ型安全.しかし, インタプリタ言語なので実行時までそのエラーはわからない
  • ただし, 変数に型を指定することがないので可読性は低い

というわけで最初にも言ったように, 静的型検査とPython3.5から導入された 型注釈(Type annotation) を導入することによって以下のメリットを提供します

  1. 可読性の担保: 新しい開発者の参入障壁を下げることにも繋がります
  2. プログラマの意識改善(Pythonだからという理由で書き捨てのコードになっていい理由はない).
  3. 実行前に型エラーを検出することでデバッグの手間を減らす

実際に導入する

型注釈

Python3.5から次のような記法がサポートされるようになりました

def add(x: int, y: int) -> int:
    return x + y

引数の値と返り値の型を記述できます. これだけでもかなりコードは読みやすくなります.

しかし, 実行時に特に制限はかかっていないので上記のコードを次のように変更しても実行はできます

def add(x: int, y: int) -> int:
    # return x + y
    return "hoge"

if __name__ == '__main__':
    add(1, 1)

そこで mypy という型チェックツールを導入します

インストールは pip install mypy でOKです

先ほどの間違ったコードに対して検査をかけます

type_checker git:(feature/mypy) ✗ mypy example_type.py
example_type.py:3: error: Incompatible return value type (got "str", expected "int")

ちゃんと定義した返り値の型と違うと怒ってくれています

また, 次のような定義済み変数の型を書き換えてしまう現象もしっかり検出できます

class User:
    def __init__(self, name: str) -> None:
        self.name: str = name
    
    def change_name_type(self, id: int) -> None:
        self.name: int = id

if __name__ == '__main__':
    u: User = User("katsuya")
    u.change_name_type(1)
    print(type(u.name))
type_checker git: 
main.py:6: error: Incompatible types in assignment (expression has type "int", variable has type "str")

これで概ねやりたことは可能になりましたので今実装中のコードに入れたりしてみました. いい感じにやばそうなコードを検出してくれます.

小ネタとして関数ポインタのように引数を扱いたい場合はこんな感じで定義します

from typing import Callable
def load_network(scale: int) -> Callable[[tf.Tensor, bool, bool], tll.InputLayer]:
    if scale == 2:
        return network2
    elif scale == 4:
        return network4
    else:
        return network4

ただ, mypyは型注釈したコードのみを検出して評価するので型注釈のないコードで型エラーがあっても素通りしてしまいます. しっかりと開発者が型注釈を用いること前提です.

また, 型の不一致などがあっても, 実行自体はできてしまうため, デプロイ前には必ずmypyによる検査を挟んでエラーがあれば実行しないというようなスクリプトを組む必要があるでしょう.

所感

可読性と実行前に安全性を担保するためにmypyと型注釈の導入を試しましたがかなり良い感じだと思います.

あとは開発者やレビュアーが型注釈に対しての心構えを持つこととmypyを用いたデプロイフローを用意すればより堅牢なPythonアプリケーションを実装することができると思います.

参考文献

Go言語でつくるインタプリタを読み終えて,独自拡張した話

Go言語でつくるインタプリタを漸く読み終わりました.といっても実際には1月末には終わっていて単純に記事にするのを忘れていただけなんです.

実際にコードを書きながら読んでいたのですが,リポジトリのログを遡るとファーストコミットは2018/6/24になってました. およそ半年と1ヶ月ほどでしょうか.合間合間にすすめていたのですごい時間かかってますね.

でも本当に良い本でした. 本書でも述べられている通り,Brainf*ckとかじゃなく割とちゃんとした,でもそこまでヘヴィじゃない言語仕様のインタプリタフルスクラッチで作るというのは中々ありませんでしたから.

独自拡張の話

で,本題なんですが本書では最終的にハッシュと組み込み関数の実装で終わっています(付録としてマクロの実装もある)

その時点で動くプログラムはこんな感じ

let map = fn(arr, f) {
    let iter = fn(arr, accumulated) {
        if (len(arr) == 0){
            accumulated
        } else {
            iter(rest(arr), push(accumulated, f(first(arr))));
        }
    };
    iter(arr, []);
};
let a = [1,2,3,4];
let double = fn(x) { x * 2 };
map(a, double);

配列要素をmap関数で2倍ずつしていくというプログラムです. これでも結構プログラムっぽいですが,次のようなコードは動きません.

let fizzbuzz = fn(n) {
    for (let i=1;i<n+1;++i) {
        switch {
            case i % 3 == 0 && i % 5 == 0:
                puts("FizzBuzz");
                break;
            case i % 3 == 0:
                puts("Fizz");
                break;
            case i % 5 == 0:
                puts("Buzz");
                break;
        }
    }
};

fizzbuzz(15);

典型的なFizzBuzzです.このプログラムを動かすのに何が足りないかというと for文, switch case文, インクリメント演算子(++), バイナリ演算子(&&) です. あと % 演算子もなかった気がする

結構足りないですね.本のコードを写経して動きを理解するだけでもインタプリタの言語処理系の実装を理解するには十分だとは思いますが,折角なので以上の要素を頑張って実装してみました.

これらの要素を説明していくのに二段階に分けます.1つ目はASTの生成である構文解析と実際に処理を行う評価の部分です

For文

構文解析

まず, ASTの定義コードを示します

// ForExpression
// original expression
// for(<statement>;<expression>;<statement>) {
//     <Block Statements>
// }
type ForExpression struct {
    Token           token.Token // 'for token
    InitStatement   Statement   //
    FinishCondition Expression
    LoopStatement   Statement
    Consequence     *BlockStatement
}

初期化部分がstatementになっているのは let i = 1 みたいなのを許容したいからです. 逆に終了条件のところは必ず式にするように制限しています. ここはお好みで変更できるので実装者によるでしょう. ループ条件も初期化部分と同様です. 中括弧の中にはループ中に実行される文が配列で格納されます.

評価

func evalForExpression(node *ast.ForExpression, env *object.Environment) object.Object {
    forEnv := object.NewEnclosedEnvironment(env)
    initEvalResult := Eval(node.InitStatement, forEnv)
    var result object.Object
    if isError(initEvalResult) {
        return initEvalResult
    }

    for {
        isFinishObj := Eval(node.FinishCondition, forEnv)
        isFinish, ok := isFinishObj.(*object.Boolean)
        if !ok {
            return newError("finish condition is not boolean")
        }
        if !isFinish.Value {
            return result
        }
        result = evalBlockStatement(node.Consequence, forEnv)
        loopEvalResult := Eval(node.LoopStatement, forEnv)
        if isError(loopEvalResult) {
            return loopEvalResult
        }
    }
}

env変数はスコープ外の変数などを保持しているマップです. 先程のastで取得した初期化条件,終了条件ループ条件を元に実際にforループを回します. for文が終わった際にはresult変数に最後のループで実行された文の結果が格納されて返されます.

SwitchCase文

本書ではIf文を実装していますが,else ifのような無限に続けていく書き方はサポートしていませんでした.そちらを拡張しても良かったのですが折角なので綺麗に見えるSwitchCaseを実装してみました.

構文解析

まずはASTの定義を見ます

type SwitchStatement struct {
    Token      token.Token
    Expression Expression
    Case       []*CaseStatement
}

type CaseStatement struct {
    Token      token.Token
    Condition  Expression
    Statements []Statement
}

さて,Switch文はSwitchとCaseそれぞれに分けました. なぜこうしたかは若干おぼろげですが,確か一つの構造体に詰め込むと解析がすごい面倒くさいことになりそうだったからだと思います.すいません

で,解析処理は以下のようになります

func (p *Parser) parseSwitchStatement() ast.Statement {
    stmt := &ast.SwitchStatement{
        Token: p.curToken,
        Case:  []*ast.CaseStatement{},
    }
    if !p.peekTokenIs(token.LBRACE) {
        exp := p.parseExpression(LOWEST)
        stmt.Expression = exp
    } else {
        stmt.Expression = nil
    }
    p.nextToken()
    for !p.peekTokenIs(token.RBRACE) {
        p.nextToken()
        switch {
        case p.curTokenIs(token.CASE):
            s := p.parseCaseStatement()
            caseStmt, ok := s.(*ast.CaseStatement)
            if !ok {
                return nil
            }
            stmt.Case = append(stmt.Case, caseStmt)
        }
    }
    p.nextToken()
    return stmt
}

func (p *Parser) parseCaseStatement() ast.Statement {
    stmt := &ast.CaseStatement{
        Token:      p.curToken,
        Statements: []ast.Statement{},
    }
    p.nextToken()
    exp := p.parseExpression(LOWEST)
    stmt.Condition = exp
    if p.peekTokenIs(token.COLON) {
        p.nextToken()
    }
    for !p.peekTokenIs(token.BREAK) {
        p.nextToken()
        caseStmts := p.parseStatement()
        stmt.Statements = append(stmt.Statements, caseStmts)
    }

    return stmt
}

Switch文は switch <expression> { [case statement] } のようになっていて最初のexpressionに関してはあってもなくても良いです. 単純にGoっぽくしたくて入れました

case文はbreakなしだと終了の判定が若干面倒くさかったので甘えて入れました.それ以外は基本的にFor文やIf文と解析の手法は変わりません.

評価

func evalSwitchStatement(node *ast.SwitchStatement, env *object.Environment) object.Object {
    for _, c := range node.Case {
        conditionValue := Eval(c.Condition, env)
        condition, ok := conditionValue.(*object.Boolean)
        if !ok {
            return newError("case condtion value is not boolean. got=%T", conditionValue)
        }
        if condition.Value {
            var result object.Object
            for _, s := range c.Statements {
                result = Eval(s, env)
            }
            return result
        }
    }
    return nil
}

こちらの評価処理は全然難しくなかったです. C言語よろしく,Case文の条件を上から判定してマッチしていたらCaseAST内部のBlockStatementを評価していくという感じです.

その他の演算子

++ 演算子は上記のFizzBuzzのように ++<Integer Object> とするようにしています. 前置にした理由は後置にすると実質中置演算になって演算子の優先順位を考慮しなきゃいけなくて面倒くさかったからです.ごめんなさい

&& 演算子の解析もAST生成は既存のコードに条件を足すだけなので難しくありません

評価に関しては若干追加したので載せておきます.

func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    case left.Type() == object.STRING_OBJ && right.Type() == object.STRING_OBJ:
        return evalStringInfixExpression(operator, left, right)
    case operator == "==":
        return nativeBoolToBooleanObject(left == right)
    case operator == "!=":
        return nativeBoolToBooleanObject(left != right)
    case operator == "&&" && left.Type() == object.BOOLEAN_OBJ && right.Type() == object.BOOLEAN_OBJ:
        return evalBinaryOperand(operator, left, right)
    case left.Type() != right.Type():
        return newError("type mismatch: %s %s %s", left.Type(), operator, right.Type())
    default:
        return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
    }
}

この処理は中置演算式の評価部分ですが,&& の左辺右辺は絶対にBoolオブジェクトであると制限して評価します. あとは簡単で,

func evalBinaryOperand(operator string, left, right object.Object) object.Object {
    leftVal := left.(*object.Boolean).Value
    rightVal := right.(*object.Boolean).Value
    switch operator {
    case "&&":
        return &object.Boolean{Value: leftVal && rightVal}
    default:
        return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
    }
}

こんな感じで実際の値を評価します. || 演算子とか足したければtokenを追加してcase文も追加すればOK % 演算子も追加しましたが他の +-*/ と同様なので省きます.

実際に実行してみる

これらを実装して,先程のFizzBuzzを実行してみると次のようになります

f:id:kk_river108:20190226114604p:plain

いい感じに出力されていますね. 最後のnullはputsの評価値を表示しているものです.

まとめ

非常に参考になり,翻訳も丁寧で原著のテンポの良い文章がそのまま楽しめた気がします. また,実際のコードもインタフェースを十全に使っているおかげで自前の拡張もかなりスムーズに行えました. 言語処理系を実際に作るというのは結構ハードルが高そうに見えますが,コンパイラとかはともかく,インタプリタは実装する言語でそのまま実行するので入門としてはかなり良い教材なのではないでしょうか?

作っている最中に普段「どうしてこんな構文なんだろ?」と思うプログラミング言語の仕様も実は実装者の苦悩の果に辿り着いたものなのだという一種の共感すら湧くようになりました.

皆さんも良ければインタプリタを作って見てください

最後に書籍のリンクと今回自分が実装したコードへのリンクを張っておきます.

github.com

Amazon CAPTCHA