Why Pseudo-Code?

When I learned Python in 1999 it was advertised, among other things, as "executable pseudo code". At my universities numerical studies we used a Pascal style pseudo code notation. Maybe it was even actually Pascal, I don't remember exactly. I didn't question a non-standard notation that changed from author to author which looked like imperative programming language syntax and was understood like imperative code but aimed to represent intentions better than any actual programming language.

Over the years I began to wonder about this pseudo-code idealism, how it became a common practice and why it is still used today? Any thoughts?

Sketching

I think of it as the coding equivalent of an artist's sketch;

pseudo-code : code :: sketch : finished painting

(a way to get the essence of an idea down in concrete form without worrying about the details.)

By joel.neely at Sat, 2009-09-26 13:57 | login or register to post comments

When I write a draft in a

When I write a draft in a language like German I do not start inventing new punctuation, an own grammar etc. unless I'm doing concrete poetry. Language designers invent new syntactic forms but this wasn't the type of activity I addressed. It's rather about using p-c in straightforward algorithmic descriptions where matching between p-c and imperative code is about 1-1 modulo some syntactic subtleties. The idea that there might be a pure-language-of-the-mind used by a genius in its artistic freedom is a romanticism and it isn't quite considered as eccentric or exceptional as I perceive it. This makes me stunned.

By Kay Schluehr at Mon, 2009-09-28 11:13 | login or register to post comments

Pseudocode wasn't always executable

As Joel points out, pseudocode allows for sketching, which can still be useful today. But pseudocode was more important back when it wasn't executable, i.e. when extant & popular languages weren't high-level enough to be capable of expressing "executable pseudocode".

Also, a lot of pseudocode was lower-level than it needed to be, perhaps being limited by the author's imagination. (Reverse Sapir-Whorf - thought limits language!) Pseudocode that looks like executable Pascal tends to fit this category.

Some of the better pseudocode can be found in the higher layers of literate programs written in the Knuth style.

By Anton van Straaten at Sat, 2009-09-26 16:16 | login or register to post comments

Good questions

The history of pseudo-code would be a fascinating thing to study. I don't recall seeing an attempt to study this aspect of the history of computing.

Here are a couple of thoughts about the other issues. First, I think an important reason for using pseudo-code is managing expectations. When code is presented the reader expects it to be complete and accurate, something the author often wants to avoid for various reasons. By declaring something is pseudo-code the burden is shifted to the reader. You as a reader may not be thrilled about this aspect of using pseudo-code, but I am quite certain this is one reason why people use it...

Second, pseudo-code enables mixing and matching of styles and notations. If at some point in the algorithm using vector notation is more convenient, you can simply use it and expect the reader to understand that a translation would be needed in order to turn the vector expression into C code, say. Instead of using the most appropriate language for each subroutine etc., one can use pseudo-code and forget about the choice of notation almost entirely. This sort of communicative malleability is common in math, say, but not when source code is presented. This non-malleability can be burdensome and hence avoided by the use of p-c.

By Ehud Lamm at Sat, 2009-09-26 21:22 | login or register to post comments

Managing cognitive complexity

Rachel Bellamy's ACM-paywalled What does pseudo-code do? a psychological analysis of the use of pseudo-code by experienced programmers says In the analysis based on [her study], I describe the kinds of tasks done using pseudo-code and pen and paper, and I offer an account of why these tasks are done using these particular notations and this medium. This study suggests that programmers use pseudo-code and pen and paper to reduce the cognitive complexity of the programming task.

By Charles Stewart at Sun, 2009-09-27 19:58 | login or register to post comments

Indeed, and opium causes

Indeed, and opium causes people to sleep because of its dormitive virtue.

By Ehud Lamm at Sun, 2009-09-27 20:10 | login or register to post comments

Well...

The other comments in this thread seem to treat pseudo-code as being in the first place a medium of communication. Bellamy's study is concerned with programmers using pseudo-code as a reasoning tool.

By Charles Stewart at Sun, 2009-09-27 21:24 | login or register to post comments

