Difference between revisions of "PEGWiki:Notational conventions"

Latest revision as of 21:15, 20 November 2011

This page documents some conventions to be followed when writing articles on PEGWiki. These are not binding policy on PEGWiki, but following them should minimize confusion and promote consistency across articles. You won't get in trouble for not following them, but what you write is likely to be slightly modified to conform with these conventions if it doesn't initially. If you see arcane or unfamiliar notation anywhere in an article, but especially in a pseudocode block, you may find its meaning here. Changes to these conventions should be discussed on the talk page.

Pseudocode conventions[edit]

Both text-mode and math-mode[edit]

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", as in Pascal, but should stand alone, as in C; 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, as in PHP or JavaScript. The body of a function should be indented.
If something is not a real command, e.g. input or print, it should not be written like a function (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 encapsulates 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, as in Scheme.

Text-mode only[edit]

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 as their single-symbol Unicode counterparts ≤, ≥, and ≠, but in most other cases a Unicode symbol should be used whenever both necessary and possible. For example, oo for ∞ is unacceptable.
Variables (and named constants) from pseudocode blocks which are referenced in the article text should be in italics; all other items, such as functions and literal constants, should be monospaced. The exception is literal numerical constants; it is acceptable not to format them specially, since they cause no confusion.

Math-mode only[edit]

The LaTeX \sqrt command is almost always preferable to typing out $\operatorname{sqrt}$ .
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 $a^b$ rather than in the form $a$ ^ $b$ . 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 $e$ : you can replace $e^x$ with $\exp(x)$ 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 $\gets$ symbol (LaTeX code: \gets)

Technical notation[edit]

Sets and related items[edit]

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.
A set/multiset that contains no elements is denoted ∅ (LaTeX: $\emptyset$ ).
A set/multiset that contains all elements of a given type is denoted $U$ , the universal set. The type can generally be inferred from context.
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, unlike sets and multisets, may contain elements of different types, and, again unlike sets and multisets, they have a fixed size.
Equality of tuples is denoted by an equals sign, $=$ . Two tuples are equal if and only if they are equal in size and all corresponding pairs of elements are equal; hence, $(B,A) \neq (A,B) \neq (A,B,C)$ .
The symbol ∈ means "is a member of", and ∉ means "is not a member of ".
The union of two sets or multisets $S$ and $T$ is denoted $S\cup T$ , their intersection $S\cap T$ , and their difference $S\setminus T$ .
The size or cardinality of a set or multiset $S$ is denoted $|S|$ .
The symbols $\subseteq$ , $\subsetneq$ , $\supseteq$ , and $\supsetneq$ denote subset, proper subset, superset, and proper superset, respectively. The symbols $\subset$ and $\supset$ are ambiguous and should be avoided. These relations are defined on multisets similarly to how they are defined on sets.
The Cartesian product of two sets or multisets $S$ and $T$ is denoted $S \times T$ .
The complement of a set is denoted $S'$ ; the complement is not defined on multisets.
The sum of two multisets $S$ and $T$ is denoted $S \uplus T$ ; this is not defined on ordinary sets.
A list is written like a set but with square brackets, $[\,]$ . It is an ordered collection of elements of the same type. A list is like a set in that its size is not fixed but elements can be added and removed. It is like a tuple in that two lists are considered equal if and only if they are of the same size and all pairs of corresponding elements are equal. Hence, $[1,2,3] \neq [1,3,2]$ , as their elements are in different orders.
Two lists written with a plus sign between them represents the concatenation of the two lists: hence, $[1,2] + [3,4] = [1,2,3,4]$ . Notice that concatenation is noncommutative.
$\mathbb{N}_1$ represents the positive integers. $\mathbb{N}_0$ represents the non-negative integers. Unless the intended meaning is absolutely clear from context, please use a subscript 0 or 1 instead of simply writing $\mathbb{N}$ .

Graph theory[edit]

Vertices in graphs should be given either non-negative integers or letters as labels; letters however must be italicized except when in code blocks. Subscripts on letters are okay: we might for example label the vertices of a bipartite graph as $A_1,A_2,A_3,A_4,\ldots,B_1,B_2,B_3,B_4,\ldots$ , in which edges exist only between $A$ s and $B$ s. Subscripts on numbers, however, are not.
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: we can write $(A,B) \in E(G)$ to indicate that there exists an edge from $A$ to $B$ . However, the notation $(A,B) \in G$ is incorrect.
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$ .
The weight of an edge from vertex u to vertex v is regarded as the value of a cost function which should be denoted by a sensible name such as wt, hence we have wt(u,v) and so on. A weighted graph is then regarded as the tuple $(V,E,\mathrm{wt})$ .

Coding style[edit]

Blocks of code written in real programming languages should be enclosed in <syntaxhighlight> ... </syntaxhighlight> blocks. A list of supported languages can be found here. Longer implementations of algorithms described in articles should be placed in a "subarticle" (e.g., Foo/Bar.cpp).

Avoid choosing programming languages that programmers and computer scientists would not ordinarily use for implementing complex algorithms. C, C++, Pascal, and Java are preferable; they are the languages most often used in algorithmic programming contests, and they are the languages in which Sedgewick's Algorithms is available. C#, Python, LISP and its derivatives, Haskell, and ML-derived languages are acceptable. Try to stay away from PHP, Perl, VB, JavaScript, and assembly language (yes, I know Knuth uses assembly language, but still). Specialized programming languages such as Maple and MATLAB are sometimes justifiable but should not be used in general.

Because you are expected to choose a language that a programmer with a primarily algorithmic (rather than development-based) background would be somewhat familiar with, you can assume that the reader knows the language fairly well, so write code idiomatically whenever possible. It is not necessary to adhere to any particular style site-wide; it's okay for some articles to have beginning curly braces on the following line and others to have them on the same line, but try to be consistent within individual articles.

@@ Line 1: / Line 1: @@
-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. You won't get in trouble for not following them, but what you write is likely to be slightly modified to conform with these conventions if it doesn't initially. If you see arcane or unfamiliar notation anywhere in an article, but especially in a pseudocode block, you may find its meaning here. Changes to these conventions should be discussed on the [[PEGWiki_talk:Pseudocode conventions|talk page]].
+This page documents some conventions to be followed when writing articles on PEGWiki. These are not binding policy on PEGWiki, but following them should minimize confusion and promote consistency across articles. You won't get in trouble for not following them, but what you write is likely to be slightly modified to conform with these conventions if it doesn't initially. If you see arcane or unfamiliar notation anywhere in an article, but especially in a pseudocode block, you may find its meaning here. Changes to these conventions should be discussed on the [[PEGWiki_talk:Notational conventions|talk page]].
-=Universal conventions=
+==Pseudocode conventions==
+===Both text-mode and math-mode===
 * '''Structure should be indicated by indentation''', as in Python. Adding braces <code>{}</code> as in C or words such as <code>begin</code> and <code>end</code> 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 "<code>\ </code>").)
