27
$\begingroup$

In many academic papers algorithms are described. They seem to use similar "syntax".

Is there a standard for this language? If I want to describe an algorithm, would I improvise my description?

For example, note that papers in general use

a <-- b

to assign a, not a = b. But where is that standard?

$\endgroup$
7
  • 1
    $\begingroup$ Usually, textbooks have a consistent choice of symbols -- and I'd expect most papers would copy one of those styles -- but I'm not aware of any specific widely-used standard. The symbol "=" is generally not used for assignment, as algorithms are usually discussed in a mathematical context, where the "=" symbol already has a different meaning. $\endgroup$
    – Discrete lizard
    Commented Mar 13, 2023 at 20:27
  • 1
    $\begingroup$ Assignment can also be denoted with $:=$ (not to be confused with "defined as" in mathematical notation). You can get inspiration on how to write pseudocode by looking at Algol-60 samples. craftofcoding.wordpress.com/tag/algol $\endgroup$
    – user16034
    Commented Mar 13, 2023 at 22:28
  • 1
    $\begingroup$ as an answerer pointed out, this is called pseudocode, and in my opinion by definition it won't have a standard. Since if it has a standard, then we can make a parser/interpreter for it and it becomes a new programming language of its own, and no longer a pseudocode :) $\endgroup$
    – justhalf
    Commented Mar 14, 2023 at 6:40
  • 4
    $\begingroup$ Any sufficiently standardised pseudocode is indistinguishable from an actual programming language. (Conversely, if your pseudocode is indistinguishable from an actual programming language, it’s overly precise and you should really back it off a bit.) $\endgroup$ Commented Mar 14, 2023 at 9:19
  • 1
    $\begingroup$ In fact, Algol was originally designed to be such a standard, but it's nearly impossible to keep a single language updated with every idiom authors in different domains would like to use. Use-cases change, and pseudocode will adapt to them. $\endgroup$
    – chepner
    Commented Mar 15, 2023 at 13:59

6 Answers 6

30
$\begingroup$

No. There is no universal standard. There are some conventions that have become more popular over time, through gradual evolution.

A good starting place to look would be to look at the pseudocode notation used in a few common algorithms textbooks, pick one you like, and try to emulate it. Probably anything done in a popular and well-regarded textbook is going to be reasonable and understandable to others.

$\endgroup$
5
  • 11
    $\begingroup$ Also worth noting is that you should look at pseudocode notation used in a similar problem domain to that which your algorithm is in. Pseudocode is written in the language of the problem domain, and so different conventions apply for different problems. $\endgroup$
    – Pseudonym
    Commented Mar 13, 2023 at 23:49
  • 4
    $\begingroup$ One of the most famous algorithm books, Knuth's The Art of Computer Programming, invented a non-existent CPU so that he can describe algorithms in a neutral assembly language. $\endgroup$
    – slebetman
    Commented Mar 14, 2023 at 4:52
  • $\begingroup$ While there are many great answers, I am accepting this due to its compactness. $\endgroup$ Commented Mar 14, 2023 at 13:24
  • $\begingroup$ I second the idea that individual language communities have their own conventions, and that it's important to seek out the community in question. You'd mostly be understood if you spoke Cockney English in Mississippi, but at the University of Mississippi, you'd best use a standard, formal English for writing papers no matter where you are from. $\endgroup$
    – J D
    Commented Mar 15, 2023 at 18:56
  • $\begingroup$ And here we see a reason for things like different ways of writing the same symbol or different ways of spelling the same word in human languages, which can all be legitimate until some authority comes in and establishes a standard, which may or may not have other, competing standards. $\endgroup$ Commented Mar 15, 2023 at 23:58
25
$\begingroup$

The word you are looking for is pseudocode. :) There is no official standard, but as you have observed, there are general conventions that most people follow. Partly this is dictated by popular LaTeX packages (see, for example, this guide).

It's worth noting that the point of pseudocode is not to be formally specified, but to be human-readable. As a result, it is unlikely that all aspects of it could be standardized. For example, in pseudocode one sometimes takes a shortcut like:

for all vertices v reachable from u, do:
   ...

with the understanding that we can implement this using a DFS or a BFS. To a human reader, this is often clearer than writing out the DFS or BFS explicitly. In short, pseudocode cannot be fully standardized, because its goal is to be read and easily understood by a human.

That being said, there are some conventions that most pseudocode follows, which are considered easier to read than the alternatives. A short list is:

  • Pseudocode is generally written imperatively, that is as a set of functions or procedures which consist of sequentially composed instructions, if-then blocks, while, and for loops.

  • For variable assignment, $a \gets b$ or $a := b$ is generally preferred to $a = b$ as it distinguishes assignment from equality

  • Mathematical expressions are usually written as formulas rather than programmatically: e.g. "while $n \le \sqrt{m + 1}$" is preferred over while (n <= sqrt(m + 1)).

  • Data structures are named explicitly using standard naming conventions: for example, "dynamic array" for a growable, O(1) accessible list rather than something like "vector".

  • Function calls and control flow jumps are usually made explicit using a keyword: e.g. "return $x$", "call $f(x, y)$", "break", and "continue". "goto" and "label" are also sometimes used, though probably somewhat discouraged.

$\endgroup$
6
  • 9
    $\begingroup$ Another big difference I've seen between pseudo-code and programming code is that variables are sometimes described using sequence notation rather than a single letter. For instance, if you have a loop with a loop counter $k$ and a variable $a$ that is updated exactly once per loop iteration, it's common in pseudo-code to call this variable $a_k$ instead of just $a$; this is particularly useful if you have to write a mathematical proof of the correctness or time-complexity of the algorithm, and you want the notation of your proof to be consistent with the notation of the algorithm. $\endgroup$
    – Stef
    Commented Mar 14, 2023 at 9:53
  • $\begingroup$ The LaTeX is a good place to start. I do know what pseudo-code is. I guess its formality has increased over time and it now appears to be another code called Pseudo, instead of it being pseudo.... $\endgroup$ Commented Mar 14, 2023 at 13:22
  • 1
    $\begingroup$ Using $a_n$ instead of $a[n]$ to denote array access can be confusing, at least if a is explicitly created as an array ("let a be an …"). It's ok if $a$ is just an implicit sequence whose parts are initialised individually (for $i$ from 1 to n, do $a_i := 0$) $\endgroup$
    – Bergi
    Commented Mar 14, 2023 at 13:48
  • 2
    $\begingroup$ Pseudocode is written imperative if the goal is to show an imperative algorithm. Something like Okasaki's "Purely Functional Data Structures" doesn't write examples imperatively. $\endgroup$
    – prosfilaes
    Commented Mar 14, 2023 at 20:18
  • 1
    $\begingroup$ @prosfilaes: Okasaki's Purely Functional Data Structures claims to use Standard ML (with Haskell translations in an appendix), rather than a neutral pseudocode. That said, it conservatively extends Standard ML to support laziness, and it uses book-style formatting and characters instead of monospaced ASCII (such as smallcaps for signature names, bold and italics for syntax highlighting, α instead of 'a, → instead of ->, and × instead of *), so I won't blame you if you prefer to regard it as pseudocode! $\endgroup$
    – ruakh
    Commented Mar 14, 2023 at 23:50
7
$\begingroup$

There is no common standard because for languages of any kind (both in theoretical CS, i.e. more abstract languages like lambda calculus; as well as in practical programming languages used to write actual code) there always is a preferred mode of usage, or a type of problem where using a particular language would make most sense, compared to other languages.

As an example: you can use any Turing-complete language to solve any kind of problem we can think about; and basically everything that's worth talking about in this context is Turing-complete. So all languages can perform the same work. But depending on the problem to solve, using, say, a purely functional language like Haskell may be super easy and elegant, while solving the same problem in a purely imperative language like C might be very hard or at least annoying. And vice versa of course; you would program a Kernel driver in C, but not in ProLog.

The same goes for papers. Sometimes it may be perfectly optimal to use lambda calculus to talk about some problem; but sometimes you might be better off with a very basic imperative "language" which basically just formalizes natural language a little bit. You would use, for example, lambda calculus if the problem you wish to solve somehow benefits from the semantics of that language (and any proofs/theorems that are already established). But if you just wish to use a quick pseudo language to make some ideas clearer, a simple intuitive imperative notation with intuitive semantics may be just fine.

