Jakie są punkty ścisłości Haskella?

90

Wszyscy wiemy (lub powinniśmy wiedzieć), że Haskell jest domyślnie leniwy. Nic nie jest oceniane, dopóki nie musi zostać ocenione. Kiedy więc trzeba coś ocenić? Są punkty, w których Haskell musi być surowy. Nazywam te „punktami ścisłości”, chociaż ten konkretny termin nie jest tak rozpowszechniony, jak myślałem. Jeśli chodzi o mnie:

Redukcja (lub ocena) w Haskell występuje tylko w punktach ścisłości.

A więc pytanie brzmi: czym dokładnie są punkty ścisłości Haskella? Moja intuicja mówi, że main, seq/ wzory bang, pasujące do wzorca, a także wszelkie IOdziałania wykonywane poprzez mainto główne punkty surowość, ale ja naprawdę nie wiem dlaczego ja o tym wiedzieć.

(Jeśli nie są nazywane „punktami ścisłości”, jak się je nazywa?)

Wyobrażam sobie, że dobra odpowiedź będzie obejmować dyskusję na temat WHNF i tak dalej. Wyobrażam sobie również, że może to dotyczyć rachunku lambda.


Edycja: dodatkowe przemyślenia na temat tego pytania.

Kiedy zastanawiałem się nad tym pytaniem, myślę, że byłoby jaśniejsze dodanie czegoś do definicji punktu ścisłości. Punkty ścisłości mogą mieć różne konteksty i różną głębokość (lub rygorystyczność). Wracając do mojej definicji, że „redukcja Haskella występuje tylko w punktach ścisłości”, dodajmy do tej definicji następującą klauzulę: „punkt ścisłości jest wyzwalany tylko wtedy, gdy otaczający go kontekst jest oceniany lub redukowany”.

Pozwól, że spróbuję zacząć od odpowiedzi, jakiej chcę. mainjest punktem ścisłości. Jest specjalnie wyznaczony jako główny punkt ścisłości swojego kontekstu: program. Kiedy program ( mainkontekst) jest oceniany, uaktywniany jest punkt ścisłości main. Głębokość maina jest maksymalna: musi być w pełni oceniona. Main zwykle składa się z działań IO, które są również punktami ścisłości, których kontekst jest main.

Teraz spróbuj: omówić seqi dopasować wzorce w tych terminach. Wyjaśnij niuanse stosowania funkcji: jak to jest ścisłe? Jak to nie jest? O co chodzi deepseq? leti caseoświadczenia? unsafePerformIO? Debug.Trace? Definicje najwyższego poziomu? Ścisłe typy danych? Wzory Bang? Itd. Ile z tych pozycji można opisać za pomocą samego dopasowania sekwencji lub wzorca?

Dan Burton
źródło
10
Twoja intuicyjna lista prawdopodobnie nie jest zbyt ortogonalna. Podejrzewam, że seqi dopasowanie wzorców jest wystarczające, a reszta jest zdefiniowana w tych kategoriach. Myślę, że dopasowanie wzorców zapewnia IOna przykład ścisłość kręgosłupa działań.
CA McCann
Prymitywy, takie jak +wbudowane typy liczbowe, również wymuszają ścisłość i zakładam, że to samo dotyczy czystych wywołań FFI.
hammar
4
Wydaje się, że są tu pomieszane dwa pojęcia. Dopasowywanie wzorców oraz wzorce seq i bang to sposoby, w jakie wyrażenie może stać się ścisłe w swoich wyrażeniach podrzędnych - to znaczy, jeśli wyliczane jest najwyższe wyrażenie, tak samo jest z wyrażeniem podrzędnym. Z drugiej strony ewaluacja rozpoczyna się od głównych działań realizujących zamówienia publiczne . To są różne rzeczy i umieszczenie ich na tej samej liście jest rodzajem błędu.
Chris Smith
@ChrisSmith Nie próbuję mylić tych dwóch różnych przypadków; jeśli cokolwiek, proszę o dalsze wyjaśnienia dotyczące ich interakcji. Surowość jakoś się zdarza i oba przypadki są ważnymi, choć różniącymi się częściami ścisłości „dziejącej się”. (i @ monadic: ಠ_ಠ)
Dan Burton,
Jeśli chcesz / potrzebujesz miejsca na omówienie aspektów tego pytania, bez próby pełnej odpowiedzi, pozwól mi zasugerować wykorzystanie komentarzy na moim / r / haskell postu do tego pytania
Dan Burton

Odpowiedzi:

46

