Arantium Maestum

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

CPS変換はじめてみた

インタプリタ自作によってプログラミング言語の諸概念を学んでいく「Essentials of Programming Languages」の第5章、第6章はどちらも継続渡しスタイルについて語っている。

第5章は「インタプリタを継続渡しスタイルで書くとどうなるか」という話を掘り下げていく内容で、このブログの「めざそう言語処理系の沼」シリーズの元ネタにもなっている。

第6章は「プログラムを継続渡しスタイルに変換してから実行するインタプリタ」についての話だ。ソースに対してCPS変換を行うことで実行が末尾呼び出しの形になったり、複雑な制御フローをCPSの形として脱糖することでインタプリタの評価関数には手を入れることなく実装できたりする、らしい。さらにはCPS変換したソースは最適化した上でコンパイルするのが楽らしい。EoPLにはそういった話題はないが、「最新コンパイラ構成技法」(通称「虎本」)の著者としても有名なAppelの「Compiling with Continuations」というそのままズバリな著作もある。

後者を読んでいくための下準備としても、EoPLの第6章を読んで簡単なCPS変換を行うインタプリタを実装してみたい。

eopl-ocaml/by-lang/cpsmin at master · zehnpaard/eopl-ocaml · GitHub

実装してみた。

ソース言語

言語機能としては

  • S式
  • if分岐
  • 多引数のビルトイン・ユーザ定義関数
  • 関数の仮引数としての変数
  • リテラル整数

が存在している。letletrecはまだない。

使用例

例1変換前:

(+ 1 (- 5 3) 2)

変換後:

(- 5 3 (proc [gensym2]
         (+ 1 gensym2 2 (proc [gensym1] gensym1))))

例2変換前:

((proc [x] (+ (* x x) 1)) 5)

変換後:

((proc [gensym7]
   (gensym7 5 (proc [gensym6] gensym6)))
 (proc [x gensym8]
   (* x x (proc [gensym9]
            (+ gensym9 1 gensym8)))))

例3変換前:

(if (zero? 3) (+ 1 2) (+ 3 4))

変換後:

(zero? 3 (proc [gensym1]
           (if gensym1
             (+ 1 2 (proc [gensym0] gensym0))
             (+ 3 4 (proc [gensym0] gensym0)))))

となる。

コード

CPS変換するためのコードはTocpsモジュールに入っている:

eopl-ocaml/tocps.ml at master · zehnpaard/eopl-ocaml · GitHub

CPS変換するためには、継続の仮引数に今まで使われていない新しい変数を割り当てる必要がある。そのためのgensym関数:

let gensym =
  let n = ref (-1) in
  let f () = incr n; "gensym" ^ (string_of_int !n) in
  f

gensym0などの変数名を作成する。本当は「継続の中に入る式を検査して自由変数が被っていないかを調べる」という手順があったほうがいいのだがめんどくさいので割愛。ソースプログラムにはgensym_という形の変数は出てこないと仮定する。(パーサの仕様でユーザが変数として使えない文字列を使っても良かったかもしれない・・・)

CPS変換する場合、関数呼び出しの一部にリテラルや変数が入っていた場合はその部分は継続化しないようにしたい(継続化してもどっちみち引数である変数がその部分に入るし・・・)。というわけでリテラルや変数かどうかを判定するis_simple関数:

let is_simple = function
| Const _ | Var _ -> true
| _ -> false

ただのパターンマッチである。

次にCPS変換の心臓部になる関数。しかし名前をつけるのが億劫だったのでg。「今からおまえの名前はgだ。いいかい、gだよ」:

let rec g k e = match e with
| Const _ | Var _ -> Call(k,[e])

gの引数は

  • 継続k
  • CPS変換する式e

となる。eリテラルや変数だった場合、継続kにその式を適用するCall(k,[e])CPS変換の結果となる。

関数適用をCPS変換する場合:

| Call(proc,es) ->
  let es = proc::es in
  let es' = List.filter (fun e -> not @@ is_simple e) es in
  let vs' = List.map (fun _ -> gensym ()) es' in
  let evs = List.rev @@ List.combine es' vs' in
  let f e = match List.assoc_opt e evs with
  | None -> e
  | Some v -> Var(v)
  in
  let es = List.map f es in
  let cont_body = Call(List.hd es,List.tl es @ [k]) in
  let g' cont_body (e, v) = g (Proc([v],cont_body)) e in
  List.fold_left g' cont_body evs

関数と実引数のうち、「変数あるいはリテラル整数」ではない(つまりis_simpleでない)ものをes'というリストに入れ、それらにgensymによる変数を割り当てる。それらだけ入れ替えたcont_bodyという式を作り、最終的にList.fold_leftを使ってis_simpleでない要素の分だけ入れ子状態の継続にしている。

ifのケース:

| If(cond,yes,no) ->
  let v = gensym () in
  let cont = Proc([v],If(Var(v),g k yes,g k no)) in
  g cont cond

条件文にあたるcondのところだけ継続化。今見直してみると、ここもis_simpleのチェックを入れたほうが良かった。

関数定義のCPS変換:

| Proc(ss,body) ->
  let v = gensym () in
  Call(k,[Proc(ss@[v], g (Var v) body)])

処理としては:

  • 定義された関数の仮引数の最後に継続のためのものを追加
  • その変数を継続として関数本体の式をgCPS変換
  • 継続kに作成された関数を渡す(この部分は変数やリテラルの扱いと同じ)

という式を返す流れとなる。

これでgの定義は終わり。

あとは終端継続を定義して、それをgに渡すことでトップレベルの式をCPS変換するTocps.fを定義:

let f e =
  let v = gensym () in
  g (Proc([v],Var v)) e

終端継続は値を受け取ってそのまま返す(Proc([v],Var v))という関数になる。

不満

Tocps.fExp.t -> Exp.tで、まるで「同じインタプリタで実行できる言語内での変換」であるように見える。が実際はそうではない。

前述の例をとってみると:

(+ 1 (- 5 3) 2)

(- 5 3 (proc [gensym2] (+ 1 gensym2 2 (proc [gensym1] gensym1))))

+-といったビルトイン関数の挙動が変わっている。具体的には最終引数に継続をとるようになっている。

このことによって、(+ 1 (- 5 3) 2)CPS変換なしにインタプリタに実行させようとすると「最後の引数が関数ではない」とエラーを吐く。

実行できないのはいいとして、それなら実行時エラーではなくコンパイルが通らないほうがいい。

というわけでCPS変換前と後では型を変えたほうがいいように思うので、次はその変更を加えてみたい。

Shibuya.lisp #87 でKontlangについて発表した

もう一週間以上前になるが、Shibuya.lisp #86に続いて#87でもKontlangについて話してきた。

speakerdeck.com

内容としては

  • kontlangの紹介
  • shift/resetのセマンティクスとkontlangにおける実装
  • マクロとモジュール
  • shift/resetとマクロとモジュールを使ったmonadic reflectionライブラリ
  • reify/reflectとreturn/bindの関係

とスライドを用意しながら「多くね?」と思うくらい盛り込んでしまったのだが、スライドを作る前にタイトルを発表してしまったので・・・

しかし説明不足なところは多々あったにせよ、最後の方で失速してしまった前回と違ってとりあえずは話し通せたので良かった。質疑応答で鋭い質問が飛んでくるのは前回と同様で勉強になる。そして自分で実装してブログに記事も書いているというのに、発表するとなるといろいろと再構築し直さなければいけないのも大変ながら勉強になる、気がしている。

他の発表ではephemeronという特殊なガベージコレクションロジックのあるデータ構造についての詳細が知れたり(その後OCamlにもあることをツイッターで知った)と大変有意義な時間だった。

運営のみなさまありがとうございました。

現在Zoomによるオンライン開催で参加しやすくなっているので、迷っている方は是非参加してみてください。Shibuya.lispは楽しいです。

次回話すネタ何かあるかな・・・

Monadic Reflectionについて

kontlang作成の一つの目標は、この資料を元に:

www.slideshare.net

モナドをつくれるようにしてみたい、というものだった。

結果的にMaybe、ListやStateモナドを「つくって」みたのだが。

そもそもこのつくったものは本当にモナドなのか?という疑問が湧いてきた。

挙動はHaskelldo記法に非常に近いが、微妙に違いもあるし、そもそもモナドとはreturnbindがあるものなのでは?

というわけで「モナドをつくろう」の参考資料であるAndrzej FilinskiのRepresenting Monadsと、同じ著者によるMonadic Reflection in Haskellを読んでみた。

Representing Monadsの「5 Implementation and Examples」を見たところ:

(letfn [reflect [m]
  (shift [k] (bind m k))] ...)

(let [reify (macro [expr]
  (reset (return expr)))] ...)

という定義で特定のモナドbindreturn、そしてshiftresetがあればreifyreflectは書ける。

そして論文には出てないようだがreifyreflectがあればreturnbindは書ける:

(letfn [return [a] (reify a)] ...)

(let [bind (macro [m f] (reify (reflect (f (reflect m)))))] ...)

というわけでbindreturnreifyreflectの間にはかなり密接な関係がある。bindreturnreifyreflectだけで定義できるのに対し、reifyreflectbindreturnに加えてshiftresetが必要なことを考えるとreifyreflectのほうが強力なようだ。

reifyreflectとは、モナドAPIであるbindreturnと同程度以上の表現力(?)を持ち、専用のdo構文などを用意せずともdirect styleでモナディックなコードを書けるようにする関数(あるいはマクロ)ということになるだろうか。

というわけで、たしかにreifyreflectを実装しておけばとりあえず「モナドをつくった」と言えそうである。よかったよかった。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その22 モジュール

実装したモナドmapfold_leftなどの関数をライブラリ化することで毎回定義し直さなくても済むようにしたい。

その準備段階としてモジュールを実装する。(ファイルから読み込む場合もモジュールとして扱いたいため)

具体的には

  • (module [...])という構文でモジュール(第1級オブジェクト)を定義
  • (define ... ...)でモジュール内での変数束縛
  • M.xなどでモジュールM内の変数xにアクセス

を追加して

(let [M (module [(define x 5) (define y 10)])]
  (+ M.x M.y))

のような書き方ができるようにする。

今回のコード差分:

Comparing v0.16...v0.17 · zehnpaard/kontlang · GitHub

define

モジュール定義の中でだけ使えるキーワードdefineを追加する。

まずExp

type t =
...
| Define of string * t

let rec get_free bound free = function
...
| Define(_, e) -> get_free bound free e

モジュール内で束縛する変数名を表す文字列と、その変数に束縛する値へと評価される式を持つ。

define式の自由変数は保持している式の中の自由変数である。

define式は独自の値とはならず、式の評価も必ずmodule式の一部として評価される。

なのでExecute.evalで生のExp.Defineに当たると:

let eval env cont = function
...
| Exp.Define _ -> failwith "Define used outside of Module definition"

この通り実行時エラーを吐く。実際にはパーサにも制約をかけてあって、(module [...])の中以外でdefineを使うとパースエラーになるのでこの実行時エラーのケースには到達しない(はず)。

また、独自の値にならないのでValcontモジュールには登場しない。

module

無名モジュールを作成するmodule式を定義する。

まずExp

type t =
...
| Module of t list

let rec get_free bound free = function
...
| Module [] -> free
| Module((Define(s,e))::es) -> get_free (s::bound) (get_free bound free e) (Module es)
| Module(e::es) -> get_free bound (get_free bound free e) (Module es)

モジュールは式のリストを保持する。defineだけではなく、副作用を起こすような任意の式もモジュール内で記述できるので保持する式にはなんの制限もない。