Finally, you can also whip up a quick DSL (domain specific language) which not only contains abstract language semantics, but also somehow includes features of the domain in the notation. For example, most of the symbols, conventions and semantics used in maths itself are, basically, a DSL - and if you compare that to notation for physical math, you will find so many differences that a person familiar with the one might be incapable to understand the other, albeit the other makes much more sense for that particular domain.

And within all these languages, the textual representation is usually a matter of taste and convention, which may be different in different special areas of CS; or even from country to country.

$\endgroup$
6
$\begingroup$

As others note, there won't be any one universal standard for pseudocode.

That said, Rosen's Discrete Mathematics has a particularly well-defined system for pseudocode (in Appendix 3), and if you were looking for a particular grammar, then it could be a good model.

$\endgroup$
4
$\begingroup$

There is no official standard, but I would argue that algorithm pseudocode conventionally follows much of the syntax of Dijkstra's Guarded Command Language, with influence from other structured programming syntaxes of the late seventies and early eighties, and often used explicitly in texts such as Carroll Morgan's Programming From Specifications (1990–1998). Because there is no officially maintained standard for pseudocode, and many CS papers do not explicitly place their algorithm description within a syntax and semantics, the relationship is not one of strict conformance, but of family resemblance.

The formatting provided by the standard LaTeX packages for algorithms are also strongly influenced by this syntax, and this tooling infrastructure helps continue the convention.

Some examples:

  • Using symbols like $\geq$ instead of the more common executable programming language syntax of >=
  • The use of logical predicates with richer set theory syntax as guards
  • The use of structured programming era style blocks for conditionals and loops, with named if/end if and do / od pairs, rather than braces, as in C-style languages, or whitespace syntax, as in Python.

There are some counter-examples, including the use of $\leftarrow$ rather than := for assignment, as in GCL. I suspect this is because of a certain continuity of mathematical style and because it saves slightly on horizontal space when formatting pages close to the page limit of publications and conferences. Some more careful close reading of papers historical and present could help trace the style lineage more precisely.

$\endgroup$
2
$\begingroup$

The type of pseudocode I’ve most commonly seen is loosely based on ALGOL, sometimes falling back to natural language or algebraic notation.

For example, compare this sample (from Wikipedia) of Algol-60:

BEGIN
INTEGER p, q;
y := 0; i := k := 1;
     for p := 1 step 1 until n do
         for q := 1 step 1 until m do
             if abs(a[p, q]) > y then
                 begin y := abs(a[p, q]);
                     i := p; k := q
                 end
 END Absmax

With this pseudocode from the second paper I checked at random:

Notation: The flight corridor ℬ; global guide path 𝒯;
Initial and goal position: 𝑝0, 𝑝g; local guide point 𝑝h
Input: 𝒯, 𝑝0, 𝑝g
Output: ℬ

2  Initialize ℬcur = GenerateOneSphere(𝑝0);
3  ℬ.PushBack(ℬcur);
4  while True do
5      𝑝h = GetForwardPointOnPath(𝒯, ℬcur);
6      ℬcur = BatchSample(𝑝h, ℬcur);
7      ℬ.PushBack(ℬcur);
8      if 𝑝g ∈ ℬcur then
9          break;
10     end
11 end
12 WaypointAndTimeInitialization(ℬ);

This doesn’t quite match the formatting of the original (Algorithm 1 on page 4), such as the syntax highlighting, and it introduces mathematical notation such as that very few programming languages support (Haskell being one that can), but you can see the similarities.

In particular, it retains the semicolons and end statements of ALGOL, even though only parsers that ignore whitespace need them, and they are completely redundant in pseudocode written for human eyes. This listing does not use the := assignment operator, but I have seen many that do. Because = sometimes means assignment, and sometimes a test for equality, you need to be careful to be unambiguous. This is likely one reason for the use of the left arrow (one of whose most influential users was Donald E. Knuth).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.