/prog/ - Too bad CPS is SLOW AS FUCK

Name: Anonymous 2011-01-28 19:08

(fact values 100000), ten times (cps)
cpu time: 431239 real time: 431781 gc time: 132998
(fact 100000), ten times (tail recursive)
cpu time: 7 real time: 6 gc time: 0

Name: Anonymous 2011-01-28 19:22

cps vs tail-recursive doesn't make sense. If you didn't end up with all tail calls then you did cps wrong.

Name: Anonymous 2011-01-28 19:54

>>2
Isn't cps (cps-f cont args)? With cps-f defined as (k (do-something-with-args))?

Name: Anonymous 2011-01-28 20:29

>>3
I'm not sure I understand what you're saying, but if you are not tail-calling a continuation with the results, then you don't have CPS.
Also, CPS is not intended as an optimisation.



; naive factorial

(define factorial

  (lambda (n)

    (if (< n 2)

        1

        (* n

           (factorial (- n 1))))))



; naive factorial cpsed, with cpsed primitives

(define factorial-cps

  (lambda (n k)

    (<cps n 2

          (lambda (k2)     

            (if k2

                (k 1)

                (-cps n 1

                      (lambda (k3)

                        (factorial-cps k3

                                       (lambda (k4)

                                         (*cps n k4 k))))))))))

Name: Anonymous 2011-01-28 20:53

>>4



(define-values

  (cps= cps- cps*)

    (values (λ (x y k) (k (= x y)))

            (λ (x y k) (k (- x y)))

            (λ (x y k) (k (* x y)))))

(define (f n k)

  (define (f-aux n a k)

    (cps= n 0

      (lambda (n1)

        (if n1 (k a)

        (cps- n 1

              (lambda (n2)

            (cps* n a

                  (lambda (n3)

                (f-aux n2 n3 k)))))))))

  (f-aux n 1 k))

(f 5 values)

Also, CPS is not intended as an optimisation.
I know that, but is is really slow.
I wanted to use it for my toy Scheme implementation, but it would be slower than Ruby.

Too bad CPS is SLOW AS FUCK

1 Name: Anonymous 2011-01-28 19:08

2 Name: Anonymous 2011-01-28 19:22

3 Name: Anonymous 2011-01-28 19:54

4 Name: Anonymous 2011-01-28 20:29

5 Name: Anonymous 2011-01-28 20:53

Name: Anonymous 2011-01-28 19:08

Name: Anonymous 2011-01-28 19:22

Name: Anonymous 2011-01-28 19:54

Name: Anonymous 2011-01-28 20:29

Name: Anonymous 2011-01-28 20:53