Escaping from search

Another interesting way to escape from a search is using a laziness.

def somePredicate(a:Int,b:Int,c:Int):Boolean = {
  (a*a + b*b == c*c) && (c*c - b*b == a*a)
}

val domain = List.tabulate(100){n=>n+2}
val data1 = for {tail1 <- domain.tails
                 if tail1.nonEmpty
                 a = tail1.head
                 tail2 <- tail1.tail.tails
                 if tail2.nonEmpty
                 b = tail2.head
                 c <- tail2.view
                 //_ = println(s"testing $a, $b, $c")
                 if somePredicate(a, b, c)
                 } yield (a,b,c)

Now data1.next() will compute exactly enough of the loop to find an a,b,c satisfying the predicate.

But the following fails. It computes a Vector of all such triples. It’s not clear to me why it fails.

val data2 = for {c <- (1 to 100)
                 b <- (1 to c)
                 a <- (1 to b).view
                 //_ = println(s"testing $a, $b, $c")
                 if somePredicate(a, b, c)
                 } yield (a,b,c)
1 Like

https://github.com/scala/scala-collection-contrib provides an extension method lazyFoldLeft which probably does what you want.

1 Like

In the introduction to Scala course which I just finished teaching, I didn’t touch the issue of breaking out of a loop, neither did I talk about exceptions nor return. I assigned a final project where the students needed to find arrangements of cards which satisfy certain predicates, and a majority of the 15 students used return to break out of functions once finding the arrangement they sought.

This is yet more evidence, that such a facility is basic, not seen as an advanced feature, and is missing from the language. People who need it find a way.

Another piece of evidence (not conclusive evidence admittedly) is that the Scala standard library makes use of such a ad-hoc facility (the brittle non-reentrant breakable/break described above). If users wish to use standard library facility, they are forced to write imperative code using var.

Nonlocal returns http://dotty.epfl.ch/docs/reference/dropped-features/nonlocal-returns.html worked only because your students used them in strict and synchronous transformations. Look at this code:

def process(seq: Seq[Int]): Seq[Int] = {
  seq.map(num => if (num == 5) return Vector(0) else num + 1)
}

println(process(Seq(1, 2, 3)).mkString(", "))
println(process(Seq(1, 3, 5)).mkString(", "))
println(process(LazyList(1, 2, 3)).mkString(", "))
println(process(LazyList(1, 3, 5)).mkString(", "))

It throws an exception on the last line: https://scastie.scala-lang.org/SXJFVgcHRaCADz3X2RXglg
Is that OK for you?

1 Like

I find that as an evidence that you should have teach them that in Scala the return keyword shouldn’t be used in the 99% of the time (I justa assume it doesn’t exist).

@tarsa shows another great example of why such a feature shouldn’t be used (as well as why using Seqs is bad).

Edit: added a note that it sometimes has to be used as @Russ mentioned, I just think it is almost never and certainly not something you should care when learning (again my opinion).

No, this has been discussed before, and the “return” keyword has legitimate uses.

No, it really doesn’t. It proves that return is common in other languages, which tend to be much more imperatively-focused. So they are used to it from those other languages, so they reflexively want to use it, because they are used to imperative programming.

Scala’s idiom is different. Yes, return has valid uses – but I still maintain that it should be considered an edge case, and only used by advanced users. When used by beginners, it tends to trip them up and cause bugs (I hit a case of this at work just the other day), because it isn’t as easy to use correctly as they think it is. That’s because Scala thinks differently than those other languages, and you wind up with more complex code structures.

As I often point out: in eight years of full-time Scala, I have never used return, and rarely felt the lack. You have to develop different habits, but that’s what learning another language well is about…

1 Like

That’s one way to look it. The way I see it, “return” is like “var” in that both should be avoided in most cases, but they still have perfectly appropriate and acceptable use cases.

If the entire purpose of a function is to iterate through a sequence to find some value, why not just return that value as soon as it is found?

Here is an example. I have a Vector of altitude segments (climbing, level, or descent), and I want to find the index of the segment at a given distance along the route:

