unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
* 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

* 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).