Page 121 - Textos de Matemática Vol. 40

3.3. Streams in scheme 109
would not terminate. For this reason streams are represented in scheme using a new category of objects, called promises which are outside of the pure functional framework. Promises are generated by the routine delay which blocks the evaluation of its argument until it is released by a call of force. So the evaluation of an object a in the expression (delay a) is delayed until it is released by a call of (force (delay a)).11 The stream construction function (cons-stream a b) is defined as syntactic sugar for (cons a (delay b)). The destructor functions head and tail are introduced as scheme functions by:
(define (head stream) (car stream))
(define (tail stream) (force (cdr stream)))
Now one gets the n-th element of a stream using the function nth-stream which is recursively defined by:12
(define (nth-stream n x)
(if (= n 0)
(head s)
(nth-stream (-1+ n) (tail s))))
With respect to the strict evaluation, delay cannot be a scheme proce- dure, but must be a special operation at the syntax level, cf. [AS85, footnote 34, p. 262]. At this level (delay a) is easily definable as an abbreviation for the procedure with no arguments (lambda () a). Then force becomes the evalua- tion of such a procedure and is defined by (define (force x) (x)), cf. [AS85, p. 264].
If we model scheme procedures with no arguments by constant unary functions in applicative theories, the meaning of delay corresponds exactly to the operation t → t. Moreover force corresponds to val. So promises of scheme behave like the pointers we have introduced in FPA. If the cons func- tion is modeled by pairing in applicative theories, (cons-stream a b) becomes p a (λy.b), y ̸∈ FV(b), head becomes λx.p0 x, and tail becomes λx.val (p1 x). For nth-stream we get as translation the function nth satisfying the following recursion equation:
nthxy ≃ dN (p0 y)(nth(pN x)(val(p1 y)))x0.
As an example we give the representation of the stream of Fibonacci numbers which may be introduced in scheme in the following way, cf. [AS85, p. 267]:
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
11In scheme force and delay also provide some properties concerning memory handling and efficiency. Because this is not related to the computational content of streams, we do not discuss it here.
12-1+ is the scheme function which decrements the argument.