1
$\begingroup$

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to" like phrases to jump back or forward to another step, thus avoiding explicit loops). I mean something like this:

  1. Step: Do ...
  2. Step: If ..., go back to step 1. Else, do ...
  3. Do ...

This is in contrast to pseudocode that is written more in the style of source code of some structured programming language, like this. With this approach, one tends to avoid "go to" statements, which are considered harmful in programming. I wonder to what extent the criticism of go to statements applies also to the presentation of algorithms in theoretical computer science (outside of programming). I think if one uses something like Hoare logic to prove the correctness of some algorithm, it seems avoiding go to statements is the thing to do.

On the other side, I feel that the enumerative way of describing an algorithm has the advantage that whole algorithm is neatly split into a few chunks, which makes it often conceptually easier for me to read the algorithm, whereas the source code approach often contains many nested loops with many indentations making the algorithm hard to read.

Now I wonder, and this is my big question: Which of the two approaches (enumerative vs source code approach) do you think is more appropriate and suitable in research of theoretical computer science? Which style should be used in research articles? What are the advantages and disadvantages of the two approaches?

$\endgroup$
  • $\begingroup$ Why do you think that program logics cannot deal with control-flow commands like goto? That may have been the case in the 1960s but it's no longer the case today, and moreover, correctness arguments in algo papers tend to be informal, rather than using the rigour of Hoare logic (whether that's a good thing or not is a different question). As to which style to use, how about When in Rome, do as the Romans do: the fact that most algo papers use the "enumerative way" is a pretty good indication that it works well for algorithm description. The "style of source code" is more verbose. $\endgroup$ – Martin Berger Nov 4 '18 at 13:42
  • $\begingroup$ "Why do you think that program logics cannot deal with control-flow commands like goto?" Could you please give the exact quote from my post you are refering to? $\endgroup$ – user419308 Nov 4 '18 at 14:06
  • $\begingroup$ @MartinBerger: Concerning your answer "As to which style to use, how about When in Rome, do as the Romans do: the fact that most algo papers use the "enumerative way" is a pretty good indication that it works well for algorithm description. The "style of source code" is more verbose.", I am very thankful! :-) $\endgroup$ – user419308 Nov 4 '18 at 14:07
  • $\begingroup$ Note that usually you need to number the lines of your algorithm anyway, so that you can refer to individual steps in the text (e.g., in the proof of correctness). $\endgroup$ – Emil Jeřábek Nov 4 '18 at 14:42
  • 1
    $\begingroup$ I am actually sceptical about one style clearly dominating the other. I have done both, and I try to use the style that makes my algorithm and proofs as clear as possible. I tend to prefer pseudocode if the logic of the algorithm is somewhat complicated. $\endgroup$ – Sasho Nikolov Nov 6 '18 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.