Глава 1 Основной язык
- 1.1 Основы
- 1.2 Типы данных
- 1.3 Функции как значения
- 1.4 Записи и варианты
- 1.5 Императивные возможности
- 1.6 Исключения
- 1.7 Ленивые выражения
- 1.8 Символьная обработка выражений
- 1.9 Красивая печать
- 1.10 Форматы Printf
- 1.11 Программы OCaml в виде отдельных исполняемых файлов
Эта часть руководства — это вводное руководство по языку OCaml. Предполагается хорошее знакомство с программированием на обычных языках (например, C или Java), но предварительное знакомство с функциональными языками не требуется. В данной главе представлен основной язык. Глава 2 посвящена системе модулей, глава 3 — объектно-ориентированным возможностям, глава 4 — помеченным аргументам, глава 5 — полиморфным вариантам, глава 6 — ограничениям полиморфизма, а глава 8 — некоторым продвинутым примерам.
1.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: This expression 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
1.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 и возвращает список того же типа.
1.3 Функции как значения
OCaml — это функциональный язык: функции в полном математическом смысле поддерживаются и могут свободно передаваться так же, как и любые другие данные. Например, вот функция deriv, которая принимает любую функцию с плавающей точкой в качестве аргумента и возвращает приближение ее производной функции:
# let deriv f dx = function 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 = function 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 (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 = 1.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 = 1.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). Следовательно, добавление явных аннотаций типов для руководства по устранению неоднозначностей более надёжно, чем полагаться на устранение неоднозначностей по последнему определённому типу.
1.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)
1.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; assert false
with Done -> !x;;
val fixpoint : ('a -> 'a) -> 'a -> 'a = функция f не может генерировать исключение Done, что устраняет целые классы некорректно работающих функций.
1.7 Ленивые выражения
OCaml позволяет отложить вычисление выражения до момента, когда нам понадобится результат этого вычисления.
Мы используем lazy (expr), чтобы отложить вычисление выражения 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, даже если это шаблон подстановки, всегда принуждает к вычислению отложенного вычисления.
1.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"))
1.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 = ()
1.10 Форматы Printf
В модуле Printf (см. главу 2) есть функция printf, которая позволяет более лаконично выполнять форматированный вывод. Она следует поведению функции 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: This expression 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 = ()
1.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 обычно состоят из нескольких исходных файлов и могут использовать предварительно скомпилированные библиотеки. Глава 11 и 14 описывают, как использовать пакетные компиляторы ocamlc и ocamlopt. Перекомпиляцию проектов OCaml из нескольких файлов можно автоматизировать с помощью систем сборки сторонних производителей, таких как dune.
© 1995-2022 INRIA.
https://v2.ocaml.org/releases/4.14/htmlman/coreexamples.html
