Dlaczego koncepcja leniwej oceny jest przydatna?

Wydaje się, że leniwa ocena wyrażeń może spowodować utratę kontroli przez programistę nad kolejnością wykonywania kodu. Mam problem ze zrozumieniem, dlaczego programista może to zaakceptować.

Jak można wykorzystać ten paradygmat do budowy przewidywalnego oprogramowania, które działa zgodnie z przeznaczeniem, skoro nie mamy gwarancji, kiedy i gdzie wyrażenie zostanie ocenione?

Wiele odpowiedzi dotyczy rzeczy takich jak nieskończone listy i wzrost wydajności z nieocenionych części obliczeń, ale brakuje w tym większej motywacji do lenistwa: modułowości .

Klasyczny argument znajduje się w cytowanym artykule Johna Hughesa pt. „Dlaczego funkcjonalne programowanie ma znaczenie” (link PDF) . Kluczowym przykładem w tym artykule (Część 5) jest gra Tic-Tac-Toe przy użyciu algorytmu wyszukiwania alfa-beta. Kluczową kwestią jest (s. 9):

[Leniwa ocena] pozwala na modularyzację programu jako generatora, który konstruuje dużą liczbę możliwych odpowiedzi, i selektora, który wybiera odpowiedni.

Program Kółko i krzyżyk można napisać jako funkcję, która generuje całe drzewo gry, zaczynając od określonej pozycji, i jako osobną funkcję, która je pochłania. W czasie wykonywania nie generuje to samo w sobie całego drzewa gry, tylko te części, których konsument tak naprawdę potrzebuje. Możemy zmienić kolejność i kombinację, w których wytwarzane są alternatywy, zmieniając konsumenta; w ogóle nie trzeba zmieniać generatora.

W gorliwym języku nie możesz tego napisać w ten sposób, ponieważ prawdopodobnie spędziłbyś zbyt dużo czasu i pamięci na wygenerowaniu drzewa. Więc kończysz albo:

1. Łączenie wytwarzania i zużycia w tę samą funkcję;
2. Pisanie producenta, który działa optymalnie tylko dla niektórych konsumentów;
3. Wdrażanie własnej wersji lenistwa.

Jak można wykorzystać ten paradygmat do budowy przewidywalnego oprogramowania, które działa zgodnie z przeznaczeniem, skoro nie mamy gwarancji, kiedy i gdzie wyrażenie zostanie ocenione?

Gdy wyrażenie jest wolne od skutków ubocznych, kolejność, w jakiej wyrażenia są oceniane, nie wpływa na ich wartość, więc kolejność nie wpływa na zachowanie programu. Zachowanie jest więc całkowicie przewidywalne.

Teraz skutki uboczne to inna sprawa. Gdyby działania niepożądane mogły wystąpić w dowolnej kolejności, zachowanie programu byłoby rzeczywiście nieprzewidywalne. Ale tak nie jest. Leniwe języki, takie jak Haskell, wymagają odniesienia do przejrzystości, tzn. Upewnienia się, że kolejność, w jakiej wyrażenia są oceniane, nigdy nie wpłynie na ich wynik. W Haskell jest to osiągane poprzez zmuszanie wszystkich operacji z widocznymi dla użytkownika efektami ubocznymi do wystąpienia wewnątrz monady IO. Dzięki temu wszystkie działania niepożądane wystąpią dokładnie w oczekiwanej kolejności.

Jeśli znasz bazy danych, bardzo częstym sposobem przetwarzania danych jest:

• Zadaj pytanie jak select * from foobar
• Gdy jest więcej danych, wykonaj: pobierz następny wiersz wyników i przetworz go

Nie kontrolujesz, w jaki sposób generowany jest wynik i w jaki sposób (indeksy? Pełne skanowanie tabeli?) Lub kiedy (czy wszystkie dane powinny być generowane jednocześnie, czy narastająco, gdy zostaniesz o to poproszony?). Wiesz tylko: jeśli jest więcej danych, otrzymasz je, gdy o to poprosisz.

Leniwa ocena jest bardzo zbliżona do tej samej rzeczy. Załóżmy, że masz nieskończoną listę zdefiniowaną jako np. sekwencja Fibonacciego - jeśli potrzebujesz pięciu liczb, otrzymujesz pięć liczb; jeśli potrzebujesz 1000, dostajesz 1000. Sztuczka polega na tym, że środowisko wykonawcze wie, co zapewnić gdzie i kiedy. Jest bardzo, bardzo przydatny.

(Programiści Java mogą emulować to zachowanie za pomocą Iteratorów - inne języki mogą mieć coś podobnego)

Zastanów się, czy nie poprosić bazy danych o listę pierwszych 2000 użytkowników, których nazwy zaczynają się na „Ab” i są starsze niż 20 lat. Oni też muszą być mężczyznami.

Oto mały schemat.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

Jak widać po tej strasznej, okropnej interakcji, „baza danych” właściwie nic nie robi, dopóki nie będzie gotowa na wszystkie warunki. Leniwie ładuje wyniki na każdym kroku i za każdym razem stosuje nowe warunki.

W przeciwieństwie do pozyskiwania pierwszych 2000 użytkowników, zwracanie ich, filtrowanie ich pod kątem „Ab”, zwracanie ich, filtrowanie ich przez ponad 20, zwracanie ich oraz filtrowanie pod kątem mężczyzn i ich wreszcie zwracanie.

Leniwe ładowanie w pigułce.

Leniwa ocena wyrażeń spowoduje, że projektant danego fragmentu kodu straci kontrolę nad sekwencją wykonywania kodu.

Projektant nie powinien dbać o kolejność, w jakiej wyrażenia są oceniane, pod warunkiem, że wynik będzie taki sam. Odraczając ocenę, można uniknąć całkowitej oceny niektórych wyrażeń, co oszczędza czas.

Ten sam pomysł można zaobserwować w pracy na niższym poziomie: wiele mikroprocesorów jest w stanie wykonywać instrukcje poza kolejnością, co pozwala im efektywniej korzystać z różnych jednostek wykonawczych. Kluczem jest to, że patrzą na zależności między instrukcjami i unikają zmiany kolejności tam, gdzie mogłoby to zmienić wynik.

Istnieje kilka argumentów za leniwą oceną, które moim zdaniem są przekonujące

1. Modułowość z oceną leniwe można złamać kod na części. Załóżmy na przykład, że masz problem ze „znalezieniem pierwszych dziesięciu odwrotności elementów na liście, tak aby wzajemności były mniejsze niż 1.” W czymś takim jak Haskell możesz pisać

   take 10 . filter (<1) . map (1/)
   

   ale jest to po prostu niepoprawne w ścisłym języku, ponieważ jeśli go [2,3,4,5,6,7,8,9,10,11,12,0]podasz, będziesz dzielić przez zero. Zobacz odpowiedź sacundim, aby dowiedzieć się, dlaczego jest to niesamowite w praktyce

2. Więcej rzeczy działa Ściśle (zamierzone) więcej programów kończy się bez ścisłej oceny niż przy ścisłej ocenie. Jeśli twój program zakończy się „chętną” strategią oceny, zakończy się „leniwą”, ale przeciwieństwo nie jest prawdą. Dostajesz rzeczy takie jak nieskończone struktury danych (które są naprawdę całkiem fajne) jako konkretne przykłady tego zjawiska. Więcej programów działa w leniwych językach.

3. Optymalność Ocena według zapotrzebowania jest asymptotycznie optymalna pod względem czasu. Chociaż główne leniwe języki (którymi w zasadzie są Haskell i Haskell) nie obiecują wezwania na żądanie, możesz mniej więcej oczekiwać optymalnego modelu kosztów. Analizatory dokładności (i ocena spekulacyjna) utrzymują koszty ogólne w praktyce. Przestrzeń kosmiczna jest sprawą bardziej skomplikowaną.

4. Wymuszanie czystości za pomocą leniwej oceny sprawia, że ​​radzenie sobie z efektami ubocznymi w niezdyscyplinowany sposób jest całkowitym bólem, ponieważ, jak to ujmujesz, programista traci kontrolę. To coś dobrego. Przezroczystość referencyjna znacznie ułatwia programowanie, refaktoryzację i wnioskowanie o programach. Surowe języki nieuchronnie uciekają od presji posiadania nieczystych kawałków - coś, czemu Haskell i Clean pięknie się oparli. Nie oznacza to, że skutki uboczne są zawsze złe, ale kontrolowanie ich jest tak przydatne, że sam ten powód wystarcza do używania leniwych języków.

Załóżmy, że masz wiele drogich obliczeń w ofercie, ale nie wiesz, które z nich będą faktycznie potrzebne lub w jakiej kolejności. Możesz dodać skomplikowany protokół Mother-May-i, aby zmusić konsumenta do ustalenia, co jest dostępne, i uruchomić obliczenia, które nie zostały jeszcze wykonane. Lub możesz po prostu zapewnić interfejs, który działa tak, jakby wszystkie obliczenia zostały wykonane.

Załóżmy również, że masz nieskończony wynik. Na przykład zestaw wszystkich liczb pierwszych. Oczywiste jest, że nie można obliczyć zestawu z góry, więc każda operacja w dziedzinie liczb pierwszych musi być leniwa.

z leniwą oceną nie tracisz kontroli nad wykonywaniem kodu, jest to nadal absolutnie deterministyczne. Trudno się jednak z tym przyzwyczaić.

leniwa ocena jest przydatna, ponieważ jest to sposób na ograniczenie lambda, który zakończy się w niektórych przypadkach, w których chętna ocena zakończy się niepowodzeniem, ale nie odwrotnie. Obejmuje to 1) gdy trzeba połączyć się z wynikiem obliczeń przed faktycznym wykonaniem obliczeń, na przykład, gdy konstruujesz cykliczną strukturę wykresu, ale chcesz to zrobić w stylu funkcjonalnym 2), gdy definiujesz nieskończoną strukturę danych, ale funkcja ta przesyła strukturę używać tylko części struktury danych.