在OCaml中退出循环的惯用例外

Question

在OCaml中,可以通过引发异常提前退出命令式循环.

虽然在OCaml中使用命令式循环本身并不是惯用语,但我想知道在早期退出时模拟命令式循环的最惯用方法是什么(考虑到性能等方面,如果可能的话).

例如,旧的OCaml FAQ提到例外Exit:

Exit:用于跳出循环或函数.

它仍然是最新的吗？该标准库简单地提到它作为一个通用的异常:

该Exit异常没有被任何库函数提高.它可以在您的程序中使用.

与此相关,这个回答另外一个问题提到使用预计算let exit = Exit例外,以避免在循环中分配.它还需要吗？

此外,有时人们想要从具有特定值的循环中退出,例如raise (Leave 42).是否有惯用的例外或命名约定来执行此操作？在这种情况下我应该使用引用(例如let res = ref -1 in ... <loop body> ... res := 42; raise Exit)吗？

最后,Exit在嵌套循环中的使用可以防止某些人想要退出几个循环的情况,比如break <label>在Java中.这将需要定义具有不同名称的异常,或者至少使用整数来指示应退出多少范围(例如Leave 2,指示应退出2个级别).同样,这里有一个惯用的方法/异常命名吗？

Answer 1

正如最初在评论中发布的那样,在OCaml中提前退出的惯用方法是使用continuation.在您希望提前返回的位置,您创建一个延续,并将其传递给可能提前返回的代码.这比循环标签更通用,因为您可以退出几乎任何有权访问延续的东西.

此外,如在注释中发布的那样,请注意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

如您所见,上面通过隐藏异常来实现提前退出.continuation实际上是一个部分应用的函数,它知道创建它的上下文的唯一id,并且有一个引用单元来存储结果值,同时将异常抛出到该上下文.上面的代码打印15.您可以根据需要传递延续k.您还可以在f传递函数的位置立即定义函数with_early_exit,从而产生类似于在循环上具有标签的效果.我经常使用它.

上面的问题是'a cont我任意设置的结果类型unit.实际上,类型的函数'a cont永远不会返回,所以我们希望它表现得像raise- 在任何类型都可以使用的地方都可以使用.但是,这不会立即起作用.如果您执行类似操作type ('a, 'b) cont = 'a -> 'b并将其传递给嵌套函数,则类型检查器将'b在一个上下文中推断类型,然后强制您仅在具有相同类型的上下文中调用continuation,即您将无法做的事情

(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方法与此处描述的方法有效地相同,事实上我之前有一个实现,它使用一流模块生成异常类型.我不确定为什么我最终选择了这个 - 可能会有微妙的差异:)