Arantium Maestum

プログラミング、囲碁、読書の話題

型クラスのある言語の実装に向けて:その1(何が必要かを考える)

つらつらと「型クラスのある自作言語の処理系を作りたいなー」と考えている。

実用性は度外視で、ある程度型クラスの雰囲気さえ味わえればいい。

Essentials of Programming LanguagesのINFERRED言語を以前実装した:

zehnpaard.hatenablog.com

再帰関数くらいまでは定義できる言語に型検査と型推論を追加したものだ。これに手を加えていってなんとかならないか。

必要な修正としては:

  • 構文をS式化する
  • 文字列を型として追加する
  • tuple型を追加する
  • builtin関数の充実
  • 型クラスの機能を追加する
  • 単一の型(tupleでも可)を持つ単一のコンストラクタで、新しい型が定義できるようにする
  • 新しく定義された型を既存の型クラスに追加できるようにする
  • 新しい型クラスを定義できるようにする

あたりだろうか。

とりあえず最初の4つをやれば「静的型付Lisp」的なものができるのでそこから始めてみよう。(EoPLの言語の構文がめんどくさい上にあまり好みではなく、拡張を考えるのもめんどくさいのでS式でいきたい・・・)

少し悩んだ点としては * リスト型 * 相互再帰 を実装するかどうかだが、まずは言語仕様を単純化するためになしでいこうと思う。

次回は型クラスのない「静的型付Lisp」の言語仕様を考えてみたい。

ちなみに参考としては:

www.youtube.com

okmij.org

とTypes and Programming Languagesを見ている。

Monadic Parser実装を通して近付く「モナドのお気持ち」

OCamlでMonadic Parserを作ってみる 前編後編で書ききれなかったポエム的なもの。さきにそちらを読んでもらえればわかりやすいかと思う。

HaskellのTypeclassopediaに

The wise student will focus their attention on definitions and examples, without leaning too heavily on any particular metaphor. Intuition will come, in time, on its own.

と書いてある通り、モナドと愉快な仲間たちの概念はまず抽象的な定義をよく読んでから、概念の使用例にたくさん触れていってお気持ちを理解していく必要がある。

今回はパーサコンビネータを通じてモナドの便利さの一側面を見ていきたい。

ネタとしては:

え、パーサをモナドに?・・・できらあ!

そもそもパーサをモナドにするとはどういうことなのか?

そもそもパーサとは?

定義を見てみると「構文解析をするプログラムの総称」とのことで、まあ文字列を受け取ってなんらかの言語だと認識してその構造を表すデータに変換するものだと考えられる。

例えば「文字のリストを受け取って、構文の規則にマッチしているならその部分を表すデータ構造と残った文字列を返し、マッチしないなら失敗する」という流れになる。型で表すなら:

type parser = char list -> (token list * char list) option

とか

type parser = char list -> (expr * char list) option

のようなものになるだろう。

パーサをモナドにする第一歩は、ここでぐっと我慢して

type 'a parser = char list -> ('a * char list) option

と任意の型'aをパラメータにとるよう抽象化することである。

ここで抽象化する理由は「こうしておけばtokenを返すパーサもexprを返すパーサも同じライブラリで作れるし便利」ということではない。結果的にそういう利点もあるが、そこは主眼ではない。

それよりもparserを「任意の型に対するコンテキスト」としての型だと定義していることがMonad的には大事。最終的にexprを返すパーサを作る過程で「文字を返すパーサ」「文字列を返すパーサ」「整数を返すパーサ」、さらには「関数を返すパーサ」などを定義して、その上でそれらを組み合わせていく。正直これはMonadic Parserを調べていた当初はかなり非直感的な考え方だった。

Functor

'a型の値を返すパーサに対して'a->'b型の関数を『適用』して'b型の値を返すパーサを作成する関数mapを定義してやれば'a parser型はFunctor(またの名を関手)となる。

これ単独だと、文字を返すパーサにChar.codeを適用して数字を返すパーサにしたり、Char.uppercase_asciiを適用して文字をパースして大文字に変換して返すパーサを作ったりできる。が、それくらいで表現力はまだまだ弱い。

Functorだと「パーサ同士を組み合わせる」ということができない。これだとまだコンビネータじゃない。

Applicative

FunctorをApplicativeに拡張するには

  • 'a型の値を、その値を返すパーサに変換するpure関数
  • 'a->'b型の関数を返すパーサと'a型の値を返すパーサを組み合わせて'b型の値を返すパーサを作成するapply関数

を追加する必要がある。

余談だがpureapplyはFunctorのmapを二段階に分解したパーツだとイメージすることもできる。

これでパーサが組み合わせられる!やった!

そんな風にテンションが上がっても仕方ないくらい、実際Applicativeで一気に表現力があがってパーサらしいことができるようになる。

let get_two = pure (fun x y -> [x; y]) <*> get_char <*> get_char

で二つの文字をパースして文字リストを返すパーサを、一文字をパースするget_charと、普通の関数であるfun x y -> [x; y]で作れる。(<*>applyの中置演算子である)

ちなみに上記の例ではcurryingが行われていて、まずこれが:

pure (fun x y -> [x; y]) : ('a -> 'a -> 'a list) parser

こうなって:

(pure (fun x y -> [x; y]) <*> get_char) : (char -> char list) parser

こうなる:

(pure (fun x y -> [x; y]) <*> get_char <*> get_char) : char list parser

パーサの型の中に関数がはいっていて、それを他の型のパーサと組み合わせている。

Applicativeのpureapplyを使っていろいろと他にも便利な関数や構文が用意できる:

(* パーサ二つを順に組み合わせて左側のパーサの結果を結果とする *)
let ( <* ) xp yp = (fun x _ -> x) <$> xp <*> yp

(* パーサ二つを順に組み合わせて右側のパーサの結果を結果とする *)
let ( *> ) xp yp = (fun _ x -> x) <$> xp <*> yp


let product xp yp = (fun x y -> (x, y)) <$> xp <*> yp

let (let+) x f = map f x
let (and+) xa ya = product xa ya

ここらへんの演算子や構文の使用例は「OCamlでMonadic Parserを作ってみる 前編後編」に多く書いた。

Functorと合わせて、Parser世界とは関係ない関数を使って、複数の(型が異なる可能性もある)パーサを組み合わせていけるようになり、かなり表現力が増した。

しかし、まだかなり重要な二つのことができない:

  • パーサの分岐(あるパースを試してみて、もし失敗したら違うパースを試す)
  • 前の部分のパース結果の値によって、その後のパースを決める

Alternative

パーサの分岐(あるパースを試してみて、もし失敗したら違うパースを試す)

というのはパーサを書いている時にかなり重要な機能だ。

そもそも、Functor/Applicativeまでの機能だと「パーサは失敗するかもしれない」という概念自体が明示的に現れない。

「失敗するかもしれない」という概念を導入し、「このパーサが失敗した場合は次にこのパーサを試す」という分岐ができるようにするために

  • 必ず失敗するパーサempty
  • パーサを2つ受け取り、「片方が失敗したらもう片方を試す」パーサを作成する<|>演算子

を定義することになる。

これでさらに表現力が強まる。例えばあるパーサを0回以上、あるいは1回以上適用する、というmanysomeを:

let rec many p cs =
  (some p <|> pure []) cs
and some p cs =
  (List.cons <$> p <*> many p) cs

のように定義できるようになる(eta conversionのためのcs引数がダサいが)

Monad

前の部分のパース結果の値によって、その後のパースを決める

というのはかなり抽象的な物言いだが、パーサコンビネータ実装にあたってこの段階でモナドがすごく欲しくなる理由が一つある。

プリミティブな(つまりコンビネータをまったく使わずに定義された)パーサがget_charだけな場合、モナドなしでは「この文字や文字列以外はパース失敗」というパーサが書けない!

get_charが空リストを受け取ると失敗するので「文字列の長さが一定以上かどうか」を確認するパーサは書けるが・・・

モナドbind(やその演算子>>=)があれば'a parserと関数'a -> 'b parserを組み合わせることができる。

let satisfy p =
  let f x =
    if p x
      then pure x
      else empty
  in
  get_char >>= f

fは文字xをとってp x = trueならxを返すパーサ、falseなら失敗するパーサを返す。(実際にはもっと多相な関数だが、get_charと一緒にしか使っていないため)

これで「次がある文字であればパース成功、それ以外ならパース失敗」というパーサが作れる。

これをFunctor/Applicative/Alternativeとして定義した関数・演算子などと組み合わせて複雑化していけば「任意の文字列」だとか「四則演算式」だとか「プログラミング言語」だとかをパースできるようになる。

パーサコンビネータモナドにすると何が嬉しいのか

パーサの型をパラメトリック多相にして、Functor、Applicative、AlternativeそしてMonadとしての演算を定義してパーサコンビネータを作ってきた。

パーサコンビネータ自体はこのような形式をとる必要はない。一例として以下の記事ではF#でパーサコンビネータを作っているが「Monad」の単語も出てこない:

fsharpforfunandprofit.com

(ちなみにこの記事はかなり丁寧なチュートリアルで非常に勉強になった。モナモナせずにただパーサコンビネータについて知りたい、という場合はここから始めるのもいいと思う)

今回パーサコンビネータモナドにして感じたメリットは二つ:

  • モナド(と仲間たち)は非常に組み合わせやすく破綻しにくいAPIであること
  • パーサ以外のコンテキストでも出てくる共通のAPIであること

まず第一のポイント。コンビネータを作る時に「どうやって組み合わせて作っていくのか」を隅々までイメージして作るのは非常に困難だ。気をつけないとすぐ「この組み合わせ方は想定していなかった」ということで、ある処理を記述できなかったり、あるいはバグったりする。それに対して、Monadなどの処理は(数学的なバックグラウンドがあることもあって)抽象性が高く、組み合わせやすい。組み合わせて様々な処理ができ、その処理がなんらかの最低限の保証があるよう、すでに考えられ使われている。そのAPIデザインにタダ乗りできる、というのはとてもありがたい。

第二のポイント。MonadAPIは様々なコンテキストで同一のものが出てくる。Haskellなどを見るとオプション型からIO型からエラー型まで全部モナドのインタフェースで操作できる。OCamlはそこまでモナモナしていないにしろ、option型はちゃんと定義すればMonad的に扱えて便利だし、非同期プログラミングのLwtライブラリなどはPromiseをモナドとして操作するようになっている。パーサコンビネータモナド化することはユーザに馴染みの深いAPIを提供することになる(特定界隈の人たち限定ではあるけど)。

というわけでモナドは嬉しい(必須ではないが)

パーサコンビネータモナドにすると何が嬉しいのか

実はあまり嬉しくないかもしれない・・・

と書くとついさっき述べたことと矛盾しているようだが、そうではない(はず)。

パーサに限ればモナドにしなくてもAlternativeで十分じゃないか?という議論についてである。

Applicative parsing | Notes on Computing

Parsing context-sensitive languages with Applicative | blog :: Brent -> [String]

今回モナドを導入した最大の理由は「パース結果を元にパースが成功したか失敗したかを決定する」satisifyを書くためで、これをプリミティブとしてコンビネータを使わずに書いてしまえばいい。

モナドの他の使いどころとしては

let rec expr cs =
  (let* t = term in
    (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t) cs
(* 以下略 *)

let* t = ...のように、<|>でまったく同じ部分を二度パースする手間を省くために使ったりなどもする。ここらへんは多分コンビネータで書かれたパーサを一旦静的解析して効率化すれば必要なくなるはず。

なのでMonadじゃなくてその手前のApplicative(というよりAlternative)までの機能を提供するだけのほうがいいかもしれない。ただし、その場合それなりに使える効率を出すには実装はもっと難しくなって、パーサをAST化して静的解析して云々、が必要になりそう。

モナドのお気持ち

モナドというのはXみたいなものだ」というのは界隈では有名なジョークみたいなもので、Xにはいるものがなんであれ、この主張の妥当性は常に疑わしい。

「『モナドというのはXみたいなものだ』という人は、象の一部分を触って『象というのはYみたいなものだ』と主張する盲人のようなものだ」とは言えるかもしれない。

パーサをモナド的に作ったからといって「だからモナドはこうなんだ」というにはモナドの抽象性と意外なところでの有用性は高すぎる。

私が言えるのは「パーサをモナド的に作ってみたらこんな感じだったよ」(「象をぺたぺた触ってみたら、触った部分はなんか長くてぐにゃぐにゃしてたよ」)というくらいである。

ただ、「モナドのお気持ち」への理解は、数多くのこのような「ぺたぺた触ってみた」経験の総体の先にあるのではないだろうか。

というわけでこの文章が誰かの「モナドのお気持ち」理解の一助になれば幸いである。

追記

以前の記事でも述べたが、この記事の元になっているのはGraham HuttonのProgramming in Haskellの第13章、タイトルはそのまんま「Monadic Parsing」。邦訳もあるようなのでオススメである。

OCamlでMonadic Parserを作ってみる(後編)

前回に続いてMonadic Parser Combinatorを実装していく。

再帰

OCamlのような先行評価の言語でMonadic Parserの定義に再帰を使うと問題になる場合とならない場合があるぞい。

問題にならない場合:

let match_string s =
  let rec f = function
      [] -> pure []
    | c::cs -> let* _ = match_char c
               and* _ = f cs
               in pure (c::cs)
  in
  String.to_list s |> f |> map String.of_list

ある文字列がパース対象の先頭にあるか、というパーサ。「先頭にあってほしい文字列」に対して再帰しているので普通に停止する。

問題になる場合:

let rec many p =
  some p <|> pure []
and some p =
  List.cons <$> p <*> many p

あるパーサを0回以上適用するmanyと1回以上適用するsomeを相互再帰で定義している、つもりなコード。

これはHutton本に出てくるHaskell版:

many x = some x <|> pure []
some x = pure (:) <*> x <*> many x

のほぼ直訳で、残念ながらOCamlではうまくいかない。使ってみるとStack Overflowを起こす:

utop # parse (many get_char) "abc";;
Stack overflow during evaluation (looping recursion?).

コードをよく読んでみればわかるが、先行評価では無限再帰してしまう。ちょっとダサくなるが、eta conversionを入れる(明示的にパーサの引数を書く)ことで無限再帰を回避できる:

let rec many p cs =
  (some p <|> pure []) cs
and some p cs =
  (List.cons <$> p <*> many p) cs

ちょっとダサいが・・・

コンビネータ

manysomeを使ってさらにコンビネータを定義:

let match_ident =
  let match_ident_list = List.cons <$> match_lower <*> many match_alphanum in
  String.of_list <$> match_ident_list

let match_nat =
  int_of_string <$> (String.of_list <$> some match_digit)

let match_int =
  match_nat <|> ((~-) <$> (match_char '-' *> match_nat))

小文字から始まるidentifierや整数をパースできるようになった。

次はまわりの空白を無視してパースするget_token関数:

let get_token p = many match_space *> p <* many match_space

get_tokenを使っていろいろ定義してみる:

let get_ident = get_token match_ident
let get_nat = get_token match_nat
let get_int = get_token match_int
let get_symbol s = get_token (match_string s)

使ってみる:

let get_nats =
  let+ _ = get_symbol "["
  and+ n = get_nat
  and+ ns = many (get_symbol "," *> get_nat)
  and+ _ = get_symbol "]" in
  n :: ns
utop # parse get_nats "[1, 2, 3, 4, 5]";;
- : (int list * char list) option = Some ([1; 2; 3; 4; 5], [])

余談だがlet+は使わずにget_natsを定義することもできる:

let get_nats =
  pure List.cons <* get_symbol "(" <*> get_nat <*> many (get_symbol "," *> get_nat) <* get_symbol ")"

どっちが読みやすいか・・・ これだけ長いとlet+を使った方がどの部分が最終的な結果に使われるかわかりやすいように思う。というわけでApplicative letは便利。

計算順序に則った数式パーサ

パーサコンビネータとしてある程度機能が揃ってきたので、これを使って計算順序を守った足し算・掛け算式のパーサを書いてみる。

Haskell版:

expr = do t <- term
          do symbol "+"
             e <- expr
             return (t + e)
          <|> return t

term = do f <- factor
          do symbol "*"
             t <- term
             return (f * t)
          <|> return f

factor = do symbol "("
            e <- expr
            symbol ")"
            return e
         <|> natural

ダメなOCaml版:

let rec expr =
  let* t = term in
   (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t
and term =
  let* f = factor in
   (pure (( * ) f) <*> (get_symbol "*" *> term)) <|> pure f
and factor =
  get_symbol "(" *> expr <* get_symbol ")" <|> get_nat;;

何故ダメなのかというと、やっぱり無限再帰の問題である。

解決策はやはりeta conversion:

let rec expr cs =
  (let* t = term in
    (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t) cs
and term cs =
  (let* f = factor in
    (pure (( * ) f) <*> (get_symbol "*" *> term)) <|> pure f) cs
and factor cs =
  (get_symbol "(" *> expr <* get_symbol ")" <|> get_nat) cs

ちょっとダサいが・・・ いや、これは実際かなりダサい。somemanyの場合はパーサコンビネータ側でパーサの実装がchar list -> ('a * char list) optionであることを利用してeta expansionしているわけだが、exprの場合はコンビネータのユーザ側のコードで同じことをせざるを得なくなっている。うまい解決方法があればいいのだが、思いつかない(&調べたところeta expansionしろ、というのがStack Overflowなどでは一般的な助言のようだ)。ぐぬぬ

使ってみるとこんな感じ:

utop # parse expr "1+2*3+4*(5+6)";;
- : (int * char list) option = Some (51, [])

感想

大枠ではHaskellとほぼ同一の表現でいけることがわかった。

違いとしては

  • Stringがchar listじゃない。すこし変換の手間がかかるが大したことではない
  • HaskellのStandard Libraryのほうが充実している。OCamlString.of_listis_upperなどがStandard Libraryにないのは悲しい。
  • 遅延評価 vs 先行評価。これが一番大きい。プログラミング言語の定義は大概再帰的になっているので、パーサのいろんなところでeta conversionする必要が出てくるように思う。ダサい・・・

コンビネータ部分やFunctor/Applicative/Alternative/Monad部分をlazyを使って遅延化すれば避けられるか?とも考えたのだが、exprtermfactorのようなユーザコード側での相互再帰的な定義に対しての影響力はないはず(引数部分が先行で評価されてしまう)。けっきょくユーザコードでもlazyを使う羽目になるし、それだったらeta conversionするのもほとんど変わらないはず?効率化の観点からはlazyのほうがいいかもしれないが・・・

ちなみに全然違うやり方として以下の記事で紹介されている「パーサをいったん独自のAST的データ構造で表現し、パースするときはそのコードを評価する」という手法もあるらしい。機会があったら試してみたい。

jobjo.github.io

今回のコード

github.com

OCamlでMonadic Parserを作ってみる(前編)

OCaml 4.08でmonadic/applicative letの構文が入ったことだし、これを使ってみよう、ということでHaskellのParsecのようなMonadic Parser Combinatorが作れるか試してみた。

具体的にはGraham HuttonのProgramming in Haskellの13章にあたる「Monadic parsing」の章をOCamlで追ってみたい。

Parser

Huttonの例ではParserは

newtype Parser a = P (String -> [(a, String)])

となっている。文字列を受け取り、パースが失敗したら空リスト、成功したらパースした結果と残りの文字列のタプルが唯一の要素のリストを返す。

OCamlに訳すにあたって三つ変えてみる:

  • コンストラクタを使わない。Haskellではtypeclassのインスタンスにするためにnewtypeとコンストラクタを用意しているがOCamlではそもそもtypeclassがないので。
  • stringではなくchar listを使う。HaskellだとStringはそのまま[Char]なのでパターンマッチできたり、tailがO(1)で取れたりして便利。OCamlだと文字列はリストではないのでそのまま扱うにはいろいろとめんどくさい。
  • 戻り値はlistではなくoptionを使う。複数の可能なパース結果を返す、といったことをしないかぎりリストを使う意味はない。

というわけでParser.tはこうなる:

type 'a t = char list -> ('a * char list) option

ついでに文字列にこのParser.t型の関数を適用できるように、parseという関数を定義しておく:

let parse p s = p @@ String.to_list s

(余談だが今回はcontainersというOCaml標準ライブラリを補う拡張ライブラリを使っている。普段使っているBatteriesがOCaml4.08に対応していなかったため・・・)

最小限のパーサ

文字リストから先頭の文字一つを結果としてとるget_charパーサを実装してみる:

let get_char = function
  | [] -> None
  | c::cs -> Some (c, cs)

使ってみるとこんな感じ:

utop # parse get_char "ABC";;
- : (char * char list) option = Some ('A', ['B'; 'C'])

これを元にいろいろと組み合わせて使えるパーサコンビネータを作っていく。

Functor

まずParser.tをFunctorとして使えるようにmapを定義する:

let map f p = fun cs -> (match p cs with
  | None -> None
  | Some (v, cs') -> Some (f v, cs'))

これで何ができるようになるかというと、あるパーサと、そのパース結果の型を引数にとる関数を組み合わせることができる。

例えばget_charのパース結果はchar型だが、その文字に対応するascii codeをパース結果とするパーサがほしいとすると:

let get_charcode = map Char.code get_char

でその新しいパーサが作れてしまう。パーサの内部実装などはまったく触らずに、パーサAの結果に対して関数を適用したものがパース結果になるパーサBを作成する。

Applicative

Functorとしてmapが定義されているのはうれしいが、まだまだ表現力が貧弱だ。例えば「二つのパーサを順番に並べて、その二つのパース結果を組み合わせたものをパース結果とする」ようなパーサはmapだけでは作れない。そのためにはApplicativeの関数であるpureapplyが必要になる。

pureはある値aをとり、「入力である文字リストをまったく消費せずにその値aをパース結果とするパーサ」を返す関数:

let pure v = fun cs -> Some (v, cs)

そしてapplyは「関数を返すパーサ」と「その関数の引数を返すパーサ」を組み合わせて「関数適用の結果を返すパーサ」を作成する関数:

let apply fp xp = fun cs -> (match fp cs with
  | None -> None
  | Some (f, cs') -> (map f xp) cs')

(* applyの中置演算子 *)
let (<*>) = apply

いくつか関連した演算子も追加:

let (<$>) = map

(* パーサ二つを順に組み合わせて左側のパーサの結果を結果とする *)
let ( <* ) xp yp = (fun x _ -> x) <$> xp <*> yp

(* パーサ二つを順に組み合わせて右側のパーサの結果を結果とする *)
let ( *> ) xp yp = (fun _ x -> x) <$> xp <*> yp

これで例えば「連続した二つの文字をとるパーサ」や「三つの文字を消費して真ん中の文字だけを結果として残すパーサ」などを定義できる:

let get_two = (fun x y -> [x;y]) <$> get_char <*> get_char
let get_middle = get_char *> get_char <* get_char
utop # parse get_two "ABC";;
- : (char list * char list) option = Some (['A'; 'B'], ['C'])

utop # parse get_middle "abc";;
- : (char * char list) option = Some ('b', [])

ついでにapplicative letも定義しておく:

let product xp yp = (fun x y -> (x, y)) <$> xp <*> yp

let (let+) x f = map f x
let (and+) xa ya = product xa ya

(Applicative Letについては前回の記事を参照してほしい)

Alternative

Applicativeをさらに強化して「二つのパーサのどちらかが成功したらそのパーサの結果を使う」というような合成を可能にしたい。Alternative Functorというらしい。

Alternativeのためにはまず「必ず失敗するパーサ」を定義する:

let empty = fun _ -> None

そして「二つのパーサのどちらかが成功したらそのパーサの結果を使う」を実現するeither

let either xp yp = fun cs -> (match xp cs with
  | None -> yp cs
  | Some _ as r -> r)

(* eitherの中置演算子 *)
let (<|>) = either

Monad

ApplicativeやAlternativeを使うと成功したパース結果を別の値に変換したり組み合わせたり、失敗したら別のパーサを試したり、などとかなり表現力が強まる。ただ、パースした結果を元に次のパーサを選んだり、一つのパーサの結果を調べてパースを失敗させたり、などということはできない。

そういうことだってできちゃう、そう、Monadならね。

というわけでモナドの登場。すでにApplicativeであるParser.tMonadとして使うために必要なのは、「a型を結果とするパーサ」と「aを引数に別のパーサを返す関数」を組み合わせるbind関数:

let bind xp fp = fun cs -> (match xp cs with
  | None -> None
  | Some (x, cs') -> fp x cs')

let (>>=) = bind

let (let*) x f = bind x f

これを使って:

let satisfy p =
  let* x = get_char in
  if p x
    then pure x
    else empty

というような関数が定義でき、さらに

(* 特定の文字ひとつ *)
let match_char c = satisfy (Char.equals c)

(* アルファベット小文字ひとつ *)
let match_lower =
  let p = function
    | 'a' .. 'z' -> true
    | _ -> false
  in
  satisfy p

(* アルファベット大文字ひとつ *)
let match_upper =
  let p = function
    | 'A' .. 'Z' -> true
    | _ -> false
  in
  satisfy p

(* 数字ひとつ *)
let match_digit =
  let p = function
    | '0' .. '9' -> true
    | _ -> false
  in
  satisfy p

(* アルファベット文字ひとつ *)
let match_letter = match_lower <|> match_upper

(* 英数字ひとつ *)
let match_alphanum = match_letter <|> match_digit

(* 空白一つ *)
let match_space =
  let p = function
    | ' ' | '\t' | '\n' | '\r' -> true
    | _ -> false
  in
  satisfy p

などと一気にいろいろできるようになる。

次回

Monadまでの機能を実装したところで長くなってきたので一旦ここまで。次回はこれを使ってsomemanyなどのコンビネータ、それらを使ってget_tokenget_intなどのより複雑なパーサを作り、最終的には簡単な四則演算パーサ&計算機を実装する。

ついでにHutton本に載っているHaskell版との比較などについても言及したい。

続き

OCaml4.08のmonadic/applicative let/andについて

OCaml4.08でシンタックスシュガーとしてlet*let+and+などの構文が新たに導入された。

詳細については

jobjo.github.io

がわかりやすかった。

直接モナドやApplicativeをサポートする構文というよりは、

let (let*) x f = g x f

などと好きに定義すれば

let* x = a in
h x

が脱糖されて

g a (fun x -> h x)

になる、ということのようだ。モナドだったらlet (let*) x f = bind x f、Applicativeだったらlet (let+) x f = map f xにすればうまくいく。

let (let+) x f = map f x
let (let*) x f = bind x f

let+ x = a in
g x
(* desugars to map (fun x -> g x) a *)

let* y = b in
h y
(* desugars to bind b (fun y -> h y) *)
(* or alternatively b >>= (fun y -> h y) *)

しかし、and+がどう脱糖されるのかいまいちピンとこなかった。

基本的にlet+and+はApplicativeのために使われることが期待されており

let (let+) x f = map f x
let (and+) xa ya = product xa ya

と定義するのが正しいようだ。

productというのはApplicativeと同一の表現力を持つMonoidal Functorの関数で

val product : 'a t -> 'b t -> ('a * 'b) t

という型を持つ。つまり「Functorに入った値」二つを「一つのFunctorに入ったタプル」に変換する関数だ。

それがどう

let+ x = a
and+ y = b in
h x y

みたいな構文とつながるのか。調べてみたところこの構文を入れたPRにこんなコメントがあった:

github.com

The unmixed applicative case needs to translate:

let+ x = a

and+ y = b

and+ z = c in

body

into

map (fun ((x, y), z) -> body) (prod (prod a b) c)

let+ ... and+ ... and+ ... in ...はまずlet+ ... ... ... inの部分でApplicativeのproductを使ってネストしたタプルの入ったFunctorを作り、それに対して「引数をdestructureして使う関数」をin ...の部分から作成して適用している。なるほど?

この構文はなかなか便利そうで、これを使って近々Graham HuttonのProgramming in Haskellに出てくるMonadic Parserを実装してみたい。

型推論を実装する その3 (型推論のある言語を作る)

型なしのLETREC、型検査のCHECKEDときて、ついに型推論ができるINFERREDの実装に移る。

github.com

言語仕様の変更

前回のCHECKEDでは

letrec int double(x : int)
  = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2))
  in
  (double 6)

のように関数の仮引数の型と、再帰関数の戻り値の型を明示的に指定する必要があった。

INFERREDでは型注釈の部分に「?」を入れることで、型をプログラマが指定せずに言語側で推論するようにできる:

letrec ? double(x : ?)
  = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2))
  in
  (double 6)

HaskellやMLのように型注釈を完全に省略するのではなく、C++のautoのように本来明示的に型を書くべきところに?と書くことで推論に回す、という構文だ。

今までType.tは:

type t = Int
       | Bool
       | Proc of t * t

のように、数値型、真偽型、そして関数型の三種が定義されていたのだが、今回そこに二つ追加する:

       | Unknown
       | Var of int

?で型注釈が省略されたところに、パースの時点でType.Unknownにしておいて、型検査の時にType.Var nとユニークな型変数を振っていく。

そのためにTypeモジュールに、新しい(ユニークな数字が振ってある)型変数を作成するnew_var関数と、それを使ってType.UnknownType.Var nに変換するmake_concrete関数を定義する:

let n = ref 0
let init () = n := 0
let new_var () = let x = !n in (incr n; Var x)

let make_concrete = function
  | Unknown -> new_var ()
  | t -> t

Type.nがグローバルステートになっているが・・・ まあこういうところで限定的に副作用が使えるのもOCamlらしいということで・・・

最後に、ある型変数が別の型の中に出てくるかを調べるoccurs関数:

let rec occurs t1 = function
  | Int | Bool -> false
  | Var _ as t2 -> t1 = t2
  | Proc (t2, t3) ->
      occurs t1 t2 || occurs t1 t3
  | Unknown -> failwith "Invalid no occurrence check against Unknown type"

型推論

それではついに型推論の話に移る。

INFERREDでは型推論は型検査と同時に起きる。というか型検査の一部として、型注釈が?な部分に型変数を振った上で解決可能かをつどつど調べていく。

なのでTypecheckモジュールの中で型推論している。ConstVarLetはCHECKEDと変わらず:

let rec check tenv = function
  | Exp.Const _ -> Type.Int
  | Exp.Var s -> (match Tenv.find tenv s with
      | Some t -> t
      | None -> failwith "Variable not typed")
  | Exp.Let (s1, e1, e2) ->
      let t1 = check tenv e1 in
      let tenv' = Tenv.extend tenv s1 t1 in
      check tenv' e2

ZeroPDiffIfあたりから違いがで始める:

  | Exp.ZeroP e -> 
      let t = check tenv e in
      begin
        Unify.f t Type.Int;
        Type.Bool
      end
  | Exp.Diff (e1, e2) ->
      begin
        Unify.f (check tenv e1) Type.Int;
        Unify.f (check tenv e2) Type.Int;
        Type.Int
      end
  | Exp.If (e1, e2, e3) ->
      begin
        Unify.f (check tenv e1) Type.Bool;
        Unify.f (check tenv e2) (check tenv e3);
        check tenv e2
      end

大事なポイントはUnify.f関数を使っている点(Unify.fの実装については後述。論理プログラミングなどでいうところの「単一化」のための関数である)。CHECKEDと違ってINFERREDではcheck tenv eなどが型変数を返すことがあり得るので、「ZeroPの引数が数値型かどうか」などを直接調べることができない。Unify.fを使って「ZeroPの引数が数値型であると仮定して矛盾が起きないか」を調べることになる。

関数定義:

  | Exp.Proc (s, t, e) ->
      let t1 = Type.make_concrete t in
      let t2 = check (Tenv.extend tenv s t1) e in
      Type.Proc (t1, t2)

前述のType.make_concreteで型注釈が省略されている場合は引数に型変数を振る(明示的な型注釈がある場合はその型をそのまま使う)。Unify.fを使う必要はなし。

再帰関数定義:

  | Exp.LetRec (t1, fname, arg, t2, body, e) ->
      let rt = Type.make_concrete t1 in
      let at = Type.make_concrete t2 in
      let tenv' = Tenv.extend tenv fname (Type.Proc (at, rt)) in
      let tenv'' = Tenv.extend tenv' arg at in
      let bt = check tenv'' body in
      begin
        Unify.f bt rt;
        check tenv' e
      end

再帰関数は引数と戻り値両方に型注釈がつくので、Type.make_concreteも二回呼び出している。Unify.fは一回だけ(戻り値の型注釈と、再帰関数のbody部分の型に矛盾がないかを検査している)。

関数呼び出し:

  | Exp.Call (e1, e2) ->
      let rt = Type.new_var () in
      let t1 = check tenv e1 in
      let t2 = check tenv e2 in
      begin
        Unify.f t1 (Type.Proc (t2, rt));
        rt
      end

関数適用の結果の型は、型検査が進まないとわからない。なので結果に対して新たに型変数を振って、関数部分の型と(引数部分の型 -> 適用結果の型変数)に対してUnify.fを使って矛盾がないか確認した上で、式全体の型としては適用結果の型変数を返す。

これでTypecheckの主要部分は見終わった。次にUnify.fの実装。

まずは単一化したい二つの型の型変数を解決できるだけ解決しておいてからmatchする:

let rec f t1 t2 =
  match Subst.apply t1, Subst.apply t2 with
 ...

Subst.applyで型変数を解決する。この場合解決とは、出てくる型変数すべてを(わかっているだけ)固有の型に変換する、という意味。

もし二つの型が同一なら何もせずに単一化が成功する。

    | t1', t2' when t1' = t2' -> ()

片方が型変数だった場合:

    | Type.Var _ as t1', t2' ->
      if Type.occurs t1' t2' then failwith "No occurrence condition violated"
      else Subst.extend t1' t2'
    | t1', (Type.Var _ as t2') ->
      if Type.occurs t2' t1' then failwith "No occurrence condition violated"
      else Subst.extend t2' t1'

片方が型変数だった場合、その型変数ともう片方の型との対応を追加する形でSubst内の状態を更新する(Subst.extend)。ただし、片方が型変数、もう片方に同じ型変数が使われていた場合、再帰的になってしまうがそれは許されていない。単一化は失敗し型エラーとなる。

どちらも関数型だった場合:

    | Type.Proc (atype1, rtype1), Type.Proc (atype2, rtype2) ->
      begin
        f atype1 atype2;
        f rtype1 rtype2
      end

引数の型どうし、戻り値の型どうしを単一化させて終わり。

上記以外はエラー:

    | _ -> failwith "Unification failed"

単一化する二つの対象が

  • 型が完全に一致
  • 片方が型変数
  • 両方が関数型

以外の場合エラーだというのは考えてみれば納得できると思う。

最後に型変数の環境とも言えるSubstモジュール:

type t = (Type.t * Type.t) list ref

let subst : t = ref [] 
let init () = subst := []

let extend tv t = match tv with
  | Type.Var _ -> subst := (tv, t)::!subst 
  | _ -> failwith "Cannot extend substitution with a non-var LHS"

let rec apply = function
  | Type.Int -> Type.Int
  | Type.Bool -> Type.Bool
  | Type.Proc (t1, t2) ->
      Type.Proc (apply t1, apply t2)
  | Type.Var _ as t1 -> (match List.assoc_opt t1 !subst with
      | Some t2 -> t2
      | None -> t1)
  | Type.Unknown -> failwith "Invalid substitution application to Unknown type"

Substモジュールの中核にあるのは(型変数 * 型) list refのデータ構造で、それを初期化するinit、listに(型変数 * 型)を追加するextendと、型変数を解決する関数applyが定義されている。

これもグローバル変数的なものになっているのは気になる・・・ が、元々はTypecheck.checkSubst.tを引数・戻り値両方に含むような形でコードを書いた(EoPLも同じようなコードになっていた)のだが、それをグローバル変数化したことでTypecheckのコードの見通しがものすごくよくなったという経緯があるので仕方ない。

使ってみる

再帰関数:

>>> let f = proc (x:?) -(x, 1) in
let g = proc(h:?) (h 1) in
(g f)

0

再帰関数:

>>> letrec ? double(x : ?)
  = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2))
  in
  (double 6)

