Pseudocode Primer

Pseudocode is a good way to talk about code in a generic way that does not tie you to a specific language. Therefore it is a very good way to describe algorithms.

- Joseph Hopper

A Small Pseudocode Notation Primer

This document is intended to aid you as a student in learning, understanding, and using the pseudocode notation used in the readings and assignments for the CSE 382 class.

Types

Value Types

• \(Integer\)
• \(Real\)
• \(Character\)
• \(Boolean\)
• \(acc\) - an accumulator of any type, including a list.
• \(\{a,b\}\) - a 2-tuple

Operators

• \(\bigoplus\)- a symbol representing an operator to be specified elsewhere.
• \(\lceil \rceil\) - an operator representing the ceiling behavior.
• \(\lfloor \rfloor\) - an operator representing the floor behavior.
• \(\big | x \big |\) - an operator representing the absolute value of \(x\) behavior.
• \(+,-,\cdot,\div\) - addition, subtraction, multiplication, and division as per standard mathematics.
• \(<,>,=,<=,>=\) - comparison operators as usually defined in mathematics.
• \(;\) - the end of a function clause.
• \(.\) - the end of a function.
• \(:::\) - an operator read as 'of type'.
• \(\circ\) - an operator representing composition.
• \(\looparrowright\) - an operator representing tuple decomposition
• \(\gg =\) - an operator representing binding.
• \(\text{%%} \) - an operator indicating a single line comment.
• \(\_\) - an operator indicating a parameter or element is ignored.

Lists

Declaring Lists

• \([]\) - an empty list containing elements of any type.
• \([]:::Type\) - an empty list containing element of the specified type.
• \([a]\) - a list that may or may not be empty containing elements of any type.
• \([a]:::Type\) - a list that may or may not be empty containing elements of the specified type.

Building Lists

Any example listed here can be used with lists of a specified type or lists of any type. The examples listed here use lists of any type to reduce verbosity.

• \(x\doubleplus [a]\) - creates a new list, set, or heap that is the result of prepending \(x\), if \(a\) is a list or stack, or adding \(x\) if \([a]\) is a set or heap.
• \([a]\doubleplus x\) - creates a new list that is the result of appending \(x\) to the list \([a]\).
• \([a]\doubleplus [b]\) - creates a new list by appending lists containing different elements.
• \([a]\doubleplus [a]\) - creates a new list by appending lists containing the same elements.

Reducing Lists

• \([h\mid t]\) - popping the first element of a list, set, queue, min_heap, or max_heap. \(h\) is the first element or head of the original data structure and \(t\) is the remaining elements. If the data structure is a list or queue, \(t\) consists of the elements in the first list without the head in their original order.
• \([h:t]\) - popping the last element of a list. \(t\) is the last element or tail of the original list and \(h\) is the first list without the tail with all elements in their original order.

Data Structures

• \([n]_{set}\) - a set of elements.
• \([n]_{queue}\) - a queue of elements.
• \([n]_{min\_heap}\) - a heap of elements sorted with the least element at the root.
• \([n]_{max\_heap}\) - a heap of elements sorted with the greatest element at the root.
• \([a\looparrowleft b]\) - a dictionary consisting of a single key \(a\) and value \(b\)
• \([\ \looparrowleft\ ]\) - an empty dictionary
• \(a\twoheadrightarrow\ set\) - determine if \(a\) is or is not an element of \(set\). The value is a Boolean.
• \(set\twoheadleftarrow\ a\) - creating a new set by adding \(a\) to the existing set \(set\).
• \(set - a\) - creating a new set by removing \(a\) from the existing set \(set\).
• \(dict\twoheadleftarrow a\ b\) - creating a new dictionary by adding the key-value pair \(a,b\) to the existing dictionary \(dict\)
• \(a\twoheadrightarrow\ dict\) - using the key \(a\) to get the key's associated value from the dictionary \(dict\)

Function Declarations

All function declarations follow the same pattern. They begin with the name of the function. This is separated from the set of parameters by two colons, \(::\). The parameter set is space separated. This is then followed by a right arrow representing an assertion of truth. The arrow points at the value of the function (in programmer terms, the return value).

Examples

• \(start::\text{ }\rightarrow Real \) - a function named \(start\) with no parameters. The value of the function is a \(Real\).
• \(length::[a]\rightarrow Integer\) - a function named \(length\) with a single parameter that is a list that may or may not be empty. The value of the function is an \(Integer\).
• \(comparator::x\text{ }y\rightarrow r\) - a function called \(comparator\) that has two parameters and has a value of undetermined type.
• \(in::x\text{ }[a]\rightarrow Boolean\) - a function called \(in\) that has two parameters, a value and a list that may or may not be empty and has a defined value type. In this case, \(Boolean\).
• \(b\_search:: a\text{ }[b]\text{ }(f::x\text{ }y\rightarrow Integer)\rightarrow c\) - a function called \(b\_search\) that has three parameters, a value, a list that may or may not be empty, and a function named \(f\) that itself has two parameters and a value of \(Integer\). The \(b\_search\) function's value is of undeclared type.

Keywords

• \(when\) - a guard for execution of a code clause consisting of one or more sub-statements.
• \(otherwise\) - used in conjunction with the when keyword to indicate all other possibilities.
• \(nil\) - indicating the lack of existence. Nothing.
• \(or, and, xor\) - as traditionally defined in logic.
• \(true, false\) - as traditionally defined in logic.

Usage Examples

A function specification without a definition

This function determines the length of a list. Notice that all specifications begin with $-spec$ to differentiate the specification from the function itself. Specifications are used to declare the function's name, parameters, and its value. The types of the parameters are also included. In the example below, $b$ is of type $Integer$. The $a$ is left as an undefined type. $$\begin{align*} -spec\ len&::[a]\rightarrow \ b:::Integer \end{align*}$$

A function declaration followed by its two clauses that are the function's definition.

This function adds all the elements of a list. $$\begin{align*} -spec\ sum &::[a]\rightarrow a:::Real\\ sum &:: [a]\rightarrow 0 \text{ }when\text{ }[a]\text{ is empty;}\\ sum &:: [h\mid t]\rightarrow h+sum\text{ }t \text{ } otherwise. \end{align*}$$

A function declaration and definition that uses previously declared functions.

This function calculates the average of a list of numbers. $$\begin{align*} -spec\ average&::[a]\rightarrow a:::Real\\ average&= sum\text{ }[a]\div len\text{ }[a]. \end{align*}$$

List Comprehensions

The pseudocode below builds a list of even integers from the list of all positive integers. $$\begin{align*} [x\in[1\ 2\ 3\ldots]\ :\ x\equiv 0\pmod{2}]\\ \end{align*}$$ Here is pseudocode that produces a list of 2-tuples. No predicate is used. $$\begin{align*} [\{x\in[1\ 2\ 3 \ldots],y\in[a b c\ldots z]\}]\\ \end{align*}$$ Multiple predicates can be applied using the boolean keywords listed above.