Fair enough. (Assuming that

Fair enough. (Assuming that there is a real distinction between communicating and reasoning, of course.)

By Ehud Lamm at Mon, 2009-09-28 00:33 | login or register to post comments

Communicating & reasoning

real distinction — no clear separation, but different pragmatics: one is public, the other is, normally, a private act.

By Charles Stewart at Mon, 2009-09-28 05:35 | login or register to post comments

Well, there are some doubts

Well, sure, but there are some doubts about the significance of this, as you surely know (riddle: what does PI 243-315 signify?)

By Ehud Lamm at Mon, 2009-09-28 05:45 | login or register to post comments

Stumped

No idea where your riddle is going.

The point about significance, I guess, is an allusion to the private language argument. To make the point in Wittgensteinian terms, the two activities are different language games, with different classes of participant, and different `rules' about what counts as valid `moves' within the language game.

By Charles Stewart at Mon, 2009-09-28 05:49 | login or register to post comments

Yep, the private language

Yep, the private language argument is what I was getting at, and the reference is to the sections in W's Philosophical Investigations (PE was supposed to be PI, sorry about that...) where the argument(s) is presented.

By Ehud Lamm at Mon, 2009-09-28 06:22 | login or register to post comments

Pseudo-code is code that is not machine code

Grace Hopper's Programmer's Glossary, 1954, defines:

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

and likewise

Interpretation decodes the pseudo-code and refers to static subroutines during compilation. It does not produce a specific routine for a problem.

Cf. p7, J.L. Jones, 1954, A survey of automatic coding techniques for digital computers [scanned PDF]. I'm guessing that the glossary of Hopper's he cites is a preprint of the ACM "First glossary of programming terminology", but the text doesn't have proper references. It is well worth looking at, though.

By Charles Stewart at Sun, 2009-09-27 21:51 | login or register to post comments

Thanks! I remembered

Thanks! I remembered something like that, but I wasn't sure. Possibly in Mythical Man Month (I can't seem to find this usage there now, fwiw)?

By Ehud Lamm at Mon, 2009-09-28 00:56 | login or register to post comments

python is not "executable pseudo-code"

Bah.

One of the main ways people use pseudo-code on paper or in publications is to bring in compact notations from mathematics that aren't commonly found in programming languages.

Here is one fragment of pseudo-code from the first journal I grabbed:

  e <<_{_f} lock(TR, X, i, R_j)

Here is another from a different article:

  f := minimum {j ∈ γ:CG(z,γ,j) = true};

In those cases, the notation refers in a familiar way to a kind of naive theory of finite sets and families. The programmer is expected to be able to puzzle out was to actually implement, say, an appropriate representation for the set at hand, but for reasoning about the correctness of the algorithms, those details are inconsequential and the math notation more helpful.

Another common use of pseudo-code is to explain a general structure which many programs might have, but for which there is no practical need in most cases to explicitly code the pattern. For example:

  initial declaration;
  repeat forever
    noncritical section;
    trying;
    critical section;
    exit;
  end repeat

I can't imagine ever realistically want to have a piece of code that says all that. The abstraction is handy for reasoning about the semantics of the program but it would be strange and distorted to try to write the program that way, adding definitions for something like critical section. The closest I can imagine would be in a literate programming environment but even there, one would likely choose a more descriptive and application-specific name than critical section.

Python lets you indicate nesting by indentation. It's light on punctuation (like ";" at the end of statements). In that way it resembles some popular kinds of pseudo-code, but that's not the same thing as being "executable pseudo-code".

Finally, especially with "pen and paper" (or an editor-equivalent), people use pseudo-code to just down a rough draft of code but without worrying about dotting t's and crossing i's to the satisfaction of a compiler. They use it as a "rough draft" mechanism before something is ready to give to a compiler. For example, I often write "code" like this pseudo-C fragment:

   if (x == y)
     exit (2);
   else
     {
       reactivate the foobar device;
       log the condition;
     }
   cleanup ();
   return 0;

A virtue of that is that if I do pass such code through the compiler, I'll get error messages that take me directly to that part of the code I forgot to finish earlier, where I've left a note of what code is needed there. The virtue here is partly, precisely, that the pseudo-code is not executable.

-t

By Thomas Lord at Sun, 2009-09-27 23:01 | login or register to post comments

I hate pseudo code. My utterly cynical view of pseudo-code

One of the main ways people use pseudo-code on paper or in publications is to bring in compact notations from mathematics that aren't commonly found in programming languages.

To me that invariably comes down to one of these cases...

The language the author codes in is insufficiently expressive and lacks a decent library.
The author is an academic writing for academics and expects them to have years in which to look up and puzzle out the weird notation, which he won't bothered to actually define, (but is subtly different from what other authors are using).
He is incapable of writing readable code.
He hasn't actually done this himself... but if he did, he would do something like this....

Explain a general structure

Think of writing it in a real language and then running it through the compiler / interpreter as a sort of spell & grammar checker for pseudo-code. You spell check and grammar check the rest of your document, so why not the pseudo-code?

Rubies (and perl's) -c "check syntax only" option is very handy for that.

At least a real language is unambiguous and has a publically well defined meaning.

By John Carter at Tue, 2009-09-29 01:51 | login or register to post comments

on hating pseudo-code

Perhaps we need a Bourbaki for pseudo-code.

-t

By Thomas Lord at Tue, 2009-09-29 02:35 | login or register to post comments

Another use case...

...is to try to express exactly what an algorithm is, without the distraction of how this or that programming language would realise it.

Think of writing it in a real language and then running it through the compiler / interpreter as a sort of spell & grammar checker for pseudo-code.

This is a good point, and I think it is a case where very dynamic languages like Smalltalk, which are tolerant of incomplete programs, have a valuable edge. We might say that pseudo-code is an approximation to executable code (a definition with a principled connection to Hopper's use of the term); then it is a property of some languages that they are tolerant of incomplete approximations in code.

By Charles Stewart at Tue, 2009-09-29 07:28 | login or register to post comments

Examples in Python

I'm not sure about your first example without knowing what <<_f does, but your second example would be the same in Python:

f := reduce(min,[j for j in Î³ if CG(z,Î³,j) == true])

Your comments about the need to deduce proper representations and relationships would hold if efficiency was a concern, but psuedo-code tends to be used for prototyping and sketching in which case the efficiency would be irrelevant.

I'm surprised to hear that people were touting Python as a form of executable psuedo code back in '99 as the language has changed a lot since then, and I don't think those earlier versions would live up to that promise.

Also the pedant in me would claim that "executable psuedo-code" is an oxymoron, as the designation does really mean "here is something like code, that is not". Much as you've described in your last example.

By Andrew Moss at Sat, 2009-10-03 20:21 | login or register to post comments

examples in Python

I'm not sure about your first example without knowing what <<_f does, but your second example would be the same in Python:
f := reduce(min,[j for j in Î³ if CG(z,Î³,j) == true])

The problem is that the python code is not obviously "the same". The Python version of the code is doing left to right reduction using binary "min" on a temporally sequential set of of values returned by the "_iter_" method of the object bound to Î³. In only a subset of programs where such a python statement occurs will the semantics of the statement conform to the model of sets used in the paper. Moreover, the mathematical discussion (of the mutual exclusion problem) in the paper does not rely upon using "reduce" but (implicitly) defines "minimum" in terms of second order logic using quantifiers.

It would be terribly awkward to have to rewrite the discussion and proofs in the paper using Python as opposed to ordinary math notation.

Oh my goodness - the paper is actually on-line! Please enjoy:

Leslie Lamport's "The Mutual Exclusion Problem" parts I and II from 1986, JACM v33#2. Independently of our burbling here about pseudo-code, it's a beautiful (two part) paper.

-t

By Thomas Lord at Sat, 2009-10-03 22:18 | login or register to post comments

The code is exactly the

The code is exactly the same, but only for the correct definition of "same". Your two examples were provided without context, in particular there was no context for min, and so the assumption in the Python code that it would be the standard definition was the same that the reader made.

Refining this code now that we know that the min function was in fact very different is easy - just override the definition of min. It will still compare two objects in a partial order. The only requirements for reduce to execute correctly is that the new min function should be associative and commutative, as we know min defines a partial ordering this is so.

Although the sequence returned by __iter__ is an arbitrary and transient list of the elements in Î³, the operator CG is stateless and so the filtering operation will alway produce the same subset regardless of the ordering chosen by __iter__. The only salient feature is that the iterator is complete over the container.

Anyway, the paper seems to use a standard set theory, regardless of the details of the (rather elegant) logic defined in it. It is not clear in what way the statement semantics will not conform to the model of sets, as you suggest. If I have read (understood) you correctly then hopefully the preceding description will demonstrate that the model produced by the original pseudo-code statement is the "same" as that produced by the Python snippet.

Thanks for the pointer to the paper. I read some of Lamport's work on clock synchronisation a few years ago but didn't find this particular gem. As you say, it's a very beautiful paper. Oh yes, and I wouldn't suggest rewriting proofs or discussion in papers using something like Python. The lovely thing about pseudo-code is that we can skip this justification of semantics completely and say "well, it's only a pseudo-code, it's *obvious* what it does...."

By Andrew Moss at Mon, 2009-10-05 11:31 | login or register to post comments

notations, theories, and pseudo-code

The two main reasons I say the pseudo-code and the Python are different:

(Trivial reason): The pseudo-code makes no mention of "reduce" it mentions the minimum value of a set. That is, the semantics of the pseudo-code would be defined using quantifiers (x in Y such that for all z in Y, x

(Deeper reason): That higher level of abstraction links the notation in the pseudo-code to elementary set theory and second order logic, making the code easier to write about. For example, if I see, in pseudo-code, v := min { some set } then I know that there does not exist some value z in the set which is less than the value assigned to v. I know that by definition. I can use that fact in proofs, etc. In contrast, as you've shown yourself, I can't do that with the python code unless I first stipulate a lot of side conditions that python itself doesn't (and can't) enforce. If I want to get to that lemma about the non-existence of z, from the Python code, I have to start adding all these side notes like requiring that the "new min function is reflexive and transitive". By the time I've described all of these conditions, I'll essentially have reduced my idiomatic use of python to the original pseudo-code but re-expressed in awkward and unfamiliar notation.

-t

By Thomas Lord at Mon, 2009-10-05 16:57 | login or register to post comments

The Myth of DWIM

No one has yet mentioned one of the cornerstones of the "executable pseudo-code" meme: DWIM ( Do What I Mean ).

This is the deep belief that many users of technology have (including programmers, who really should know better) that computers are just being pedantic or obstructive when they behave as we instruct them, not as we intended. If not the computers, maybe it is the designers of the interface who were just being pedantic or obstructive, so that the poor user is forced to be so explicit with instructions.

DWIM posits that you should be able to leave out "extraneous detail" and have things work out, because of course, we know what mean, don't we? We are used to making hand-wavy arguments to ourselves and other people, and we take it as given that we could trivially work out the details if need be.

Through programming we very often discover that when we drill down into the details we DON'T actually know how to fill them in without a lot of work. And sometimes we find that the details actually sink our "great idea" of what was going on completely, as we uncover contradictions and woolly-minded premises.

So why does this myth continue to exist, even among programmers? Self-soothing optimism, I think.

We can't bear to confront the inadequacies of our understanding that real coding lays bare. ;-)

By Marc Hamann at Tue, 2009-09-29 13:05 | login or register to post comments

accidental vs. essential complexity

i think it is because a lot of what we have to specify is stupid crap that we shouldn't have to specify cf. manual memory management. as new and better languages raise the level of abstraction and expressive power available to us, the more we can write "pseudocode" that is actual code, and yet have it miraculously DWIM because WIW is WIM.

By raould at Tue, 2009-09-29 18:01 | login or register to post comments

Algorithmic complexity

the more we can write "pseudocode" that is actual code, and yet have it miraculously DWIM because WIW is WIM.

I was referring to "essential" algorithmic complexity, such as when on the surface we think we understand the "simple" problem, but it turns out to have hidden depths.

High-level code is not really pseudo-code, is it? It's code...

I think the use of pseudo-code in an algorithms textbook, where well-studied, well-defined and very general algorithms are described this way as a learning aid (and to protect textbook sales should language fashions change ;-) ) is perfectly legitimate and quite different from the DWIM philosophy applied to designing algorithms, or languages.

By Marc Hamann at Tue, 2009-09-29 20:34 | login or register to post comments

You've nailed it!

You've have restated my cynical view perfectly. I'm in full agreement.

One of the "woolly" bits that real code, even in the most expressive and succinct of dynamic languages, forces to the front is dataflow and causality.

In every chunk of "pseudo-code" is a line that basically says "do what I mean".

If you replace that with real code invocation of a function...

  do what I mean

you suddenly realize that you have constrained the "do_what_I_mean" function to operate _only_ on the instance variables, class variables and global variables visible to it.

Whoops.

That probably isn't what I meant.

  do what I mean with the following list of data items and returning ...

Suddenly you realize your pseudo code is actually quite messy and complex, and perhaps, you haven't really thought the structuring through. ie. You are using pseudo-code not as a communication medium, but as an excuse for sloppy communication.

You realize pseudo-code is like a person mumbling. Easier to do, but lazy and irritating.

By John Carter at Thu, 2009-10-01 00:32 | login or register to post comments

You realize pseudo-code is

You realize pseudo-code is like a person mumbling. Easier to do, but lazy and irritating.

This coincides nicely with the cognitive scientists opinion about "complexity reduction" except that it lacks a para-scientific touch.

On Sunday we send prayers to Church and Turing. On Weekdays we believe in ghosts and fairies who order the loose natural language material which ends up as precise meaning and concise syntax.

By Kay Schluehr at Thu, 2009-10-01 02:32 | login or register to post comments

DWIM and peanut butter sandwiches

When I first learned to program in a structured way (as opposed to a self-taught random hacking way, not necessarily, though actually, Structured Programming) we used pseudo-code as a means to bridge the gap between our natural DWIM methods of communication and the realities of trying to get the peanut butter sandwich made.

I'm sure many of you remember the instructor sitting in front of class with bread, a knife and peanut butter saying, "I know nothing about anything, please teach me how to make a peanut butter sandwich." What ensued was an excellent session of hilarity, frustration and enlightenment. The tool we used to this was our own pseudo-code made up on the fly while we tried to get this idiot to make a sandwich.

The instructor then took what we had devised and began to transform it into gradually more formal language until we had a real computer language (Pascal at the time). Thus we learned how to use pseudo-code as a reasoning tool for things we didn't really understand how to do and we also learned the concept of compiling/interpreting as being analogous to that transformation from pseudo-code to compilable code.

I still find it useful from time-to-time, but really only for lower-level or really verbose languages when the detail is not necessary to the development of the algorithm.

And it seems to me that, much like many things from computing's past, the use of pseudo-code is being replaced by higher level languages that allow for more abstract representation. Pseudo-code with lower level languages allows one to "program" at a higher level and then compile it down to the target language, just as earlier programmers would code in (perhaps first pseudo-code, then) assembler and then assemble it (quite literally) into machine code by hand. First, that was replaced with compilers and assembler and linkers leaving just the pseudo-code -> target language step. Higher level languages are taking over that remaining step as these languages allow you to reason directly in their syntax.

In the end, I think pseudo-code is just a tool, like any other, to be used or abused as appropriate.

By Andrew Sackville-West at Sun, 2009-10-04 14:49 | login or register to post comments

Languages that Learn...

I know nothing about anything, please teach me how to make a peanut butter sandwich.

A language that integrated with a massive database of rules, vocabulary, and heuristics for best-guess comprehension of poorly specified programs could probably go a long way towards making DWIM practical.

I've read about declarative meta-programming techniques that can take a sketch of a program and requirements and produce something useful, albeit currently limited to focused domains (i.e. optimizers for compilers, or compilation itself). I'm looking forward to what happens with those techniques over the next few decades.

By dmbarbour at Mon, 2009-10-05 18:49 | login or register to post comments

Hand waving?

Much use of pseudo-code is not executable. Introduction to Algorithms (CLRS), justified it this way:

What separates pseudocode from "real" code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm. Sometimes, the clearest method is English, so do not be surprised if you come across an English phrase or sentence embedded within a section of "real" code. Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering. Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely.

By Chris Rathman at Tue, 2009-09-29 15:34 | login or register to post comments

Lambda the Ultimate

User login

Navigation