3

In the same vein as this question about conditionals, I am interested in the first time a language provided functionality we assume as a given for modern programming languages. The question is when a programming language fully embraced structured programming by providing all 4 control structures (sequence, selection, iteration & recursion).

Now, "sequence" seems like a given, but selection, iteration & recursion also need to be provided. As far as I can see that means

  • conditional keywords (e.g. if...then)
  • loop keywords (while, for etc.)
  • functions which are able to call themselves

For the keywords, they should be dedicated keywords for the purpose mentioned here, opposed to "things that can also be used that way".

When was a programmer first able to make use of all 4 control structures in a language?

migrated from softwareengineering.stackexchange.com Apr 18 at 14:19

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 1
    My memory doesn't go back far enough to name a particular language, but I expect the first higher-level (i.e. non-assembly) languages to fit the bill. Assembly has all of them except the loop keywords. – Bart van Ingen Schenau Apr 18 at 13:36
  • ALGOL 58 was the first widely-known language. You could start there and work your way backwards. – BobDalgleish Apr 18 at 13:47
  • "Dedicated keywords"? Other than that, Lisp would be the answer. (Lisp doesn't need keywords, dedicated or otherwise.) – Drew Jun 4 at 22:27
8

See also:

  • 1
    So if I understand correctly, the first three are pioneers for the respective parts and ALGOL 58 was the first to provide the whole set in 1958? – R. Schmitz Apr 18 at 14:58
  • 3
    @R.Schmitz well, assembler had conditional jump instructions since the beginning, not sure if you would count that. And of course people would do loops using that. I do not know if you want a recursion keyword... if you want that, then FORTRAN 77 is the first, you write recursive subroutine when declaring. – Theraot Apr 18 at 15:13
  • 1
    Standard Fortran 77 did not include recursion, though most real-world "Fortran 77" compilers had a non-standard way to do it. The first Fortran standard to permit recursion was Fortran 90. – alephzero Apr 18 at 15:22
  • 1
    I would consider Algol the first structured language. Assembly languages can emulate structured languages but they're not inherently structured. – Tim Locke Apr 18 at 15:49
  • @TimLocke "Assembly languages can emulate structured languages but they're not inherently structured." Hitting the nail on the head with that; I did not manage to put that into words as well as you. – R. Schmitz Apr 19 at 9:20
3

A couple of misconceptions in this one:

  1. Recursion is just another kind of iteration. It was in fact the only iteration mechanism provided in early versions of Lisp. Any use of recursion can be transformed into standard looping iteration (although many of them require use of a stack as well). Recursion can be viewed as kind of a hack to be able to leverage the program stack for your stack usage while iterating (in languages that use a program stack). Likewise early Lisp demonstrated that its possible (although not always convenient) to use recursion for all your iteration needs.
  2. I have never before heard that support for recursion is required for a language to be considered a "structured language". Really all that is required is that the language be Turing complete without relying on "unstructured" branch statements (aka: GOTOs)

Now with all these caveats, most of the early "Structured Programming" developers were also at the same time involved in the development and use of ALGOL. This includes most prominently Dijkstra, who was the leading light in both the Structured Programming movement and developed the first ALGOL 60 compiler. Hoare and Dahl were also very involved in the development of both.

The other major languages that were extant at the time were COBOL and FORTRAN. Early FORTRAN in particular made extensive use of GOTOs, along with data overlays that are essentially the data equivalent of GOTOS, and thus a large amount of the development of ALGOL was in reaction to FORTRAN. So if you are looking for the early standard-bearer for the paradigm, ALGOL is probably your language.

  • 1
    Recursion is just another kind of iteration. -- This whole paragraph kind of begs the question. Yes, recursion and iteration are interchangeable. Would you want to, though? – Robert Harvey Apr 18 at 16:21
  • 1
    Really all that is required is that the language be Turing complete... Same thing. Brainfuck is interesting from an intellectual perspective, but nobody seriously considers writing real programs in it. – Robert Harvey Apr 18 at 16:22
  • @RobertHarvey - Tons of reasons why you might want to. Compilers routinely do it as an optimization. Early LISP users with no other looping mechanism also did it routinely the other way. I've personally implemented algorithms both ways, and picked the one that looked easier to read/maintain. – T.E.D. Apr 18 at 16:24
  • 2
    Well, yes. But none of that has much to do with whether a language can be defined as having "full structured programming support," unless you can offer more particulars. – Robert Harvey Apr 18 at 16:26
  • @RobertHarvey - Well, yes, because that term is nonsense, and thus there's no such thing. I did put a paragraph at the end relating it to the languages that were current at the time. That's really the best that can be legitimately done with the question that was asked. – T.E.D. Apr 18 at 16:32
1

This is a copy-paste of my answer to the other question. R. Schmitz said I could do it though.

If we are talking about a block structured conditional like

if condition
    some arbitrary sequence of statements including perhaps nested ifs
else 
    some other arbitrary sequence of statements including perhaps nested ifs

rather than just if ... goto some label which is no different to a conditional branch, then two early contenders would be:

  • Lisp (1958) which has an if and cond function. I think condpredates if. When I learned Lisp in the 1980's I'm fairly sure that if wasn't there. Lisp also had recursion, which means it had iteration by definition.
  • Algol 60 (1960) which has the structured if inherited by most modern imperative languages. Also while and for loops and recursion.

Early versions of FORTRAN and COBOL did not have structured if statements as far as I know or recursion.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.