Lecture notes: Composition of iteration plans
Plan composition
Very often the requirements specification for a program requests that different sub-tasks be carried out or different sub-problems be solved. To each sub-task or sub-problem there corresponds a goals and thus a plan in the program. There are different ways in which plans can be composed into the solution to a problem, depending on the problem itself.
- Abutment: the plans are applied one after the other one; each plan is present as a complete unit
- Nesting: plans are applied one nested within another one; a typical example is the nested loops used to scan the lines of a matrix.
- Merge or interleaving: the plans have actions in common that can be carried out only once, thus the corresponding instructions’ blocks are merged into one block of instructions; in order to merge two plans it is often necessary to decompose and recompose in a suitable way, depending on the problem to be solved.
Merging and nesting plans is not always immediate, it often requires some design to correctly compose the sub-solutions.
We will now illustrate the composition types through examples on iteration plans.
Abutment of iteration plans
Specification. Given a list of numbers, print the sum of the numers that are greater than half the greatest value in the list. For example, if the list is 4, 10, 2, 3, 5, 7, 6, the result will be 23 (the sum of 10, 7, and 6, i.e. the numbers > 10/2) To solve this problem, we first have to compute the maximum, by examining the whole list and exploiting the extreme (best) iteration plan. Once we have computed the maximum, we need to compute the sum of the numbers that are greater than half the maximum, we thus need a total iteration plan. Each item of the list must compared with half the maximum, we thus have to scan the whole list a secon time.
The extreme (best) iteration plan and the total iteration plan need to be abuted one after the other. The two plans could also be implemented in two separate functions, as shown here, which will be called one after the other one (greatest at line 4 and sumIfAbove at line 5)
func main() {
list := []int{4, 10, 2, 3, 5, 7, 6}
var max, sum int
max = greatest(list)
sum = sumIfAbove(list, max/2)
fmt.Println(sum)
}
func greatest( list []int ) int {
max := list [0]
for _, el := range list {
if el > max {
max = el
}
}
return max
}
func sumIfAbove(list []int, threshold int) int {
var sum = 0
for _, el := range list {
if el > threshold {
sum += el
}
}
return sum
}Nesting iteration plans
Specification. Given a list of strings, compute: i) how many of the strings contain at least a digit, ii) the number of digits in each string. To accomplish this task we need counting iteration plan both for the first and the second goal: to count the strings that contain digits and, for each string, to count the digits it contains. In the following code snippet it can be observed that the counting iteration plan for the digits (lines 3-9) is nested within the counting iteration plan for the strings that have digits (lines 1-2, 10-13): the latter one (the external one) iterates on the strings of the list, the former (the inner one), for each string, iterates on its characters (runes). The counter countDigits, belonging to the inner loop, is initialized to 0 every time a new string must be processed, that is at every iteration of the outer loop.
countStrings := 0
for _, word := range os.Args[1:] {
countDigits := 0
for _,letter := range word {
if unicode.IsDigit(letter) {
countDigits++
}
}
fmt.Println(word, "contains", countDigits, "digits.")
if countDigits > 0 {
countStrings++
}
}
fmt.Println("There are", countDigits, "strings with at least a digit.")Merging (or interleaving) iteration plans
Specification. Given a list of grades, compute the greatest grade and the grades’ sum.
When more computations are requested on the same sequence of data, it is not always necessary to scan the sequence more times; often it is possible to “merge” the plans in a single loop.
In this case the required plans are the extreme (best) iteration plan and the total iteration plan. The function maxAndSum below solves the problem: the extreme (best) iteration plan (max) is implemented at lines 12-13-14-15-17, the total iteration plan at lines 12-16-17. Note that the lines 12 and 17 are common to both plans: the plans have been merged in order to scan the list only once.
func main() {
list := []int{24, 29, 22, 23, 25, 27, 18}
var max, sum int
max, sum = maxAndSum(list)
fmt.Println("max:", max, ", sum:", sum)
}
func maxAndSum( list []int ) (int, int) {
sum := 0
max := list [0]
for _, el := range list {
if el > max {
max = el
}
sum += el
}
return max, sum
}Observation
If the plans under consideration are iteration plans, each of them will have a loop. It will be possible to identify the way they have been composed by looking at how many loops are present, and in the case there are more than one loop, at how they appear:
- abutment: two loops, one after the other one;
- nesting: two loops, one inside the other one;
- merging or interleaving: one loop.