CSE271: Principles of Programming Languages

Continuation Passing Style (CPS)

Jooyong Yi (UNIST)

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

Example: Transforming to CPS

(fact 3) = (* 3 (fact 2))
         = (* 3 (* 2 (fact 1)))
         = (* 3 (* 2 (* 1 (fact 0))))
         = (* 3 (* 2 (* 1 1)))
         = (* 3 (* 2 1))
         = (* 3 2)
         = 6

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

↓

(define fact/k 
  (lambda (n cont)
    (if (zero? n)
        ...

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

↓

(define fact/k 
  (lambda (n cont)
    (if (zero? n)
        ...

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

↓

(define fact/k 
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        ...

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

↓

(define fact/k 
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        (fact/k (- n 1) (fact1-cont n cont)))))

Example: Transforming to CPS

(define fact 
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

↓

(define fact 
  (lambda (n) (fact/k n (end-cont))))

(define fact/k
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        (fact/k (- n 1) (fact1-cont n cont)))))

end-cont and fact1-cont

(apply-cont (end-cont) val) = val
(apply-cont (fact1-cont n cont) val) = (apply-cont cont (* n val))

Execution Trace

(fact 3) = (fact/k 3 (end-cont))

(define fact 
  (lambda (n) (fact/k n (end-cont))))

Execution Trace

(fact 3) = (fact/k 3 (end-cont))
         = (fact/k 2 (fact1-cont 3 (end-cont)))

(define fact/k
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        (fact/k (- n 1) (fact1-cont n cont)))))

Execution Trace

(fact 3) = (fact/k 3 (end-cont))
         = (fact/k 2 (fact1-cont 3 (end-cont)))
         = (fact/k 1 (fact1-cont 2 (fact1-cont 3 (end-cont))))
         = (fact/k 0 (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))))         
         = (apply-cont (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))) 1)

(define fact/k
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        (fact/k (- n 1) (fact1-cont n cont)))))

Execution Trace

(fact 3) = ...
         = (fact/k 0 (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))))         
         = (apply-cont (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))) 1)         
         = (apply-cont (fact1-cont 2 (fact1-cont 3 (end-cont))) (* 1 1))
         = (apply-cont (fact1-cont 3 (end-cont)) (* 2 (* 1 1)))
         = (apply-cont (end-cont) (* 3 (* 2 (* 1 1))))

(apply-cont (fact1-cont n cont) val) = (apply-cont cont (* n val))

Execution Trace

(fact 3) = ...
         = (fact/k 0 (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))))         
         = (apply-cont (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))) 1)         
         = (apply-cont (fact1-cont 2 (fact1-cont 3 (end-cont))) (* 1 1))
         = (apply-cont (fact1-cont 3 (end-cont)) (* 2 (* 1 1)))
         = (apply-cont (end-cont) (* 3 (* 2 (* 1 1))))
         = 6

(apply-cont (end-cont) val) = val

Overall Execution Trace

(fact 3) = (fact/k 3 (end-cont))
         = (fact/k 2 (fact1-cont 3 (end-cont)))
         = (fact/k 1 (fact1-cont 2 (fact1-cont 3 (end-cont))))
         = (fact/k 0 (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))))
         = (apply-cont (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))) 1)         
         = (apply-cont (fact1-cont 2 (fact1-cont 3 (end-cont))) (* 1 1))
         = (apply-cont (fact1-cont 3 (end-cont)) (* 2 (* 1 1)))
         = (apply-cont (end-cont) (* 3 (* 2 (* 1 1))))
         = 6

Comparison

(define fact                                       (fact 2) = (* 2 (fact 1))
  (lambda (n)                                               = (* 2 (* 1 (fact 0)))
    (if (zero? n)                                           = (* 2 (* 1 1))
        1                                                   = 2
        (* n (fact (- n 1))))))

(define fact/k                                     (fact/k 2 (end-cont)) 
  (lambda (n cont)                               = (fact/k 1 (fact1-cont 2 (end-cont)))
    (if (zero? n)                                = (fact/k 0 (fact1-cont 1 (fact1-cont 2 (end-cont))))
        (apply-cont cont 1)                      = (apply-cont (fact1-cont 1 (fact1-cont 2 (end-cont))) 1)
        (fact/k (- n 1)                          = (apply-cont (fact1-cont 2 (end-cont)) (* 1 1))                
                (fact1-cont n cont)))))          = (apply-cont (end-cont) (* 2 (* 1 1)))
                                                 = 2       

(apply-cont (end-cont) val) = val
(apply-cont (fact1-cont n cont) val) = (apply-cont cont (* n val))

Implementing Continuations

;; Spec
(apply-cont (end-cont) val) = val
(apply-cont (fact1-cont n cont) val) = (apply-cont cont (* n val))                     

• Using datatype and pattern matching

(define-datatype continuation continuation?                                            
  (end-cont)
  (fact1-cont 
    (n integer?)
    (cont continuation?)))

(define apply-cont
  (lambda (cont val)
    (cases continuation cont
      (end-cont () val)
      (fact1-cont (saved-n saved-cont)
        (apply-cont saved-cont (* saved-n val))))))

Implementing Continuations

