就職しました
本日、Tsuru Capitalのポジションを得ました。
Tsuru Capitalはデリバティブの取引を行っている企業で、自動株取引の会社ではありません。取引に関わっている10人のメンバーのうち、創始者であるSimonを除く全員がHaskellerで、取引状況の分析や一部の取引の自動化など、あらゆるところにHaskellを使っているのが大きな特徴です。日本では数少ない、Haskellをメインに使っている企業の一つでもあります。
東京、シンガポール、バンクーバーにオフィスがあり、東京には私を含む5人の開発者と事務担当、Simonと愛犬テトがいます。
オフィスはオランダヒルズ森タワーRoPにあります。設備が非常に充実しており、東京に引っ越すまではオフィスに週数度の頻度で泊まっていました。風呂上がりにジンジャエールをラッパ飲みしながらサーバールームの熱風で体を乾かすと、すごく気持ちが良いです。 職場の雰囲気は非常にカジュアルで、テトと遊んだり時々昼寝したりすることもあります。エスプレッソと炭酸水が好きなだけ飲めるのもよいところです。
仕事
「Tsuru Capitalのインターンに応募してみよう」と思い応募した二日後に面接を行い、次の週から3カ月間インターンとして働くことになりました。面接ではマルチメディア関連のスキルについて話していたこともあり、最初のほうは主に取引状況を見るためのGUIの開発をしていましたが、最近は実際のトレードに関わるものも含めいろいろな部分に手を加えています。タスクは多種多様で、プログラムを書くのが楽しいです。私は抽象的なコードを扱うのが得意なので、そこをさらに活かせるよう頑張っています。
ソースコードについて
Tsuru Capitalの社内のコードはかなり高品質だ思います。lensやlinearなどの比較的先進的なライブラリも活用しています。尖ったリファクタリングにも寛容で、いつでも新鮮さを保っています。取引をする上ではパフォーマンスが損益に直接関わってくるため、チューニングは丹念になされていますが、もちろんHaskellerらしく抽象化は怠っていません。
とはいえ、今までストリームの処理にはレトロ感あふれるiterateeと社内ライブラリを組み合わせて使っており、お世辞にも保守しやすいとは言えないものでした。そこで、私は新たなライブラリを開発し、古いコードを徐々に置き換えています。一筋縄ではいきませんでしたが、コード量が削減されただけでなく、パフォーマンスの向上も見られました。具体的な話は来月の関数型ストリーム処理勉強会のために残しておきましょう。
私はHaskellが好きです。一番好きなプログラミング言語であるHaskellで仕事ができるのは非常に嬉しいことでもあります。開発を通じて得たノウハウをただ仕事に生かすだけではなく、これからも記事やオープンソースソフトウェアとして世界に発信していきます。
カリー化
鍋にオリーブオイルを入れる。
にんにくを細切りにし、入れる。しょうがを少しすりおろす。いつもの流れである。
玉ねぎの半分をみじん切りにし、鍋に入れ、しばらく炒める。
キャベツ、にんじん、ヒラタケ、残りの玉ねぎ、じゃがいも(皮ごと)を大き目に切り、蓋をしつつ少し間隔を置いて順に入れる。
しばらくしたあと、鶏肉を入れる。少量のクレイジーソルトとバターも入れた。
水は少しだけ加え、他は素材の水分に頼る。Vita Craftの性能に期待を寄せる。
市販のカレールウをある程度分割し、まぶすように入れる。6分程度待ち、途中で中身をひっくり返す。
火を止め、しばらく余熱を加えて完成だ。炊き立てのご飯と一緒に皿に盛り、チーズをトッピングして出来上がり。
作る前から分かっていたことだが、汁は少ない。日本で一般的なカレーとは異なる。
しかし、うまい。調理時間は短いが、肉や野菜にしっかりと火が通っており、それぞれのうまみが伝わってくる。芯ごと煮込んだ(蒸した?)キャベツは柔らかく、甘い。
男爵薯の舌触りもよい。外側についた濃い目の汁とのバランスは絶妙だ。
今夜はカレーのようなものを作った。料理は勢いでなんとかなってしまうものだ。
最近作った料理(簡単さ順)
面倒なので写真はなし。
ミニマリスティック卵スープ
- 鍋で水を沸かす。
- 創味シャンタンを1人あたり小さじ半分ほど入れる。塩で味を補う。
- 溶き卵を乱暴に投入する。
賞味期限の近い具材を消費するためのチャーハン
- ごま油とサラダ油を強火で熱したフライパンに入れる。
- 溶き卵を乱暴に投入する。
- 数秒後にご飯を投入する。
- ねぎと薄く切ったにんにくを入れる。
- 創味シャンタンを小さじ半分入れる。
- 適当な具材を入れる。賞味期限が切れそうだったソーセージとキムチを入れた。
- 醤油と黒胡椒で味を調える。
牛丼
- ごま油とサラダ油をフライパンに入れる。
- みじん切りにしたにんにく、少量のおろししょうがを加える。
- ここで七味唐辛子を投入する。
- 揚げるがごとく炒め、香りがいい感じになるのを待つ。
- 玉ねぎと、和風だしの素をごく少量入れ、炒める。
- 水、適量の醤油、三温糖を入れる。
- 牛肉を入れ、火が通るまで加熱する。
備考: 生の唐辛子を使おうと思っていた部分を七味唐辛子で代用したが、案外こちらのほうがよいかもしれない。酒も入れたかったが、筆者が未成年ゆえ入手できなかったため省いた。
lensパッケージのオプティクス(弱い順)
lensではオプティクスと呼ばれる様々な構造が定義されている。これらの関係を把握していれば、ドキュメントから欲しいものを見つけるのが楽になる。この記事では弱い順にオプティックの数々を紹介していく。
Fold
type Fold s a = forall f. (Applicative f, Contravariant f) => (a -> f a) -> s -> f s
Contravariantがついているのでわかりにくいが、これは本質的に以下の型と等価だ。mappend
は*>
、mempty
はfmap absurd $ contramap absurd $ pure ()
に相当する。
type Fold s a = forall r. (Monoid r) => (a -> r) -> s -> r
で、これは何かと言えば、foldMap :: Foldable f => (a -> r) -> f a -> r
の一般化そのものだ。foldMap
はf a
の要素a
を畳み込むが、Fold s a
はs
の中のa
を畳み込む。当然、Foldable
でできることはFold
でもできる。そのあたりはモノイドと継続渡しの道具箱で触れている。
FoldはそのままではfoldMapの一般化としては使いにくいため、Control.Lens.Foldモジュールでユーティリティが定義されている。Foldable
のメソッドとしてfoo
があったとき、Foldable
の代わりにFold
を受け取るfooOf
という関数が提供されている。
Getter
Getterはより強く、Functorしか要求しない。
type Getter s a = forall f. (Functor f, Contravariant f) => (a -> f a) -> s -> f s
こちらは、Applicativeに由来するモノイドの力を必要としないため、forall r. (a -> r) -> s -> r
という関数と等価になる。これはs -> a
という関数を継続渡しスタイルにしたものだ。したがって、Getter s a
はs -> a
と同じものとして見てよい。
view :: ((a -> Const a a) -> s -> Const a s) -> s -> a view l = getConst . l Const
Setter
FoldやGetterと独立した概念としてSetterがある。ASetter
はSetter
型の特殊な場合であるが、本質的な差はない。
type ASetter s t a b = (a -> Identity b) -> s -> Identity t over :: ASetter s t a b -> (a -> b) -> s -> t over l f = runIdentity . l (Identity . f)
こちらは(a -> b) -> (s -> t)
と等価だ。セッターとして使えるが、セットした際の型の変化を許すようになっている。
Traversal
FoldがfoldMap
の一般化だったのに対し、TraversalはTraversable
クラスのメソッドtraverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)の一般化になっている。
type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t
そのため、traverse
やmapM
の代わりを作る感覚でTraversal
を定義できる。例えば、リストの偶数番目の要素に対するtraverseEven
は以下のようになる。
traverseEven :: Traversal [a] [a] a a traverseEven f (x:y:xs) = (:) <$> f x <*> fmap (y:) (elementsEven f xs) traverseEven _ xs = pure xs
Traversal
はFold
であり、Setter
でもあるのが特に重要である。例えばover elementsEven (*3)
は偶数番目の要素を3倍にするし、sumOf elementsEven
は偶数番目の要素の合計を求める関数になる。
Lens
Traversal
が複数の要素を扱うのに対し、Lens
と呼ばれる構造はただ1つの対象しか扱わない。
type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t
Lens
はTraversal
でもあり、Setter
かつGetter
である。レコードのフィールドの表現に使えるだけあって人気も高く、パッケージ名になっているほどである。
Lens
はtraverse
と似たような感覚で作れる。Traversalは0個や複数の要素を扱うのにpure
や<*>
を使うが、要素が1つならばfmap
だけでよいというのはわかりやすい。
Review
ReviewはGetterを逆転させたものだ。回りくどいが、Review t b
はb -> t
という関数と等価である。
type AReview t b = Tagged b (Identity b) -> Tagged t (Identity t) (#) :: AReview t b -> b -> t (#) l = runIdentity . unTagged . l . Tagged . Identity
Prism
type Prism s t a b = forall p f. (Choice p, Applicative f) => p a (f b) -> p s (f t)
Prism
はTraversal
かつReview
である。これは作りにくいので、自分で定義する際はprism :: (b -> t) -> (s -> Either t a) -> Prism s t a b
という関数を使おう。
_Just :: Prism (Maybe a) (Maybe b) a b
_Just
はMaybe
に対するtraverse
としての機能を持つが、Review
でもあるため、_Just # 42
からJust 42
を得るということができる。代数的データ型のコンストラクタと似たような雰囲気で、値を埋め込んだり取り出したりできる。
Iso
type Iso s t a b = forall p f. (Profunctor p, Functor f) => p a (f b) -> p s (f t)
Iso
はLens
かつPrism
であり、こちらは要素が必ず1つあることが保証されている。したがって同型な二つのデータ型にならIso
を定義できる。こちらはヘルパー関数なしでも作りやすい。
enum :: Enum a => Iso Int Int a a enum = dimap toEnum (fmap fromEnum)
Equality
type Equality s t a b = forall p f. p a (f b) -> p s (f t)
Equality
はIso
よりさらに強い。Equality
になる値はid
ただ一つしかないため、型の等価性を表現する。等価性を採取して他の場所に運びたいときに使えるが、その目的ならbase
パッケージのData.Type.Equality
があるため、使う場面はかなり少ない。
まとめ
構造を「使いたい」と思ったときは弱いほうから、「作りたい」と思ったら強いほうから、対応するモジュールを調べてみよう。この力の関係を知っていれば、よりよくlensを活用できるに違いない。
Haskellの型クラスを活用する
Haskellの型クラスは、うまく使えば高いパフォーマンスと抽象度を両立できる、優れた仕組みである。その使い方のコツは、決して理解の難しいものではない。
小さな性質、大きな恩恵
プログラマは大きなものを小さく見せがちだ。オブジェクト指向プログラミングに慣れている人がやりがちなアンチパターンとして、欲しい機能と、それを分割する基準が現実に寄りすぎていて、一つ一つが巨大というものがある。
普通のプログラミングではありえない例かもしれないが、たとえば家を作りたいことを考える。「ベッド」「箪笥」「台所」「冷蔵庫」「トイレ」「風呂」のように設備ごとに分けた抽象化をしたいと考えるだろう。確かにこれは理に適っているように見える。だが、これらの設備を型クラスでまとめるのは悪手だ。
風呂やトイレには水を利用できるという性質が、冷蔵庫には電気が必要だ。部屋と部屋は壁で仕切られ、場合によっては扉があるかもしれない。水を伝えるにはパイプで繋がなければいけない。電気を取り出すにはコンセントで繋ぎ、扉を取り付けるには蝶番がなければ。繋ぐと一言で言っても、その方法は様々である。「繋がれたものは安定して機能を果たせる」という論理的な共通点から、様々な操作を「繋ぐ」という言葉で抽象化している。このレベルの話でやっと型クラスが有用になってくる。
コンパイル時の定め
Semigroup
という型クラスがsemigroups
パッケージで定義されている。これは半群という代数的構造を表すクラスで、二項演算(<>)
を持つ。
class Semigroup a where (<>) :: a -> a -> a
ただし、正当なSemigroupになるには条件があり、どんなa, b, cに対してもa <> (b <> c) == (a <> b) <> c
が成り立たななければいけない。
Semigroupの例として、リストとその結合、数値の足し算や掛け算などがある。()
の場合は何もしない。
instance Semigroup () where () <> () = () instance Semigroup [] where (<>) = (++) instance Num a => Semigroup (Sum a) where Sum a <> Sum b = Sum (a + b) instance Num a => Semigroup (Product a) where Product a <> Product b = Product (a * b)
型さえはっきりしていれば、コンパイル時にインスタンスが選択され、(<>)
はふさわしい実装で置き換えられる。これに関してパフォーマンスで心配する必要はないし、繰り返し使うのにも適している。一方、仮に風呂が型クラスのメソッドだったとしても、風呂をたくさん置く家はあまりないだろう。
実行の前奏曲
GHC 7.10以前は、Preludeのfoldr
などの関数はリスト専用だった。7.10以降は、Foldable
のメソッドとして一般化されている。これによって今までのコードが遅くなる心配をする必要はない。実際にリストに対するfoldr
を含むプログラムを-ddump-rule-rewrites
オプションをつけてコンパイルすると、リスト専用のfoldr
に置換されるのを確認できる。
Rule fired Rule: Class op foldr Before: Data.Foldable.foldr TyArg [] ValArg Data.Foldable.$fFoldable[] TyArg GHC.Types.Int TyArg GHC.Types.Int ValArg GHC.Num.$fNumInt_$c+ ValArg GHC.Types.I# 0 ValArg GHC.Enum.$fEnumInt_$cenumFromTo (GHC.Types.I# 0) i_aqJ After: GHC.Base.foldr Cont: Stop[BoringCtxt] GHC.Types.Int
コンパイル時の置換をより積極的に利用した例としてlens
パッケージも挙げられる。Lensはゲッターとセッターの対から構築されるアクセサである。
lens :: Functor f => (s -> a) -> (s -> b -> t) -> (a -> f b) -> s -> f t lens getter setter f s = fmap (setter s) (f (getter s))
view
やset
は、Lensが使うfmap
をConst
やIdentity
のために特殊化することでゲッター、セッターとしての機能を取り出している。
view :: ((a -> Const a a) -> s -> Const a s) -> s -> a view l = getConst . l Const set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t set l b = runIdentity . l (Identity . const b)
実際に式を変形するとその挙動は明らかだ。lens
パッケージはcoerce
なども併用することで、以下の変形をコストなしで実現している。なんたる業前か!
view (lens getter setter) s = getConst $ fmap (setter s) (Const (getter s)) = getConst $ Const (getter s) -- fmap _ (Const x) = Const x = getter s set (lens getter setter) b s = runIdentity $ fmap (setter s) (Identity (const b (getter s))) = runIdentity $ fmap (setter s) (Identity b) = runIdentity $ Identity (setter s b) -- fmap f (Identity a) = Identity (f a) = setter s b
こうしてみると、型クラスは「複雑な処理をまとめる」というよりは「特定の性質を持つ処理を最適な形で具体化する」ものと見ることができる。たいていの型クラスは半群や関手のような代数的な構造であり、ライブラリとして既に定義されている場合がほとんどである。その観点では、ユーザーである私たちは、あえて新しいクラスを定義する必要は基本的にないのだ。私はHaswerkというMinecraftクローンを開発しているが、今のところ独自のクラスは宣言しておらず、これから作る予定もない。
まずは、Haskellのエコシステムに鎮座する型クラスの数々を最大限に活用しよう。型クラスは抽象化のポータル(玄関口)である。クラスのメソッドを使うことで、あるいはインスタンスを定義することで、互いに再利用できるコードが生まれる――インスタンスが満たす「性質」を頼りにして。
最近やったこと
最近やったことのまとめ。
CPSのモナド変換子
で作ったmtl-cの塵を払い、Hackageにリリースした。
StateTやWriterTは中でタプルを作ったり壊したりしているが、CPS変換するとそれがなくなり、しかも(>>=)
も最適化されるためそれなりのパフォーマンスの向上が期待できる。モナドガチユーザにおすすめだ。
補足 GHC 7.10.1現在、StateTに関しては最適化がうまく効くらしく、Lazy、Strict、CPS版のパフォーマンスはほぼ同じだった。一方、CPS版WriterTは正格にしているためか、Strictの4倍、Lazyの8倍の速度を発揮した。なお、CPS版はベースのモナドが重いときには特に効果的に働く。
後悔なく具現化できるモナド
monad-skeletonというパッケージを公開した。インターフェイスとしては普通のOperationalモナドだが、実装に一工夫がされており、(>>=)
が左結合になってもパフォーマンスが落ちにくい特長がある。
基本となる型Skeleton t
は、命令t
の列がなすモナドである。命令を持ち上げるにはbone :: t a -> Skeleton t a
、命令を取り出すときはunbone :: Skeleton t a -> MonadView t (Skeleton t) a
を使い、MonadView
に対するパターンマッチによってSkeleton
のインタプリタを書ける。
data MonadView t m x where Return :: a -> MonadView t m a (:>>=) :: t a -> (a -> m b) -> MonadView t m b
命令を集めて君だけのモナドを作ろう!
吹きすさび要素を枯らすイテレータ
witherableの新しいバージョンをリリースした。
Traversableクラスのtraverse
は作用を伴った要素のマッピングをするが、このパッケージで定義されているWitherable
はtraverse
の能力に加え要素の削除も抽象化する。Witherableのメソッドを見ればわかりやすい。
class Traversable t => Witherable t where wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b) mapMaybe :: (a -> Maybe b) -> t a -> t b catMaybes :: t (Maybe a) -> t a filterA :: Applicative f => (a -> f Bool) -> t a -> f (t a) filter :: (a -> Bool) -> t a -> t a
幅広く使えそうだが、元々は定命のオブジェクト(死ぬオブジェクト)の集まりを管理する関数apprises
の実装のためだけに作った。
あえてリストで返さずに継続を使う理由については、モノイドと継続渡しの道具箱も参照されたい。
apprises :: (Witherable t, Monad m, Monoid r) => f a -- メッセージ -> (a -> r) -- 結果を回収 -> (b -> r) -- もしくはオブジェクトの亡骸を回収 -> StateT (t (Mortal f m b)) m r -- 定命のオブジェクトのコンテナへの操作
拡張可能なデータ構造
extensibleを更新した。なんといってもextensibleの売りは、今までの拡張可能系ライブラリとは一線を画し、どんな種でも扱えることだ。
extensibleが提供する拡張可能レコードおよびバリアントは以下の種を持っている。
RecordOf :: (v -> *) -> [Assoc k v] -> * VariantOf :: (v -> *) -> [Assoc k v] -> *
v -> *
のパラメータを利用すれば、*
でも* -> *
でも* -> * -> *
でも、レコードおよびバリアントの対象になる。そのおかげで、単純なレコードだけでなく、多相型も使えるExtensible effects、ファーストクラスパターンマッチ、objectiveと組み合わせればクラスベースオブジェクト指向も実装できるぞ。以下はextensibleとaesonを組み合わせ、要素に型の付けられるJSONパーサを実装する例。
objective
Michael Snoyman先生のおかげでインスタンスが例外安全になった(https://github.com/fumieval/objective/commit/ffffc5b7afba88155be9c08c1b8204b7cadfe0a4)。もしオブジェクトが例外を投げたとき、例外を発生させる前のオブジェクトにロールバックする。これによって不正な状態の発生を防ぐことができる。オブジェクト指向の実装で、このようにしてオブジェクトの整合性を保つのはなかなか新しいアイデアだと思う。
また、extensibleと組み合わせてExtensible effectsの実現も試みている。山本和彦さん曰くobjective以外でOperationalモナドが本当に役立つ例を見たことがないそうなので、おそらくobjectiveパッケージの一部として提供することになる。
謎のひも
ファイルから音声を読み込むなど、シーク可能なデータを扱いたい場面がある。相対的なものと絶対的なものを合わせればシーク操作はモノイドになるという点に着目し、実験段階だがtapesというものを実装したが、終端の扱いにまだ疑問が残る。開いたり閉じたりする概念は本質的に難しい。
Haskellでいかに多態を表すか
オブジェクト指向を行使する心 ではオブジェクト指向の必要性と仕組みについて議論した。
インスタンスは言語によって様々な実装方法があるが、大きく分けて「クラス(処理)のインデックス」か「処理そのもの」のどちらかがインスタンスの内部に隠れている。
と述べたが、Haskellの場合、クラスのインデックスに基づいた表現では、インターフェイスは型クラス、クラスはインスタンス、インスタンスは存在量化された型の値に対応する。…といってもややこしいことこの上ないので、実装例を考えてみよう。
まず、問題となっている愚直な実装は、Haskellではこんな感じだ。
data World = World { … } data SceneId = Menu | Map | Battle draw :: SceneId -> World -> IO World draw Menu = … draw Map = … draw Battle = …
Worldは描画に必要なすべての情報が入っている、グローバル変数のようなものと考えてよい。新しいシーンを追加するにはSceneId
とdraw
を両方書き換える必要があるため扱いにくく、シーンではなくキャラクターなどを管理するとなればなおさらだ。
存在量化を用いると以下のように書ける。
data Menu = Menu data Map = Map data Battle = Battle class Scene a where draw :: a -> World -> IO World instance Scene Menu where draw = … instance Scene Map where draw = … instance Scene Battle where draw = … instance Scene SomeScene where draw (SomeScene a) = draw a data SomeScene = forall a. Scene a => SomeScene a
data Menu = Menu
のくだりは若干ばかげているようにも見えるが、定義にシーン固有の値を追加してもよい。各シーンを表す値であるMenu
、Map
、Battle
をSomeScene
で包むと、内部にはインスタンスを識別するためのタグが入り、型を共通にしつつ実行時に処理を切り替えられる。標準ライブラリのControl.Exception
ではこの方法を採用しており、便利ではあるがSomeScene
のようなものを毎回作らなければならないのがいまいちだ。
インスタンスに直接処理を格納するアプローチとしてはHaskell's overlooked object system*1のHListがある。異なった型の要素を持てるリストを用い、操作の直接的な集まりとしてインスタンスを表す。
import Data.HList draw = Label :: Label "draw" type Scene = Record '[Tagged "draw" (World -> IO World)] sceneMenu :: Scene sceneMenu = draw .=. … .*. emptyRecord sceneMap :: Scene sceneMap = draw .=. … .*. emptyRecord sceneBattle :: Scene sceneBattle = draw .=. … .*. emptyRecord
こちらはシーンを値として定義できるのが魅力だ。演算子(#) :: HasField l r v => r -> Label l -> v
でdraw
の処理を呼び出せる。しかしその裏の仕組みがとても複雑なうえ、IORef
などを用いないと状態をまともに扱えないのが難点である。
objectiveはそのどちらでもなく、オブジェクトの中身は「操作を解釈する関数」になっている。
newtype Object f g = Object { runObject :: forall x. f x -> g (x, Object f g) }
あくまで操作とオブジェクトは別の概念として扱うのが特徴で、種が* -> *
ならば任意のデータ型を操作として利用できる。Scene
型のオブジェクトはSceneOp
を受け取りStateT World IO
の型のアクションを生み出す。
import Control.Object data SceneOp a where Draw :: SceneOp () type Scene = Object SceneOp (StateT World IO) sceneMenu :: Scene sceneMenu = Object $ \Draw -> … sceneMap :: Scene sceneMap = Object $ \Draw -> … sceneBattle :: Scene sceneBattle = Object $ \Draw -> …
runObject
にオブジェクトとDraw
を渡すと、オブジェクトはDraw
の結果と次のオブジェクトを返す。これをそのまま使ってもよいが、new :: Object f g -> IO (Instance f g)
を用いてインスタンスを生成することもできる。(.-) :: Instance f g -> f x -> g x
を使うと、インスタンスは次のオブジェクトで置き換わるため、広く使われているメソッド呼び出しも可能だ。
オブジェクトは関数と同様のコンポーザビリティを持ち、既存のオブジェクト指向の実装を超える拡張方法も提供する。具体的な利用については以下のちゅーんさんの記事で詳しく述べられているので、こちらも参照されたい。
存在量化、HList、objectiveは多態を実現するが、それぞれ表現方法は全く異なる。純粋、ファーストクラス、合成可能、この言葉にピンときたらobjectiveを是非使ってみてほしい。
*1:Oleg Kiselyov, Ralf Lämmel , http://arxiv.org/pdf/cs/0509027.pdf, 2008