Глава 1. Основной язык
Эта часть руководства представляет собой вводное учебное пособие по языку OCaml. Предполагается хорошее знание программирования на традиционных языках (например, C или Java), но предварительное знакомство с функциональными языками не требуется. В этой главе представлен основной язык. В главе 2 рассматривается система модулей, в главе 3 — объектно-ориентированные возможности, в главе 4 — именованные аргументы, в главе 5 — полиморфные варианты, в главе 6 — ограничения полиморфизма, а в главе 8 приведено несколько дополнительных примеров.
1 Основы
В этом обзоре OCaml мы будем использовать интерактивную систему, которую можно запустить, введя ocaml в оболочке Unix или командной строке Windows. Учебное пособие представлено в виде записи сеанса работы с интерактивной системой: строки, начинающиеся с #, обозначают ввод пользователя; ответы системы выводятся ниже без начального символа #.
В интерактивной системе пользователь вводит фразы OCaml, заканчивающиеся на ;;, в ответ на приглашение #; система компилирует их на лету, выполняет и выводит результат вычисления. Фразами могут быть простые выражения или определения идентификаторов с помощью let (значений или функций).
# 1 + 2 * 3;; - : int = 7
# let pi = 4.0 *. atan 1.0;; val pi : float = 3.14159265358979312
# let square x = x *. x;; val square : float -> float =
# square (sin pi) +. square (cos pi);; - : float = 1.
Система OCaml вычисляет как значение, так и тип каждой фразы. Даже типы параметров функций не нужно объявлять явно: система выводит их из использования в функции. Обратите также внимание, что целые числа и числа с плавающей точкой имеют разные типы и разные операторы: + и * работают с целыми числами, а +. и *. — с числами с плавающей точкой.
# 1.0 * 2;;
Error: The constant 1.0 has type float but an expression was expected of type
int Рекурсивные функции определяются с помощью связывания let rec:
# let rec fib n =
if n < 2 then n else fib (n - 1) + fib (n - 2);;
val fib : int -> int = # fib 10;; - : int = 55
2 Типы данных
Помимо целых чисел и чисел с плавающей точкой, в OCaml есть стандартные базовые типы данных:
- логические значения
# (1 < 2) = false;; - : bool = false
# let one = if true then 1 else 2;; val one : int = 1
- символы
# 'a';; - : char = 'a'
# int_of_char '\n';; - : int = 10
- неизменяемые строки символов
# "Hello" ^ " " ^ "world";; - : string = "Hello world"
# {|This is a quoted string, here, neither \ nor " are special characters|};; - : string = "This is a quoted string, here, neither \\ nor \" are special characters"# {|"\\"|}="\"\\\\\"";; - : bool = true# {delimiter|the end of this|}quoted string is here|delimiter} = "the end of this|}quoted string is here";; - : bool = true
К предопределённым структурам данных относятся кортежи, массивы и списки. Существуют также универсальные средства для определения собственных структур данных, например записей и вариантов; они будут подробнее рассмотрены далее. Пока же сосредоточимся на списках. Списки можно задавать перечислением элементов, разделённых точками с запятой и заключённых в квадратные скобки, или строить, добавляя элементы в начало пустого списка [] (произносится «нил») с помощью оператора :: («конс»).
# 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."]
Как и все остальные структуры данных OCaml, списки не нужно явно выделять и освобождать в памяти: управление памятью в OCaml полностью автоматическое. Аналогично, указателями не нужно управлять явно: компилятор OCaml незаметно добавляет их там, где это необходимо.
Как и для большинства структур данных OCaml, для просмотра списков и извлечения из них элементов используется сопоставление с образцом. Образцы списков имеют ту же форму, что и выражения-списки, а идентификаторы обозначают неопределённые части списка. Например, вот сортировка вставками для списка:
# 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 =
val insert : 'a -> 'a list -> 'a list = # sort l;; - : string list = ["a"; "etc."; "is"; "tale"; "told"]
Выведенный тип sort, 'a list -> 'a list, означает, что sort может работать со списками любого типа и возвращает список того же типа. Тип 'a — это переменная типа, обозначающая произвольный тип. Функция sort может работать со списками любого типа, потому что сравнения (=, <= и т. д.) в OCaml являются полиморфными: они работают с любыми двумя значениями одного типа. Поэтому сама функция sort полиморфна для всех типов списков.
# sort [6; 2; 5; 3];; - : int list = [2; 3; 5; 6]
# sort [3.14; 2.718];; - : float list = [2.718; 3.14]
Приведённая выше функция sort не изменяет исходный список: она строит и возвращает новый список, содержащий те же элементы, что и исходный, в порядке возрастания. В OCaml невозможно изменить список на месте после его создания: такие структуры данных называются неизменяемыми. Большинство структур данных OCaml неизменяемы, но некоторые (в первую очередь массивы) являются изменяемыми, то есть их можно изменять на месте в любой момент.
В OCaml тип функции с несколькими аргументами записывается так:
arg1_type -> arg2_type -> ... -> return_type. Например, выведенный тип функции insert, 'a -> 'a list -> 'a list, означает, что insert принимает два аргумента: элемент произвольного типа 'a и список элементов того же типа 'a, а возвращает список этого же типа.
3 Функции как значения
OCaml — функциональный язык: он поддерживает функции в полном математическом смысле, и их можно свободно передавать, как любые другие данные. Например, функция deriv принимает в качестве аргумента любую функцию над числами с плавающей точкой и возвращает приближение её производной:
# let deriv f dx = fun x -> (f (x +. dx) -. f x) /. dx;; val deriv : (float -> float) -> float -> float -> float =
# let sin' = deriv sin 1e-6;; val sin' : float -> float =
# sin' pi;; - : float = -1.00000000013961143
Даже композицию функций можно определить:
# let compose f g = fun x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = # let cos2 = compose square cos;; val cos2 : float -> float =
Функции, принимающие другие функции в качестве аргументов, называются «функционалами» или «функциями высшего порядка». Функционалы особенно полезны для реализации итераторов и других универсальных операций над структурами данных. Например, стандартная библиотека OCaml предоставляет функционал List.map, который применяет заданную функцию к каждому элементу списка и возвращает список результатов:
# List.map (fun 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 = 4 Записи и варианты
Пользовательские структуры данных включают записи и варианты. И те и другие определяются объявлением type. Здесь мы объявим тип записи для представления рациональных чисел.
# type ratio = {num: int; denom: int};;
type ratio = { num : int; denom : int; } # let add_ratio r1 r2 =
{num = r1.num * r2.denom + r2.num * r1.denom;
denom = r1.denom * r2.denom};;
val add_ratio : ratio -> ratio -> ratio = # add_ratio {num=1; denom=3} {num=2; denom=5};;
- : ratio = {num = 11; denom = 15} К полям записи можно также обращаться с помощью сопоставления с образцом:
# let integer_part r =
match r with
{num=num; denom=denom} -> num / denom;;
val integer_part : ratio -> int = Поскольку в этом сопоставлении с образцом имеется только один вариант, аргумент r можно непосредственно раскрыть в образце записи:
# let integer_part {num=num; denom=denom} = num / denom;;
val integer_part : ratio -> int = Ненужные поля можно опустить:
# let get_denom {denom=denom} = denom;;
val get_denom : ratio -> int = При необходимости пропущенные поля можно явно обозначить, поставив в конце списка полей подстановочный символ _::
# let get_num {num=num; _ } = num;;
val get_num : ratio -> int = Если обе стороны знака = совпадают, имя поля можно не повторять, опустив часть =field:
# let integer_part {num; denom} = num / denom;;
val integer_part : ratio -> int = Эта краткая запись полей работает и при создании записей:
# let ratio num denom = {num; denom};;
val ratio : int -> int -> ratio = Наконец, можно одновременно обновить несколько полей записи:
# let integer_product integer ratio = { ratio with num = integer * ratio.num };;
val integer_product : int -> ratio -> ratio = При таком функциональном обновлении запись слева от with копируется, за исключением полей, указанных справа, которые обновляются.
В объявлении типа-варианта перечисляются все возможные формы значений этого типа. Каждый вариант обозначается именем, называемым конструктором. Конструкторы используются как для создания значений типа-варианта, так и для их проверки с помощью сопоставления с образцом. Имена конструкторов пишутся с заглавной буквы, чтобы отличать их от имён переменных (которые должны начинаться со строчной буквы). Например, вот тип-вариант для арифметики со смешанными числами (целыми и числами с плавающей точкой):
# type number = Int of int | Float of float | Error;; type number = Int of int | Float of float | Error
Это объявление означает, что значение типа number может быть целым числом, числом с плавающей точкой или константой Error, обозначающей результат недопустимой операции (например, деления на ноль).
Перечислимые типы — это частный случай типов-вариантов, в которых все варианты являются константами:
# type sign = Positive | Negative;; type sign = Positive | Negative
# let sign_int n = if n >= 0 then Positive else Negative;; val sign_int : int -> sign =
Чтобы определить арифметические операции для типа 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 = # add_num (Int 123) (Float 3.14159);; - : number = Float 126.14159
Ещё один интересный пример типа-варианта — встроенный тип 'a option, представляющий значение типа 'a или его отсутствие:
# type 'a option = Some of 'a | None;; type 'a option = Some of 'a | None
Этот тип особенно полезен при определении функций, которые могут завершиться неудачно в обычных ситуациях, например:
# let safe_square_root x = if x >= 0. then Some(sqrt x) else None;; val safe_square_root : float -> float option =
Чаще всего типы-варианты используются для описания рекурсивных структур данных. Рассмотрим, например, тип бинарных деревьев:
# type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;; type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
Это определение означает, что бинарное дерево со значениями типа 'a (произвольного типа) либо пусто, либо является узлом, содержащим одно значение типа 'a и два поддерева, также содержащих значения типа 'a, то есть два значения типа 'a btree.
Операции над бинарными деревьями естественно выражаются рекурсивными функциями, структура которых соответствует самому определению типа. Например, вот функции поиска и вставки в упорядоченные бинарные деревья (элементы возрастают слева направо):
# 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 = # 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 = 4.1 Разрешение неоднозначности записей и вариантов
(Этот подраздел можно пропустить при первом чтении.)
Внимательный читатель, возможно, задался вопросом, что происходит, когда два или более поля записи или конструктора имеют одинаковое имя
# type first_record = { x:int; y:int; z:int }
type middle_record = { x:int; z:int }
type last_record = { x:int };;
# type first_variant = A | B | C type last_variant = A;;
Если возможны несколько вариантов, OCaml пытается использовать доступную в текущем контексте информацию, чтобы устранить неоднозначность между разными полями и конструкторами. Во-первых, если тип записи или варианта известен, OCaml может однозначно выбрать соответствующее поле или конструктор. Например:
# let look_at_x_then_z (r:first_record) =
let x = r.x in
x + r.z;;
val look_at_x_then_z : first_record -> int = # let permute (x:first_variant) = match x with
| A -> (B:first_variant)
| B -> A
| C -> C;;
val permute : first_variant -> first_variant = # type wrapped = First of first_record let f (First r) = r, r.x;; type wrapped = First of first_record val f : wrapped -> first_record * int =
В первом примере (r:first_record) — это явная аннотация, указывающая OCaml, что тип r — first_record. Благодаря этой аннотации OCaml знает, что r.x обозначает поле x первой записи. Аналогично, аннотация типа во втором примере позволяет OCaml определить, что конструкторы A, B и C относятся к первому типу-варианту. В последнем примере OCaml самостоятельно вывел, что типом r может быть только first_record, поэтому явные аннотации типов не нужны.
Такие явные аннотации типов можно использовать где угодно. В большинстве случаев они не нужны, но полезны для устранения неоднозначности, диагностики неожиданных ошибок типов, а также в сочетании с некоторыми более продвинутыми возможностями OCaml, описанными в последующих главах.
Во-вторых, для записей OCaml может определить правильный тип записи, изучив весь набор полей, используемых в выражении или образце:
# let project_and_rotate {x; y; _} = { x= - y; y = x; z = 0} ;;
val project_and_rotate : first_record -> first_record = Поскольку поля x и y могут одновременно присутствовать только в первой записи, OCaml выводит, что тип функции project_and_rotate — first_record -> first_record.
В крайнем случае, если информации недостаточно для устранения неоднозначности между разными полями или конструкторами, OCaml выбирает последний объявленный тип среди всех допустимых в текущем контексте вариантов:
# let look_at_xz {x; z} = x;;
val look_at_xz : middle_record -> int = В данном случае OCaml вывел, что возможными типами для {x;z} являются first_record и middle_record, поскольку у типа last_record нет поля z. Затем OCaml выбирает тип middle_record, так как он объявлен последним из двух возможных типов.
Обратите внимание, что это последнее средство разрешения неоднозначности действует локально: выбрав вариант, OCaml придерживается его, даже если впоследствии это приводит к ошибке типа:
# let look_at_x_then_y r =
let x = r.x in (* Ocaml deduces [r: last_record] *)
x + r.y;;
Error: This expression has type last_record
There is no field y within type last_record # let is_a_or_b x = match x with
| A -> true (* OCaml infers [x: last_variant] *)
| B -> true;;
Error: This variant pattern is expected to have type last_variant
There is no constructor B within type last_variant Кроме того, положение последнего объявленного типа довольно неустойчиво и может незаметно измениться после добавления или перемещения определения типа либо после открытия модуля (см. главу 2). Поэтому явные аннотации типов, помогающие устранить неоднозначность, надёжнее, чем выбор последнего объявленного типа.
5 Императивные возможности
Хотя все приведённые до сих пор примеры были написаны в чисто аппликативном стиле, OCaml также поддерживает полноценное императивное программирование. К его возможностям относятся обычные циклы while и for, а также изменяемые структуры данных, такие как массивы. Массивы можно создавать, перечисляя значения элементов, разделённые точками с запятой и заключённые в скобки [| и |], либо выделять для них память и инициализировать их с помощью функции Array.make, а затем заполнять присваиваниями. Например, приведённая ниже функция складывает два вектора (представленных массивами чисел с плавающей точкой) покомпонентно.
# let add_vect v1 v2 =
let len = min (Array.length v1) (Array.length v2) in
let res = Array.make 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 = # 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 = # 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.} В OCaml нет встроенного понятия переменной — идентификатора, текущее значение которого можно изменить присваиванием. (Связывание let не является присваиванием: оно вводит новый идентификатор с новой областью видимости.) Однако стандартная библиотека предоставляет ссылки — изменяемые ячейки косвенной адресации с операторами ! для получения текущего содержимого ссылки и := для присваивания содержимого. Таким образом, переменные можно эмулировать, связав ссылку с помощью 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 = Ссылки также полезны для написания функций, сохраняющих текущее состояние между вызовами. Например, следующий генератор псевдослучайных чисел хранит последнее возвращённое число в ссылке:
# 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 = И снова: в ссылках нет ничего особенного. Они реализованы как изменяемая запись с одним полем, как показано ниже.
# type 'a ref = { mutable contents: 'a };;
type 'a ref = { mutable contents : 'a; } # let ( ! ) r = r.contents;; val ( ! ) : 'a ref -> 'a =
# let ( := ) r newval = r.contents <- newval;; val ( := ) : 'a ref -> 'a -> unit =
В некоторых особых случаях может понадобиться хранить полиморфную функцию в структуре данных, сохраняя её полиморфизм. Для этого нужны предоставляемые пользователем аннотации типов, поскольку полиморфизм автоматически вводится только для глобальных определений. Однако полиморфные типы можно явно задавать для полей записей.
# type idref = { mutable id: 'a. 'a -> 'a };;
type idref = { mutable id : 'a. 'a -> 'a; } # let r = {id = fun x -> x};;
val r : idref = {id = } # let g s = (s.id 1, s.id true);; val g : idref -> int * bool =
# r.id <- (fun x -> print_string "called id\n"; x);; - : unit = ()
# g r;; called id called id - : int * bool = (1, true)
6 Исключения
В OCaml есть исключения для обозначения и обработки исключительных ситуаций. Исключения также можно использовать как универсальный механизм нелокального управления потоком выполнения, хотя злоупотреблять ими не следует, поскольку из-за этого код может стать труднее для понимания. Исключения объявляются конструкцией 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 = # head [1; 2];; - : int = 1
# head [];; Exception: Empty_list.
Исключения используются во всей стандартной библиотеке для обозначения случаев, когда функции библиотеки не могут завершиться обычным образом. Например, функция List.assoc, возвращающая данные, связанные с заданным ключом в списке пар (ключ, данные), вызывает предопределённое исключение 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 = # name_of_binary_digit 0;; - : string = "zero"
# name_of_binary_digit (-1);; - : string = "not a binary digit"
В части with выполняется сопоставление значения исключения с образцом с тем же синтаксисом и поведением, что и у match. Поэтому одной конструкцией try…with можно перехватить несколько исключений:
# let rec first_named_value values names =
try
List.assoc (head values) names
with
| Empty_list -> "no named value"
| Not_found -> first_named_value (List.tl values) names;;
val first_named_value : 'a list -> ('a * string) list -> string = # first_named_value [0; 10] [1, "one"; 10, "ten"];; - : string = "ten"
Кроме того, завершающие действия можно выполнить, перехватив все исключения, выполнив эти действия, а затем повторно вызвав исключение:
# 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 = Вместо try…with исключение можно перехватить при сопоставлении с образцом:
# let assoc_may_map f x l =
match List.assoc x l with
| exception Not_found -> None
| y -> f y;;
val assoc_may_map : ('a -> 'b option) -> 'c -> ('c * 'a) list -> 'b option =
Обратите внимание, что эта конструкция полезна только в том случае, если исключение вызывается внутри match…with. Образцы исключений можно сочетать с обычными образцами на верхнем уровне,
# let flat_assoc_opt x l =
match List.assoc x l with
| None | exception Not_found -> None
| Some _ as v -> v;;
val flat_assoc_opt : 'a -> ('a * 'b option) list -> 'b option = но их нельзя вкладывать в другие образцы. Например, образец Some (exception A) недопустим.
Если исключения используются для управления потоком выполнения, полезно сделать их как можно более локальными, объявив исключение в локальной области. Например, при таком объявлении
# let fixpoint f x =
let exception Done in
let x = ref x in
try while true do
let y = f !x in
if !x = y then raise Done else x := y
done
with Done -> !x;;
val fixpoint : ('a -> 'a) -> 'a -> 'a = функция f не может вызвать исключение Done, что исключает целый класс функций с нежелательным поведением.
7 Ленивые выражения
OCaml позволяет отложить вычисление до того момента, когда понадобится его результат.
Чтобы отложить вычисление выражения expr, используется конструкция lazy (expr). Например, вычисление 1+1 можно отложить до тех пор, пока не понадобится результат этого выражения — 2. Посмотрим, как инициализировать ленивое выражение.
# let lazy_two = lazy (print_endline "lazy_two evaluation"; 1 + 1);; val lazy_two : int lazy_t =
Мы добавили print_endline "lazy_two evaluation", чтобы видеть, когда вычисляется ленивое выражение.
Значение lazy_two отображается как <lazy>: это означает, что выражение ещё не вычислено и его окончательное значение неизвестно.
Обратите внимание, что lazy_two имеет тип int lazy_t. Однако тип 'a lazy_t — это внутреннее имя типа, поэтому по возможности следует предпочитать тип 'a Lazy.t.
Когда результат ленивого выражения наконец понадобится, можно вызвать для этого выражения Lazy.force, чтобы выполнить его вычисление. Функция force находится в модуле стандартной библиотеки Lazy.
# Lazy.force lazy_two;; lazy_two evaluation - : int = 2
Обратите внимание: приведённый выше вызов функции выводит «lazy_two evaluation», а затем возвращает обычное значение вычисления.
Теперь, если посмотреть на значение lazy_two, мы увидим, что оно отображается уже не как <lazy>, а как lazy 2.
# lazy_two;; - : int lazy_t = lazy 2
Это происходит потому, что Lazy.force сохраняет результат вычисления принудительно вычисленного выражения. Иными словами, при каждом последующем вызове Lazy.force для этого выражения возвращается результат первого вычисления, и повторного вычисления ленивого выражения не происходит. Давайте ещё раз вычислим lazy_two.
# Lazy.force lazy_two;; - : int = 2
На этот раз выражение не вычисляется: обратите внимание, что «lazy_two evaluation» не выводится. Просто возвращается результат первоначального вычисления.
Ленивые образцы предоставляют ещё один способ принудительно вычислить ленивое выражение.
# let lazy_l = lazy ([1; 2] @ [3; 4]);; val lazy_l : int list lazy_t =
# let lazy l = lazy_l;; val l : int list = [1; 2; 3; 4]
Мы также можем использовать ленивые шаблоны при сопоставлении с образцом.
# let maybe_eval lazy_guard lazy_expr =
match lazy_guard, lazy_expr with
| lazy false, _ -> "matches if (Lazy.force lazy_guard = false); lazy_expr not forced"
| lazy true, lazy _ -> "matches if (Lazy.force lazy_guard = true); lazy_expr forced";;
val maybe_eval : bool lazy_t -> 'a lazy_t -> string = Ленивое выражение lazy_expr вычисляется только в том случае, если после вычисления значение lazy_guard оказывается равным true. Действительно, простой шаблон-подстановочный знак (не ленивый) никогда не инициирует вычисление ленивого выражения. Однако шаблон с ключевым словом lazy, даже если это шаблон-подстановочный знак, всегда инициирует вычисление отложенного вычисления.
8 Символьная обработка выражений
Завершим это введение более полным примером использования OCaml для символьной обработки: формальных преобразований арифметических выражений, содержащих переменные. Следующий вариантный тип описывает выражения, с которыми мы будем работать:
# 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 = # 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 = # 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"))
9 Форматированный вывод
Как видно из приведённых выше примеров, внутреннее представление выражений (также называемое абстрактным синтаксисом) быстро становится трудным для чтения и записи по мере увеличения выражений. Нам нужны принтер и парсер, чтобы преобразовывать абстрактный синтаксис в конкретный синтаксис и обратно. В случае выражений это привычная алгебраическая запись (например, 2*x+1).
При выводе мы учитываем обычные правила приоритета (то есть * имеет более высокий приоритет, чем +), чтобы не выводить лишние скобки. Для этого мы отслеживаем текущий приоритет оператора и заключаем оператор в скобки, только если его приоритет ниже текущего.
# 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 = # 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 = ()
10 Форматы Printf
В модуле Printf есть функция printf (см. главу 2), которая позволяет лаконично выводить форматированный текст. Она работает так же, как функция printf из стандартной библиотеки C. Функция printf принимает строку формата, описывающую желаемый вывод как текст, перемежающийся спецификаторами (например, %d, %f). Затем спецификаторы заменяются следующими аргументами в порядке их появления в строке формата:
# Printf.printf "%i + %i is an integer value, %F * %F is a float, %S\n" 3 2 4.5 1. "this is a string";; 3 + 2 is an integer value, 4.5 * 1. is a float, "this is a string" - : unit = ()
Система типов OCaml проверяет совместимость типов аргументов со спецификаторами. Если передать аргумент типа, не соответствующего спецификатору формата, компилятор выведет сообщение об ошибке:
# Printf.printf "Float value: %F" 42;;
Error: The constant 42 has type int but an expression was expected of type
float
Hint: Did you mean 42.? Функция fprintf похожа на printf, но принимает канал вывода в качестве первого аргумента. Спецификатор %a может пригодиться для определения пользовательских принтеров (для пользовательских типов). Например, можно создать шаблон вывода, преобразующий целочисленный аргумент в знаковое десятичное число:
# let pp_int ppf n = Printf.fprintf ppf "%d" n;; val pp_int : out_channel -> int -> unit =
# Printf.printf "Outputting an integer using a custom printer: %a " pp_int 42;; Outputting an integer using a custom printer: 42 - : unit = ()
Преимущество таких принтеров на основе спецификатора %a заключается в том, что их можно комбинировать, пошагово создавая более сложные принтеры. Можно определить комбинатор, который преобразует принтер для типа 'a в принтер для типа 'a optional:
# let pp_option printer ppf = function
| None -> Printf.fprintf ppf "None"
| Some v -> Printf.fprintf ppf "Some(%a)" printer v;;
val pp_option :
(out_channel -> 'a -> unit) -> out_channel -> 'a option -> unit = # Printf.fprintf stdout
"The current setting is %a. \nThere is only %a\n"
(pp_option pp_int) (Some 3)
(pp_option pp_int) None
;;
The current setting is Some(3).
There is only None
- : unit = () Если значение его аргумента равно None, принтер, возвращаемый pp_option printer, выводит None; в противном случае он использует переданный принтер для вывода Some .
Вот как можно переписать принтер форматированного вывода с помощью fprintf:
# let pp_expr ppf expr =
let open_paren prec op_prec output =
if prec > op_prec then Printf.fprintf output "%s" "(" in
let close_paren prec op_prec output =
if prec > op_prec then Printf.fprintf output "%s" ")" in
let rec print prec ppf expr =
match expr with
| Const c -> Printf.fprintf ppf "%F" c
| Var v -> Printf.fprintf ppf "%s" v
| Sum(f, g) ->
open_paren prec 0 ppf;
Printf.fprintf ppf "%a + %a" (print 0) f (print 0) g;
close_paren prec 0 ppf
| Diff(f, g) ->
open_paren prec 0 ppf;
Printf.fprintf ppf "%a - %a" (print 0) f (print 1) g;
close_paren prec 0 ppf
| Prod(f, g) ->
open_paren prec 2 ppf;
Printf.fprintf ppf "%a * %a" (print 2) f (print 2) g;
close_paren prec 2 ppf
| Quot(f, g) ->
open_paren prec 2 ppf;
Printf.fprintf ppf "%a / %a" (print 2) f (print 3) g;
close_paren prec 2 ppf
in print 0 ppf expr;;
val pp_expr : out_channel -> expression -> unit = # pp_expr stdout e; print_newline ();; 2. * x + 1. - : unit = ()
# pp_expr stdout (deriv e "x"); print_newline ();; 2. * 1. + 0. * x + 0. - : unit = ()
Из-за способа создания строк формата для хранения строки формата требуется явное указание типа:
# let str : _ format =
"%i is an integer value, %F is a float, %S\n";;
# Printf.printf str 3 4.5 "string value";; 3 is an integer value, 4.5 is a float, "string value" - : unit = ()
11 Отдельно запускаемые программы OCaml
Все приведённые до сих пор примеры выполнялись в интерактивной системе. Код OCaml также можно компилировать отдельно и запускать в неинтерактивном режиме с помощью пакетных компиляторов ocamlc и ocamlopt. Исходный код должен находиться в файле с расширением .ml. Он состоит из последовательности фраз, которые во время выполнения вычисляются в порядке их появления в исходном файле. В отличие от интерактивного режима, типы и значения не выводятся автоматически; для вывода программа должна явно вызывать функции печати. Символ ;;, использованный в интерактивных примерах, не требуется в исходных файлах для компиляторов OCaml, но может быть полезен для однозначного обозначения конца выражения верхнего уровня даже при наличии синтаксических ошибок. Ниже приведён пример отдельно запускаемой программы, выводящей наибольший общий делитель (НОД) двух чисел:
(* File gcd.ml *) let rec gcd a b = if b = 0 then a else gcd b (a mod b);; let main () = let a = int_of_string Sys.argv.(1) in let b = int_of_string Sys.argv.(2) in Printf.printf "%d\n" (gcd a b); exit 0;; main ();;
Sys.argv — это массив строк, содержащий параметры командной строки. Следовательно, Sys.argv.(1) — это первый параметр командной строки. Приведённая выше программа компилируется и запускается следующими командами оболочки:
$ ocamlc -o gcd gcd.ml $ ./gcd 6 9 3 $ ./gcd 7 11 1
Более сложные отдельно запускаемые программы OCaml обычно состоят из нескольких исходных файлов и могут связываться с предварительно скомпилированными библиотеками. В главах 13 и 16 объясняется, как использовать пакетные компиляторы ocamlc и ocamlopt. Повторную компиляцию многофайловых проектов OCaml можно автоматизировать с помощью сторонних систем сборки, таких как dune.
© 1995-2026 INRIA.
https://ocaml.org/manual/5.5/coreexamples.html
