9
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ pseudo code is code without a compiler :). So I don't think there needs to be a specific requirement for one or the other, as long as the question is not linked directly to a specific code issue (for which programmers/SO might be more appropriate) $\endgroup$ – Suresh Mar 7 '12 at 23:00
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I like this answer particularly the, "Rule of thumb means that if you go looking for exceptions, you'll find them", I think this is the best way to deal with this question. $\endgroup$ – BrotherJack Apr 10 '12 at 3:30
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I agree this is not so clear cut, and I would also encourage using actual code for these reasons: 1) the "pseudo" in the pseudo-code isn't really pseudo. It's just bad Pascal, so bad that if people actually used Pascal instead, the overall effect would have been better. 2) Pseudo-Pascal encourages the kind of thinking inappropriate for many languages. 3) Real programming languages are formally defined, the definition is itself verified multiple times by lots of people, while ad hoc invented code tends to be inconsistent / poorly defined. $\endgroup$ – wvxvw Sep 30 '15 at 7:05
  • 1
    $\begingroup$ @wvxvw Items 1)-3) are irrelevant. Pseudo code has one purpose and one purpose only: communicate concepts to humans. Not every piece of pseudo code manages that (e.g. by missing the "everybody (in the target group) understands the syntax" paradigm), and some pieces of real code do. Nevertheless, it's that purpose only that should drive your choice of how to express an algorithm in most CS contexts. (Then you can implement them for tests and experiments.) $\endgroup$ – Raphael Oct 2 '15 at 6:46
  • $\begingroup$ My point is that pseudo-code fails to communicate concepts to humans more often than almost any other programming language. But I'm not going to convince you or anyone else by saying it again. I've already lost count of how many times I've repeated it. If you choose to ignore it, there's nothing I can do to help it. $\endgroup$ – wvxvw Oct 2 '15 at 8:35
  • $\begingroup$ @wvxvw You have repeated this claim, yes. So far, you have failed to provide evidence. On the other hand, the fact that generations of students and researchers have been working successfully (arguably) with pseudocode shows that it can't be too bad. (Again, I don't claim every piece of pseudo code is without problems.) $\endgroup$ – Raphael Oct 2 '15 at 12:24
  • $\begingroup$ One can only go so far as to bring the camel to the water. You can be in denial no matter what I say: this is what I mean by theological debate. Generations of researchers worked with pseudo-code? so what? Generations before Guttenberg wrote books on parchment by hand, successfully! Generations of sincere believers sacrificed the lives of other sincere believers to whatever gods they prayed to, arguably successfully. Industry and agriculture of generations successfully employed slaves, but it can't be too bad, can it? $\endgroup$ – wvxvw Oct 2 '15 at 12:35