12

型が合わないと:

>>> letrec ? double(x : ?)
  = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2))
  in
  (double zero?(5))

Fatal error: exception Failure("Unification failed")

成功。

というわけでTypecheckでの型検査時に「この二つの型(変数)が同一だと考えて矛盾が生じるかどうか」をUnifyで調べ、矛盾が生じなければその対応関係を型変数環境ともいうべきSubstにどんどん入れていく、というおおまかな流れで型推論が実装できた。

型推論を実装する その2 (型検査のある言語を作る)

前回登場したLETREC言語に型注釈と型検査をつけたCHECKED言語を実装する。

github.com

具体的には無名関数を定義するprocの仮引数、再帰関数を定義するletrecの仮引数と戻り値に対して型注釈を必要とし、その情報を元に型検査する。

CHECKEDで使う型は以下のように定義されている:

type t = Int
       | Bool
       | Proc of t * t

整数と真偽と、あとは任意の二つの型を組み合わせる関数のための再帰型。後者はネストが可能で(Bool -> Bool) -> Intなどといった型を作ったりできる。

型注釈の記述はこんな感じ:

letrec int double(x : int)
  = if zero?(x) then 0 else -((double -(x, 1)), -(0, 2))
  in
  (double 6)

これがパースされて、ASTに取り込まれる:

