Idiomatyczne wyjątki dla wychodzących pętli w OCaml

Question

W OCaml, pętle w stylu imperatywu mogą zostać zakończone wcześnie poprzez zgłaszanie wyjątków.

Chociaż zastosowanie nadrzędnych pętli nie jest idiomatyczne per se w SML, chciałbym wiedzieć, jakie są najbardziej idiomatyczne sposoby naśladować nadrzędne pętle z pierwszych zjazdów (biorąc pod uwagę takie aspekty jak: wydajność, jeśli to możliwe).

Przykładowo wymienia an old OCaml FAQ wyjątek Exit:

Exit: umożliwiają przechodzenie z pętli lub funkcji.

Czy nadal jest aktualny? standard library po prostu wspomina o tym jako wyjątku ogólnego przeznaczenia:

Wyjątek Exit nie jest wywoływany przez żadną funkcję biblioteczną. Jest przeznaczony do użytku w twoich programach.

Relatedly, this answer do następnego pytania wspomina stosując Precomputed let exit = Exit wyjątek uniknąć alokacji wewnątrz pętli. Czy nadal jest wymagane?

Czasami chce się wyjść z pętli o określonej wartości, na przykład raise (Leave 42). Czy istnieje wyjątek idiomatyczny lub konwencja nazewnictwa, aby to zrobić? Czy w tym przypadku należy używać referencji (np. let res = ref -1 in ... <loop body> ... res := 42; raise Exit)?

Wreszcie, użycie Exit w zagnieżdżonych pętlach zapobiega przypadkom, w których chciałoby się wyjść z kilku pętli, na przykład break <label> w Javie. Wymagałoby to zdefiniowania wyjątków o różnych nazwach lub przynajmniej użycia liczby całkowitej, aby wskazać, ile wyjść powinno zostać zakończonych (np. Leave 2, aby wskazać, że należy opuścić 2 poziomy). Ponownie, czy jest tu idiomatyczne nazewnictwo podejścia/wyjątku?

Answer 1

Zgodnie z pierwotnymi komentarzami, idiomatyczny sposób na wcześniejsze wyjście z OCaml jest kontynuacją. W miejscu, w którym chcesz wrócić do wcześniejszego powrotu, tworzysz kontynuację i przekazujesz ją do kodu, który może wrócić wcześniej. Jest to bardziej ogólne niż etykiety dla pętli, ponieważ możesz wyjść z niemal wszystkiego, co ma dostęp do kontynuacji.

Ponadto, jak podano w komentarzach, należy zwrócić uwagę na użycie raise_notrace dla wyjątków, których ślad nigdy nie powinien zostać wygenerowany w środowisku wykonawczym.

A „naiwny” Pierwsza próba:

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 

Jak widać, powyższe narzędzia wczesne wyjście ukrywając wyjątek. Kontynuacja jest właściwie częściowo zastosowaną funkcją, która zna unikalny identyfikator kontekstu, dla którego została utworzona, i ma komórkę odniesienia do przechowywania wartości wyniku, podczas gdy wyjątek jest rzucany do tego kontekstu. Powyższy kod drukuje 15. Możesz kontynuować kontynuację k tak głęboko, jak chcesz. Możesz również zdefiniować funkcję f natychmiast w miejscu, w którym zostanie przekazana do with_early_exit, dając efekt podobny do etykiety w pętli. Używam tego bardzo często.

Problem z powyższym jest wynikiem typu 'a cont, który arbitralnie ustawiłem na unit. W rzeczywistości funkcja typu 'a cont nigdy nie wraca, więc chcemy, aby zachowywała się ona jak raise - może być użyta tam, gdzie oczekuje się dowolnego typu. Jednak to nie działa od razu. Jeśli zrobisz coś takiego, jak type ('a, 'b) cont = 'a -> 'b, i przekażesz to do funkcji zagnieżdżonej, sprawdzacz typów określi typ dla 'b w jednym kontekście, a następnie zmusi Cię do wywołania kontynuacji tylko w kontekstach tego samego typu, tj. Nie będziesz w stanie robić takie rzeczy jak

(if ... then 3 else k 15) 
... 
(if ... then "s" else k 16) 

ponieważ pierwsze siły ekspresji 'b być int, ale drugi wymaga 'b być string.

Aby rozwiązać ten problem, że trzeba zapewnić funkcje analogiczne do raise wczesnego powrotu, to znaczy

(if ... then 3 else throw k 15) 
... 
(if ... then "s" else throw k 16) 

Oznacza to, odsuwając się od czystych przedłużeń. Musimy un-częściowo stosuje make_cont powyżej (i przemianował ją na throw) i przekazać nagi kontekst wokół zamiast:

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 

