Nested Loops, and Keeping Them Readable

Part I · Module 9 · Chapter 9.10 · Nested Loops, and Keeping Them Readable

1. A loop inside a loop

Nothing special is needed — the inner loop is just a command in the outer one's body:

set table {{1 2} {3 4} {5 6}}

foreach row $table {
    foreach cell $row {
        puts -nonewline "$cell "
    }
    puts ""
}

1 2 
3 4 
5 6

This is the natural shape for the nested lists of Chapter 6.11: the outer loop takes a row, the inner one takes a cell.

With an index on each level when you need the position:

set r 0
foreach row $table {
    set c 0
    foreach cell $row {
        puts "($r,$c) = $cell"
        incr c
    }
    incr r
}

(0,0) = 1
(0,1) = 2
(1,0) = 3
(1,1) = 4
(2,0) = 5
(2,1) = 6

2. break and continue affect only the innermost loop

This is the rule to see rather than be told:

set table {{1 2} {3 4} {5 6}}

foreach row $table {
    foreach cell $row {
        if {$cell == 3} break
        puts -nonewline "$cell "
    }
}
puts ""

1 2 5 6

Read the output. The break fired on the row {3 4} and ended the inner loop for that row only — 4 was skipped. The outer loop then carried on to {5 6}, which is why 5 and 6 are there. If break had ended both loops the output would have stopped at 1 2.

continue is the same:

foreach row $table {
    foreach cell $row {
        if {$cell % 2 == 0} continue
        puts -nonewline "$cell "
    }
}
puts ""

1 3 5

Each even cell was skipped within its own row; no row was abandoned.

3. Leaving both loops: the flag

The mechanical answer:

set table {{1 2} {3 4} {5 6}}

set done 0
foreach row $table {
    if {$done} break
    foreach cell $row {
        if {$cell == 3} { set done 1 ; break }
        puts -nonewline "$cell "
    }
}
puts ""

1 2

It works. It costs a variable, an extra test at the top of the outer loop, and a reader who has to find all three pieces before they can be sure the loop ends where they think.

4. Leaving both loops: return

Inside a procedure, return leaves everything at once:

proc find_cell {table want} {
    set r 0
    foreach row $table {
        set c 0
        foreach cell $row {
            if {$cell == $want} {
                return "row $r col $c"
            }
            incr c
        }
        incr r
    }
    return "not found"
}

puts [find_cell {{1 2} {3 4} {5 6}} 4]
puts [find_cell {{1 2} {3 4} {5 6}} 99]

row 1 col 1
not found

No flag, no extra test, and the exit is visible at the point where the decision is made. This is the right answer for a search, and it is the first of the two reasons this chapter ends by recommending procedures.

5. When to stop nesting

Three levels is where it usually stops being readable:

set designs {
    {alpha {{clk 1} {data 32}}}
    {beta  {{clk 1} {rst 1} {addr 16}}}
}

foreach d $designs {
    lassign $d name ports
    puts "$name:"
    foreach p $ports {
        lassign $p pname width
        if {$width > 1} {
            puts "  $pname is $width bits wide"
        }
    }
}

alpha:
  data is 32 bits wide
beta:
  addr is 16 bits wide

That is still just about fine at two levels with a condition. Add one more level — say each port had a list of attributes — and the body of the innermost loop sits four indents deep, with its context spread over three lassign lines you have to scroll up to find.

The fix is not more indentation discipline. It is to name the inner work:

proc wide_ports {ports} {
    set out {}
    foreach p $ports {
        lassign $p pname width
        if {$width > 1} {
            lappend out "$pname is $width bits wide"
        }
    }
    return $out
}

foreach d $designs {
    lassign $d name ports
    puts "$name:"
    foreach line [wide_ports $ports] {
        puts "  $line"
    }
}

alpha:
  data is 32 bits wide
beta:
  addr is 16 bits wide

Identical output. The outer loop now reads as "for each design, print its wide ports", which is what it does, and wide_ports can be read, tested and changed on its own.

6. Nested loops over different structures

The two levels do not have to be the same kind of loop:

set widths {8 16 32}

foreach w $widths {
    puts -nonewline [format "%3d: " $w]
    for {set bit 0} {$bit < $w} {incr bit 8} {
        puts -nonewline "[expr {$bit / 8}] "
    }
    puts ""
}

  8: 0 
 16: 0 1 
 32: 0 1 2 3

A foreach outside and a for inside, because the outer level has a list and the inner one has a numeric range — the distinction from Chapter 9.4.

7. A worked example

Counting across two levels, with the inner work extracted:

proc count_wide {ports} {
    set n 0
    foreach p $ports {
        lassign $p pname width
        if {$width > 1} { incr n }
    }
    return $n
}

