Appendix: Algorithm and Pseudocode Conventions

Summary

The algorithms presented in this book assume eager evaluation. The values of primitive types (integers, reals, strings) are passed by value, and tuples, lists, arrays, sets, stacks, queues, etc., are passed by reference, similar to how Java treats primitive values and objects.

The data structures (container types) like sets, arrays, stacks and queues, and the operations on those structures carry their usual meaning, and their usages in the algorithms are self explanatory.

Tuple

A tuple is an ordered collection of fixed number of elements, where each element may be of a different type. A tuple is represented as a comma separated sequence of elements, surrounded by parenthesis.

tuple → ( ELEMENT ₁ , ELEMENT ₂ , … , ELEMENT _k)

A tuple of two elements is called a pair, for example, (S, null), ((A, S), 1), (S, [A, B]) are pairs. And a tuple of three elements is called a triple, for example, (S, null, 0), (A, S, 1), (S, A, B) are triples. A tuple of k elements is called a k-tuple, for example, (S, MAX, −∞, ∞), (A, MIN, LIVE, ∞, 42).

Note: parenthesis is also used to indicate precedence, like in (3+1) * 4 or in (1 : (4 : [ ])), its usage will be clear from the context.

List

A list is an ordered collection of an arbitrary number of elements of the same type. A list is read from left to right and new elements are added at the left end. Lists are constructed recursively like in Haskell.

list → ELEMENT : list

list → [ ]

The ‘:’ operator is a list constructor; it takes an element (HEAD) and a list (TAIL) and constructs a new list (HEAD : TAIL) similar to cons(HEAD, TAIL) in LISP. Using head:tail notation, a list such as [3, 1, 4] is recursively constructed from (3 : (1 : (4 : [ ]))), similar to cons(3, cons(1, cons(4, nil))) in LISP. The empty list [ ] has no head or tail.