Hash λ Bye

Haskell, Clojure, MLなどの話

GHCの中間言語Coreへの脱糖を覗き見る

Haskell (その3) Advent Calendar 2017 11日目の記事。(予約投稿知らなかったのでフライングになった)

GHCコンパイルの途中で中間表現として用いるCoreの生成っぷりを観察する。

観察して、あーはいはいなるほどね(わかってない)、と言うだけになりそう。

はじめに

GHCHaskellソースコードを低レベルなコードへとコンパイルする過程で様々なpass(コンパイルのステージ)を通じてプログラムデータを変換する。 俯瞰図は下記のリンクに詳しい。

Compiling one module: HscMain

僕がGHCの話をどこかで聞きかじってかっこいいな、と思ったのは、 GHCコンパイラ中間言語として定義しているCoreを知った時。

このCoreと名付けられた中間言語はDesugar passにて生成され、下記のような性質を持っている。

  • 小さな構文
    • 3つのデータ型と15の値コンストラクタ
  • 束縛変数には全て型がついている
    • 前段で推論されている
  • 全て型がついているため高速に型検査ができる
    • もう推論は終わっているので検査が高速
  • 単純だが大きな表現力を持つ

GHCはリリースのたびに様々な言語拡張が増えていて、 表面上の構文は多様になってきている。 それにも関わらずこのCoreという中間言語は下記のような小ささを保っている。

  • 3つのデータ型
  • 15の値コンストラクタ

ghc-8.2.2 CoreSyn

data Expr b
  = Var   Id
  | Lit   Literal
  | App   (Expr b) (Arg b)
  | Lam   b (Expr b)
  | Let   (Bind b) (Expr b)
  | Case  (Expr b) b Type [Alt b]
  | Cast  (Expr b) Coercion
  | Tick  (Tickish Id) (Expr b)
  | Type  Type
  | Coercion Coercion
  deriving Data

data AltCon
  = DataAlt DataCon 
  | LitAlt  Literal
  | DEFAULT
   deriving (Eq, Data)

data Bind b = NonRec b (Expr b)
            | Rec [(b, (Expr b))]
  deriving Data

type Arg b = Expr b
type Alt b = (AltCon, [b], Expr b)

各値コンストラクタが依存している更に細かいデータ型はあるにせよ、 Haskellソースコード上記のデータ型にdesugar(脱糖)されて単純化される。

正直、僕もすべてのコンストラクタの意味が解っているわけではない。 しかしあの多彩な表現力を持ったHaskellの構文が この小さなCoreに変換可能である ことに大きく驚いた。

ここではこれらのデータ型の詳細には立ち入らず、 実際にHaskellのプログラム書きながらこのdesugarされたCoreがどう変化しているかを見てみようと思う。

観察してみる

この節ではGHCデバッグオプションを使って、 parseされたプログラムがDesugar passを経た後の結果を確認してみる。

どんな感じで見えるんだろ。

Setup

stack.yamlにオプションをつけておこう。

ghc-options:
  "*":  -ddump-to-file  -ddump-ds -ddump-simpl -dsuppress-idinfo -dsuppress-coercions -dsuppress-uniques -dsuppress-module-prefixes

長い。長いけれどポイントは -ddump-ds のみ。 -dsuppres 系は冗長な出力を減らすために指定しているだけ。

このオプションをつけておくとstackのビルドの成果物を格納する .stack-work ディレクトリの下にレポートが出力される。

今回 src/Lib.hs に定義を書き下しているため出力結果は

.stack-work/dist/x86_64-linux-nix/Cabal-1.24.2.0/build/src/Lib.dump-ds

というファイルに出力される。

定数

stringConst :: String
stringConst = "Hello"
-- RHS size: {terms: 2, types: 0, coercions: 0}
stringConst :: String
stringConst = unpackCString# "Hello"#

まあ、なんか、うん。そうだよね。

関数適用

falsy :: Bool
falsy = not True
-- RHS size: {terms: 2, types: 0, coercions: 0}
falsy :: Bool
falsy = not True

変化なし。単純過ぎたか。

Infix

two :: Int
two = 1 + 1
-- RHS size: {terms: 6, types: 1, coercions: 0}
two :: Int
two = + $fNumInt (I# 1#) (I# 1#)

なにか起きた。。。

二項演算子も結局は関数なので、 + 1 1 のようなS式っぽい見た目になるのはわかる。

$fNumInt という謎のシンボルが出てきた。

後でも出てくるが型クラス NumInt インスタンス定義を渡している模様。

関数合成

notNot :: Bool -> Bool
notNot = not . not
-- RHS size: {terms: 3, types: 3, coercions: 0}
notNot :: Bool -> Bool
notNot = . @ Bool @ Bool @ Bool not not

x . y. x y に変換された。 これもまた二項演算子が2引数の関数に変換されている。

だけではなくて @ Bool なる記号が出てくる。 これは . が持つ多相性に関連する。 次で説明。

多相関数

identity :: a -> a
identity x = x
-- RHS size: {terms: 3, types: 3, coercions: 0}
identity :: forall a. a -> a
identity = \ (@ a) (x :: a) -> x

ちょっと形が変わった。大事なところにきた。

Haskellで匿名関数と作る時は

\ x -> x

とする。

なので

\ (x :: a) -> x

となるなら解る。 「aという型を持つxという値を受けとり、そのxを返す」というような意味で読める。

しかし実際は

\ (@ a) (x :: a) -> x

こう。

(@ a)

匿名関数に引数が増えている。

これは 型変数が関数の仮引数として定義されている ことを表す。

とても不思議。

-- 型    値
\  (@ a) (x :: a) -> x

型と値が同列の引数として扱われていることになる。

Coreでは型の引数と値の引数が同列に扱われて関数に適用される。

なのでこの関数に引数を適用する場合は、

identity Int 1

のようにして型引数が決定され、値引数が決定されているものと思われる。

補足: forall について

identity :: forall a. a -> a

forall が表れるが意味的にはもとの a -> a となんら変わらない。 糖衣構文として forall の省略が許容されていたものが、 脱糖を経て明示化されただけ。

補足: Core上の表現

この関数がCore上でどう表現されているかというと

Lam (TyVar "a") (Lam (Id "x") (Var (Id "x")))

ラムダ計算っぽく書くと

λ a. λ x: a. x 

こんな感じ? (解らないけど a にはkindとして * でもつくのかな?)

1つめのラムダ抽象の引数は型で、 2つめのラムダ抽象の引数はa型の値xとなる。

この2つの引数はCore言語内で Var という型を持つ。

Var

型と値が同列で引数になる仕組みは簡単で、 関数の引数に束縛されるデータ型 Var が下記のようになっているから。

data Var
  = TyVar ...   -- 型レベルの変数
  | TcTyVar ... -- 不明 "Used for kind variables during inference" らしい
  | Id ...      -- 値レベルの変数

この関数の引数に与えられるデータが

  • TyVar: 型
  • Id: 値

どちらも受け付けるようになっている。

多相関数の適用 (型変数が決定されるのか?)

本当に型も引数として関数に適用されているのかを観察。 先程の多相関数に引数を適用してみる。

one :: Int
one = identity 1
-- RHS size: {terms: 3, types: 1, coercions: 0}
one :: Int
one = identity @ Int (I# 1#)

予想通り。

@ Int で確かに型を適用している。

高階関数

おなじみの関数合成。

comp :: (b -> c) -> (a -> b) -> a -> c
comp f g x = f (g x)
-- RHS size: {terms: 9, types: 11, coercions: 0}
comp :: forall b c a. (b -> c) -> (a -> b) -> a -> c
comp =
  \ (@ b) (@ c) (@ a) (f :: b -> c) (g :: a -> b) (x :: a) -> f (g x)

引数がお化け。。。。

だけれど、型変数の抽出ルールはやはり明確だ。

型変数は b c a の順で登場する。 それに合わせて forall b c a の順で定義される。

さらに forall に続く型変数はCoreのラムダ抽象で引数になる。

パターンマッチ

hasValue :: Maybe a -> Bool
hasValue (Just _) = True
hasValue Nothing  = False
-- RHS size: {terms: 8, types: 7, coercions: 0}
hasValue :: forall a. Maybe a -> Bool
hasValue =
  \ (@ a) (ds :: Maybe a) ->
    case ds of _ {
      Nothing -> False;
      Just _ -> True
    }

関数定義部におけるパターンパッチはcase of構文に変換されている。

CoreのCaseコンストラクタに変換されているらしい。

Case  (Expr b) b Type [Alt b]

実はこのコンストラクタ bType の部分がまだ何者か判明していない。

bExpr b を束縛しており、 Type[Alt b] の式の型を注釈している?

型クラス制約

型クラスつきの関数を定義するとどうなるだろうか。

join :: (Monad m) => m (m a) -> m a
join = (>>= id)
-- RHS size: {terms: 8, types: 17, coercions: 0}
join :: forall (m :: * -> *) a. Monad m => m (m a) -> m a
join =
  \ (@ (m :: * -> *)) (@ a) ($dMonad :: Monad m) (ds :: m (m a)) ->
    >>= @ m $dMonad @ (m a) @ a ds (id @ (m a))

斬新な変数が出てきた。 引数部分を分解して一つ一つ読み解こう。

(@ (m :: * -> *))    -- Monadのインスタンスとなるべき型
(@ a)                -- mで修飾された入力値の型の一部
($dMonad :: Monad m) -- 型クラスを満たすインスタンスの定義
(ds :: m (m a))      -- 実際の関数の入力値

join に表れる型変数は ma

なのでその2つは最初に (@ (m :: * -> *))@ a として束縛される。 (ds :: m (m a)) は実際の関数の引数なので疑問なし。 問題は ($dMonad :: Monad m) というどこから出てきたのか解らない束縛。

これは型クラスのインスタンスも関数の引数として受け取るための束縛らしい。

ということは、型クラスのインスタンスを渡しているところも見られるかもしれない。。。

型クラスのインスタンス適用

さきほど定義した join を使ってみよう。

maybeOne :: Maybe Int
maybeOne = join (Just (Just 1))
-- RHS size: {terms: 6, types: 5, coercions: 0}
maybeOne :: Maybe Int
maybeOne =
  join
    -- (@ (m :: * -> *))
    @ Maybe
    -- (@ a)
    @ Int
    -- ($dMonad :: Monad m)
    $fMonadMaybe
    -- (ds :: m (m a))
    (Just @ (Maybe Int) (Just @ Int (I# 1#)))

コメントで先程の join の定義と対照してみた。

Monadインスタンス定義を受け取る部分には

$fMonadMaybe

が。

名前から察するにどうやらMaybeのインスタンス定義が渡されているようだ。 (Scalaが型クラスのインスタンスとしてimplicitパラメータで渡しているものと、ほぼ同じものだと思われる。)

Monad

最後にモナドを含むdo記法がどのようにCoreに変換されるのかを見てみる。

printArgs :: IO ()
printArgs = do
  args <- System.Environment.getArgs
  print args
-- RHS size: {terms: 7, types: 8, coercions: 0}
printArgs :: IO ()
printArgs =
  >>=
    @ IO
    $fMonadIO
    @ [String]
    @ ()
    getArgs
    (\ (args :: [String]) -> print @ [String] $dShow args)

doは糖衣構文なので脱糖後は >>= を使った式に変換されるのは予想できた。

型周りは思ったよりいろいろ混ざってきて混乱。 上から見ていく。

bind関数の定義。(型制約は除く)

>>= :: m a -> (a -> m b) -> m b

これは forall つきで表現すると

>>= :: forall m a b. m a -> (a -> m b) -> m b

となる。

よって

(@ (m :: * -> *))
(@ a)
(@ b)

が型変数として関数の引数に抽出される。 実際の対応をみてみると

-- (@ (m :: * -> *))
@ IO
-- ここはMonadのインスタンスとしてIOの定義を渡している
$fMonadIO
-- (@ a)
@ [String]
-- (@ b)
@ ()

これらを使うと >>= は下記のように具象化される。

--     getArgsより    printより
>>= :: IO [String] -> ([String] -> IO ()) -> IO ()

型変数だった部分全てに具体的な型が当てはまった。

まとめ

Haskellのプログラムはdesugar(脱糖)後にCoreという中間言語に変換される。

Coreは基本的に型付きラムダ計算(の変種)なので

  • 変数
  • 関数の定義
  • 関数の適用
  • その他 Let, Case ...

などのわずかな定義で構成される。

さらに値と型が同レベルで束縛されるラムダ抽象を用いることで

などの操作が ただの関数適用 で実現されている。

少ない規則で多彩なユースケースを実現している好例がGHCの中に潜んでいることを知ることができてよかった。

Less is more.

Yoshiko is Yohane.

Reference

下記、余談

モチベーション

Haskell Day 2016が日本で開催された時にSimon Peyton Jonesさんが"Into the Core"というタイトルでプレゼンされたらしい。 残念ながら僕は都合がつかず聞きにいけなかったけれど、同じテーマの講演が動画に収められていたのでそれをリンクしておく。

Into the Core - Squeezing Haskell into Nine Constructors by Simon Peyton Jones

早口過ぎて99%何を言っているのか僕には解らない。 けれどところどころなんとなく伝わる気がする。

プレゼンで使ったスライドは こちら

これをぼんやり聞いていて「Coreってなんだか面白いな」と思ったのがきっかけ。

これから

Coreの理論的背景になっているSystemFというラムダ計算の一種が何者なのか気になる。

GHCで用いられているSystemFCという変種については下記のリンクが参考になりそうだけど。

System F with type equality coercions

僕はそもそもラムダ計算素人なので下記の書籍を読み進める必要がありそう。

型システム入門 プログラミング言語と型の理論

最短で

  • 3章: 型無し算術式
  • 8章: 型付き算術式
  • 9章: 単純型付きラムダ計算
  • 23章: 全称型

を読めば辿り着けるように見える。

いやーほんとかなあ。。。

SMLの関数適用を構文解析する時の問題

まだ構文解析器で苦労している。 今回も詰まっているのは構文のconflict。

問題

これが関数適用

app : exp exp

これが二項演算子適用

infixapp : exp vid exp

この時に入力を

x y z

とすると2つの解釈ができてしまうことになる。

((x y) z)

とするネストした関数適用なのか

x y z

とする二項演算子の適用なのかParserが判断つけられない。

前者ならreduceするが後者ならshiftする。 なのでこれはshift/reduce conflictが起きていると言える。 happyはデフォルトでshiftするので二項演算子として解釈される。

これを解消したい。

解決

sml-njやmltonのgrmファイルの定義を覗いたところ

FlatAppExp : exp list

のようなデータコンストラクタを使ってとりあえずシンボルのリストとしていったん読み込んでしまうらしい。 なぜ関数適用と二項演算子適用は全然違う構造にも関わらず峻別せずに扱うのだろうと疑問に思った。

なぜだろう

SMLではfixityを自分で定義して二項演算子を作れる。

左結合か右結合かをどこかのテーブルに保存しておくことになる。(おそらくEnv的なもの?まだそのあたり解らない) こういう動的にassociativityが定義される二項演算子はパーサジェネレータでは扱えないっぽい。

なので一度解析しきってから、後でsanityチェックして弾くっぽい。

解析の途中でこのfixityのテーブルを更新しながら進めば別に解析の完了を待たなくてもいいじゃんとも思った。 けれど、それだとfixityの定義が必ず演算子の使用よりも前に定義済みである必要がある。 それは不便だろう。

ということでFlatなんたらという構造を導入してなんとか解決はできた。

追記

http://dev.stephendiehl.com/fun/008_extended_parser.html

ここを見るとinfix operatorを動的に定義していく方法が提示されているが、やはりparsecだな。ghcはどうやっているのか見てみる必要ありかな。。。

納得いってない

悪手かなと思うのは、こうした構文解析上の問題のために抽象的なデータ構造にコンストラクタを追加しなければならないという点。 せっかくきれいにsyntax objectを定義できたのにノイズが入ってしまうみたいでイマイチだなと思う。

これだと

1 + 2 + 3

みたいな入力は

[ "1", "+", "2", "+", "3" ]

のようにreduceされる。

parsecならこれをexpression builder的なAPIでうまく木構造に変換できるのだが。。。 まあ、部分的にparsec使うのはありかもしれない。

これから

あとはモジュール系の構文解析が作れればとりあえず構文解析のステージは終わりだろう。 と、言いたいところだがshift/reduceやreduce/reduceのconflictがわんさか残っている。

どうしよう。。。問題ないならこのまま進めてしまいたい。 正直conflictの解消法は未だにわかってない。

あとまだわかってないこと。

  • 構文解析終わった後のsyntax objectに位置情報を顕に保存していないけれどtype checkエラーの時に位置情報含めてレポートできるのか?
  • そもそもエラーレポートがすごくわかりにくい。後で苦労するので早めにverboseなレポート出せるようにしたい。

やりながら良かったと思うこと。

  • haskellのhappy使ってるけどmlyaccやyaccととても似ているため他のツールチェイン使った時もこのノウハウは活きるだろう
  • テストはこまめに書いているので「ここまでは動く」という証左が得られる安心感はやっぱり良い。プログラマとしてこの感覚は大事にしたい。

その他近況メモ(ぼやき)

カーネル

詳解Linuxカーネル読んでる。 メモリアドレッシングからいきなりハードル高い。

特にページングテーブルの初期化のところとか全然解らない。

Clojure

Scala勉強しなきゃ、からマッハで脱線してClojureの情報ばかり漁っている。

どっかの記事で「Clojureは大規模プロジェクトになるとメンテナンスが難しくなってきてスケールしない」みたいなこと言ってた。 そうだろうなと思う。 リファクタリングはそれほど気軽にできないだろう。

specが出てきてチェック機構は揃ってきているけれど、 それでもやはり「実行しないと結果が解らない」という制約は残る。

REPLで探索しながら直すべきところは見つけられるよ、という意見もあるかもしれないけれど リファクタリングの過程で影響のあるところ全部を検査する仕組みはやっぱり無いではなかろうか。 というかリファクタリングして壊れたところを機械的に見つける手段が無い、と言うべきか。

Clojureもそうだけど、RubyPythonやJS使っている人たちどうしているのだろう。素朴に疑問。

とかぐだぐだ言いながらもなんかClojure好きなので勉強を続けてしまう。

好きなプログラミング言語の好きなところについて思った

改めて最近実感すること。

Haskell, Elm, Clojureほんと好き。

Scala勉強しなきゃなーと思いながらClojureを触ってしまうことが多かったのだけれど、 その理由が少しずつわかってきた。

いい言語たち

いままで少しだけ触れてきたJava, Python, Scala, Goはいずれもとても大きなユーザを抱えている。 どの言語もたくさんのユーザを得るために現場で使えるようなエコシステムをどんどん投下してあっという間に大きなユーザベースを獲得した。

プログラミングのしやすさを大事にして、誰でもすんなり入門できるように設計されている。 僕が入門できるくらいだから本当に敷居が低くて、けれどどんなやりたいことも実現させてくれるいい言語ばかりだ。 押し付けがましい思想も少ない。

たのしい言語たち

一方でHaskell, Elm, Clojureはちょっと独特だ。

HaskellではMonadicなプログラミングやSTM, デフォルト遅延評価など今まで触れたこともないようなパラダイムで溢れていた。

ElmではElm Architectureという一見してみると強い制約のもとでWeb UIを構築しなければいけなかった。

ClojureではREPL駆動開発やtransducer, 状態のオペレーション(STM, Atom, Agentなど)という独特なキーワードが骨子になっている。

(あ、全部関数型プログラミングだ。。。)

いずれも今までの自分には聞いたこともないような概念ばかりで、きっと解らなくてすぐに挫折してしまうだろうと思った。 だけど全然そんなことはなかった。むしろ楽しかった。

やりたいことが手元にあって、それを実現するためにどうしようかと考える時、Haskell, Elm, Clojureではまず素直に落とし込めない。 どんなやり方があるのか調べて、どれがその言語らしい XXX way なのかを知っていかなければいけない。 本当に手間がかかることが多い。

なのになんでこんな楽しいのだろう。進まない。進まないのに。

簡単≠たのしい

その制約のせいか、「できた!」と思った時の瞬間が本当に嬉しい。やっていることは全然大したことない。 SpringBootとかDjangoとか使えば瞬殺なのだろう。

でも、なんというか、その言語の思想に沿うように実装できた時の嬉しさは要求を鮮やかに実現できた時の歓喜とは別の何かだ。 3Dプリンターで模型を切り出すのではなくて、彫刻刀で大仏を彫り出すような変なドグマの混じったカタルシスを感じる。

何ができるかではなくて、どうやるかが楽しい。 ほんと、仕事としてプログラマやっている人間としては全然駄目だと思う。 実際問題、顧客の要求を低コストで十分に実装する能力や判断力の方が絶対にお金は入るはずなんだ。 成果物や収益から逸脱して、作法や流儀や過程に楽しみを見出してコストを支払うなんて多分駄目なはずなんだ。

でも何故だろうか、遠回りなのに美しい道が用意されているように見えるプログラミング言語ばかり好きになってしまう。 マーケットとか人材の需要とかじゃなくて、思想や信念や流儀に見え隠れする怪しさ(妖しさ?)に惹かれてしまう。

本当はScalaPythonやGoに触れて経験を積んだ方がきっとすぐに応用に入れる場面も多いはずなのに。 どうもそういう打算が働かず、ただただ楽しいと思うプログラミング言語に傾倒していくのを自ら止められずうろうろしている。

幸い、Haskell, Elm, Clojureはプロダクションでの採用事例も増えてきている。いずれ自分が書いたHaskell, Elm, Clojureのコードがプロダクション環境で動く日が来たらいいなあ、と思う。

Erlangとかもなんだか光背が見える言語だ。。。気になる。

ネットワーク機器の制御とかでHaskell, Elm, Clojureあたり使っている会社の仕事とかあったらいいなー。 ネットワーク(特にバックボーン)業界はだいたいPythonJava, Goなのでもう少し僕が好きなプログラミング言語の実装増えてこないかなあ。

(自分で書いていけってことか。。。)

技術書を読む時の問題意識について(答えはまだない)

何か学習したい、と思う動機があるとする。

現在の僕の場合は「仕事の関係でLinuxカーネルについておさえておきたい」とか。

学習したいので何らかの書籍を参照することになる。

問題

読んでいる内容が頭に定着していない感覚

購入した詳解Linuxカーネルでは「メモリアドレッシング」の章で、 ハードウェアの仕様も含めて、章タイトルについての詳細な説明がなされている。

どうもこれを読んで頭に入っていると感じない。

そもそもセグメンテーションて何だ、というのがわからない状態で読み出す。

何故か

そもそもメモリアドレッシングについての問題意識がない。 気にしたことがないし、それについて知りたいと思うような動機づけの体験がない。

なので読んだところで「読まされている」状態から抜け出せない。

逆説的に、メモリアドレッシングにまつわる問題に過去出会っていて、 どうしても詳細まで掘り下げたかった人はよく頭に入ることだろう。

書籍を読んでいて「なるほど」と思うには、 まずそれを解きたいと思うなりに本人の中に謎みたいなものが定着している必要がある。 これまでの体験により伏線だけが溜まっている状態だ。

書籍を読むことで体験した事実に対する説明がなされて、 伏線回収がおこなわれる。 この時に初めて「なるほど」と納得する。

僕が頭に定着する、と言っているのはこの変化のことを指す。

つまり、僕は伏線を持たずに伏線回収の説明をされている状態なわけだ。

どうしたらいいのか

2つくらい思いついた。

1. 愚直にわからないところを調べる

読み進めるにあたって解らないところを新しく問題意識の対象と捉えて解きにかかる、という考え方。

Intelアーキテクチャまで知らないとだめなのでは。 いったいどこまで深く潜ったらいいのだろう。

DMACも調べないといけない。

足元に広がるハードウェアの世界は広すぎて探索の意欲が減っていきそうだ。

2. 解ったことを整理して解らなかったところを記録する

たぶん現実的な解法。

「あとでがんばる」という判断で不明なところを棚上げにして進む。

詳解Linuxカーネルは頭から読んでいくような章立てに必ずしもなっていないし、 これからも細部でわからないところが想像以上に出てくるだろう。

これにいちいち付き合って深堀していると前進感も得られないし、 きっとどこかで挫折するだろう。

シナリオを進めるためにはいったん「逃げる」コマンドを使うことも必要だということかな。

大事なのはあとで「戻ってくる」ことだけれど、うーん、戻ってくる気が起きるかどうか。。。。

まとめ

書籍を読んで納得するには、知りたい問題が頭の中に既に用意されている方が良い。

といっても書籍に書いてあること全てに対して問題意識を持っているということはまず無い。

なので納得に至らないなら、一度進んでまた戻ってくる方が精神衛生に良さそう。

結城浩さんの数学ガールは問題意識の発露からストーリーに乗せて語るので、読者が露頭に迷うことが少ないのかな、と脱線しながら思った。

小さく作ることとモチベーション

Minimum viable product - Wikipedia

小さく作りながら進めるのがうまい人は作業ステップの分割ではなくてゴールの分割に優れているなあ、と思う。 最低限のユーザが試すことができる機能のみを搭載したプロダクトをMVP(Minimum Viable Product)というらしい。

ユーザストーマッピングの本にも書いてあった。

僕が実例で見て痛感したのはRui Ueyamaさんの動画。

www.youtube.com

小さいけれど動くものを作る。 できたものをテストして、また機能をリッチにしていく。

Rebuild.fm #153にUeyamaさんが出ていた回では「インクリメンタル」と表現していたアプローチ。

なんでこれが良いのか

僕自身のモチベーションが維持できる。 小さくてもフィードバックが得られるから。

小さくても動くという達成感がいかに大きいか、最近Haskellでコード書いていてつくづく思う。 少し書いたら小さなテストを作って確認していく。

「ここまでは動きそうだな」というのが安心感として得られる。

安心!

安心が大事だ。モチベーションは精神性に根ざすので、安心という心の状態がモチベーションに寄与するのは、なんとなくreasonableな気がする。

安心して進めたい。うんうんと頷きながら進めたい。わけがわからなくなって疲れて飽きてやめたくない。

そのためにゴールを小さく分割して作っていこうよ、という活動が僕なりのMVPの効用だ。

はまりがちなこと

頭にあるものを一気に吐き出そうとすると、前述の進め方を忘れてしまうことがある。

とにかく全部一度作りきろうとするのだ。

すると一気に作ったあと一気に動作を検証していくことになる。 一気に作ったものがきれいに動作することは大抵なくて、長いデバッグが始まることを意味する。

フィードバックを得る機会は先延ばしになり、モチベーションは消費されるだけになってくる。

今度はだんだんデバッグが辛くなってきて腰が重くなってくる。 こうなるともう赤信号だ。

今までこういう隘路にはまって続かないことが多かった。

小さくゴールを分割するということ

これは難しい課題だ。

問題領域がよく解っているならゴールの分割はわけないだろう。 でもインクリメンタルにモノを作っていく時、大概の場合は作ろうとしているモノの全体像はわからない。 自然と探索的にゴールを切り取っていくことになる。

これに定石があるようには思えない。なので都度頭を悩ませながらゴールを切り取っていくのだろう。

けれど、間違った判断をしていることに気づけるかもしれない。 例えば、ゴールを分割するのではなく、作業工程を分割するような間違いだ。 ユーザーストーリーマッピングの本では、とても大きなケーキを作る作業を例えにだしていた。

ゴールを小さく区切るMVPの考え方に従うと、小さなゴールとは例えば1/16くらいのサイズのカップケーキのようなものだという。

誤った分割をしている場合は、大きなスポンジを作ることだという。

大きなケーキを工程で分割してしまうと後者の過ちを踏むことになる。 対照的にMVPに従ってゴールを分割すると、前者のように小さいけれどユーザにデリバリできる単位が成果になる。

フィードバックを得やすいのは明らかに前者、ということだ。大きなスポンジだけ渡されても、それはケーキではないから誰も評価できない。 一方小さなケーキは小さくてもケーキだ。食べてケーキとしての出来栄えの感想を述べることができる。

幸いにしてソフトウェアは小さな部品を合成して大きな部品を構築できる性質を備えている。 小さなケーキを合成すると大きなケーキが作れる。

これを利用しない手はない、ということらしい。

まとめ

小さいけれど充分に動作する機能を反復的に作っていく。 これはモチベーションを維持していくことにとても効果がありそうだと思った。

もちろん難しいのはゴールの分割する思考法だ。

それでも三日坊主になりがちな僕でもモノを作り続けられるかもしれない唯一のアプローチではないかと思っている。

仕事で使った言語

僕もまとめておこう。

Java

書いたコードの量はダントツに多い。

リフレクションお化けにハマったり、JavaEEにハマったりした。

いまはJavaに興味なくてJVMに興味が移ってしまった。

JavaScript

jQueryが流行ってた頃に一度検索バーの補完用モジュール書いたりしてた。

その後、一度別のツールでReact使ったりした。

Python

Webアプリを書くときに使った。 良い言語だと思う。関数型プログラミングを少しかじれるのは魅力なんだけど、イミュータブルデータ用のAPIが少なくて結局関数型プログラミングを活かしきれないと結論づけている。

Go

簡単なログ収集ツールとかテキストデータの解析で使った。 プログラミングスタイルに慣れていなかったので、意図を関数と構造体で表現するのにとても苦労した。 もう少しCとか書いてから再入門したらきっとmind blowingな発見があるのだろう。

Haskell

ちょっとしたデータ解析のコマンドラインツールで使った。作ったバイナリをポータブルにできなかったので、作るだけ作って配布は断念した悲しい経験。

Clojure

テストスクリプトのスケルトンを出力するツールを作るのに利用した。

安易にNPEを引いてデバッグに苦労した記憶。すごく好きな言語だけど、もう少しREPLを使った開発に慣れないと安定して動くプログラムを組むのに時間がかかるなという印象。

まとめ

あたりを満たせてる言語だと僕の場合はすんなりプログラムが組めるみたい。

実行ファイルの配布やメンテナンスを考えると実はScalaあたりが自分にフィットするのかな、とは思う。

Haskellが好きなのは変わらないのだけれど、仕事で使うにはまだ僕自身の課題が多そう。

なのでやっぱりScalaなのかなー。

ちなみにプライベートではHaskellのalexとhappyを使ってSMLの構文解析器書いてる。コンパイラ技術はとても楽しい。

左再帰を含む構文解析むずい

やろうとしていること

Haskellのparsecを使ってSMLの構文を解析し構文木を生成する。

やっていること

SMLの構文解析はいろいろステップがある。

  1. リテラル (special constants)
  2. 識別子 (identifier)
  3. 型注釈 !!イマココ!!
  4. パターンマッチ
  5. 宣言
  6. モジュール構文

リテラルや識別子はなんとか倒して、いま型注釈の解析に取り組んでいるところ。

苦戦しているところ

この型注釈の構文解析で例の問題に突き当たった。

再帰問題だ。

SMLの型注釈の構文はこんな感じ。

ty ::= tyvar
       { <tyrow> }
       tyseq longtycon
       ty -> ty'
       ( ty )

tyrow ::= lab : ty <, tyrow>

上記の中でもいま苦戦しているのが、

tyseq longtycon

というところ。

tyseq

とは0回以上tyにマッチするtype constructorへの引数を表す。最後にtype constructorにマッチさせる。

0回以上tyにマッチするかどうか検査するためには、再帰的にtyを呼び出すが、これが無限再帰を起こす。 つまり構文木の左側をぐんぐん掘り進めていってしまう。

これは素朴な数値演算式でも起きうる問題だ。

expr ::= expr + expr

などでも再帰的に解析が走るためparserが停止しないというよく知られた問題。

今回のケースではlongtyconがoperatorとなりtyseqがoperandとなるためポーランド記法のようなものと捉えることができる。

幸いにしてText.Parsec.Exprにはこのようにoperatorがpostfixとして出現するケースを式として解析する技がある。 しかしこのlongtyconは解析の過程で動的に発見される。果たして素直に使うことができるのだろうか。。。

市井の例を見るとpredefinedな算術演算子のみを扱っているケースが多くてあまり参考にならない。

この先

parsecでこのままくのか。

それとも、Alex + Happyでparser generateするのか。

このあたりがわからなくなってきている。

IdrisやElmはparser combinatorをある程度自前で実装して構文解析しているのを見ると、やはりparsecでも左再帰を解決しつつ解析できそうな気がするのだけれど。

追記

Adam Wespiser Parsing

If our language required a lot of left-recursive parsing, Alex & Happy would probably be a better choice.

こんな記述があった。 この記事ではschemeは比較的構文がシンプルなのでparsecでいくよ、と言っていた。

はて、僕が解析しようとしているSMLはどうだろう。とても左再帰が多い構文だ。

diehlさんも最初にparsec使っておいて結局Alex + Happy使っていたな。

Write You a Haskell ( Stephen Diehl )

いまはparsingの技術を掘り下げるよりも前に進むことを考えよう!

ということで、再びAlexでの字句解析をインクリメンタルに進めよう。