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

Why would you want to go back to three previous pubs? Because you're drunk, and hence lost, and hence retracing your steps. Been there, done that...

Incidentally, what jump-substitute are you talking about in prolog? I'm guessing, from the mention of efficiency, that you're talking about the cut... but the cut is fundamentally different to the jump...

Not quite. A recursive definition has to "tend to a solution".
Hence the simple solution, followed by the bit that splits the difficult case into simpler cases. For example:

define paint the floor(top,left,bottom,right)
if right-left=1 and bottom-top=1 then paint the square(top,left):end
if right-left>1 and bottom-top=1 then paint the square(top,left):paint the floor(top,left+1,bottom,right):end
if right-left=1 and bottom-top>1 then paint the square(top,left):paint the floor(top+1,left,bottom,right):end
else paint the floor(top,left,bottom-((bottom-top)/2),right):paint the floor(top+((bottom-top)/2),left,bottom,right):end

This process will either paint the last square, and end, or paint the last square in a row, then paint the rest of the row, or paint the last square in a column, and then the rest of the column, or split the area to be painted in half, and paint both areas.

In ALL cases, the problem that it has to deal with is simpler than the problem that it was passed, and it will thus finish eventually.
Also, you can define the solution to the simple case, and then orget about it, making the more complex case easier to resolve.
This is something that does not occur in iterative programming. (not that I've noticed anyway).

oh, one more thing...

Be careful saying that anything is the "fundamental" part of computing - be it jump, test, and assign, or whatever. The nature of the beast is that you can rewrite anything as anything - the only question is how easy it is to write, and how efficient it is...

I am not sure what jump substitute in prolog. I only know that they had to introduce some way of explicitly looping into the language, otherwise for some cases it resulted in VERY inefficient behaviour.
Incidently, it is not just prolog that has had to do this, EVERY functional and logical language that had no facility for looping and other iterative behaviour ended up having to add it.

I am (hopefully) using fundamental in it's correct (in this case) sense of a set of atomic funtions that all other functions can be defined in terms of. Which ones are fundamental and which ones are derived tends to be determined by how you slice the cake, and often there are multiple sets of functions that can be the "fundamental" one. The derived ones aren't useless (the case statement in particular is very usefull) they are just not the fundamental ones.

> A recursive definition has to "tend to a solution".

Huh? Why?

int f(x) { return f(x); }

^-- a perfectly legal recursive definition in C. Sure, it's not terribly useful, but that doesn't mean it's not possible. There are other useful functions around which don't tend to solutions.

I don't know why it has to "tend to a solution", it just said it that was in the degree notes that I read, and in a number of other places too. I would guess that it is to do with ending eventually, as a recursive procedure that didn't would tend to run forever. NOTE functions can call themselves with the output of their computation (like a mandlebrot set is called with the output of the previous iteration), but in that case you have iteration, not recursion, and if you frame it that way, your program will almost certainly overflow it's stack area, and crash. There are better ways to write iterative code, which won't crash your programming language.

tum-tum. I do try to stay on topic in PR, honestly!

Ok - first off: jumps in prolog. The primary feature of prolog that was introduced to make it more efficient is the 'cut' - but this certainly isn't a jump-like facility: it's rather more the opposite: it's a "Don't Go To" command. I can't really think what a jump command would even *mean* in Prolog...

Likewise, Pure ML doesn't have iterative loops: only recursive loops. All iterative loops can be rewritten as tail-recursive loops, and a good compiler can create equally good code from either. Sure, ML code tends to be slower than C, but that's for a bunch of reasons which are quite seperate from recursion.

next off: fundamental. Sure, from jump, test, and assign (and numbers and arithmetic) you can build anything. But then, from abstraction and application you can build anything - and you don't even need numbers and arithmetic to do so (lambda-calculus). Have a look at intercal sometime: it's fundamental operations are severely weird, and addition and suchlike are handled by libraries. Pure ML uses create, test, and function call as its fundamental operations - and it could rewrite jump, test, and assign in terms of those - though it'd be a touch pointless. Essence being - what's fundamental and what's derived is largely a product of how you look at it...

finally: solution-tending. Yes, it's a good thing to have - but you can have recursive functions which don't have that property, and some of them are even useful. For example:

define search_tree(tree, val):
if leaf node and value of node is 'val', then do the following:
print "I found it!"
terminate
otherwise, do the following:
search_tree(tree.left, val)
search_tree(tree.right, val)
enifed

This'll print out all the values of a binary tree, in depth first order. Whether it's solution-tending depends on whether the passed tree contains any loops, and where those loops are, and where there are nodes with value 'val'. Nevertheless, such a function can be useful in some circumstances - you might use a variation of this algorithm to find good chess moves, for instance.

If you can overflow a stack with a tail-recursive function like the mandelbrot set you mention, it really is time to get a better optimising compiler. :-p

Anyone mention the PERFORM ..... VARYING .... UNTIL that I used to use in COBOL?

BBS

Right I have updated and fixed the entry, I hope!
I best point out what I meant by novices, as in people trying to learn programming but who get freaked by all the jargon, and over complex description.
Yes I do know about research and I have researched and included what I found on REPEAT UNTIL, but when I wrote that I had no idea whether anyone had written anything on it or whether it would be accurate.
I have done a bit on normal loops and a bit on assembly loops and GOTO is in there. However judging by the amount of debate on recursion I am glad I have steered clear for now, if I can think of a simple non-jargon explaination I'll put it in. If you can think of one that takes no more than a paragraph, has no technical jargon, is not debateable and assumes no knowledge, I will happily include it.
So go and have a look at the new version and tell me where I went wrong this time.
Researcher PSG

COBOL! Though it doesn't compare to ALGOL for sheer levels of terror...

I miss my BBC Basic For...Next loops. They weren't anything special, until you made a typo, and wrote something like this:

for i = 1 to n
for j = 1 to n
print "| "
next i
next j

note that lines 4 and 5 got swapped over by mistake here. What happens when its run varies drastically depending on all kinds of obscure factors - the result is almost as unpredictable as buggy C code. Almost.... but not quite...

PSG - ignore the controversy - h2g2 can get controversial about just about anything, up to and including whether something can indeed come from nothing. There's some argumentative souls here like that...

I didn't mean the "research" comment as a slight in any way - just trying to say that there are three ways round a gap in your knowledge when writing guide entries: you can ask for collaboration from someone who knows, you can avoid the issue in your entry, or you can do some research. All three methods can work, but I wanted to suggest that this is a case where research is fairly likely to be your best bet. Just trying to share a little experience - now I've said that, fifty people will no doubt delurk and offer to write huge chunks of stuff for the entry - but what the hey.

Incidentally, you've written "I will use instructions from the MOTOROLA 68000 processor as an example", and this is very good - but I suspect you need to write a similar explanation at the top before your pieces of C code - otherwise people won't necessarilly know what language it is.

Finally, I think you may need a title change: you've said yourself that this isn't really a universal entry - of course, you've got a better idea what you want the focus of the entry to be, and who you want to read it, so it's really up to you...

As a total aside - your wealth of experience with assembly, and the motorola processor in particular, really shows through towards the end of the entry. We have an edited entry on assembly in general, at http://www.bbc.co.uk/h2g2/guide/A464573 - but we don't have any kind of detail about what real assembly looks like, or how to create it for a specific chip. Could be an interesting topic for an entry... *shrug*

'delurk'... nice verb!

GTB

Thanks Lucinda!
I have taken your advice and put in a bit saying the examples for the higher level languages use the format from C. And I have changed the title to "Programming Loops (An Introduction)" hopefully that makes it clearer.

As an aside on your aside I'm glad you liked the MOTOROLA 68000 stuff, I'll take a look at the assembly entry and see if I can write something to complement it.

To all and sundry, any more comments on the revised entry will be apreciated, or any complements would be gratefully recieved.

Researcher PSG

xyroth:
r=0?!
r=1 is more like it.

Another example of recursion is the solution to the Towers of Hanoi puzzle. However, it's a crappy example since the puzzle is rather abstract and takes too much time to fully explain.

You seem to have either improved or masively unimproved this entry depending on if it is supposed to be about how to do loops in C.
It would be much better to use psuedocode for your examples, as using C meant that you kept having to explain the C syntax, which if is not a problem in an article about loops in C, but is a problem in an article about loops in general.
Also, the stuff about assembly, while very good, deserves to have an entry of it's own, whih you can link to from this one.

Ok I feel quite damning about this entry - sorry - no offence meant.

BUT ..... I have programmed for almost 20 years; ZX81, BBC Micro, Assembly, COBOL, 4GLs. So I think I have a fairly good understanding of the concepts of programming. However I've never been near C and I can't understand this entry, YET it is supposed to be an introduction. I don't think anyone without a programming background has a hope in hells chance with this entry. Maybe I'm wrong, let's canvass opinion.

IMHO an introduction to the concept of loops would explain why you might need to do them. The entry doesn't give this just says they're universal and dives in to using some C syntax (or whatever).

I think it needs some pseudo code to present the ideas, before we move onto language specific examples (if we even should).

Maybe a nice example from the real world. For example how about the classic loop we all started with printing your name on the screen over and over again. Entry could go something like this .....

Line 1 - print name "Bright Blue Shorts" on screen
Line 2 - go to line 1

So then we can say maybe we only want to do it 10 times ....

Line 1 - set my "count of times message printed" to 0.
Line 2 - print name "Bright Blue Shorts" on screen.
Line 3 - add 1 to my "count of times message printed".
Line 4 - check whether my counter has reached 10 (and therefore I've displayed my message 10 times). If I haven't go back to line 2. Otherwise I've finished.

Here we begin to see the use of a variable to count how many times the message has been displayed.

Some languages provide easy sysntax for doing this e.g. the For ... Next loop etc, etc and the entry can ramble on ......

I quite liked the posting back at no. 8 which talked about pre-test, during test and post-test loop types. That was good at a conceptual level.

Within the current entry I didn't like the bit titled "The use of the semi-colon in programming". This makes it sound like every language uses the semi-colon in this way. In fact none of those I've used, ever have.

Anyway sorry if that's all too damning, but I think an introduction is only worthwhile for the beginner and therefore needs to be pitched as such. The use of pseudo-code rather than a specific language syntax would vastly improve this. Although you may think the syntax seems simple I can assure you that to anyone who is unfamiliar to a language it means nothing. Even things like variables and condition values are not plain everyday English to Josephine Average. Possibly even my attempted pseudo code is still difficult to understand.

The alternative is to retitled it to "Programming loops in C and Assembler" (or whatever).

Hope that helps,
BBS

I'm sorry, I see this latest version as a massive step backwards.

There's a real opportunity to define loops simply in terms of basic (fundamental or atomic, if you prefer) constructs. There really is no need at all to mention specific key words (like REPEAT, DO, UNTIL, WHILE) until a final section illustrating how the concepts are implemented in one or two languages.

As someone (xyroth, I think) indicated before, there are only three basic loops and that's what the article should concentrate on.

All the assembler belongs somewhere else altogether as it's about branches, not loops (yes, I know they're fundamental to loops in assembler, but this isn't about loops in assembler, it's about loops in general).

Hmmm looks like we had a near-simulpost there manolan - you seem to echo my thoughts.

While I was away I had a thought about what I'd written as pseudo-code and decided even that is too techy! In my first example, I'd written

Line 1 - print name "Bright Blue Shorts" on screen
Line 2 - go to line 1

but I think would be better as:

1st Command - display message "Hello Bright Blue Shorts" on screen.
2nd Command - begin again from command 1.

***

Damn great programmer I used to be. It all got especially good when you had

10 INPUT "What is your name?" #NAME
20 PRINT "HELLO " #NAME
30 GOTO 20

Maybe we could start an entry/discussion thread about the first programs ever written, or how to start programming in BASIC!

BBS

Oh yes and since I was last here I reckon you could classify them into 3 types :

1) infinite (like the print example)
2) set number of occurrences (e.g. For ... Next loop)
3) until a condition is met (e.g. Repeat Until .... )

BBS

Infinite doesn't actually add anything, as almost all of the infinite loops I have seen in practice are due to either bad code specification, or a bodge to get around the language nothaving the type of loop you need. also most infinite loops aren't, they contain a conditional jump inside, and should be discouraged and rewritten.