Who created the idea(s) of the first loop constructs?

Question

while (1) {
      if (1+1==2) {
             print "Yes, you paid attention in Preschool!";
      } else {
             print "Wait... I thought 1+1=2";
      }
 }

As a developer, we all have to use loops very frequently. We know that. What I was wondering was, who thought of the idea to have loops? What language introduced loops? What was the first loop construct? Was it a while loop? A for loop? etc?

Answer 1

As mouviciel and Emilio Garavaglia noted, the concept predates computing. However, the first instance of a software loop was the loop Ada Lovelace used to calculate Bernoulli numbers, as described in Note G of her translation of the Sketch of the Analytical Engine Invented by Charles Babbage, by L. F. Menabrea. The Analytical Engine's ability to loop is noted early on by Menabrea:

This being understood, let us, at the beginning of the series of operations we wish to execute, place the needle C on the division 2, the needle B on the division 5, and the needle A on the division 9. Let us allow the hammer of the dial C to strike; it will strike twice, and at the same time the needle B will pass over two divisions. The latter will then indicate the number 7, which succeeds the number 5 in the column of first differences. If we now permit the hammer of the dial B to strike in its turn, it will strike seven times, during which the needle A will advance seven divisions; these added to the nine already marked by it will give the number 16, which is the square number consecutive to 9. If we now recommence these operations, beginning with the needle C, which is always to be left on the division 2, we shall perceive that by repeating them indefinitely, we may successively reproduce the series of whole square numbers by means of a very simple mechanism.

The Analytical Engine's looping mechanism is directly inherited from Joseph Marie Jacquard's mechanical loom (1801), as noted in the memoir by Menabrea:

It will now be inquired how the machine can of itself, and without having recourse to the hand of man, assume the successive dispositions suited to the operations. The solution of this problem has been taken from Jacquard's apparatus, used for the manufacture of brocaded stuffs, in the following manner:—

Two species of threads are usually distinguished in woven stuffs; one is the warp or longitudinal thread, the other the woof or transverse thread, which is conveyed by the instrument called the shuttle, and which crosses the longitudinal thread or warp. When a brocaded stuff is required, it is necessary in turn to prevent certain threads from crossing the woof, and this according to a succession which is determined by the nature of the design that is to be reproduced. Formerly this process was lengthy and difficult, and it was requisite that the workman, by attending to the design which he was to copy, should himself regulate the movements the threads were to take. Thence arose the high price of this description of stuffs, especially if threads of various colours entered into the fabric. To simplify this manufacture, Jacquard devised the plan of connecting each group of threads that were to act together, with a distinct lever belonging exclusively to that group. All these levers terminate in rods, which are united together in one bundle, having usually the form of a parallelopiped with a rectangular base. The rods are cylindrical, and are separated from each other by small intervals. The process of raising the threads is thus resolved into that of moving these various lever-arms in the requisite order. To effect this, a rectangular sheet of pasteboard is taken, somewhat larger in size than a section of the bundle of lever-arms. If this sheet be applied to the base of the bundle, and an advancing motion be then communicated to the pasteboard, this latter will move with it all the rods of the bundle, and consequently the threads that are connected with each of them. But if the pasteboard, instead of being plain, were pierced with holes corresponding to the extremities of the levers which meet it, then, since each of the levers would pass through the pasteboard during the motion of the latter, they would all remain in their places. We thus see that it is easy so to determine the position of the holes in the pasteboard, that, at any given moment, there shall be a certain number of levers, and consequently of parcels of threads, raised, while the rest remain where they were. Supposing this process is successively repeated according to a law indicated by the pattern to be executed, we perceive that this pattern may be reproduced on the stuff. For this purpose we need merely compose a series of cards according to the law required, and arrange them in suitable order one after the other; then, by causing them to pass over a polygonal beam which is so connected as to turn a new face for every stroke of the shuttle, which face shall then be impelled parallelly to itself against the bundle of lever-arms, the operation of raising the threads will be regularly performed. Thus we see that brocaded tissues may be manufactured with a precision and rapidity formerly difficult to obtain.

Jacquard's loom is a very early application of a loop in the context of ordering a machine to produce a repeated output:

The idea behind the Jacquard-loom was a system of punch cards and hooks. The cards were made very thick and had rectangular holes punched in them. The hooks and needles used in weaving were guided by these holes in the cardboard. When the hooks came into contact with the card they were held stationary unless it encountered one of the punched holes. Then the hook was able to pass through the hole with a needle inserting another thread, thus forming the desired pattern. Intricate patterns were achieved by having many cards arranged one after the other and/or used repeatedly.

Jacquard's loom is also recognized as a very early form of a stored program:

