TIM Labs

1024によるエントリー一覧

Haskell は純粋であるだとか、参照透過性を満たしているだとかよく話題になる。参照透過性を満たしているということは、同じ関数に同じ引数を渡せば、いつ、誰が簡約しても結果が変わらないということを意味している。いつ簡約しても結果が変わらないということは、並列に簡約しても良いわけだし、逆順に簡約してもいいわけだし、コンパイル時に簡約したっていいわけだ。じゃあ、以下のコードが、常に HELLOWORLD を出力し、 WORLDHELLO となることはない理由は何なのか? putStr "WORLD"putStr "HELLO" よりも先に簡約したって良いのでは?

do
  putStr "HELLO"
  putStr "WORLD"

実際のところ、「IO モナドってのは特別なんだ」とかそういう理解であっても、とりあえずモノを作るにはそんなに困らない。だいたいそう動くし、そういうもんだと思っていれば十分である。

でも、どういう仕組みなのかやっぱり気になるよね? そんな人のために、ちょっと大変だけど、このプログラムを手で簡約してみたいと思う。自分で簡約し、ついでに実行もして、実際に HELLOWORLD が出力できれば、ある程度の納得を得られるはずだ。

少し前までは Haskell はインストールが非常に手間がかかる上に、ライブラリ類のバージョン整合性をとるのが非常に困難なのが大きな欠点だったのだが、 Stack なるビルドツールが現れてからはその点が一気に解消されて大変便利になった。コンパイル時に様々な問題を一気に洗い出してくれる Haskell は、書いている自分でも驚くほど正しく動くし、変更にも強い。言語の選択はもちろん適材適所なので一概には言えないが、堅牢なプログラムを素早く書くという観点ではお勧めできる言語だ。

しかし一方で、Haskell で書かれたプログラムにはパフォーマンスバグ(時間、空間、あるいはその両方)が含まれていることも多い。ビルドさえできればたいてい「正しく動く」が、意図したパフォーマンスが得られなかったり、余計なメモリを消費し続けたりといったことでは片手落ちである。

今回は、そんななかでも並列プログラミングを行う場合に遅延評価が問題となる例とその解決法を紹介する。

RAII の話題は C++ の例が多いが、それもそのはず、ここ最近は GC が面倒を見てくれることがほとんどなので、 RAII の需要そのものが減っている。とはいえネットワークコネクションやらファイルハンドルやらと、あまりリソース解放のタイミングを遅らせたくないものに関しては、 RAII パターンで寿命を明示しておきたいのは GC があったとしても同じこと。

Ruby もそういったリソースに関してはブロックを渡すことで解放もしてくれる RAII パターンを実装したインターフェースが提供されているので、積極的に使っていきたいところだ。そういったリソースがひとつだけなら、素直に書けばいいだけのことなのであまり考える必要はない。

open(...) do |fp|
  something(fp)
end # ここでファイルハンドルが解放される

ところが、配列になっているものに対し、すべての要素を開き、同時に使いたいとなると意外と面倒なことに気付く。配列 arr = [a1, a2, a3, ...] があったとき、意味的にはこういうことがしたい。

open(a1) do |b1|
  open(a2) do |b2|
    open(a3) do |b3|
      ...
      something([b1, b2, b3, ...])
    end
  end
end

が、配列の要素数がわからない以上、この方針でネストを続けていくわけにはいかない。 果て...。どうすればいいだろう?

巷では「ズンドコキヨシ」というプログラミング課題が流行っているらしい。そりゃなんぞや、というところだが、要点としては《「ズン」「ドコ」のいずれかをランダムで出力し続け、「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ!」と出力して終了するプログラムを作成せよ》ということになるだろうか。既に多くの方が挑戦しているようで、以下にまとめられている。

ズンドコキヨシまとめ

すっかり波には乗り遅れている感じではあるが、それはともかくとしてもプログラミング課題としてとてもセンスが良い。ざっと思いつくプログラミング上のポイントは

  • 文字列出力
  • 乱数利用
  • 状態管理
  • 繰り返し、およびその中断

あたりだろうか。ツボを押さえたとても良い課題である。

というわけで、是非やってみたい。そう、敢えて、「手続き型」 Haskell で。

と、こんな表題で書くからには当然、「等価ではないこともある」と言いたいわけだが、その前に一般的な話をおさらいしておこう。

Ruby では表題の通り、 method1 { |e| e.method2 }method1(&:method2) は基本的に等価だとされる。こんな感じだ:

[1,2,3].map { |e| e.to_s } # => ["1", "2", "3"]
[1,2,3].map(&:to_s)        # => ["1", "2", "3"]

どちらの書き方が良いのか、というのは人やプロジェクトなどによりけりではあるが、後者のメリットのひとつとして「ブロック内の変数を命名しなくて良い」というものがある。我々ソフトウェアエンジニアにとって命名とは一般的に重労働であり、その労働力はできればもっと重要な箇所で使いたい。そんなわけで我々としてはできれば後者の記法を利用していきたいわけである。

ところが表題の通り、この二つは必ずしも同じ挙動になるとは限らない。実際に二つほど発見したので紹介しよう。

早速だが、コードを見てほしい。ネットワークデータを一旦ローカルの一時ファイルに受け取り、後でゆっくり読み書きしよう、という意図のコードだ。呼び出し元はファイルハンドルを受けとり、シークを含めた読み書きができる、というか、したい。

def create_tempfile(*)
  network_source = ... # 省略
  Tempfile.new("example").binmode.tap do |file|
    IO.copy_stream(network_source, file)
    file.rewind
  end
end

ところが、このコードには問題がある。普段何も問題なく動くのに、時折このメソッドから受け取るファイルに対して操作をしようとしたら IOError が発生することがある。しかもこのエラーは環境や時間、扱うデータによって発生したりしなかったりするし、スタックトレースはなにやら所謂ライブラリ類の奥深く。そもそも問題の原因がここであることを突き止めるにも一苦労があったわけだが、えーっと、現場の苦労話はさておきだ、とにかく「問題の原因はこのコード」、「発生している例外が持つメッセージは "closed stream"」である。

どう直せば解決するか、分かっただろうか?

先日 GHOST と呼ばれる glibc の脆弱性が発表された。なんでも、「リモートから任意のコードを実行できる可能性がある」らしいではないか。しかも様々なプログラムで利用されているライブラリ部分の問題とあって、影響範囲がとても広い。なかなか厄介なことである。

はて、しかし一体全体どうやってリモートから任意のコードを実行しようというのだろう? 話を聞くに、たかが数バイトの情報を範囲外のメモリに書き込める可能性があるだけだという。実際それだけのことでサーバーの乗っ取りなどできるものなのだろうか。そんなわけで、その疑問に答えるべく、本記事では以下の URL で解説されている実際の攻撃方法を若干端折って紹介してみようと思う。

http://www.openwall.com/lists/oss-security/2015/01/27/9

なお、本記事はこの脆弱性そのものに対する緊急度などについて言及するものではないし、実際に攻撃を行うことを推奨するものでもない。くれぐれも攻撃に用いたりしないようご注意願いたい。また、脆弱性そのものに対する適切な対応などについては、専門機関や専門家の指示や勧告に従って欲しい。

こんな感じにデータを持ってる sample_table があるとする。

+----+----------+------------+---------+
| id | group_id | updated_at | comment |
+----+----------+------------+---------+
|  1 |        1 | 2013-12-01 | C       |
|  2 |        2 | 2013-12-01 | A       |
|  3 |        1 | 2013-12-02 | B       |
|  4 |        2 | 2013-11-30 | D       |
+----+----------+------------+---------+

MySQL で同じデータを作成したければ、以下の SQL で再現できる。

CREATE TABLE sample_table (
    id int(11) NOT NULL,
    group_id int(11) NOT NULL,
    updated_at date NOT NULL,
    comment varchar(60) NOT NULL
);
INSERT INTO sample_table VALUES
    (1, 1, '2013-12-01', 'C'),
    (2, 2, '2013-12-01', 'A'),
    (3, 1, '2013-12-02', 'B'),
    (4, 2, '2013-11-30', 'D');

こんなデータのとき、同じグループ内であるフィールドが最大(あるいは最小)のレコードを取得したい、ということがたまにある。例では、group_id それぞれについて、 updated_at が最新のレコード、即ち comment が A および B のレコードを取得したいとしよう。

さて、どんな SQL を書けばよいだろう?

Rails のバリデーションには特定のコンテキストのときだけ実行させることができる on オプションが存在している。

validates :field1, presence: true
validates :field2, presence: true
validates :field3, presence: true, on: :admin

こうすると、 valid?(:admin) のときだけは全てのフィールドが必須入力となるが、そうでない場合は field1field2 のみ必須となり、 field3 は任意入力になる。なるほど、便利だ。

ところが、これを逆転させたいとき、即ち :admin コンテキストのとき「だけ」field3 を任意入力にしたいとなると、途端に面倒なことになる。

validates :field1, presence: true
validates :field2, presence: true
validates :field3, presence: true, on: [:create, :update, :context_foo, :context_bar]

おおう。これ、 :context_baz が増えたら、ここもメンテナンスせなあかんのか? ちょっとそれはなくない? このコードからは「:admin コンテキストの時だけ任意入力」という意図が全く読み取れない(そもそも :admin が出てこないではないか)ので、適切にメンテナンスするのは無理がある。

前回、無理数の取り扱いを複素数的な考えで取り扱ってフィボナッチ数列の一般項を求めた。意味的にはさほど遅くないはずの実装ではあるが、それでも 100,000,000 番目を求めようとすると結構時間がかかってしまう。実際に計測するとこんな感じだ。

90.67s user 0.21s system 99% cpu 1:30.94 total

チューニングの余地があるのは恐らく素朴に書いた累乗計算、fibExp だ。素朴と言っても一応アルゴリズム的な考慮はしたつもりだが、とはいえ言語について詳しく知っているわけでもなし、色々素人が小手先のチューニングを施すよりも、標準ライブラリに任せたほうがこういうものは余程パフォーマンスがいいものと相場が決まっている。

Haskell での累乗計算は (^) を使う。GHCi に聞いてみると、

> :i (^)
(^) :: (Num a, Integral b) => a -> b -> a       -- Defined in `GHC.Real'
infixr 8 ^

ということなので、a が Num クラスに属してさえいれば、a はなんだっていい。ということは、前回の FibNum を Num クラスのインスタンスにしてしまえばいいわけだ。それさえできれば標準の (^) が独自の型にも適用できるようになる。素晴らしい。

このアーカイブについて

このページには、1024が最近書いたブログ記事が含まれています。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。