type t =
  | Const of int
  | Var of string
  | ZeroP of t
  | Diff of t * t
  | If of t * t * t
  | Let of string * t * t
  | Proc of string * Type.t * t
  | Call of t * t
  | LetRec of Type.t * string * string * Type.t * t * t

評価される時点ではこの型は無視される。式評価のためのEvalモジュールおよび評価結果の値を表すValモジュールにはTypeモジュールはまったく出てこない。

そのかわり、Evalモジュールと構造がよく似たTypecheckモジュールが定義されていて、Eval.fが呼ばれる前にTypecheck.fが呼ばれる。

型検査

型検査器の構造は評価器と非常に近い。まずは、変数の型を保持する型環境:

type env = (string * Type.t) list
let empty = []
let rec find tenv s = match tenv with
  | [] -> None
  | (s', t')::tenv' -> if s = s' then Some t' else find tenv' s
let extend tenv s t = (s, t)::tenv

Envと同じように別モジュールにわけてもよかったのだが、横着して同じモジュール内で定義してある。

次に型検査用の再帰関数check

let rec check tenv = function
  | Exp.Const _ -> Type.Int

Constは当然Int型。

ZeroPDiffIf

  | Exp.ZeroP e -> (match check tenv e with
      | Type.Int -> Type.Bool
      | _ -> failwith "Non-numeric type passed to zero?")
  | Exp.Diff (e1, e2) -> (match check tenv e1, check tenv e2 with
      | Type.Int, Type.Int -> Type.Int
      | _ -> failwith "Non-numeric type passed to -(x,y)")
  | Exp.If (e1, e2, e3) -> (match check tenv e1 with
      | Type.Bool ->
          let t = check tenv e2 in
          if t = check tenv e3 then t
          else failwith "Different types in if then and else clauses"
      | _ -> failwith "Non-boolean passed as if condition")

