Re: Question on usage of Stream

Ok, it's good to learn the problem comes from something else and that there is a workaround.

Thanks,
Sebastien

2009/1/7 James Iry <jamesiry [at] gmail [dot] com>
Interesting. 
java.lang.StackOverflowError
    at sun.nio.cs.UTF_8$Encoder.encodeArrayLoop(UTF_8.java:446)
    at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:517)
    at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
    at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252)
    at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
    at java.io.OutputStreamWriter.write(OutputStreamWr...


But since a Stream's tail is lazily evaluated, tail recursion isn't needed in your construction. Note the addition of a foreach in the print here.

scala> def from(n:Int) : Stream[Int] = Stream.cons(n, from(n + 1))
from: (Int)Stream[Int]

scala> from(2) take 3715 foreach print 

....
537063707370837093710371137123713371437153716
scala>



On Tue, Jan 6, 2009 at 2:54 PM, Sebastien Bocq <sebastien [dot] bocq [at] gmail [dot] com> wrote:
Hello,

The following simple example illustrates the usage of streams in the documentation of Stream.scala:

> def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))

It looks very simple but the problem is that obviously the method is not tail recursive and if I do:

> from(2) take 3715 print

I get a java.lang.StackOverflowError

This shows that building infinite streams this way is quite limited :)

But is there a better way?
 
Thanks,
Sébastien


Re: Question on usage of Stream

Added by Seth Tisue on 2009-01-08, 18:07

>>>>> "Sebastien" == Sebastien Bocq writes:

Sebastien> Hello, The following simple example illustrates the usage of
Sebastien> streams in the documentation of Stream.scala:
>> def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))
Sebastien> It looks very simple but the problem is that obviously the
Sebastien> method is not tail recursive and if I do:
>> from(2) take 3715 print
Sebastien> I get a java.lang.StackOverflowError
Sebastien> This shows that building infinite streams this way is quite
Sebastien> limited :)

A side note: with 2.7.2.final, I don't get a stack overflow error until
the 130154th item. I don't know your stack is overflowing so much
earlier.

More importantly: this works fine, no overflow:

scala> from(2).drop(100000000).first

which suggests to me that the source of the overflow in your example
is different than you think. It looks to me like the problem is in
Stream.print(), not in from() itself.

Re: Question on usage of Stream

Added by Sebastien Bocq on 2009-01-08, 23:27
Indeed, James said so too. What he suggested is something like this:

scala> from(2) take 200000 foreach print

which works fine on my machine, so yes, its probably a problem with Stream.print. It is defined like this:

def print(sep: String) {
    if (isEmpty) Console.println("Stream.empty")
    else { Console.print(head); Console.print(sep); tail.print(sep) }
  }

Shouldn't there be a 'final' in front of the method?

Sebastien

2009/1/8 Seth Tisue <seth [at] tisue [dot] net>
>>>>> "Sebastien" == Sebastien Bocq <sebastien [dot] bocq [at] gmail [dot] com> writes:

 Sebastien> Hello, The following simple example illustrates the usage of
 Sebastien> streams in the documentation of Stream.scala:
 >> def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))
 Sebastien> It looks very simple but the problem is that obviously the
 Sebastien> method is not tail recursive and if I do:
 >> from(2) take 3715 print
 Sebastien> I get a java.lang.StackOverflowError
 Sebastien> This shows that building infinite streams this way is quite
 Sebastien> limited :)

A side note: with 2.7.2.final, I don't get a stack overflow error until
the 130154th item.  I don't know your stack is overflowing so much
earlier.

More importantly: this works fine, no overflow:

scala> from(2).drop(100000000).first

which suggests to me that the source of the overflow in your example
is different than you think.  It looks to me like the problem is in
Stream.print(), not in from() itself.

--
Seth Tisue / http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

Re: Question on usage of Stream

Added by Seth Tisue on 2009-01-08, 23:47

>>>>> "Sebastien" == Sebastien Bocq writes:

Sebastien> Indeed, James said so too. What is suggest is something like
Sebastien> this:
scala> from(2) take 200000 foreach print

Sebastien> which works fine on my machine, so yes, its probably a
Sebastien> problem with Stream.print. It is defined like this:

Sebastien> def print(sep: String) { if (isEmpty)
Sebastien> Console.println("Stream.empty") else { Console.print(head);
Sebastien> Console.print(sep); tail.print(sep) } }

Sebastien> Shouldn't there be a 'final' in front of the method?

I imagine that would fix the problem, but it would also tie the hands of
people wanting to subclass Stream. I think the standard solution in
these cases is to nest a locally defined truly tail recursive function
inside the outer definition.

Re: Question on usage of Stream

Added by Sebastien Bocq on 2009-01-09, 00:47
That makes more sense indeed, shall I file a bug?

Sebastien

2009/1/8 Seth Tisue <seth [at] tisue [dot] net>
>>>>> "Sebastien" == Sebastien Bocq <sebastien [dot] bocq [at] gmail [dot] com> writes:

 Sebastien> Indeed, James said so too. What is suggest is something like
 Sebastien> this:
 scala> from(2) take 200000 foreach print

 Sebastien> which works fine on my machine, so yes, its probably a
 Sebastien> problem with Stream.print. It is defined like this:

 Sebastien> def print(sep: String) { if (isEmpty)
 Sebastien> Console.println("Stream.empty") else { Console.print(head);
 Sebastien> Console.print(sep); tail.print(sep) } }

 Sebastien> Shouldn't there be a 'final' in front of the method?

I imagine that would fix the problem, but it would also tie the hands of
people wanting to subclass Stream.  I think the standard solution in
these cases is to nest a locally defined truly tail recursive function
inside the outer definition.

--
Seth Tisue / http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/


Re: Question on usage of Stream

Added by Sebastien Bocq on 2009-01-10, 12:07
I created a ticket: http://lampsvn.epfl.ch/trac/scala/ticket/1631

Thanks,
Sebastien

2009/1/9 Sebastien Bocq <sebastien [dot] bocq [at] gmail [dot] com>
That makes more sense indeed, shall I file a bug?

Sebastien

2009/1/8 Seth Tisue <seth [at] tisue [dot] net>
>>>>> "Sebastien" == Sebastien Bocq <sebastien [dot] bocq [at] gmail [dot] com> writes:

 Sebastien> Indeed, James said so too. What is suggest is something like
 Sebastien> this:
 scala> from(2) take 200000 foreach print

 Sebastien> which works fine on my machine, so yes, its probably a
 Sebastien> problem with Stream.print. It is defined like this:

 Sebastien> def print(sep: String) { if (isEmpty)
 Sebastien> Console.println("Stream.empty") else { Console.print(head);
 Sebastien> Console.print(sep); tail.print(sep) } }

 Sebastien> Shouldn't there be a 'final' in front of the method?

I imagine that would fix the problem, but it would also tie the hands of
people wanting to subclass Stream.  I think the standard solution in
these cases is to nest a locally defined truly tail recursive function
inside the outer definition.

--
Seth Tisue / http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/



Copyright © 2013 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland