h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

http://www.bbc.co.uk/h2g2/a520895
Hello
I wrote this entry because I noticed that with loops in programming their seems to be 2 types that are fairly universal and I feel this is a good introduction to them.
Any comments from more advanced programmers would be welcome.

http://www.bbc.co.uk/h2g2/guide/A520895
sorry trying to get used to move to BBC.

it is in general a guide to the novice, is that how it comes across?

*puts on her 'difficult' hat*

Hmm. I'm afraid that you're lacking rather large chunks of stuff which I at least feel are relevant to programming loops... here's some of what you're missing:

- other loops in iterative programs: eg, do...while, repeat...until, loop...until
- other types of for loops: foreach, for...next, etc
- changing the condition variable inside the body of the loop
- showing how the differing looping constructs are equivalent, and can be rewritten in terms of each other
- recursive loops.
- loops using GOTO
- loops in languages which aren't like C/java/BASIC/generic iterative programming languags: IE functional and logical programming languages like ML or Prolog
- infinite loops & the halting problem
- variants and invariants of loops to make sure they work as you want them too

Ok, that's a long list, and you almost certainly don't have to cover it all - but if you use words like "universal" there'll always be some smart alec (me!) telling you it ain't so.

Currently, it reads more like "Loops in C", than anything else - if that's what you intended, fine - but I don't think it is? Over to you...

--
on a more nitpicky level:

in a C-style for loop, with for( int i = 0 ; i < 4 ; i++ ), the loop terminates when the second argument is NOT true - not when it is true.

you say "see general syntax", but there is no general syntax section... I'm confused...

I think Lucinda is going overboard a bit in that list. You don't have to put all that stuff in. But it might be worth mentioning the Repeat Until loop, because the condition is at the end rather than the start.

Looping using GOTO, recursive loops and so on are just ways of implementing these loops in languages which haven't got them built in. (I know the recursive brigade will object to that!)

The C-like syntax is OK. You have to write it using some syntax and C is as good as any other. But I don't like your comment about "for the use of semicolon" and referring to a General Syntax section which isn't there.

I think I'm more with Lucinda on this one. The syntax is too C-like. Personally, I would completely re-write it.

There's a general loop structure which consists of a body of code which is repeated until some form of condition is met.

Then there are variants depending on whether the loop condition is evaluated at the start or the end, whether it is a positive or negative condition (WHILE or UNTIL). Note that in some languages only a subsection of these are available, whereas in others they're all there (and more).

Then there are variants which iterate in a particularly defined way either via a numeric index (for - BTW the C syntax is a particularly bad example as it is too concise) or over some sort of hash (foreach).

Perl has a particularly complete set (or OTT, depending on your view) of loops.

