Sun Apr 26 16:41:40 CEST 2009

CPS + optimization



  mzc -vk comp.ss ; mzc --decompile compiled/comp_ss.zo

comp.ss :

  (define (inc x k)
    (k (+ 1 x)))

  (define (inc3_ x k)
    (inc x (lambda (x)
    (inc x (lambda (x)
    (inc x k))))))

Inspecting the output gives something like this:

  (define (inc3 p k)
    (let* ((p1 (+ '1 p))
           (p2 (+ '1 p1)))
           (k  (+ '1 p2))))

So it does look like this rep might be valuable as an abstraction
mechanism.  Let's see if it still works with more complicated

(define (add p k)
  (k (cons (+ (car p)
              (cadr p))
           (cddr p))))
(define (add4 p k)
  (add p  (lambda (p1)
  (add p1 (lambda (p2)
  (add p2 k))))))


  (define (add4 p k)
    (let* ((p1 (cons
                (+ (car p)
                   (cadr p))
                (cddr p)))
           (p2 (cons
                (+ (car p1)
                   (cadr p1))
                (cddr p1))))
      (k (cons
          (+ (car p2)
             (cadr p2))
          (cddr p2)))))

So the function gets inlined and applied closures are converted to let

Now, instead of using cps, it might be easier to already put the
compositions in let form.  The goal eventually is to add other let
bindings to a list!

So, let*-transformation works like:

(a b c) ->

(lambda (p)
  (let* ((p (a p))
         (p (b p))
         (p (c p)))

Or better in it's nested form which works better with other
let-transformers, which can be spliced right in.  This then makes the
locals problem completely trivial.

(lambda (p)
  (let ((p (a p)))
  (let ((p (b p)))
  (let ((p (c p)))

So, let's switch the rpn language to a "nested let" representation
(EDIT: administrative normal form[1]).  This is quite trivial.

... foldl ... #`(apply atom #,expr)


... foldr ... #`(let ((p (apply atom p))) #,expr))))

Tests pass without trouble.

Ha! for once i have the feeling i know what i'm doing!