mutually recursive streams

[Daniel]

Hi group,

I recently started learning Scheme. At the moment I am playing with
streams / lazy lists. More specifically, I am trying to solve the
problem described at http://rosettacode.org/wiki/Formal_Power_Series.

The idea is to use lazy lists for the Taylor series expansion of
functions. These should then be used to define the sine and cosine
functions in a mutually recursive way using their integrals.

The following code is what I have so far. It implements lazy lists of
Taylor series expansions and defines integration and differentiation on
them. These behave as intended. But when I try to define the sine and
cosine functions in a mutually recursive way, the result is "Error:
undefined variable stream-sin". I tried it with mit-scheme and
scheme48. Is there any way to make this work? When I try to work out
what is supposed to happen on paper, I do get the correct expansions.

Another thing I was trying to figure out, was how to define stream-add
in terms of stream-map in such a way that it accepts an arbitrary
number of streams. I don't want to repeat what is in the definition of
stream-map.

This is the code:

(define-syntax stream-cons
(syntax-rules ()
((stream-cons x y)
(cons x (delay y)))))

(define (stream-car stream)
(car stream))

(define (stream-cdr stream)
(force (cdr stream)))

(define (stream-map function . streams)
(stream-cons (apply function (map stream-car streams))
(apply stream-map function (map stream-cdr streams))))

(define (integers-from start)
(stream-cons start (integers-from (+ start 1))))

(define (stream-constant number)
(stream-cons number (stream-constant number)))

(define integers
(integers-from 1))

;; integration
(define (stream-int stream)
(stream-cons 0 (stream-map * stream (stream-map / integers))))

;; differentiation
(define (stream-dif stream)
(stream-map * integers (stream-cdr stream)))

(define (stream-take count stream)
(if (zero? count)
(list)
(cons (stream-car stream) (stream-take (- count 1) (stream-cdr
stream)))))

;; int (1) = x
(display (stream-take 10 (stream-int (stream-cons 1 (stream-constant
0)))))
(newline)

;; dif (1 + x + x^2) = 1 + 2 * x
(display (stream-take 10 (stream-dif (stream-cons 1 (stream-cons 1
(stream-cons 1 (stream-constant 0)))))))
(newline)

(define stream-cos
(stream-map - (stream-constant 1) (stream-int stream-sin)))

(define stream-sin
(stream-int stream-cos))

(display (stream-take 10 stream-sin))
(newline)

Any suggestions?
Thanks, Daniel

[Vitaly Magerya]

Daniel wrote:
> Another thing I was trying to figure out, was how to define stream-add
> in terms of stream-map in such a way that it accepts an arbitrary
> number of streams. I don't want to repeat what is in the definition of
> stream-map.

Is this what you're looking for?

(define (stream-add . streams)
(apply stream-map + streams))

> (define stream-cos
> (stream-map - (stream-constant 1) (stream-int stream-sin)))

Both stream-map and stream-int are functions, not macros, so stream-sin
needs to be evaluated prior to function call; thus the error. What you
need is to delay the evaluation of stream-sin variable till it's defined.

Telling you the truth, I don't know of an elegant solution here. One
solution is to turn stream constructors into macros. Like this:

(define-syntax define-stream-constructor
(syntax-rules ()
((_ (name . args) body)
(define-syntax name
(syntax-rules ()
((_ . args) body))))))

And then change the stream-int definition to:

(define-stream-constructor (stream-int stream)

(stream-cons 0 (stream-map * stream (stream-map / integers))))

Or you could just embed the stream-int definition into stream-cos
definition (it uses stream-cons giving you the needed delay).

Another solution is to use even streams, i.e. represent streams not as
(cons x (delay y)), but as (delay (cons x (delay y))). Then you could
just write (delay (force stream-sin)) instead of stream-sin in the
definition of stream-cos.

BTW, that was not a correct cosine. The correct one is:

(define stream-cos
(stream-map
-
(stream-cons 1 (stream-constant 0))
(stream-int stream-sin)))

> (define stream-sin
> (stream-int stream-cos))
>
> (display (stream-take 10 stream-sin))
> (newline)

With If you try using macros and correct the cosine definition, the
result will be:

(0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880)

Finally, I recommend you to look at SRFI 41 [1] for a solid streams
implementation, and a discussion of how odd and even streams differ.
Unfortunately SRFI 41 does not expose the delay/force/lazy primitives
that it uses internally; otherwise wrapping stream-sin into stream-lazy
would be a solution.

[1] http://srfi.schemers.org/srfi-41/srfi-41.html

[Daniel]

Vitaly Magerya wrote:
> Daniel wrote:
>> Another thing I was trying to figure out, was how to define
>> stream-add in terms of stream-map in such a way that it accepts an
>> arbitrary number of streams. I don't want to repeat what is in the
>> definition of stream-map.
>
> Is this what you're looking for?
>
> (define (stream-add . streams)
> (apply stream-map + streams))

Thanks a lot for your reply. I guess I didn't try it like this, because
apply works on lists. I oversaw the fact that streams are also lists.

> Both stream-map and stream-int are functions, not macros, so
> stream-sin needs to be evaluated prior to function call; thus the
> error. What you need is to delay the evaluation of stream-sin variable
> till it's defined.
>
> Telling you the truth, I don't know of an elegant solution here. One
> solution is to turn stream constructors into macros. Like this:
>
> (define-syntax define-stream-constructor
> (syntax-rules ()
> ((_ (name . args) body)
> (define-syntax name
> (syntax-rules ()
> ((_ . args) body))))))
>
> And then change the stream-int definition to:
>
> (define-stream-constructor (stream-int stream)
> (stream-cons 0 (stream-map * stream (stream-map / integers))))

Very nice! It works perfectly like this. I still need to read up on
define-syntax.

> Or you could just embed the stream-int definition into stream-cos
> definition (it uses stream-cons giving you the needed delay).
>
> Another solution is to use even streams, i.e. represent streams not as
> (cons x (delay y)), but as (delay (cons x (delay y))). Then you could
> just write (delay (force stream-sin)) instead of stream-sin in the
> definition of stream-cos.

So it seems that even streams are somehow more elegant than the odd
ones. I will try to work out how this problem can be solved with odd
streams.

> BTW, that was not a correct cosine. The correct one is:
>
> (define stream-cos
> (stream-map
> -
> (stream-cons 1 (stream-constant 0))
> (stream-int stream-sin)))

Yes, of course. Just a stupid mistake.

> With If you try using macros and correct the cosine definition, the
> result will be:
>
> (0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880)

Yes, it works nicely now. Also defining sine and cosine in terms of
their derivatives works when stream-dif is defined using
define-stream-constructor.

> Finally, I recommend you to look at SRFI 41 [1] for a solid streams
> implementation, and a discussion of how odd and even streams differ.
> Unfortunately SRFI 41 does not expose the delay/force/lazy primitives
> that it uses internally; otherwise wrapping stream-sin into
> stream-lazy would be a solution.
>
> [1] http://srfi.schemers.org/srfi-41/srfi-41.html

I found that one too. Definitely an interesting read. Too bad it doesn't
expose all the details that are necessary for an implementation.

Greetings, Daniel

[Daniel]

For the interested:
I added a Scheme section to
http://rosettacode.org/wiki/Formal_Power_Series. The solution still
uses odd streams. Maybe sometime I will try to implement a solution
using even streams.

Daniel

[Vitaly Magerya]

By the way, did you look at the CL code? It uses odd streams, but avoids
the problem you bumped into by wrapping the sine and cosine definitions
in a delay (which is not completely unlike even streams). In short, you
can use your initial code, but change the final part to:

(define stream-cos-promise
(delay (stream-map
-
(stream-constant 1)
(stream-int (force stream-sin-promise)))))

(define stream-sin-promise
(delay (stream-int (force stream-cos-promise))))

(display (stream-take 10 (force stream-sin-promise)))
(newline)

[Daniel]

Vitaly Magerya wrote:
> By the way, did you look at the CL code? It uses odd streams, but
> avoids the problem you bumped into by wrapping the sine and cosine
> definitions in a delay (which is not completely unlike even streams).

I did have a look at the CL code. I am still trying to understand how it
works.

> In short, you can use your initial code, but change the final part to:
>
> (define stream-cos-promise
> (delay (stream-map
> -
> (stream-constant 1)
> (stream-int (force stream-sin-promise)))))
>
> (define stream-sin-promise
> (delay (stream-int (force stream-cos-promise))))
>
> (display (stream-take 10 (force stream-sin-promise)))
> (newline)

That would be an option. However, when I use define-stream-constructor
for the definition of stream-int, the definitions of sine and cosine
become more elegant:

(define fps-sin
(fps-int fps-cos))

(define fps-cos
(fps-subtract fps-one (fps-int fps-sin)))

It seems there is some kind of conservation law of inelegance :)

In your previous reply you suggested the following:

> Another solution is to use even streams, i.e. represent streams not as
> (cons x (delay y)), but as (delay (cons x (delay y))). Then you could
> just write (delay (force stream-sin)) instead of stream-sin in the
> definition of stream-cos.

Indeed, I don't need define-stream-constructor when I use even streams.
Now I use:

(define-syntax stream-cons
(syntax-rules ()
((_ object stream) (delay (cons object (delay stream))))))

(define (stream-car stream)
(car (force stream)))

(define (stream-cdr stream)
(force (cdr (force stream))))

and:

(define (fps-int fps)
(stream-cons 0 (stream-map * fps (stream-map / stream-integers))))

(define fps-sin
(fps-int (delay (force fps-cos))))

(define fps-cos
(fps-subtract fps-one (fps-int (delay (force fps-sin)))))

Not bad. Thanks for your help!

[Daniel]

Daniel wrote:
> (define (fps-int fps)
> (stream-cons 0 (stream-map * fps (stream-map / stream-integers))))
>
> (define fps-sin
> (fps-int (delay (force fps-cos))))
>
> (define fps-cos
> (fps-subtract fps-one (fps-int (delay (force fps-sin)))))

Just a little update: I can also place the (delay (force )) inside the
definition of fps-int. This way the definitions of fps-sin and fps-cos
become very elegant again...