scopeschemeevaluationsicpmit-scheme

Redefining the special form after the usage of that special form in one func definition has no effects to that definition in Scheme


I am reading SICP section 3.5.1 where it gives the implementation of primitive procedures provided in MIT/GNU Scheme.

I tried to load these implementations without considering the order since they are all (define ...), but actually the order matters (For the following simplified demo, we need to run (define (cons-stream a b) ...) before (define (stream-enumerate-interval low high) ...)).

I run:

;; case 1
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(stream-enumerate-interval 0 10)

(define (cons-stream a b)
  (display "call cons-stream")
  (cons a (delay b)))

(stream-enumerate-interval 0 10)
; not output "call cons-stream"

;; case 2
(define (cons-stream-1 a b)
  (display "call cons-stream")
  (cons a (delay b)))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream-1
       low
       (stream-enumerate-interval (+ low 1) high))))

(stream-enumerate-interval 0 10)

(define (cons-stream-1 a b)
  (display "call cons-stream-1")
  (cons a (delay b)))

(stream-enumerate-interval 0 10)
; will use the new "cons-stream-1" by outputing "call cons-stream-1".

;; case 3
(define (test-redefine-+ . args)
  (display (apply + args)))

(test-redefine-+ 2 3 4)
(define (+ . args)
  (apply * args))
(test-redefine-+ 2 3 4)
; redefinition works by outputing 24.

As the book says:

we will suppose that there is a global environment, consisting of a single frame (with no enclosing environment) that includes values for the symbols associated with the primitive procedures.

A procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the arguments of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure object being applied.

A procedure is created by evaluating a lambda expression relative to a given environment. The resulting procedure object is a pair consisting of the text of the lambda expression and a pointer to the environment in which the procedure was created.

As the above says, we only record "the text of the lambda expression" when define without recording the value of procedure used inside like cons-stream.

So IMHO when we call the 2nd (stream-enumerate-interval 0 10), we will try finding the value of cons-stream in the "new environment" with the parameter binding. Since that will fail, then we look at the "enclosing environment", i.e. the global env here. Then there it is expected that cons-stream has been binded to the new value. But that is not that case.

However, the above problem doesn't occur for user-defined lambda func cons-stream-1. Could someone tell me the difference between the env diagram corresponding to these 2 cases (not necessary to draw the diagram that may be routine and tedious. Clear words are fine for me)?


Solution

  • This is not to do with environments: it is to do with how cons-stream must be defined. Both of your definitions are incorrect, because cons-stream must be defined so that

    (cons-stream a b) is equivalent to (cons a (delay b)) (from 3.5.1).

    Such a thing cannot be defined as a procedure in an applicative-order language because a form like (a b c) is evaluated as:

    1. evaluate a, b and c in some order;
    2. apply the procedure resulting from the evaluation of a to the results of evaluating the two arguments.

    Neither cons-stream nor delay can be implemented this way, because they must not evaluate one or more of their arguments.

    Instead they either are primitives defined by the language, or they are macros, which can be thought of as rules which specify how certain bits of source get turned into other bits of source.

    This means, for instance, that

    (define upfrom
      (lambda (v)
        (cons-stream v (upfrom (+ v 1)))))
    
    (define upfrom-0 (upfrom 0))
    

    will work: it is easy to see that it can not do so – it will fail to terminate – with your definition of cons-stream.

    What has happened then, is that the transformation of source code into other source code has happened before you defined cons-stream to be an ordinary procedure.


    A way to think of what happens is that, when looking at a form like (<x> ...) the evaluator says something like:

    Now the point is that the first case can be done entirely before anything else is done: you can walk over the form and do all the macro stuff, and then have a form which doesn't include the first case. And, obviously any kind of compiler will have to do that: an interpreter may choose not to. But the first case may well happen at the point the (define ...) form is evaluated.

    So, if cons-stream is initially a macro (and it will be, since there is no reason for it to be a primitive), then it's just not defined what happens if you later define it to be something else.