Глава 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: 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
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 позволяет нам отложить вычисление некоторого выражения до тех пор, пока нам не понадобится результат этого вычисления.
Мы используем 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, даже если он является образцом «подстановочного знака», всегда принуждает к вычислению отложенного вычисления.
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 (см. главу 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`, печатает 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-2024 INRIA.
https://ocaml.org/manual/5.2/coreexamples.html
