# Software Development : Structured Programming

As the Internet is full of introductory material, this section will contain only a few remarks that might give the material at other sites a bit different flavor.

## Contents

# Loops

## Translatability

Any common loop construct can be rewritten by using any other common loop construct. For example, the following for-loop

```
for(i=0;i<42;i++){
do_something();
} // for
```

is equivalent to the following while-loop:

```
i=0;
while (i<42){
do_something();
i++;
}
```

which is equivalent to the following (Ruby) code:

```
i=0
begin
if (i<42)
do_something();
i++;
end # if
end while (i<42)
```

which in turn can be rewritten as the for-loop at the start of this example.

## Generalisations

By citing Андрей Николаевич Терехов, a way to comprehensibly describe a loop is:

```
FOR i FROM a BY b TO c WHILE d
DO f OD
```

## Loop Parallelization

If separate iterations of a loop do not depend on each other, then the result of the loop does not depend on the execution order of its iterations.

```
function the_output_of_this_function_does_not_depend_on_the_rand_value(x) {
var ar_data = [42, 77, 55];
// 0.0 <= Math.random() <= 1.0
var b_choice_1 = (0.5 <= Math.random());
if (b_choice_1) {
for (i = 0; i < 3; i++) {
ar_data[i] = ar_data[i] + x;
} // for
} else {
if (0.5 <= Math.random()) {
// The key phrase here is: "loop unrolling".
// If loops are short "enough", then the
// unrolling can be used as an assembler
// level optimization technique that is based
// on the idea that by unrolling a loop, there is
// no need to allocate a CPU register for
// the loop iteration variable, in this case,
// "the i", and the "i=0" assembler command
// can also be skipped.
ar_data[1] = ar_data[1] + x;
ar_data[2] = ar_data[2] + x;
ar_data[0] = ar_data[0] + x;
} else {
if (0.5 <= Math.random()) {
ar_data[2] = ar_data[2] + x;
ar_data[1] = ar_data[1] + x;
ar_data[0] = ar_data[0] + x;
} else {
ar_data[1] = ar_data[1] + x;
ar_data[0] = ar_data[0] + x;
ar_data[2] = ar_data[2] + x;
} // else
} // else
} // else
return ar_data;
} // the_output_of_this_function_does_not_depend_on_the_rand_value
```

Loop parallelization that takes advantage of the CPU SIMD*(Single-Instruction-Multiple-Data)* instructions is called **vectorization**. As of 2015 the command line arguments for switching in vectorization of GCC and LLVM is:

```
S_THE_REST=" -ftree-vectorize "
-mtune=native $S_THE_REST # optimizes for the current CPU, but inserts extra code
# for backwards compatibility with older CPU types
-march=native $S_THE_REST # optimizes for the current CPU, but
# does NOT insert the extra code for the
# backwards compatibility with the older CPU types
```

Loop parallelization can be used for executing different iterations of the loop at different computers in a cluster. In that case program execution continues after the results of all of the iterations of the loop have been received from the various computers in the cluster. The keyword is MapReduce. If in stead of a cluster the iterations are run at different CPU cores of a single computer, then one possible algorithm for spreading the iterations between CPU cores is to load the iteration tasks to a queue and have the CPU cores fetch the tasks from that queue at their own pace. More detailed descriptions of that algorithm can be found by searching the phrase "work stealing", but a key thing to remember with that algorithm is that the activity of distributing the tasks between CPU cores can be too expensive for some tasks and to start an operating system process is even more expensive.

### The Amdahl’s law

Speed-up that can be achieved by algorithm parallelization has a theoretical limit that can be explained by an example, where the algorithm consists of 3 function calls.

```
function the_algorithm() {
func_part_1(); //if sequential, takes 0.2 time units
func_part_2(); //if sequential, takes 0.5 time units
func_part_3(); //if sequential, takes 0.3 time units
// 0.2 + 0.5 + 0.3 = 1.0
} // the_algorithm
```

If the time spent on the execution of the `func_part_2()`

were divided by 2 by parallelizing the `func_part_2()`

and executing the iterations on 2 CPU cores in parallel, then the whole execution time of the `func_part_2()`

would be

$$\cfrac{0.5 timeunits}{2} = 0.25 timeunits$$

and the time spent on the execution of `the_algorithm()`

would be

$$0.2 timeunits + 0.25 timeunits + 0.3 timeunits = 0.75 timeunits$$

If the `func_part_1()`

were to be executed on 100 CPU-cores in parallel and the `func_part_2()`

and `func_part_3()`

were executed on a single CPU core, then the time spent on the execution of `the_algorithm()`

would still be

