ocamllexのlexerとmenhirのparserの間に任意のOCamlコードによる変換を挿入する
OCamlでパーサを書く場合
- lexerをocamllexで書く
- そのlexerを受け取るparserをmenhirで書く
というのが最近の鉄板のようだ。
let lexbuf = Lexing.from_channel stdin in let exp = Parser.f Lexer.f lexbuf in print (eval exp)
というような流れ。
ocamllexもmenhirも構文が普通のOCamlではなく、いったん独自構文で書かれた.mll/.mlyファイルを両ツールでOCamlの.mlに変換してから普通のOCamlモジュールとして使う。
なので長らくぱっと見どうやってocamllex製のlexerが返すトークンに対して任意の変換を行ってからmenhir製のparserに渡せばいいのか、イメージが湧かなかった。
しかし実際にやってみたら拍子抜けするほど簡単。
パースしたい言語
たし算をネストしたインデントで表現するこんな言語を考えてみたい：
+
1
2
+
3
4
5
これが(+ 1 2 (+ 3 4) 5)のようにパースされてほしい。
インデントをパースするための方針としては
- lexerは改行後のスペースの数を数えて
SPACE nというトークンを作成する - parserに渡す前にlexerのトークンを解析し、
SPACE nをINDENT、DEDENT、BRといった新しいトークンに変換する - 変換済みのトークンをparserに渡す。parserの規則には
SPACEは出て来ず、INDENT、DEDENT、BRでマッチする
lexer
ocamllexで定義するlexerはこんな感じ：
{ open Parser } let digit = ['0'-'9'] let num = (digit | ['1'-'9'] digit*) let indent = '\n' ' '* let whitespace = [' ' '\t'] rule f = parse | indent as s { SPACE (String.length s - 1) } | whitespace+ { f lexbuf } | num as n { INT (int_of_string n) } | "+" { ADD } | eof { EOF }
'\n' ' '*という文字列がマッチされ、SPACE (String.length s - 1)で（改行を除いた）空白の文字数を保持するSPACEトークンが作成されている。
これをocamllexに通すとLexerというモジュールが作成され、その中のf関数が目的のlexerである。
Lexer.fの型は
val f : Lexing.lexbuf -> Parser.token
Lexing.lexbufというOCaml標準ライブラリ内のlexer用の文字列データ型を引数として、menhirに渡す予定のparser.mlyで定義されているtoken型を一つ返す。
ミュータブルなlexbufを受け取り、副作用的にlexbufから文字を必要なだけ「消費」して一つのtokenを返す、という仕様だ。
終端tokenが帰ってくるまで何回でも同じlexbufを引数にLexer.fが呼ばれる想定となる。
parser
parser.mlyはこんな感じ：
%token <int> INT %token ADD %token EOF %token <int> SPACE %token INDENT %token DEDENT %token BR %start f <Exp.t> %% f : e = expr; EOF { e } expr : | n = INT; BR { Exp.Int n } | ADD; BR; INDENT; es = list(expr); DEDENT { Exp.Add es }
これもmenhirを通すとParserというモジュールになり、その中のf関数がparserとなる。
型は：
val f : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> Exp.t
lexerとlexbufを受け取り、別モジュールで定義されているExp.t型のASTを返す。
この関数の内部実装は確認していないが、前述の通りLexing.lexbuf -> token型の第一引数を第二引数のlexbufに対して何回も（終端トークンがでてくるまで）適用しているようだ。
ならLexer.fをラップしたLexing.lexbuf -> token型の関数を用意してやればいい。
indenter
それがIndenter.f関数：
module P = Parser let convert_space_to_indent width f = let indent = ref 0 in let make_indent _ = [P.BR; P.INDENT] in let make_dedent _ = [P.BR; P.DEDENT] in let g h a b = List.init (a - b) h |> List.concat in fun lexbuf -> match f lexbuf with | P.SPACE n -> let m = n / width in let k = !indent in if m > k then (indent := m; g make_indent m k) else if m < k then (indent := m; g make_dedent k m) else [P.BR] | P.EOF -> let k = !indent in (indent := 0; g make_dedent k 0 @ [P.EOF]) | e -> [e] let flatten f = let xs = ref [] in fun lexbuf -> match !xs with | x::xs' -> xs := xs'; x | [] -> (match f lexbuf with | x::xs' -> xs := xs'; x | [] -> failwith "Lexer did not return EOF token") let f = Lexer.f |> convert_space_to_indent 2 |> flatten
convert_space_to_indent関数はindent一つ分のスペース数の指定と、lexbuf -> tokenな関数（この場合はLexer.fを想定している）を引数に取り、lexbuf -> token listな関数を返す。
その返ってきた関数はlexbufを受け取り、Lexer.fに渡し、戻ってきたトークンが：
- SPACEなら現在のインデントレベル（クロージャにrefとして保持されている）と比較し、インデントレベルの変更があればクロージャを変更したのちINDENT, DEDENT, BRトークンを必要なだけ返す。インデントに変更がなければBRだけのリストを返す。
- EOFなら現在のインデントレベル分のDEDENTとEOFの入ったリストを返す
- SPACEかEOF以外ならそのトークンだけが入ったリストを返す
flattenはlexbuf -> token listな関数を引数に取り、lexbuf -> tokenな関数を返す。
クロージャに保持しているlist refにいったんtoken listを格納して、そのlistが空じゃない場合はlexbufをまったく消費せずにそのlistからトークンを返す仕様になっている。
この二つをLexer.fと組み合わせてIndenter.fを作っている。
ただ、見返してみると、この実装だとIndenterモジュールの中にmutable stateを持ち込んでいてあまりよろしくない。
let f n = Lexer.f |> convert_space_to_indent n |> flatten
として呼び出す側で(Indenter.f 2)などと新しくクロージャを作成するようにしたほうがいい。
使い方
あとはまあ使うだけ：
let rec eval = function | Exp.Int n -> n | Exp.Add ns -> List.map eval ns |> List.fold_left (+) 0 let _ = Lexing.from_channel stdin |> Parser.f Indenter.f |> eval |> string_of_int |> print_endline
普通だったらParser.f Lexer.fとしてるところをParser.f Indenter.fとしている。
まとめ
基本的にmenhirで作ったパーサにはLexing.lexbuf -> token型で呼び出すごとにtokenが返ってくるような関数を渡してやればいいだけなので、内部状態をクロージャとして持つ関数でocamllex製のlexerをラップしてしまえば任意のコードでトークンストリームを変換できることがわかった。
今回のgist：
OCamlで相互再帰な型を二つのModuleにわける方法二つ
Essentials of Programming LanguageをOCamlで実装するのをぼちぼちとすすめている。
前回LETを実装した時「式を評価した結果の値」を表す型とその型に対する関数を集めたValと「変数とそれに対応する値の対応関係を保持する環境」のモジュールEnvを作った。
上記の説明からも推測できると思うが、Envの定義にVal.tが使われている:
type t = (string * Val.t) list
次に実装するPROC言語では第一級関数が定義できる。関数が変数の値となりえるのでVal.tのバリアントの一つとしてProcが追加される。そしてそのProcはクロージャを持つ、つまり変数環境を保持する必要がある。
type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t
しかしEnvの定義にVal.tが使われており、Val.tの定義にEnv.tを使おうとすると相互再帰になってしまう。どうしよう。
解決策が二つわかった（一つは@camloebaさんに教えてもらった。ありがとうございます！）のでメモ。
相互再帰的なモジュール
一つ目のやりかたはモジュール自体を相互再帰的にしてしまうことだ。
PROC言語はその方法で実装してみた：
Valenv.mlというモジュールでmodule rec ... and ...という構文を使ってValとEnvを相互再帰的に実装する：
module rec Val : sig type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t val to_str : t -> string end = struct type t = Num of int | Bool of bool | Proc of string * Exp.t * Env.t let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False" | Proc _ -> "Proc" end and Env : sig type t val empty : t val find : t -> string -> Val.t option val extend : t -> string -> Val.t -> t end = struct type t = (string * Val.t) list let empty = [] let rec find env s = match env with | [] -> None | (s', v')::env' -> if s = s' then Some v' else find env' s let extend env s v = (s, v)::env end
あとはValenv.mliでsignatureだけ明示して、Val.mlとEnv.mlでinclude Valenv.Val、include Valenv.Envするだけ。
少々かったるい点としては相互再帰的モジュールはValenv.ml内で実装を定義するときもsignatureが必要なので同じものが.mlと.mliで重複すること。
相互再帰的な型を定義し、それを使ってモジュールを定義する
相互再帰的な型とモジュールについてツイッターでつぶやいたら以下のようにご教示いただいた：
こんにちは。それをおすすめします。再帰モジュールにしてもいいですが、実装ファイルを分けれるわけでもなく、あまり嬉しくないです
— Jun Furuse 🐫🌴 (@camloeba) 2019年6月3日
type t1 = Foo of t2 and t2 = Bar of t1
— Jun Furuse 🐫🌴 (@camloeba) 2019年6月3日
module A = struct
type t = t1 = Foo of t2
...
end
module B : sig
type t
end = strucr
type t = t2
...
end
とかできます
type t = t1 = Foo of t2の構文が私が躓いていたポイントで、こう書かないとA.Foo x2のようにコンストラクタが使えなくなってしまう。
LETREC言語はこのデザインで実装してみた：
Valenv.mlはこんな感じ：
type valt = Num of int | Bool of bool | Proc of string * Exp.t * envt and envt = Empty | Extend of string * valt * envt | ExtendRec of string * string * Exp.t * envt module Val = struct type t = valt = Num of int | Bool of bool | Proc of string * Exp.t * envt let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False" | Proc _ -> "Proc" end module Env = struct type t = envt let empty = Empty let rec find env s = match env with | Empty -> None | Extend (s', v', env') -> if s = s' then Some v' else find env' s | ExtendRec (fname, arg, body, env') -> if s = fname then Some (Val.Proc (arg, body, env)) else find env' s let extend env s v = Extend (s, v, env) let extend_rec env f a b = ExtendRec (f, a, b, env) end
Valenv.mliにはvaltの具体型、envtの抽象型そしてValとEnvのsignatureを書く：
type envt type valt = Num of int | Bool of bool | Proc of string * Exp.t * envt module Val : sig type t = valt = Num of int | Bool of bool | Proc of string * Exp.t * envt val to_str : t -> string end module Env : sig type t = envt val empty : t val find : t -> string -> valt option val extend : t -> string -> valt -> t val extend_rec : t -> string -> string -> Exp.t -> t end
Val.mlとEnv.mlでinclude Valenv.Val、include Valenv.EnvするだけなのはPROCと同じ。
雑考
実はValenvではvaltとenvtの定義だけをしてVal.mlとEnv.mlで各モジュールの内容を定義できれば、と考えていたのだが、その場合うまくenvtを抽象型にする方法が思い浮かばなかったので断念。Env.mlの中ではenvtの実装を使う必要があるので・・・ C++のFriend的な定義ができれば（EnvモジュールがVarenvの実装に特権的にアクセスできるような指定ができれば）解決するのだが、そういう言語機能はなさそう。
EoPLのLetlangをocamllex/menhir/duneで実装してみた
前回の記事の構成に従って、簡単な言語のインタプリタを実装してみた。
Essentials of Programming Languagesという本の最初に出てくるLETという言語で、機能としては整数値の引き算、0チェック、if式による分岐、let式による変数束縛。関数定義などはできない。
一例：
let x = 5 in
let y = if zero?(x) then 1 else 2 in
-(x, y)
これは3に評価される。
ディレクトリ構成は以下の通り：
├── bin
│ ├── dune
│ └── ex.ml #ライブラリを呼び出して実行するプログラム
├── dune-project
└── src #ライブラリ部分
├── dune
├── env.ml #変数環境の実装
├── env.mli #変数環境のインタフェース
├── eval.ml #評価器の実装
├── eval.mli #評価器のインタフェース
├── exp.mli #AST式の型定義
├── lexer.mll #OCamllexを使ったLexer
├── parser.mly #Menhirを使ったParser
├── val.ml #評価結果である「値」の実装
└── val.mli #「値」のインタフェース
式
LETには文は存在せず、式しかない。のでASTもすべて式だけで表現できる。
その式の型はsrc/exp.mliに定義されている：
type t = | Const of int #数値リテラル | Diff of t * t #二つの式の評価値の差 | ZeroP of t #式の評価値が0か | If of t * t * t #If式 | Var of string #変数 | Let of string * t * t #letによる変数束縛
Expモジュールはこの一つの型のためのみに存在するので、モジュール内で定義される型はOCamlの慣習に則ってtype tである。Expモジュールの外からはExp.tなどとモジュールを指定して使う。
また、Expモジュールには型の定義しか存在しないので、インタフェースである.mliだけが書かれている。
値
式を評価した結果の値を表現する型はsrc/val.mliとsrc/val.mlで定義されている。
val.mli:
type t = | Num of int | Bool of bool val to_str: t -> string
val.ml:
type t = | Num of int | Bool of bool let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False"
型定義が.mlと.mliで重複するのはよくあることらしい。
LET言語では、式を評価した結果は数値か真偽値のみとなる。それを表現する型と、それを文字列に変換する関数。
Parser
src/parser.mly:
%token <int> INT %token <string> ID %token DIFF %token LPAREN %token RPAREN %token COMMA %token ZERO %token IF %token THEN %token ELSE %token LET %token EQ %token IN %token EOF %start <Exp.t> f %% f : e = expr; EOF { e } expr : | n = INT { Exp.Const n } | DIFF; LPAREN; e1 = expr; COMMA; e2 = expr; RPAREN { Exp.Diff (e1, e2) } | ZERO; LPAREN; e = expr; RPAREN { Exp.ZeroP e } | IF; e1 = expr; THEN; e2 = expr; ELSE; e3 = expr { Exp.If (e1, e2, e3) } | v = ID { Exp.Var v } | LET; v = ID; EQ; e1 = expr; IN; e2 = expr { Exp.Let (v, e1, e2) }
これは普通のOCamlではなく、Menhirというパーサジェネレータに与えるOCamlチックな独自表記である。なのでファイル拡張子もmlyである。まずparser.mlyが普通のOCamlに変換されてから全体がコンパイルされる。（そういったbuild指定はduneファイルで行われる）
Lexerから受け取れるトークンをまず指定し、そのトークンの組み合わせのパターンマッチでExp.t型の戻り値を返す（パターンマッチは当然再帰的）。
最終的に%start <Exp.t> fとf : e = expr; EOF { e }の部分で定義されているfがパーサ関数となる。
Lexer
LexerはOcamllexを使う。Parserと同じく、OCamlではなく独自表記の.mll拡張子。
src/lexer.mll:
{ open Parser } let digit = ['0'-'9'] let number = '-'? digit digit* let whitespace = ['\t' ' ' '\n'] let char = ['a'-'z' 'A'-'Z'] let identifier = char (char|digit)* rule tokenize = parse | whitespace+ { tokenize lexbuf } | number as n { INT (int_of_string n ) } | "-" { DIFF } | "(" { LPAREN } | ")" { RPAREN } | "," { COMMA } | "zero?" { ZERO } | "if" { IF } | "then" { THEN } | "else" { ELSE } | "let" { LET } | "=" { EQ } | "in" { IN } | identifier { ID (Lexing.lexeme lexbuf) } | eof { EOF }
このソースがOcamllexに変換されてOCamlコードになると、rule tokenize = parse ...のtokenizeがlexer関数名となる。（これもfでもよかったかも・・・）
変数環境
LETにはlet式による変数束縛があるので、式の中で変数が出てきた場合、なんの値に束縛されているかを評価時に調べなくてはいけない。
そのため、式の評価には式そのものの他に変数環境が必要である。src/env.mliとsrc/env.mlに定義されている。
env.mli:
type t val empty: t val find: t -> string -> Val.t option val extend: t -> string -> Val.t -> t
env.ml:
type t = (string * Val.t) list let empty = [] let rec find env s = match env with | [] -> None | (s', v)::env' -> if s = s' then Some v else find env' s let extend env s v = (s, v)::env
変数環境の実装は単なる(変数名 * 値)のタプルのリストで、初期値emptyと関数find、extendが定義されている。.mliではtype tとしか定義されていないのでEnvモジュールの外では(string * Val.t) listをVal.t型として扱うことはできない（型の実装が隠蔽されている）。
評価器
LET言語の評価器はsrc/eval.mliとsrc/eval.mlで定義されている。
eval.mli:
val f: Exp.t -> Val.t
eval.ml:
let rec eval' env = function | Exp.Const n -> Val.Num n | Exp.Diff (e1, e2) -> (match eval' env e1, eval' env e2 with | Val.Num n, Val.Num m -> Val.Num (n - m) | _ -> failwith "Diffing non-numeric values") | Exp.ZeroP e -> (match eval' env e with | Val.Num n -> Val.Bool (n = 0) | _ -> failwith "Zero-checking non-numeric value") | Exp.If (e1, e2, e3) -> (match eval' env e1 with | Val.Bool b -> eval' env (if b then e2 else e3) | _ -> failwith "If-condition on non-boolean value") | Exp.Var s -> (match Env.find env s with | Some x -> x | None -> failwith "Variable not in environment") | Exp.Let (s1, e1, e2) -> let v1 = eval' env e1 in let env' = Env.extend env s1 v1 in eval' env' e2 let f = eval' Env.empty
Evalモジュールは一つの関数fのみを外部に提供する。内部実装としては、式とともに変数環境を引数にとる再帰関数eval'をまず定義し、eval'に空の変数環境を渡したものがfになる。
Build指示
Buildの指示は前述の通りsrc/duneに書いてある：
(menhir (modules parser)) (ocamllex lexer) (library (name letlang) (modules_without_implementation exp))
- Parserはmenhirで前処理すること
- Lexerはocamllexで前処理すること
- Expモジュールはインタフェース
.mliのみであること - ライブラリ全体の名前は
Letlangであること
が指定されている。
実行プログラム
bin/ex.ml:
open Letlang let _ = Lexing.from_channel stdin |> Parser.f Lexer.tokenize |> Eval.f |> Val.to_str |> print_endline
stdinをパーサに渡し（パーサはParser.fにLexer.tokenizeを第一引数として渡したもの）、評価し、結果を文字列化して出力する。
これのbuild指示はbin/duneにある：
(executable (name ex) (libraries letlang))
それ以外
ついでにsrcとbinの上のディレクトリにdune-projectというファイルがある：
(lang dune 1.0) (using menhir 1.0)
duneとmenhirのバージョン指定。
実行
実行するにはdune execというコマンドを使う。
たとえば
> echo "let x = 5 in -(x, 1)" | dune exec bin/ex.bc 4
あるいは記事冒頭にあるサンプルプログラムのtest.txtファイルを作って：
let x = 5 in
let y = if zero?(x) then 1 else 2 in
-(x, y)
catで流し込む：
> cat test.txt | dune exec bin/ex.bc 3
成功。
OCamlで言語処理系覚え書き ocamllex/menhirパーサをduneでビルドする
OCamlでocamllexとmenhirを使ったパーサを書き、duneでビルドする場合の構成を調べていて、ようやく少しわかってきたので備忘録的に書き留めておく。
例として整数のたし算をパースして評価する非常に簡単な計算プログラムを実装する。
ディレクトリ構成
.
├── dune-project
├── src
│ ├── ast.ml
│ ├── parser.mly
│ ├── lexer.mll
│ └── dune
└── bin
├── ex.ml
└── dune
トップレベル
dune-projectが以下のように定義されている：
(lang dune 1.0) (using menhir 1.0)
srcディレクトリ内
src/ast.mlでAST定義：
type expr = | Int of int | Plus of expr * expr
そのAST定義を使ってMenhir Parserをsrc/parser.mlyで定義：
%{ open Ast %} %token LPAREN %token RPAREN %token EOF %token <int> INT %token PLUS %left PLUS %start <Ast.expr> prog %% prog: | e = expr EOF { e } expr: | LPAREN; e = expr; RPAREN { e } | i = INT { Int i } | e1 = expr; PLUS; e2 = expr { Plus (e1, e2) }
parserで定義されているtokenを出力するsrc/lexer.mll:
{ open Parser } let digit = ['0'-'9'] let number = '-'? digit digit* let whitespace = ['\t' ' ' '\n'] rule tokenize = parse | whitespace+ { tokenize lexbuf } | "(" { LPAREN } | ")" { RPAREN } | "+" { PLUS } | number as n { INT (int_of_string n ) } | eof { EOF }
srcディレクトリにあるast.ml、parser.mly、lexer.mllをadderというライブラリとしてビルドするためのsrc/duneファイル：
(menhir (modules parser)) (ocamllex lexer) (library (name adder))
binディレクトリ内
adderライブラリを使うmain関数的なものが定義されているex.ml:
open Adder let rec pprint = function | Ast.Int n -> string_of_int n | Ast.Plus (n, m) -> Printf.sprintf "(Plus %s %s)" (pprint n) (pprint m) let rec eval = function | Ast.Int n -> n | Ast.Plus (n, m) -> eval n + eval m let _ = let lexbuf = Lexing.from_channel stdin in let expr = Parser.prog Lexer.tokenize lexbuf in Printf.printf "%s = %d\n" (pprint expr) (eval expr)
bin/duneファイル：
(executable (name ex) (libraries adder))
実行
shellで：
> echo '1+2+(3+4)+5' | dune exec bin/ex.bc (Add (Add (Add 1 2) (Add 3 4)) 5) = 15
参考資料
lambda関数だけのPython世界で四則演算
お察しかもしれないがラムダ計算についての話である。
最近あったPyConで気になるチュートリアルがあった：
このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、
Pythonのlambdaキーワードで作る無名関数だけで、ラムダ計算の世界をのぞいてみよう
という趣旨。
かなり面白かったので、備忘録的にメモってみる＆内容を少しだけ発展させて自然数のわり算まで実装してみる。
ルール
Pythonのlambda関数しかない世界。
なのでできるのはlambda関数の作成と呼び出しのみ。
さらにいうと単一引数のみ。
例えばこんな感じ：
X = lambda x: x Y = lambda y: y(X) Z = lambda x: lambda y: lambda z: z(x)(y)
Z関数ではcurryingにより、単一引数ながらも複数の値を入力として受け取る関数が定義できることがわかる。記述がややこしくなるのを避けるため、今後このようなcurryingされている関数のことを「ある関数がn個の引数をとる」「ある関数の第一引数、第二引数」などという表現をする。
便宜上トップレベルでは変数への代入をしているが、あくまで名前付けのためのみ許される。
言い換えると、変数を値の式ですべて書き直すことが可能である必要がある。
このルールでどうすれば計算を表現することができるか。
真偽値
まずはTRUE/FALSE：
TRUE = lambda x: lambda y: x FALSE = lambda x: lambda y: y
この世界では
- 「真」は「引数xとyを順番に受け取り、xを返す関数」
- 「偽」は「引数xとyを順番に受け取り、yを返す関数」
に対応づけられる。
そうするとNOT, AND, ORも以下のように定義できる：
NOT = lambda x: x(FALSE)(TRUE) AND = lambda x: lambda y: x(y)(x) OR = lambda x: lambda y: x(x)(y)
データ構造
複数のデータをひとつのオブジェクトとしてまとめて、単一引数に渡せるようにしたい。
LispでもおなじみのCONSセルの出番である：
CONS = lambda x: lambda y: lambda f: f(x)(y) CAR = lambda x: x(TRUE) CDR = lambda x: x(FALSE)
CONSは引数二つをとって、ある関数を返す。その関数にTRUEを与えるとCONSの第一引数、FALSEを与えると第二引数を返す。
CARとCDRはその関数を受け取ってTRUE/FALSEを与えるだけ。
数字
ここから数字と対応づけられる関数が何か、を考えていく。話を簡単にするために０からはじまる自然数のみ。
考えていく、と言ったがそれは嘘で、昔から知られているチャーチ数を使うだけ。
ZERO = lambda f: lambda x: x ONE = lambda f: lambda x: f(x) TWO = lambda f: lambda x: f(f(x))
数字はすべて二つの引数をとる関数で、「第二引数に第一引数をn回適用した結果を返す関数」を自然数nに対応させる。
任意の自然数を作れるように、「ある数より１大きい数を作る関数」SUCCを定義する：
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))
fが適用される回数が一回上がる。
SUCCを使えばたし算ができる：
ADD = lambda n: lambda m: n(SUCC)(m)
この関数は実は少し単純化できる：
ADD = lambda n: n(SUCC)
というのも、この世界だとすべてのものが関数なので、以下の等式が（ほとんどの場合）あてはまる：
lambda x: X(x)=X
（先行評価・遅延評価の関連であてはまらないケースについては後述する）
なので
lambda n: lambda m: n(SUCC)(m)=lambda n: n(SUCC)
となる。
たし算を使ってかけ算を定義：
MUL = lambda n: lambda m: n(ADD(m))(ZERO)
次にひき算を定義したいのだが、そのためには「一個前の数」を返すPRED関数が必要になる。
ここで以前定義したCONSを使う：
PRED = ( lambda n: CDR (n(lambda x: CONS(SUCC(CAR(x)))(CAR(x))) (CONS(ZERO)(ZERO))))
（横幅が足りなくなってきたので()内では複数行に分割できるというPython構文を利用している）
この定義は：
自然数n-1は
(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), ...という無限列のn番目のCONSセルのCDR
という考察がベースとなっている。ちなみにこの定義だとZEROのPREDはZEROのままであることに注意。
PREDがあればSUBは簡単：
SUB = lambda n: lambda m: m(PRED)(n)
さらに比較用の関数：
ISZERO = lambda n: n(lambda _: FALSE)(TRUE) LE = lambda n: lambda m: ISZERO(SUB(n)(m)) EQ = lambda n: lambda m: AND(LE(n)(m))(LE(m)(n)) LT = lambda n: lambda m: AND(LE(n)(m))(NOT(LE(m)(n)))
さて、残る四則演算はわり算のみとなったのだが・・・
考え方としては
nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数
を返す関数を作りたい。この「繰り返し」を実装するために再帰ができるようにしたい。
再帰
まずはルール違反な例を挙げる：
BADFACT1 = lambda n: ISZERO(n)(ONE)(MUL(n)(BADFACT1(PRED(n)))) BADFACT2 = lambda n: ISZERO(n)(ONE)(lambda _: MUL(n)(BADFACT2(PRED(n)))(_))
BADFACT1はそもそも無限再帰になってしまいうまくいかない。ISZERO(n)(m)(p)でIF分岐しているのだが、nもmもpもすべて評価してからnの値によってmかpかを選ぶ、という評価戦略になっているのが理由だ。
無限再帰を避けるため、BADFACT2では
lambda x: X(x)=X
があてはまらないケースを利用している。関数の中に入れることでXの評価を遅延させることができる。最終的にすべて評価されれば値は同じになるはずだが、これだと無限再帰を起こさない。
しかし、このようにBADFACT2の定義の中でBADFACT2という名前を利用するのはルール違反である。
この定義を「名前なしで」書こうとするとやはり無限ループが起きて、式の長さが無限になってしまう。
Y = ( lambda f: (lambda x: lambda _: f(x(x))(_)) (lambda x: lambda _: f(x(x))(_)))
Yコンビネータに関しては解説できるほど理解が進んでいないのであらかた割愛するが、一点だけ。
普通はYコンビネータといえばlambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))のような形で出てくるのだが、やはり遅延評価して無限再帰を回避するために追加でlambda _: ...というステップを追加している。
Yコンビネータを使えばFactorialやFibonacciがルール内で以下のように書ける：
FACT = (
Y
(lambda f: lambda n:
ISZERO(n)
(ONE)
(lambda _: MUL(n)(f(PRED(n)))(_))))
FIB = (
Y
(lambda f: lambda n:
LE(n)(TWO)
(ONE)
(lambda _: ADD
(f(PRED(n)))
(f(PRED(PRED(n))))(_))))
わり算
これでピースは全て揃った。あとは書くだけ：
DIV = ( lambda n: lambda m: Y (lambda f: lambda x: LT(CAR(x))(m) (CDR(x)) (lambda _: f(CONS(SUB(CAR(x))(m))(SUCC(CDR(x))))(_))) (CONS(n)(ZERO)))
考え方としては前述の通り
nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数
を返す関数。初期値がnとZEROのCONSセル(p, k)に対して再帰的に(p-m, k+1)に変えていき 、pがm未満になった時点でkを返す。
普通のPythonで書くならこんなロジック：
def divide(n, m): def f(p, k): return k if p < m else f(p-m, k+1) return f(n, 0)
使ってみる
まずは他にいくつか数字を定義しておく：
THREE = ADD(ONE)(TWO) FIVE = ADD(TWO)(THREE) TEN = ADD(FIVE)(FIVE) HUNDRED = MUL(TEN)(TEN)
この世界の数字に対応するPythonの数字をプリントする関数を定義：
def show(n): print(n(lambda x: x+1)(0))
この関数はラムダ計算世界の結果を、我々が理解できるように出力するためだけに使う（演算には使われていない）。のでルール外の存在。
この関数を使ってFACT, FIB, DIVを使った計算結果を出力してみる：
>>> show(FACT(FIVE)) 120 >>> show(FIB(TEN)) 55 >>> show(DIV(HUNDRED)(THREE)) 33
成功。
AtCoder Beginners SelectionをOCamlで（後編）
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
今回は最後の２問、白昼夢 / DaydreamとTravellingの解法とOCamlを使った所感。
ABC049C - 白昼夢 / Daydream
ある文字列が、"dream", "erase", "dreamer", "eraser"の四語のどれかを繰り返すことで作られているかを判定する
open Batteries let s = read_line () |> String.explode |> List.rev let rec f = function | [] -> true | 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | _ -> false let ans = if f s then "YES" else "NO" let () = print_endline ans
"dream"と"dreamer"、"erase" "eraser"と先頭から読んでいくと候補が重複してしまう。バックトラックするようなロジックも考えられるが、この四語だったら一番楽なのは後ろからパースすることだろう（後ろから見ると重複する候補はないため）。
OCamlのリストと文字がパターンマッチ可能なことを利用した再帰関数でパースできる。
ABC086C - Traveling
格子上の点を特定のスケジュールで移動できるかどうかを判定する。
open Batteries let parse_triplet s = Scanf.sscanf s "%d %d %d" (fun a b c -> (a,b,c)) let diff ((_,_,_), (a,b,c)) (x,y,z) = ((x-a,y-b,z-c), (x,y,z)) let pred (a, b, c) = let d = abs b + abs c in a >= d && a mod 2 = d mod 2 let n = read_int () let x = Enum.init n (fun _ -> read_line ()) |> Enum.map parse_triplet |> Enum.scanl diff ((0,0,0), (0,0,0)) |> Enum.map fst |> Enum.for_all pred let ans = if x then "Yes" else "No" let () = print_endline ans
スケジュールは時間順に与えられるので、隣接するスケジュールの差だけを調べていけばいい。
スケジュールの差が可能かどうかの判定は以下の二点：
- 移動量は時間内に収まるか
- 移動量と時間の偶奇が一致するか（余った時間は２つずつ無駄に消費することが可能なため）
Enum.scanlはfoldに似ているけど、foldでいうところの中間結果をすべて要素として持つ遅延リスト。
Enum.scanl f x (a1; a2; a3)は(x; f x a1; f (f x a1) a2; f (f (f x a1) a2) a3)となる（ここでは(x;y;z)はx``y``zを要素に持つ遅延リストだとする）。
これを使って「差額の遅延リスト」を作成して、すべてが上記の二点を満たしているかをEnum.for_allで判定している。
OCamlをAtCoderで使ってみて
OCamlは去年の１０月くらいからかれこれ四ヶ月ほど（業務外で・・・）使っていて少しは慣れてきたと思うのだが、主に言語実装系のことばかりしていたので競技プログラミングは勝手がけっこう違った。言語処理系の実装だとASTなどの処理のために「再帰関数でパターンマッチ」が多くなるのだが、AtCoder Beginners Selectionではあまり木構造をどうこうすることもなく、直線的かつフラットにデータ変換のロジックを書いていくことが多かった。
OCamlは|>演算子やEnumの各関数などで十分そのような書き方もできる言語だとわかったのは嬉しい。
個人的にはOCamlの命令型でも記述できるところはすごく便利だと思っているのだが、振り返ると一度もref、Array、Hashtblなどの破壊的代入が可能なデータやforループなどの命令的な構文などを使う必要がなかった。Dynamic Programmingなどでは絶対必要になってくると思うが、Batteriesのモジュールや関数、とくにEnum関連を使いこなせば関数型プログラミングのスタイルだけでもかなりの処理を（しかもそれなりに宣言的に）記述できることも実感できた。個人的にはこれはPythonなどでも感じていたことだが・・・
Pythonとは実行速度が比較にならないほど早い、という点もAtCoder向きだ。
比較のためにOtoshidamaをPythonとOCamlで同じ（意図的にアルゴリズムの良さよりも記述の明快さを重視した）ロジックで書いてみた：
Pythonの内包表記的なgenerator expressionは記法としてはやはりすごく好きだ・・・ がほぼ完全に一致するロジックのコードで、Pythonが719 ms、OCamlが58 msで十倍以上の差がある。コードが煩雑になるような定数倍最適化を行わなくてはならない、というケースが減りそうでとても魅力的。
というわけでこれからもちょくちょくOCamlでAtCoderの過去問を解いていこうと思う。ArrayやHashtblなどを使ってDPやUnion Find Treeなどの問題を解いていって、それらの記法にも馴染んできた時点で実際のコンテストにもまた参加したい。まずは最近開催されたEDPCの問題かな・・・
AtCoder Beginners SelectionをOCamlで（中編）
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
（この記事はSome Sums, Card Game for Two, Kagamimochi, Otoshidamaの４問について）
ABC083B - Some Sums
0~Nまでの数で、各桁の合計がa以上b以下になるものを合計する。
open Batteries let add_digits x = string_of_int x |> String.explode |> List.map (fun x -> int_of_char x - 48) |> List.fold_left (+) 0 let n, a, b = Scanf.scanf "%d %d %d" (fun n a b -> n, a, b) let ans = Enum.range 1 ~until:n |> Enum.filter (fun x -> let y = add_digits x in a <= y && y <= b) |> Enum.reduce (+) |> string_of_int let () = print_endline ans
問題をそのままコード化できたように思うがどうだろうか。
ABC088B - Card Game for Two
交互に数字の書いてあるカードをとっていくゲームで、お互いに最善を尽くした場合の点差を計算する。
open Batteries let rec diff_two n = function | [] -> n | [x] -> n + x | x :: y :: zs -> diff_two (n + x - y) zs;; let _ = read_line () let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> diff_two 0 |> string_of_int let () = print_endline ans
降順にソートされた数字の奇数番と偶数番の和の差。
List.sort (flip compare)で逆順ソートになるのは思いつけてよかった。(fun a b -> - (compare a b)とか書くのかなー、いやだなーと思っていたので・・・
逆に再帰でdiff_twoを書いているのは少し不満がある。なんらかの高階関数を組み合わせて表現できないものか・・・
今ふとこんな解も思いついたが
let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> List.fold_left (fun (n, m) x -> (n + (m * x), - m)) (0, 1) |> fst |> string_of_int
これはちょっと問題固有の部分に引きずられすぎているだろうか？あまりテクニックとして汎用性がなさそうにも見える。
ABC085B - Kagami Mochi
いくつかの直径の餅を「下にある餅は必ず上にある餅よりも直径が大きい」という制約でいくつ積み重ねることができるか。
open Batteries module S = Set.Make(Int) let n = read_int () let ans = List.init n (fun _ -> read_int ()) |> S.of_list |> S.cardinal |> string_of_int let () = print_endline ans
ユニークな直径の数を求めればいいのでSetを使う。OCamlだとSetはFunctor（モジュールをうけとりモジュールを返す「関数」）なので、Batteriesで定義されているIntモジュールを渡すことで整数を要素にとる集合を表すことができる。
あとはList.init n (fun _ -> read_int ())でn行に渡る整数の入力値をリスト化し、S.of_listで集合化し、S.cardinalで要素数を数えてstring_of_intで文字列化する。
ABC085C - Otoshidama
10000円札、5000円札、1000円札を合計N枚使ってY円を作ることができるか。
open Batteries open Enum.Infix let n, y = Scanf.scanf "%d %d" (fun n y -> (n, y)) let f i = let z = (y - 10000*i - 1000*(n-i)) / 4000 in (i, z, n - i - z) let p (a, b, c) = y = a * 10000 + b * 5000 + c * 1000 && 0 <= a && 0 <= b && 0 <= c let xs = Enum.map f (0--(y / 10000)) let ans = let a, b, c = try Enum.find p xs with Not_found -> (-1, -1, -1) in Printf.sprintf "%d %d %d" a b c let () = print_endline ans
「5000円札、1000円札を合計N枚使ってY円を作る」というのはつるかめ算的なサムシングなので、それをまずf関数で表す。
ただし、5000円札A枚、1000円札B枚のAとBが整数でなかったり片方が負数だったりする場合を排除しないといけないので、そのためのp述語を定義する。
あとはEnum.Infixに定義された--演算子でrangeを手軽に表したものにfでmapし、`try＋Enum.find pで合致する要素を探し、見つからなかった場合はNot_foundをキャッチして(-1, -1, -1)を返している。Enum.Infixは継続して使うか少し悩むところだ・・・ （関数でも同じことができるのと、ぱっと見で理解しやすいか微妙な気がするため）
あと今回も入力が一行のみなのでScanf.scanfを使っている。
やはり長くなってきたので後編に続く。
