- 追加された行はこの色です。
- 削除された行はこの色です。
*Chapter 1 The core language [#k53c59c2]
本章は Objective Caml のチュートリアルです。手続き型言語 (Pascal や C) に詳しいことを前提としますが、特に関数型言語に詳しい必要はありません。 3 章ではオブジェクト指向の特徴、 2 章ではモジュールシステムについて解説します。
**1.1 Basics [#obbe890d]
ここでは、OCaml の対話式システムを使用して Caml の概要を説明します。Unix シェルでは ocaml で起動します。Windows では OCamlwin.exe で起動します。ユーザの入力には行頭に # をつけて、システムの返答には行頭に # をつけずに表記します。
対話式システムでは、ユーザの入力文が ;; で区切られます。システムはその入力文をその場でコンパイルし、実行し、評価の結果を表示します。文は単純な式か、識別子の let 定義式 (値か関数) です。
#1+2*3;;
- : int = 7
#let pi = 4.0 *. atan 1.0;;
val pi : float = 3.14159265359
#let square x = x *. x;;
val square : float -> float = <fun>
#square(sin pi) +. square(cos pi);;
- : float = 1.
Caml システムはそれぞれの文に対して値と型の両方を計算するので、関数の引数であっても、明示的な型の宣言は必要ありません。システムが引数の扱われ方からその引数の型を推論します。整数 (integer) と浮動小数 (float) は異なる型なので、オペレータも異なることに注意してください。+ と * は整数同士を計算して整数を返し、+. と *. は浮動小数同士を計算して浮動小数を返します。
#1.0 * 2;;
This expression has type float but is here used with type int
再帰的な関数は let rec で定義します。
#let rec fib n =
if n < 2 then 1 else fib(n-1) + fib(n-2);;
val fib : int -> int = <fun>
#fib 10;;
- : int = 891.2 Data types
- : int = 89
**1.2 Data types [#i3ecc9fe]
整数と浮動小数以外に、Caml には boolean 、文字 (character) 、文字列 (character strings) の基本型があります。
#(1 < 2) = false;;
- : bool = false
#'a';;
- : char = 'a'
#"Hello world";;
- : string = "Hello world"
あらかじめ定義されているデータ構造として、組 (tuple) 、配列 (array) 、リスト (list) があります。ユーザが自分でデータ構造を定義することも出来ます (後述) 。リストは要素をセミコロンで区切りバケットで囲んだ形で書くか、または、リストの先頭に要素を付け加えたリストを返す演算子 :: で空リスト [] (nil と発音します) に要素を加える形で書くことが出来ます。
#let l = ["is"; "a"; "tale"; "told"; "etc."];;
val l : string list = ["is"; "a"; "tale"; "told"; "etc."]
#"Life" :: l;;
- : string list = ["Life"; "is"; "a"; "tale"; "told"; "etc."]
リストは明示的にメモリを確保、開放する必要はありません。他のすべてのデータ構造についても同じです。Caml が自動的に全てのメモリ管理を行います。同様に明示的にポインタを扱う必要もありません。Caml のコンパイラが必要に応じて暗黙のうちにポインタを導入します。
リストの中を見たり解体したりするためにはパターンマッチングを用います。他の大半のデータ構造についても同じです。List patterns have the exact same shape as list expressions, with identifier representing unspecified parts of the list. 例としてリストの挿入ソートを示します。
#let rec sort lst =
match lst with
[] -> []
| head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
[] -> [elt]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
;;
val sort : 'a list -> 'a list = <fun>
val insert : 'a -> 'a list -> 'a list = <fun>
#sort l;;
- : string list = ["a"; "etc."; "is"; "tale"; "told"]
sort の型は 'a list -> 'a list と推論されます。つまり sort はどんな型のリストでも引数にとれ、同じ型のリストを返します。'a は 型変数 (type variable) で、与えられた引数の型を表します。sort が全ての型のリストを受け取れるのは、Caml において比較演算子 (= 、<= など) が同じ型の二つの変数をとり比較を行う、型多相 (polymorphic) の演算子であるためです。
#sort [6;2;5;3];;
- : int list = [2; 3; 5; 6]
#sort [3.14; 2.718];;
- : float list = [2.718; 3.14]
上の sort 関数は入力されたリストを書き換えません。入力されたリストと同じ要素をソート順に並べた新しいリストを作って返します。Caml において、一度リストの中に組み込まれた要素を書き換える方法はありません。リストは 不変 (immutable) のデータ構造です。Caml の大半のデータ構造は不変ですが、いくつかのデータ構造 (有名なところでは配列) は 可変 (mutable) で、いつでも置き換えが可能です。
**1.3 Functions as values [#x9a479c6]
Caml は関数型言語です。当然数学的な意味の関数としても使えますし、他のデータと同じように自由に扱うことも出来ます。例として deriv 関数を示します。この関数は浮動小数の関数を引数にとり、導関数の近似を返します。
#let deriv f dx = function x -> (f(x +. dx) -. f(x)) /. dx;;
val deriv : (float -> float) -> float -> float -> float = <fun>
#let sin' = deriv sin 1e-6;;
val sin' : float -> float = <fun>
#sin' pi;;
- : float = -1.00000000014
関数の合成も定義出来ます。
#let compose f g = function x -> f(g(x));;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
#let cos2 = compose square cos;;
val cos2 : float -> float = <fun>
関数の引数として渡された関数は ``functionals'' や ``高階関数 (higher-order functions)'' と呼ばれます。高階関数は特にイテレータや、各データ構造に共通の作業を行うのに使われます。たとえば、標準 Caml ライブラリに List.map という関数がありますが、この関数は引数に与えられた関数を、すべてのリストの要素に適用し、その結果のリストを返します。
#List.map (function n -> n * 2 + 1) [0;1;2;3;4];;
- : int list = [1; 3; 5; 7; 9]
この高階関数などのように、リストや配列を処理する高階関数は使用頻度が高いのですでに定義されていますが、内部構造を知っていないと出来ないというわけではありません。以下のように簡単に定義することが出来ます。
#let rec map f l =
match l with
[] -> []
| hd :: tl -> f hd :: map f tl;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>1.4 Records and variants
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
**1.4 Records and variants [#nd89a729]
ユーザ定義データ構造にはレコード (record) とバリアント (variant) があり、ともに type 宣言で定義できます。比を表すレコードを定義してみます。
#type ratio = {num: int; denum: int};;
type ratio = { num : int; denum : int; }
#let add_ratio r1 r2 =
{num = r1.num * r2.denum + r2.num * r1.denum;
denum = r1.denum * r2.denum};;
val add_ratio : ratio -> ratio -> ratio = <fun>
#add_ratio {num=1; denum=3} {num=2; denum=5};;
- : ratio = {num = 11; denum = 15}
バリアント型の宣言は、その型の値が取りうる形を全て並べ立てます。それぞれのケースはコンストラクタと言われる名前で識別されます。コンストラクタは、そのバリアント型の値を構成するためと、パターンマッチングのために使われます。コンストラクタの名前は変数名と区別するため大文字で書きます (変数名の頭文字は小文字です) 。以下に (整数と浮動小数の) 数値を混合するバリアント型を示します。
#type number = Int of int | Float of float | Error;;
type number = Int of int | Float of float | Error
この宣言は number 型が、整数か浮動小数か (0 除算などの) 無効な演算を表す定数 Error の 3 つしか取りえないことを意味します。
バリアント型の特殊な場合として、すべてが定数であるものがあります。
#type sign = Positive | Negative;;
type sign = Positive | Negative
#let sign_int n = if n >= 0 then Positive else Negative;;
val sign_int : int -> sign = <fun>
number 型の算術演算を定義するには、2 つの number 型値に対してパターンマッチングを用います。
#let add_num n1 n2 =
match (n1, n2) with
(Int i1, Int i2) ->
(* Check for overflow of integer addition *)
if sign_int i1 = sign_int i2 && sign_int(i1 + i2) <> sign_int i1
then Float(float i1 +. float i2)
else Int(i1 + i2)
| (Int i1, Float f2) -> Float(float i1 +. f2)
| (Float f1, Int i2) -> Float(f1 +. float i2)
| (Float f1, Float f2) -> Float(f1 +. f2)
| (Error, _) -> Error
| (_, Error) -> Error;;
val add_num : number -> number -> number = <fun>
#add_num (Int 123) (Float 3.14159);;
- : number = Float 126.14159
バリアント型の主な用途は再帰的なデータ構造の記述です。2 分木の型は以下のようになります。
#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
これは、'a (型は自由) 型の値を持つ 2 分木は、空 (Empty) か、1 つの値と 2 つの副木を持つ節 (Node) で構成されるという意味です。副木もまた 'a btree 型です。
2 分木の処理は、データ構造の型定義に従うような再帰関数で自然に表現出来ます。例として、ソートされた 2 分木に探索 (lookup) と挿入 (insert) を行う関数を示します (要素は左から右に増えます) 。
#let rec member x btree =
match btree with
Empty -> false
| Node(y, left, right) ->
if x = y then true else
if x < y then member x left else member x right;;
val member : 'a -> 'a btree -> bool = <fun>
#let rec insert x btree =
match btree with
Empty -> Node(x, Empty, Empty)
| Node(y, left, right) ->
if x <= y then Node(y, insert x left, right)
else Node(y, left, insert x right);;
val insert : 'a -> 'a btree -> 'a btree = <fun>1.5 Imperative features
val insert : 'a -> 'a btree -> 'a btree = <fun>
**1.5 Imperative features [#a65b5cb6]
今まではすべての例を純粋な関数型スタイルで書いてきましたが、Caml には手続き型のスタイルも備わっています。配列などの可変データ構造や、while ループや for ループです。配列は [| と |] のバケットでリストのように記述するか、Array.create でメモリ割り当てと初期化を行い、後で代入によって値を埋めることが出来ます。例として、2 つのベクトルを加算する関数を示します (ベクトルは浮動小数の配列で表されます) 。
#let add_vect v1 v2 =
let len = min (Array.length v1) (Array.length v2) in
let res = Array.create len 0.0 in
for i = 0 to len - 1 do
res.(i) <- v1.(i) +. v2.(i)
done;
res;;
val add_vect : float array -> float array -> float array = <fun>
#add_vect [| 1.0; 2.0 |] [| 3.0; 4.0 |];;
- : float array = [|4.; 6.|]
レコード型の定義に mutable が宣言されているフィールドならば、そのフィールドも代入によって上書きすることが出来ます。
#type mutable_point = { mutable x: float; mutable y: float };;
type mutable_point = { mutable x : float; mutable y : float; }
#let translate p dx dy =
p.x <- p.x +. dx; p.y <- p.y +. dy;;
val translate : mutable_point -> float -> float -> unit = <fun>
#let mypoint = { x = 0.0; y = 0.0 };;
val mypoint : mutable_point = {x = 0.; y = 0.}
#translate mypoint 1.0 2.0;;
- : unit = ()
#mypoint;;
- : mutable_point = {x = 1.; y = 2.}
Caml には変数という概念が組み込まれていません。ここで言う変数とは代入によって現在の値に上書きできる識別子のことです (let の割り当ては代入ではなく、新しいスコープを作り新しい識別子として割り当てます) 。しかし標準ライブラリに参照 (reference) があります。これは mutable のセル (または 1 要素の配列) で、オペレータ ! で参照が現在保持している内容を取り出し、:= で内容を上書き代入します。let で割り当てられた参照で、擬似的に変数を実現できます。例として、配列の置き換え挿入ソートを示します。
#let insertion_sort a =
for i = 1 to Array.length a - 1 do
let val_i = a.(i) in
let j = ref i in
while !j > 0 && val_i < a.(!j - 1) do
a.(!j) <- a.(!j - 1);
j := !j - 1
done;
a.(!j) <- val_i
done;;
val insertion_sort : 'a array -> unit = <fun>
次の呼び出しがあるまで現在の状態を保持しなければならない関数を定義するときも、参照が使えます。例として、最後返した結果を参照に保存する疑似乱数生成関数を示します。
#let current_rand = ref 0;;
val current_rand : int ref = {contents = 0}
#let random () =
current_rand := !current_rand * 25713 + 1345;
!current_rand;;
val random : unit -> int = <fun>
再度説明しますが、参照は内部的に実現されているわけではありません。以下のように 1 つのフィールドからなるレコードで実装されています。
#type 'a ref = { mutable contents: 'a };;
type 'a ref = { mutable contents : 'a; }
#let (!) r = r.contents;;
val ( ! ) : 'a ref -> 'a = <fun>
#let (:=) r newval = r.contents <- newval;;
val ( := ) : 'a ref -> 'a -> unit = <fun>
型多相な関数を、型多相のままデータ構造に保持しなくてはならない場合もあると思います。通常のユーザ定義型宣言では不可能です。型多相はグローバルレベルのみで実現可能なためです。しかしレコードのフィールドに明示的に型多相を指定することが出来ます。
#type idref = { mutable id: 'a. 'a -> 'a };;
type idref = { mutable id : 'a. 'a -> 'a; }
#let r = {id = fun x -> x};;
val r : idref = {id = <fun>}
#let g s = (s.id 1, s.id true);;
val g : idref -> int * bool = <fun>
#r.id <- (fun x -> print_string "called id\n"; x);;
- : unit = ()
#g r;;
called id
called id
- : int * bool = (1, true)1.6 Exceptions
- : int * bool = (1, true)
**1.6 Exceptions [#v16830f1]
Caml では例外状況を伝え、受け取るための例外機構が提供されています。Exceptions can also be used as a general-purpose non-local control structure. 例外は exception で宣言され、raise で発生させることが出来ます。例として、リストの先頭を返す関数を示します。この関数は空リストを渡されたとき例外を発生します。
#exception Empty_list;;
exception Empty_list
#let head l =
match l with
[] -> raise Empty_list
| hd :: tl -> hd;;
val head : 'a list -> 'a = <fun>
#head [1;2];;
- : int = 1
#head [];;
Exception: Empty_list.
標準ライブラリの関数は正常に処理を完了できなかったとき例外を発生します。たとえば List.assoc は、(key, data) というペアのリストから、与えられた key に該当する data を返す関数ですが、key が list から見つからなかったとき、定義済みの例外 Not_found を発生します。
#List.assoc 1 [(0, "zero"); (1, "one")];;
- : string = "one"
#List.assoc 2 [(0, "zero"); (1, "one")];;
Exception: Not_found.
例外は try...with でトラップすることが出来ます。
#let name_of_binary_digit digit =
try
List.assoc digit [0, "zero"; 1, "one"]
with Not_found ->
"not a binary digit";;
val name_of_binary_digit : int -> string = <fun>
#name_of_binary_digit 0;;
- : string = "zero"
#name_of_binary_digit (-1);;
- : string = "not a binary digit"
with の部分は、例外の値をパターンマッチングすることが出来ます。よって 1 つの try...with で複数の例外をトラップすることが出来ます。さらに、すべての例外をトラップしたのち終了処理を行い、再度その例外を発生させることで終了処理が可能です。
#let temporarily_set_reference ref newval funct =
let oldval = !ref in
try
ref := newval;
let res = funct () in
ref := oldval;
res
with x ->
ref := oldval;
raise x;;
val temporarily_set_reference : 'a ref -> 'a -> (unit -> 'b) -> 'b = <fun>1.7 Symbolic processing of expressions
val temporarily_set_reference : 'a ref -> 'a -> (unit -> 'b) -> 'b = <fun>
**1.7 Symbolic processing of expressions [#zc54ea13]
このチュートリアルの最後に、Caml の記号処理の使い方を代表するようなもっと完全な例として、変数を含む算術式の処理を示します。以下のようなバリアント型で処理する式を構成します。
#type expression =
Const of float
| Var of string
| Sum of expression * expression (* e1 + e2 *)
| Diff of expression * expression (* e1 - e2 *)
| Prod of expression * expression (* e1 * e2 *)
| Quot of expression * expression (* e1 / e2 *)
;;
type expression =
Const of float
| Var of string
| Sum of expression * expression
| Diff of expression * expression
| Prod of expression * expression
| Quot of expression * expression
変数名に値を割り当てた環境から、計算式を評価する関数を定義します。単純に言えば、環境とは連想リストで表されます。
#exception Unbound_variable of string;;
exception Unbound_variable of string
#let rec eval env exp =
match exp with
Const c -> c
| Var v ->
(try List.assoc v env with Not_found -> raise(Unbound_variable v))
| Sum(f, g) -> eval env f +. eval env g
| Diff(f, g) -> eval env f -. eval env g
| Prod(f, g) -> eval env f *. eval env g
| Quot(f, g) -> eval env f /. eval env g;;
val eval : (string * float) list -> expression -> float = <fun>
#eval [("x", 1.0); ("y", 3.14)] (Prod(Sum(Var "x", Const 2.0), Var "y"));;
- : float = 9.42
#exception Unbound_variable of string;;
exception Unbound_variable of string
#let rec eval env exp =
match exp with
Const c -> c
| Var v ->
(try List.assoc v env with Not_found -> raise(Unbound_variable v))
| Sum(f, g) -> eval env f +. eval env g
| Diff(f, g) -> eval env f -. eval env g
| Prod(f, g) -> eval env f *. eval env g
| Quot(f, g) -> eval env f /. eval env g;;
val eval : (string * float) list -> expression -> float = <fun>
#eval [("x", 1.0); ("y", 3.14)] (Prod(Sum(Var "x", Const 2.0), Var "y"));;
- : float = 9.42
本当の記号処理として、与えられた式の与えられた変数 dv での導関数を定義します。
#let rec deriv exp dv =
match exp with
Const c -> Const 0.0
| Var v -> if v = dv then Const 1.0 else Const 0.0
| Sum(f, g) -> Sum(deriv f dv, deriv g dv)
| Diff(f, g) -> Diff(deriv f dv, deriv g dv)
| Prod(f, g) -> Sum(Prod(f, deriv g dv), Prod(deriv f dv, g))
| Quot(f, g) -> Quot(Diff(Prod(deriv f dv, g), Prod(f, deriv g dv)),
Prod(g, g))
;;
val deriv : expression -> string -> expression = <fun>
#deriv (Quot(Const 1.0, Var "x")) "x";;
- : expression =
Quot (Diff (Prod (Const 0., Var "x"), Prod (Const 1., Const 1.)),
Prod (Var "x", Var "x"))1.8 Pretty-printing and parsing
#let rec deriv exp dv =
match exp with
Const c -> Const 0.0
| Var v -> if v = dv then Const 1.0 else Const 0.0
| Sum(f, g) -> Sum(deriv f dv, deriv g dv)
| Diff(f, g) -> Diff(deriv f dv, deriv g dv)
| Prod(f, g) -> Sum(Prod(f, deriv g dv), Prod(deriv f dv, g))
| Quot(f, g) -> Quot(Diff(Prod(deriv f dv, g), Prod(f, deriv g dv)),
Prod(g, g))
;;
val deriv : expression -> string -> expression = <fun>
#deriv (Quot(Const 1.0, Var "x")) "x";;
- : expression =
Quot (Diff (Prod (Const 0., Var "x"), Prod (Const 1., Const 1.)),
Prod (Var "x", Var "x"))
**1.8 Pretty-printing and parsing [#na8dcc74]
上の例で示された例では、少し式が大きくなるだけで、式の内部的表現 (抽象文法 (abstract syntax) とも言う) を読み書きするのが困難になります。(2*x+1 のような) よく見る代数表記を 具体文法 (concrete syntax)と言いますが、抽象文法から具体文法を得るプリンタや、その逆のパーザが必要です。
プリンタの関数が不要なカッコを表記しないで済むように、演算子の優先順位 (つまり * が + より強いということ) を導入します。この結果プリンタの関数は、現在の演算子の優先度を保持しておき、次の演算子の優先度が現在の優先度より低い場合のみカッコを表示します。
#let print_expr exp =
(* Local function definitions *)
let open_paren prec op_prec =
if prec > op_prec then print_string "(" in
let close_paren prec op_prec =
if prec > op_prec then print_string ")" in
let rec print prec exp = (* prec is the current precedence *)
match exp with
Const c -> print_float c
| Var v -> print_string v
| Sum(f, g) ->
open_paren prec 0;
print 0 f; print_string " + "; print 0 g;
close_paren prec 0
| Diff(f, g) ->
open_paren prec 0;
print 0 f; print_string " - "; print 1 g;
close_paren prec 0
| Prod(f, g) ->
open_paren prec 2;
print 2 f; print_string " * "; print 2 g;
close_paren prec 2
| Quot(f, g) ->
open_paren prec 2;
print 2 f; print_string " / "; print 3 g;
close_paren prec 2
in print 0 exp;;
val print_expr : expression -> unit = <fun>
#let print_expr exp =
(* Local function definitions *)
let open_paren prec op_prec =
if prec > op_prec then print_string "(" in
let close_paren prec op_prec =
if prec > op_prec then print_string ")" in
let rec print prec exp = (* prec is the current precedence *)
match exp with
Const c -> print_float c
| Var v -> print_string v
| Sum(f, g) ->
open_paren prec 0;
print 0 f; print_string " + "; print 0 g;
close_paren prec 0
| Diff(f, g) ->
open_paren prec 0;
print 0 f; print_string " - "; print 1 g;
close_paren prec 0
| Prod(f, g) ->
open_paren prec 2;
print 2 f; print_string " * "; print 2 g;
close_paren prec 2
| Quot(f, g) ->
open_paren prec 2;
print 2 f; print_string " / "; print 3 g;
close_paren prec 2
in print 0 exp;;
val print_expr : expression -> unit = <fun>
#let e = Sum(Prod(Const 2.0, Var "x"), Const 1.0);;
val e : expression = Sum (Prod (Const 2., Var "x"), Const 1.)
#let e = Sum(Prod(Const 2.0, Var "x"), Const 1.0);;
val e : expression = Sum (Prod (Const 2., Var "x"), Const 1.)
#print_expr e; print_newline();;
2. * x + 1.
- : unit = ()
#print_expr (deriv e "x"); print_newline();;
2. * 1. + 0. * x + 0.
- : unit = ()
#print_expr e; print_newline();;
2. * x + 1.
- : unit = ()
#print_expr (deriv e "x"); print_newline();;
2. * 1. + 0. * x + 0.
- : unit = ()
(具体文法から抽象文法に変換する) パージングは大抵プリントより面倒です。Caml にはパーザを書くためのツールがあります。字句解析器生成系 Lex と構文解析生成系 Yacc の OCaml 版があります (詳細は 12 章を見てください) 。Yacc は LALR(1) 文法をプッシュダウンオートマトンで扱います。また、文字やトークンのストリームの型がすでに定義されていて、そのストリームをパターンマッチングすることができます。これを使うことで容易に LL(1) 文法の再帰下降パーザが書けます。ocamllex と ocamlyacc を使う例は 12 章にありますので、ここではストリームパーザを使ってみます。このストリームパーザの補助機構は Camlp4 プリプロセッサにあります。Camlp4 プリプロセッサは、対話式システムでは #load 指示語で以下のようにロードできます
##load "camlp4o.cma";;
Camlp4 Parsing version 3.05 (2002-07-22)
##load "camlp4o.cma";;
Camlp4 Parsing version 3.05 (2002-07-22)
#open Genlex;;
let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"];;
val lexer : char Stream.t -> Genlex.token Stream.t = <fun>
#open Genlex;;
let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"];;
val lexer : char Stream.t -> Genlex.token Stream.t = <fun>
(与えられた文字列をトークンのストリームに変換する) 字句解析では、標準ライブラリで提供される Genlex モジュールの一般字句解析器 (``generic'' lexer) を使用します。make_lexer 関数は、キーワードのリストを受け取り、文字のストリームを受け取り字句解析する関数を返します。識別子、キーワード、リテラル (整数、浮動小数、文字、文字列) をトークンとします。空白やコメントは無視されます。
#let token_stream = lexer(Stream.of_string "1.0 +x");;
val token_stream : Genlex.token Stream.t = <abstr>
#Stream.next token_stream;;
- : Genlex.token = Float 1.
#Stream.next token_stream;;
- : Genlex.token = Kwd "+"
#Stream.next token_stream;;
- : Genlex.token = Ident "x"
#let token_stream = lexer(Stream.of_string "1.0 +x");;
val token_stream : Genlex.token Stream.t = <abstr>
#Stream.next token_stream;;
- : Genlex.token = Float 1.
#Stream.next token_stream;;
- : Genlex.token = Kwd "+"
#Stream.next token_stream;;
- : Genlex.token = Ident "x"
パージング自体はトークンのストリームをパターンマッチングすることで行います。通常再帰下降パーザは、オペレータの優先順位や関連性を反映するため、いくつか内部パージング関数を持ちます。ストリームのパターンマッチングは、副コンポーネントのパターン内部でパージング関数を再帰的に呼ぶことが出来、通常のデータ構造でのパターンマッチングより強力です。 7 章に詳細があります。
対話式システムのトップレベルでストリームパーザを使用するためには camlp4 プリプロセッサをロードする必要があります。
##load"camlp4o.cma";;
Camlp4 Parsing version 3.05 (2002-07-22)
##load"camlp4o.cma";;
Camlp4 Parsing version 3.05 (2002-07-22)
それからパーザを定義します。
#let rec parse_expr = parser
[< e1 = parse_mult; e = parse_more_adds e1 >] -> e
and parse_more_adds e1 = parser
[< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
| [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
| [< >] -> e1
and parse_mult = parser
[< e1 = parse_simple; e = parse_more_mults e1 >] -> e
and parse_more_mults e1 = parser
[< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
| [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
| [< >] -> e1
and parse_simple = parser
[< 'Ident s >] -> Var s
| [< 'Int i >] -> Const(float i)
| [< 'Float f >] -> Const f
| [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e;;
val parse_expr : Genlex.token Stream.t -> expression = <fun>
val parse_more_adds : expression -> Genlex.token Stream.t -> expression =
<fun>
val parse_mult : Genlex.token Stream.t -> expression = <fun>
val parse_more_mults : expression -> Genlex.token Stream.t -> expression =
<fun>
val parse_simple : Genlex.token Stream.t -> expression = <fun>
#let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e;;
val parse_expression : Genlex.token Stream.t -> expression = <fun>
#let rec parse_expr = parser
[< e1 = parse_mult; e = parse_more_adds e1 >] -> e
and parse_more_adds e1 = parser
[< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
| [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
| [< >] -> e1
and parse_mult = parser
[< e1 = parse_simple; e = parse_more_mults e1 >] -> e
and parse_more_mults e1 = parser
[< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
| [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
| [< >] -> e1
and parse_simple = parser
[< 'Ident s >] -> Var s
| [< 'Int i >] -> Const(float i)
| [< 'Float f >] -> Const f
| [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e;;
val parse_expr : Genlex.token Stream.t -> expression = <fun>
val parse_more_adds : expression -> Genlex.token Stream.t -> expression =
<fun>
val parse_mult : Genlex.token Stream.t -> expression = <fun>
val parse_more_mults : expression -> Genlex.token Stream.t -> expression =
<fun>
val parse_simple : Genlex.token Stream.t -> expression = <fun>
#let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e;;
val parse_expression : Genlex.token Stream.t -> expression = <fun>
字句解析器と構文解析器を作成し、文字列から計算式を読む関数を得ることが出来ました。
#let read_expression s = parse_expression(lexer(Stream.of_string s));;
val read_expression : string -> expression = <fun>
#let read_expression s = parse_expression(lexer(Stream.of_string s));;
val read_expression : string -> expression = <fun>
#read_expression "2*(x+y)";;
- : expression = Prod (Const 2., Sum (Var "x", Var "y"))
#read_expression "2*(x+y)";;
- : expression = Prod (Const 2., Sum (Var "x", Var "y"))
ちょっとしたクイズです。なぜ以下の 2 つの例は結果が異なるのでしょう。
#read_expression "x - 1";;
- : expression = Diff (Var "x", Const 1.)
#read_expression "x-1";;
Exception: Stream.Error "".
#read_expression "x - 1";;
- : expression = Diff (Var "x", Const 1.)
#read_expression "x-1";;
Exception: Stream.Error "".
答えです。Genlex の字句解析器は負の整数を 1 つの整数として判断します。x-1 は Ident "x" というトークンの後に Int(-1) というトークンがあると見なされたわけです。この文はどのパージングのルールにも該当しません。x - 1 は、2 つ目の空白の影響で Ident "x" 、Kwd "-" 、Int(1) と見なされます。
1.9 Standalone Caml programs
**1.9 Standalone Caml programs [#lceb9c2e]
今までは対話式システムですべての例を実行してきました。Caml のコードは、バッチコンパイラ ocamlc または ocamlopt を使用することで分割コンパイルも出来、非対話的に実行することも出来ます。ソースコードのファイルは拡張子を .ml としてください。ソースコードは文の列から成り、実行時にソースコードの上から順に評価していきます。対話式と異なり、型や値が自動的に表示されることはありません。何か出力するときはプログラムから明示的にプリントの関数を呼んでください。以下にフィボナッチ数列を表示するスタンドアロンのプログラム例を示します。
(* File fib.ml *)
let rec fib n =
if n < 2 then 1 else fib(n-1) + fib(n-2);;
let main () =
let arg = int_of_string Sys.argv.(1) in
print_int(fib arg);
print_newline();
exit 0;;
main ();;
(* File fib.ml *)
let rec fib n =
if n < 2 then 1 else fib(n-1) + fib(n-2);;
let main () =
let arg = int_of_string Sys.argv.(1) in
print_int(fib arg);
print_newline();
exit 0;;
main ();;
Sys.argv はコマンドライン引数の文字列の配列です。Sys.argv.(1) はその配列先頭の引数の文字列です。以上のプログラムをコンパイルして、以下のようにシェルから起動出来ます。
$ ocamlc -o fib fib.ml
$ ./fib 10
89
$ ./fib 20
10946
$ ocamlc -o fib fib.ml
$ ./fib 10
89
$ ./fib 20
10946