$$\cfrac{0.2 timeunits}{100} + 0.5 timeunits + 0.3 timeunits = 0.002 timeunits + 0.8 timeunits = 0.802 timeunits$$

INCOMPLETE, POOLELI, lisada profileerimise peatükk, sinna teadusarvutuste graafi-lõikamise algoritm ning siis interpreteeritavate keelte JIT'i sisseülituse vältimisest tulenev muutujate väljaspool tsüklit deklareerimise jutt. Profileerimise peatükki lisada ka GCC ja LLVM'iga binaaride instrumenteerimise osa.

##### References

### Multithreaded Programming Related References

- File:2009 07 xx freescale NXP EMBMCRM Rev 0 Embedded Multicore An Introduction.pdf includes an overview of different types of parallelism.
- File:1999 xx xx Java s Insecure Parallelism Pointed out by the PER BRINCH HANSEN.pdf is a 1999 comment, basically an old school blog post, by one of the inventors of mutexes, where he very elegantly describes some core aspects of multi-threaded programming.

# Recursion

A recursive function is a function that has at least one call to itself as part of its implementation. A tail-recursive function is a function that contains exactly one call to itself and that call to itself resides at the very last line before return statement. Any tail-recursive function can be re-written as a while-loop.

```
function a_tailrecursive_function(a, b) {
if (20 <= a) { // Recursion stop condition.
return a;
} // if
var a_new = a + b;
var c = a_tailrecursive_function(a_new, b);
return c;
} // a_tailrecursive_function
function the_tailrecursive_function_converted_to_a_loop(a, b) {
var c = a;
while (c < 20) {
c += b;
} // while
return c;
} // the_tailrecursive_function_converted_to_a_loop
```

If a recursion stop condition is not met, a recursion based infinite loop analogue, an infinite recursion, occurs. If recursion occurs not within a single function, but within a set of functions, then the possibility of an infinite recursion, can be difficult for humans to notice, specially if the occurrence of the recursion is not intentional and involves multiple exhaustive components.

```
function func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
if (20 <= a) { // The recursion stop condition.
return a;
} // if
var c = func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b);
return c;
} // func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions
function func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
var a_new = a + b;
var c = func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a_new, b);
return c;
} // func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions
```

## Walking on Trees

If the number of vertices in the tree is not an issue, that is to say, the dataset size is not an issue, then the various simplistic tree-walking algorithms that are presented in various study books, are sufficient. However, there is an analogy with sorting algorithms in the sense that the non-laborous-to-implement bubblesort is fine for smaller datasets, but for real-life data-sets a more complex and more laborous-to-implement algorithm is needed. Just like with sorting algorithms, a general recommendation is to avoid creating a custom implementation, because implementing a proper tree-walker is a laborous effort. **An assumption of many tree-walking algorithms is that the tree does not change during the tree-walk and walking takes time regardless of implementation**. For file systems that assumption might not hold, specially if multiple operating system processes work on the same folder. A general structure of a primitive tree-walking function might look like this:

```
function with_heavy_input_verification_and_comfort_features(various_parameters) {
// blabla, a lot of code
function the_actual_recursive_function_that_receives_only_2_vertices(a_vertex,
the_root_vertex_of_the_tree) {
// The recursion stop condition
// function can take a look at the sub-vertices of
// the a_vertex, but that's an implementation detail of
// the recursion stop condition function.
if (func_stop_the_recursion_by_condition_1(a_vertex)) {
return; // stop the recursion
} // if
if (func_stop_the_recursion_by_condition_2(a_vertex)) {
return; // stop the recursion
} // if
// ...
// The rest of the code of the recursive function.
} // the_actual_recursive_function_that_receives_only_2_vertices
// The various calls to the
// the_actual_recursive_function_that_receives_only_2_vertices(...)
// and the implementation of the comfort related features
return something_that_may_be_different_from_the_recursive_function_output
} // with_heavy_input_verification_and_comfort_features
```

A Ruby example of a primitive tree-walking implementation that has been inspired by the book "Head First Design Patterns":

