Monday, December 26, 2011

Preface to Homer

But of the tree of the knowledge of good and euill, thou ſhalt not eate of it: for in the day that thou eateſt thereof, thou ſhalt ſurely die.
Genesis 2:17 (King James Version)
I'm going to suggest a hypothesis on the evolution of societies, natural languages, and memetic organisms.  Relating human language and human thought to programming is a straightforward exercise left to the student.

Eric Havelock in his magnum opus Preface to Plato (fascinating stuff) describes two profoundly different stages in the evolution of human societies, which he calls oral society and literate society.  Greek society, reckons Havelock, was transforming from oral to literate around the time of Plato; the epics of Homer are characteristic of oral culture.  I suggest that there is a stage of societal evolution before that of oral poetry such as Homer's — and that just as Afghan culture is a surviving example of oral society, the Pirahã culture recently studied in the Amazon is a surviving example of... verbal society.  (I can't bring myself to call it "pre-oral", since language is still spoken; but it does have words, and is missing oration, so "verbal" will do till something better comes along.)

Scientific organisms need a literate environment to survive; religious organisms don't need literacy, and were, I reckon, the giants that roamed the ideosphere in the age of orality.  But in the age before Homer's, religions could not have survived either.  If ever there were an actual event that fits beautifully with the myth of Adam and Eve eating of the fruit of the Tree of Knowledge, the transition from verbal to oral society would be it.

Oral thought

In an oral society (in Havelock's vision — I've also read parts of Walter Ong's Orality and Literacy, which follows Havelock's paradigm), knowledge is preserved through an oral tradition.  The form of the account matters; facts are mutated as convenient to put them in a form that will be successfully replicated over many retellings.  Standard patterns are used.  Repetition is used.  A good story also always has an actor:  things don't just happen, they are done, by somebody, which may favor a polytheistic society, with deities personifying what we (in a literate society) would call "abstract" forces.  One might well end up with some such pattern as
And God said, let there be x.  And there was x.  And God saw the x, and saw that it was good.  And the morning and the evening were the nth day.

And God said, let there be y.  And there was y.  And God saw the y, and saw that it was good.  And the morning and the evening were the n+1st day.
(Note the repetition of each item, repetition of the pattern, and the actor.)  For a more concrete example, here is the start of Thomas Hobbes's 1676 translation of Homer's Iliad:
O goddess sing what woe the discontent
Of Thetis’ son brought to the Greeks; what souls
Of heroes down to Erebus it sent,
Leaving their bodies unto dogs and fowls;
Whilst the two princes of the army strove,
King Agamemnon and Achilles stout.
Notice that things here don't happen, somebody/something does them.  The goddess sings.  The discontent (of Thetis' son) brings, sends, leaves.  The two princes strive.

The things that are acted on are concrete as well; nothing is abstract in our literate sense.

Such oral tradition can be written down, and was written down, without disrupting the orality of the society.  Literate society is what happens when the culture itself embraces writing as a means of preserving knowledge instead of an oral tradition.  Once literacy is assimilated, set patterns are no longer needed, repetition is no longer needed, pervasive actors are no longer needed, and details become reliably stable in a way that simply doesn't happen in oral society — the keepers of an oral tradition are apt to believe they tell a story exactly the same way each time, but only because they and their telling change as one.  When the actors go away, it becomes possible to conceive of abstract entities.  Plato, with his descriptions of shadows on a cave wall, and Ideal Forms, and such, was (Havelock reckoned) trying to explain literate abstraction in a way that might be understood by someone with an oral worldview.

Note that science can't possibly survive in an oral environment.  It relies on an objectively fixed record of phenomena, against which to judge theories; and it centrally studies abstract forces.  Religion, on the other hand, is ideally suited to an oral environment.  I suggest that religious organisms were the dominant taxon of memetic organisms in oral society, and the taxon of scientific organisms evolved once literate society made it possible.  Leading to a classic Darwinian struggle for survival between the two taxa.

Verbal thought

Those who study natural languages have a luxury not afforded to artlangers, those who create languages artistically:  When a natural language crops up that violates the "natural" rules that linguists thought they understood, new rules can be invented to fit.  But, if an artlanger creates a language that violates the rules linguists think they understand, their creation is likely to be ridiculed.  This was the observation of David J. Peterson in an essay in 2007 (he gives a "Smiley award" to a conlang each year, and does so in essays containing some brilliant deep insights into conlanging).
What is it to a linguist if Pirahã exists? "That sounds totally fake," says the skeptic. Says the linguist, "Yeah, doesn't it?" But in a world where Pirahã doesn't exist, imagine the conlanger who created it. "I just made up a language with no temporal vocabulary or tense whatsoever, no number system, and a culture of people who have no oral history, no art, and no appreciation for storytelling. Oh, yeah, and the language can just as easily be whistled, hummed or drummed as spoken. Oh, and the men and women have different phonologies. Oh yeah, and it's spoken in an area with a dominant language, but nobody speaks it, because they think their language is the best. Oh yeah, and it's supposed to be a naturalistic language." Suddenly when someone counters and says, "That sounds totally fake," the conlanger is put on the defensive, because they do have to account for it—in other words, "Yeah, doesn't it?" isn't going to fly.
— David J. Peterson, The 2007 Smiley Award Winner: Teonaht
Which is interesting for a conlanger, but fascinating in light of Havelock's notion of oral society.  That list of features is pretty much explicitly saying the language doesn't and can't support an oral society:  "no oral history, no art, and no appreciation for storytelling" (doesn't), "no temporal vocabulary or tense whatsoever, no number sytem" (can't).  And for a verbal society to survive in a world where the main Darwinian memetic struggle is between literacy and orality, of course it would have to be an extraordinarily compelling instance of verbality — "nobody speaks" the dominant language of the area, "because they think their language is the best."

The fruit of the Tree of Knowledge

The Pirahã were studied by Daniel Everett, who originally approached them with an evangelical mission — the point of such efforts is to learn an isolated people's language, then translate the teachings of Christianity into that language.  Of course this failed miserably with the Pirahã, with their compellingly verbal language and culture (J.R.R. Tolkien criticized the international auxilliary language Esperanto as sterile because it had no mythology behind it (one could argue Esperanto now does have a mythology of a sort (but I digress))).  Within a few years after completing his dissertation, Everett became an atheist.  (Everett's 2008 book on his experiences with the Pirahã is Don't Sleep There are Snakes: Life and Language in the Amazonian Jungle.)

All of which goes to show that the myth of the fruit of the Tree of Knowledge can be handily applied to the transition from verbal to oral society.  However, as I pointed out in my earlier post on memetic organisms, religious teachings are naturally selected for their ambiguity, their ability to be given a wide variety of different interpretations.  The plausibility of an interpretation of the myth is, therefore, pretty much meaningless — the myth is a contextual chamelion, expected to blend plausibly into different belief systems.  But it is interesting to consider how the myth might have evolved.  The early Judaic written tradition is evidently a written record of an originally oral tradition, and an oral tradition mutates events into a good story (i.e., a highly replicable one).  If the verbality conjecture is somewhere in the general neighborhood of the truth, there may once have been a vast cultural upheaval as orality supplanted verbality, perhaps (or perhaps not) on a par with the modern struggle between scientific and religious thinking (a major theme of current geopolitics).  Such an upheaval might be expected to make a lasting impression on the oral societies that emerged; the lasting impression would be a myth; and the myth would be shaped into the forms of orality, with concrete actors and objects.  What sort of myth do you think might result?

Friday, December 9, 2011

The trouble with monads

IT was six men of Indostan
    To learning much inclined,
Who went to see the Elephant
    (Though all of them were blind),
That each by observation
    Might satisfy his mind.
The Blind Men and the Elephant, John Godfrey Saxe
Note:  So far, I've found three different ways of applying this epigraph to the following blog post.
Monadic programming is a device by which pure functional languages are able to handle impure forms of computation (side-effects).  Depending on who you ask, it's either very natural or preposterously esoteric.

I submit there is a systemic problem with monadic programming in its current form.  Superficially, the problem appears technical.  Just beneath that surface, it appears to be about breaking abstraction barriers.  Below that, the abstraction barriers seem to have already been broken by the pure functional programming paradigm.  I'll suggest, broadly, an alternative approach to functional programming that might resurrect the otherwise disabled abstraction barriers.

What monads do for pure FP

A pure function has no side-effects.  Pure functional programming —programming entirely with pure functions— has some advantages for correctness proofs, which is (arguably) all very well as long as the purpose of the program is to produce a final answer.  Producing a final answer is just what a pure function does.  Sometimes, though, impurities are part of the purpose of the program.  I/O is the canonical example:  if the point is to interact with the external world, a program that cannot interact with the external world certainly misses the point.

If the point is to interact with the external world, and you still want to use a pure function to do it, you can write a pure function that (in essence) takes the state of the external world as a parameter, and returns its result together with a consequent state of the external world.  Other forms of impurity can be handled similarly, with a pure function that explicitly provides for the particular variety of impurity; monads are "simply" a general pattern for a broad range of such explicit provisions.

Note, however, that while the monadic program is parameterized by the initial state of the external world, the monad itself is hardcoded into the type signature of the pure function.

What goes wrong

The essential difficulty with this approach is that since the monad is hardcoded into the function's type signature, it also gets hardcoded into clients who wish to call that function.

To illustrate the resulting brittleness, suppose some relatively small function f is used by a large program p, involving many functions, with calls to f at the bottom of many layers of nesting of calls.  Suppose all the functions in p are pure, but later, we decide each call to f should incidentally output some diagnostic message, which makes no difference to the operation of the program but is meant to be observed by a human operator.  That's I/O, and the type signature of f hadn't provided for I/O; so we have to change its type signature by wiring in a suitable I/O monad.  But then, each function that directly calls f has to be changed to recognize the new signature of f, and since the calling function now involves I/O, its type signature too has to change.  And type signatures change all the way up the hierarchy of nested function calls, until the main function of p gets a different type signature.

Every direct or indirect client of f has been forced to provide for the stateful I/O behavior of f.  One could ask, though, why this stateful behavior of f should make any difference at all to those clients.  They don't do any I/O, and if not for this type-signature business they wouldn't care that f does; so why should f's I/O be any of their business?  For them to bother with it at all seems a violation of an abstraction barrier of f.

Actually, this very real abstraction violation was not caused by the introduction of monads into pure functional programming — it was highlighted by that introduction.  The violation had already occurred with the imposition of pure functional programming, which denies each component function the right to practice impurities behind an abstraction barrier while merely presenting a pure appearance to its clients.

The introduction of monads also created the distracting illusion that the clients were the ones responsible for violating the abstraction barrier.  On the contrary, the clients are merely where the symptoms of the violation appear.  The question should not be why the client function cares whether f is internally impure (it doesn't care; its involvement was forced), but rather, who is it who does care, and why?

Bigness

Monads come from a relatively modern branch of mathematics (it's a mere half-century old) called category theory.

A category is a well-behaved family of morphisms between objects of some uniform kind.  The category provides one operation on morphisms:  composition, which is defined only when one morphism ends on the same object where the next morphism starts.  (Technically, a category is its composition operation, in that two different categories may have the same objects and the same morphisms, and still be different if their composition operation is different.)

The canonical example is category Set, which is the family of mathematical functions between sets — with the usual notion of function composition.  That's all possible functions, between all possible sets.  This is typical of the scale at which category theory is brought to bear on computation theory:  a category represents the universe of all possible computations of interest.  The categories involved are then things like all computable pure functions, or all computable functions with a certain kind of side-effect — it should be clearly understood that these categories are big.  Staggeringly, cosmologically, big.

Besides well-behaved families of morphisms between objects of a uniform kind, there are also well-behaved families of morphisms from objects of one uniform kind to objects of another uniform kind.  These families of heterogenous morphisms are called adjunctions.  An adjunction includes, within its structure, a category of homogeneous morphisms within each of the two kinds of objects — called the domain category (from which) and codomain category (to which the heterogeneous morphisms of the adjunction go).  The adjunction also projects objects and morphisms of each category onto the other, projects each of its own heterogeneous morphisms as a homogeneous morphism in each of the categories, and requires various relations to hold in each category between the various projections.

The whole massive adjunction structure can be viewed as a morphism from the domain category to the codomain category — and adjunctions viewed this way are, in fact, composable in a (what else?) very well-behaved way, so that one has a category Adj whose objects are categories and whose morphisms are adjunctions.  If the categories we're interested in are whole universes of computation, and the adjunctions are massive structures relating pairs of universes, the adjunctive category Adj is mind-numbingly vast.  (In its rigorous mathematical treatment, Adj is a large category, which means it's too big to be contained in large categories, which can themselves only contain "small" categories — an arrangement that prevents large categories from containing themselves and thereby avoids Russell's paradox.)

A monad is the result of projecting all the parts of an adjunction onto its domain category — in effect, it is the "shadow" that the adjunction casts in the domain.  This allows the entire relation between the two categories to be viewed within the universe of the domain; and in the categorical view of computation, it allows various forms of impure computation to be viewed within the universe of pure computation.  This was (to my knowledge) the earliest use of monads in relation to computation:  a device for viewing impure computation within the world of pure computation.  A significant limitation in this manner of viewing impure computations is that, although adjunctions are composable, monads in general are not.  Here the "shadow" metaphor works tolerably well:  two unconnected things may appear from their shadows to be connected.  Adjunctions are only composable if the domain of one is the codomain of the other — which is almost certainly not true here, because all our monads have the same domain category (pure computation), while the shadows cast in pure computation all appear to coincide since the distinct codomains have all been collapsed into the domain.

Who is viewing these various forms of computation, through the shadows they cast on the world of pure computation?  Evidently, the programmer — in their role as Creator.  A God's eye view.  Viewing the totality of p through the universe of pure computation is the point of the exercise; the need for all clients of f to accommodate themselves to f's internal use of I/O is an artifact of the programmer's choice of view.

Rethinking the paradigm

So, here are the points we have to work with.
  • A monad represents the physical laws of a computational universe within which functions exist.
  • The monad itself exists within the pure computational universe, rather than within the universe whose laws it represents.  This is why monads are generally uncomposable:  they have forgotten which actual universes they represent, and composition of adjunctions wants that forgotten knowledge.
  • Function signatures reflect these computational laws, but serve two different purposes.  From the client's eye view, a function signature is an interface abstraction; while from the God's eye view (in the pure computational universe), a function signature is the laws under which the function and everything it uses must operate.
To uncouple a function's interface from its laws of computation, we need a function signature that does not take a God's eye view.  The most "purity" one can then ascribe to a function f, looking at the definition of f without the definitions of other functions it calls, is that f uses other functions as if they were pure, and doesn't itself introduce any impurities. From a God's eye view, computational laws then have to pass from function to function, either
  • by synthesis — when function f calls function g, g returns its computational laws along with its result value, and f works out how to knit them all into a coherent behavior, and returns its own knit-together computational laws along with its own result value — or
  • by inheritance — when function f calls function g, f passes in its computation laws along with its parameters to g, and g works out both how to knit them into its own computational laws internally, and how to present itself to f in terms f can understand.
For purposes of abstraction, inheritance ought to be the way to go, because the point of abstraction is to reduce the conceptual burden on the caller, rather than increase it.  Not surprisingly, inheritance also appears to be the more daunting strategy to figure out.