Идиоматические исключения для выхода из циклов в OCaml
В OCaml циклы императивного стиля можно завершить на раннем этапе, вызвав исключения.
Хотя использование императивных циклов само по себе не является идиоматическим в OCaml, я хотел бы знать, каковы наиболее идиоматические способы эмуляции императивных циклов при ранних выходах (принимая во внимание такие аспекты, как производительность, если это возможно).
Например, в старом FAQ по OCaml упоминается исключение Exit:
Exit: используется для выпрыгивания из циклов или функций.
Это все еще актуально? Стандартная библиотека просто упоминает это как исключение общего назначения:
Exitисключение не вызывается какой-либо библиотечной функцией. Это предусмотрено для использования в ваших программах.
В связи с этим в этом ответе на другой вопрос упоминается использование предварительно вычисленных let exit = Exit исключение, чтобы избежать выделения внутри цикла. Это все еще требуется?
Также иногда хочется выйти из цикла с определенным значением, таким как raise (Leave 42), Есть ли для этого идиоматическое исключение или соглашение об именах? Должен ли я использовать ссылки в этом случае (например, let res = ref -1 in ... <loop body> ... res := 42; raise Exit)?
Наконец, использование Exit во вложенных циклах предотвращает некоторые случаи, когда нужно выйти из нескольких циклов, например break <label> на Яве. Это потребует определения исключений с разными именами или, по крайней мере, использования целого числа, чтобы указать, сколько областей должно быть завершено (например, Leave 2 указать, что 2 уровня должны быть завершены). Опять же, есть ли подход и именование исключений, которые здесь идиоматичны?
4 ответа
Как было первоначально написано в комментариях, идиоматический способ сделать ранний выход в OCaml - использовать продолжения. В тот момент, когда вы хотите, чтобы раннее возвращение было выполнено, вы создаете продолжение и передаете его в код, который может вернуться рано. Это более общий термин, чем метки для циклов, поскольку вы можете выйти из всего, что имеет доступ к продолжению.
Также, как указано в комментариях, обратите внимание на использование raise_notrace для исключений, чей след вы никогда не хотите генерировать во время выполнения.
"Наивная" первая попытка:
module Continuation :
sig
(* This is the flaw with this approach: there is no good choice for
the result type. *)
type 'a cont = 'a -> unit
(* with_early_exit f passes a function "k" to f. If f calls k,
execution resumes as if with_early_exit completed
immediately. *)
val with_early_exit : ('a cont -> 'a) -> 'a
end =
struct
type 'a cont = 'a -> unit
(* Early return is implemented by throwing an exception. The ref
cell is used to store the value with which the continuation is
called - this is a way to avoid having to generate an exception
type that can store 'a for each 'a this module is used with. The
integer is supposed to be a unique identifier for distinguishing
returns to different nested contexts. *)
type 'a context = 'a option ref * int64
exception Unwind of int64
let make_cont ((cell, id) : 'a context) =
fun result -> cell := Some result; raise_notrace (Unwind id)
let generate_id =
let last_id = ref 0L in
fun () -> last_id := Int64.add !last_id 1L; !last_id
let with_early_exit f =
let id = generate_id () in
let cell = ref None in
let cont : 'a cont = make_cont (cell, id) in
try
f cont
with Unwind i when i = id ->
match !cell with
| Some result -> result
(* This should never happen... *)
| None -> failwith "with_early_exit"
end
let _ =
let nested_function i k = k 15; i in
Continuation.with_early_exit (nested_function 42)
|> string_of_int
|> print_endline
Как вы можете видеть, вышеприведенное реализует ранний выход, скрывая исключение. На самом деле продолжение является частично примененной функцией, которая знает уникальный идентификатор контекста, для которого она была создана, и имеет ячейку ссылки для хранения значения результата, в то время как исключение выдается в этот контекст. Код выше печатает 15. Вы можете передать продолжение k так глубоко, как вы хотите. Вы также можете определить функцию f непосредственно в точке, где оно передается with_early_exit, давая эффект, похожий на ярлык в цикле. Я использую это очень часто.
Проблема с вышеупомянутым типом результата 'a contкоторый я произвольно установил unit, На самом деле, функция типа 'a cont никогда не возвращается, поэтому мы хотим, чтобы он вел себя как raise - быть пригодным для использования там, где ожидается любой тип. Однако это не сразу работает. Если вы делаете что-то вроде type ('a, 'b) cont = 'a -> 'bи передайте это вашей вложенной функции, средство проверки типов выведет тип для 'b в одном контексте, а затем заставлять вас вызывать продолжения только в контекстах одного типа, т.е. вы не сможете делать такие вещи, как
(if ... then 3 else k 15)
...
(if ... then "s" else k 16)
потому что первое выражение силы 'b быть int, но второе требует 'b быть string,
Чтобы решить эту проблему, нам нужно предоставить функцию, аналогичную raise для раннего возвращения, т.е.
(if ... then 3 else throw k 15)
...
(if ... then "s" else throw k 16)
Это значит отойти от чистых продолжений. Мы должны частично подать заявку make_cont выше (и я переименовал его в throw), и вместо этого передайте открытый контекст:
module BetterContinuation :
sig
type 'a context
val throw : 'a context -> 'a -> _
val with_early_exit : ('a context -> 'a) -> 'a
end =
struct
type 'a context = 'a option ref * int64
exception Unwind of int64
let throw ((cell, id) : 'a context) =
fun result -> cell := Some result; raise_notrace (Unwind id)
let generate_id = (* Same *)
let with_early_exit f =
let id = generate_id () in
let cell = ref None in
let context = (cell, id) in
try
f context
with Unwind i when i = id ->
match !cell with
| Some result -> result
| None -> failwith "with_early_exit"
end
let _ =
let nested_function i k = ignore (BetterContinuation.throw k 15); i in
BetterContinuation.with_early_exit (nested_function 42)
|> string_of_int
|> print_endline
Выражение throw k v может использоваться в тех случаях, когда требуются разные типы.
Я использую этот подход повсеместно в некоторых больших приложениях, над которыми я работаю. Я предпочитаю это даже регулярным исключениям. У меня есть более сложный вариант, где with_early_exit имеет подпись примерно так:
val with_early_exit : ('a context -> 'b) -> ('a -> 'b) -> 'b
где первая функция представляет попытку что-то сделать, а вторая представляет обработчик ошибок типа 'a это может привести. Вместе с вариантами и полиморфными вариантами это дает более явный тип обработки исключений. Это особенно эффективно с полиморфными вариантами, так как компилятор может вывести множество вариантов ошибок.
Подход Jane Street эффективно делает то же, что описано здесь, и на самом деле у меня ранее была реализация, которая генерировала типы исключений с первоклассными модулями. Я больше не уверен, почему я в итоге выбрал этот - могут быть тонкие различия:)
Просто чтобы ответить на конкретную часть моего вопроса, которая не упоминалась в других ответах:
... используя предварительно вычисленное исключение let exit = Exit, чтобы избежать выделения внутри цикла. Это все еще требуется?
Я сделал несколько микро-тестов, используя Core_bench на 4.02.1+fp и результаты показывают отсутствие существенной разницы: при сравнении двух одинаковых циклов, один из которых содержит локальный exit объявленный до цикла, а другой без него, разница во времени минимальна.
Разница между raise Exit а также raise_notrace Exit в этом примере он также был минимальным, около 2% в одних прогонах, до 7% в других, но он вполне мог быть в пределах погрешностей такого короткого эксперимента.
В целом, я не мог измерить заметную разницу, поэтому, если у кого-то не будет примеров, где Exit/exit значительно повлиять на производительность, я бы предпочел первый, так как он более понятен и избегает создания в основном бесполезной переменной.
Наконец, я также сравнил разницу между двумя идиомами: использование ссылки на значение перед выходом из цикла или создание определенного типа исключения, содержащего возвращаемое значение.
С учетом значения результата + Exit:
let res = ref 0 in
let r =
try
for i = 0 to n-1 do
if a.(i) = v then
(res := v; raise_notrace Exit)
done;
assert false
with Exit -> !res
in ...
С конкретным типом исключения:
exception Res of int
let r =
try
for i = 0 to n-1 do
if a.(i) = v then
raise_notrace (Res v)
done;
assert false
with Res v -> v
in ...
Еще раз, различия были минимальными и сильно варьировались между пробегами. В общем, первая версия (ссылка + Exit), казалось, имел небольшое преимущество (на 0-10% быстрее), но разница была недостаточно значительной, чтобы рекомендовать одну версию над другой.
Поскольку первое требует определения начального значения (которое может не существовать) или использования типа параметра для инициализации ссылки, а второе требует определения нового исключения для каждого типа значения, возвращаемого из цикла, здесь нет идеального решения.
По поводу точки
используя предварительно вычисленное исключение let exit = Exit, чтобы избежать выделения внутри цикла. Это все еще требуется?
Ответ - нет с достаточно недавними версиями OCaml. Вот соответствующая выдержка из журнала изменений OCaml 4.02.0.
- PR # 6203: Конструкторы исключений констант больше не выделяются (Ален Фриш)
Вот PR6203: http://caml.inria.fr/mantis/view.php?id=6203
Exit это нормально (я не уверен, могу ли я сказать, что это идиоматично). Но убедитесь, что вы используете raise_notrace, если вы используете достаточно недавний компилятор (с 4.02).
Еще лучшее решение, это использовать with_return из библиотеки OCaml Core. У него не будет проблем с областью действия, потому что он создаст новый новый тип исключения для каждой вложенности.
Конечно, вы можете достичь тех же результатов или просто взять исходный код реализации Core.
И еще более идиоматично, не использовать исключения для короткого замыкания итерации, а рассмотреть возможность использования существующего алгоритма (find, find_map, existsи т. д.) или просто напишите рекурсивную функцию, если никакой алгоритм вам не подходит.