Jakie są zasady oceny funkcji a -> () w Haskell?

12

Tak jak w tytule: jakie są gwarancje, że jednostka zwrotna funkcji Haskell zostanie poddana ocenie? Można by pomyśleć, że w takim przypadku nie ma potrzeby przeprowadzania żadnej oceny, kompilator mógłby zastąpić wszystkie takie wywołania natychmiastową ()wartością, chyba że istnieją wyraźne żądania zachowania ścisłości, w którym to przypadku kod może zdecydować, czy powinien powrót ()lub dół.
Eksperymentowałem z tym w GHCi i wydaje się, że dzieje się odwrotnie, to znaczy, że taka funkcja wydaje się być oceniana. Byłby to bardzo prymitywny przykład

f :: a -> ()
f _ = undefined

Ocena f 1powoduje błąd z powodu obecności undefined, więc pewna ocena zdecydowanie się zdarza. Nie jest jednak jasne, jak daleko sięga ocena; czasami wydaje się, że idzie tak głęboko, jak to konieczne, aby ocenić wszystkie powracające wywołania funkcji (). Przykład:

g :: [a] -> ()
g [] = ()
g (_:xs) = g xs

Ten kod zapętla się w nieskończoność, jeśli jest wyświetlany z g (let x = 1:x in x). Ale wtedy

f :: a -> ()
f _ = undefined
h :: a -> ()
h _ = ()

może być użyty do pokazania, że h (f 1)zwraca (), więc w tym przypadku nie wszystkie podwyrażenia o wartości jednostkowej są oceniane. Jaka jest tutaj ogólna zasada?

ETA: oczywiście wiem o lenistwie. Pytam, co uniemożliwia pisarzom kompilatorów uczynienie tego konkretnego przypadku jeszcze bardziej leniwym, niż zwykle jest to możliwe.

ETA2: podsumowanie przykładów: GHC wydaje się traktować ()dokładnie tak, jak każdy inny typ, tzn. Jakby istniało pytanie o to, która regularna wartość zamieszkująca ten typ powinna zostać zwrócona z funkcji. Fakt, że istnieje tylko jedna taka wartość, nie wydaje się (ab) wykorzystywany przez algorytmy optymalizacyjne.

ETA3: kiedy mówię Haskell, mam na myśli Haskella, jak zdefiniowano w Raporcie, a nie Haskell-the-H-in-GHC. Wydaje się, że jest to założenie, które nie jest tak szeroko rozpowszechnione, jak sobie wyobrażałem (co stanowiło „100% czytelników”), lub prawdopodobnie byłbym w stanie sformułować jaśniejsze pytanie. Mimo to żałuję, że zmieniłem tytuł pytania, ponieważ pierwotnie pytano, jakie są gwarancje wywołania takiej funkcji.

ETA4: wydaje się, że pytanie to już się potoczyło i uważam, że nie ma na nie odpowiedzi. (Szukałem funkcji „zamknij pytanie”, ale znalazłem tylko „odpowiedz na swoje pytanie”, a ponieważ nie można na nie odpowiedzieć, nie poszedłem tą drogą.) Nikt nie przywołał niczego w Raporcie, które by to zadecydowało w obu przypadkach , który kusi mnie, by interpretować jako mocną, ale nieokreśloną odpowiedź „nie ma gwarancji dla języka jako takiego”. Wiemy tylko, że obecna implementacja GHC nie pominie oceny takiej funkcji.

Natknąłem się na rzeczywisty problem podczas przenoszenia aplikacji OCaml do Haskell. Oryginalna aplikacja miała wzajemnie rekurencyjną strukturę wielu typów, a kod zadeklarował szereg funkcji wywoływanych assert_structureN_is_correctdla N w 1..6 lub 7, z których każda zwróciła jednostkę, jeśli struktura była rzeczywiście poprawna, i zgłosiła wyjątek, jeśli nie była . Ponadto funkcje te wywoływały się nawzajem, ponieważ rozkładały warunki poprawności. W Haskell lepiej sobie z tym Either Stringporadzić za pomocą monady, więc zapisałem to w ten sposób, ale pytanie jako kwestia teoretyczna pozostało. Dzięki za wszystkie dane wejściowe i odpowiedzi.

Kryptozoon
źródło
1
To jest lenistwo w pracy. O ile wynik funkcji nie jest wymagany (np. Przez dopasowanie wzorca względem konstruktora), ciało funkcji nie jest oceniane. Aby zaobserwować różnicę, spróbuj porównać h1::()->() ; h1 () = ()i h2::()->() ; h2 _ = (). Uruchom oba h1 (f 1)i h2 (f 1)i przekonaj się, że wymaga tego tylko pierwszy (f 1).
chi
1
„Lenistwo wydaje się dyktować, że zastępuje się je () bez dokonywania jakiejkolwiek oceny”. Co to znaczy? f 1jest „zastąpiony” przez undefinedwe wszystkich przypadkach.
oisdk
3
Funkcja ... -> ()może 1) zakończyć i zwrócić (), 2) zakończyć z błędem wyjątku / czasu działania i nie zwrócić niczego, lub 3) odejść (nieskończona rekurencja). GHC nie optymalizuje kodu, zakładając, że tylko 1) może się zdarzyć: jeśli f 1jest wymagany, nie pomija jego oceny i powrotu (). Semantyka Haskella polega na jej ocenie i sprawdzeniu, co dzieje się wśród 1,2,3.
chi
2
W ()tym pytaniu nie ma nic specjalnego (ani typu, ani wartości). Wszystkie te same obserwacje zdarzają się, jeśli zastąpisz () :: ()je, powiedzmy, 0 :: Intwszędzie. To wszystko nudne stare konsekwencje leniwej oceny.
Daniel Wagner
2
nie, „unikanie” itp. nie jest semantyką Haskella. i są dwie możliwe wartości ()typu ()i undefined.
Czy Ness

Odpowiedzi:

10

Wygląda na to, że wywodzisz się z założenia, że ​​typ ()ma tylko jedną możliwą wartość, ()a zatem oczekujesz, że każde wywołanie funkcji zwracające wartość typu ()powinno być automatycznie zakładane, aby rzeczywiście wygenerowało tę wartość ().

Nie tak działa Haskell. Każdy typ ma jeszcze jedną wartość w Haskell, a mianowicie brak wartości, błąd lub tak zwane „dno”, zakodowane przez undefined. Tak więc faktycznie odbywa się ocena:

main = print (f 1)

jest odpowiednikiem języka podstawowego

main = _Case (f 1) _Of x -> print x   -- pseudocode illustration

lub nawet (*)

main = _Case (f 1) _Of x -> putStr "()"

i rdzenia _Casejest zmuszanie :

„Ocena %case[wyrażenia] wymusza ocenę testowanego wyrażenia („ badanego ”). Wartość badanego jest powiązana ze zmienną występującą po %ofsłowie kluczowym,…”.

Wartość jest zmuszona do osłabienia normalnej postaci głowy. Jest to część definicji języka.

Haskell nie jest deklaratywnym językiem programowania.


(*) print x = putStr (show x) i show () = "()", więc showpołączenie można całkowicie skompilować.

Wartość jest rzeczywiście znana z góry jako (), a nawet wartość show ()znana jest z góry jako "()". Nadal akceptowane semantyka Haskell żądać wartość (f 1)jest zmuszony do słabej głowy postaci normalnej, przed przystąpieniem do drukowania z góry wiadomo, że ciąg, "()".


edycja: Rozważ concat (repeat []). Powinien być [], czy powinien być nieskończoną pętlą?

Odpowiedź „deklaratywnego języka” na to jest najprawdopodobniej []. Odpowiedź Haskella brzmi: nieskończona pętla .

Lenistwo to „deklaratywne programowanie biednego człowieka”, ale nadal nie jest prawdziwe .

edit2 : print $ h (f 1) == _Case (h (f 1)) _Of () -> print ()i tylko hjest wymuszony, a nie f; i produkować swoją odpowiedź hnie ma nic na siłę, zgodnie z jego definicją h _ = ().

uwagi pożegnalne: lenistwo może mieć rację bytu, ale nie jest to jego definicja. Lenistwo jest tym, czym jest. Definiuje się, że wszystkie wartości są początkowo thunkami, które są zmuszane do WHNF zgodnie z pochodzącymi wymaganiami main. Jeśli pomaga uniknąć dna w określonym przypadku zgodnie z jego konkretnymi okolicznościami, to robi. Jeśli nie, nie. To wszystko.

Pomaga wdrożyć go samemu, w twoim ulubionym języku, aby poczuć to. Ale możemy również prześledzić ocenę dowolnego wyrażenia, ostrożnie nazywając wszystkie wartości pośrednie, gdy tylko powstają.


Idąc za raportem , mamy

f :: a -> ()
f = \_ -> (undefined :: ())

następnie

print (f 1)
 = print ((\ _ ->  undefined :: ()) 1)
 = print          (undefined :: ())
 = putStrLn (show (undefined :: ()))

i z

instance Show () where
    show :: () -> String
    show x = case x of () -> "()"

kontynuuje

 = putStrLn (case (undefined :: ()) of () -> "()")

Teraz sekcja 3.17.3 Formalna semantyka dopasowywania wzorców raportu mówi

Semantyka casewyrażeń [podano] na rycinach 3.1–3.3. Każda implementacja powinna zachowywać się tak, aby te tożsamości zawierały [...].

i przypadek (r), w schemacie 3.2 stany

(r)     case  of { K x1  xn -> e; _ -> e } =  
        where K is a data constructor of arity n 

() jest konstruktorem danych typu arity 0, więc jest taki sam jak

(r)     case  of { () -> e; _ -> e } =  

a zatem ogólny wynik oceny jest taki .

Will Ness
źródło
2
Podoba mi się twoje wyjaśnienie. To jest jasne i proste.
arrowd
@DanielWagner Właściwie miałem na myśli caserdzeń i ignorowałem ziejącą dziurę. :) Zredagowałem, aby wspomnieć o rdzeniu.
Czy Ness
1
Czy wymuszenie nie byłoby showwywołane przez print? Coś w stylushow x = case x of () -> "()"
user253751
1
Mam na myśli caserdzeń, a nie sam Haskell. Haskell jest tłumaczony na Core, który ma wymuszenie case, AFAIK. Masz rację, że casew Haskell samo w sobie nie narzuca. Mógłbym napisać coś w Schemacie lub ML (gdybym mógł napisać ML to znaczy) lub pseudokod.
Czy Ness
1
Autorytatywna odpowiedź na to wszystko jest prawdopodobnie gdzieś w Raporcie. Wiem tylko, że nie ma tu mowy o „optymalizacji”, a „wartość regularna” nie ma w tym kontekście znaczenia. Cokolwiek jest zmuszone, wymuszone. printzmusza tyle wydruków, ile potrzeba. nie patrzy na typ, typy są usuwane, usuwane, do czasu uruchomienia programu wybrana jest już poprawna procedura drukowania i kompilowana zgodnie z typem w czasie kompilacji; ten podprogram nadal będzie wymuszał wartość wejściową WHNF w czasie wykonywania, a jeśli nie zostanie zdefiniowany, spowoduje błąd.
Czy Ness