Is the `R_{Var}^{ANF}` language defined in Figure 2.12 too broad?

[rundong08]

Consider the following example in R_{Var}

(+ 1 (+ 2 (+ 3 4)))

From the description of rco-exp and rco-atom, it appears that the book wanted the following translation to R_{Var}^{ANF}:

;; Code 1
(let ([tmp.1 (+ 3 4)])
  (let ([tmp.2 (+ 2 tmp.1)])
    (+ 1 tmp.2)))

However, there is another way to do this:

;; Code 2
(let ([tmp.1
       (let ([tmp.2 (+ 3 4)])
         (+ 2 tmp.2))])
  (+ 1 tmp.1))

which I believe is also a valid R_{Var}^{ANF} program. But I feel Code 2 is harder to evaluate, which would need a stack, while Code 1 can be evaluated without a stack.

Should we restrict the R_{Var}^{ANF} such that Code 1 is valid but Code 2 is invalid, for example, by not allowing e in (Let x e body) to contain any Let expression?

[jsiek]

Consider the following input program

(let ([x (+ 42 (- 10))])
  (+ x 10))

Our reference compiler produces the following output from remove-complex-opera*:

(let ([x88924 (let ([tmp88925 (- 10)])
                 (+ 42 tmp88925))])
   (+ x88924 10))

While it is certainly possible for us to instead float the let-bindings for temporaries up to the top during remove-complex-opera*, we instead choose to accomplish that task in the explicate-control pass.

[rundong08]

Ah, I see. Thanks for the explanation!