Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

avoid early evaluation in some Stream's methods #6415

Closed
scabug opened this issue Sep 22, 2012 · 4 comments
Closed

avoid early evaluation in some Stream's methods #6415

scabug opened this issue Sep 22, 2012 · 4 comments
Assignees
Milestone

Comments

@scabug
Copy link

@scabug scabug commented Sep 22, 2012

scala> lazy val x = \{ println("evaluated"); 1 }
x: Int = <lazy>

scala> 0 #:: x #:: Stream.empty
res0: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res0.isDefinedAt(0)
evaluated
res1: Boolean = true

I think that It is not lazy to call GenTraversableLike#tail in LinearSeqOptimized#lengthCompare.

@scabug
Copy link
Author

@scabug scabug commented Sep 22, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6415?orig=1
Reporter: Shinya Mochizuki (lyrical_logical)
Affected Versions: 2.10.0-M7

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 25, 2012

@jsuereth said:
Just a note on laziness:

While we attempt to be as lazy as possible in stream, it's more than likely that size/take/indexOf, etc. may reify one too many terms of the stream. This is the case in many of the implementations because of how 'escaping' loops work. We offer no guarantees on when we evaluate things, only that we defer as long as we can.

I'm migrating this to an enhancement, since the current behavior isn't 'broken'. That said, we'll see if there's anything we can do to improve the laziness.

Loading

@scabug
Copy link
Author

@scabug scabug commented Sep 29, 2012

Shinya Mochizuki (lyrical_logical) said:
Yes, I collectly agree with you.
Stream's laziness isn't specified by any documents. We should not assume many assumption(contract) of methods.

I think that almost early evaluation is caused by unnecessary GenTraversableLike#tail method calling.
It is good to remove such method calling for other classes without need unnecessary method calliing, maybe such class dosen't exist.

Loading

@scabug
Copy link
Author

@scabug scabug commented Dec 12, 2012

@retronym said:
If you want to systematically find methods that should be overriden methods, reflection is pretty handy:

scala> val u = reflect.runtime.universe
u: scala.reflect.api.JavaUniverse = scala.reflect.runtime.JavaUniverse@5d38c394

scala> val t = u.typeOf[Stream[Any]]
t: u.Type = scala.Stream[Any]

