Why is self-naming legal in function definition but illegal meaning?
Structure and Interpretation of Computer Programs (SICP) 3.5.2 introduces endless streams:
(define ones
(cons-stream 1 ones))
This code does not work in DrRacket with the error:
units: undefined; cannot refer to an identifier before it is defined
Another code:
(define (integers-starting-from n)
(cons-stream n
(integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
raises an error:
Interaction disabled
(falling in an endless loop?)
While I'm reading (SICP), the key to implementing an infinite stream is latency estimation:
(define (delay exp)
(lambda () exp))
(define (cons-stream a b)
(cons a
(delay b)))
When used in an cons-stream
endless stream, it is still illegal.
Such a data structure reminds me of a recursive function, the definition of which self-engagement is legal (when compiled) within or without actual output.
Why is it illegal for the value to refer to itself? Even the link was delayed?
Can an endless stream be supported by another programming language?
If not, is it about how the processor handles assembly language? Data stack stuff?
source to share
When you do a procedure, the arguments are already evaluated when you run the procedure body. Thus, delay
it would not have done anything, since it was already calculated at this time. cons-stream
should be a macro.
DrRacket is not one language implementation. It is an IDE that supports many languages. One of them is the SICP compatibility language. I was able to run the code without error using this code in DrRacket:
#!planet neil/sicp (define ones (cons-stream 1 ones)) (define (integers-starting-from n) (cons-stream n (integers-starting-from (+ n 1)))) (define integers (integers-starting-from 1))
It works like a charm. The default language in DrRacket, #!racket
, has also flows , but have different names:
#!racket (define ones (stream-cons 1 ones)) (define (integers-starting-from n) (stream-cons n (integers-starting-from (+ n 1)))) (define integers (integers-starting-from 1))
However, for the circuit, you have to use SRFI-41 which you can use from both #!racket
(using (require srfi/41)
) and #!r6rs
(and R7RS-large when done)
(import (rnrs) (srfi :41)) (define ones (stream-cons 1 ones)) (define (integers-starting-from n) (stream-cons n (integers-starting-from (+ n 1)))) (define integers (integers-starting-from 1))
To roll your own SICP streams to both in #!racket
and out #!r6rs
, you can usedefine-syntax
(define-syntax stream-cons (syntax-rules () ((_ a d) (cons a (delay d)))))
Note that the native RSFI-41 and rackets streaming library for #!racket
delays both values in stream-cons
, not just as a tail like here in the SICP version.
source to share
This is because the expression is define
evaluated before the name is bound to the value. It tries to evaluate (cons-stream 1 ones)
before it is ones
defined, causing an error.
The reason this works great for functions is because the body of the function is not evaluated when the function is. That is, to evaluate (lambda (x) (f x))
, the language returns a function without looking at its body. As
(define (f x) (f x))
is syntactic sugar for defining a lambda, the same logic applies.
Did you define yourself cons-stream
as above? If you do a normal function cons-stream
, it won't work as expected. Since the default schema is strict, the arguments are evaluated before the function is called. If cons-stream
is a normal function, it b
will be fully evaluated before passing it to delay
, which will hit an infinite loop.
cons-stream
in SICP it is a "special form" and not a function, which means that it can control how its arguments are evaluated.
If you use operations stream-cons
and others stream-
built into Racket, you get the behavior you want.
Finally, some other languages allow you to reference values. A great example is Haskell where this works because everything is lazy by default. Here's a Haskell snippet defining ones
an infinite list. (Since everything is lazy, Haskell lists behave exactly like Scheme streams):
ones = 1 : ones
source to share
This definition works in Racket:
(define ones
(cons-stream 1 ones))
... While you provide the delayed implementation cons-stream
as a special form, which is the whole point of section 3.5 in the SICP:
(define-syntax cons-stream (syntax-rules () ((_ head tail) (cons head (delay tail)))))
source to share
Add to the above answers to make sure the code is running, you should also define delay
like this:
(define-syntax delay
(syntax-rules ()
((_ exp)
(lambda () exp))))
delay
and cons-stream
must also be defined as a macro.
Alternatively, you can simply call the delay
predefined one in Racket rather than create a new one.
But don't do this:
(define (delay exp)
(lambda () exp))
The compiler will accept your definition, so the program will crash:
Interaction disabled
source to share