Computer programs are also formal instructions telling the computer hardware just what steps to perform. Programs actually have two separate parts. One part describes the variables or memory locations where data will be stored and manipulated and the second part describes the sequence of steps that are followed manipulating this data.
Many programs receive data from the outside world via keyboard or Internet or sensors that can read temperature or video input. Many programs communicate with the outside world via display or speaker or data sent out to printers or the Internet. In addition, data is kept in a program where it may be manipulated, searched, processed mathematically, or used to make decisions. For example, the computer in my car will take some action when it notices I only have 50 miles more range before I run out of gas. It will sound a chime and display a message on my dashboard.
Computer programs can test if two items of data are equal or if one is bigger than the other and then a program can make a selection of what code to follow depending on the result of these tests. That’s the basis of all programs. Programs can write data or increment data or, in other ways, manipulate the data stored in memory. Exactly how this is done or the exact sequence or “syntax” used to make these tests and instructions varies depending if the programming language is BASIC or C or C++ or Java or one of thousands of other programming languages.
Besides instructions, recipes also have something I can compare to data. It is the “ingredients.” Many recipes start by listing the ingredients so you’ll know what to gather to make the dish. These ingredients are described and the recipe lists how much of each one is needed: a cup of this, a teaspoon of that, a pound of this and a can of that.
The recipe then goes on to tell you what to do with these ingredients: how to combine them and mix them and stir them and heat them and serve them.
That led me to these thoughts about computer programs. You see, simple programs only run one time. For example, there might be a program to print a file. You would start this program and it would move data from some location to your printer causing a printed output to appear. But many programs, especially the programs that make up your operating system or any complex program such as Microsoft Word or Excel do many, many different tasks in different order. Sometimes they do the same thing over and over again, but with slightly different data.
A simple way to repeat an instruction is called a "loop." That’s like a recipe telling you to stir something for a minute. You swirl the spoon around over and over again. Some programs execute the same section of code over and over again until the result desired is accomplished. For example, the “search” function in Microsoft Word examines each word in the text and compares it to the word being searched for. This loop stops or “terminates” when a word matching the search text is encountered or the program tests all the words and none of them match.
There is another way to repeat things in a computer program that is much deeper and more interesting than a simple loop. It is called “recursion.” In recursion a section of code will repeat itself in a form of déjà vu. But in this case, when it repeats itself, it uses a whole new set of data.
In computer programs, recursion is done when a section of code, usually called a "function" or a "procedure," calls itself. That's sort of like the recipe for a Bunt Cake instructing the cook to follow another recipe for a Bunt cake. Not quite what a program will do, but close. Very complex and very fascinating. Using recursion it seems that the computer can actually do two things at once.
It isn’t really performing two (or more) things at the same time, but the speed of the computer makes it appear that the system is multitasking … doing several things at the same time. Actually, just like humans, computers can only do one thing at a time. They just keep switching from one unfinished task to another unfinished task and accomplish both goals during the same time period.
An exception to this is modern multi-core computers. They actually can perform two or more tasks at the same time. This is called "parallel operation." Multi-core PC processors have only appeared in the last ten years. Before that, all multitasking was done on a single processor core.
That’s a lot like preparing dinner from several recipes. Many different dishes are in the process of preparation and cooking and the chef switches from task to task to accomplish the final goal of “dinner.”
The earliest version of PC DOS, versions 1.0 and 1.1, did not allow recursion. They were not designed for recursion. They didn’t have the ability to reuse data that was in use, which is what is needed to allow for recursion.
And then the “new” PC DOS 2.0 was released. It had a new print function that could be used to print a file while the computer continued on with other tasks. This was the first multitasking on the IBM PC. Experts were amazed because they knew that PC DOS was not designed for multitasking and could not operate recursively. So everyone wanted to know how in the world IBM had accomplished this.
Upon some research, they found that IBM had added a flag to the operating system. A flag is a piece of data that stores a condition. This flag was called “DOS busy.” Any time DOS entered a section of code that could not be interrupted, that could not be run recursively, the “DOS busy” flag was set. Once this non-interruptible section of code completed, the flag was reset.
You could compare this to a one-way bridge on a country road that has a signal light at each end. When traffic is traveling one way across the bridge, traffic from the other side is stopped until the first cars clear the bridge. "DOS busy" was the traffic light.
When the second function, “Print,” was running too, it would stop any time the “DOS busy” flag was set and wait for that section of code to be completed before continuing. This worked very well and allowed DOS to print out a file while allowing the computer to perform other work simultaneously. That’s multitasking.
More modern operating systems, such as Windows, UNIX, and Mac OS, use a stack oriented data system that doesn’t require such flags to support multitasking, but the primitive DOS operating system was not so sophisticated.
Of course, almost immediately, other companies took advantage of this “DOS busy” flag to write their own recursive and multitasking programs. One of the first was a company that created a compiler for the Pascal programming language. The company was called Borland and they had a very successful "Turbo Pascal" compiler program for the IBM PC.
They branched out introducing Borland “Sidekick.” This was a program that came out in 1983 and that would maintain your personal information. It worked on DOS 2.0 using the built in "busy" flag. It would keep a calendar, address book, notepad, automatic phone dialer, and other useful features running in the background. No matter what task you were performing on the PC, a special combinations of keys would pop Sidekick up to add to the calendar or look up and dial a phone number.
This was the start of “pop ups,” which were just multitasking programs that ran in the “background” on PC DOS. All this was managed by using the “DOS busy” flag to keep different programs from “stepping on each other.”
The key to recursion is managing the storage of data. Suppose you had a section of code that stored a value in a particular memory location and used that information to update progress. This might be a value to keeps track of where the cursor is located on the screen.
Well, if another program takes control momentarily, like a “pop up,” and it changes the memory location value, then when the original program recovers control, it will have lost track of where the cursor is located. DOS busy prevented two programs from using the same set of code that had such important memory reads and writes. But a much better method is to let each program store its data in different locations.
Recursion is a powerful problem solving technique or "recipe," and most modern programming languages and operating systems support the use of this technique.
The problem is that recursion allows the same set of program to be used multiple times. So solving this problem requires a sort of temporary storage. Suppose you were making two dishes for dinner at the same time. Each one uses a cup of something, and you only have one measuring cup. So if the first recipe had you pour a cup of milk, and then you switch to the second recipe and it calls for a cup of flour, you can’t reuse the measuring cup because it is already full of milk.
The solution is multiple cups. You might have a stack of measuring cups in your cupboard. The solution with computer programs is similar. You use a data structure called a “stack” to store data and then each recursive call of a section of code will have its own “cup” to store data. All of the modern computer operating systems used today have this stack data structure and support recursion as naturally as a cook on the Food Channel follows a recipe.
That was not a very detailed explanation. To really describe program recursion you would need to understand subprograms and parameter passing and local variables and all kinds of stuff that people started using back in the days of Turbo Pascal. I wonder how many engineers writing the latest versions of Windows or iOS got their start with Turbo. Anyway, you can use another modern program, Google, to look up recursion and see how it is used in mathematics and programming and even in photography ... an example of which is the picture with this blog article.
Computer programs are so much like cooking that writing this is making me hungry. I’m also nostalgic thinking of Borland Sidekick and PC DOS and computers so many years ago. I think I’ll go out to the “Sixties Diner” for a little lunch accompanied by oldies on the juke box. TTFN.
No comments:
Post a Comment