scala> println(t.members.map(sym => (sym.name.decoded, sym.owner.fullName, t.baseType(sym.owner), t.baseClasses.indexOf(sym.owner))).toSeq.sortBy(t => (-t._4, t._1)).map { case (name, bt, _, _) => f"$name%20s inherited from ${bt.toString.replace("scala.collection", "s.c")}" }.mkString("\n"))
                  != inherited from scala.Any
                  == inherited from scala.Any
        asInstanceOf inherited from scala.Any
        isInstanceOf inherited from scala.Any
                  != inherited from java.lang.Object
                  ## inherited from java.lang.Object
       $asInstanceOf inherited from java.lang.Object
       $isInstanceOf inherited from java.lang.Object
                  == inherited from java.lang.Object
               clone inherited from java.lang.Object
                  eq inherited from java.lang.Object
            finalize inherited from java.lang.Object
            getClass inherited from java.lang.Object
                  ne inherited from java.lang.Object
              notify inherited from java.lang.Object
           notifyAll inherited from java.lang.Object
        synchronized inherited from java.lang.Object
                wait inherited from java.lang.Object
                wait inherited from java.lang.Object
                wait inherited from java.lang.Object
                 /:\ inherited from s.c.GenTraversableOnce
                  /: inherited from s.c.TraversableOnce
                  :\ inherited from s.c.TraversableOnce
           addString inherited from s.c.TraversableOnce
           addString inherited from s.c.TraversableOnce
           aggregate inherited from s.c.TraversableOnce
        collectFirst inherited from s.c.TraversableOnce
         copyToArray inherited from s.c.TraversableOnce
         copyToArray inherited from s.c.TraversableOnce
        copyToBuffer inherited from s.c.TraversableOnce
               count inherited from s.c.TraversableOnce
                fold inherited from s.c.TraversableOnce
                 max inherited from s.c.TraversableOnce
               maxBy inherited from s.c.TraversableOnce
                 min inherited from s.c.TraversableOnce
               minBy inherited from s.c.TraversableOnce
            nonEmpty inherited from s.c.TraversableOnce
             product inherited from s.c.TraversableOnce
              reduce inherited from s.c.TraversableOnce
    reduceLeftOption inherited from s.c.TraversableOnce
        reduceOption inherited from s.c.TraversableOnce
   reduceRightOption inherited from s.c.TraversableOnce
            reversed inherited from s.c.TraversableOnce
                 sum inherited from s.c.TraversableOnce
             toArray inherited from s.c.TraversableOnce
            toBuffer inherited from s.c.TraversableOnce
        toIndexedSeq inherited from s.c.TraversableOnce
              toList inherited from s.c.TraversableOnce
               toMap inherited from s.c.TraversableOnce
               toSet inherited from s.c.TraversableOnce
            toVector inherited from s.c.TraversableOnce
                 par inherited from s.c.Parallelizable
                 ++: inherited from s.c.TraversableLike
                 ++: inherited from s.c.TraversableLike
                Self inherited from s.c.TraversableLike
          WithFilter inherited from s.c.TraversableLike
           filterNot inherited from s.c.TraversableLike
             groupBy inherited from s.c.TraversableLike
          headOption inherited from s.c.TraversableLike
               inits inherited from s.c.TraversableLike
  isTraversableAgain inherited from s.c.TraversableLike
   iterateUntilEmpty inherited from s.c.TraversableLike
          lastOption inherited from s.c.TraversableLike
                repr inherited from s.c.TraversableLike
                scan inherited from s.c.TraversableLike
           scanRight inherited from s.c.TraversableLike
 sliceWithKnownBound inherited from s.c.TraversableLike
 sliceWithKnownDelta inherited from s.c.TraversableLike
                tail inherited from s.c.TraversableLike
               tails inherited from s.c.TraversableLike
                  to inherited from s.c.TraversableLike
       toTraversable inherited from s.c.TraversableLike
      genericBuilder inherited from s.c.generic.GenericTraversableTemplate
          newBuilder inherited from s.c.generic.GenericTraversableTemplate
          sequential inherited from s.c.generic.GenericTraversableTemplate
           transpose inherited from s.c.generic.GenericTraversableTemplate
               unzip inherited from s.c.generic.GenericTraversableTemplate
              unzip3 inherited from s.c.generic.GenericTraversableTemplate
            canEqual inherited from s.c.IterableLike
         copyToArray inherited from s.c.IterableLike
             grouped inherited from s.c.IterableLike
                head inherited from s.c.IterableLike
             sliding inherited from s.c.IterableLike
             sliding inherited from s.c.IterableLike
          toIterable inherited from s.c.IterableLike
          toIterator inherited from s.c.IterableLike
              zipAll inherited from s.c.IterableLike
             compose inherited from scala.Function1
             andThen inherited from scala.PartialFunction
         applyOrElse inherited from scala.PartialFunction
                lift inherited from scala.PartialFunction
              orElse inherited from scala.PartialFunction
             runWith inherited from scala.PartialFunction
              equals inherited from s.c.GenSeqLike
             indexOf inherited from s.c.GenSeqLike
             indexOf inherited from s.c.GenSeqLike
          indexWhere inherited from s.c.GenSeqLike
         lastIndexOf inherited from s.c.GenSeqLike
         lastIndexOf inherited from s.c.GenSeqLike
      lastIndexWhere inherited from s.c.GenSeqLike
        prefixLength inherited from s.c.GenSeqLike
          startsWith inherited from s.c.GenSeqLike
                  :+ inherited from s.c.SeqLike
     CombinationsItr inherited from s.c.SeqLike
     PermutationsItr inherited from s.c.SeqLike
        combinations inherited from s.c.SeqLike
       containsSlice inherited from s.c.SeqLike
                diff inherited from s.c.SeqLike
            endsWith inherited from s.c.SeqLike
        indexOfSlice inherited from s.c.SeqLike
        indexOfSlice inherited from s.c.SeqLike
             indices inherited from s.c.SeqLike
           intersect inherited from s.c.SeqLike
             isEmpty inherited from s.c.SeqLike
    lastIndexOfSlice inherited from s.c.SeqLike
    lastIndexOfSlice inherited from s.c.SeqLike
           occCounts inherited from s.c.SeqLike
               patch inherited from s.c.SeqLike
        permutations inherited from s.c.SeqLike
     reverseIterator inherited from s.c.SeqLike
          reverseMap inherited from s.c.SeqLike
                size inherited from s.c.SeqLike
              sortBy inherited from s.c.SeqLike
            sortWith inherited from s.c.SeqLike
              sorted inherited from s.c.SeqLike
          startsWith inherited from s.c.SeqLike
               union inherited from s.c.SeqLike
             updated inherited from s.c.SeqLike
                view inherited from s.c.SeqLike
         parCombiner inherited from s.c.immutable.Seq
               toSeq inherited from s.c.immutable.Seq
         corresponds inherited from s.c.LinearSeqLike
            hashCode inherited from s.c.LinearSeqLike
      thisCollection inherited from s.c.LinearSeqLike
        toCollection inherited from s.c.LinearSeqLike
                 seq inherited from s.c.immutable.LinearSeq
              $init$ inherited from s.c.LinearSeqOptimized
               apply inherited from s.c.LinearSeqOptimized
            contains inherited from s.c.LinearSeqOptimized
           dropRight inherited from s.c.LinearSeqOptimized
              exists inherited from s.c.LinearSeqOptimized
                find inherited from s.c.LinearSeqOptimized
           foldRight inherited from s.c.LinearSeqOptimized
              forall inherited from s.c.LinearSeqOptimized
          indexWhere inherited from s.c.LinearSeqOptimized
         isDefinedAt inherited from s.c.LinearSeqOptimized
                last inherited from s.c.LinearSeqOptimized
      lastIndexWhere inherited from s.c.LinearSeqOptimized
       lengthCompare inherited from s.c.LinearSeqOptimized
         reduceRight inherited from s.c.LinearSeqOptimized
        sameElements inherited from s.c.LinearSeqOptimized
       segmentLength inherited from s.c.LinearSeqOptimized
                span inherited from s.c.LinearSeqOptimized
  super$sameElements inherited from s.c.LinearSeqOptimized
                  ++ inherited from s.c.immutable.Stream
                  +: inherited from s.c.immutable.Stream
              <init> inherited from s.c.immutable.Stream
    StreamWithFilter inherited from s.c.immutable.Stream
           addString inherited from s.c.immutable.Stream
              append inherited from s.c.immutable.Stream
            asStream inherited from s.c.immutable.Stream
              asThat inherited from s.c.immutable.Stream
             collect inherited from s.c.immutable.Stream
           companion inherited from s.c.immutable.Stream
            distinct inherited from s.c.immutable.Stream
                drop inherited from s.c.immutable.Stream
           dropWhile inherited from s.c.immutable.Stream
              filter inherited from s.c.immutable.Stream
             flatMap inherited from s.c.immutable.Stream
             flatten inherited from s.c.immutable.Stream
            foldLeft inherited from s.c.immutable.Stream
               force inherited from s.c.immutable.Stream
             foreach inherited from s.c.immutable.Stream
     hasDefiniteSize inherited from s.c.immutable.Stream
                init inherited from s.c.immutable.Stream
     isStreamBuilder inherited from s.c.immutable.Stream
            iterator inherited from s.c.immutable.Stream
              length inherited from s.c.immutable.Stream
                 map inherited from s.c.immutable.Stream
            mkString inherited from s.c.immutable.Stream
            mkString inherited from s.c.immutable.Stream
            mkString inherited from s.c.immutable.Stream
               padTo inherited from s.c.immutable.Stream
           partition inherited from s.c.immutable.Stream
               print inherited from s.c.immutable.Stream
               print inherited from s.c.immutable.Stream
          reduceLeft inherited from s.c.immutable.Stream
             reverse inherited from s.c.immutable.Stream
            scanLeft inherited from s.c.immutable.Stream
               slice inherited from s.c.immutable.Stream
             splitAt inherited from s.c.immutable.Stream
        stringPrefix inherited from s.c.immutable.Stream
         tailDefined inherited from s.c.immutable.Stream
                take inherited from s.c.immutable.Stream
           takeRight inherited from s.c.immutable.Stream
           takeWhile inherited from s.c.immutable.Stream
            toStream inherited from s.c.immutable.Stream
            toString inherited from s.c.immutable.Stream
                view inherited from s.c.immutable.Stream
          withFilter inherited from s.c.immutable.Stream
                 zip inherited from s.c.immutable.Stream
        zipWithIndex inherited from s.c.immutable.Stream

For Stream, I'm almost willing to add a test case that pins down this output, so that each new method added above it fails the build and forces us to consciously choose whether or not to override.

For related reading, see #4290

Loading

@scabug scabug closed this Jan 6, 2013
@scabug scabug added this to the 2.10.1 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants