Scala Programming Language
  1. Scala Programming Language
  2. SI-6415

avoid early evaluation in some Stream's methods

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: Scala 2.10.0-M7
    • Fix Version/s: Scala 2.10.1
    • Component/s: Collections
    • Labels:
      None

      Description

      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.

        Activity

        Hide
        Josh Suereth added a comment -

        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.

        Show
        Josh Suereth added a comment - 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.
        Hide
        Shinya Mochizuki added a comment -

        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.

        Show
        Shinya Mochizuki added a comment - 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.
        Hide
        Jason Zaugg added a comment -

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

        scala> val u = reflect.runtime.universeu: 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 SI-4290

        Show
        Jason Zaugg added a comment - If you want to systematically find methods that should be overriden methods, reflection is pretty handy: scala> val u = reflect.runtime.universeu: 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 SI-4290

          People

          • Assignee:
            Jean-Remi Desjardins
            Reporter:
            Shinya Mochizuki
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development