Functions and Recursive Functions

From TimPenner.ca
Jump to: navigation, search

This page is a work in progress.



The advent of the concept of stored-program devices was the first and key event that presaged programmability and, ultimately, computer technology. The second event was the advent of the function subprogram.

Consider a player piano with its music roll. You put the roll in and the piano plays the tune to the end, according to the sequence of the marks (or holes) in the roll. Image what it would be like if you could make holes in the roll that would cause the piano to replay a certain part a set number of times - I mean without making a roll into a loop that repeats the entire sequence of notes endlessly. (You'll have to imagine that somehow reversing the movement of the roll back to replay from a preset point does not affect the cadence of the music.) For long repeated sequences, like verses of a song, it would make rolls a lot shorter.

One feature that most who hear this little story don't realize: the marks in the roll that cause a section of the music to be repeated are, logically, quite different. These marks are instructions for the roll mechanism, not indications of notes to play. That difference is a fundamental distinction in this discussion of programmability.

Now imagine being able to program the player piano with a roll that allows the repeated use of a phrase, like a chorus for example, stored on a second roll, that could be called up with special indicator marks on the main roll. If having multiple rolls doesn't make the piano too complicated, you could have several rolls, perhaps with many different tunes and parts of tunes pre-stored on rolls that could be changed while other rolls are "playing". You could even have a main roll whose function is to respond to marks that just select which other rolls to play. This is, again, a logically distinct aspect of programmability that this discussion is intended to highlight.

This is would quite a complicated piano, perhaps a lot bigger than a regular upright with a single player roll in it, but there would be all kinds of entertainment possibilities.

This little story about a complicated player piano describes many important features characteristic of the way that computers deal with computer programs.


Here's how it works:

  • programs are lists of instructions that device follow in a set sequence that is controllable by the programmer
One of the main concerns of a computer programmer is to carefully stipulate instruction sequence to accommodate
  • programmers need to be able to use common sequences of instructions repeatedly in different situations
As I type these words, I'm thinking about the different situations in which I expect my computer to understand keystrokes and how efficient it would be if the software that accepts these keystrokes was used in all those situations
  • There is also the need to repeat sets of instructions
Personal tools
Namespaces

Variants
Actions
Navigation
Contact
Areas Intros
References
Tools