[racket] Tail recursive module cons

Using accumulator+reverse won't really improve the runtime at all.

The thing is, Racket's "stack" is a list of continuations. I don't see
how explicitly keeping the "stack" in an accumulator would help. Stack
overflow won't be a problem since the "stack" is a list on the heap, and
unless memory runs out you wont overflow. Obviously memory can run out
if the accumulator gets too big also.

Stupid benchmark:

#lang racket
(define (list-incr/direct lst)
  (cond
    [(empty? lst) empty]
    [else (cons (add1 (car lst))
                (list-incr/direct (cdr lst)))]))

(define (list-incr/acc lst (acc empty))
  (cond
    [(empty? lst) (reverse acc)]
    [else (list-incr/acc (cdr lst)
                         (cons (add1 (car lst))
                               acc))]))

(define huge-list
  (build-list 50000 identity))

(time
 (for ([i 20])
   (list-incr/direct huge-list))
 (collect-garbage)
 (collect-garbage)
 (collect-garbage))

(time
 (for ([i 20])
   (list-incr/acc huge-list))
 (collect-garbage)
 (collect-garbage)
 (collect-garbage))

> cpu time: 1496 real time: 1495 gc time: 1368
> cpu time: 1464 real time: 1465 gc time: 1368

I think that tail recursion doesn't help at all, and introduces
conceptual overhead. Racket doesn't use the stack, and converts to
continuation-passing, which is surprise-surprise *tail recursive* at
runtime anyway.


On Sun, 2014-03-16 at 17:30 -0400, Sam Tobin-Hochstadt wrote:
> Basically, avoiding growing the stack when building a list, by
> compiling this program:
> 
> (define (list-id l)
>   (if (null? l) l
>       (cons (car l) (list-id (cdr l)))))
> 
> into this one:
> 
> (define (list-id* l acc)
>   (if (null? l)
>      (set-cdr! acc null)
>      (let ([p (cons (car l) #f)])
>        (set-cdr! acc p)
>        (list-id (cdr l) p))))
> 
> There's a pretty good discussion on Wikipedia:
> http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons
> 
> Note that this doesn't run in constant space, since we're allocating a
> pair at each step, but it changes the complexity from 2n to n.
> 
> Sam
> 
> 
> On Sun, Mar 16, 2014 at 5:13 PM, Matthias Felleisen
> <matthias at ccs.neu.edu> wrote:
> >
> > What does tail-recursion modulo cons mean?
> >
> >
> > On Mar 16, 2014, at 3:38 PM, Sam Tobin-Hochstadt wrote:
> >
> >> On Sun, Mar 16, 2014 at 2:55 PM, Patrick Useldinger
> >> <uselpa.list at gmail.com> wrote:
> >>>
> >>>
> >>> My questions are:
> >>>
> >>> (1) Is Racket "tail-recursive modulo cons"? If not, is there a reason for
> >>> this?
> >>
> >> Racket is not "tail-recursive modulo cons".
> >>
> >>> (2) Is the last example "reverse free" or does it use reverse under the
> >>> hood?
> >>
> >> `for/list` uses `reverse` internally -- you can see for yourself how
> >> this works by using the Macro Stepper.
> >>
> >>> (3) finally, what is the recommended way to write this procedure in terms of
> >>> performance?
> >>
> >> I took your program, and made all the functions run on much longer
> >> lists. Here are the timings:
> >>
> >> $ r /tmp/even-list.rkt
> >> 'plain
> >> cpu time: 1288 real time: 1294 gc time: 936
> >> 't
> >> cpu time: 440 real time: 441 gc time: 320
> >> 'for/fold
> >> cpu time: 484 real time: 485 gc time: 328
> >> 'mcons
> >> cpu time: 204 real time: 204 gc time: 148
> >> 'mcons-convert
> >> cpu time: 632 real time: 631 gc time: 416
> >> 'for/list
> >> cpu time: 460 real time: 460 gc time: 332
> >>
> >> 'mcons-convert is one that uses `mcons`, but converts back to plain
> >> `cons` at the end.
> >>
> >> Sam
> >> ____________________
> >>  Racket Users list:
> >>  http://lists.racket-lang.org/users
> >
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users