Daily Archives: December 17, 2007

On Von Neumann’s First Program

[First published as XO-Python: On Von Neumann’s First Program on December 17, 2007.]

While doing some web research preparing the previous post in this series on Python and the XO, Python-XO: Programming as applied mathematics, I came across a fascinating article by Don Knuth about John von Neumann’s first program, Von Neumann’s First Program (PDF).

John von Neumann was one of the greatest physicists and mathematicians of the 20th century. He was legendary for his ability to do complex mathematical computations in his head, and set out much of the foundations of the structure of computers as we use them today. Back in my days in grad school several decades ago it was common to hear his name associated with computers, though as Wikipedia notes this is now rarely the case.

Though I had read some of von Neumanns’ early work in the late 1940’s in typescript form in the Courant library while in grad school, I was not familiar with this work, which was done in 1945 It was kept by Herman Goldstine, another of the pioneers of computing, in manuscript form. Don Knuth, the best computer scientist of his generation, begins his paper as follows:

A handwritten document now in the possession of Dr. Herman H. Goldstine contains what is probably the earliest extant program for a stored program digital computer. Its author, the remarkably talented mathematician John von Neumann (1903-1957), was in the process of refining the stored program concept as he was writing this code; so his program represents a significant step in the evolution of computer organization as well as of programming techniques. In this paper we will therefore investigate the contents of yon Neumann’s manuscript in some detail, attempting to relate its ideas to other developments in the early history of high speed computing.

The program we will study is not what we might expect an “ordinary” mathematician to have written; it does not solve a partial differential equation! Instead, it deals with what was considered at that time to be the principal example of a nonnumeric application for computers, namely, the problem of sorting data into nondecreasing order.

Shortly thereafter we learn that:

The key question was whether or not the proposed instruction set provided a satisfactory means of logical control for complex processes, and so he felt that a sorting program would be a most instructive test case. Furthermore, the existence of IBM’s special purpose machines for sorting gave him a standard against which he could measure the proposed computer’s speed.

By way of background, the “IBM machines” mentioned were not computers, but specially-built mechanical devices that could sort punched cards. I go back far enough that I can recall using such machines, and they were a joy to use, though the occasional jam could ruin a day. They gave a real-time demonstration of what is known as a “radix sort.”

It is worth noting that von Neumann was not only working out fundamental principles of operation of computers as we know them today but was also from the start interested in measuring the performance of his program. He was not programming in the abstract world of Turing machines (about which we will learn more in forthcoming posts) but in the real world, a world where cost and performance mattered, especially given the great cost needed to build computers in those days, even though von Neumann was designing for a machine with only three 32- bit registers and 8192 words of memory. The current state of the art at the time, as expressed by Knuth, was “The ENIAC was a highly parallel computer; weighing over 30 tons, it involved over 19,000 vacuum tubes, 1500 relays, etc. Because of its electronic circuitry, it was considerably faster than any computing machine previously built. But it had only 20 words of internal memory, and it required complicated manual operations for setting up a program on plugboards.”

Hardware afficionados can appreciate the following comment:

The EDVAC memory was to be divided into 256 “tanks” of 32 words each, operating in a cyclic fashion. Word 0 of each tank would pass a reading station one bit at a time, then (32 bit-times later) word 1 would be available,…, finally word 31, then word 0 again, etc. Thus the accessing of information from tanks is essentially the same as we now have from drums or head-per-track disks.

This means of accessing information is not only that used in disks today but was also used to access memory in the earliest versions of what is now the x86 architecture. Indeed, the requirement to account for a similar delay in accessing memory led to the infamous “wrong” byte order in the 8080 architecture that has plagued generations of programmers. [1]

Key to von Neumann’s means of expressing programs is the notion of sequencing, what is called “control flow”:

Instructions were to be executed from consecutive locations, unless the sequence of control was modified by a JMP order. If the control sequence would come across a number (not an instruction word), the effect would be as if an LOD instruction were performed referring to this number.

Von Neumann sketched out only part of the complete algorithm, in a form of notation similar to mathematics. Knuth translates that into “pseudo” code that is is recognizable as code to any programmer. “Pseudo code” is code not for a particular machine, but code for a hypothetical machine to illustrate how a computation can be carried out.
A few sections are of particular interest to those first learning a programming language such as Python:

After having written the program, he assigned actual addresses to the subscripted ones. In order to make the code relocatable, for use as a general open subroutine, he assigned the addresses relative to an unspecified starting location e. His address assignments are shown in Figure 2 at the right of the instructions.

Von Neumann discussed the relocatability of this routine by enumerating the nine instructions which are variable (those whose codes depend on p, EXIT, or the relocation factor e). He didn’t say exactly how these instructions were to be changed after they have been read in from tape; he apparently did not yet realize that the limited EDVAC code he had proposed (with no shift instructions, for example) made it difficult to insert p into the “PIK” and “PUT” instructions, since the machine could only store into the address field of instruction words. It is perhaps significant that he thought of this program as an open subroutine, not closed, since he did not regard EXIT as a parameter on a par with n, m, location(x0), etc.

Von Neumann here first sketched out, or defined, what are now known as subroutines or procedures. These are expressed in Python using the def statement.

Not a great deal of technical expertise is needed to read Knuth’s full paper. Much of it is quite accessible; it provides a fascinating insight to the first expression of key concepts that every programmer takes for granted. As such, it serves as a reminder that what seems commonplace now was once unknown.

Notes:

1. I once heard a talk by the designer (whose name I can’t recall now) of the Intel 8086 architecture. He said that during the design process he had been given the option of putting the bytes in the “right” order, but decided to leave things as they were. This comment was met by a loud groan from all the programmers in the audience, and he said he had come to realize the error of his ways.

Programmers sometimes have to live with their mistakes for decades. For example, if you ever happen to meet a Google employee named Stu Feldman, give him a hard stare while silently saying the phrase “tab character” to yourself. You don’t have to say anything out loud, just don the appropriate look of despair as you recall the hours that have been wasted putting tabs at the right place in “make” files. He’ll get the message. You will make his day.

Programming as applied mathematics

[First published as Python-XO: Programming as applied mathematics on December 17, 2007.]

Python is the programming language used to write most of the applications that come with the XO Laptop.

In Python-XO: The Farmer in the Dell, I said that programming is just a form of writing, and gave a brief example of a program in the Python programming language.

The writing that is programming is scientific in nature. Programs specify how computers are to operate. Computers– including desktops, laptops, or contained within wrist watches, printers, cell phones, and games such as the Sony Playstation and the Microsoft XBox — are the creation of scientists and engineers. The essential elements of programming languages are dictated by the structure of computers and are mathematical in nature. Programming is thus a form of applied mathematics.

However, this view of programming as applied mathematics is not a common one. For example, let’s look at several views of Python.

Guido Rossum, the creator of Python, says, in his Executive Summary:

What is Python? Executive Summary

Python is an interpreted, object-oriented, high-level programming language with dynamic semantics. Its high-level built in data structures, combined with dynamic typing and dynamic binding, make it very attractive for Rapid Application Development, as well as for use as a scripting or glue language to connect existing components together. Python’s simple, easy to learn syntax emphasizes readability and therefore reduces the cost of program maintenance. Python supports modules and packages, which encourages program modularity and code reuse. The Python interpreter and the extensive standard library are available in source or binary form without charge for all major platforms, and can be freely distributed.

Often, programmers fall in love with Python because of the increased productivity it provides. Since there is no compilation step, the edit-test-debug cycle is incredibly fast. Debugging Python programs is easy: a bug or bad input will never cause a segmentation fault. Instead, when the interpreter discovers an error, it raises an exception. When the program doesn’t catch the exception, the interpreter prints a stack trace. A source level debugger allows inspection of local and global variables, evaluation of arbitrary expressions, setting breakpoints, stepping through the code a line at a time, and so on. The debugger is written in Python itself, testifying to Python’s introspective power. On the other hand, often the quickest way to debug a program is to add a few print statements to the source: the fast edit-test-debug cycle makes this simple approach very effective.