Wyrażenie throw k v może być stosowany w sytuacjach, gdzie wymagane są różne typy.

Używam tego podejścia wszechobecnie w niektórych dużych aplikacjach, nad którymi pracuję. Wolę to od zwykłych wyjątków. Mam bardziej skomplikowany wariant, w którym with_early_exit posiada podpis mniej więcej tak:

val with_early_exit : ('a context -> 'b) -> ('a -> 'b) -> 'b 

gdzie pierwsza funkcja stanowi próbę zrobienia czegoś, a druga reprezentuje obsługi błędów typu 'a które mogą wyniknąć. Wraz z wariantami i odmianami polimorficznymi daje to wyraźniejsze podejście do obsługi wyjątków. Jest szczególnie silny w przypadku odmian polimorficznych, ponieważ zestaw wariantów błędów może być wywnioskowany przez kompilator.

Podejście Jane Street skutecznie działa tak samo, jak to tutaj opisano, aw rzeczywistości poprzednio miałem implementację, która generowała typy wyjątków z pierwszorzędnymi modułami. Nie jestem pewien, dlaczego ja już ostatecznie wybrał ten - mogą być subtelne różnice :)

Answer 2

Exit jest ok (nie jestem pewien, czy mogę powiedzieć, że jest idiomatyczny). Ale upewnij się, że używasz raise_notrace, jeśli korzystasz z najnowszej kompilacji (od wersji 4.02).

Jeszcze lepszym rozwiązaniem jest użycie with_return z OCaml Core library. Nie będzie miał żadnych problemów z zasięgiem, ponieważ stworzy nowy nowy typ wyjątku dla każdego zagnieżdżenia.

Oczywiście można osiągnąć takie same wyniki lub po prostu wziąć kod źródłowy implementacji Core.

A nawet więcej idiomatyczne, to nie używać wyjątków dla zwierania swoją iteracji i rozważyć użycie istniejącego algorytmu (find, find_map, exists, etc) lub po prostu napisać rekurencyjną funkcję, jeśli nie ma cię garnitury algorytmu.

Answer 3

Wystarczy odpowiedzieć na konkretną część mojego pytania, które nie zostało wymienione w innych odpowiedzi:

... używając prekompute let exit = Wyjdź z wyjątku, aby uniknąć przydziałów w pętli. Czy nadal jest wymagane?

Zrobiłem kilka mikro-wzorców używając Core_bench na 4.02.1+fp a wyniki nie wskazują na istotną różnicę: przy porównywaniu dwóch identycznych pętli, jeden zawierający lokalny exit zadeklarowane przed pętlą i drugi bez niego, różnica czasu jest minimalny .

Różnica między raise Exit i raise_notrace Exit w tym przykładzie była również minimalna, około 2% w niektórych seriach, do 7% w innych, ale może również zawierać się marginesy błędu tak krótkiego eksperymentu.

Ogólnie rzecz biorąc, nie mogłem zmierzyć żadnej zauważalnej różnicy, więc chyba, że ​​ktoś miałby przykłady, w których Exit/exit znacząco wpłynęłoby na wydajność, wolałbym ten pierwszy, ponieważ jest bardziej przejrzysty i unika tworzenia najczęściej niepotrzebnej zmiennej.

Na koniec porównałem również różnicę między dwoma idiomami: używając odwołania do wartości przed wyjściem z pętli lub tworząc określony typ wyjątku zawierający zwracaną wartość.

Nawiązując doprowadzić wartość ± 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 ... 

z konkretnego typu wyjątek:

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 ... 

Ponownie te różnice były niewielkie i zmieniać się w poszczególnych seriach. Ogólnie rzecz biorąc, pierwsza wersja (referencja + Exit) wydawała się mieć niewielką przewagę (o 0% do 10% szybciej), ale różnica nie była na tyle znacząca, aby zalecić jedną wersję względem drugiej.

Ponieważ pierwsza z nich wymaga zdefiniowania wartości początkowej (która może nie istnieć) lub użycia typu opcji w celu zainicjowania referencji, a druga wymaga zdefiniowania nowego wyjątku dla każdego typu wartości zwróconej z pętli, nie ma idealnego rozwiązania tutaj.

Answer 4

Odnośnie punktu

stosując Precomputed let wyjście = Wyjście wyjątek uniknąć przydziały wewnątrz pętli. Czy nadal jest wymagane?

odpowiedź brzmi: no z wystarczająco nowymi wersjami OCaml. Oto odpowiedni fragment ze zmian w OCaml 4.02.0.

• PR # 6203: Stała konstruktorzy wyjątków nie przeznaczyć (Alain Frisch)

Oto PR6203: http://caml.inria.fr/mantis/view.php?id=6203