apply, apply-primitive-procedure and apply-in-underlying-scheme

Question

Apply is defined in 4.1.1 The Core of the Evaluator of SICP as:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure ;
          procedure
          arguments));

        ((compound-procedure? procedure)
        .....
        (else
        ....)

I referenced the definition of apply-primitive-procedure in "4.1.4 Rnning the Evaluator as a Program" as:

(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))

So apply-primitive-procedure is implemented by apply-in-underlying-scheme

Nonetheless, refer to the footnotes:

Apply-in-underlying-scheme is the apply procedure we have used in earlier chapters. The metacircular evaluator's apply procedure ([[4.1.1]]) models the working of this primitive. Having two different things called apply leads to a technical problem in running the metacircular evaluator, because defining the metacircular evaluator's apply will mask the definition of the primitive. One way around this is to rename the metacircular =apply= to avoid conflict with the name of the primitive procedure. We have assumed instead that we have saved a reference to the underlying =apply= by doing
(define apply-in-underlying-scheme apply)
before defining the metacircular apply. This allows us to access the original version of apply under a different name.

It states the apply-in-underlying-scheme is apply in 4.1.1.

In a summary:

 ,-> apply -> apply-primitive-procedure -> apply-in-underlying-scheme --.
 '----------------------------------------------------------------------'

I guess it not a recursion.

What's wrong with my understanding?

Answer 1

Apply means function application for everything that is not a special form (the special forms are considered in eval). Apply is a recursive function that will ever finish.

Apply is subdivided in 2 cases of procedure application:

-- internal to the system that implements the language

This is the place where is made the transition between the target language and the language that is used to implement the target language (source language).

Here you need to evaluate each parameter (through eval) and convert the resulting object to a similar object in source language before to call the application function of the source language. For some parameters the recursion of eval->apply may happen.

-- a combination created in the target language by using the means of combination that the target language provides.

In this case also you need to recursively call eval for each parameter and use function application in the target language. In this case you do not need to convert the result of eval to an object in the source language.

So in case of combinations there is also recursion in apply, but it is a kind of recursion that will finish (function application function is a primitive-recursive function) because you evaluate a smaller piece each time (operator, operands vs the full initial expression).

I think that you did not notice that apply is a primitive-recursive operator and you were afraid it will not finish.