History of Loops
Loops at first glance seemed to be a natural construct in computing. Obviously every language had them and they were just there from the beginning right? Then I learned about lisp and realized you could construct a language without loops. This created a few questions that I’m attempting to answer here.
- Where did loops come from?
- How did we decide that loops should be one of the fundamental constructs in most programming languages?
- How did our looping constructs evolve over time?
One of the realizations that comes quickly when looking into history is that loops are a very old construct. They get recreated many times throughout the history of computing and in reality start as a concept far before the first computer exists1.
All of this makes loops seem obvious. Small children get the idea of repeating something over and over again. Yet they are also critical for representing and understanding the world around us. (An aside here I’m aware that you can use recursion in place of looping but I’m using loop as a shorthand for iteration in this piece).
The other problem that you run into with loops in computing is that it’s not a construct in the CPU. Instead in assembly or inside the CPU we jump to a specific instruction. This is a very different way of looking at the world that is alien to most modern programmers.
This means that loops existed outside of computing for a long time and then the idea was brought to computers. This history of rediscovery or perhaps it would be better to call it reintroduction results in multiple iterations of loop constructs. Though by 1960 we have the modern for and while loop. On the other hand foreach loops don’t come until much later in the late 1970’s.
Loops Outside of Programming
The first human object that recognizes the concept of loops is the sundial. We see loops coming up over and over again in systems that are designed by people. They are also critical for understanding many natural phenomena and are a common occurrence in nature.
This means that our understanding of loops really doesn’t start with computers. Instead we have to look outside of computing and see how that influenced the development of programming languages.
We can see loops arising in nature, mechanical devices and mathematics. All of these provided inspiration for loops in programming. In many ways loops are necessary to model the world. This is true for both physical phenomena and many business activities. For example if we want to run payroll we’d loop through a list of each employee and make a series of calculations to figure out how much we owe each of them and what taxes need to be paid.
This means that there needed to be a way to represent loops inside a computer. Of course if you look at a CPU there isn’t a default loop instruction. Instead we rely on gotos to provide flow control. This makes modeling the world harder than it would be with a loop.
When we are talking about loops that are done mechanically we have to discuss the Jacquard loom. This is because the design of the machine itself resulted in the drums turning over in what amounted to an infinite loop 2.
Actions inside the loop for a Jacquard loom were controlled by punch cards. These punch cards are what allowed for the loom wrap to raise up and down and controlled what pattern was actually weaved into the cloth. As the cylinder turned over the pattern would repeat. These repeating patterns allowed for weaving of very complicated shapes using a mechanical process. This provided an inspiration for the early development of ideas that would become computers.
Loops in Early Computing
As with many things in computing when we talk about the beginning of the loop we have to talk about Charles Babbage’s Analytical Engine. While it was never actually built, Ada Lovelace wrote the first programs for the analytical engine.
When Ada Lovelace created her first program to calculate Bernoulli numbers one of the things that was stated was to repeat indefinitely3. So from the dawn of computing we have the idea of the infinite loop. Repeating the same operation over and over again to keep producing output. At this point the whole idea of a loop is very abstract since there isn’t an actual machine to produce any calculations on.
To get to the first loop that was actually compiled we’re forced to jump forward over a 100 years to the 1950’s and computers that were actually built. To do that we will look at how loops were handled in Fortran in its early specs. These loops were also there to allow users to more easily model scientific and business processes.
Algol, Cobol and Fortran
John Backus actually thought that loops were one of the fundamental reasons to make fortran.
“What Fortran did primarily was to mechanize the organization of loops”4
Mechanizing loops allowed for the creation of far more complex software. This is because phenomena could be modeled much more easily. Understanding and creating complicated models in code first requires those models to exist in the programmer’s mind. If causing a process to repeat is complicated that makes translating a mental model into something a computer can do is much harder.
While Fortran had a conception of loops in early Fortran this was only the Do loop. Do loops are functionally very similar to for loops however they have different syntax. For example here is a do loop to generate a cumulative sum of numbers between 1 and 10 5.
integer i, n, sum
sum = 0
do 10 i = 1, n
sum = sum + i
write(*,*) 'i =', i
write(*,*) 'sum =', sum
10 continue
Any other loop construct in Fortran had to be simulated with if statements and gotos. This means that even though Fortran brought loops into mainstream programming it was still quite limited. At this point it was still common for flow control to be managed by GOTO and we have not truly entered the era of structured programming.
Cobol has a similar story to Fortran in terms of loops. They were certainly part of the language but it wasn’t at all like modern languages loop construction. In Cobol the loop construct is perform until. This loop construct would look like this6:
B-100-PROCESS.
READ PAY-FILE
AT END
MOVE "Y" TO EOF-IND.
PERFORM B-200-LOOP
UNTIL EOF-IND = "Y".
This is functionally very similar to a while loop. Once again though early Cobol only had a single construct for loops. Interestingly the more modern For loop construct was actually defined before the Cobol standard was created in 1958. This was done with the creation of the spec for Algol 58. However Algol 58 was more of an idea than an actually implemented language.
Despite this, if we want to see the actual predecessor of loops in most modern programming languages ALGOL is actually the place that we need to look. In Algol there were the full components of structured programming including for and while loops that basically are the same as for and while loops in most modern languages.
Algol adopted the three part syntax for a for loop that we recognize today. This was carried down by C and its descendants making it the most common style of loop that we now have. This is also true for if statements. The while loop followed in the next version of the ALGOL spec ALGOL 60.
In both cases though this significantly predates the coining of the term structured programming. The term was first used in 19667 Then it was popularized by Djikstra. At this point it is the way we program so we don’t think much about it. However the first implementation of this was in Algol.
Structured Programming and For Each Loops
The thing was though Algol wasn’t really used it was an academic language at best since it lacked important features like file IO. Most programming that was actually done was in fortran, cobol or assembler. This meant that at the time the ideas in structured programming were controversial. This is hard to remember today when basically every programming language uses structured programming.
The debate over structured programming wasn’t fully settled until the late 1980’s. It was also around this period where we also started seeing loops that could run directly over data structures in languages such as smalltalk. In Smalltalk there was a loop over a collection for example8 :
anOrderedCollection := OrderedCollection new.
anOrderedCollection add: 1; add: 2; add: 3; add: 4.
anOrderedCollection do:[:each | Transcript show: each]. "Prints --> 1234"
This was kept in most modern programming languages for example in python
l = [1,2,3,4]
for i in l:
print(l)
At this point we’ve skipped through quite a few of the highlights of loops. Now I mostly avoided talking about recursion which can easily be viewed as another form of iteration. However this was already getting big enough as a post without talking about it.
There were a few common threads that brought together loops in modern programming. Fortran and Cobol loops as representation of the world and to allow for models Structured programming and Algol which brought about the for and while loop Small talk and the concept of looping over a collection.
Loops and our improvements to them though really are about bringing notions for how humans think into a way that computers understand. Fundemendantly we want to be able to make repeating a process easy and simple to think about especially since we use computers to automate repetitive tasks. This pushes us to make constructs in our programming languages that make it easy to cycle through the same set of operations over and over again until we’ve either finished with computing that set of data or just having the computer wait in a loop until more data arrives.