Warto zacząć od zrozumienia tego artykułu: A Natural Semantics for Lazy Evalution (Launchbury). Dzięki temu dowiesz się, kiedy wyrażenia są oceniane dla małego języka podobnego do Core GHC. Pozostaje pytanie, jak zmapować cały Haskell do Core, a większość tego tłumaczenia jest podana w samym raporcie Haskella. W GHC nazywamy ten proces „desugeringiem”, ponieważ usuwa cukier syntaktyczny.

Cóż, to nie wszystko, ponieważ GHC zawiera całą gamę optymalizacji między desugeringiem a generowaniem kodu, a wiele z tych transformacji zmieni układ Core, aby rzeczy były oceniane w różnym czasie (w szczególności analiza ścisłości spowoduje, że rzeczy zostaną ocenione wcześniej). Aby naprawdę zrozumieć, w jaki sposób Twój program będzie oceniany, musisz spojrzeć na rdzeń wyprodukowany przez GHC.

Być może ta odpowiedź wydaje ci się nieco abstrakcyjna (nie wspomniałem konkretnie o wzorach huku lub sekwencji), ale poprosiłeś o coś precyzyjnego i to jest najlepsze, co możemy zrobić.

Simon Marlow
źródło
18
Zawsze uważałem to za zabawne, że w tym, co GHC nazywa „desugaring”, usuwany cukier składniowy obejmuje rzeczywistą składnię samego języka Haskell ... co oznacza, że ​​mogłoby się wydawać, że GHC jest w rzeczywistości optymalizującym kompilatorem dla GHC Język podstawowy, który, nawiasem mówiąc, zawiera również bardzo rozbudowany interfejs do tłumaczenia Haskell na Core. :]
CA McCann
Systemy czcionek nie są jednak precyzyjne ... szczególnie, ale nie tylko w odniesieniu do tłumaczenia typeklas na jawne słowniki, o czym pamiętam. A wszystkie najnowsze rzeczy dotyczące TF / GADT, jak rozumiem, jeszcze bardziej poszerzyły tę lukę.
sclv
1
GCC też nie optymalizuje C: gcc.gnu.org/onlinedocs/gccint/Passes.html#Passes
György Andrasek
20

Prawdopodobnie przeformułowałbym to pytanie jako: W jakich okolicznościach Haskell oceni wyrażenie? (Być może przypisz „słabą normalną formę głowy”).

W pierwszym przybliżeniu możemy to określić następująco:

  • Wykonywanie działań we / wy oceni wszystkie wyrażenia, których „potrzebują”. (Więc musisz wiedzieć, czy akcja IO jest wykonywana, np. Jego nazwa to main, czy jest wywoływana z main ORAZ musisz wiedzieć, czego potrzebuje akcja).
  • Wyrażenie, które jest oceniane (hej, to definicja rekurencyjna!) Będzie oceniać wszystkie wyrażenia, których potrzebuje.

Z Twojej intuicyjnej listy akcje główne i IO należą do pierwszej kategorii, a dopasowywanie sekwencji i wzorców do drugiej kategorii. Ale myślę, że pierwsza kategoria jest bardziej zgodna z twoją ideą „punktu ścisłości”, ponieważ tak naprawdę sprawiamy, że ocena w Haskell staje się obserwowalnymi efektami dla użytkowników.

Podanie wszystkich szczegółów jest dużym zadaniem, ponieważ Haskell jest dużym językiem. Jest to również dość subtelne, ponieważ Concurrent Haskell może oceniać rzeczy spekulatywnie, nawet jeśli ostatecznie nie wykorzystujemy wyniku: jest to trzeci rodzaj rzeczy, które powodują ocenę. Druga kategoria jest dość dobrze zbadana: chcesz przyjrzeć się surowości związanych z nią funkcji. Pierwsza kategoria również może być uważana za rodzaj „surowości”, chociaż jest to trochę podejrzane, ponieważ evaluate xi seq x $ return ()są w rzeczywistości różne! Możesz traktować to właściwie, jeśli nadasz jakąś semantykę monadzie IO (jawne przekazanie RealWorld#tokenu działa w prostych przypadkach), ale nie wiem, czy ogólnie istnieje nazwa dla tego rodzaju warstwowej analizy ścisłości.

Edward Z. Yang
źródło
17

C ma koncepcję punktów sekwencji , które są gwarancją dla określonych operacji, że jeden operand zostanie oceniony przed drugim. Myślę, że jest to najbliższa istniejąca koncepcja, ale zasadniczo równoważny termin punkt ścisłości (lub być może punkt siły ) jest bardziej zgodny z myśleniem Haskella.

W praktyce Haskell nie jest językiem czysto leniwym: na przykład dopasowywanie wzorców jest zwykle ścisłe (więc próba dopasowania wzorca wymusza ocenę na co najmniej na tyle daleko, aby zaakceptować lub odrzucić dopasowanie.

Programiści mogą również użyć operacji seqpierwotnej, aby wymusić na wyrażeniu ocenę, niezależnie od tego, czy wynik zostanie kiedykolwiek użyty.

$!jest zdefiniowany w kategoriach seq.

- Leniwy a nieścisły .

Więc twoje myślenie o !/ $!i seqjest zasadniczo słuszne, ale dopasowywanie wzorców podlega subtelniejszym regułom. Oczywiście zawsze możesz ~wymusić leniwe dopasowywanie wzorców. Ciekawy punkt z tego samego artykułu:

Analizator ścisłości wyszukuje również przypadki, w których wyrażenia podrzędne są zawsze wymagane przez wyrażenie zewnętrzne, i konwertuje je na gorliwą ocenę. Może to zrobić, ponieważ semantyka (w kategoriach „dołu”) się nie zmienia.

Kontynuujmy w dół króliczej nory i spójrzmy na dokumentację pod kątem optymalizacji wykonanych przez GHC:

Analiza ścisłości to proces, w ramach którego GHC próbuje określić w czasie kompilacji, które dane z pewnością będą „zawsze potrzebne”. GHC może następnie zbudować kod, aby po prostu obliczyć takie dane, zamiast normalnego (wyższego narzutu) procesu przechowywania obliczeń i wykonywania ich później.

- Optymalizacje GHC: Analiza ścisłości .

Innymi słowy, ścisły kod może zostać wygenerowany w dowolnym miejscu jako optymalizacja, ponieważ tworzenie thunks jest niepotrzebnie kosztowne, gdy dane będą zawsze potrzebne (i / lub mogą być użyte tylko raz).

… Nie można już przeprowadzić oceny wartości; mówi się, że jest w normalnej formie . Jeśli jesteśmy na którymkolwiek z pośrednich kroków, tak że wykonaliśmy przynajmniej część oceny wartości, jest ona w postaci normalnej głowy słabej (WHNF). (Istnieje również „normalna forma głowy”, ale nie jest używana w Haskell). Pełne oszacowanie czegoś w WHNF redukuje to do czegoś w normalnej formie…

- Wikibooks Haskell: Lenistwo

(Termin jest w normalnej postaci głowy, jeśli nie ma beta-redex w pozycji head 1. Redex jest head redex, jeśli jest poprzedzony tylko przez wyrażanie lambda abstrakcji innych niż redexes 2. ) Więc kiedy zaczynasz wymuszać thunk, pracujesz w WHNF; kiedy nie ma już więcej rzeczy do wymuszenia, jesteś w normalnej formie. Kolejny interesujący punkt:

… Gdybyśmy w którymś momencie musieli, powiedzmy, wydrukować z użytkownika, musielibyśmy to w pełni ocenić…

Co naturalnie oznacza, że rzeczywiście, każda IOczynność wykonana z main dokłada oceny siły, co powinno być oczywiste, biorąc pod uwagę, że programy Haskell zrobić w rzeczywistości, robić różne rzeczy. Wszystko, co musi przejść przez sekwencję zdefiniowaną w, mainmusi mieć normalną formę i dlatego podlega ścisłej ocenie.

Jednak CA McCann dobrze to zrozumiał w komentarzach: jedyną rzeczą, która jest wyjątkowa, mainjest to, że mainjest zdefiniowana jako wyjątkowa; dopasowanie wzorca w konstruktorze jest wystarczające, aby zapewnić sekwencję narzuconą przez IOmonadę. Tylko pod tym względem seqi dopasowywanie wzorców jest fundamentalne.

Jon Purdy
źródło
4
Faktycznie stwierdzenie „jeśli w którymś momencie musielibyśmy, powiedzmy, wydrukować z użytkownika użytkownikowi, musielibyśmy to w pełni ocenić” nie jest całkowicie poprawne. Jest tak ścisły, jak Showinstancja drukowanej wartości.
nominolo
10

Haskell to AFAIK nie jest czysto leniwym językiem, ale raczej językiem nieostrym. Oznacza to, że niekoniecznie ocenia warunki w ostatniej możliwej chwili.

Dobre źródło modelu „lenistwa” firmy Haskell można znaleźć tutaj: http://en.wikibooks.org/wiki/Haskell/Laziness

Zasadniczo ważne jest, aby zrozumieć różnicę między formą WHNF a typem normalnym ze słabym nagłówkiem.

Rozumiem, że haskell przeciąga obliczenia wstecz w porównaniu z językami imperatywnymi. Oznacza to, że przy braku wzorców „seq” i bang ostatecznie będzie to jakiś efekt uboczny, który wymusi ocenę daru, który może z kolei spowodować wcześniejsze oceny (prawdziwe lenistwo).

Ponieważ doprowadziłoby to do okropnego wycieku przestrzeni, kompilator wymyśla wtedy, jak i kiedy oceniać błędy z wyprzedzeniem, aby zaoszczędzić miejsce. Programista może wtedy wesprzeć ten proces, dodając adnotacje ścisłości (en.wikibooks.org/wiki/Haskell/Strictness, www.haskell.org/haskellwiki/Performance/Strictness), aby jeszcze bardziej zmniejszyć wykorzystanie miejsca w postaci zagnieżdżonych ciągów.

Nie jestem ekspertem w zakresie semantyki operacyjnej haskell, więc po prostu zostawię łącze jako zasób.

Więcej zasobów:

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

płyn
źródło
6

Leniwy nie oznacza nic nie rób. Ilekroć wzorzec programu pasuje do casewyrażenia, ocenia coś - i tak wystarczy. W przeciwnym razie nie może dowiedzieć się, którego RHS użyć. Nie widzisz w kodzie wyrażeń wielkości liter? Nie martw się, kompilator tłumaczy twój kod do okrojonej formy Haskell, gdzie trudno ich uniknąć.

Dla początkującego podstawową zasadą letjest leniwy, casemniej leniwy.

T_S_
źródło
2
Zauważ, że chociaż casezawsze wymusza ocenę w GHC Core, nie robi tego w zwykłym Haskellu. Na przykład spróbuj case undefined of _ -> 42.
hammar
2
casew GHC Core ocenia swój argument do WHNF, podczas gdy casew Haskell ocenia swój argument tak często, jak potrzeba, aby wybrać odpowiednią gałąź. W przykładzie case 1:undefined of x:y:z -> 42Hammara to wcale nie jest, ale w przypadku wartości jest głębsze niż WHNF.
Max
A także case something of (y,x) -> (x,y)nie musi w ogóle oceniać something. Dotyczy to wszystkich typów produktów.
Ingo
@Ingo - to nieprawda. somethingmusiałyby zostać ocenione w WHNF, aby dotrzeć do konstruktora krotki.
John L
John - dlaczego? Wiemy, że musi to być krotka, więc po co ją oceniać? Wystarczy, że x i y są zobowiązane do kodu, który ocenia krotkę i wyodrębnia odpowiednią szczelinę, jeśli one same kiedykolwiek będą potrzebne.
Ingo,
4

Nie jest to pełna odpowiedź mająca na celu karmę, ale tylko element układanki - w zakresie, w jakim dotyczy to semantyki, należy pamiętać, że istnieje wiele strategii oceny, które zapewniają tę samą semantykę. Dobrym przykładem tutaj - a projekt również mówi o tym, jak zwykle myślimy o semantyce Haskella - był projekt Eager Haskell, który radykalnie zmienił strategie oceny przy zachowaniu tej samej semantyki: http://csg.csail.mit.edu/ pubs / haskell.html

sclv
źródło
2

Kompilator Glasgow Haskell tłumaczy twój kod na język podobny do rachunku Lambda zwany core . W tym języku coś zostanie ocenione, za każdym razem, gdy dopasujesz to do wzorca przez case-statement. Tak więc, jeśli wywoływana jest funkcja, zostanie oszacowany najbardziej zewnętrzny konstruktor i tylko ona (jeśli nie ma pól wymuszonych). Wszystko inne jest w puszce. (Thunks są wprowadzane przez letwiązania).

Oczywiście nie jest to dokładnie to, co dzieje się w prawdziwym języku. Kompilator konwertuje Haskell na Core w bardzo wyrafinowany sposób, czyniąc tyle rzeczy, ile może być leniwych, i wszystko, co jest zawsze potrzebne, leniwe. Ponadto istnieją wartości i krotki, które nie są opakowane, które są zawsze ścisłe.

Jeśli spróbujesz oszacować funkcję ręcznie, możesz po prostu pomyśleć:

  • Spróbuj ocenić najbardziej zewnętrzny konstruktor zwrotu.
  • Jeśli do uzyskania wyniku potrzebne jest coś innego (ale tylko wtedy, gdy jest to naprawdę potrzebne), również zostanie ocenione. Kolejność nie ma znaczenia.
  • W przypadku IO musisz ocenić wyniki wszystkich stwierdzeń od pierwszego do ostatniego w tym. Jest to trochę bardziej skomplikowane, ponieważ monada IO wykonuje pewne sztuczki, aby wymusić ocenę w określonej kolejności.
fuz
źródło