Revision as of 19:17, 19 November 2009

This page documents some conventions to be followed when writing pseudocode on PEGWiki. These are not binding policy on PEGWiki, but following them should minimize confusion and promote consistency across articles. Similarly, if you see unfamiliar notation in a pseudocode block, you may find its meaning here. Changes to these conventions should be discussed on the talk page.

Universal conventions

• Structure should be indicated by indentation, as in Python. Adding braces {} as in C or words such as begin and end as in Pascal would introduce unnecessary clutter into pseudocode blocks. Do not use tabs for indentation. Five spaces is a good guideline. (In LaTeX pseudocode, this means five full-width spaces (a full-width space is "\ ").)
• The for, if/else, and while statements should not be followed by words like "do" or "then"; pseudocode is intended for humans, not machines.
• Similarly, statements should not end in semicolons.
• Indices into arrays should be placed in square brackets, []. The Pascal convention of separating indices by commas is preferred to the C convention of having a separate set of brackets for each index (simply by virtue of being nicer and more intuitive), but the latter may be occasionally appropriate to reinforce the interpretation of the array's structure. Use your common sense.
• Parameter lists should be enclosed in parentheses, (), and parameters should be separated by commas.
• A function header should contain with the word function, the function's name, and the function's parameter list, in that order. The body of a function should be indented.
• If something is not a real command, e.g. "input" or "print", its parameter list should not have parentheses.
• Object-oriented code should be used wherever appropriate, and nowhere else. The members of an object should be indicated by the dot operator .. For example, it makes sense to represent a data structure as an object (which encapuslates the structure's data). However, please do not wrap an entire algorithm in an object as would be done in Java; that is pointless and only leads to clutter.
• The mod operator should never return a negative result; the number-theoretic convention of always yielding a non-negative integer should be followed.

Text-mode conventions

• Variable assignment should occur through the use of a single equals sign, =, although the Pascal notation of := is also acceptable.
• Equality testing should also occur through the use of a single equals sign, =, but is distinguished from variable assignment by context. For example, if it is preceded by if, it is an equality test, and if it stands alone, it is an assignment. The C notation of == should be avoided.
• The symbols <=/>= and ≤/≥ are equally acceptable, but in most other cases a Unicode symbol should be used whenever both necessary and possible. For example, oo for ∞ is unacceptable.

Math-mode conventions

• The LaTeX \sqrt command is almost always preferable to typing out .
• The vinculum (horizontal bar) to indicate division (produced by the \frac command) is usually best, but if the numerator or denominator is complex, a single slash is preferable when it improves readability or overall aesthetic appeal.
• Exponentiation should always occur in the form rather than in the form ^. When the exponent is so complex that superscripting makes the expression look ugly, use a temporary variable for the exponent. The exception is when the base is : you can replace with in that case.
• Actual words, such as "if" and "and", should not be italicized. Use the \mathrm function to de-italicize them.
• Equality testing should occur through the symbol.
• Variable assignment should occur through the symbol (LaTeX code: "\gets")

Technical notation

• The symbol ∈ means "is a member of". For example, is a member of the set of real numbers, hence we might write . Similarly, ∉ means "is not a member of"; .
• Items enclosed in braces {} and separated by commas form a set or multiset. For example, {1,2,3} is a set containing the elements 1, 2, and 3. Normally they form a set; they form a multiset if stated otherwise. The difference is that a set contains no duplicate elements. Sets and multisets should be typed: that is, a set or multiset should not contain elements of different types. However, a set/multiset may itself contain sets/multisets, or any other kind of item.
• Items enclosed in parentheses () and separated by commas form a tuple. For example, (a,b) is an ordered pair (a tuple with two elements). Tuples may contain elements of different types.
• An edge in a directed graph is an ordered pair of vertices. For example, if a graph has an edge from a to b, then this can be described as (a,b). An edge in an undirected graph is an unordered pair, or a set containing two vertices: for example, {a,b}. (If self-loops are allowed, then it's actually a multiset.)
• A graph is an ordered pair of two sets: V and E. The former is the set of vertices, and the latter the set of edges. We can write G = (V,E) to indicate that the graph G has vertex set V and edge set E. Also, given some graph G, V(G) is the vertex set of G, and E(G) is the edge set of G. An example of a graph is then ({a,b,c},{(a,b),(b,c),(a,c)}), for which V={a,b,c} and E={(a,b),(b,c),(a,c)}. This graph has vertices a, b, and c, an edge from a to b, an edge from b to c, and an edge from a to c. Note: It is incorrect to write (u,v) ∈ G.
• The number of vertices in graph G is denoted |V(G)| (the size of the vertex set), and the number of edges |E(G)| (the size of the edge set). When discussing asymptotic performance, however, we generally write just V and E.