Jak zaimplementowane są leniwe sekwencje w Clojure?

Wiem, że leniwe sekwencje oceniają tylko te elementy w sekwencji, o które są proszone, jak to robi?

Myślę, że wcześniej zamieszczone odpowiedzi już dobrze wyjaśniają tę część. Dodam tylko, że "wymuszanie" leniwej sekwencji jest niejawne-paren-free! :- ) -- wywołanie funkcji; być może ten sposób myślenia o tym sprawi, że niektóre rzeczy będą jaśniejsze. Zauważ również, że wymuszanie sekwencji leniwej wiąże się z ukrytą mutacją - wymuszenie musi wytworzyć wartość, zapisać ją w pamięci podręcznej (mutacja!) i wyrzucić jego kod wykonywalny, który nie będzie już potrzebny (znowu mutacja!).

Wiem, że leniwe sekwencje oceniają tylko te elementy w sekwencji, o które są proszone, jak to robi?

Co sprawia, że leniwe sekwencje są tak wydajne, że nie zużywają zbyt dużo stacka?

Jakie zasoby zużywają leniwe sekwencje, aby robić to, co robi?

Nie zużywają stosu, ponieważ zużywają zamiast tego kupa. Leniwa sekwencja jest strukturą danych, żyjącą na stercie, która zawiera mały bit kodu wykonywalnego, który może być wywołany, aby wytworzyć więcej struktury danych, jeśli / kiedy jest to wymagane.

Jak to możliwe, że można zawinąć rekurencyjne wywołania w leniwą sekwencję i nie uzyskać stos nad przepływem dla dużych obliczeń?

Po pierwsze, jak wspomniał dbyrne, można bardzo dobrze uzyskać so podczas pracy z leniwymi sekwencjami, jeśli same thunksy muszą wykonać kod z bardzo głęboko zagnieżdżoną strukturą połączeń.

Jednak w pewnym sensie możesz używać leniwych seqs zamiast rekurencji ogonowej, a do tego stopnia, że to działa dla ciebie, możesz powiedzieć, że pomagają one w unikaniu SOs. W rzeczywistości, co dość istotne, funkcje tworzące leniwe sekwencje nie powinny być rekurencyjne ogonem; zachowanie przestrzeni stosu z leniwymi producentami seq wynika z wyżej wymienionego transferu stosu - > sterty i wszelkie próby ich zapisu w sposób rekurencyjny ogonem będą tylko niszczyć rzeczy.

Kluczowy wgląd jest taki, że leniwa sekwencja jest obiektem, który po pierwszym utworzeniu nie zawiera żadnych elementów( jak zawsze robi to ścisła Sekwencja); gdy funkcja zwraca leniwą sekwencję, tylko ten "leniwy obiekt sekwencji" jest zwracany do wywołującego, zanim nastąpi jakiekolwiek wymuszenie. W ten sposób ramka stosu użyta przez wywołanie, które zwróciło leniwą sekwencję, jest zrywana przed jakimkolwiek wymuszaniem. Spójrzmy na przykładową funkcję producenta:

(defn foo-producer [] ; not tail recursive...
  (lazy-seq
    (cons :foo        ; because it returns the value of the cons call...
           (foo-producer)))) ; which wraps a non-tail self-call

To działa, ponieważ lazy-seq zwraca natychmiast , zatem (cons :foo (foo-producer)) również zwraca natychmiast, a ramka stosu użyta przez zewnętrzne wywołanie foo-producer jest natychmiast wyrzucana. Wewnętrzne wywołanie {[4] } jest ukryte w rest części sekwencji, która jest thunk; jeśli / kiedy thunk jest wymuszony, na krótko użyje własnej ramki na stosie, ale następnie natychmiast powróci, jak opisano powyżej itp.

Chunking (wspomniany przez dbyrne) zmienia to zdjęcie bardzo nieznacznie, ponieważ większa liczba elements gets produced at every step, but the principle remain the same: every step used up some stack when the appropriate elements of the lazy seq are being produced, then that stack is recurrived before {32]} more forcing ma miejsce.

W jakich scenariuszach leniwe sekwencje są nieefektywne?

W jakich scenariuszach leniwe sekwencje są najbardziej efektywne?

(->> (lazy-seq-producer)               ; possibly (->> (range)
     (a-lazy-seq-transformer-function) ;               (filter even?)
     (another-transformer-function))   ;               (map inc))

Robienie tego w ścisły sposób i tak przydzieliłoby mnóstwo sterty, ponieważ musiałbyś trzymać pośrednie wyniki wokół, aby przejść do następnego etapu przetwarzania. Co więcej, musisz zachować całość wokół, co jest właściwie niemożliwe w przypadku (range) -- nieskończonej sekwencji! -- a kiedy jest to możliwe, jest to zwykle nieefektywne.

Oryginalnie, leniwe sekwencje w Clojure były oceniane po kolei według potrzeb. Chunked sekwencje zostały dodane w Clojure 1.1 w celu poprawy wydajności. Zamiast oceny element po elemencie, "kawałki" 32 elementów są oceniane na raz. Zmniejsza to koszty, które ponosi leniwa ocena. Pozwala również clojure korzystać z bazowych struktur danych. Na przykład, {[0] } jest zaimplementowane jako drzewo 32 tablic elementów. Oznacza to, że aby uzyskać dostęp do elementu, musisz przemierzaj drzewo aż do znalezienia odpowiedniej tablicy. Z chunked sekwencji, całe tablice są przechwytywane na raz. Oznacza to, że każdy z 32 elementów może zostać odzyskany przed ponownym przejściem drzewa.

Dyskutowano o sposobie wymuszenia oceny punkt po punkcie w sytuacjach, w których wymagane jest pełne lenistwo. Jednak nie sądzę, aby został dodany do języka jeszcze.

Dlaczego można zawinąć wywołania rekurencyjne w leniwą sekwencję i nie dłużej uzyskać stos nad przepływem dla dużych obliczeń?