PDA for PDA

As I intend this page to summarize my work for anyone I happen to befriend, I intend to present my work in successive levels of detail.

Generalities

Every day, people orally communicate with one another. Even the simplest of conversations are difficult for a computer to understand because we rely on implied context and some genuine guess-work to determine the meaning of a sentence.

Could you pass me my glass?

We refer to objects by specifying their qualities, ownership, location, etc. Sometimes we elide all specifications and simply refer to people and things as "he", "she", and "it", relying on prior context or our interlocutor's intuition. Additionally, the words we use often have multiple meanings, only one of which fits the context.

Computer programming languages are far more rigidly defined than natural languages, so ambiguity of meaning rarely occurs; however, ambiguity of approach does occur. I use the term approach to refer to how the machine computes the algorithm specified by the program.

A programmer rarely fully specifies the machine-level implementation of a given algorithm. She will rely on libraries that provide general solutions to portions of the algorithm. More importantly, many programs written today manipulate abstract, symbolic data like bank accounts, message inboxes, physical sensors, and other programs. The specific representation of these data as streams of ones and zeros is rarely specified by the programmer.

The programmer instead relies on a compiler to intelligently translate the program into ones and zeros that the computer can understand. The compiler must recover contextual information about how various general utilities and concepts are used in the given program. A program's data often have unwritten invariants which the program implicitly or explicitly understands, but does not communicate in source code. These invariants can be as simple as this numeric variable is always positive or as complex as this anonymous function is only called at call sites C3 and C45 with values of types A or B.

Compilers generally must produce safe code, which is to say, no matter what happens at run-time, the program will execute correctly. This is analogous to a workman instructing his apprentice to bring a hammer with the expectation that this hammer function equally well as a sludge hammer and a nimble picture hanging hammer. Program invariants are like an implicit understanding that the hammer need only drive a picture nail rather than a heavy slug.

Invariants in hand, the compiler is free to produce more efficient programs.

back