def altSegmentIndex(dist: Scalar): Int = {
  for ((p, i) <- altSegments.zipWithIndex.reverse)
    if (dist >= p.dist) return i
  0
  }

Edit: I just realized that I can use indexWhere for this. But I wonder if that function itself uses a return.

Also, I often find myself developing algorithms involving aircraft trajectories, where the algorithm is undefined or does nothing useful if a particular Vector is empty or has less than a certain number of elements. Why shouldn’t I just check the length up front and return an appropriate value if the length is insufficient? Then I don’t have to worry about accessing the head of an empty Vector, for example. Yes, of course I could avoid return by using an additonal nesting level, but that is just unnecessary complexity as far as I am concerned. I realize that others see it differently, but in the end it is just a matter of style. To my way of thinking, seeing the return right up front makes the intent crystal clear, whereas additional nesting can quickly get confusing.

I agree that return should be avoided. I never covered this in class, and I suppose that since I failed to mention why to avoid it, some students used it in their final projects.

As I mentioned before, since return doesn’t work, or at least its semantics are difficult to explain, I believe there should be some recommended and robust way to perform non-local exit.

@jducoeur, Perhaps I misstated. I am not claiming return should be used. I’m rather claiming that a robust non-local-exit is important and missing. The fact that the scala library developers implemented a brittle one, and used it in find and perhaps elsewhere is further evidence. In order to use the block/break from the standard library we are forced to write imperative code using var.

For my own purposes, I can use block which I defined in the original post, which accepts a continuation body:(A=>Nothing)=>A as argument. However, I would not want to try to explain this to beginner students.

Is there a cousin of find which takes an additional function:

def cousinOfFind[A,B](seq:Findable[A], f:A=>B, predicate:B=>Boolean):(A,B) ...

which searches some input (probably more general than Seq) for an element, a, for which f(a) satisfies the predicate, and when found, returns the pair (a,f(a)), the logic being that find almost does this but only returns a, forcing the caller to call f(a) again which might be expensive or impossible to re-compute. It may be impossible in the case that it depends on an iterator.

That kind of illustrates the problem right there. The issue with non-local exit isn’t implementation, it’s definition. In a relatively deep language like Scala, where closures and nested functions are totally routine, what does an easy-to-use, robust, non-local exit look like?

That’s not a rhetorical question, and there might be a good answer, but I haven’t seen it yet…

1 Like

Deprecated: Nonlocal Returns shows the replacement of non-local returns:

import scala.util.control.NonLocalReturns._

returning { ... throwReturn(x) ... }

That’s how non-local returns work today (except they don’t create a closure), but is written explicitly.

1 Like

This one also throws an exception and it doesn’t use return. I don’t really understand why.

BTW what is the meaning of the error? java.lang.ExceptionInInitializerError

But returning/throwReturn is still brittle, right?, as the throwReturn may not be lexically within the returning. It doesn’t seem to provide a way for the programmer to return from any of several concentric returning calls. — a problem which continuations are intended to solve.

You’ve just emulated non-local returns. The mechanics and problem are the same. process returns before elements were mapped (because LazyList is lazy, i.e. element are computed on first usage) and actual mapping happens elsewhere, in this case during .mkString.

returning/throwReturn is exactly what non-local returns are today, just written explicitly. I’ll show a disassembly soon to show what’s going on.

I’m sorry I don’t know what this means. What are non-local returns today? Are you talking about return or about throw/catch?

Source code in Scala:

class Demo {
  def withLocalReturn(nameOpt: Option[String]): String = {
    nameOpt match {
      case Some(name) => return s"Hello, $name!"
      case None => "Hello!"
    }
  }

  def withNonLocalReturn(nameOpt: Option[String]): String = {
    nameOpt.map { name =>
      return s"Hello, $name!"
    }.getOrElse("Hello!")
  }
}

After compilation to *.class file and decompilation to *.java code IntelliJ shows that:

//decompiled from Demo.class
import java.lang.invoke.SerializedLambda;
import scala.MatchError;
import scala.Option;
import scala.Some;
import scala.None.;
import scala.reflect.ScalaSignature;
import scala.runtime.NonLocalReturnControl;

@ScalaSignature(
   bytes = "\u0006\u0005!2A\u0001B\u0003\u0001\u0011!)q\u0002\u0001C\u0001!!)1\u0003\u0001C\u0001)!)Q\u0005\u0001C\u0001M\t!A)Z7p\u0015\u00051\u0011a\u0002\u001ff[B$\u0018PP\u0002\u0001'\t\u0001\u0011\u0002\u0005\u0002\u000b\u001b5\t1BC\u0001\r\u0003\u0015\u00198-\u00197b\u0013\tq1B\u0001\u0004B]f\u0014VMZ\u0001\u0007y%t\u0017\u000e\u001e \u0015\u0003E\u0001\"A\u0005\u0001\u000e\u0003\u0015\tqb^5uQ2{7-\u00197SKR,(O\u001c\u000b\u0003+\u0001\u0002\"AF\u000f\u000f\u0005]Y\u0002C\u0001\r\f\u001b\u0005I\"B\u0001\u000e\b\u0003\u0019a$o\\8u}%\u0011AdC\u0001\u0007!J,G-\u001a4\n\u0005yy\"AB*ue&twM\u0003\u0002\u001d\u0017!)\u0011E\u0001a\u0001E\u00059a.Y7f\u001fB$\bc\u0001\u0006$+%\u0011Ae\u0003\u0002\u0007\u001fB$\u0018n\u001c8\u0002%]LG\u000f\u001b(p]2{7-\u00197SKR,(O\u001c\u000b\u0003+\u001dBQ!I\u0002A\u0002\t\u0002"
)
public class Demo {
   public String withLocalReturn(final Option nameOpt) {
      if (nameOpt instanceof Some) {
         Some var4 = (Some)nameOpt;
         String name = (String)var4.value();
         return (new StringBuilder(8)).append("Hello, ").append(name).append("!").toString();
      } else if (.MODULE$.equals(nameOpt)) {
         String var2 = "Hello!";
         return var2;
      } else {
         throw new MatchError(nameOpt);
      }
   }

   public String withNonLocalReturn(final Option nameOpt) {
      Object var2 = new Object();

      String var10000;
      try {
         var10000 = (String)nameOpt.map((name) -> {
            throw new NonLocalReturnControl(var2, (new StringBuilder(8)).append("Hello, ").append(name).append("!").toString());
         }).getOrElse(() -> {
            return "Hello!";
         });
      } catch (NonLocalReturnControl var4) {
         if (var4.key() != var2) {
            throw var4;
         }

         var10000 = (String)var4.value();
      }

      return var10000;
   }

   // $FF: synthetic method
   private static Object $deserializeLambda$(SerializedLambda var0) {
      return Class.lambdaDeserialize<invokedynamic>(var0);
   }
}

As you see, the withNonLocalReturn contains try/catch with throw inside a lambda. If you move that lambda elsewhere then returning exception won’t be caught by that try/catch mechanism as it only works when the exception is thown during execution of that try/catch block.

This example is indeed enlightening. I admit, I don’t understand why it doesn’t work.
In my code, when the instance of the NonLocalExit class is constructed, what is the value of body which initializes the ident slot of the instance? Why doesn’t the catch catch it?

Perhaps in light of your recent post, perhaps the problem is that the exception gets through outside the dynamic extent of the catch ???

Here’s even simpler example:

object Demo {
  def main(args: Array[String]): Unit = {
    val fn = {
      try { // try catches exceptions thrown during its evaluation
        // but here we're returning a function without evaluating it
        () => throw new Exception("my exception")
      } catch {
        case e: Exception =>
          println(s"Exception caught: $e")
          () => ()
      }
    }
    // here we run the function with a `throw` inside
    // but we aren't in a try/catch block, so we get unhandled exception
    fn()
  }
}

If you look closely then you’ll see that it’s exactly the same mechanism as visible in the decompiled code in my post above.