Order of evaluation compound procedures metacircular 'apply'

Question

I'm studying SICP chapter 4 and its implementation of a metacircular Scheme evaluator. I'm having difficulties understanding how user defined procedures are handled by its apply procedure.

The metacircular evaluator is composed of two main procedures: eval and apply. The basic idea is to recursively apply eval until there's only self-evaluating expressions (like numbers and strings) or expressions with primitive procedures that can be handled directly by apply.

The evaluator works following the environment model of evaluation, where we bind variables to their associated values and create new frames every time lambda is invoked. Procedure definitions are handled this way. The procedure name is binded in the environment and when it's called, its body is evaluated in a new frame where the parameters have been binded to the arguments used to call it.

This specific part is reflected in the following lines of the apply procedure:

(define (apply procedure arguments)
  (cond (...)
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (...)

An user defined procedure is recognized by the compound-procedure? predicate. The eval-sequence procedure just evaluates (procedure-body procedure) and (extend-environment ...) sequentially and returns the value of the last expression.

My problem is that, as I understand it, we should extend the environment first and only then evaluate the body of the procedure:

         (eval-sequence
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))
           (procedure-body procedure))

For example in:

(define (square x) (* x x))
(square 5)

The first line will bind square to a lambda (with its associated parameters and body). This binding will be recognized in the second line. Then I understand we create a new frame where x = 5 and only then is the body of square executed. But this order seems to be inverted by the apply procedure, where the body of the procedure is evaluated before binding the parameters to the arguments.

I'd really appreciate if someone could help me understand this issue.

Barmar Barmar · Accepted Answer · 2020-07-24T17:47:59

(procedure-body procedure) does not evaluate the body of the procedure, it simply returns it.

The body of the procedure is evaluated by eval-sequence. It receives the new environment as its second argument, and that environment is created by extend-environment, which adds all the parameter bindings to the environment.

Then eval-sequence evaluates the procedure body in the scope of that extended environment.

Order of evaluation compound procedures metacircular 'apply'

1 Answers