219 lines
6.6 KiB
Org Mode
219 lines
6.6 KiB
Org Mode
#+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
|