;; Spec
(apply-cont (end-cont) val) = val
(apply-cont (fact1-cont n cont) val) = (apply-cont cont (* n val))                     

• Using procedural representations

(define apply-cont
  (lambda (cont val) (cont val)))

(define end-cont
  (lambda () (lambda (val) val)))

(define fact1-cont
  (lambda (n cont)
    (lambda (val) (cont (* n val)))))

Execution Trace (Procedure Representation)

(fact 3) = ... = (apply-cont (fact1-cont 1 (fact1-cont 2 (fact1-cont 3 (end-cont)))) 1)
= ((fact1-cont 2 (fact1-cont 3 (end-cont))) (* 1 1))
= ((fact1-cont 3 (end-cont)) (* 2 (* 1 1)))
= ((end-cont) (* 3 (* 2 (* 1 1))))
= 6

(define apply-cont
  (lambda (cont val) (cont val)))

(define end-cont
  (lambda () (lambda (val) val)))

(define fact1-cont
  (lambda (n cont)
    (lambda (val) (cont (* n val)))))

Inlining

(define fact/k                                                                                
  (lambda (n cont)
    (if (zero? n)
        (apply-cont cont 1)
        (fact/k (- n 1)
                (fact1-cont n cont)))))

↓

(define apply-cont                                                                               
  (lambda (cont val) (cont val)))

↓

(define fact/k                                                                               
  (lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/k (- n 1)
                (fact1-cont n cont)))))

Inlining

(define fact/k                                                                               
  (lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/k (- n 1)
                (fact1-cont n cont)))))

↓

(define fact1-cont                                                                               
  (lambda (n cont)
    (lambda (val) (cont (* n val)))))  

↓

(define fact/k                                                                               
  (lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/k (- n 1)
                (lambda (val) (cont (* n val)))))))

Execution Trace (Inlining)

(fact 3) = (fact/k 3 (end-cont))
         = (fact/k 2 (lambda (val) (end-cont (* 3 val))))
         = (fact/k 1 (lambda (val) ((lambda (val) (end-cont (* 3 val))) (* 2 val))))
         = (fact/k 0 (lambda (val) ((lambda (val) ((lambda (val) (end-cont (* 3 val))) (* 2 val))) (* 1 val))))
         = ((lambda (val) 
                    ((lambda (val) 
                             ((lambda (val) 
                                      (end-cont 
                                       (* 3 val))) 
                              (* 2 val))) 
                     (* 1 val)))
            1)

(define fact/k                                                                               
  (lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/k (- n 1)
                (lambda (val) (cont (* n val)))))))

Execution Trace (Inlining)

(fact 3) = ...
         = ((lambda (val) 
                    ((lambda (val) 
                             ((lambda (val) 
                                      (end-cont 
                                       (* 3 val))) 
                              (* 2 val))) 
                     (* 1 val)))
            1)
         = ((lambda (val) 
                    ((lambda (val) 
                             (end-cont 
                              (* 3 val))) 
                     (* 2 val)))
            (* 1 1))

Execution Trace (Inlining)

(fact 3) = ...
         = ((lambda (val) 
                    ((lambda (val) 
                             (end-cont 
                              (* 3 val))) 
                     (* 2 val)))
            (* 1 1))
         = ((lambda (val) 
                    (end-cont 
                     (* 3 val)))
            (* 2 (* 1 1)))

Execution Trace (Inlining)

(fact 3) = ...
         = ((lambda (val) 
                    ((lambda (val) 
                             (end-cont 
                              (* 3 val))) 
                     (* 2 val)))
            (* 1 1))
         = ((lambda (val) 
                    (end-cont 
                     (* 3 val)))
            (* 2 (* 1 1)))
         = (end-cont (* 3 (* 2 (* 1 1))))
         = 6

Overall Execution Trace (Inlining)

(fact 3) = ...
         = ((lambda (val) ;; f1
                    ((lambda (val) ;; f2
                             ((lambda (val) ;; f3
                                      (end-cont 
                                       (* 3 val))) 
                              (* 2 val))) 
                     (* 1 val)))
            1)
         = ((lambda (val) 
                    ((lambda (val) 
                             (end-cont 
                              (* 3 val))) 
                     (* 2 val)))
            (* 1 1))
         = ((lambda (val) 
                    (end-cont 
                     (* 3 val)))
            (* 2 (* 1 1)))
         = (end-cont (* 3 (* 2 (* 1 1))))
         = 6

Dataflow through Continuations

(fact 3) = ...                                                                                         
         = ((lambda (val) ;; f1
                    ((lambda (val) ;; f2
                             ((lambda (val) ;; f3
                                      (end-cont 
                                       (* 3 val))) 
                              (* 2 val))) 
                     (* 1 val)))
            1)
         = ((lambda (val) 
                    ((lambda (val) 
                             (end-cont 
                              (* 3 val))) 
                     (* 2 val)))
            (* 1 1))
         = ((lambda (val) 
                    (end-cont 
                     (* 3 val)))
            (* 2 (* 1 1)))
         = (end-cont (* 3 (* 2 (* 1 1))))
         = 6

1 → f1 → f2 → f3 → end-cont → 6

• Reactive Programs