If the impetus behind much of the development of calculating machines discussed so far had arisen from numerical computation, the motivation that led to the earliest form of `stored program' was to come from a very different source: the textile industry. We have seen earlier that one of the fundamental aspects of computational systems is the concept of representing information and, although we have not done so explicitly, the application of this idea can be discerned in all of the artefacts that we have examined up to now: in the development of written representations for numeric values and the mechanical parallels that sprung from these. Thus, the alignment of pebbles on an abacus frame, the juxtaposition of moving scales on a slide-rule, and the configuration of cogged gears on the devices of Schickard, Pascal and Leibniz, are all examples of representational techniques that seek to simplify the complex processes underlying arithmetic tasks. There are, however, categories of information, and representations thereof, other than number upon which computational processes can be performed. The weaving technology developed by Joseph-Marie Jacquard in 1801 illustrates one example of such a category.

Charles Babbage also adapted Jacquard's storing procedure into the Analytical Engine, the presence or absence of a hole communicated a simple on-off command to the machine:

The Analytical Engine has many essential features found in the modern digital computer. It was programmable using punched cards, an idea borrowed from the Jacquard loom used for weaving complex patterns in textiles. The Engine had a 'Store' where numbers and intermediate results could be held, and a separate 'Mill' where the arithmetic processing was performed. It had an internal repertoire of the four arithmetical functions and could perform direct multiplication and division. It was also capable of functions for which we have modern names: conditional branching, looping (iteration), microprogramming, parallel processing, iteration, latching, polling, and pulse-shaping, amongst others, though Babbage nowhere used these terms. It had a variety of outputs including hardcopy printout, punched cards, graph plotting and the automatic production of stereotypes - trays of soft material into which results were impressed that could be used as molds for making printing plates.

The Analytical Engine's conditional branches combined with the Jacquard inspired mechanical loops and storing procedure are dauntingly similar (conceptually) to your example, especially if we add Babbage's printer to the mix, for the print "..."; parts.

Obviously mechanical loops predate Jacquard's loom, the first known device to work in a loop fashion being the Antikythera mechanism (100 BCE), and if we look even further into history (and venture horribly off topic), sundials are probably the oldest man made mechanisms where an understanding of loops is evident, following of course the repeating pattern of the sun's and other stellar bodies' orbits.

However I think that in context of computing (and not calculating or anything else), the Analytical Engine and Ada's Bernoulli numbers calculating algorithm can be credited for introducing loops, sharing at least some of the credit with Jacquard's loom, having directly adapted the concept from it.

Answer 2

Loops predate computing. You can find them in musical notation as early as Gregorian chant:

Answer 3

The concept of "do it again" is somehow "primitive" to human perception. You can tell this to a child that has just elaborated a minimal comprehension of the natural language.

In discrete systems loops are found in all the finite state machines when you admit you can reach a state you alredy have been before.

The simplest loop is the cycle between two states (a clock). Given that any higher number of states can result from a count from it, every more complex machine is contructed upon a "counter" incremented by a clock that can made "jump" upon certain flags representing certain combinatory operations. This is the core of a Von Neumann machine every microprocessor based computer is based on.

In machine code, a jump is coded JP-Z-nnnn (where Z is whatefer flag ypu base your condition on). In higher level language this translate almost immediately into

if(z) goto x;

A loop is nothing more than a goto where the x label precedes the goto instruction itself.

Every other formulation (for, do, while, etc.) is just "syntactic sugar" to better domesticate the wild goto in the very common cases of repeating until something happens

Answer 4

The concept of looping is one of the things that distinguish a full-blown computer from a simple calculating machine. If a system doesn't support looping then it's not turing-complete and therefore not a computer.

The first Turing-complete design was Babbage's Analytical Engine, so it must have had a concept of looping. However, there are systems that do have looping but aren't Turing complete (because they omit something else). Babbage's work is probably a good starting point, though.

Answer 5

Assuming you mean modern text computer programming languages.

Algol60 has "FOR", "DO", "UNTIL" and "WHILE", so it was before 1960.

The Retro Computing Museum has a few languages pre 1960.

Kvikkalkul, the language from the '50s for programming Swedish nuclear subs only has GOTO. (However, Kvikkalkul is almost certainly a hoax from the '90s, not a real historical language.)

Plankalkül by Konrad Zuse is the earliest I could find. It has a "für" construct.

Answer 6

The work of both Liebniz and Newton contains algorithms with loop constructs. Liebniz built a mechanical calculator and speculated (as Lovelace did years later) about a machine to perform more sophisticated analysis. His notes on these ideas are sketchy, but they describe stuctured logic with loops.

However, the idea of repetition sequences and count controlled loops, as well as what we would call while loops are discussed in the work of the man for whom algorithms are named: Muhammad ibn Musa al-Khwarizmi from the ninth Century. His second book, al-Kitab al-mukhtasar fi hisab al-jabr wa'l-muqabala (الكتاب المختصر في حساب الجبر والمقابلة) (A Compendium on Calculation by Completion and Balancing) was known to Newton, Liebniz, Babbage, Lovelace, etc.

Of course al-Khwarizmi relied, in part, on the ancient Greeks. At some point we probably get back to Adam and Eve's version of rinse, lather, repeat.

For more about Al-Khwārizmī and his work see:

http://www-groups.dcs.st-andrews.ac.uk/history/Mathematicians/Al-Khwarizmi.html