Elegant breaking from nested loops

I have two nested loops like this:

loop1 do
  ...
  loop2 do
    ...
    break if cond
   ...
  end
  ...
end

Here, the break just gets me out of the inner loop2 but I want to get out of both.
I have a cludge way of doing that, but does Crystal provide an elegant way to break out of both?

If by elegant you mean something like Ruby’s throw + catch, then Crystal doesn’t have this.

You can use break with value, but that wouldn’t be so elegant on it’s own.

i = 0
j = 0

while i < 1_000_000
  r = while j < 1_000_000
    break :exit if j > 10
    j += 1
  end

  break if r == :exit
  i += 1
end

p! i, j
1 Like

return will break out of both. That may force you to enclose the outer loop in a method.

2 Likes

I can do something like this:

flag = false
loop1 do
  ...
  loop2 do
    ...
   (flag = true; break) if cond
   ...
  end
  break if flag
end
....

But by elegant I mean something like:

loop1 do
  ...
  loop2 do
    ...
   break_all if cond
   ...
  end
end
....

Crystal currently doesn’t have this, right?
Would be nice though (equivalent to a compiled old-school GOTO)

Addition:
Or even better:

loop1 do
  ...
  loop2 do
    ...
   break: here if cond
   ...
  end
end
here:
....

Then for nested loops > 2 you can set break points for any subset of loops.

Here’s the original actual code.

loop do                           # for r0..sqrtN primes mark their multiples
    if (r += 1) == rscnt; r = 0; modk += md; k += 1 end # each resgroup params
    next if (prms[k] & (1 << r)) != 0 # skip pc if not prime
    prm_r = res[r]                  # if prime save its residue value
    prime = modk + prm_r            # numerate the prime value
    break if prime > Math.isqrt(val)# exit loop when it's > sqrtN
    res.each do |ri|                # mark prime's multiples in prms
      kn, rn = (prm_r * ri - 2).divmod md # cross-product resgroup|residue
      kpm = k * (prime + ri) + kn   # mark prime’s multiples starting here
      while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
  end end
  # prms now contains the nonprime positions for the prime candidates r0..N
  # extract only primes that are in inputs range into array 'primes'
  primes = [] of UInt64             # create empty dynamic array for primes
  prms.each_with_index do |resgroup, k| # for each kth residue group
    res.each_with_index do |r_i, i| # check for each ith residue in resgroup         
      if resgroup & (1 << i) == 0   # if bit location a prime
        prime = md * k + r_i        # numerate its value, store if in range
        # check if prime has multiple in range, if so keep it, if not don't
        n, rem = start_num.divmod prime # if rem is 0 then start_num multiple of prime
        primes << prime if (res_0 <= prime <= val) && (prime * (n + 1) <= end_num || rem == 0)
  end end end
  prime

I wanted to use the same loop structure in the bottom in the top, but the nested loops required me to do this to retain the expressive form of the bottom.

  flag = false
  prms.each_with_index do |resgroup, k|# for each kth residue group
    break if flag
    res.each_with_index do |prm_r, i|  # check for each ith residue in resgroup         
      next if resgroup & (1 << i) != 0 # if bit location a prime
      prime = md * k + prm_r           # numerate its value, store if in range
      (flag = true; break) if prime > Math.isqrt(val) # exit loop when it's > sqrtN
      res.each do |ri|                 # mark prime's multiples in prms
        kn, rn = (prm_r * ri - 2).divmod md # cross-product resgroup|residue
        kpm = k * (prime + ri) + kn    # mark prime’s multiples starting here
        while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
  end end end
  # prms now contains the nonprime positions for the prime candidates r0..N
  # extract only primes that are in inputs range into array 'primes'
  primes = [] of UInt64             # create empty dynamic array for primes
  prms.each_with_index do |resgroup, k| # for each kth residue group
    res.each_with_index do |r_i, i| # check for each ith residue in resgroup         
      if resgroup & (1 << i) == 0   # if bit location a prime
        prime = md * k + r_i        # numerate its value, store if in range
        # check if prime has multiple in range, if so keep it, if not don't
        n, rem = start_num.divmod prime # if rem is 0 then start_num multiple of prime
        primes << prime if (res_0 <= prime <= val) && (prime * (n + 1) <= end_num || rem == 0)
  end end end
  primes

This works, and compiles to the same size, and runs with the same speed, but the later code expresses more precisely|consistently what’s going on, but gives me this icky feeling when I look at it. But if I could write it as below, it would be easier to understand and feel less icky.

  prms.each_with_index do |resgroup, k|# for each kth residue group
    res.each_with_index do |prm_r, i|  # check for each ith residue in resgroup         
      next if resgroup & (1 << i) != 0 # if bit location a prime
      prime = md * k + prm_r           # numerate its value, store if in range
      break_to here: if prime > Math.isqrt(val) # exit loop when it's > sqrtN
      res.each do |ri|                 # mark prime's multiples in prms
        kn, rn = (prm_r * ri - 2).divmod md # cross-product resgroup|residue
        kpm = k * (prime + ri) + kn    # mark prime’s multiples starting here
        while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
  end end end
  here:
  # prms now contains the nonprime positions for the prime candidates r0..N
  # extract only primes that are in inputs range into array 'primes'
  primes = [] of UInt64             # create empty dynamic array for primes
  prms.each_with_index do |resgroup, k| # for each kth residue group
    res.each_with_index do |r_i, i| # check for each ith residue in resgroup         
      if resgroup & (1 << i) == 0   # if bit location a prime
        prime = md * k + r_i        # numerate its value, store if in range
        # check if prime has multiple in range, if so keep it, if not don't
        n, rem = start_num.divmod prime # if rem is 0 then start_num multiple of prime
        primes << prime if (res_0 <= prime <= val) && (prime * (n + 1) <= end_num || rem == 0)
  end end end
  primes

Another way to do it is to leverage the ability for break/loop to return a value. E.g.

loop do
  b = loop do
    break true if true
  end
    
  break if b
end

Similar to your flag example, but a bit more concise/robust.

1 Like

Yeh, but the desire is to not use two break points.

As I stated above, a method, and then using return is the easiest way to accomplish that.

def mark_nonprimes(nonprimes, residues, val, md, bitn, kmax)
  breakpoint = Math.isqrt(val) 
  nonprimes.each_with_index do |resgroup, k|# for each kth residue group
      residues.each_with_index do |prime_residue, i|  # check for each ith residue in resgroup         
        next if resgroup & (1 << i) != 0 # if bit location a prime
        prime = md * k + prime_residue           # numerate its value, store if in range
        return if prime > breakpoint # exit loop when it's > sqrtN
        residues.each do |ri|                 # mark prime's multiples in primes
          kn, rn = (prime_residue * ri - 2).divmod(md) # cross-product resgroup|residue
          prime_multiple = k * (prime + ri) + kn    # mark prime’s multiples starting here
          while prime_multiple < kmax; 
            nonprimes[prime_multiple] |= bitn[rn]
            prime_multiple += prime
        end 
      end
    end 
  end
end 

I also took the liberty to clarify up the variable naming a bit, but a lot more could be done there.

3 Likes

Thanks for your example. But again, I don’t want to make the code more complex.
It’s clear there’s no simple(r) way to break out of nested loops than to use nested breaks, or my original code that only created one loop to break out of.

Maybe someone from core team can speak to why throw/catch from Ruby was not added to Crystal.

Also related: throw and catch with `SkipMacroException` · Issue #11658 · crystal-lang/crystal · GitHub.

1 Like

I suppose this could be solved with throw/catch but really a more direct solution would be a nesting value for break. In PHP for example, you can pass a number to break which determines how many nested levels of loops it should break.

throw/catch is often critizised for pulling code out of context and making it hard (for humans) to follow control flow.

3 Likes

I was never a big fan of the pass the number of loops to break out of approach, it seems too easy to mess up when moving code around and encourages deep loop nesting in the first place. I’m also unsure how well it fits and interacts with the fact that Crystal loops are really just repeatedly called blocks.

I actually like when a language forces me to solve this by extracting an inner loop or two into a method to achieve the breaking using return. It usually leads to cleaner/easier to follow code IME. Also IME in a language with a lot of list and map data manipulation methods in the standard library like Crystal it’s often easy to avoid deeply nested loops for a more map/reduce focused kind of approach.

8 Likes

There’s also the thing that if we allow breaking from an inner loop then we need to think about how the type inference/flow changes. All type inference done up until the “break” point is carried over outside, which makes the compiler and the language harder to implement and understand.

2 Likes

break can be extended, without breaking code, by, as suggested, using it as

break 2 if cond

where 2 is the number of nested loops, with default as 1, or explicitly like

break here: if cond

where here: is a marker in the code to begin execution from (basically a GOTO).

This is very useful for multidimensional numerical processing algorithms, where if some point in an inner loop requires aborting the whole process, it would make Crystal very attractive to such applications, to be able to use short and clear idiomatic loop structures, like in my example, and have a language defined way to jump out of any level of nesting in a clean, non-hacky, way.

This would have definitely increased my programming productivity to write that top level looping process like the bottom (where it doesn’t break). But I wrote it originally as shown because it was the simplest way to get what I needed within 1 loop.

But think if you’re doing something like a 3 dimensional graphic algorithm, et al. At least initially, to establish functional correctness, you want to mimic the canonical definition of the algorithm as much as possible to establish you’ve satisfied all the edge cases. Once it produces correct results, then you can tear it apart to try to optimize it (speed|memory). But in many applications an idiomatic clean version is all that’s needed, especially if you factor in code maintainability and documentation.

I see being able to idiomatically jump out of any level of loop nesting an attractive feature for Crystal to people doing these type of algorithms, and in general.

1 Like

Will something like the following work for you? Caveat: it breaks to the specific place but holds no value. But perhaps for your uses you can adapt my solution…

class Break < Exception
  getter symbol : Symbol

  def initialize(@symbol : Symbol)
  end
end

def catch(symbol : Symbol)
  begin
    yield
  rescue e : Break
    raise e unless e.symbol == symbol
  end
end

i = 0
j = 0

catch(:here) do
  while i < 1_000
    catch(:there) do
      while j < 1_000
        case rand 100
        when 1
          raise Break.new(:here)
        when 2
          raise Break.new(:there)
        end
        j += 1
      end
    end
    i += 1
  end
end

p! i, j

This said, as mentioned already, gotos have several issues, even if there are some valid uses.

5 Likes

When @matthewmcgarvey was porting Roda to Crystal he actually implemented throw / catch because that’s how Roda bails on processing the request. He uses LibUnwind directly to avoid generating a stack trace, which IIRC was the most expensive part of raising an exception, so it should theoretically be lighter-weight than a typical raise.

I don’t know how well it works in practice because I haven’t tried it, but I remember he did check it pretty thoroughly at the time. But it does exist if you want to try it. :slightly_smiling_face:

3 Likes

If you want to avoid a stack trace, there’s no need to use libunwind directly. You just need to assign a value to the exception’s callstack property before raising.

3 Likes

Found the thread where it was discussed before. I couldn’t remember the details.

I tried it, and it works. But - catch :here || catch(:here) - produces error.

In catchtest.cr:59:3

 59 | catch :here
      ^----
Error: 'catch' is expected to be invoked with a block, but no block was given

In catchtest.cr:59:3

 59 | catch(:here)
      ^----
Error: 'catch' is expected to be invoked with a block, but no block was given

But these work - catch :here {} || catch(:here) {}

Could make visually nicer, something like this:

Break.new(:here)  -> throw :here
catch :here {} -> catch :here

Otherwise it seems to work, at lease in this example.
This definitely would have made writing the original code a snap.
I would urge adding this capability into the language! :+1:

Here’s the test code (made sozpg simpler for testing purposes).

class Break < Exception
  getter symbol : Symbol

  def initialize(@symbol : Symbol)
  end
end

def catch(symbol : Symbol)
  begin
    yield
  rescue e : Break
    raise e unless e.symbol == symbol
  end
end

def sozpg(val)
  md, rscnt = 30u64, 8
  res  = [7,11,13,17,19,23,29,31] 
  bitn = [0,0,0,0,0,1,0,0,0,2,0,4,0,0,0,8,0,16,0,0,0,32,0,0,0,0,0,64,0,128]

  kmax = (val - 2) // md + 1
  prms = Array(UInt8).new(kmax, 0)  

  prms.each_with_index do |resgroup, k|
    res.each_with_index do |prm_r, i|         
      next if resgroup & (1 << i) != 0
      prime = md * k + prm_r
      Break.new(:here) if prime > Math.isqrt(val)
      res.each do |ri|
        kn, rn = (prm_r * ri - 2).divmod md
        kpm = k * (prime + ri) + kn
        while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
  end end end
  catch :here {}
  primes = [2, 3, 5] of UInt64
  prms.each_with_index do |resgroup, k|
    res.each_with_index do |r_i, i|           
       primes << md * k + r_i  if resgroup & (1 << i) == 0
  end end
  primes
end

puts (primes = sozpg(541)).size
print primes

https://play.crystal-lang.org/#/r/cqdy