各部分の型が期待通りであることを(再帰的にcheckを呼び出して)確かめ、その上で式全体の型を返す。

変数Var:

  | Exp.Var s -> (match find tenv s with
      | Some t -> t
      | None -> failwith "Variable not typed")

変数に対応する型が型環境に入っているので、それを取得する(評価時に変数に対応する値を環境から取得するのと全く同じ)。

変数束縛Let:

  | Exp.Let (s1, e1, e2) ->
      let t1 = check tenv e1 in
      let tenv' = extend tenv s1 t1 in
      check tenv' e2

変数に束縛される値の型を計算し、その対応関係を型環境にいれてからbody部分(e2)の型検査を行う。

関数Proc:

  | Exp.Proc (s, t, e) ->
      let tenv' = extend tenv s t in
      let rettype = check tenv' e in
      Type.Proc (t, rettype)

仮引数に型注釈がついているので、型環境に仮引数とその型の対応を入れて、関数のbody部分の型を検査。それで帰ってきた型が戻り値の型なので、関数自体の型は(仮引数の型 -> 戻り値の型)となる。

再帰関数LetRec:

  | Exp.LetRec (t1, fname, farg, t2, fbody, e) ->
      let t' = Type.Proc(t2, t1) in
      let tenv' = extend tenv fname t' in
      let tenv'' = extend tenv' farg t2 in
      (ignore @@ check tenv'' fbody; check tenv' e)

再帰関数の再帰部分もProcと同じように型検査しようとすると再帰的呼び出しにあたったところで、型環境に関数名がはいっていなくてエラーになってしまう。なので再帰関数の場合、仮引数だけではなく戻り値の型も注釈が必要で、それを元に関数の型を作成、型環境にいれる。その上で、まず関数body部分を仮引数とその型の対応を入れた新しい型環境を使って型検査し(これで再帰関数の戻り値部分の型注釈が正しいかどうかがわかる)、その後letrec ... in ...の後半部分を検査する。

関数呼び出しCall:

  | Exp.Call (e1, e2) -> (match check tenv e1 with
      | Type.Proc (t1, t2) ->
          if t1 = check tenv e2 then t2
          else failwith "Proc signature and argument types are mismatched"
      | _ -> failwith "Non-proc type in proc position of call")

関数部分の型を調べ、その型の仮引数部分と引数の型が合致しているかを確認した上で、関数の型の戻り値部分を「関数適用」全体の型として返す。

最後にEvalと全く同じように、check関数に空の環境を渡してTypecheck.f関数を作成している:

let f = check empty

使ってみる

高階関数を使ってみる:

>>> let f = proc (x:int) -(x, 1) in
let g = proc(h : (int -> int)) (h 1) in
(g f)

0

高階関数の型を間違えるとエラー:

>>> let f = proc (x:int) -(x, 1) in
let g = proc(h:int) (h 1) in
(g f)

Fatal error: exception Failure("Non-proc type in proc position of call")

再帰を使った例:

>>> letrec int double(x : int) =
if zero?(x) then 0 else -((double -(x, 1)), -(0, 2)) in
(double 6)

12

型があっていないと:

>>> letrec bool double(x : int) =
if zero?(x) then 0 else -((double -(x, 1)), -(0, 2)) in
(double 6)

Fatal error: exception Failure("Non-numeric type passed to -(x,y)")

関数内にあるdoubleの呼び出しがboolを返すはずなのだが、その結果がその後intしか取らないはずの-(x, y)に渡されていて型検査が(正しく)失敗する。

これから

これで前準備は完了となり、次回はついに型推論を実装したINFERRED言語の話。