#+title: ABI

largely based on the Guile Hoot's [[https://codeberg.org/spritely/hoot/src/branch/main/design/ABI.md][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

#+begin_src scheme
  ;; 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))
#+end_src

** fac

*** Scheme source

#+begin_src scheme
(define fac
  (λ (n)
    (if (zero? n)
        1
        (* n (fac (- n 1))))))

(fac 3)
#+end_src

*** CPS

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

(fac 3 halt)

#+end_src

*** tailified

#+begin_src scheme
(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)
#+end_src

evaluation of ~(fac 0)~:

#+begin_src scheme
(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] []
#+end_src

evaluation of ~(fac 3)~

#+begin_src scheme
(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)
#+end_src