Eric S. Raymond, another well-known programmer, says in his essay, Why Python?:

I had already heard just enough about Python to know that it is what is nowadays called a “scripting language”, an interpretive language with its own built-in memory management and good facilities for calling and cooperating with other programs. So I dived into Programming Python with one question uppermost in my mind: what has this got that Perl does not?

Here is part of the brief summary from the Python wiki:

What Is Python?

Python is a programming/scripting language that can be used on many different computers and operating systems, including Windows, Unix, Macintosh, etc. I’ve heard of it being run on everything from palm computers to Cray super computers. For a number of reasons, it’s the *best* way to learn computer programming in general. The first few that come to mind are:

* The interactive “shell” allows you to instantly see if you did it right. Personally I find the Python shell easier to use than a calculator for everyday math at home and at work.

* The language is elegant and just plain makes sense, which means you or someone else can read your code weeks or months after you wrote it, and it will still make sense!

* Python was designed from the ground up for learning programming.

* You gotta love the awesome Python community of people who really want to help, such as the Python tutor email list.

* It has a short learning curve, which can have you programming successfully within minutes (really).

* Including the one that comes with the free Python download, there plenty of tutorials available for both programmers and people new to programming.

* It’s free and open source.

* It was named after Monty Python, which makes you wonder…..

* It’s a good stepping-stone to languages like Perl, Java, and C++, which make more sense after picking up some Python.

* It’s cross-platform, so the code you write for your Windows PC at home can be run on the linux server at work!

Though all these summaries are accurate, and I agree with most of the points they make, they don’t capture the essence of Python as I see it.

I spent the best years of my professional life — over a decade’s worth as it turned out — working on SETL, a language inspired by a simple observation by Jacob T. “Jack” Schwartz:

It would be an interesting experiment to base a programming language on finite set theory.

Python is based in part on some of the ideas found in SETL, and is the language closest in spirit to SETL that is currently in widespread use. The power of Python comes in large part from the power of set theory itself, for set theory is fundamental to mathematics. Here is an example, in the form of some pictures.

200712 032
On Sets

The page on the left is from Naive Set Theory by Paul R. Halmos. The part just above the miniature terminal says (emphasis added):

A pack of wolves, a bunch of grapes, or a flock of pigeons are all examples of sets of things. The mathematical concept of a set can be used as the foundation for all known mathematics.

The page on the right is from the lecture notes of a course in Mathematical Logic by Professor Martin Davis of NYU’s Courant Institute of Mathematical Sciences (CIMS) that I took in the Fall of 1969 (emphasis added):

Theorem 7.1. N is inconsistent.

This result should serve to emphasize that a theory whose postulates seem plausible enough can turn out to be inconsistent. Because all of contemporary mathematics can be developed in terms of the notion of set theory, N might have been thought of as an entirely reasonable starting point for the derivation of the entire body of mathematics.

Here is photo of the first page of Halmos’s classic work, Measure Theory:

200712 036
Chaper I: Measure Theory
:

Note that the first word in the first chapter is “sets,” another indication of the fundamental importance of set theory to mathematics.

The Preface to Naive Set Theory begins as follows:

Every mathematician agrees that every mathematician must know some set theory; the disagreement begins in trying to decide how much is some. This book contains my answer to that question. The purpose of the book is to tell the beginning student of advanced mathematics the basic set-theoretic facts of life, and to do so with a minimum of philosophical discourse and logical formalism.

Though one need not know any advanced mathematics, including set theory, to be a programmer, I think that an appreciation for the mathematical foundations of programming will make one a better programmer, and I expect that most skilled programmers know , though they might not first appreciate it, more mathematics than they give themselves credit for.

  • Pages

  • December 2007
    M T W T F S S
    « Nov   Jan »
     12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31  
  • RSS The Wayward Word Press

  • Recent Comments

    Sahana’s Respo… on A brief history of Sahana by S…
    Sahana’s Respo… on A brief history of Sahana by S…
    James Murray on On being the maintainer, sole…
    James Murray on On being the maintainer, sole…
    mrrdev on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated