Code vs pseudo-code

Question

What will the policy on providing code be?

In my question it was commented that it might not be on topic as it seemes like I was asking for working code. I wrote my algorithm in pseudo-code because my problem didnt ask for working C++ or whatever language.

Should we only allow pseudo-code here? if so, is there a standard at which we would need to keep in our pseudo-code?

I for 1 dont know if/what the syntax for pseudo-code is, so I just write it as a way in which I can read the code easily.

What should the guidelines be?

Answer 1

I think as a rule of thumb, if you need to write actual code, the question is a programming question and belongs on Stack Overflow but not here. If pseudocode is good enough and any language of the right variety would do, it's an algorithm question and is likely to be on-topic here.

Rule of thumb means that if you go looking for exceptions, you'll find them. For example, a question about the semantics of a programming language would be on-topic here and might show a code fragment.

Answer 2

As answerer, I am torn.

Clearly, pseudo code should be enough if written properly. However, pseudo code often is buggy and/or definite (by fault of the author).

Therefore, I like to write clear (!) code in a real programming language that allows high levels of abstraction, in particular functional languages (depending on the principle shown, this might be a good or bad choice). You have seen me use Scala. This has the advantage that I (and anyone interested) can take the code and execute it, if only for the purpose of "testing". Besides, the semantics are well-defined.

The same holds for questions: if real code is given I can run it, adapt and run it, and so on.

I think real code is fine as long as

• it is not overly detailed, i.e. helper functions should probably left out,
• the language features used are (sufficiently) clear to a reader unfamiliar with the language (to grasp what the algorithm is doing) and
• the question does not depend on the particular language used.

Answer 3

Coming from a perspective of a designer who specialized in typography, I claim that the fact that humanity still uses cuneiform also known as "universal mathematical language" is one of those cases where tradition defeats rationalization hands down. Pseudo-code is a tribute to this tradition of obscure symbolism, sloppy writing, legible only to the writer but not the readers, comfortable only insofar as to impose less restrictions on the writer, while disadvantaging the readers.

Computer scientists being, technically, a sub-division of mathematicians, will fight tooth and nail to keep the things just as they "had always been". Just as ancient Babylonians, who removed zeros from multiple digit numbers for conciseness! (actually, they must've been just lazy to inscribe those pesky zeros into their clay tablets). Pseudo-code is a modern form of this cuneiform.

My personal experience, as a programmer, is along these lines: most often the subject of pseudo-code comes up during job interviews, where I'm asked to present some algorithm in pseudo-code. Just for kicks, I tried to represent a Prolog or an ML program in make-believe Prolog or make-believe ML. You know what: those people asking for pseudo-code actually wanted Java. Except that Java is a bad programming language, where you cannot avoid writing a lot of inessential details. So, they wanted Java, but with type declarations removed and literals for initializing collections. Probably, if they ever saw Python, their need for pseudo-code would have been eliminated.

History of the problem

Perhaps to better understand the phenomenon, let's look into the etymology of the word. Interestingly enough we find that:

Compile (verb) — The process of producing from pseudo-code a specific routine for a particular problem ...

-- Grace Hopper's Programmer's Glossary, 1954

this is probably the first mention that I could find

So, actually, in the very early days of programming pseudo-code used to mean any high-level programming language, while code was the shorthand for machine-code! The rationale for using pseudo-code thus is clear: use a high-level language to allow higher level of abstraction. It was intended to be compiled, without it, it is gibberish.

Join the resistance

Gerald Jay Sussman, the author of SICP, one of the best books on programming, had also written a book on physics. An example page shows that he chose to use Scheme to represent formulas. To quote this book:

The mathematical notation is in one-to-one correspondence with the expressions of the computer language Scheme [21]. Scheme is based on the λ-calculus [12] and directly supports the manipulation of functions. We augment Scheme with symbolic, numerical, and generic features to support our applications. [...] The correspondence between the mathematical notation and Scheme requires that mathematical expressions be unambiguous and self-contained. Scheme provides immediate feedback in verification of mathematical deductions, and facilitates the exploration of the behavior of systems.

Also:

For very complicated expressions the prefix notation of Scheme is often better, but simplification is almost always useful.

---

In conclusion: I would discourage the use of pseudo-code as it is used today (say, in LaTeX packages). It is almost never representative of the actual tools the programmer will have to implement the algorithm. It is conducive to a particular kind of programming and almost entirely ignores a lot of other valid approaches. There are better tools, which offer automatic verification, generation of example problems and solutions, convenient editing environments, better typography, which altogether helps sharing understanding of the problem.

Answer 4

As per request, here are examples of pseudo-code posted to SE.CS with explanation for why they are problematic:

Note: I did not select any examples specifically for this demonstration, I just took first five search results containing any pseudo-code.

What is the meaning of this pseudo-code function?

Function end(q)
    return ∀q_i ∈ subtreeNodes(q): isLeaf(q_i) ⟹ eof(Tq_i)

1. Without looking at the reference, can you tell whether this function returns a boolean or a set?
2. What is the priority of infix operators here?
3. return in Haskell means something absolutely unrelated to return in C.
4. There are plenty of languages which don't have return keyword at all. The users of such languages would be puzzled by this construct.
5. Not to mention the author of the question couldn't figure this "concise" piece of information, as can be seen from the quote:

   A function in the algorithm confused me, since I can understand what it is supposed to do, but can't deconstruct the notation:

Failing to understand the pseudo code of the inorder traversal

sub P(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      P(TreeNode.LeftNode)
   Output(TreeNode.value)
   If RightPointer(TreeNode) != NULL Then
      P(TreeNode.RightNode)
end sub

1. There are quite a few languages which cannot just output anything at arbitrary place in the program. Haskell, Mercury, J are some examples.
2. The concept of pointer is specific to a very small fraction of languages with manual memory management.
3. Technically, this isn't some non-existing pseudo-language. This is valid Basic.

Filling Rows of a Matrix Subject to Conditions

// (N+1)*(N+2)*(N+3)/6 is a lot
array[2*N]

// What you'll call
printRows(N)
   printRows(N, 1)

printRows(N, pos)
   if pos == array.length + 1
      // reached the bottom-most recursion call
      // we don't really have a choice of value here since we need to get to N
      //   and only have the current value left
      array[array.length] = N
      print array
   else
      for i = N; i >= 0; i--
         array[pos] = i
         printRows(N-i, pos+1)

1. This pseudo-code assumes that arrays can be dynamically extended, which is not true for majority of languages which have array data structure. And especially not in the way suggested in this piece of code.
2. Quite a few languages use // as integer division (used to mean comments here).
3. The overall look and feel is that the author tried to cross-breed Python and C, but it didn't quite work out.
4. The code still displays uninteresting details of implementation of iteration in C-like languages (something most of programming languages don't have / don't use). I.e. this code is conducive of C-like languages, and disregards other ways of accomplishing the same task.

Why is the complexity of this nested for loop not $O(n^2)$?

mystery(n):
if n <= 50 :
    for i = 1 ... n :
        for j = 1 ... n :
            print i*j
else :
    mystery(n-1)

1. This is practically Python 2.7 (except for whatever reason the writer decided to replace range(n) with 1 ... n). This didn't make the code more concise / shorter, but it made it impossible to run on an interpreter.

https://cs.stackexchange.com/questions/47637/proof-of-complexity-for-depth-first-search

1.Stack stack; // i have named my stack as "stack"
2.isVisited(root) = true;
3.stack.push(root);
4.while(stack is not empty)
5.{
6.      currentNode = stack.top();
7.        stack.pop();
8.        print(currNode); //or whatever operation you want to do!
9.       for all each v in adj[currNode]
10       if(!isVisited[v])
11        {
12           stack.push(v);
13          isVisited[v] = true;
14        }
15 }

1. Because this code was written by a sloppy writer, and there wasn't a text editor to help the writer, the code came out badly formatted.
2. for all each - that's definitely a nice construct to have in your repertoire.
3. Again, this is, basically, Java, with typical for Java and family array access, destructive assignment, while loop and so on. This code is only "pseudo" in the sense that it is pseudo-Java. It is just bad Java. If, however, the writer would put a little bit more effort and actually wrote a Java program to do that, he or she would have had interned the algorithm, followed the inner workings of it, had the editor help them figure out what is possible and what isn't wrt their code.