CIS531 Project 2 -- `anf-convert`, CPS and CPS Conversion

cps-notes.rkt

#lang racket

;; CIS531 -- Fall 2025
;; Kristopher Micinski
;;
;; Notes on CPS Conversion

#;(+ (* (read) 3) (+ 4 5))

;; When we translate constructs like +, *, and other
;; primitive operations down to CPU instructions
;; the arguments (operands) of those instructions
;; must be atomic
;;
;; x86-64 instructions must have "atomic" operands
;; in the sense that all operands must be able to be
;; evaluated by the CPU within the clock cycle.
;; 
;; add $5, %rbx

;; translate the example into
#;(let ([x0 (read)]) ;; introduce "administrative" bindings 
  (let ([x1 (* x0 3)])
    (let ([x2 (+ 4 5)])
      (let ([x3 (+ x1 x2)])
        x3))))

(define (r1-e? e)
  (match e
    [(? integer? i) #t]
    [`(read) #t]
    [(? symbol? x) #t]
    [`(let ([,(? symbol? x) ,(? r1-e? e)]) ,(? r1-e? e-b)) #t]
    [`(+ ,(? r1-e? e0) ,(? r1-e? e1)) #t]
    [`(- ,(? r1-e? e)) #t]
    [_ #f]))

(define (atom? a)
    (match a
      [(? integer? i) #t]
      [(? symbol? x)  #t]))

(define (r1-anf? e)
  (match e
    [(? atom? a) #t]
    ['(read) #t]
    [`(let ([,(? symbol? x) ,(? r1-anf? e)]) ,(? r1-anf? e-b)) #t]
    [`(+ ,(? atom? a0) ,(? atom? a1)) #t]
    [`(- ,(? atom? a)) #t]
    [_ #f]))

;; anf-convert : r1-e? -> r1-anf?
(define (anf-convert expr)
  ;; c-e converts a complex expression e
  ;; whenever it's done, we need to pass
  ;; its result to k.
  (define (c-e e k)
    (match e
      [(? integer? i)
       ;; just call the continuation on i
       (k i)]
      [(? symbol? x)
       (k x)]
      [`(- ,e)
       (c-e e (λ (a0) ;; atom?
                (define x (gensym 'int))
                `(let ([,x (- ,a0)])
                    ;; should be x, not a0! Thanks to student from CIS531
                   ,(k x))))]
      [`(+ ,e0 ,e1)
       ;; e0 / e1 are not necessarily in ANF
       ;; I need to emit a let expression which
       ;; captures the result of converting e0
       ;; and creates an administrative binding
       ;; using `let`.
       ;; Then, I've got a variable name for the
       ;; binding, which I can use to invoke my
       ;; continuation k
       (define e0-res (gensym 'int))
       (c-e e0 (lambda (a0) ;; atom?
                 (c-e e1 (lambda (a1)
                           `(let ([,e0-res (+ ,a0 ,a1)])
                              ,(k e0-res))))))]))
  (c-e expr (lambda (x) x)))

;; Start by discussing "continuation passing style."
;;
;; Write functions which take a "continuation" as an
;; argument.

;; Simple motivating example: how would you walk over
;; a tree in a tail-recursive fashion?

;; say we want to walk over a list and add all even
;; elements...
(define (add-even-tail l acc)
  (match l
    ['() acc]
    [`(,hd . ,tl)
     (let ([int (if (even? hd) (+ hd acc) acc)])
       (add-even-tail (rest l) int))]))

(add-even-tail '(1 2 3 4 5) 0)

;; How can we do a similar accumulator walk over a tree?
(define (tree? t)
  (match t
    ['empty #t]
    [`(node ,v ,(? tree? t0) ,(? tree? t1)) #t]
    [_ #f]))

(define (sum-tree t)
  (match t
    ['empty 0]
    [`(node ,v ,t0 ,t1)
     (+ v (sum-tree t0) (sum-tree t1))]))

(define (binary-search t v)
  (match t
    ['empty #f]
    [`(node ,v+ ,t0 ,t1)
     (cond [(equal? v+ v) #t]
           [(< v v+) (binary-search t0 v)]
           [else     (binary-search t1 v)])]))

;; the function k is a "continuation," which we must call
;; with our result.
(define (sum-even-tree t k)
  (match t
    ['empty (k 0)]
    [`(node ,v ,t0 ,t1)
     (define this-nodes-contribution (if (even? v) v 0))
     (sum-even-tree t0
                    (λ (t0s-sum)
                      (sum-even-tree t1
                                     (λ (t1s-sum)
                                       (k (+ t0s-sum t1s-sum this-nodes-contribution))))))]))

;; Continuation-passing style is a style of programming where I augment
;; every function definition to include a "continuation" parameter.
;; The requirement of the paradigm (i.e., calling convention of sorts?)
;; is that whenever I get my result, I invoke the continuation on that
;; result.
;; 

;; [email protected]