Thursday, August 5, 2010

Reverse in continuation passing style

A simple reverse in continuation passing style...

(define cp-reverse
  (lambda (lst)
    (letrec ([cpr (lambda (lst k)
                 (cond 
                   ((null? lst) (k '()))
                   (else 
                    (cpr (cdr lst)
                         (lambda (v)
                           (cons (car lst) (k v)))))))])
      (cpr lst (lambda (v) v)))))

This is a rather classical example, indeed. Performance wise it's much slower than the reverse builtin in PLT-Scheme/Racket, still it's a lot faster than even more classical trivial implementations such as:


(define (sl-reverse lst)
  (cond
    ((null? lst) '())
    (else (append (sl-reverse (cdr lst)) (list (car lst))))))

In fact the example relies on TCO modulo cons.

In order to test the whole thing in racket I used this snippet:

(define (print-times min max step)
  (for ([m (in-range min max step)])
    (let ([lst (for/list ([i (in-range m)]) i)])
      (time (reverse lst))
      (time (cp-reverse lst))
      (time (sl-reverse lst)))))


> (print-times 5000 10000 1000)
cpu time: 0 real time: 10 gc time: 0
cpu time: 5 real time: 61 gc time: 0
cpu time: 1320 real time: 2088 gc time: 1099
cpu time: 1 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 463 real time: 493 gc time: 185
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 21 gc time: 0
cpu time: 888 real time: 926 gc time: 505
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2729 real time: 2766 gc time: 2235
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2157 real time: 2227 gc time: 1522

No comments: