# 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`)

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: https://github.com/crystal-lang/crystal/issues/11658.

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, `goto`s 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.

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!

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