Dlaczego koncepcja leniwej oceny jest przydatna?

30

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?

akashchandrakar
źródło
10
W większości przypadków to po prostu nie ma znaczenia. Dla wszystkich innych możesz po prostu egzekwować surowość.
Cat Plus Plus
22
W przypadku czysto funkcjonalnych języków, takich jak haskell , nie trzeba się przejmować uruchomieniem kodu, ponieważ jest on wolny od efektów ubocznych.
maska ​​bitowa
21
Musisz przestać myśleć o „wykonywaniu kodu” i zacząć myśleć o „obliczaniu wyników”, ponieważ tak naprawdę chcesz w najbardziej interesujących problemach. Oczywiście programy zwykle również muszą w jakiś sposób wchodzić w interakcje ze środowiskiem, ale często można to zredukować do niewielkiej części kodu. Co do reszty, możesz pracować wyłącznie funkcjonalnie , a lenistwo może znacznie ułatwić rozumowanie.
leftaroundabout
6
Pytanie w tytule („Dlaczego warto korzystać z leniwej oceny?”) Bardzo różni się od pytania w treści („Jak korzystać z leniwej oceny?”). W przypadku tych pierwszych zobacz moją odpowiedź na to powiązane pytanie .
Daniel Wagner,
1
Przykład, kiedy lenistwo jest przydatne: w Haskell head . sortma O(n)złożoność z powodu lenistwa (nie O(n log n)). Zobacz Leniwa ocena i złożoność czasu .
Petr Pudlák

Odpowiedzi:

62

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.
sacundim
źródło
Proszę o więcej informacji lub przykład. Brzmi intrygująco.
Alex Nye,
1
@AlexNye: Artykuł Johna Hughesa zawiera więcej informacji. Pomimo tego, że jest to artykuł akademicki --- i dlatego bez wątpienia onieśmiela --- jest w rzeczywistości bardzo dostępny i czytelny. Gdyby nie jego długość, prawdopodobnie byłaby tu odpowiednia odpowiedź!
Tikhon Jelvis
Być może, aby zrozumieć tę odpowiedź, trzeba przeczytać artykuł Hughesa ... nie uczyniwszy tego, wciąż nie rozumiem, w jaki sposób i dlaczego lenistwo i modułowość są ze sobą powiązane.
stakx
@stakx Bez lepszego opisu nie wydają się być powiązane, chyba że przez przypadek. Zaletą lenistwa w tym przykładzie jest to, że leniwy generator jest w stanie generować wszystkie możliwe stany gry, ale nie marnuje czasu / pamięci, ponieważ tylko te, które się zdarzają, zostaną zużyte. Generator można oddzielić od konsumenta, nie będąc leniwym generatorem, i możliwe jest (choć trudniejsze) być leniwym bez oddzielenia od konsumenta.
Izkata
@Iztaka: „Generator można oddzielić od konsumenta, nie będąc leniwym generatorem, i można (choć trudniej) być leniwym bez oddzielenia od konsumenta”. Zauważ, że kiedy wybierzesz tę drogę, możesz skończyć z ** nadmiernie wyspecjalizowanym generatorem ** - generator został napisany w celu zoptymalizowania jednego konsumenta, a gdy zostanie ponownie użyty dla innych, nie będzie optymalny. Typowym przykładem są mapujące obiekty relacyjne, które pobierają i konstruują wykres całego obiektu tylko dlatego, że chcesz mieć jeden ciąg z obiektu głównego. Lenistwo unika wielu takich przypadków (ale nie wszystkich).
święta
32

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.

sepp2k
źródło
15
Dlatego tylko języki z „wymuszoną czystością”, takie jak Haskell, domyślnie wszędzie obsługują lenistwo. Języki „promowanej czystości”, takie jak Scala, wymagają od programisty, aby wyraźnie powiedział, gdzie chcą lenistwa, i to od programisty zależy, czy lenistwo nie spowoduje problemów. Język, który domyślnie miał lenistwo i nie wyśledził efektów ubocznych, rzeczywiście byłby trudny do zaprogramowania.
Ben
1
z pewnością monady inne niż IO mogą również powodować działania niepożądane
jk.
1
@jk Tylko IO może powodować zewnętrzne skutki uboczne.
dave4420
@ dave4420 tak, ale to nie to, co mówi ta odpowiedź
jk.
1
@jk W Haskell faktycznie nie. Żadna monada oprócz IO (lub tych opartych na IO) nie ma skutków ubocznych. A to tylko dlatego, że kompilator traktuje IO inaczej. Uważa IO za „Immutable Off”. Monady to tylko (sprytny) sposób na zapewnienie określonego polecenia wykonania (więc plik zostanie usunięty dopiero po wpisaniu przez użytkownika „tak”).
scarfridge
22

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)

samthebrand
źródło
Słuszna uwaga. Na przykład Collection2.filter()(podobnie jak inne metody z tej klasy) w zasadzie implementuje się leniwą ocenę: wynik „wygląda jak” zwykły Collection, ale kolejność wykonywania może być nieintuicyjna (lub przynajmniej nieoczywista). Jest też yieldw Pythonie (i podobnej funkcji w języku C #, którego nie pamiętam nazwy), który jest jeszcze bliższy do obsługi leniwej oceny niż normalny Iterator.
Joachim Sauer
@JachachSauer w C # zwrot z wydajności, lub oczywiście możesz użyć prebuild linq oprerators, z których około połowa jest leniwa
jk.
+1: Za wspomnienie o iteratorach w języku imperatywnym / obiektowym. Użyłem podobnego rozwiązania do implementacji strumieni i funkcji strumieniowych w Javie. Za pomocą iteratorów mogłem mieć funkcje takie jak take (n), dropWhile () na strumieniu wejściowym o nieznanej długości.
Giorgio
13

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.

sergserg
źródło
1
to naprawdę kiepskie wytłumaczenie IMHO. Niestety nie mam wystarczającej liczby przedstawicieli na tej konkretnej stronie SE, aby zagłosować. Rzeczywistym punktem leniwej oceny jest to, że żaden z tych wyników nie jest generowany, dopóki coś innego nie będzie gotowe do ich wykorzystania.
Alnitak
Moja opublikowana odpowiedź mówi dokładnie to samo, co twój komentarz.
sergserg,
To bardzo uprzejmy procesor programu.
Julian
9

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.

Caleb
źródło
5

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.

Philip JF
źródło
2

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.

ddyer
źródło
1

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.

permeakra
źródło