-* The <code>for</code>, <code>if</code>/<code>else</code>, and <code>while</code> statements should not be followed by words like "do" or "then"; pseudocode is intended for humans, not machines.
+* The <code>for</code>, <code>if</code>/<code>else</code>, and <code>while</code> statements should not be followed by words like "do" or "then", as in Pascal, but should stand alone, as in C; pseudocode is intended for humans, not machines.
 * Similarly, statements should not end in semicolons.
 * Indices into arrays should be placed in square brackets, <code>[]</code>. 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, <code>()</code>, and parameters should be separated by commas.
-* A function header should contain with the word <code>function</code>, the function's name, and the function's parameter list, in that order. The body of a function should be indented.
+* A function header should contain with the word <code>function</code>, the function's name, and the function's parameter list, in that order, as in PHP or JavaScript. The body of a function should be indented.
 * If something is not a real command, ''e.g.'' <code>input</code> or <code>print</code>, it should not be written like a function (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 <code>.</code>. For example, it makes sense to represent a data structure as an object (which encapsulates 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.
+* The mod operator should never return a negative result; the number-theoretic convention of always yielding a non-negative integer should be followed, as in Scheme.
-=Text-mode conventions=
+===Text-mode only===
 * Variable assignment should occur through the use of a single equals sign, <code>=</code>, although the Pascal notation of <code>:=</code> is also acceptable.
 * Equality testing should also occur through the use of a single equals sign, <code>=</code>, but is distinguished from variable assignment by context. For example, if it is preceded by <code>if</code>, it is an equality test, and if it stands alone, it is an assignment. The C notation of <code>==</code> should be avoided.
-* The symbols <code>&lt;=</code>/<code>&gt;=</code>/<code>&lt;&gt;</code> and <code>&le;/&ge;/&ne;</code> are equally acceptable, but in most other cases a Unicode symbol should be used whenever both necessary and possible. For example, <code>oo</code> for <code>∞</code> is unacceptable.
+* The symbols <code>&lt;=</code>, <code>&gt;=</code>, and <code>&lt;&gt;</code> are equally acceptable as their single-symbol Unicode counterparts <code>&le;</code>, <code>&ge;</code>, and <code>&ne;</code>, but in most other cases a Unicode symbol should be used whenever both necessary and possible. For example, <code>oo</code> for <code>∞</code> is unacceptable.
 * Variables (and named constants) from pseudocode blocks which are referenced in the article text should be in <i>italics</i>; all other items, such as functions and literal constants, should be <code>monospaced</code>. The exception is literal numerical constants; it is acceptable not to format them specially, since they cause no confusion.
-=Math-mode conventions=
+===Math-mode only===
 * The LaTeX <code>\sqrt</code> command is almost always preferable to typing out <math>\operatorname{sqrt}</math>.
 * The vinculum (horizontal bar) to indicate division (produced by the <code>\frac</code> command) is usually best, but if the numerator or denominator is complex, a single slash <math>/</math> is preferable when it improves readability or overall aesthetic appeal.
@@ Line 26: / Line 27: @@
 * Variable assignment should occur through the <math>\gets</math> symbol (LaTeX code: <code>\gets</code>)
-=Technical notation=
+==Technical notation==
-==Sets and related items==
+===Sets and related items===
-* The symbol ∈ means "is a member of". For example, <math>\pi</math> is a member of the set of real numbers, hence we might write <math>\pi \in \mathbb{R}</math>. Similarly, ∉ means "is not a member of"; <math>\pi \notin \mathbb{Q}</math>. The union of two sets <math>S</math> and <math>T</math> is denoted <math>S\cup T</math>, their intersection <math>S\cap T</math>, and their difference <math>S\setminus T</math>.
+* Items enclosed in braces <math>\{\}</math> and separated by commas form a set or multiset. For example, <math>\{1,2,3\}</math> 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 braces {} and separated by commas form a set or multiset. For example, <math>\{1,2,3\}</math> 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.
+* A set/multiset that contains no elements is denoted ∅ (LaTeX: <math>\emptyset</math>).
-* Items enclosed in parentheses () and separated by commas form a ''tuple''. For example, <math>(A,B)</math> is an ordered pair (a tuple with two elements). Tuples may contain elements of different types.
+* A set/multiset that contains all elements of a given type is denoted <math>U</math>, the universal set. The type can generally be inferred from context.
-==Graph theory==
+* Items enclosed in parentheses <math>()</math> and separated by commas form a ''tuple''. For example, <math>(A,B)</math> is an ordered pair (a tuple with two elements). Tuples, unlike sets and multisets, may contain elements of different types, and, again unlike sets and multisets, they have a fixed size.
+* Equality of tuples is denoted by an equals sign, <math>=</math>. Two tuples are equal if and only if they are equal in size and all corresponding pairs of elements are equal; hence, <math>(B,A) \neq (A,B) \neq (A,B,C)</math>.
+* The symbol ∈ means "is a member of", and ∉ means "is not a member of ".
+* The union of two sets or multisets <math>S</math> and <math>T</math> is denoted <math>S\cup T</math>, their intersection <math>S\cap T</math>, and their difference <math>S\setminus T</math>.
+* The size or cardinality of a set or multiset <math>S</math> is denoted <math>|S|</math>.
+* The symbols <math>\subseteq</math>, <math>\subsetneq</math>, <math>\supseteq</math>, and <math>\supsetneq</math> denote subset, proper subset, superset, and proper superset, respectively. The symbols <math>\subset</math> and <math>\supset</math> are ambiguous and should be avoided. These relations are defined on multisets similarly to how they are defined on sets.
+* The Cartesian product of two sets or multisets <math>S</math> and <math>T</math> is denoted <math>S \times T</math>.
+* The complement of a set is denoted <math>S'</math>; the complement is not defined on multisets.
+* The sum of two multisets <math>S</math> and <math>T</math> is denoted <math>S \uplus T</math>; this is not defined on ordinary sets.
+* A ''list'' is written like a set but with square brackets, <math>[\,]</math>. It is an ordered collection of elements of the same type. A list is like a set in that its size is not fixed but elements can be added and removed. It is like a tuple in that two lists are considered equal if and only if they are of the same size and all pairs of corresponding elements are equal. Hence, <math>[1,2,3] \neq [1,3,2]</math>, as their elements are in different orders.
+* Two lists written with a plus sign between them represents the concatenation of the two lists: hence, <math>[1,2] + [3,4] = [1,2,3,4]</math>. Notice that concatenation is noncommutative.
+* <math>\mathbb{N}_1</math> represents the positive integers. <math>\mathbb{N}_0</math> represents the non-negative integers. Unless the intended meaning is absolutely clear from context, please use a subscript 0 or 1 instead of simply writing <math>\mathbb{N}</math>.
+===Graph theory===
 * Vertices in graphs should be given either non-negative integers or letters as labels; letters however must be italicized except when in code blocks. Subscripts on letters are okay: we might for example label the vertices of a bipartite graph as <math>A_1,A_2,A_3,A_4,\ldots,B_1,B_2,B_3,B_4,\ldots</math>, in which edges exist only between <math>A</math>s and <math>B</math>s. Subscripts on numbers, however, are not.
 * An edge in a directed graph is an ordered pair of vertices. For example, if a graph has an edge from <math>A</math> to <math>B</math>, then this can be described as <math>(A,B)</math>. An edge in an undirected graph is an unordered pair, or a set containing two vertices: for example, <math>\{A,B\}</math>. (If self-loops are allowed, then it's actually a multiset.)
 * A graph is an ordered pair of two sets: <math>V</math> and <math>E</math>. The former is the set of vertices, and the latter the set of edges. We can write <math>G = (V,E)</math> to indicate that the graph <math>G</math> has vertex set <math>V</math> and edge set <math>E</math>. Also, given some graph <math>G</math>, <math>V(G)</math> is the vertex set of <math>G</math>, and <math>E(G)</math> is the edge set of <math>G</math>. An example of a graph is then <math>(\{A,B,C\},\{(A,B),(B,C),(A,C)\})</math>, for which <math>V=\{A,B,C\}</math> and <math>E=\{(A,B),(B,C),(A,C)\}</math>. This graph has vertices <math>A</math>, <math>B</math>, and <math>C</math>, an edge from <math>A</math> to <math>B</math>, an edge from <math>B</math> to <math>C</math>, and an edge from <math>A</math> to <math>C</math>. Note: we can write <math>(A,B) \in E(G)</math> to indicate that there exists an edge from <math>A</math> to <math>B</math>. However, the notation <math>(A,B) \in G</math> is incorrect.
 * The number of vertices in graph <math>G</math> is denoted <math>|V(G)|</math> (the size of the vertex set), and the number of edges <math>|E(G)|</math> (the size of the edge set). When discussing asymptotic performance, however, we generally write just <math>V</math> and <math>E</math>.
+* The weight of an edge from vertex ''u'' to vertex ''v'' is regarded as the value of a ''cost function'' which should be denoted by a sensible name such as <code>wt</code>, hence we have <code>wt(u,v)</code> and so on. A weighted graph is then regarded as the tuple <math>(V,E,\mathrm{wt})</math>.
+==Coding style==
+Blocks of code written in real programming languages should be enclosed in <nowiki><syntaxhighlight> ... </syntaxhighlight></nowiki> blocks. A list of supported languages can be found [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi here]. Longer implementations of algorithms described in articles should be placed in a "subarticle" (''e.g.'', Foo/Bar.cpp).
+Avoid choosing programming languages that programmers and computer scientists would not ordinarily use for implementing complex algorithms. C, C++, Pascal, and Java are preferable; they are the languages most often used in algorithmic programming contests, and they are the languages in which Sedgewick's ''Algorithms'' is available. C#, Python, LISP and its derivatives, Haskell, and ML-derived languages are acceptable. Try to stay away from PHP, Perl, VB, JavaScript, and assembly language (yes, I know Knuth uses assembly language, but still). Specialized programming languages such as Maple and MATLAB are sometimes justifiable but should not be used in general.
+Because you are expected to choose a language that a programmer with a primarily algorithmic (rather than development-based) background would be somewhat familiar with, you can assume that the reader knows the language fairly well, so write code idiomatically whenever possible. It is not necessary to adhere to any particular style site-wide; it's okay for some articles to have beginning curly braces on the following line and others to have them on the same line, but try to be consistent within individual articles.

Difference between revisions of "PEGWiki:Notational conventions"

Latest revision as of 21:15, 20 November 2011

Contents

Pseudocode conventions[edit]

Both text-mode and math-mode[edit]

Text-mode only[edit]

Math-mode only[edit]

Technical notation[edit]

Sets and related items[edit]

Graph theory[edit]

Coding style[edit]

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools