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

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?

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

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.

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.

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

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.

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

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.