gyehoek-hs/doc/abi.org

ABI

• calling convention
  • non-tail calls
• scratchpad
  • fac
    • Scheme source
    • CPS
    • tailified

largely based on the Guile Hoot's ABI.

calling convention

non-tail calls

• set the global variable $current-closure to the callee's closure.
• load arguments into globals $arg0, $arg1, $arg2, …
• push return continuation onto $cont-stack

scratchpad

  ;; Scheme source
  (define (silly f g h x)
    (f (h x) (g x)))


  ;; continuation-passing style
  (define (silly f g h x ktail)
    (h x (κ (x0)
            (g x (κ (x1)
                    (f x0 x1 ktail))))))

  ;; with explicit stacks
  (define (silly)
    (define f (pop!))
    (define g (pop!))
    (define h (pop!))
    (define x (pop!))
    (define ktail (pop-cont!))
    (push-cont! (κ (x0)
                   (define x* (pop!))
                   (define g* (pop!))
                   (push-cont! (κ (x1)
                                  (define f* (pop!))
                                  (define x0* (pop!))
                                  (push-cont! ktail)
                                  (push! x0*)
                                  (push! x1)
                                  (call! f)))
                   (push! x*)
                   (call! g)))
    (push! x)
    (call! h))

fac

Scheme source

(define fac
  (λ (n)
    (if (zero? n)
        1
        (* n (fac (- n 1))))))

(fac 3)

CPS

  (define fac
  (λ (n ktail)
    (zero? n (κ (x0)
                (if x0
                    1
                    (- n 1
                       (κ (x1)
                          (fac x1
                               (κ (x2)
                                  (* n x2 ktail))))))))))

(fac 3 halt)

tailified

(define (fac-k1)
  (define n (pop!))
  (define x2 (pop!))
  (define x3 (* n x2))
  (define ktail (pop-cont!))
  (push! x3)
  (call! ktail))

(define (fac-k0)
  (define x0 (pop!))
  (define n (pop!))
  (if x0
      (begin (define ktail (pop-cont!))
             (push! 1)
             (call! ktail))
      (begin (define x1 (- n 1))
             (push! x1)
             (push-cont! fac-k1)
             (call! fac))))

(define (fac)
  (define n (pop!))
  (push! n)
  (push-cont! fac-k0)
  (push! n)
  (call! zero?))

(push! 3)
(push-cont! halt)
(call! fac)

evaluation of (fac 0):