set designs {
    {alpha {{clk 1} {data 32}}}
    {beta  {{clk 1} {rst 1} {addr 16}}}
    {gamma {{clk 1}}}
}

set total 0
foreach d $designs {
    lassign $d name ports
    set n [count_wide $ports]
    incr total $n
    puts [format "  %-6s %d of %d ports are wide" $name $n [llength $ports]]
}
puts "total wide ports: $total"

  alpha  1 of 2 ports are wide
  beta   1 of 3 ports are wide
  gamma  0 of 1 ports are wide
total wide ports: 2

The outer loop accumulates — Chapter 9.9 — and the inner loop has a name, so neither level is doing two things at once.

8. What Module 9 covered

Ten chapters on iteration:

• foreach as the default loop, and why removing the index removes a whole class of bug
• Several lists in parallel, with the padding rule that differs from every other language's zip
• Several variables per pass, for walking flat key-value data in place
• for when the index itself is the job, and while when the number of passes is unknown
• break and continue, and continue as a guard that keeps loop bodies flat
• The frozen condition that hangs a loop silently, demonstrated with a safety counter
• lmap, what version added it, and what to do without it
• The four accumulator shapes, and the initialisation bugs behind most of their failures
• Nesting, its one firm rule, and when to stop

Two threads run through it. The first is the one from Module 8: these are commands, not syntax, and almost every surprise comes from substitution happening earlier than you assumed — the quoted condition, the quoted body, the snapshot that foreach takes. The second is newer: the loop is rarely where the bug is. It is in the line before it, where the accumulator was initialised, or in the line that advances the counter and turned out to be unreachable.

9. What comes next

Module 10 is Procedures and Reuse — proc, arguments with defaults, args, return, what "local" actually means, and when something deserves to be a procedure at all.

This chapter has already made the case twice. Extracting the inner loop in section 5 and returning from inside nested loops in section 4 are both procedure arguments, made before you had the vocabulary to state them properly. Module 10 supplies it.

10. Exercises

Exercise 1. Why does this print 1 2 5 6 rather than 1 2?

foreach row {{1 2} {3 4} {5 6}} {
    foreach cell $row {
        if {$cell == 3} break
        puts -nonewline "$cell "
    }
}

Exercise 2. Write a nested loop printing every pair from {a b} and {1 2}.

Exercise 3. Name the three ways to leave both loops at once and say which you would prefer.

Exercise 4. What goes wrong if a flag is set in the inner loop but never tested in the outer one?

Exercise 5. Extract the inner loop of this into a procedure:

foreach g $groups {
    lassign $g name items
    set n 0
    foreach i $items { if {$i > 10} { incr n } }
    puts "$name: $n"
}

Exercise 6. Give the test for whether a nested loop should be extracted into a procedure.

Answers

1. Because break ends only the loop it is directly inside. It ended the inner loop for the row {3 4}, skipping 4, and the outer loop then moved on to {5 6} as normal. Only 4 is missing from the output.

2.

foreach a {a b} {
    foreach n {1 2} {
        puts "$a$n"
    }
}

a1
a2
b1
b2

3. A flag tested at the top of the outer loop; return from an enclosing procedure; or restructuring so the inner loop is a procedure that returns a result. return from a procedure is the best when the loops are a search, because the exit is stated where the decision is made and there is nothing to keep in sync.

4. The inner loop stops, the outer one carries on to the next iteration, and the inner loop runs again — immediately hitting its break condition or not, depending on the data. The symptom is a loop that appears to ignore its own exit condition.

5.

proc count_over {items limit} {
    set n 0
    foreach i $items {
        if {$i > $limit} { incr n }
    }
    return $n
}

foreach g $groups {
    lassign $g name items
    puts "$name: [count_over $items 10]"
}

6. Whether you can describe what the inner loop does in a short phrase. If you can, that phrase is the procedure's name. If you cannot, the nesting is probably doing two unrelated things and should be split for that reason instead.

11. Remember

• A nested loop is just a loop in another loop's body — the natural shape for a list of lists.
• break and continue affect only the loop they are directly inside. There is no labelled break in Tcl.
• A flag leaves both loops, but must be tested at the top of the outer loop as well as set in the inner one.
• return from a procedure leaves every enclosing loop at once and is the best answer for a search.
• Three levels is usually one too many. The fix is a named procedure, not deeper indentation.
• The test for extracting is whether you can name what the inner loop does in a short phrase.
• The two levels need not be the same kind of loop — foreach outside and for inside is common.
• The loop is rarely where the bug is — look at the initialisation before it and the advance inside it.