>> DFB: You said you wanted to talk about Algol 60? Because somebody has said
it's its 60th anniversary of release? Which is right. I mean, it did come out in 1960.
Which is why it was called Algol 60 (!) And so yes, it is 60 years old. >> Sean: 60 years of Algol60 !
>> DFB: Happy Birthday Algol60! It's another of these [languages] that was tremendously
influential at the time and a flag that everybody could rally around. But in
the end it was designed by a committee. And despite all their attempts to be
reasonable - and not too demanding - individual committee members tried like
heck to get their favourite things in there, regardless of how expensive they
were to implement and sulked mightily, or tended to, if they didn't get them in.
I'm going to start off with an Algol60 version of - we've done a video on it -
Ackermann's function. Now, Algol 60, one of its famous selling points was that, at
last, you'll be able to do truly, desperately, recursive things like
Ackermann's function. because this time ... And there was a big punch-up in the
Committee about it. Basically saying: "Do we want to do recursion? It's bound to give
us a bad name because it'll be slow ..." And everybody said: "No! we've got to do it,
you know." It's no good saying things like 'factorial' and 'fibonacci' can be done - not
properly recursively - in loops. Essentially things like 'ackermann' can't.
So we've got to do it! It's part of our duty as to what Algol's going to be.
So, this is the way it came out. And it worked just fine. I think I can even
explain it to you using on here [points to iPad] the [highlight] comments thing. OK, so I've just
dragged over the word 'begin'. Later on in the 60s decade when C came upon us they
used { and } to define a block of code.
Algol is much more verbose. It uses 'begin' and 'end'. >> Sean: Could you nest those? >> DFB: Yes in fact
I've got one here, look. The initial 'begin' is up at the top and
this matches with that 'end'. But hidden in here, as part of this program, there is a
'do' loop here. But, to show the extent of the 'do' loop, not curly braces, like in C,
[but rather] 'begin' and 'end.' So here's my 'begin' and here's the matching 'end' that goes with it.
Oh it's sort of working! But then what happens after that? Well, let's cut to the
chase and let me tell you. This thing [declaration] first of all, defines the 'ackermann'
procedure that is going to get called. And it does it, obviously, in Algol 60
nomenclature. Part way down the procedure [declaration] stops and the bottom half is the main
program. Now here is another contentious discussion point it's not immediately
obvious, until you look at the structure of the program, that down here, where it
says "integer m n" - that is not a part of the Ackermann function. It's part of the
main program so when you move on to C - which you can remember is 8 or 9
years downstream of the Algol 60 Committee - so many lessons have been
learned. And the feeling was that Algol is terrible sometimes for you to have to
mentally parse the program to discover where the main program begins(!) Wouldn't
it be nice to flag it up with something like 'main' which was obligatory. Yes - it would.
It's a very good idea. So if we go through this line by line we've got a
'begin' and then that next line says: 'integer procedure ackermann (m, n)'
OK it's a procedure, no abbreviation, no ability to use 'proc' or anything like that. It's a
procedure. It delivers an integer. No abbreviations allowed. It's got to be
'integer', not 'int' and what it's saying is: "ackerman takes two arguments m and n but
at the end of the day when it's done its work it delivers back an integer". That's
why you say it's an 'integer procedure'. OK so it's heralding the idea of
what's actually called a 'function', more in C i.e. a thing that delivers back a value,
in integer or float or [string of] characters or whatever. Here we go then.
Ah! now here comes something that we will absolutely be stumbling over in
future discussion. You had to say that the incoming arguments 'm' and 'n' were
not very clever ones - they were mere 'value's so you actually have to say not
just [that] 'm' and 'n' are integers but also that 'm' and 'n' are passed by value and not by reference -
which was [a subset of] the most general mechanism. So all of that top line then
is just the procedure heading. Then there's something which really does put
alarm among you. 'ackermann := 'if' m = 0 'then' n plus 1 'else' if ....' whatever.
The rule was in Algol60 that you returned the value of a
function - not with the reserved word 'return', which by the time C came along became
the standard [which] was that you say 'return thing', or whatever -
no, you returned it, in a very logical way, by doing a pseudo-assignment to the name
of the procedure. You're saying the whole 'ackermann' effect becomes the
action of this procedure body here (which I'm writing out on the right-hand side).
{so] 'ackermann' becomes the truth or falsehood of 'if m = 0 then deliver back
n plus 1'. So the value of m + 1, whatever that is - 6 or something - would
get put into - not a real [i.e. genuine] variable, but into a pseudo-variable that is there to
return just the result of the procedure. Now that can be so confusing for beginners! To say that ....
>> Sean: It's confusing for me right now! >> DFB: You declare it as a
procedure, but that's what it is. So the obvious way to return its results is not
to say 'return n' but to say ackermann *becomes* this thing. Making it look
like a pseudo assignment statement. Some people love it; some people hate it. But,
you see, you can have arbitrary complexity on the right hand side.
It's saying "Well, if m = 0 then you deliver the result n plus 1 .... "
And here's the notorious bit - that we've already covered in a video somewhere -
" ... otherwise if n = 0 then you call up
'ackermann' again. Now, that's your first example of a recursive call. You're
calling up 'ackermann' within 'ackermann' but with arguments 'n - 1' and '1'
this time. And if that is not true - if it isn't 0, then the most general
recursive call of 'ackermann' is ackermann(n - 1) and then the second
'argument from hell' is itself a call of 'ackerman' to work out your second
parameter and it's *that* that drives it super-exponential eventually. But that's
the end of the whole thing! It may not be obvious to you but that thing they're
saying in ' ... else ackermann(m, n - 1), the next line says 'integer m, n'. What's that
got to do with this function? Nothing at all! It's part of the main program because,
you see, you have given what would be a one-liner definition of what you want to
deliver into 'ackermann'. So that, clearly, with its semicolon at the end of it,
is all you need to define what 'ackermann' has to deliver. So, you didn't use a 'begin' and
'end' because you didn't have to. It was an integer procedure - there's the header - and
it was a one-liner pseudo-assignment statement that returned the value. Oh! gosh! I
used to love teaching this to raw beginners! So, you had sort of put this paper [mask]
down to, but not including 'integer m n', it's the procedure body. But by
the time we come through 'integer m n' it's extra declarations in the main
program here! You've already defined the procedure 'ackermann' but now these are
common-or-garden integers were going to use. So, integer variables, basically, 'm' and 'n'.
Fair enough. And then we get on to a piece of code that is very very similar
in C, very similar in whatever language you do. Basically just putting
two 'do' loops inside each other to investigate the low-value-parameter end
of the Ackermann function. So, we've got here for 'm' - different but similar you know -
you can think of a 'for' loop in C with its parentheses and semi-colons
inside it, but this is very similar. 'for m := 0' that's the start value
'step 1' step it up in ones as we go around the loop until it reaches 3
'do' the following. But then, straightaway nested inside that,
it doesn't just say 'do' it says 'do begin' There's another 'for' loop ! 'for n from 0
step 1 until 6 do' And then here's the next nightmare! Did Algol 60 have
standardly defined input/output? No! "It'll be too complicated and caused too many
fist-fights in the committee" So, it's implementation-dependent
what your input/output will look like! It's always a mess and it's nothing
to do with us but your programming manual will define for you what the
input/output conventions are for your compilers, running on your computer, at
your university, or whatever. So, I've got here this particular version from
Rosetta Code they've used 'outinteger' which is as good as anything. So 'outinteger'
and 'outstring', they're using actually here. And the way they're doing
this is just putting out the values for 'm' and 'n'increasing in fact you know, as
we all know the first "zeroth" values are just the [integer] numbers themselves, like 1 2
3 4 5 6 7 and so on. So, yes, you can see from the printed out numbers there it
works just fine but I think in terms of impenetrable obscurity it is not good.
the worst bit is the fact that you can carry on - after what is obvious at the
end of the 'integer procedure' definition - because there's a semicolon. There are no
extra 'begin's or 'end's to help you. They're not necessary. I can't quite recall
whether it would have been wrong to put them in but anyway it was his heart was
in the right place but the trouble is ... it was a committee and this is what came out of it.
>> Sean: These things you're talking about now, with the benefit of hindsight
and having used C for many years, would you have thought of these things then or
is this stuff that you can just see in hindsight? >> DFB: You get a lot of it you know in hindsight.
The thing I think a lot of people said was:
in the real live engineering and science world you might have some need
for a 'factorial' but you could always calculate it by going around a loop
because it's a primitive recursive function. And when people said "But what
do you really need recursion for, that would matter to me?", the answer is:
" ... probably nothing" A lot of people did say, and rightly, [that] once recursion becomes
part of the scenery people will work out how to implement it far more efficiently.
And it is actually for some problems a very very elegant way of coping with it.
But you need to be sure that your implementation of recursion has been
done by somebody with at least the talents of Ken Thomson to make sure it
doesn't run hideously, hideously slowly. So there we are.
It works! Algol 60 did the job! It wasn't exactly obvious syntax as a
method for doing it ... you can't even see where the main program begins but nevertheless it
did the job. How did things improve and get more efficient? By the time C was
developed to fruition, roughly eight to ten years later, well rather than spend
ages doing that myself I will refer you to one of my videos which is about the
Ackermann function. What was it: "The Most Difficult Program to Compute?"
is what we called it >> Sean: Yes, the question mark was important as we went on to
find different, [and] more difficult ones .... >> DFB:Oh yes, yes, we discovered it wasn't ....
We discovered "Busy Beaver" was far worse, but that's another story.
No in the Ackermann [video] info block I think you will find if you revisit that
video there is a link out there to either a package of stuff or to a
listing of the C version of how to do the Ackermann function. Let me say, right here
and now, I did it that way to prove a point. It is very very old-fashioned C.
It is original Kernighan and Ritchie C, where you specified the type of the
incoming arguments to functions separately
from the procedure-head. You had like a little separate ... well, like in Algol 60
you said 'int a, b' inside not up at the top. So, please don't castigate me because
at the time I was interested to see if my original usage of C to show that
Ackermann's function worked, would still stand up in a modern compiler and -
thank you 'gcc'. You did not fake a 'theological' approach and refuse to
compile me - you just understood it was old-fashioned [C] but it was OK and it works.