(module
  [(define x 10)
   (define y (+ x 5))]

のように、先にdefineで定義された変数を後々モジュール内で使えるようにするので自由変数を求める時にmoduleの保持する式を再帰的に探っていきdefineの場合は後続の式にとってのbound変数を更新している。

今見直すと再帰するたびにExp.Moduleを解体しては新しく作り直していてあまり効率がよくない。fold_leftで綺麗に書けそうなので今度書き直したい。

次にValcontモジュール:

type valt =
...
| Module of (string * valt) list
and contt =
...
| ModuleExp of Exp.t list * (string * valt) list
| ModuleDefine of string * Exp.t list * (string * valt) list

Module値はモジュール内で束縛されている「変数と値」のリストを保持する。

そして継続としては

  • モジュール式の中のdefine式を評価していることを表すModuleDefine
  • モジュール式の中のdefine以外の式を評価していることを表すModuleExp

を追加。

ModuleExpは未評価の式のリストと、これまで評価済みの「変数と値」のリストを持つ。

ModuleDefineModuleExpのデータに加えて「現在評価中のdefineで束縛される変数の文字列」を持つ。

ではExecute.eval

let eval env cont = function
...
| Exp.Define _ -> failwith "Define used outside of Module definition"

まずはExp.Defineのケース。これは特殊でdefineはモジュール定義内でのみ使われることになっていて、Exp.Moduleの評価やCont.ModuleDefineCont.ModuleExpの継続適用の一部として処理されることになる。パーサの仕様上それ以外の状況で出てくることはないはずだが、もし出現してevalされた場合は実行時エラー。

次にExecute.evalExp.Moduleケース:

| Exp.Module(Exp.Define(s, e)::es) ->
  let env' = []::env in
  let cont' = Cont.add (Cont.ModuleDefine(s, es, [])) @@ Cont.add Cont.Env cont in
  Eval(env', cont', e)
| Exp.Module(e::es) ->
  let env' = []::env in
  let cont' = Cont.add (Cont.ModuleExp(es, [])) @@ Cont.add Cont.Env cont in
  Eval(env', cont', e)
| Exp.Module [] -> ApplyCont(env, cont, Val.Module [])

三つのケースが考えられる:

  • モジュール内の式の先頭がdefineだった場合
  • モジュール内の式の先頭がdefine以外だった場合
  • モジュール内で式定義がなかった場合(つまり(module [])

後者はエラーでもいいと思ったのだが、空のモジュールを禁止する強い理由もないので許容。

モジュール内の式の先頭がdefineだった場合は、変数環境を新しく区切り(モジュール内でdefineを使って定義された変数がそれ以降のモジュール内定義で使用できるようにするため&モジュール定義が終わったら変数環境から外せるようにするため)、Cont.Envを継続に追加。さらにCont.ModuleDefineに「先頭要素以外のモジュール内の式のリスト」と(define x e)xに当たる変数名を保持させて継続に追加。この変数環境と継続で(define x e)eの式を評価する。

モジュール内の式の先頭がdefine以外だった場合もほぼ同じだが、Cont.ModuleDefineの代わりにCont.ModuleExpを使う(変数名は保持しない)。そしてモジュール内の式の先頭要素すべてを評価する((define x e)のように分解して一部を評価、といった手順は踏まない)。

次にExecute.apply_contCont.ModuleDefineケース:

let apply_cont env cont v = match cont with
...
| (Cont.ModuleDefine(s, [], svs)::cont')::cont'' ->
    ApplyCont(env, cont'::cont'', Val.Module((s, v)::svs))

もし未評価の式が残っていなければ、たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加して、それを保持するVal.Module値を作成、それを現在の継続に渡す。(Execute.evalExp.Moduleケースを見れば最初に行われるのは「現在の変数環境を一つ外す」である)

Cont.ModuleDefineに未評価の式が残っていて、その先頭の要素がExp.Defineだったケース:

| (Cont.ModuleDefine(s, Exp.Define(s', e')::es, svs)::cont')::cont'' ->
    let env' = Env.extend_current s v env in
    let cont''' = Cont.add (Cont.ModuleDefine(s', es, (s,v)::svs)) (cont'::cont'')in
    Eval(env', cont''', e')

たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加すると同時に変数環境にも追加。先頭の要素がExp.Defineなので、次の継続もCont.ModuleDefineとなる。その新しいCont.ModuleDefineを継続に追加してから新しい変数環境と継続でExp.Defineの保持する式を評価する。

Cont.ModuleDefineに未評価の式が残っていて、その先頭の要素がExp.Define以外だったケース:

| (Cont.ModuleDefine(s, e::es, svs)::cont')::cont'' ->
    let env' = Env.extend_current s v env in
    let cont''' = Cont.add (Cont.ModuleExp(es, (s,v)::svs)) (cont'::cont'')in
    Eval(env', cont''', e)

たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加すると同時に変数環境にも追加(これは直前のケースとまったく同じ)。次の継続はCont.ModuleExpとなる。未評価の式の先頭要素を新しい変数環境と継続で評価する。

Execute.apply_contCont.ModuleExpのケース:

| (Cont.ModuleExp([], svs)::cont')::cont'' ->
    ApplyCont(env, cont'::cont'', Val.Module svs)
| (Cont.ModuleExp(Exp.Define(s', e')::es, svs)::cont')::cont'' ->
    let cont''' = Cont.add (Cont.ModuleDefine(s', es, svs)) (cont'::cont'')in
    Eval(env, cont''', e')
| (Cont.ModuleExp(e::es, svs)::cont')::cont'' ->
    let cont''' = Cont.add (Cont.ModuleExp(es, svs)) (cont'::cont'')in
    Eval(env, cont''', e)

ModuleDefineから少々修正しただけなので詳細は割愛。

ここまでで(module [(define x 5) (define y 10) (define f (fn [a b] (+ a b)))])のようなモジュールが作成できるようになった。

モジュール変数にアクセス

モジュールを作ったはいいが、中の変数にアクセスする方法が必要。

というわけでM.xM.N.yのようにドット記法でモジュールの中身にアクセスできるようにする。M.N.yは「Mモジュール内の変数Nに束縛されているモジュールのy変数にアクセス」という意味になる。

まずはExpモジュールで式を定義:

type t =
...
| MVar of string list

let rec get_free bound free = function
...
| MVar [] -> free
| MVar(s::_) -> if (List.mem s bound) then free else s::free

MVarはモジュール変数の意。M.N.yだとMVar ["M"; "N"; "y"]と表現されることになる。

自由変数検出に関しては、先頭の要素のみ検出される。つまりM.N.yというモジュール変数が出てきた場合、Mはもしかすると自由変数かもしれないが、Nyは自由変数にはなり得ない。

珍しくlexerのコードも載せてみる:

let char = ['a'-'z' 'A'-'Z' '+' '-' '*' '/' '<' '>' '=' '!' '?' '_']
let number = ('0'|['1'-'9'] digit*)
let variable = char (char|digit)*
let mvariable = variable '.' variable ('.' variable)*

rule f = parse
...
  | mvariable as s { Parser.MVAR (String.split_on_char '.' s) }

mvariableという正規表現っぽいパターンにマッチした文字列をString.split_on_chat '.'で分割したリストをMVARとしてパーサに渡している。

Execute.eval

let eval env cont = function
...
| Exp.MVar([]) -> failwith "Evaluating invalid/empty module var"
| Exp.MVar(s::ss) ->
  let m = Env.find s env in
  let f m s = match m with
  | Val.Module svs -> (match List.assoc_opt s svs with
    | Some n -> n
    | None -> failwith @@ Printf.sprintf "Member %s of module does not exist" s)
  | _ -> failwith @@ "Accessing member of non-module"
  in
  let v = List.fold_left f m ss in
  ApplyCont(env, cont, v)

Exp.MVarが空リストということはパーサ上あり得ないが、パターンマッチの網羅性のために実行時エラーになるケースを追加しておく。

Exp.MVarの変数名リストに要素が含まれている場合はまず先頭要素の変数を現在の変数環境の中から探して、その値を起点にfold_leftで残りの変数名リストを解決していく。変数が見つからない場合と最後の変数名以外がモジュールでない値であった場合には実行時エラーとなる。

これでモジュールの基本機能である「作成」と「アクセス」は完了。

再掲になるが:

(let [M (module [(define x 5) (define y 10)])]
  (+ M.x M.y))

のような書き方ができて、結果は15になる。

次回

次は外部ファイルからモジュールを読み込めるようにする。

merlinサポートのあるエディタでOCamlを書いていて微妙にイラっとくること

私は現在Visual Studio CodeOCaml & Reason IDEを使っている。

全般的に非常に気に入っているのだが、一つ頻繁に起きて心をすこしだけささくれ立たせることがあるので書き出しておく。OCaml & Reason IDEプラグインはエラー検出などにmerlinを使っているのでこれは多分VS Code特有の挙動ではないと思う。

ちなみにこれはプラグインやmerlinに対する批判を意図するものではないことは先に断っておく。

例えばこんな型があるとして:

type t =
| Int of int
| Var of string
| Let of (string * t) list * t
| Add of t * t

この型に対するパターンマッチを書くとする:

let rec eval = function
| Int n -> n

とここまで書くとfunctionから-> nまで全部赤線でエラーだと注意される。

This pattern match is not exhaustive...

云々。

もちろん言いたいことはわかるし、コンパイル前にパターンマッチが網羅的でないことを教えてくれるのはありがたい、のだが。

「今書いてるところだから!さらに他のエラーはないのか?!」と強く言いたくなる。

let rec eval env = function
| Int n -> n
| Var s -> find env s
| Let sts e -> eval (sts :: env) e

とここまで書いてもfunction以降は全部赤線である。本当はsts :: envじゃなくてsts @ envであるべき、などの型エラーも隠してくれたりする。書いた瞬間に教えてくれるのがエディタによるエラーハイライトの利点じゃないのか・・・

なのでちょっと大きめのパターンマッチを書くときは必ず:

let rec eval env = function
| _ -> failwith ""

とすべてのパターンにマッチし、どんな型とも整合性の取れるケースを追加しておく。

そしてすべてのケースを書き終わったと思ったら取り除いて網羅的かどうか確認する。

これで挙動としてはいいのだが、毎回毎回同じ行を書いては消し、書いては消しとやっているのもなんだか癪で、他によりスマートな方法があるのでは?と考えてしまう。

もしご存知のかたがいたらぜひ教えてほしい。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その21 やはり俺のListモナドはまちがっている。

前回こう書いた:

ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた

今回はその話。

reifyの型

Representing Monadsreifyreflectの型定義:

signature RMONAD = 
  sig
    structure M : MONAD
    val reflect : '1a M.t -> '1a
    val reify : (unit -> 'a) -> 'a M.t
  end;

これを見てみるとreify'a型を返すthunkを引数にとり、'aを包んだモナディックな値を返す、という型になっている。(前回の記事でも言及したが、Kontlangではreifyはマクロなので(unit -> 'a)なthunk関数ではなく、評価されたら'a型になる式をそのまま受け取れる)

それに対して、前々回でListモナドを使ってみた時、このような形で書いた:

(reify
  (let [(x (reflect (list 1 2 3 4 5)))
        (y (reflect (list 1 2 3 4 5)))
        (z (reflect (list 1 2 3 4 5)))]
    (if (= (* z z)
           (+ (* x x)
              (* y y)))
      (return (list x y z))
      nil)))

reifyの中の式が返す値は(return ...)nilで、どちらもモナディックな値(この場合リスト)となっている。((return (list x y z))(list x y z)returnでさらにネストした要素1のリストに変換していることに注意)

これだとreifyの型は(unit -> 'a M.t) -> 'a M.tとなってしまう。

実際reifyの定義もこうなっていた:

(define reify (macro [expr] (reset expr)))

resetに包むだけで他の変換は何もしていないわけだから、(unit -> 'a M.t) -> 'a M.tなのも当然とも言える。

そう考えると正しい定義は:

(define reify (macro [expr] (reset (list expr))))

このように式の結果をモナディックな値(Listモナドなら当然リスト)に変換する処理を入れるのが大事。こうすれば(return (list x y z))からreturnが省ける。

しかし今度はif分岐のもう一つの結果であるnilが問題となってくる。こちらもreify(reset (list expr))でリスト化されてしまって、最終的な結果に残ってしまう(例えば(nil nil ... (3 4 5) nil ... (4 3 5) ...)のような結果が返ってくる)。

nilの代わりに「分岐のこちら側は失敗でなんの結果も返さない」という意味の処理が必要となる。

failあるいは(reflect nil)

この問題の解決方法もやはりRepresenting Monadsに書かれていた。

failという関数を定義して使えばいい:

(letfn [fail [] (reflect nil)]
  ...)

少し非直観的なのでreflect関数の挙動を考えてみる。

複数の要素が含まれるリストをreflectすると、それ以降の処理が各要素につき一回ずつ、バックトラックで行われる。

素数1のリストをreflectすると、それ以降の処理がその一つの要素に関してのみ実行される。なので(let [a (reflect (list b))] ...)(let [a b] ...)と変わらない。

では空リストをreflectするとどうなるのか?それ以降の処理を適用する要素がないので、そのまま実行を打ち切り、なんの結果も返さずにバックトラックする。

この挙動が(if condition result nil)nilの部分に本当に欲しかったものだ。

なので(letfn [fail [] (reflect nil)] ...)で「空リストをreflect」を実行する引数0の関数failを定義する。

これで「この式が評価されるところまで来たらなんの結果も返さずに処理を打ち切ってバックトラック」というポイントを(fail)で指定できる。

使ってみる:

修正したreifyと追加したfailを前述の例で使ってみる:

(reify
  (let [(x (reflect (list 1 2 3 4 5)))
        (y (reflect (list 1 2 3 4 5)))
        (z (reflect (list 1 2 3 4 5)))]
    (if (= (* z z)
           (+ (* x x)
              (* y y)))
      (list x y z)
      (fail))))

これでreifyのなかの式は返り値がモナディックではない値でよくなった(わかりにくいことにこのケースではそれでも返り値はリストだが、「モナドとしてのリスト」ではない)。

気になるのはfailの型だが・・・ なんの値も返さない(nilすら)ので、逆になんの型とも矛盾しないということで() -> 'aになるのか・・・?まあkontlangは動的型付けなのであまり関係ないが・・・

次回

次は話を戻してモジュールの実装を進めていく。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その20 Stateモナドとreflect

前回このように書いた:

Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。

しかし「限定継続を使ってモナドを表現する」というアイデアの元となるRepresenting Monadsという論文を読み直していたらちゃんとStateモナドreflectについても書かれていたので訂正したい。

モジュールの話はまた後々。

reflectの定義

そもそもreflectとは何をする関数なのか。

前述の論文を当たってみると:

signature RMONAD = 
  sig
    structure M : MONAD
    val reflect : '1a M.t -> '1a
    val reify : (unit -> 'a) -> 'a M.t
  end;

というSMLでのモジュールシグニチャ(つまりモジュールの型)定義が出てくる。

reflectは何らかのモナディックな値を引数にとり、モナディックではない値を返す関数とのこと。

逆にreifyは「モナディックではない値を返すthunk」を引数にとり、モナディックな値を返す関数となっている。(SMLではreifyはマクロではなく関数なので、評価を遅延させるために引数0のthunk関数を使っている)

例えばListモナドを例にとると:

(reify
  (let [(a (reflect (list 1 2 3)))
        (b (reflect (list 4 5 6)))]
    ...))

この場合モナディックな値とはリストのことなので、(list 1 2 3)(list 4 5 6)の部分である。

それらを包んだreflectの結果を束縛しているabは確かにリストではなく整数として扱われている。reifyの中でというのが前提条件だが、確かにreflectはモナディックな値を普通の値に変換する役割を持つようだ。

(ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた。次の記事で修正する話を書きたい)

Stateモナドにおけるモナディックな値

reflectがモナディックな値を普通の値に変換することがわかった。

それではStateモナドにとっての「モナディックな値」とは何だろうか?

reifyは「モナディックではない値を返すthunk」を引数にとり、モナディックな値を返す関数

という型情報から、(reify ...)が返す値がStateにとってのモナディックな値(の型)であることがわかる。

reifyの定義:

(define reify
  (macro [expr]
    (reset
      (let [result expr]
        (fn [state] (cons result state))))))

というわけで(fn [state] (cons ... ...))という関数がStateモナドのモナディックな値の形である。

直感的な説明としては「現在の状態を引数にとり、計算結果である値と次の状態のタプルを返す関数」だ。

Stateモナドreflect

このStateモナドの型定義と前述のreflectの型定義:

reflectは何らかのモナディックな値を引数にとり、モナディックではない値を返す関数

これらを踏まえてreflectを書いてみる:

(letfn [reflect [f]
  (shift [k]
    (fn [state]
      (let* [(val-state (f state))
             (val (car val-state))
             (state1 (cdr val-state))]
        ((k val) state1))))]
  ...)

reflectの引数である関数fstateを引数として渡され、(cons val state1)を返しているので正しくStateモナドのモナディック値(fn [state] (cons .. ..))という形になっていることが確認できる。

shift内で「モナディックではない値を返す」とは限定継続にモナディックではない値を渡すということ。((k val) state1)とやっているのでそこもクリアしている。

次はreflectを使ってgetputを書き直す:

(letfn [get []
  (reflect
    (fn [state] (cons state state)))]
  ...)

(letfn [put [val]
  (reflect
    (fn [state] (cons nil val)))]
  ...)

getは「限定継続に渡す値」も「次の状態」も、引数であるstateをそのまま使っている。なので「状態を変更せずに、現在の状態を値として取り出す」という挙動となる。

put valは「限定継続に渡す値」はnil、「次の状態」はvalとなる。「返す値はnilで状態だけをセットする」という挙動だ。

前回使った「shift/resetプログラミング入門」の例題をreflectも使って書くと:

(run_state
  (reify
    (let* [(tick
             (fn []
               (reflect
                 (fn [state] (cons nil (+ state 1))))))
           (_ (tick))
           (_ (tick))
           (a (get))
           (_ (tick))]
       (- (get) a)))
  0)

これもちゃんと(1 . 3)という結果が返ってくる。

次回

次回はListモナドを修正して型がちゃんとあうようにする。