[MIT-Scheme-devel] Y combinator RTL

[Taylor R Campbell]

Here's the RTL for a simplification of Y, annotated with what's going
on.  The problem starts on the line marked with `***'.  Looking into
why the problem arises now...

RTL for object 1
    (named-lambda (y f)
      (let ((g (lambda (g) (f (lambda (x) ((g g) x))))))
        (g g)))


;;; Code for Y

(procedure-header y-4 2 2)
;; Stack on entry: f

;; Cons a closure for g = (lambda (g) (f (lambda (x) ((g g) x)))).
(assign (register #x12) (cons-closure (entry:procedure lambda-2) 2 2 1))
(assign (register #x11) (cons-pointer (machine-constant #x28) (register #x12)))
(assign (register #x13) (register #x12))

;; Fetch f from 0(sp) into r14.
(assign (register #x14) (offset (register 4) (machine-constant 0)))

;; Store f in the closure for g.
(assign (offset (register #x13) (machine-constant 2)) (register #x14))

;; Replace the current application frame by (g g).
(assign (offset (register 4) (machine-constant 0)) (register #x11))
(assign (pre-increment (register 4) -1) (register #x11))
;; Stack is now: g g

;; Invoke g.
(invocation:jump 2 #f lambda-2)

;;; Code for g: (lambda (g) (f ((lambda (x) ((g g) x)))))

(closure-header lambda-2 1 0)
;; Stack on entry: g g

;; Fetch g from 0(sp) into r11.
(assign (register #x11) (offset (register 4) (machine-constant 0)))

;; Read f from the closure for g into r10.  (*)
(assign (register #x12) (object->address (register #x11)))
(assign (register #x10) (offset (register #x12) (machine-constant 2)))

;; Start replacing current application frame by (f (lambda (x) ...)).
(assign (offset (register 4) (machine-constant 0)) (register #x10))
;; Stack is now: f g

;; Cons closure for h = (lambda (x) ((g g) x)).
(assign (register #x15) (cons-closure (entry:procedure lambda-1) 2 2 1))
(assign (register #x14) (cons-pointer (machine-constant #x28) (register #x15)))

;; *** Store f (not g!) into h.  (r10 is f; r11 is g.)
(assign (offset (register #x15) (machine-constant 2)) (register #x10))

;; Finish replacing current application frame by (f (lambda (x) ...)).
(assign (offset (register 4) (machine-constant 1)) (register #x14))
;; Stack is now: f h

;; Invoke f.
(invocation:apply 2 #f)

;;; Code for h: (lambda (x) ((g g) x))

(closure-header lambda-1 1 0)
;; Stack on entry: h x

;; Push a continuation for ([] x).
(assign (register #x12) (cons-pointer (machine-constant #x28) 
(entry:continuation continuation-0)))
(assign (pre-increment (register 4) -1) (register #x12))
;; Stack is now: k h x

;; Read h from 1(sp) into r13.
(assign (register #x13) (offset (register 4) (machine-constant 1)))

;; Read f (not g!) from h into r14.
(assign (register #x14) (object->address (register #x13)))
(assign (register #x15) (offset (register #x14) (machine-constant 2)))

;; Push application frame for (f f) (not (g g)!).
(assign (pre-increment (register 4) -1) (register #x15))
(assign (pre-increment (register 4) -1) (register #x15))
;; Stack is now: f f k h x

;; Invoke g with the wrong application frame.  Who knows what the line
;; marked (*) will read from f when it expects g...
(invocation:jump 2 continuation-0 lambda-2)

;;; Code for continuation ([] x)

(continuation-header continuation-0)
;; Stack on entry: h x

;; Read return value p into r10.
(assign (register #x10) (offset (register 6) (machine-constant 2)))

;; Replace current application frame by (p x).
(assign (offset (register 4) (machine-constant 0)) (register #x10))
;; Stack is now: p x

;; Invoke p.
(invocation:apply 2 #f)