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)?
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:
a
, b
and c
in some order;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:
<x>
a symbol? If it is then
(<x> ...)
using the definition of the macro and start again on the result;if
, or lambda
)? If it does then use whatever idiosyncratic rule is defined for that;<x>
and all its arguments, and apply the value of <x>
to the values of the argumentsNow 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.