(push! 0)                  ; [] []
(push-cont! halt)          ; [0] []
(call! fac)                ; [0] [halt]
(define n (pop!))          ; [0] [halt]
(push! n)                  ; [] [halt]
(push-cont! fac-k0)        ; [0] [halt]
(push! n)                  ; [0] [halt fac-k0]
(call! zero?)              ; [0 0] [halt fac-k0]
#<internals of zero?>      ; [0 0] [halt fac-k0]
(define x0 (pop!))         ; [0 #t] [halt]
(define n (pop!))          ; [0] [halt]
(define ktail (pop-cont!)) ; [] [halt]
(push! 1)                  ; [] []
(call! ktail)              ; [1] []

evaluation of (fac 3)

(push! 3)                  ; [] []
(push-cont! halt)          ; [3] []
(call! fac)                ; [3] [halt]

(define n (pop!))          ; [3] [halt]
(push! n)                  ; [] [halt]
(push-cont! fac-k0)        ; [3] [halt]
(push! n)                  ; [3] [halt fac-k0]
(call! zero?)              ; [3 3] [halt fac-k0]
#<internals of zero?>      ; [3 3] [halt fac-k0]
(define x0 (pop!))         ; [3 #f] [halt]
(define n (pop!))          ; [3] [halt]
(define x1 (- n 1))        ; [] [halt]
(push! n)                  ; [] [halt]
(push! x1)                 ; [3] [halt]
(push-cont! fac-k1)        ; [3 2] [halt]
(call! fac)                ; [3 2] [halt fac-k1]

(define n (pop!))          ; [3 2] [halt fac-k1]
(push! n)                  ; [3 ] [halt fac-k1]
(push-cont! fac-k0)        ; [3 2] [halt fac-k1]
(push! n)                  ; [3 2] [halt fac-k1 fac-k0]
(call! zero?)              ; [3 2 2] [halt fac-k1 fac-k0]
#<internals of zero?>      ; [3 2 2] [halt fac-k1 fac-k0]
(define x0 (pop!))         ; [3 2 #f] [halt fac-k1]
(define n (pop!))          ; [3 2] [halt fac-k1]
(define x1 (- n 1))        ; [3] [halt fac-k1]
(push! n)                  ; [3] [halt fac-k1]
(push! x1)                 ; [3 2] [halt fac-k1]
(push-cont! fac-k1)        ; [3 2 1] [halt fac-k1]
(call! fac)                ; [3 2 1] [halt fac-k1 fac-k1]

(define n (pop!))          ; [3 2 1] [halt fac-k1 fac-k1]
(push! n)                  ; [3 2] [halt fac-k1 fac-k1]
(push-cont! fac-k0)        ; [3 2 1] [halt fac-k1 fac-k1]
(push! n)                  ; [3 2 1] [halt fac-k1 fac-k1 fac-k0]
(call! zero?)              ; [3 2 1 1] [halt fac-k1 fac-k1 fac-k0]
#<internals of zero?>      ; [3 2 1 1] [halt fac-k1 fac-k1 fac-k0]
(define x0 (pop!))         ; [3 2 1 #f] [halt fac-k1 fac-k1]
(define n (pop!))          ; [3 2 1] [halt fac-k1 fac-k1]
(define x1 (- n 1))        ; [3 2] [halt fac-k1 fac-k1]
(push! n)                  ; [3 2] [halt fac-k1]
(push! x1)                 ; [3 2 1] [halt fac-k1 fac-k1]
(push-cont! fac-k1)        ; [3 2 1 0] [halt fac-k1 fac-k1]
(call! fac)                ; [3 2 1 0] [halt fac-k1 fac-k1 fac-k1]

(define n (pop!))          ; [3 2 1 0] [halt fac-k1 fac-k1 fac-k1]
(push! n)                  ; [3 2 1] [halt fac-k1 fac-k1 fac-k1]
(push-cont! fac-k0)        ; [3 2 1 0] [halt fac-k1 fac-k1 fac-k1]
(push! n)                  ; [3 2 1 0] [halt fac-k1 fac-k1 fac-k1 fac-k0]
(call! zero?)              ; [3 2 1 0 0] [halt fac-k1 fac-k1 fac-k1 fac-k0]
#<internals of zero?>      ; [3 2 1 0 0] [halt fac-k1 fac-k1 fac-k1 fac-k0]
(define x0 (pop!))         ; [3 2 1 0 #t] [halt fac-k1 fac-k1 fac-k1]
(define n (pop!))          ; [3 2 1 0] [halt fac-k1 fac-k1 fac-k1]
(define ktail (pop-cont!)) ; [3 2 1] [halt fac-k1 fac-k1 fac-k1]
(push! 1)                  ; [3 2 1 1] [halt fac-k1 fac-k1]
(call! ktail)              ; [3 2 1 1] [halt fac-k1 fac-k1]

(define n (pop!))          ; [3 2 1 1] [halt fac-k1 fac-k1]
(define x2 (pop!))         ; [3 2 1] [halt fac-k1 fac-k1]
(define x3 (* n x2))       ; [3 2] [halt fac-k1 fac-k1]
(define ktail (pop-cont!)) ; [3 2] [halt fac-k1 fac-k1]
(push! x3)                 ; [3 2] [halt fac-k1]
(call! ktail)              ; [3 2 1] [halt fac-k1]

(define n (pop!))          ; [3 2 1] [halt fac-k1]
(define x2 (pop!))         ; [3 2] [halt fac-k1]
(define x3 (* n x2))       ; [3] [halt fac-k1]
(define ktail (pop-cont!)) ; [3] [halt fac-k1]
(push! x3)                 ; [3] [halt]
(call! ktail)              ; [3 2] [halt]

(define n (pop!))          ; [3 2] [halt]
(define x2 (pop!))         ; [3] [halt]
(define x3 (* n x2))       ; [] [halt]
(define ktail (pop-cont!)) ; [] [halt]
(push! x3)                 ; [] []
(call! ktail)              ; [6] []
;; => (halt 6)