-4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I don't understand how your interview experiences are relevant. We're not asking for Java or pseudo-Java. We're asking for pseudocode, similar to what is typically found in algorithms textbooks. Talking about your experiences in interviews hardly seems relevant to our policy here, as it attacks a strawman we are not advocating. Analogies like cuneiform are provocative but are not a substitute for a substantive argument. $\endgroup$ – D.W. Sep 30 '15 at 17:39
  • 1
    $\begingroup$ As far as "not representative of the actual tools the programmer has", I'm not sure what you mean by that. I doubt you are claiming that algorithms written in pseudocode are not implementable. If you are claiming that code is easier to read, or more concise, than pseudocode, I feel like it'd be more persuasive if you could give some examples. Also, you don't address the reasons for pseudocode, which are that (a) pseudocode is typically more concise than working code; (b) there is no single language that all of our readership is familiar with. $\endgroup$ – D.W. Sep 30 '15 at 17:42
  • $\begingroup$ This is an incomprehensible rant, not an answer. $\endgroup$ – David Richerby Sep 30 '15 at 17:44
  • $\begingroup$ Let me suggest that a more persuasive way to make your case would be with data. Can you select a random sample of, say, 5 recent posts that used code, and make the case that their code is more comprehensible than pseudocode would be? Or a random sample of 5 posts with pseudocode, and show an example of how they'd be clearer if they used code rather than pseudocode? $\endgroup$ – D.W. Sep 30 '15 at 17:45
  • $\begingroup$ @D.W. Yes, I know what is typically found in algorithm books. Being a typographist by trade, I have some idea of how that works. Yes, I claim that algorithms written in pseudo-code are gibberish more often then algorithms written in any of the standardized programming languages. Pseudo-code are never more concise than any other programming language simply because it is a programming language, just a bad one (think Java / Cobol). There is no difference in being familiar with Python and pseudo-code. $\endgroup$ – wvxvw Sep 30 '15 at 18:24
  • $\begingroup$ @D.W. I'll look for examples with failed pseudo-code. I also have lots of those in my textbooks, but I'll also try to find some here too. $\endgroup$ – wvxvw Sep 30 '15 at 18:24
  • $\begingroup$ Whatever makes you think that "real" code will have higher quality than pseudo code, if prepared by the same author? $\endgroup$ – Raphael Sep 30 '15 at 18:58
  • $\begingroup$ @Raphael two things: 1) SO site. Whenever I look at the questions there, in the vast majority of cases the code is at least in the shape it compiles, can be interpreted etc. Pseudo-code posted here or everywhere else is just gibberish. 2) There is a very advanced infrastructure to ensure that real code makes sense: all sorts of automatic checkers like compilers, interpreters, linters, PMD and so on. Not all authors will know how to use it, but some of them will, which is a net win. $\endgroup$ – wvxvw Sep 30 '15 at 20:13
  • $\begingroup$ And why do you think that people who would rather write pseudo code would bother to use such tools? (SO posters != cs.SE posters) $\endgroup$ – Raphael Sep 30 '15 at 21:16
  • $\begingroup$ @Raphael I'm participating in code.org project and I routinely get updates on "small victories" of programming literacy. There are quite a few places in the world where programming has been made a mandatory subject in elementary schools. Understanding real code is closing in on understanding written natural language. Thus you are much more likely to find a person who will understand Python or Java than someone who'd understand ad hoc invented language. Consequently, if you expect meaningful conversation, you'd try to use a common language. $\endgroup$ – wvxvw Sep 30 '15 at 21:45
  • $\begingroup$ In computer science, (procedural) pseudo code is much more common than any fixed programming language. $\endgroup$ – Raphael Sep 30 '15 at 22:54
  • 2
    $\begingroup$ "There is no difference in being familiar with Python and pseudo-code." This is simply not true. The meaning of pseudocode is (at least supposed to be) self-evident; the meaning of a piece of code in any particular language may depend on subtle features specific to that language and require a deep understanding of the features of that specific language. Implementations in actual code also tend to be optimized to at least some extent and contain low-level detail, which tends to obscure the underlying algorithm. I'd much rather read "append to list" than the equivalent C pointer manipulations. $\endgroup$ – David Richerby Oct 1 '15 at 12:35
  • 2
    $\begingroup$ @wvxvw "I've seen a lot of pseudo-code and I never seen even a single one which was in some way more evident than an equivalent program written in any real programming language." You mean "written in any real programming language that I understand well." And that's precisely the point I'm trying to make. Well-written code in an unfamiliar language can be completely incomprehensible; well-written pseudocode should be comprehensible to everyone. (And badly written anything is incomprehensible, whether it's your favourite language, pseudocode or anything else.) $\endgroup$ – David Richerby Oct 1 '15 at 12:42
  • 1
    $\begingroup$ Sorry, but I've never had any difficulty understanding what "append to list" means. If you prefer, I would have written "append X to list Y" but didn't have enough characters in the comment. If you think that "append X to list Y" is anything less than crystal clear then, I'm sorry, I have zero comprehension of where you're coming from. $\endgroup$ – David Richerby Oct 1 '15 at 12:46
  • 1
    $\begingroup$ Your analogy with mathematics is fallacious. While mathematics sometimes tries to be very precise, it is usually written for humans. Typical texts have finite (even small) "unfolding" depth, i.e. implicit conventions and ambiguities remain. Pseudo code is similar: it is written for humans, not computers. The promise of the author is, "all detail that is relevant to the point I'm trying to make is here". Of course, not every piece of pseudo code serves every purpose -- nobody disputes that. But then, so doesn't "real" code because detail can obscure. $\endgroup$ – Raphael Oct 2 '15 at 6:35
-4
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ You've failed to show in what way pseudocode is problematic. The only problems you raise is when treating those snippets as code in an actual programming language rather than pseudocode. For example, with the first snippet: 1. who cares? if it did matter the explanation in English should say. 2. all common math texts are consistent on that score; for ambiguous cases there's parentheses. 3. The meaning of return in Haskell and C is irrelevant. 4. “Return” is an English word. 5. How would a programming language that the asker doesn't know have been any better? $\endgroup$ – Gilles 'SO- stop being evil' Sep 30 '15 at 20:29
  • $\begingroup$ @Gilles that's just your opinion and you wanting to support an idiotic tradition. The poster says they don't understand the code, but you will gladly ignore it. The poster says there isn't actually any pseudo-code, there are only pseudo-Java, pseudo-C, pseudo-Basic, but you'll ignore it and go on fantasising about some other kind of "good" pseudo-code. Point by point reply will follow in the next comment. $\endgroup$ – wvxvw Sep 30 '15 at 20:32
  • $\begingroup$ 1. I care as any other reader does. I want to understand why was this even written. The purpose of code is not to stay clear of writing in English, but to define exact meaning of words. 2. All common math textbooks are glorious examples of bad typography and bad language design. You could use parenthesis, but you didn't, and now nobody knows what you meant. In standardized code this wouldn't have happened. 3. Again, you should not use undefined words in math. If you are going to use English, you should be posting to SE.EL instead. $\endgroup$ – wvxvw Sep 30 '15 at 20:35
  • $\begingroup$ 5. The programming language is defined. It has a standard written for it, that standard is something that you can understand through experimentation with real-life implementation, through talking to a community of people with shared understanding. None of that is possible when reading gibberish brainfarts which you call pseudo-code. $\endgroup$ – wvxvw Sep 30 '15 at 20:37
  • 2
    $\begingroup$ "for whatever reason the writer decided to replace range(n) with 1 ... n" The reason is, presumably, that "1...n" is comprehensible to anyone, whereas "range(n)" requires knowledge of exactly what that function/keyword in Python does. Even if I guessed that it produces a range of integers (and I don't think I would), I'd have to look at the manual to see whether that range is 0..n or 1..n or maybe even 0..n-1. $\endgroup$ – David Richerby Oct 1 '15 at 12:37
  • $\begingroup$ @DavidRicherby Even if I guessed that 1 ... n produces a range of integers (and I don't think I would), I'd have to look at the sky to see whether that range is 1..n or maybe even 2..n-1. $\endgroup$ – wvxvw Oct 1 '15 at 15:33
  • 1
    $\begingroup$ @wvxvw Um. You think that "1...n" might mean "2..n-1"? That's a really weird interpretation of one extra dot. So weird that I can't actually believe you're being serious. $\endgroup$ – David Richerby Oct 1 '15 at 15:38
  • $\begingroup$ @DavidRicherby google for E. Dijkstra "why numbering should start at zero". PS. Compare your minor problems of looking up the Python language reference (google for "Python range") and my not so minor problems of googling for "pseudo-code ellipsis", and how likely I am to find out what that may mean. $\endgroup$ – wvxvw Oct 1 '15 at 15:41
  • 1
    $\begingroup$ @wvxvw Your line of reasoning is, basically, "Under the assumption that I am correct in my assertions, my point is correct. So you all have to agree." I hope you can see why that won't work. I agree with Gilles: you have not shown how the use of pseudo code was problematic here. In 1, for instance, everybody with a basic knowledge of mathematics knows what it means. The user would not have fared better had it been real code. $\endgroup$ – Raphael Oct 2 '15 at 6:43
  • 1
    $\begingroup$ Anyway, my example is this. Which version of the algorithm do you think is most comprehensible? $\endgroup$ – Raphael Oct 2 '15 at 6:43
  • $\begingroup$ @Raphael I have basic knowledge of mathematics, and I have absolutely no clue what 1 means. What happens is that posters like David make arguments from ignorance (I don't know X, therefore not X), but when faced with the fact that someone else knows X they choose to stick to their blind faith or tradition, instead of revisiting "I don't know X" part. And this arguments becomes a theological debate. $\endgroup$ – wvxvw Oct 2 '15 at 8:41
  • $\begingroup$ @Raphael as for your other questions: I'd say the last one. I don't know Isabelle, so it's hard for me to judge immediately, but if my goal was to understand the algorithm, I'd invested an effort and learned it. The high-level one gives a hand-wavy "take it on faith" description which I would ignore, and the mid-level uses some bizarre broken C to try to illustrate the idea. Sometimes I don't have enough time to learn the language, and I'd try to guess what the author wanted to say, but I hate it when I'm in this situation. $\endgroup$ – wvxvw Oct 2 '15 at 8:51
  • $\begingroup$ @Raphael look at this poor guy: cs.stackexchange.com/questions/47665/… he's been struggling with his pseudo-code for a week now. The piece of crap that his professor gave him under the title of "pseudo-code for graph traversal" is a nightmare. It's so bad that you cannot even understand whether they meant depth-first or breadth-first variant, or maybe something else entirely. It has everything: typos, unbalanced delimiters, rogue variables... and this is how all such codes are. $\endgroup$ – wvxvw Oct 2 '15 at 9:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .