Prev: Emacs Lisp's print, princ, prin1, format, message (tutorial)
Next: Breaking up a long string literal
From: Yongwei Xing on 12 Aug 2010 04:29
Hi all

I am reading the SICP recently. I have a question about the stream in
Chapter 3.

There is an example about the infinite stream like integers. When I
use the stream-ref to get the 100th,200th,500th and 3000th value of
this integers stream, everything is OK. When I try to get the 5000th
value of this integers, it threw a Stack Overflow error.

So, what's wrong with it? If there is any methond to make it a really
infinite stream?
When I try to run the code like it
(loop for i from 1 to 1000000 do (print (stream-ref integers i)))
it would stop when i is about 5000. Is there any way to solve this
problem?

Best Regards,
From: Charles on 12 Aug 2010 06:07
On Aug 12, 4:29 am, Yongwei Xing <jdxyw2...(a)gmail.com> wrote:
> Hi all
>
> I am reading the SICP recently. I have a question about the stream in
> Chapter 3.
>
> There is an example about the infinite stream like integers. When I
> use the stream-ref to get the 100th,200th,500th and 3000th value of
> this integers stream, everything is OK. When I try to get the 5000th
> value of this integers, it threw a Stack Overflow error.
>
> So, what's wrong with it? If there is any methond to make it a really
> infinite stream?
> When I try to run the code like it
> (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
> it would stop when i is about 5000. Is there any way to solve this
> problem?
>
> Best Regards,

Your Scheme environment should have a knob for changing the stack
size, which is what you'll need to do, unless there are some purely
heap based implementations I don't know about. Changing the stack size
is highly implementation-dependent, though. Read the documentation for
yours.
From: Nils M Holm on 12 Aug 2010 06:32
Charles <aloofwizard(a)gmail.com> wrote:
> Your Scheme environment should have a knob for changing the stack
> size, which is what you'll need to do, unless there are some purely
> heap based implementations I don't know about. [...]

Scheme 9 (see below homepage) allocates everything on the heap.
Haven't tried the SICP code, though.

--
Nils M Holm | http://t3x.org
From: Pascal J. Bourguignon on 12 Aug 2010 08:17
Yongwei Xing <jdxyw2004(a)gmail.com> writes:

> Hi all
>
> I am reading the SICP recently. I have a question about the stream in
> Chapter 3.
>
> There is an example about the infinite stream like integers. When I
> use the stream-ref to get the 100th,200th,500th and 3000th value of
> this integers stream, everything is OK. When I try to get the 5000th
> value of this integers, it threw a Stack Overflow error.
>
> So, what's wrong with it? If there is any methond to make it a really
> infinite stream?
> When I try to run the code like it
> (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
> it would stop when i is about 5000. Is there any way to solve this
> problem?

I assume you're using this definition of stream-ref:

(defun stream-ref (s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))

Unfortunately, while this is a tail-recursive function, Common Lisp
doesn't enforce tail-calls optimization.

Notably, if you're using clisp, the interpreter doesn't have it. You
have to compile functions in clisp to get some level of tail recursive
call optiomization. Other implementations may more often implement TCO.

In any case, you can rewrite this function in an iterative way instead
of recursive.
Read again section "1.2 Procedures and the Processes They Generate"


(defun stream-ref (s n)
(loop
:for i :from n :downto 0
:for c = s :then (stream-cdr c)
:finally (return (stream-car c))))


--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Yongwei Xing on 12 Aug 2010 09:41
On Aug 12, 8:17 pm, p...(a)informatimago.com (Pascal J. Bourguignon)
wrote:
> Yongwei Xing <jdxyw2...(a)gmail.com> writes:
> > Hi all
>
> > I am reading the SICP recently. I have a question about the stream in
> > Chapter 3.
>
> > There is an example about the infinite stream like integers. When I
> > use the stream-ref to get the 100th,200th,500th and 3000th value of
> > this integers stream, everything is OK. When I try to get the 5000th
> > value of this integers, it threw a Stack Overflow error.
>
> > So, what's wrong with it? If there is any methond to make it a really
> > infinite stream?
> > When I try to run the code like it
> > (loop for i from 1 to 1000000 do (print (stream-ref integers i)))
> > it would stop when i is about 5000. Is there any way to solve this
> > problem?
>
> I assume you're using this definition of stream-ref:
>
>     (defun stream-ref (s n)
>       (if (= n 0)
>         (stream-car s)
>         (stream-ref (stream-cdr s) (- n 1))))
>
> Unfortunately, while this is a tail-recursive function, Common Lisp
> doesn't enforce tail-calls optimization.
>
> Notably, if you're using clisp, the interpreter doesn't have it.  You
> have to compile functions in clisp to get some level of tail recursive
> call optiomization.  Other implementations may more often implement TCO..
>
> In any case, you can rewrite this function in an iterative way instead
> of recursive.
> Read again section "1.2  Procedures and the Processes They Generate"
>
>     (defun stream-ref (s n)
>       (loop
>          :for i :from n :downto 0
>          :for c = s :then (stream-cdr c)
>          :finally (return (stream-car c))))
>
> --
> __Pascal Bourguignon__                    http://www.informatimago.com/

Yes, you are right, the code you paste is exactly what I used.
I am using the clisp 2.49 now.
 |  Next  |  Last
Pages: 1 2
Prev: Emacs Lisp's print, princ, prin1, format, message (tutorial)
Next: Breaking up a long string literal