Fork me on GitHub
#clojure-italy
<
2018-03-05
>
manuel08:03:50

buon lunedì

manuel08:03:31

@skuro non fare il misterioso, fuori i nomi! (sì, ti romperò fino a che non usciranno, sorry 😁)

skuro08:03:51

sisi, fai pure @manuel che mi aiuti con l'expectation buildup

reborg10:03:10

Intuisco il problema, ma se dovessi spiegare la meccanica delle nested recursive lazy-seq non ce la farei:

(defn lazy-bomb [n]
  (letfn [(step2 [[y & ys]] (lazy-seq (cons y (step2 ys))))
          (step1 [[x & xs]] (lazy-seq (cons x (step1 (step2 xs)))))]
    (take n (step1 (range)))))

(last (lazy-bomb 10000))
;; StackOverflowError

bronsa10:03:37

@reborg in quell’esempio lazy seq non c’entra niente

bronsa10:03:03

(defn non-lazy-bomb [n]
  (letfn [(step2 [[y & ys]] (cons y (step2 ys)))
          (step1 [[x & xs]] (cons x (step1 (step2 xs))))]
    (step1 (take n (range)))))

(last (non-lazy-bomb 10000))
;;;StackOverflow

bronsa10:03:12

e` non tail recursion in generale il prolema qui

reborg10:03:11

Vero, non volevo accusare lazy-seq. Ma l'esempio, senza step2, sarebbe non tail-recursive, ma lo stack non esplode. lazy-seq senza nesting, ha l'interessante properieta' di transformare stack-consuming in heap consuming. Se c'e' nesting, la proprieta' non vale piu'.

bronsa11:03:56

senza step2 esploderebbe comunque

bronsa11:03:13

solo piu` tardi visto che lo stack crescerebbe piu` lentamente

bronsa11:03:34

non son sicuro di capire cosa intendo con l’ultima frase

bronsa11:03:08

>Ma l’esempio, senza step2, sarebbe non tail-recursive, ma lo stack non esplode. scusa, stavo pensando al mio esempio non il tuo — vero e ora ho collegato cosa intendi con l’ultima frase

bronsa11:03:58

quindi se sto capendo bene, tu vorresti spiegare perche`

(defn lazy-bomb [n]
  (letfn [(step2 [[y & ys]] (lazy-seq (cons y (step2 ys))))
          (step1 [[x & xs]] (lazy-seq (cons x (step1 (step2 xs)))))]
    (take n (step1 (range)))))
e` stack consuming mentre
(defn lazy-bomb [n]
  (letfn [(step1 [[x & xs]] (lazy-seq (cons x (step1 xs))))]
    (take n (step1 (range)))))
non lo e`?

reborg11:03:05

Si'. Anche se vedo dov'e' se ne va lo stack con println debugger, faccio fatica a spiegare il perche' questo accade.

reborg11:03:16

mi immagino se lo dovessi spiagare a qualcuno, non ce la farei

reborg11:03:16

esercizio intellettuale per la maggiorparte, ma il sieve per i numeri primi (naive version) segue questo pattern

bronsa11:03:20

il motivo per cui una (defn foo [[x & y]] (lazy-seq (cons x (foo y)))) non e` stack consuming, e` perche` internamente lazy-seq e` effettivamente un trampoline

bronsa11:03:36

ok e` tricky :)

reborg11:03:45

non sono il solo 🙂

bronsa12:03:15

@reborg

(defn lazy-bomb [n]
  (letfn [(step2 [g [y & ys]]
            (println "step2: " g y)
            (lazy-seq (cons y (step2 g ys))))
          (step1 [[x & xs]] (let [g (gensym)]
                              (println "step1: " g x)
                              (lazy-seq (cons x (step1 (step2 g xs))))))]
    (take n (step1 (range)))))
#'user/lazy-bomb
user=> (def x (lazy-bomb 10))
step1:  G__152 0
#'user/x
user=> (nth x 0)
step2:  G__152 1
step2:  G__152 2
step2:  G__152 3
step1:  G__155 1
0
user=> (nth x 1)
step2:  G__152 4
step2:  G__155 2
step2:  G__152 5
step2:  G__155 3
step2:  G__152 6
step2:  G__155 4
step1:  G__158 2
1
user=> (nth x 2)
step2:  G__152 7
step2:  G__155 5
step2:  G__158 3
step2:  G__152 8
step2:  G__155 6
step2:  G__158 4
step2:  G__152 9
step2:  G__155 7
step2:  G__158 5
step1:  G__161 3
2
user=> (nth x 3)
step2:  G__152 10
step2:  G__155 8
step2:  G__158 6
step2:  G__161 4
step2:  G__152 11
step2:  G__155 9
step2:  G__158 7
step2:  G__161 5
step2:  G__152 12
step2:  G__155 10
step2:  G__158 8
step2:  G__161 6
step1:  G__164 4
3

bronsa12:03:18

questo aiuta molto

reborg12:03:12

si, ho fatto qualcosa di simile, ma non sapevo il trick del gensym per tenere traccia dello stack!

reborg12:03:28

ogni step c'e' un po' delle precedenti lazy-seqs che viene iterato sullo stack fino a che ovviamente non esplode

reborg18:03:29

Dunque, ho una teoria. Mentre una ricorsione normale con lazy-seq produce un pattern tipo:

(cons 0 (cons 1 (cons ... (lazy-seq n-2, n-1, n))
con la parte non realizzata sempre in fondo, nested lazy-seq produce qualcosa tipo:
(cons 0 (lazy-seq (cons 2 (cons 3 (cons n-3 (lazy-seq n-2, n-1, n)))))
che e' dovuto al fatto che l'ultima cosa prima di ritornare un risultato e' sempre una chiamata ricorsiva a step1 (infatti "step1: G__" e' sempre l'ultimo print). La cons da un numero ad una lazy-seq non realizzata e' sempre in testa, quindi dev'essere traversata sullo stack "modello tunnel" per arrivare al fondo e prendere un nuovo item. Ed ogni giro cresce la larghezza delle cons centrali.

bronsa19:03:34

sì era la mia teoria - - ha lo stesso tipo di tail growth di step 1 solo che cresce esponenzialmente invece di lineamente

bronsa19:03:57

però non ne son sicuro, appena arrivo a casa con un po' di tempo faccio qualche esperimento e vediamo