Right, when I posted this I expected a bit of debate.
First I'm sorry about the semi colon bit, I was going to write a little bit at the bottom about it, when I found a simplified but accurate way of defining it, but I forgot, sorry.
Second as I have been planing the re-writes I looked at recursion, and to be honest it justifies a section on it's own to explain it to the novice.
Next I can't believe I forgot do while, I plead insanity.
Finally to try and please everybody I am planning to write the do while, as well as write a little bit on assembly language loops.
But to be fair this is meant to be an definition of loops open to the novice or non-programmer as well as the trained. As I was sick of people saying it is too hard for them to understand, or making it too hard for people to understand with unnecceserily complex language.
I only really have done C, C++, Motorola 6800 assembly language and a brief introduction to Pearl, so to be honest I was a bit ambitious to try and write this, but I felt I should try and demystify this type of thing.
The re-writes and additions should be their by Monday, I will try and write a bit on Repeat Until, but I haven't done anything about it so someone may have to correct it.
If anyone else feels that I have missed anything essential to describe the CORE of programming loops, in the top several languages (I'd like to keep away from the more obscure ones to stop it from becoming too confusing). Please give me an exact description of what it is, and I will try and include it.
Thanks for all the input, and at least I didn't get a load of spelling corrections (except one logical correction, sorry simple slip of the typing).
Researcher PSG

PS I really, REALLY regret using the word universal, it's a bit like saying the Titanic is unsinkable, after it struck the iceberg.

This entry can be simplified quite a bit. There are three basic programming concepts. These are assignment (ie a=5, a=5+3, etc), test (ie if a=5) and jump. the jump is necessary so that you can have loops, of which there are only three types. Those are pre-test (while), post-test (repeat) and indexed (for). This fully covers all af the elements that you need for writting any serial program. You need a few more for parralel programs, but then you would expect that.

xyroth, nice summary.

I'm not sure whether what you've said covers a loop like that encountered in a function which evaluates, say, factorials, by calling itself. (A recusion loop) I guess the recursion loop could be rewritten as a while loop, but it isn't always, and merits discussion of its own, no?

GTB

Recursion is a special case, but can be ignored, as you can add recursion to non-recursive languages by doing gosubs, then using local variables by faking them using arrays, and as long as your recursion does not overflow the arrays, they act just the same as recursive procedures. This is why the jump is fundamental (or to be precise, the conditional jump, which is a derived function of the test, with two unconditional jumps, one from each of the two possible paths). It does work, as I know people who have done it!
It is this fundamentality of the jump which also explains why you have to introduce a bodge to do the same thing into prolog to make it possible to write efficient code in that language.

To summarise, if you have those fundamental constructs, then any more complex constructs can be re-written into the simple ones, making it easy to check if the new constructs are just variants of the old.

// switch imperative for iterative in my post above: oops.

Well, if you want it to be open to the non-programmer, there's one hugely critical piece which HAS to go in - indeed, in such a case it's the ONLY thing which is required. That bit is: "Why should I care?"

Note that non-programmers will probably switch off as soon as they see the first semi-colon. Drop the code: just talk in english, with examples like the ever-popular:

repeat "Drink a beer" until "Unable to walk in a straight line".

recursion is similarly simple to explain: for example, in order to do a pub crawl, do the following four steps:
1 go from your current place (X) to a pub (Y)
2 have a beer
3 if not vomiting then do a pub crawl
4 go from the pub (Y) to your previous place (X)

with such examples you can probably explain everything there is to know about loops - even quite complicated ideas can be expressed in such terms if you take a moment to think about it.

--

Ok - now you've got everyone up to speed on what loops actually are, and you're no doubt itching to tell them how to create loops in C. Fight that urge: such things belong in an entry on C or C syntax or Learning C or How to code in C, rather than an entry on loops.

Look at it this way: your audience will be C programmers, non-C programmers, and normals. Normals probably don't have a C compiler - the most accessible programming language is likely to be the macro language of their office suite, or simply a spreadsheet. C programmers know how to program C, and don't need to be told again. non-C programmers don't know how to program C, but don't care.

--

Aside: we ARE researchers, apparently... sometimes the best way to get round holes in our knowledge is just that: to research. Don't think "I can't write about X: I know nothing about it" - rather think "I need to find out about X so I can write about it"!

What a dreadful bit of recursion. it is itterative code in disguse, and thus not a good example.
Recursive code has two basic rules for writting it.
1. deal with the simple case and terminate.
2. split the complex case into simpler cases and terminate.

Admittedly rule 2 gets bent quite a lot, espicially if you include exception handling, but then that's recursion for you.

A better example of recursion is the factorial function, which would be written like this.

define factorial(x)
if x=1 then =1
else =x times factorial(x-1)

much simpler, neater, and probably more snazzy as well.
where recursion makes sense, it it usually blindingly obvious, as is the case for iterative solutions. The itterative form for comparison would be:

for i=1 to x
r=r*x
next

the result would then be in "r".

xyroth:

Yes, yes, recursion CAN be ignored, since it is IN PRINCIPLE reducible to simpler structures, and when learning it, it's good to see HOW it can be reduced to simple structures. The question is, in an entry, SHOULD it be ignored? I think not. I think recursion is neat, and it's a cool example of looping. Also, I agree with Lucinda about real-world example written in pseudo-code. This could apply to recursion. Lemme think....

oh, podge. I can't think right now. I expect there's a very good real-world example of recursion. I can only think of factorials, which have no real-life existence for non-mathematicians, and processes which involve dealing with a whole pile of something, (Recursive process for filing a big stack of papers: 1. File the top paper on the stack. 2. Apply this process to the stack that remains, if any.), but that seems dumb.

GTB

P.S. Hello, Moderator! Hope you're having a nice day moderating!

crossed wires, xyroth, I wrote my last posting while you were posting your last posting.... Not that this changes anything...

No, recursion should not be ignored, as recursive solutionsare sometimes the only solutions.
RATS, I just spotted that I missed the "r=0" from my itterative example of factorials.
A good example of a recursive algorithm that I use in everyday life follows.

I have lots of STUFF, some of which is junk, and need to be thrown away, but what needs to be thrown away is not obvious, so I use the following algorithm.

take next item.
is is good, if so keep it.
is it bad, if so get rid of it.
else put it in the undecided pile.

Once you have done that for all of the items, you recursively apply it to the undecided pile, which gets progressively smaller. (strange, but true).

Also, factorials crop up all over the place anywhere where you are combining stuff and a+b is not equal to b+a. the factorial(a+b) is how many combinations you have to deal with.

Here, that sorting algorithm's not an example of recursion; at least it's not stated recursively, is it? You have the user running through the entire algorithm, and then applying it iteratively to the diminishing 'undecided' pile.

Recursive processes have to call themselves, right? Like your factorial example, where fact(x) = x * fact(x-1), and fact(0) is defined to equal 1, or whatever. The point is that to evaluate one factorial, you have to evaluate a factorial of a smaller number. That's why I used the pile of paper example - as stated, in order to deal with the pile, you have to deal with a smaller pile.

Am I making any sense?

GTB

xyroth - you may have missed the point of my example: it isn't really iterative code in disguise. Specifically, it unwinds to something like:

[start at A]
go to B
drink beer
go to C
drink beer
go to D
drink beer
go to E
drink beer
[vomiting]
go to D
go to C
go to B
go to A
[end at A]

The last three instructions are the key to why it's not just iterative code rewritten: the retracing of your steps is enabled by using the "stack" you get from recursion. In iterative code you'd use a LIFO pipe.

Note that vomiting when you've had five pints is a much simpler case than vomiting when you've only had one pint, so it fits your rules too.

That said, the factorial function is a perfectly good example of recursion... it's just that personally I always prefer beer. Preferably Caffreys.

Why would you want to go back to four previous pubs, vomitting all the way?
And my example is recursive because the sort only happens to the "undecided" pile., which gets called again as the last case.

Since it seems relevant, I'm going to witter about "real" recursion, iteration, and tail-recursion.

a tail-recursive function/method is one where the recursive call is the last thing done. For example:

fun get_drunk:
have_a_pint
get_drunk
nuf

now, this function is tail-recursive, so it can be easily rewritten as:

fun get_drunk:
1: have_a_pint
GOTO 1
nuf

which is iterative. This transformation from tail-recursion to iteration is tremendously simple, and compilers do it on a regular basis. Now, try the next program:

fun backwards:
integer i = get_int_from_user
if i is not zero, then {
print i
backwards
print i
}
nuf

now, this isn't tail-recursive, so it's very difficult to replace with an iterative function, and compilers typically can't do this automatically.

The best examples of recursion are probably divide and conquer algorithms. For example

fun get_from_(A)_to_(B):
if B is less than a metre from A, go there.
otherwise, do the following {
find a point C between A and B
get_from_(A)_to_(C)
get_from_(C)_to_(B)
}
nuf

Mergesort is the classic example, and goes as follows:

fun mergesort(list) {
if the list has only one element, return it - we're done.
otherwise:
split into two equal sized halves.
mergesort(top half)
mergesort(bottom half)
merge the (now sorted) top and bottom halves together, maintaining order
return the result
}

--
not that any of this needs to be in the entry - just thought it might be handy...