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?
functional-programming
haskell
akashchandrakar
źródło
źródło
head . sort
maO(n)
złożoność z powodu lenistwa (nieO(n log n)
). Zobacz Leniwa ocena i złożoność czasu .Odpowiedzi:
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):
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:
źródło
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.
źródło
Jeśli znasz bazy danych, bardzo częstym sposobem przetwarzania danych jest:
select * from foobar
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)
źródło
Collection2.filter()
(podobnie jak inne metody z tej klasy) w zasadzie implementuje się leniwą ocenę: wynik „wygląda jak” zwykłyCollection
, ale kolejność wykonywania może być nieintuicyjna (lub przynajmniej nieoczywista). Jest teżyield
w 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.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.
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.
źródło
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.
źródło
Istnieje kilka argumentów za leniwą oceną, które moim zdaniem są przekonujące
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ć
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 praktyceWię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.
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ą.
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.
źródło
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.
źródło
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.
źródło