closure-conversion.rkt

running example:

(((λ (f) (λ (y) (f y 9))) (λ (a b) (+ a b))) 3)

oh, let's write it in consieuten:

fun makeCaller ((int int -> int) f) (int -> int) {
  fun caller(int y) int {
    return f(y,9);
  }
  return caller;
}

fun main () int {
  (int -> int) f;
  fun adder(int a, int b) int {
    return a + b;
  }
  f = makeCaller(adder);
  return f(3);
}

okay, let's see the IR (whoa!):


'(letrec ((UmakeCaller
           (λ ((Uf : (int int -> int)))
             :
             (int -> int)
             (letrec ((Ucaller
                       (λ ((Uy : int)) : int
                         (letrec ()
                           (letrec ((K0
                                     (λ ((Uf : (int int -> int))
                                         (Uy : int))
                                       : int
                                       (Uf Uy 9))))
                             (K0 Uf Uy))))))
               (letrec ((K0 (λ ((Ucaller : (int -> int)))
                              : (int -> int) Ucaller)))
                 (K0 Ucaller)))))
          (Umain
           (λ () : int
             (letrec ((Uadder
                       (λ ((Ua : int) (Ub : int))
                         : int
                         (letrec ()
                           (letrec ((K0
                                     (λ ((Ub : int)
                                         (Ua : int))
                                       : int
                                       (+ Ua Ub))))
                             (K0 Ub Ua))))))
               (letrec ((K0 (λ ((Uadder : (int int -> int))
                                (UmakeCaller : ((int int -> int) -> (int -> int))))
                              : int
                              (let ((Uf (UmakeCaller Uadder)))
                                (Uf 3)))))
                 (K0 Uadder UmakeCaller))))))
   (Umain))

... aaaand, here's the closure-converted version:

'(letrec ((CP4_makeCaller
           (λ (CV-this Uf)
             (letrec ((CP10_caller (λ (CV-this Uy)
                                     (letrec ()
                                       (letrec ((K0
                                                 (λ ((Uf : (int int -> int)) (Uy : int))
                                                   : int
                                                   ((ref Uf proc) Uf Uy 9))))
                                         (K0 (ref CV-this Uf) Uy))))))
               (letrec ((K0 (λ ((Ucaller : (int -> int)))
                              : (int -> int) Ucaller)))
                 (let ((Ucaller (new 2)))
                   (set Ucaller proc CP10_caller
                        (set Ucaller Uf Uf
                             (K0 Ucaller))))))))
          (CP5_main
           (λ (CV-this)
             (letrec ((CP14_adder
                       (λ (CV-this Ua Ub)
                         (letrec ()
                           (letrec ((K0 (λ ((Ub : int) (Ua : int)) : int (+ Ua Ub))))
                             (K0 Ub Ua))))))
               (letrec ((K0 (λ ((Uadder : (int int -> int))
                                (UmakeCaller : ((int int -> int) -> (int -> int))))
                              : int
                              (let ((Uf ((ref UmakeCaller proc) UmakeCaller Uadder)))
                                ((ref Uf proc) Uf 3)))))
                 (let ((Uadder (new 1)))
                   (set Uadder proc CP14_adder
                        (K0 Uadder (ref CV-this UmakeCaller)))))))))
   (let ((UmakeCaller (new 1))
         (Umain (new 2)))
     (set Umain proc CP5_main
          (set Umain UmakeCaller UmakeCaller
               (set UmakeCaller proc CP4_makeCaller
                    ((ref Umain proc) Umain))))))