```
# It allows one to assemble a tree structure and then to iterate
# recursively through it. The iteration can be done by calling
# method "next()" at the root node or by using a "each_node"
# iteration loop at the root node. In terms of design patterns,
# one can see it as a mixture of the "Composite Design Pattern"
# and the "Iterator Design Pattern".
class Kibuvits_iterable_tree_t1_node
attr_accessor :data_record, :name, :root_node
# the @next_node is used only in the root node instance
attr_accessor :parent_node, :next_node, :children
def initialize
@root_node=self
@next_node=self
@parent_node=self
@name="nameless"
@children=Array.new
@iteration_index=0
end # initialize
def add_child(a_child_node)
a_child_node.parent_node=self
a_child_node.root_node=@root_node
@children << a_child_node
end # add_child
def each_node(&iteration_loop)
reset_the_iteration_state
yield @root_node.next_node
x=@root_node.next
while @root_node.next_node!=@root_node do
yield @root_node.next_node
x=@root_node.next
end # loop
end # each_node()
# A Java iterator-style next(). If it is called on the root node,
# it iterates through the entire tree recursively. It returns
# a node instance.
def next
x=@root_node.next_node.next_from_node_instance
@root_node.next_node=x
return x
end # next
def reset_the_iteration_state
while @root_node.next_node!=@root_node do
@root_node.next
end # loop
end # reset_the_iteration_state
protected
def next_from_node_instance
answer=""
if (@children.length-1) < @iteration_index
@iteration_index=0
if @root_node==self
answer=self
else
answer=@parent_node.next_from_node_instance
end # if
else
answer=@children[@iteration_index]
@iteration_index+=1
end # if
return answer
end # next_from_node_instance()
end # class Kibuvits_iterable_tree_t1_node
#=========================================================================
# Sample code:
def create_a_demo_tree
a=Kibuvits_iterable_tree_t1_node.new
b=Kibuvits_iterable_tree_t1_node.new
c=Kibuvits_iterable_tree_t1_node.new
d=Kibuvits_iterable_tree_t1_node.new
e=Kibuvits_iterable_tree_t1_node.new
a.add_child(b)
a.add_child(d)
b.add_child(c)
b.add_child(e)
a.name="A"
b.name="B"
c.name="C"
d.name="D"
e.name="E"
return a
end # create_a_demo_tree
tree=create_a_demo_tree
puts "\n\n--------- Node names by \"each_node\" loop: -----------\n"
tree.each_node {|a_node| print a_node.name}
puts "\n\n--------- Node names by a Java Iterator-like loop: -----------\n"
9.times { x=tree.next; print x.name }
puts "\n\n-- Node names by Java Iterator-like loop after iteration reset: --\n"
tree.reset_the_iteration_state
5.times { x=tree.next; print x.name }
puts "\n\nThe end of story. Thanks for watching. :) \n\n"
#=========================================================================
```

A real-life tree-walker interface specification example:

INCOMPLETE, POOLELI, lisada siia Kibuvitsa puu-jalutaja liidese spec.

# Some Sample code for copy-pasting

```
<!DOCTYPE HTML>
<html>
<head>
<title>Recursion Code Examples in JavaScript and HTML5</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<script type="text/javascript">
function a_tailrecursive_function(a, b) {
if (20 <= a) { // Recursion stop condition.
return a;
} // if
var a_new = a + b;
var c = a_tailrecursive_function(a_new, b);
return c;
} // a_tailrecursive_function
function the_tailrecursive_function_converted_to_a_loop(a, b) {
var c = a;
while (c < 20) {
c += b;
} // while
return c;
} // the_tailrecursive_function_converted_to_a_loop
function func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
if (20 <= a) { // The recursion stop condition.
return a;
} // if
var c = func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b);
return c;
} // func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions
function func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
var a_new = a + b;
var c = func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a_new, b);
return c;
} // func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions
function a_demo_of_a_conditionally_infinite_recursion(a, b) {
// This is to demonstrate that recursion can be quirky.
if (20 <= a) {
return a;
} // if
var c = 0;
if (a <= 15) {
c = a_demo_of_a_conditionally_infinite_recursion((b + 12), 3);
// Infinite recursion will not occur, if 4<=b .
} // if
var d = a + b + c;
return d;
} // a_demo_of_a_conditionally_infinite_recursion
window.onload = function () {
var a, b, c = null;
var s_html = "";
//--------------------
s_html = s_html +
"<br/>a_tailrecursive_function(...) == " +
a_tailrecursive_function(9, 4); // 9, 13, 17, 21
//--------------------
s_html = s_html +
"<br/>the_tailrecursive_function_converted_to_a_loop(...) == " +
the_tailrecursive_function_converted_to_a_loop(9, 4);
//--------------------
s_html = s_html +
"<br/>func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(...) == " +
func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(9, 4);
//--------------------
b = 4; // 3 will trigger infinite recursion
s_html = s_html +
"<br/><br/>a_demo_of_a_conditionally_infinite_recursion(...) == " +
a_demo_of_a_conditionally_infinite_recursion(9, 4);
//--------------------
var ob_p_1 = document.getElementById('id_p_1');
ob_p_1.innerHTML = s_html;
} // window.onload
</script>
</head>
<body>
<p id="id_p_1"></p>
</body>
</html>
```

# Assertions

... have its own chapterr.