[racket] Tail recursive module cons

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
>