* why I love scheme @ 2021-12-14 23:44 Stefan Israelsson Tampe 2021-12-15 1:21 ` Nala Ginrut 2021-12-15 9:38 ` Zelphir Kaltstahl 0 siblings, 2 replies; 5+ messages in thread From: Stefan Israelsson Tampe @ 2021-12-14 23:44 UTC (permalink / raw) To: Guile User Maybe you think the below program is trivial, but I adore named let's so much that I just cannot fathom that when people go functional they totally miss this beauty (define (count tree) ;; s = total sum up to now ;; t = tree of the type (car = child . cdr = siblings) ;; cont is the continuation, (cont 10) will continue ;; the calculation with the sum=10 see how we initiate ;; with a continuation that evaluates returns it's argument (let loop ((s 0) (t tree) (cont (lambda (s) s))) (if (pair? t) (loop s (car t) (lambda (s) (loop s (cdr t) cont))) (cont (if (number? t) t 0)))) ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: why I love scheme 2021-12-14 23:44 why I love scheme Stefan Israelsson Tampe @ 2021-12-15 1:21 ` Nala Ginrut 2021-12-15 9:38 ` Zelphir Kaltstahl 1 sibling, 0 replies; 5+ messages in thread From: Nala Ginrut @ 2021-12-15 1:21 UTC (permalink / raw) To: Stefan Israelsson Tampe; +Cc: Guile User I see your point. Yes, continuation (CPS) is pretty cool to replace the hidden stack magic for recursive algorithms. :-) Best regards. On Wed, Dec 15, 2021, 07:45 Stefan Israelsson Tampe <stefan.itampe@gmail.com> wrote: > Maybe you think the below program is trivial, but I adore named let's so > much that I just cannot fathom that when people go functional they totally > miss this beauty > > > (define (count tree) > > ;; s = total sum up to now > > ;; t = tree of the type (car = child . cdr = siblings) > > ;; cont is the continuation, (cont 10) will continue > > ;; the calculation with the sum=10 see how we initiate > > ;; with a continuation that evaluates returns it's argument > > > (let loop ((s 0) (t tree) (cont (lambda (s) s))) > > (if (pair? t) > > (loop s (car t) (lambda (s) (loop s (cdr t) cont))) > > (cont (if (number? t) t 0)))) > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: why I love scheme 2021-12-14 23:44 why I love scheme Stefan Israelsson Tampe 2021-12-15 1:21 ` Nala Ginrut @ 2021-12-15 9:38 ` Zelphir Kaltstahl [not found] ` <CAGua6m2cwQShFHSwoEqqF5HiSewGU1cDJyBsZvmicVT46N=pOA@mail.gmail.com> 1 sibling, 1 reply; 5+ messages in thread From: Zelphir Kaltstahl @ 2021-12-15 9:38 UTC (permalink / raw) To: Stefan Israelsson Tampe; +Cc: Guile User Hello Stefan! This translates a recursive tree function into a tail recursive function. However, in this case, I am not sure it is really worth doing, in comparison to the naive (+ first-branch other-branch) solution. The reason is, that instead of a call stack for multiple branches, you are only moving that stuff into a longer and longer continuation, which will be on the stack in each recursive call. However, I think you or other people on the list probably know more about this than I do and about how the approaches compare in terms of memory and time. Maybe the stack frames are more in size than the memory consumed by the overhead of the continuation, or the other way around. Regards, Zelphir On 12/15/21 12:44 AM, Stefan Israelsson Tampe wrote: > Maybe you think the below program is trivial, but I adore named let's so > much that I just cannot fathom that when people go functional they totally > miss this beauty > > > (define (count tree) > > ;; s = total sum up to now > > ;; t = tree of the type (car = child . cdr = siblings) > > ;; cont is the continuation, (cont 10) will continue > > ;; the calculation with the sum=10 see how we initiate > > ;; with a continuation that evaluates returns it's argument > > > (let loop ((s 0) (t tree) (cont (lambda (s) s))) > > (if (pair? t) > > (loop s (car t) (lambda (s) (loop s (cdr t) cont))) > > (cont (if (number? t) t 0)))) -- repositories: https://notabug.org/ZelphirKaltstahl ^ permalink raw reply [flat|nested] 5+ messages in thread
[parent not found: <CAGua6m2cwQShFHSwoEqqF5HiSewGU1cDJyBsZvmicVT46N=pOA@mail.gmail.com>]
* Re: why I love scheme [not found] ` <CAGua6m2cwQShFHSwoEqqF5HiSewGU1cDJyBsZvmicVT46N=pOA@mail.gmail.com> @ 2021-12-15 20:30 ` Zelphir Kaltstahl 2021-12-15 21:12 ` Damien Mattei 0 siblings, 1 reply; 5+ messages in thread From: Zelphir Kaltstahl @ 2021-12-15 20:30 UTC (permalink / raw) To: Stefan Israelsson Tampe; +Cc: Guile User I did not know, that lambdas are allocated on the heap. I have a few questions now: How does this affect using fibers? (And how do fibers work better in that case?) The unrolling you mentioned. Would same not be possible for the naive-but-not-tail-recursive version? Is the idea, that the continuation tail recursive version does work better, because the compiler is somehow able to optimize it better? If so, why? I am asking, because I once had the same kind of problem and then read, that instead of growing stack levels, I am growing the continuation, so not winning anything. But perhaps that was wrong and I should have gone for the continuation solution. I would like to be able to make an educated decision when next meeting such a problem. Best regards, Zelphir On 12/15/21 1:59 PM, Stefan Israelsson Tampe wrote: > I believe that the lambda closures will be allocated from the heap and hence > this procedure will > be perfect if you are using fibers.. Also the compiler can do magic if it > want's and unroll > and untangle a few iterations, so it can be very fast as well.My point is that > the named let > is such a nice looping construct (try to do this with a for loop in java). I > use it all the time > and only sometimes I need to move to even more advanced constructs like letrec. > > On Wed, Dec 15, 2021 at 10:38 AM Zelphir Kaltstahl <zelphirkaltstahl@posteo.de > <mailto:zelphirkaltstahl@posteo.de>> wrote: > > Hello Stefan! > > This translates a recursive tree function into a tail recursive function. > However, in this case, I am not sure it is really worth doing, in > comparison to > the naive (+ first-branch other-branch) solution. The reason is, that > instead of > a call stack for multiple branches, you are only moving that stuff into a > longer > and longer continuation, which will be on the stack in each recursive call. > > However, I think you or other people on the list probably know more about this > than I do and about how the approaches compare in terms of memory and time. > Maybe the stack frames are more in size than the memory consumed by the > overhead > of the continuation, or the other way around. > > Regards, > Zelphir > > On 12/15/21 12:44 AM, Stefan Israelsson Tampe wrote: > > Maybe you think the below program is trivial, but I adore named let's so > > much that I just cannot fathom that when people go functional they totally > > miss this beauty > > > > > > (define (count tree) > > > > ;; s = total sum up to now > > > > ;; t = tree of the type (car = child . cdr = siblings) > > > > ;; cont is the continuation, (cont 10) will continue > > > > ;; the calculation with the sum=10 see how we initiate > > > > ;; with a continuation that evaluates returns it's argument > > > > > > (let loop ((s 0) (t tree) (cont (lambda (s) s))) > > > > (if (pair? t) > > > > (loop s (car t) (lambda (s) (loop s (cdr t) cont))) > > > > (cont (if (number? t) t 0)))) > > -- > repositories: https://notabug.org/ZelphirKaltstahl > <https://notabug.org/ZelphirKaltstahl> > -- repositories: https://notabug.org/ZelphirKaltstahl ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: why I love scheme 2021-12-15 20:30 ` Zelphir Kaltstahl @ 2021-12-15 21:12 ` Damien Mattei 0 siblings, 0 replies; 5+ messages in thread From: Damien Mattei @ 2021-12-15 21:12 UTC (permalink / raw) Cc: Guile User hello Stefan, i have had two Scheme teacher before graduating and being teaching scheme too. One tell us that basically CPS is the same as recursivity. The other one said students to always give an example of the use of a Scheme function of our own unless it did not read and give a note to our work. ;-) Damien On Wed, Dec 15, 2021 at 9:32 PM Zelphir Kaltstahl < zelphirkaltstahl@posteo.de> wrote: > I did not know, that lambdas are allocated on the heap. I have a few > questions now: > > How does this affect using fibers? (And how do fibers work better in that > case?) > > The unrolling you mentioned. Would same not be possible for the > naive-but-not-tail-recursive version? Is the idea, that the continuation > tail > recursive version does work better, because the compiler is somehow able to > optimize it better? If so, why? > > I am asking, because I once had the same kind of problem and then read, > that > instead of growing stack levels, I am growing the continuation, so not > winning > anything. But perhaps that was wrong and I should have gone for the > continuation > solution. I would like to be able to make an educated decision when next > meeting > such a problem. > > Best regards, > Zelphir > > > On 12/15/21 1:59 PM, Stefan Israelsson Tampe wrote: > > I believe that the lambda closures will be allocated from the heap and > hence > > this procedure will > > be perfect if you are using fibers.. Also the compiler can do magic if it > > want's and unroll > > and untangle a few iterations, so it can be very fast as well.My point > is that > > the named let > > is such a nice looping construct (try to do this with a for loop in > java). I > > use it all the time > > and only sometimes I need to move to even more advanced constructs like > letrec. > > > > On Wed, Dec 15, 2021 at 10:38 AM Zelphir Kaltstahl < > zelphirkaltstahl@posteo.de > > <mailto:zelphirkaltstahl@posteo.de>> wrote: > > > > Hello Stefan! > > > > This translates a recursive tree function into a tail recursive > function. > > However, in this case, I am not sure it is really worth doing, in > > comparison to > > the naive (+ first-branch other-branch) solution. The reason is, that > > instead of > > a call stack for multiple branches, you are only moving that stuff > into a > > longer > > and longer continuation, which will be on the stack in each > recursive call. > > > > However, I think you or other people on the list probably know more > about this > > than I do and about how the approaches compare in terms of memory > and time. > > Maybe the stack frames are more in size than the memory consumed by > the > > overhead > > of the continuation, or the other way around. > > > > Regards, > > Zelphir > > > > On 12/15/21 12:44 AM, Stefan Israelsson Tampe wrote: > > > Maybe you think the below program is trivial, but I adore named > let's so > > > much that I just cannot fathom that when people go functional they > totally > > > miss this beauty > > > > > > > > > (define (count tree) > > > > > > ;; s = total sum up to now > > > > > > ;; t = tree of the type (car = child . cdr = siblings) > > > > > > ;; cont is the continuation, (cont 10) will continue > > > > > > ;; the calculation with the sum=10 see how we initiate > > > > > > ;; with a continuation that evaluates returns it's argument > > > > > > > > > (let loop ((s 0) (t tree) (cont (lambda (s) s))) > > > > > > (if (pair? t) > > > > > > (loop s (car t) (lambda (s) (loop s (cdr t) cont))) > > > > > > (cont (if (number? t) t 0)))) > > > > -- > > repositories: https://notabug.org/ZelphirKaltstahl > > <https://notabug.org/ZelphirKaltstahl> > > > -- > repositories: https://notabug.org/ZelphirKaltstahl > > ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-12-15 21:12 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-12-14 23:44 why I love scheme Stefan Israelsson Tampe 2021-12-15 1:21 ` Nala Ginrut 2021-12-15 9:38 ` Zelphir Kaltstahl [not found] ` <CAGua6m2cwQShFHSwoEqqF5HiSewGU1cDJyBsZvmicVT46N=pOA@mail.gmail.com> 2021-12-15 20:30 ` Zelphir Kaltstahl 2021-12-15 21:12 ` Damien Mattei
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).