Lamlosuo — eliminating grammatical nouns and verbs

Language is a by-product of general properties of human cognition [...] in conjunction with the constraints on communication that are common to evolved primates [...] and the overarching constraints of human cultures on the languages that evolve from them.

— Daniel L. Everett, Don't Sleep, There are Snakes, 2009, Chapter 15.

This post is about a conlang that seeks to completely undermine the grammatical notions of noun and verb — but leaves the lexical noun/verb distinction more-or-less intact.

In the pipeline, I'm assembling some thoughts on continuations; but this material is ready to run.  I find various insights from Lamlosuo apply to programming language design, since both centrally concern the way the mind processes language — but conlanging is, to me at least (and it seems I'm not the only programming language person who thinks so), a pleasure worth savoring for its own sake.  This also relates to my ideas on the role of fiction in science, briefly mentioned in an earlier post.

Lamlosuo is an exploratory prototype; it's designed to explore the practical consequences of the grammatical premise of a project I've been working on since about the turn of the century (early 2000), in preparation for more naturalistic conlangs to be developed for the project later.  Consequently, the prototype's coverage of different areas of conlang design is spotty; and my account of it here will spotlight particular areas where the exploration has produced interesting results, while inevitably shortchanging, at least for the moment, other areas that don't bear on those particular results.  So don't be surprised by the uneven coverage.

Here's a quick list of some interestingly unexpected developments in Lamlosuo — most of which, alas, will end up deferred to a later blog post (a full description of even a modest conlang is a fairly large beast).

• I'd first imagined that since Lamlosuo isn't trying to be naturalistic, it would have no reason for irregularities.  That seems very naive to me now, but of course my view of it now includes the insights Lamlosuo has given me into the nature of linguistic irregularity.
• I deliberately omitted conjugation; but a different sort of morphosyntactic variation arose, with curious similarities and differences to conjugation.
• I'd planned to eventually include an analog to the copular verb, if only to demonstrate that it just wasn't all that important — that it wouldn't be used even though it was there.  When I finally tried to implement that plan, the grammar rejected the addition.
• I really meant the language to be isolating.  Eventually the structural integrity of the language pushed me to add a stiff dose of incorporation.
• As alluded to above:  While I eliminated the noun/verb distinction from the grammatical structure of the language, a distinction still naturally arose between lexical nouns and verbs, though the distinction lacks grammatical import.  Moreover, my work on this conlang project spun off a second project that eliminated both lexical nouns and lexical verbs while leaving grammatical nouns/verbs intact.

Since I can only find room in this post to cover one major item from this list, I've chosen incorporation.  Pseudo-conjugation was tempting, but is probably best appreciated when one is already acclimated to the grammatical structure; and tracing through the route to incorporation is a good way to acclimate.

Contents
Preliminaries: Nouns, verbs, and thought
Phonology and phonotactics
Vectors
Role alignment
Gender
Prefixes
Subordinate content particles
Provectors
Incorporation

Preliminaries: Nouns, verbs, and thought

Nouns and verbs play a central role in the grammar of, afaics, all human natlangs, and most (arguably all the naturalistic) conlangs I've seen.  I'm not talking about lexical nouns and verbs; there are North American languages that subvert the traditional distinction between the lexical categories of nouns and verbs, and of course there's Kēlen that subverts lexical verbs.  However, I see all these languages (including Kēlen) retaining nouns and verbs at the grammatical level:  a simple clause is still constructed from a verb with noun arguments, which information can then be distributed amongst words in various ways.

This conlang project undertakes to demonstrate a naturalistic class of languages that do not use the verb-with-noun-arguments grammatical construct.  That is, I'm trying to build the conlangs and describe a species of conspeakers whose thought processes naturally give rise to these languages.  On the face of it, this sounds like some sort of investigation of either Whorfianism, or Chomskyism, or both; but it isn't either by intent.

I was first struck by the grammatical centrality of nouns and verbs when contemplating the extreme non-centrality of English prepositions, whose meanings can be wildly context-dependent (and accordingly very difficult to translate to/from other languages).  I mused on the possibility of a language in which pairwise relations between nouns/verbs are more grammatically important, while nouns/verbs themselves are more context-dependent.  Meditating on this idea for a dozen years or so, I settled on the notion that while we evolved on land, where survival favored structuring our thoughts in terms of an activity and its participants, the conspeakers evolved in the open ocean where survival favored structuring their thoughts in terms of navigation.  I'd been inspired here by a claim, in the context of a discussion of the fact that dolphins and whales have bigger brains than we do, that while their brains are bigger, most of that extra wetware is oriented toward navigation; and, drawing further inspiration from the prototype of a treasure map —so many paces that way, then turn to face that thing and go till you come to such-and-such, then etc. etc.— I figured a simple clause for the conspeakers would be an arbitrarily long chain of content words, each with a specified semantic connection to the next in the chain.

Why the emphasis on how the grammatical structure arises from the conspeakers' thought processes?  Because I don't buy in to the incomprehensible aliens motif; I didn't think humans would naturally develop languages with this sort of grammar (insert anadew disclaimer here), therefore I wouldn't consider it plausible unless I could explain why some alien species would do so.  I am inclined to believe there is a principle for general-purpose intelligence analogous to computation's Church-Turing conjecture:  just as any two sufficiently powerful computation engines are capable of simulating each other, any two minds with general-purpose intelligence are capable of comprehending each other — in principle.  Intelligent minds can easily fail to figure each other out —last I heard, we still weren't even sure whether or not rongorongo is writing, let alone what it means— but this is quite different from supposing some fundamental limitation of thought processes that would inherently prevent them from comprehending each other.  I consider the incomprehensible-aliens gambit a bad tactic in science fiction, because I think the reader can feel the difference if they're reading fiction with no coherent framework behind what they can see.  The author should know how the aliens think.  (I'm similarly skeptical about the religious motif of things beyond mortal comprehension.)

The project wasn't meant to explore Chomskyan ideas because, to be brutally honest, I've never taken the universal grammar idea seriously enough even to try to refute it.  When I first read the technical papers in which Chomsky defined the Chomsky hierarchy (my first exposure to his work, as the hierarchy bears on programming-language parsing technology), I was turned off by the apparent suggestion that we have string rewriting engines in our heads; to me, a hypothesis both unnecessary and — because it felt, for lack of a better term, digital — implausible.  At any rate, there is no universal grammar consciously behind my conlangs; and, regardless of whether the universal grammar hypothesis is right or wrong, I doubt an attempt to explicitly address it would do anything for the project except bog things down.

Since the project aspires to naturalism, to my mind this requires at least one diachronic family tree of languages, recalling my earlier remark that plausible fiction has a coherent framework behind it.  The tree has to be sketched out before elaborating the languages in it (or they wouldn't be affected by it, defeating the purpose).  At the start of the project, though, I had no clue how to sketch out such a tree because I'd already merrily invalidated the basic classifications I knew of for human languages:  (1) neutral order of the basic sentence elements subject, object, and verb (VSO, SVO, etc.); in this project, a sentence doesn't have these elements; and  (2) alignment system, nominative ergative or whatever; but alignment is all about coordinating the arguments to a verb, and again, in this project a sentence has no such elements.

It seemed, then, that in order to learn the things I'd need to know to sketch out a family tree of these languages, I would have to have already constructed one, to learn how such languages can work in practice.  So the prototype language would be optimized for use as an exploratory vehicle, merrily disregarding naturalism unless, of course, in some particular instance a facet of naturalism were the thing being explored.  Conlangers are often advised to deliberately add irregularities to their languages for naturalistic feel, and from this advice I'd picked up the sense that naturalism would be the only reason for irregularity in a conlang; so I had the unconsidered expectation that the non-naturalistic prototype would have no irregularities.  I was gradually disabused of this expectation.  The prototype is unnaturally regular, though, so keep in mind that this isn't a design flaw.

Phonology and phonotactics

The phonology is the first of many areas of linguistics that the prototype language mostly doesn't explore (the better, hopefully, to focus on other areas).  The larger project design discusses phonetics and phonology extensively.  The conspeakers vocalize in pure tones; the phones (speech sounds) are notes, but the phonemes are the musical intervals from one note to the next (which meshes rather well, imho, with the vectorial/navigational mindset behind the languages).  The conspeakers, realizing they were somewhat isolated by the unpronounceability of their speech sounds to most species that speak with their mouths, constructed a standard orthophony for transdicting their speech into sequences of "oral phonemes", chosen to be manageable by most other species.  There's some good fun there, but in the prototype it would only get in the way.  The prototype phonology needs to be easily constructed and easy (for me) to pronounce, so not to discourage exploration.

I started out designing a thoroughly bland phonology.  For vowels I made a simple neutral choice:

	front	back
close	i	u
mid	e	o
open	a

I gave syllables the general form consonant-vowel-consonant, where the onset and coda would both be optional depending on context; the coda could only be a nasal — either n or m — and nasals would only be allowed in syllable codas.  The rhotic consonant r would be omitted.  These are simple generic choices.

At this point, though, it became clear that the phonology was apt to become so boring it would discourage use.  So I slipped in an experiment I'd been curious about, bearing no relation to the project at all except that it seemed to me to belong in a language that doesn't care about naturalism.  I'd wondered how well one could put together a phonology with neither plosives nor fricatives.

Unfortunately, since I was going for ease of pronunciation, and I'd already excluded onset-nasals and r, excluding plosives and fricatives left me with simply too few consonants to choose from.  I adopted three approximants — l j w, as in lore, yore, wore — but still had fewer onset consonants than vowels, which seemed wrong so I added in, after all, two unvoiced fricatives — f and s, as in fore, sore.  (Why unvoiced?  It felt right, phonaesthetically.)

	labial	labio- dental	alveolar	palatal	velar
nasal	m		n
fricative		f	s
approximant			l (lateral)	j	w (labialized)

The arrangement of five onsets and five vowels interacted with the artificial regularity of the language, to produce a great many features of the language coming in groups of five.  The high sonority also gives the language an odd, somewhat fluid phonaesthetic.

Eventually a plosive found its way into the language, by a circuitous route; but I'll get to that.

In theory, a phonotactic rule forbids two consecutive vowels in a word.  However, in some cases, two vowels with an approximant between them sound the same as if the vowels were adjacent — for example, ije sounds like ie — and if one of these vowel-consonant-vowel sequences occurs in a word, the consonant is elided when spelling the word.  So the word is constructed without consecutive vowel phonemes, but it's spelled with consecutive vowel letters.  Precisely:  if a front vowel (i or e) is followed by j and another vowel, or if a back vowel (u or o) is followed by w and another vowel, the consonant between those vowels is elided.  For example, lamlosuwo would be shortened to lamlosuo.  Why introduce these elision rules?  Because I found I was pronouncing the phoneme sequences that way anyhow, and it made the orthography (spelling) less uniform and therefore easier to get one's bearings in (like the bumps on the letters F and J on a qwerty keyboard, that help touch typists feel when their fingers are in the right place).

Vectors

All the conspeakers' content words are vectors, a single grammatical function alternative to grammatical nouns or verbs (hence, the entire phylum of languages are vector languages).  Each vector describes a sort of travel, so might be thought of as a variant on the verb to go.  To identify participants in the action of a vector, any given vector may recognize a series of available vector roles, in poetic similarity to noun cases of human natlangs.  (Imagine conspeaker linguists being frustrated to encounter a language, culturally distant from theirs, in which vectors don't have fixed sets of roles, and struggling to rescue their cherished theory of grammar.)

The prototype language has five roles:

	abbr	description
cursor	CUR	the thing that goes.
start	STR	from which it goes.
end	END	to which it goes.
path	PTH	by which it goes.
pivot	PIV	catch-all role; a participant not belonging to any of the other four.

Some roles of a given vector may be unoccupied, but there is always a cursor.

Enumerating the roles of a vector turns out to be a very good way of defining the vector.  My first vector definition was for a vector meaning roughly speak. 

cursor	what is said.
start	who says it.
end	who it is said to.
path	unoccupied.  (Several things might go here, but I've not yet chosen one.)
pivot	the language in which it is said.

A vector word has an invariant stem, and a mandatory class suffix.  A vector stem is two or more consonant-vowel syllables.  (Put the accent on the first syllable of the stem, btw.)  There are eleven classes — the neutral class, and ten genders.  The neutral suffix depends on the final vowel of the stem:  after a back vowel it's -wa, after a front or open vowel it's -ja (this is chosen so that the consonant on the neutral suffix is elided except when the stem ends with a).

An engendered vector is sort-of-like a noun.  The suffix has the form consonant-vowel, where the consonant determines one of the five roles to be emphasized — making it noun-like — and the vowel determines whether the occupant of that role is volitional or nonvolitional:  a back vowel for volitional, front vowel for nonvolitional.  I'll hold off on enumerating the gender suffixes for a moment, though, because they make much more sense after seeing the role particles, which I'm about to explain.

Role alignment

As one way to orchestrate a connection between consecutive vectors, the prototype specifies a role of each vector, at which they intersect (I imagined something vaguely like tinkertoy knobs, with a choice of sockets to plug into).  There's scope for some good fun in devising alternative ways that vector languages might connect consecutive vectors, but I figured this would do nicely to explore the vector-language concept.

I figured on inserting role particles between consecutive vectors to specify their connection.  I also figured a role particle would be a single consonant-vowel syllable, making these particles immediately distinguishable from vectors; but this presented a problem.  With five roles in each vector, there are twenty five ways to choose a role of the first vector and a role of the second vector; and there are only twenty five consonant-vowel syllables.  So one would have to use every possible syllable, and there would be some very dense way of packing the two role-choices into that one syllable (such as, the consonant determines the first role and the vowel determines the second), with no repeated patterns to aid memorization, and no redundant information to allow for transmission errors.  So instead of a single role particle, put two particles between each pair of vectors:  first a dominant role particle specifying a role of the first vector, then a subordinate role particle specifying a role of the second vector.  The consonant in a role particle indicates the role, and the vowel is back for dominant, front for subordinate.  The particles are easier to memorize, and the pairing of close or mid vowels with the consonants provides redundancy against transmission errors.  This arrangement also left available five possible role particles using the open vowel, so I made these combined role particles, indicating in a single particle that that role was being selected for both vectors.

	a  (open)	e  (front  mid)	i  (front   close)	o  (back  mid)	u (back  close)
l	la		li		lu		cursor
f	fa		fi		fu		start
s	sa	se		so			end
j	ja	je		jo			path
w	wa	we		wo			pivot
	comb.	subordinate		dominant

This table has changed a couple of times since creation.  Originally the start and end both used close vowels, which turned out to be a mistake because one really wants redundant contrasts between start and end.  Also, originally the path used a close vowel for the subordinate and mid for dominant, which had been naively intended to enhance redundant contrasts but instead turned out to be confusing since each of the other consonants used a predictable pair of vowels, and path seems to be, in practice, the least often used of the five roles.

Usually, aligning specified roles of two consecutive vectors means that the same participant occupies both roles; however, in general the meaning of the alignment is determined by role-alignment conventions of the dominant (i.e., first) vector.  In theory, the "usual" meaning of role alignment is simply the convention most vectors adopt.  Each vector has its own unique semantic "shape" that may call for non-generic role-alignment conventions.

For example, combining losua meaning speak with a second vector susua meaning sleep one could say

losua	fu	li	susua
NEUT   speak	DOM   STR	SUB   CUR	NEUT   sleep

Since the start of losua is the speaker, and the cursor of susua is the sleeper, and losua has generic role alignment, this means that some party speaks and sleeps.  One might ask whether the participant does these things simultaneously or sequentially; losua prefers to align sequentially (rather than in parallel), so the participant speaks and then sleeps.  (Note, in passing, that there would be no way in English to say this without a subject for the verbs, such as "someone", whereas our prototype sentence has no word corresponding to the subject.)

Combined particles turned out to be highly useful, but not for their original purpose.  In practice, it seems, one rarely wants to align the same role of two consecutive vectors.  However, occasionally it is necessary or convenient for a vector to connect with other vectors in a way that doesn't fit within the usual two-particle model.  Exactly because the combined particles aren't much needed for their regular function, they can be conveniently repurposed for irregular functions; and this has rapidly become a usual practice.  Just as a vector's pivot role and two-particle role-alignment conventions absorb its low-grade idiosyncrasies, its use of combined role particles absorbs medium-grade idiosyncrasies.

After some initial fumbling in the design, neutral vectors were also allowed to occur consecutively with no intervening particles.  The two vectors fuse semantically, so that they interact with the rest of the sentence as if they were a single vector.  The alignment preference of the dominant vector determines whether they fuse in parallel, a single act of travel that is both things at once; or in sequence, a single act of travel that is the first and then the second.  This serves two commonly wanted patterns:  the parallel case is essentially adverbial (advectorial), while the second supports compound navigational paths (as in the treasure-map metaphor).

Gender

The dominant and subordinate role particles are reused as gender suffixes — dominant for volitional genders, subordinate for nonvolitional genders — with one caveat.  The labio-dental fricative f has an allophone used only in start-gender suffixes:  the dental fricative, as in thin, written as t.  Use of this allophone provides redundant information to help filter out transmission errors, which is a solid justification for it; causally, I like the unvoiced dental fricative.

	NV	V
CUR	-li	-lu
STR	-ti	-tu
END	-se	-so
PTH	-je	-jo
PIV	-we	-wo

For example, here are the (usual) engendered forms of losua and susua.  Grammatically, of course, these aren't actually nouns, even though the following list describes the engendered participants:  grammatically they're vectors, so it's still possible to align with any of their non-engendered roles.

losuli	NV.CUR	message
losutu	V.STR	speaker
losuso	V.END	audience
losuo	V.PIV	living natural language
losue	NV.PIV	dead or artificial language

susulu	V.CUR	sleeper
susuti	NV.STR	falling asleep
sususo	V.END	waking
susuje	NV.PTH	sleeping
susue	NV.PIV	dreaming

Semantically, most vectors when engendered take on habitual aspect; so, for example, losutu is a sometime-speaker, rather than the speaker on a particular occasion.  Syntactically, if you are role-aligning on the engendered role of a vector, you can omit the role particle that says so.  Thus,

losutu   li   susua   V.STR   speak   SUB   CUR   NEUT   sleep

the sometime-speaker sleeps

losua   fu   susulu   NEUT   speak   DOM   STR   V.CUR   sleep

the sometime-sleeper speaks

losutu   susulu   V.STR   speak   V.CUR   sleep

the sometime-speaker (is a) sometime-sleeper

Prefixes

A vector can be modified by one or more prefixes of the form consonant-vowel-nasal.  To provide redundancy, I'd like to avoid using two prefixes that differ only by n-versus-m, leaving only twenty five possible prefixes; naturally, I'm trying to reserve them for elemental functions.  I revise the prefix set from time to time, as my ideas evolve about what is most useful.

An especially elemental, and stable, prefix is lam-, which has deictic effect, causing the vector to refer to the immediate situation.  This is notably used with engendered forms of losua:

lamlosuli	what is now being said (the utterance in which the word lamlosuli occurs).
lamlosutu	the party now speaking (first person).
lamlosuso	the party now being spoken to (second person).
lamlosuo	the language now being spoken.

It was rather cool to get the name of the conlang for free (choosing to assume it would be imported into English as a proper noun, so it would still mean the conlang when used in an English sentence); but lamlosutu and lamlosuso seemed excessively clumsy ways to express something as basic as the first and second persons.  Such clumsiness didn't match the exploratory mission of the language; so I posited there would be contractions for those words — latu for first person, laso for second.

laso   fi   losua   V.END   this   speech   SUB   STR     NEUT   speak

you speak

Subordinate content particles

As part of its exploratory mission, the prototype is meant to have a minimalist grammar.  The theory is that an exploratory design has to be changed, and then the revised version has to be relearned — and vocabulary is (says the theory) easier to change, and easier to relearn, than grammar.  In particular, I didn't want to conjugate vectors, because that weighs down the grammar.  How, then, to express something like past tense?

First I crafted a vector for the purpose:  silea, meaning age.  The cursor silelu would be the party who ages, start siletu the time they came from, etc.; but deictic lamsilea seemed so much more useful than silea itself that I figured in ordinary usage one would let the prefix be understood and simply say "siletu" for "the past", and so on.  (Notice how little irregularities are piling up?)

To relate an arbitrary sentence to this time-sense vector, I crafted a new set of grammatical words — subordinate content particles, each of which is just a single vowel.

Siletu a laso fi losua.

The subordinate content particle initiates a subclause, here laso fi losua, and then packages up that clause as if it were the occupant of the subordinate role in a role alignment.  The vowel in the content particle determines the mood of the subclause, here indicative.  The alignment with siletu is understood to specify location of the subclause (here, location in time) — so, "you spoke".  (Is this really a practical way to handle tense?  I don't claim to know; this is a game of gradual exploration.)

siletu   a   laso   fi   losua   V.STR   this   aging   INDIC       V.END   this   speech   SUB   STR     NEUT   speak

in the past: you speak

To assign mood to an entire sentence, simply place the appropriate-mood subordinate content particle at its start.  Using the invitational particle i,

i   laso   fi   losua   INVIT       V.END   this   speech   SUB   STR     NEUT   speak

please, you speak

When an invitational or imperative clause starts with laso which is then aligned with the agent of a neutral vector, the laso and its associated particle are usually left implicit, unless one wants to emphasize the second-person.  (Yes, this is very like English, where one says "please, speak" or "please, you speak"; although ordinarily one would avoid imitating English, here it's potentially interesting that some things aren't necessarily affected by the switch from verb-noun to vector grammar.)  Agents, and one or two other logical roles in a vector, pop up from time to time as the prototype develops; their use in the invitational/imperative elision convention wasn't a novelty.  The agent is a participant understood as causing the action, and if there is an agent it's usually either the cursor, the start, or the pivot.

I losua. — Please speak.
I losua so latu. — Please speak to me.
I losua wo lamlosuo. — Please speak in Lamlosuo.

Here's the complete set of subordinate content particles.

	front	back
close	i invitational	u  imperative
mid	e  noncommittal	o tentative
open	a indicative

Provectors

What if one wanted to say "please speak to me in Lamlosuo"?  The linear simple clause structure only allows aligning a vector with two others:  the one before it, and the one after it.  In our examples, the one before losua is the elided second person.  The one after it could be pivot lamlosuo or end latu.  We don't have any way to align all three with losua at once.

In my earliest sketch of the grammar, I provided for occasionally non-linear structure by means of a device called a recollective provector.  Provectors have a stem of the form vowel-nasal, and take a class suffix agreeing with their antecedent.

	front	back
close	in-  interrogative	um-  recollective
mid	en- indefinite	on- relative
open	an- demonstrative

The recollective provector um- refers to an antecedent that occurred earlier in the same clause.  What makes it recollective is that it doesn't align with its syntactic predecessor.

i   losua   so   latu   uma   wo   lamlosuo   INVIT       NEUT   speak     DOM   END     V.STR   this   speech   REC   NEUT     DOM   PIV     V.PIV   this   speech

please speak to me, that in Lamlosuo

From losua, one starts building a linear clause, but then stops when one discovers the next word is a recollective provector (losua so latu), goes back to the antecedent losua, and begins building another linear clause from there (losua wo lamlosuo). As mentioned, the recollective provector device was created early, in anticipation of later need.  Its actual use didn't begin to arise for some time, until the vocabulary became sufficiently diverse to support a significant number of sentences with more than three vectors in them.  So only then did it become apparent that there were two problems with the recollective provector.

Incorporation

The whole point of the vector-languages concept is that the conspeakers, in fluent speech, are liable to produce long chains of vectors.  Of course we've been translating small, simple English test sentences, so it's to be expected that our vector sentences don't have long simple clauses; but sooner or later, for the project to succeed, fluent vector speech will have to be demonstrated with long vector chains in it.  And both problems with recollective provectors, as originally designed, are related to long simple clauses.

The simpler problem is that in a long simple clause, we expect to find a number of neutral vectors — so that class agreement may be simply not adequate to identify the antecedent of a recollective provector.  This isn't too worrisome; it's a technical problem, but doesn't seem foundational.

There is a deeper problem, though.  Aware from the start that I would eventually have to learn to phrase things fluently — with long simple clauses — my initial plan was to concentrate on creating a language that would support fluent phrasing, and then see if I couldn't ease myself into using more fluent phrasing later on.  The above example, though — i losua so latu uma wo lamlosuo — suggests that the language I'd created might not be able to support long simple clauses:  that any complex sentence would have nonlinear structure requiring use of recollective provectors, and the recollective provectors would chop everything up into very short simple clauses (the longest simple clause in the example is one neutral vector surrounded by two engendered vectors, which might as well be SVO).

Where I'd originally meant to ease into fluent phrasing by means of the prototype, suddenly it looked needful to come up with an example of fluent vector phrasing independent of the prototype.  I've a story, second-hand, of a native German speaker discovering to his pleasure the English term coffee table book; there is something really very German about it (though in German such a thing would likely be one word, coffeetablebook), and one can see how it might strike a German speaker as a breath of air from home.  That is what I wanted:  a (metaphorical) coffee table book for vector speakers.

My test sentence:  "Over the river and through the woods to grandmother's house we go." It does seem rather navigational.  The basic structure (not worrying about specific vocabulary since that's not what we're exploring atm) might be

---lu   li   ---a   ---a   so   ---we   lu   ---tu   V.CUR   group   travel   SUB   CUR     NEUT   over     NEUT   through     DOM   END     NV.PIV   reside     DOM   CUR     V.STR   lineage

we go over-and-then-through to the residence of an ancestor

It seems unlikely the language would have a special vocabulary primitive for over-the-river, or for through-the-woods; more plausibly these would be formed by attaching pivots, respectively river and woods, to more generic primitives for go-over-something and go-through-something.  Extrapolating from the example, I conjecture that any time you have a long chain of vectors offering an opportunity for a long simple vector clause, it's likely that key elements of the chain are too specific to have vocabulary primitives.  And if the only way we have to attach modifiers is using a recollective provector, we're forced to either chop up the longer structure in order to splice in modifiers, or put all the modifiers at the end of the sentence.  Imho, putting all the modifiers at the end doesn't seem like a very navigational organization (although I think there may be some human languages that do weird stuff like that — anadew again).

This is a much narrower problem than the big, general problem addressed by recollective provectors, which are good for building almost arbitrarily complex sentences.  We just need to be able to glide over a few modifiers here and there without disrupting the simple clause structure; and for that I crafted a simple incorporation device.  Any simple clause can be fused into a single word by putting a dab of morphosyntactic glue between each pair of consecutive words; the entire word then behaves, toward the rest of the sentence, as its leading vector — as if a recollective provector had been used, but without disrupting the flow of the clause in which it occurs.  The dab of morphosyntactic glue should be something not found elsewhere; so I used a plosive — unvoiced alveolar, as in tore — pronounced as part of the onset of the following syllable, and written as an apostrophe (both to make its partitioning of the word visually prominent, and to distinguish it from the t allophone of f).

I losua'so'latu wo lamlosuo. — Please speak-to-me in Lamlosuo.

While we're at it, this also offers a possible solution to the problem of ambiguous recollective provectors.  Simply incorporate into the provector a repetition of the antecedent word; in our (admittedly trivial) example,

I losua so latu uma'losua wo lamlosuo. — please speak to me, that speaking in Lamlosuo

Abstractive power

each extensible language is surrounded by an envelope of possible extensions reachable by modest amounts of labor by unsophisticated users.

Thomas A. Standish, "Extensibility in Programming Language Design", SIGPLAN Notices 10 no. 7 (July 1975) [Special Issue on Programming Language Design], p. 20.

I said in an earlier post I should blog about abstractive power "eventually".  This is it.

This material is very much a work in progress.  Throughout this post I'll emphasize insight and intuition — but while the post starts out non-technical, it will get more mathematical by increments as it goes along.  The relation between the math and the insights works both ways:  insights into abstraction guide the mathematical development, and the mathematical development is pursued partly in hopes of eventual further insights into abstraction.  I also hope, by presenting the mathematical development in an intuitive form (as opposed to the much drier form in my 2008 techreport) to get insights into the mathematical development.  The post ends, as does the current state of the work, with an elementary test case to show feasibility.

Contents
The idea
The goal
There is no semantics
The second derivative of semantics
Recasting expressiveness
Abstractiveness
Test case

The idea

The extensible languages movement peaked around 1970, and was on its way out when Standish wrote the above.  Extensibility enthusiasts had hoped, frankly, that by means of language-extension mechanisms it would become possible for everyone to use a single base language and transform it into anything anyone needed for any particular purpose.  Standish was noting that the extension mechanisms primarily used by the movement — macro preprocessors and perhaps the ability to add new syntax rules — had a limited range, after which it became quite difficult to extend the language further.

Macro preprocessing, in particular, cannot easily be used to build a series of extensions, one on top of another, because as extension follows extension, the programmer is rapidly overcome by accumulating complexity.  In order to use a macro, you have to be able to see whatever underlying facility the macro uses.  Thus, to add a second layer of macros to a base language, you have to understand and account for the base language and all of its first layer of macros; to add a third layer of macros, you have to understand the base language, the first layer of macros, and the second layer of macros; and so on.  The visibility of the underlying layers also limits how different the extended language can be from the base language.

The extensibility movement was supplanted by the abstraction movement, which had a more semantic focus, and came to be dominated — at least for a while — by the Object-Oriented Paradigm.  Something of the spirit of the new movement is visible in this remark on lexical scoping from Steele and Sussman's 1978 The Art of the Interpreter; or, The Modularity Complex (p. 24):

What is interesting about this is that we can write procedures which construct other procedures.  This is not to be confused with the ability to construct S-expression representations of procedures; that ability is shared by all of the interpreters we have examined.  The ability to construct procedures was not available in the dynamically scoped interpreter.  In solving the violation of referential transparency we seem to have stumbled across a source of additional abstractive power.

Abstraction helps with the problem of accumulating complexity, because you can — at least, ideally — use an extension without having to worry about all the details of what underlies it.  There is still some accumulated complexity, though.  I noted this in my earlier blog post on types:

In mathematics, there may be several different views of things any one of which could be used as a foundation from which to build the others.  That's essentially perfect abstraction, in that from any one of these levels, you not only get to ignore what's under the hood, but you can't even tell whether there is anything under the hood.  Going from one level to the next leaves no residue of unhidden details: you could build B from A, C from B, and A from C, and you've really gotten back to A, not some flawed approximation of it that's either more complicated than the original, more brittle than the original, or both.

The central point of that blog post is that typing, which is evidently meant to help us manage complexity, can easily become itself a source of complexity.  The same danger applies to other tools we use to manage complexity; the tools become effectively part of the language, and are thus added complexity and subject to accumulation of further complexity.

Another four decades of experience (since Standish's post-mortem on the extensible languages movement) suggests that all programming languages have their own envelopes of reachable extensions.  However, some languages have much bigger, or smaller, envelopes than others.  What factors determine the size, and shape, of the envelope?  What, in particular, can a programming language designer do to maximize this envelope, and what are the implications of doing so?

As a useful metaphor, I call the breadth of a language's envelope its radius of abstraction.  Why "abstraction"?  Well, consider how the languages in this envelope are reached.  Starting from the base language, you incrementally modify the language by using facilities provided within the language.  That is, the new (extended) language is drawn out from the old (base) language, in which the new language had been latently present.  (Latin abs-, "out", and trahere, "pull/draw")  The terminology of layers of abstraction, in programming, goes back to the 1970s.  One also finds this use of abstraction in philosophy, for drawing out something latently present; here's a passage from Locke's 1689 An Essay Concerning Human Understanding (you may recognize this, as it's quoted at the front of the Wizard Book):

The acts of the mind, wherein it exerts its power over its simple ideas, are chiefly these three :  (1) Combining several simple ideas into one compound one ; and thus all complex ideas are made.  (2) The second is bringing two ideas, whether simple or complex, together, and setting them by one another, so as to take a view of them at once, without uniting them into one ; by which way it gets all its ideas of relations.  (3) The third is separating them from all other ideas that accompany them in their real existence : this is called abstraction : and thus all its general ideas are made.

Our programming-language use of the term abstraction does take a bit of getting used to, because we usually expect something abstracted to be smaller than what it was abstracted from.  The abstract of a paper is a short summary of it.  An abstract thought has left behind the details of concrete instances — though it seems the abstract thought may be somehow "bigger" than the more concrete thoughts from which it was drawn.  In our case, the extended language is probably equi-powerful with the base language, and therefore, even if some specific implementation details are hidden during extension, the two languages still feel as if they're the same size.  This is not really strange; recall Cantor's definition of an infinite set — a set whose elements can be put in one-to-one correspondence with those of a proper subset of itself.  Since we rarely work with finite languages, it shouldn't surprise us if we abstract from one language another language just as "big".

Ironically, though, the reason we're discussing this at all is that, despite our best efforts, the extended language is smaller than the base in the sense that its "envelope" of reachable extensions is smaller.  We'd really rather it weren't smaller.

What general principles govern radius of abstraction?  My first candidate is smoothness, a term I borrowed from M. D. McIlroy, one of the founders of the extensible languages movement.  I mean by it the property of a language that its abstractive facilities apply to the language in a free and uniform way.  This concept is also close kin to Strachey's first-class objects, and van Wijngaarden's orthogonality.  I proposed the following principle in my dissertation:

(Smoothness Conjecture)  Every roughness (violation of smoothness) in a language design ultimately bounds its radius of abstraction.

When a base language contains a defect of smoothness, I suggest, successive extensions magnify the defect, creating unbounded complexity that drags down the programmer.

The goal

The Smoothness Conjecture is a neat expression of a design priority shared by a number of programming language designers; but, looking at programming language designs over the decades, clearly many designers either don't share the priority, or don't agree on how to pursue it.

What, though, if we could develop a mathematical framework for studying the abstractive power of programming languages — a theory of abstraction.  One might then have an objective basis for discussing design principles such as the Smoothness Conjecture, that to date have always been largely a matter of taste.  I wouldn't expect the Smoothness Conjecture itself to be subject to formalization, let alone proof, at least not until the study of the subject reached quite a mature phase; but the Conjecture may inspire any number of more specific claims that could then be weighed objectively.

This, in my humble opinion, would be very cool and, as an added bonus, immensely useful.

It is not, however, a short-term goal.  For a ballpark estimate, say people have been pursuing abstractive power (under whatever name) since the founding of the extensible languages movement, circa 1960.  When I got into the game, it had already been going on for about three decades.  The more extreme OOP advocates were making claims for it that could have been lifted nearly verbatim from the more extreme extensibility advocates of two decades earlier, and by my assessment then (understandably unpopular with the OOP advocates) there was still more we didn't know than that we did.  I didn't expect to tie it all up quickly; but I'm still excited about the prospects, because every few years my thinking on it has moved (forward, I hope) slightly — and by my estimate of the difficulty, any progress at all is a very encouraging sign.

There is no semantics

Shortly after I started thinking on abstractive power, Matthias Felleisen's classic paper "On the Expressive Power of Programming Languages" was published (in the proceedings of ESOP '90), and I was encouraged by this evidence that I wasn't the only person in the world crazy enough to try to mathematize traditionally informal aspects of language design.  Felleisen's treatment has been quite a successful meme in the years since, and has some features of interest for abstraction theory — both features that apply to abstractive power, and features that offer insight because of why they don't apply to abstractive power.

Felleisen's expressiveness works roughly thus:  A programming language is a set of programs together with a partial mapping from programs to semantic values.  Language A can express language B if there is a simple way to rewrite B-programs as A-programs that preserves the overall pattern of semantics of programs — not only the semantic values of valid programs, but which programs are valid, i.e., halt and which are not valid/don't halt.  (In this case, the overall pattern of behavior is sufficiently captured by the pattern of halting/not-halting, so one might as well say there is just a single semantic value, or technically replace the "partial mapping from programs to semantic values" with a "subset of programs designated as halting".)

That is, A can express B when there exists a decidable function φ mapping each B-program p to an A-program φ(p) such that φ(p) halts iff p halts.  A can weakly express B when φ(p) halts if p halts (but not necessarily only if p halts).

How readily A can express B depends on how disruptively φ is allowed to rearrange the internal structure of p.  Felleisen's paper particularly focuses on the class of "macro", a.k.a. "polynomial", transformations φ, which correspond to Landin's notion of syntactic sugar.  Each syntactic operator σ in language B is replaced by a polynomial (a "macro", or "template") σ_φ in language A; thus,

φ(σ(e₁, ... e_n))  =  σ_φ(φ(e₁), ... φ(e_n))

When φ is of this form, one says A can macro-express B.

I described the criterion for A can express B as preserving the "overall pattern of semantics of programs".  I meant to suggest that this is more than each individual mapping p ↦ φ(p) preserving semantics; it involves preserving, across mapping φ, how the shape of program texts affects their semantics.  This preservation-of-shape is more apparent when considering macro-expressiveness, which demands similarities of program shape between p and φ(p), because this implies that the similarities and differences between φ(p₁) and φ(p₂) would be akin to the similarities and differences between p₁ and p₂; but it's not clear that polynomial/macro rewriting would be the only useful measure of similarity of program shape.  (Cf. Steele and Sussman's 1976 Lambda: The Ultimate Imperative.)  To explore more general aspects of expressiveness, one might parameterize the theory by what class of transformations are allowed.

In preparing for an analogous treatment of abstractiveness, the first thing to recognize is that while expressiveness views each program as inducing a semantic value, abstractiveness views each program as inducing a programming language.  When comparing two B-programs p₁ and p₂, we don't just ask whether they induce the same programming language, because they almost certainly do not.  Rather, we want to compare the induced programming languages to each other, probably using some measurement at least as sophisticated as expressiveness.

Consider what this means for the definition of programming language.  Picture a base language as the center of a web of languages connected by directed arrows —abstractions— each arrow labeled by a program text.  The whole thing is a sort of state machine, where the states are languages, the state transitions are abstractions, and the input "alphabet" is the set of program texts.  We could also integrate semantics into this model, by adding transitions labeled with reserved "observable" terms — and then there isn't really any need for the states of the machine at all.  Everything we could ever want to know about a given programming language is contained in the set of all possible sequences of labels on paths starting from that language; so we might as well define a language to be that set of sequences.  That is,

(D1)  A programming language over set of terms T is a set of sequences of terms P ⊆ T^* such that for all sequences of terms x and y, if xy ∈ P then x ∈ P.

This approach also appeals to the recognition that although computation theory tends to look only at computations that halt, a great many of our software processes are open-ended.

This purely syntactic, unbounded view of programming languages is foundational.  The expectation of halting — what one might call the terminal-semantic assumption — is ubiquitous:  the assumption, hardwired into one's core definitions, that a computation is meant to get an answer and stop.  Denotational semantics is a terminal-semantic model.  Theory of computation, and complexity theory, are founded on the terminal-semantic assumption.

To my mind, an essential difficulty with the terminal-semantic approach is that, patently, it prefers to disregard properties that relate to unbounded sequences of future developments.  Abstractive power is directly concerned with such sequences, but one suspects all computation really should take them into account, as most macroscopic software processes are interactive (in one or another sense) and open-ended rather than self-contained and merely producing a final result.  (Cf. Dina Goldin et al.)

The unbounded-syntax approach does not, of course, really "eliminate" semantics; but it does cause semantics to become a dependent concept, grounded in syntax.  For abstraction theory as I'm currently developing, semantics is a set of sequences of terms; in RAGs (from my master's thesis), semantics is a nonterminal symbol of a grammar.  (In a modern treatment of RAGs I'd be inclined to replace the term "metasyntax" with "co-semantics"; but I digress... sort-of.)

Note:  I've described RAGs in a later blog post, here.

The second derivative of semantics

The expressiveness of a programming language —what we ask φ to conserve when mapping B to A— is about the contours of the overall pattern of semantics of programs.  That is, it's about how variations in the text of a program change the semantics induced by the program; in short, expressiveness is the first derivative of semantics.

The abstractiveness of a programming language —which we will want conserved when we assert that one language is "as abstractively powerful" as another— is about how variations in the text of a program change the expressiveness of the language induced by the program.  Thus, as expressiveness looks at variations in semantics, and is in this sense the first derivative of semantics, abstractiveness looks at variations in expressiveness, and is thus the second derivative of semantics.

As I've set out to mathematize this, I've found the treatment becomes rather off-putting-ly elaborate (a trend I mean to minimize in this post).  I observe a lesser degree of the same effect even in Felleisen's paper, which was apparently trying to stick to just a few simple ideas and yet somehow got progressively harder to keep track of.  Some of this sort of thing is a natural result of breaking new ground:  appropriate simplifications may be recognized later.  I omitted one substantial complication from my description of Felleisen's treatment, that I suspect was simply a consequence of techniques he'd inherited from other purposes.  However, I've also introduced one new complication into expressiveness, namely parameterization by the class of transformations allowed — and I'm about to introduce a second complication, as I adapt Felleisen's treatment to my unbounded-syntax strategy.

Recasting expressiveness

In adapting expressiveness to the unbounded-syntax definition of programming language (D1), the first consideration is that a mapping φ between two languages of this sort has to respect the all-important prefix structure of the languages:

(D2)  For programming languages P and Q, a morphism from P to Q is a function φ : P → Q that preserves prefixes.

That is, for every xy ∈ P, there exists z such that φ(xy) = φ(x)z.  We write P/x for the language reached from language P by text sequence x ∈ P; and similarly, when φ : P → Q, we write φ/x for the corresponding morphism from P/x to Q/φ(x).  Thus,  P/x = { y | xy ∈ P }  and  φ(xy) = φ(x) (φ/x)(y).

As remarked earlier, we parameterize expressiveness relationships by the class of allowable morphisms.  We won't allow arbitrary classes of morphisms, though.

(D3)  A category (over programming languages with terms T) is a set C of morphisms between languages over T, closed under composition and including the identity morphism of each language over T.

For given terms T, some useful categories:

Any = category of all morphisms.
Map = category of morphisms that perform a term transformation uniformly, φ(t₁...t_n) = φ(t₁)...φ(t_n).
Macro = category of map morphisms whose term transformation is macro/polynomial.
Inc = category of inclusion morphisms, φ : P → Q with φ(x)=x
Id = category of identity morphisms, φ : P → P with φ(x)=x

Where Felleisen could avoid complicated semantic values by relying on halting behavior, we need a set of observable terms, O ⊆ T.

(D4)  Morphism φ : P → Q respects observables O if

• φ maps observables, and nothing else, into those same observables — that is, (φ/x)y=o iff y=o — and
• φ transforms each derived language into a language with exactly the same observables — that is, o∈(P/x) iff o∈(Q/φ(x)).

Morphism φ : P → Q weakly respects observables O if it satisfies all the conditions for respecting observables O except that o∈(P/x) implies o∈(Q/φ(x))  (rather than implication going both ways).

Obs_O = category of all morphisms that respect observables O
WObs_O = category of all morphisms that weakly respect observables O

Our basic expressiveness relation is then

(D5)  For category C and languages A and B,  A can C-express B for observables O if there exists φ : B → A with φ ∈ C ∩ Obs_O.

We say A is as C,O-expressive as B.  Weak C,O-expressiveness uses WObs_O in place of Obs_O.  Evidently, the as C,O-expressive as relation is transitive, as is its weak variant.  Expressiveness implies weak expressiveness (because Obs_O ⊆ WObs_O).

There is a simple theorem that the expressiveness relation is preserved if the category is made bigger, and if the set of observables is made smaller.  That is, if A is as C₁,O₁-expressive as B, category C₁⊆C₂, and observables O₂⊆O₁, then A is as C₂,O₂-expressive as B.

Note:  Although the notation here is simplified from the techreport, it still poorly handles the codomain of a derived morphism, producing such un-self-explanatory expressions as Q/φ(x).  Belatedly I see that by adopting for φ: P → Q the additional notation φ(P)=Q, one would have the more mnemonic φ/x : P/x → φ(P)/φ(x).

Abstractiveness

As expressiveness depends on φ : B → A preserving the semantic landscape of B, abstractiveness should depend on φ preserving the expressive landscape of B.  A semantic landscape for B arose from specifying a set of observables.  An expressive landscape for B arises from specifying a category of expressiveness morphisms by which to compare different languages B/x.

If it wasn't entirely certain what category to use when comparing expressiveness (hence the introduction of parameter C into the expressiveness relation, where Felleisen's treatment only looked at two choices of C), the choice of expressiveness category becomes much more obscure when considering abstractiveness.  Note in Standish's remark the phrase by modest amounts of labor; dmbarbour has remarked that multiple degrees of difficulty are of interest, and this suggests that no one choice of category will give us a full picture.  One might even imagine that a φ : B → A of one category would map expressive relations on B of a second category onto expressive relations on A of yet a third category.  The point is that, without prior experience with this mathematics, we have no clear notion which of the myriad imaginable relations we want to look at.  We hope that experience working with it may give us insight into what special case we really want, but meanwhile the endeavor seems to require a lot of parameters.  It would look rather silly to have an abstractiveness relation with, say, four parameters, so we redistribute the parameters by bundling the choice of expressive category with the language.

(D6)  A programming language with expressive structure over terms T is a pair A=〈S,C〉 of a programming language S over T with a category C over programming languages with terms T.

We call these expressive languages for short.  We may write seq(A) and cat(A) for the components of expressive language A.

For φ to preserve the expressive landscape from B to A is more involved than preserving the semantic landscape.  The expressive landscape of B=〈S,C〉 is a web of relations between languages derived from S.  Suppose g∈C with g : S/x → S/y.  Through φ : 〈S,C〉 → 〈R,D〉, derived languages S/x and S/y correspond to R/φ(x) and R/φ(y).  Moreover, we already have three morphisms between these four derived languages:

g : S/x → S/y
φ/x : S/x → R/φ(x)
φ/y : S/y → R/φ(y)

If only we had a fourth morphism h∈D with h : R/φ(x) → R/φ(y), we could ask these four morphisms to commute, h ∘ φ/x = φ/y ∘ g.

(D7)  For expressive languages P and Q,  a morphism from P to Q is a morphism φ : seq(P) → seq(Q) such that

• for all g ∈ cat(P) with g : seq(P)/x → seq(P)/y, there exists h ∈ cat(Q) with h ∘ φ/x = φ/y ∘ g, and
• for all x,y ∈ seq(P), if there is no g ∈ cat(P) with g : seq(P)/x → seq(P)/y, then there is no h ∈ cat(Q) with h : seq(Q)/φ(x) → seq(Q)/φ(y).

For category C and expressive languages A, B,  A can C-express B for observables O if there exists φ : B → A with φ ∈ C ∩ Obs_O.

Note:  I've corrected a typo in this definition:  the second condition read for all x,y ∈ seq(Q) rather than seq(P). (24 April 2014)

We say A is as C,O-abstractive as B; and weak C,O-abstractiveness uses WObs_O in place of Obs_O.  The as C,O-abstractive as relation (and its weak variant) is transitive, and is preserved by making C bigger or O smaller.  Abstractiveness implies weak abstractiveness (because, again, Obs_O ⊆ WObs_O).  The techreport proves several other rather generic theorems; for example, if A is as C,O-abstractive as B, and cat(A) respects observables O, then cat(B) respects observables O.

When the expressive languages get their expressive structure from the identity category, C,O-abstractiveness devolves to C,O-expressiveness.  That is, for all languages A and B, category C, and observables O,  〈A,Id〉 is as C,O-abstractive as 〈B,Id〉  iff  A is as C,O-expressive as B.

Test case

An obvious question at this point is, now that we've got this thing put together, does it work?  In the techreport, my sanity check was a test suite of toy languages, chosen to minimally capture the difference between a language in which local declarations are globally visible, and one in which local declarations can be private.  The wish list at the end of the techreport, of results to try for, was much more impressive — I targeted encapsulation of procedures; hygienic macros; fexprs; and strong typing — but the sanity check, as the only example thus far actually worked out in full detail, has some facets of interest.

In language L₀, records are declared with constant fields, and the fields can then be queried.  When a query occurs in a text sequence, the next text in the sequence reports the value contained in the queried field; these reports are the observable terms.  Language L_priv is identical except that individual fields may be declared "private"; private fields cannot be queried, though they can be used when specifying the value of another field in the same record.

It's easy to transform an L_priv text sequence into a valid L₀ sequence:  just remove all the "private" keywords from the field declarations.  This is a macro/polynomial transformation, and all the queries that worked in L_priv still work and give the same results in L₀.  Therefore, L₀ is weakly as Macro-expressive as L_priv.

Whether or not L₀ is as Macro-expressive as L_priv (without the "weakly" qualifier) depends on just how one sets up the languages.  Each query is a separate text in the sequence, and the only text that can follow a query is a report of the result from the query.  Expressiveness hinges on whether or not it is permissible to query a field that is not visible; and the reason this matters is that although strong expressiveness requires each derived language B/x map into a derived language A/φ(x) that has no extra observable terms, it does not require that there be no extra non-observable terms.  To see how this works, suppose u ∈ L_priv is a sequence of declarations, after which query q₁ is valid but q₂ attempts to query a private field.  Following u, the result of q₁ is r₁, and the result of q₂ would be r₂ if the field were made public.  Let v be the result of removing all "private" keywords from u.

In the techreport, a query is not permitted unless its target is visible.  Therefore, L_priv sequences include uq₁ and uq₁r₁, but not uq₂.  L₀ sequences include vq₁, vq₁r₁, vq₂, and vq₂r₂.  But expressiveness does not object to vq₂r₂ ∈ L₀ unless there is some x ∈ L_priv such that φ(x)=vq₂ but xr₂ ∉ L_priv.  Since there is no such x, the observable r₂ in vq₂r₂ causes no difficulty.  Although it is true that vq₂ ∈ L₀ even though uq₂ ∉ L_priv, this does not interfere with expressiveness because q₂ is not an observable.  The upshot is that in the techreport, L₀ is as Macro-expressive as L_priv.

Alternatively, one could allow queries regardless of whether they're valid; this is essentially a "dynamic typing" approach, where errors are detected lazily.  In that case, uq₂ ∈ L_priv; the allowance of the observable r₂ in L₀ is then a violation of strong expressiveness, and L₀ is not as Macro-expressive as L_priv (although it's still weakly as Macro-expressive).

What about Macro-abstractiveness?  Given the relative triviality of the languages, I chose to use weak category Inc for the expressive structure of the languages:  〈L₀,Inc〉 and 〈L_priv,Inc〉.  L₀ ⊆ L_priv, so using the inclusion morphism φ(x)=x from L₀ to L_priv, evidently 〈L_priv,Inc〉 is as Inc-abstractive as 〈L₀,Inc〉; and consequently, as a weaker result, 〈L_priv,Inc〉 is as Macro-abstractive as 〈L₀,Inc〉.

As for the other direction, we've already observed that L₀ is as Macro-expressive as L_priv, which is to say that 〈L₀,Id〉 is as Macro-abstractive as 〈L_priv,Id〉.  So if 〈L₀,Inc〉 isn't as Macro-abstractive as 〈L_priv,Inc〉, the difference has to be in the additional expressive structure.  This expressive structure gives us a g : L/x → L/y when, and only when, L/x ⊆ L/y.  Therefore, in order to establish (contrary to our intention) that 〈L₀,Inc〉 is as Macro-abstractive as 〈L_priv,Inc〉, we would have to demonstrate a Macro∩Obs_O morphism φ : L_priv → L₀ that preserves all of the subsetting relationships between derived languages in L_priv.

For example, the transformation remove-all-"private"-keywords, which gave us Macro-expressiveness, will not work for Macro-abstractiveness, because it washes out subsetting relationships.  Suppose u is a sequence of declarations in L_priv that contains some private fields, and v is the result of removing the "private" keywords from u.  Since v can be followed by some things that u cannot, L_priv/u is a proper subset of L_priv/v.  However, the remove-"private" transformation maps both of these languages into L₀/v, which evidently isn't a proper subset of itself; so remove-"private" doesn't preserve the expressive structure.

In fact, no Macro morphism will preserve the expressive structure.  Consider a particular private field declaration, call it d.  When d occurs within a record declaration in an L_priv sequence, it can affect later expansions of the sequence, through its use in defining other, non-private fields of the same record, changing the results of queries on those non-private fields.  The only thing that can affect later queries in L₀ is a field declaration; therefore, a Macro morphism φ must map d into one or more field declarations.  But if d is embedded in a record declaration that doesn't use it, it won't have any effect at all on later queries — and the only way that can be true in L₀ is if φ(d) doesn't declare any fields at all.  So there is no choice of φ that preserves the expressive structure (which is to say, the subsetting structure) in all cases.

So 〈L_priv,Inc〉 is strictly more Macro-abstractive than 〈L₀,Inc〉.

Explicit evaluation

...if you cannot say what you mean, you can never mean what you say.

— Centauri Minister of Intelligence, Babylon 5.

Ever since I started this blog, I've had in mind to devote a post to the relationship between the strong theory of vau-calculus and the no-go theorem of Mitchell Wand's 1998 paper The Theory of Fexprs is Trivial.  Some of my past attempts to explain this relationship have failed miserably, though, so before trying again I wanted some new insight into how to approach the explanation.  Following my mention of this issue in my recent post on bypassing no-go theorems, and some off-blog discussion it provoked, I'm going to take a stab at it.

The trouble has always been that while my result is very simple, and Wand's result is very simple, and both treatments use quite conventional mathematical techniques (playing the game strictly according to Hoyle), they're based on bewilderingly different conceptual frameworks.  There's not just one difference, but several, and if you try to explain any one of them, your audience is likely to get hung up on one or more of the others.

Here are some highlights of how these conceptual differences stack up; I'll look at things in more detail hereafter.

• Wand's paper assumes that the only equivalences of interest are those between source expressions; he acknowledges this explicitly in the paper.
• Wand's paper isn't really about fexprs — it's about computational reflection, as can be seen in the Observations and Conclusions section at the end of the paper.
• Wand's operational semantics has no terms that aren't source expressions.  This isn't a realistic depiction of fexprs as they occur in Lisp, but it is consistent with both his exclusive interest in the theory of source expressions and his interest in computational reflection.
• Wand's operational semantics uses implicit evaluation rather than explicit evaluation:  that is, to distinguish between an expression to be evaluated and an expression not to be evaluated, he uses special contexts marking expressions that aren't to be evaluated, rather than special contexts marking expressions that are to be evaluated.  From a purely mathematical standpoint, a rewriting system using implicit evaluation always has a trivial theory, while a rewriting system using explicit evaluation can have quite a strong theory.  However, Wand's conceptual commitments prevent him both from using explicit evaluation and from caring about its consequences.  He cannot use explicit evaluation because the explicit evaluation contexts would not be representable in source expressions, violating his prohibition against non-source terms.  And, even if such expressions were allowed, all of the nontrivial equivalences in the theory would involve non-source terms, so that all the equivalences Wand is interested in would still be trivial (though for a different technical reason).

The deceptively simple math

Suppose we want a term-rewriting system in which any source expression S may sometimes appear as data and other times appear as program code to be executed.  We can do this in either of two ways:  either use a special context to mark a subterm that isn't to be evaluated, or use a special context to mark a subterm that is to be evaluated.

What Wand calls contextual equivalence, and I call operational equivalence, is a binary relation on terms defined thus (up to unimportant differences between treatments):

T1 ≅ T2  iff for every context C and observable V,  C[T1] ↦* V  iff   C[T2] ↦* V

But this formal definition interacts differently with the two different approaches to marking whether S is to be evaluated.

Suppose we use a special context to mark a subterm that isn't to be evaluated.  I call this strategy implicit evaluation, because a subterm is implicitly to be evaluated unless we go out of our way to say otherwise.  This strategy would naturally occur to a traditional Lisp programmer, who is used to quotation.  If this special context is identified by an operator, likely we'd call it "quotation"; but whatever we call it, suppose Q is a context that marks its subterm as data.  This means, formally, that Q[S] is itself an observable, and that Q[S1] and Q[S2] are different observables unless S1 and S2 are syntactically identical.  It immediately follows, from our definition of operational equivalence, that no two source terms S1 and S2 can ever be operationally equivalent unless they are syntactically identical.  When you add all the trappings in Wand's paper, this trivialization of theory might look more complicated, but it still comes down to this:  if there's a context that converts arbitrary terms into irreducible observables, then the operational equivalence relation is trivial.

But suppose we use the second strategy, a special context to mark a subterm that is to be evaluated.  I call this strategy explicit evaluation because a subterm is only evaluated if it's immediately surrounded by a context that explicitly says to evaluate it.  Then the cause of Wand's trivialization of theory "simply" vanishes.  Except that the consequences aren't at all simple.  The operational equivalence relation is really measuring something different under explicit evaluation than it did under implicit evaluation (under explicit evaluation, source terms have trivial theory because they're irreducible, whereas under implicit evaluation they have trivial theory even though they aren't irreducible).  So now I'll go back to square one and build the mathematical machinery with more care.

Dramatis personae

In classical small-step operational semantics, we have a term set, and a number of binary relations on terms.

The term set includes both source expressions and the observable results of computations, and possibly also some terms that represent states of computation that are neither source expressions nor observables.

Six key properties that a binary relation on terms might have: 

• Reflexive:  T1 > T1
• Transitive:  if  T1 > T2  and  T2 > T3  then  T1 > T3
  The reflexive transitive closure ("zero or more steps") is written by suffixing "*" to the relation, as  T1 >* T2
• Commutative:  if  T1 > T2  then  T2 > T1
  A reflexive transitive commutative relation is called an equivalence.
• Compatible:  if  T1 > T2  then for all contexts C,  C[T1] > C[T2]
  A compatible equivalence is called a congruence.
• Church-Rosser:  If  T1 >* T2  and  T1 >* T3  then there exists T4 such that  T2 >* T4  and  T3 >* T4
• Deterministic:  For each T1, there is at most one T2 such that T1 > T2
  This is not usually a mathematically desirable property, because it interferes with other properties like compatibility.  However, determinism may be semantically desirable (i.e., we want a program to behave the same way each time it's run).

Four key binary relations in the small-step semantics of a programming language:

• Operational step, written  ↦
  A directed relation meant to "obviously" describe what programs in the language are supposed to do.  Because it's meant to be obviously right, it doesn't try to have nice mathematical properties like Church-Rosser-ness.  Expected to be deterministic and non-compatible.
• Calculus step, written  →
  A relation meant to have lots of nice mathematical properties, like the reduction step relation of lambda-calculus.  The calculus step is generally defined to be compatible, and if it isn't Church-Rosser, something's wrong.
• Calculus equality, written  =
  The reflexive transitive commutative closure of the calculus step (thus, the smallest equivalence relation containing the calculus step).
• Operational equivalence, written  ≅
  T1 ≅ T2  iff for every context C and observable V,  C[T1] ↦* V  iff   C[T2] ↦* V

The master theorems one wants to prove about these relations are

• completeness:
  ↦*  implies  →*
• Church-Rosser-ness:
  →  is Church-Rosser
• soundness:
  =  implies  ≅

(There's another "master theorem" we could include on this list, called standardization, but that really is way more infrastructure than we need here.)

Wand's operational semantics

The syntax of terms in Wand's semantics is:

T   ::=   x | (λx.T) | (TT) | (fexpr T) | (eval T)

That is, a term is either a variable, or a lambda-expression, or a combination, or a fexpr, or a call to eval.  Wand explained he didn't want to have two different binding constructs, one for ordinary procedures and one for fexprs.  Well, I didn't either; it's characteristic of our different approaches, though, that where Wand made his binding construct a constructor of applicatives (that evaluate their argument), and put a wrapper around it to cause the operand to be quoted, I made my binding construct a constructor of operatives (i.e., fexprs), and put a wrapper around it to cause the operand to be evaluated.

Wand has three rewriting rules: one for applying a λ-expression, one for applying a fexpr, and one for applying eval.  If we were being naive, we might try to define a calculus step like this:

((λx.T)V)   →   T[x ← V]
(fexpr V)T   →   (V encode(T))
(eval T)   →   decode(T)

Here, T is a term, and V is a value, that is, a term that's been reduced as much as it can be.  (Obscure point:  a value is a term that's irreducible by the operational step.  Don't worry about it.)

The encode/decode functions require some explanation.  The point of not evaluating certain subterms is to be able to use those unevaluated subterms as data.  So somehow you have to represent them in an accessible data form.  One way to do this would be to use a special quotation operator, and then have accessors that act on quoted expresions, like  (car (quote (T1 . T2))) → (quote T1).  However, when you're proving a no-go theorem, as Wand was doing, you want to minimize the assumptions you have to make to demonstrate the no-go result.  So Wand would naturally want to avoid introducing those extra operators, quote car and so on.  Instead, Wand used a Mogensen-Scott encoding, which, given an arbitrary term T, produces a term built up out of lambda-expressions that is not itself reducible at all but which can be queried to extract information about T.

Unfortunately this definition of a calculus step doesn't work, exactly because these rules assume → is compatible, and the whole point of Wand's exercise is that subterm rewriting isn't allowed in all contexts.  However, we can define the operational semantics step, which isn't compatible anyway.  For the deterministic operational step, we define an "evaluation context", which is a context that determines where the next redex (reducible expression) can occur.  We have

E   ::=   ⎕ | (ET) | ((λx.T)E) | (fexpr E) | (eval E)

That is, starting from the top of the syntax tree of a term, we can reduce a redex at the top of the tree, or we can descend into the operator of a combination, or into the operand of a λ-expression, or into the body of a fexpr, or into the operand of eval.  Using this, we can define the operational step.

E[((λx.T)V)]   ↦   E[T[x ← V]]
E[(fexpr V)T]   ↦   E[(V encode(T))]
E[(eval T)]   ↦   E[decode(T)]

Preprocessing as a cure for trivialization

Wand credited Albert Meyer for noting the trivialization effect.  Meyer, though, noted that quote-eval (as opposed to fexprs) need not cause trivialization.  (Meyer made this supplementary observation at least as early as 1986; see here, puzzle 3.)

The key to this non-trivialization by quotation is that quotation in traditional Lisp is a "special form", which is to say that the quotation operator, which identifies its argument as not to be evaluated, is fixed at compile-time (that is, before program evaluation begins).  So, given a Lisp source program, we can run a preprocessor over it and rewrite each quoted expression to avoid quoting more than a single symbol at a time.  (For example, one might rewrite  ($quote (+ 1 2))  as  (cons ($symbol-quote +) (cons 1 (cons 2 ()))), a style of rewriting that requires only quotation of individual symbols.)  And then the term-rewriting system doesn't have to have quotation in it at all (only, in the example, symbol-quotation, a much more restricted facility that would only trivialize the formal theory of individual symbols, not of arbitrary source expressions.)

Wand's Mogensen-Scott encoding is a similar transformation to this preprocessing of Lisp expresions using cons etc. (setting aside how the encoding treats variables, which is a whole other can of worms because lambda-calculus variables behave very differently from Lisp symbols).

However, the encoding in Wand's paper doesn't prevent trivialization, because it's used during term reduction.  Our Lisp preprocessor eliminated general quotation before term reduction ever started, so that general quotation didn't even have to be represented in the term syntax for the operational semantics.  If you wait until reduction has already started, it's too late for the encoding to matter to trivialization; you already have a trivializing context, and the encoding merely facilitates data access.

This however raises a curious possiblity:  what if we preprocessed Wand's language by encoding the arguments to all the operators?  Then, instead of encoding an operand when applying a fexpr to it, we decode an operand when applying a non-fexpr to it (or when evaluating it, a case that Wand already provides for — except that when evaluating a term, we would only decode the operators, not their operands, since we don't decode operands until we know they're to be evaluated).

One thing about this:  if we're going to decode an operand of a non-fexpr, we need to keep track of that by somehow changing the operator to indicate we've already done the decoding.  The simplest way to do this is to wrap non-fexprs (as my treatment does) instead of wrapping fexprs (as Wand's does).  There are other, clumsier ways to do it without altering Wand's syntax, but I'll go ahead and change the syntax.

T   ::=   x | (λx.T) | (TT) | (wrap T) | (eval T)

Notice the wrapper is now called wrap instead of fexpr, but the basic binding constructor of combiners is still called λ.  Actually, in my dissertation it's called vau rather than lambda (hence "vau-calculus"), but there's also an interesting point to be made by leaving it as λ (setting aside that unicode doesn't have a character for the way I write a lower-case vau).  It's just arbitrarily chosen syntax, after all... right?

Our evaluation contexts for the operational step change slightly because, beyond the switch from fexpr to wrap, we're now willing for the operational step to reduce an operand whenever the operator is a value, regardless of whether the operator is a fexpr.

E   ::=   ⎕ | (ET) | (VE) | (wrap E) | (eval E)

The operational step rules differ mainly in their treatment of encoding and decoding.  There is no encoding during reduction.  As for decoding, it is only partial.  We decode everything except the operands of combinations.  (Specifying this precisely would be tedious and contribute nothing to the discussion, but since that was already true of the encoding/decoding, we haven't specified it in the first place.)

E[((λx.T)V)]   ↦   E[T[x ← V]]
E[(wrap V)T]   ↦   E[(V partial-decode(T))]
E[(eval T)]   ↦   E[partial-decode(T)]

Note that the first rule, for applying a λ-expression to an operand, hasn't changed at all, even though a λ-expression is now an operative where in Wand's treatment it was an applicative.

Given a source program, before we set the operational step loose on the term, we preprocess the program by fully encoding it, and then partial-decoding it.  Hence the complete absence of encoding in the rules of the operational semantics.  This has the expected, but to me still rather stunning, effect that there is no longer any context in the rewriting system that has to be off-limits to rewriting.  We can therefore now define a valid compatible calculus step relation by simply removing the evaluation contexts from the operational step rules:

((λx.T)V)   →   T[x ← V]
(wrap V)T   →   (V partial-decode(T))
(eval T)   →   partial-decode(T)

I'll go only slightly out on a limb and say that all three master theorems probably hold for this arrangement — completeness, Church-Rosser-ness, and soundness.  (Completeness is obvious by construction.)  But what's really interesting here is that this arrangement both violates Wand's restriction on the term set and produces an equivalence relation that doesn't correspond to the one in his paper.

The term-set restriction is violated because source expressions, which Wand was studying exclusively, are now the things that are input to the preprocessor, and the preprocessor maps those source expressions into a proper subset of the terms in our semantics.  And the contextual equivalence on source expressions that Wand studied is concerned with these source expressions that don't even effectively belong to our term set at all, since they're mapped through the refractive lens of this encode/partial-decode preprocessor.  Yes, our ≅ is no longer a trivial equivalence — but Wand's notion of contextual equivalence of source expressons would require those source expressions to have interchangeable full encodings (in case they both appear as an operand to a fexpr), and that still won't happen unless the source expressions before preprocessing were syntactically identical.  The source-expression equivalence Wand was interested in is still trivial, and our non-trivial ≅ is simply not relevant under the treatment used in his paper.

One last thought about this preprocessed, pseudo-explicit-evaluation variant of Wand's semantics.  The first rule of the calculus step is the call-by-value β-rule.  So this calculus is (if I've not made a goof somewhere) a conservative extension of call-by-value lambda-calculus, and its equational theory includes all the equations in the theory of call-by-value lambda-calculus plus others.

Vau-calculus

Although my pseudo-explicit-evaluation variant of Wand's system does demonstrate some of the principles involved, the encoding/decoding, and the preprocessor, are obstacles to extracting clear insights from it.  Unlike Wand, I'm not trying to prove a no-go theorem; I'm showing that something can be done, so my interest lies in making it clear how to do it, and I'll happly introduce more syntax in order to avoid a complication such as Mogensen-Scott encoding, or preprocessing.

Instead of distinguishing data from to-be-evaluated expressions by means of a deep encoding (in which the entire term is transformed, from its root to its leaves), I simply introduce syntax for fully representing Lisp source expressions as data structures, entirely separate from the syntax for things like combinations and procedures (noting that procedures cannot be expressed by Lisp source expressons:  you write a source expression that would evaluate to a procedure, but until you commit to evaluating it, it's not a procedure but a structure built out of atomic data, symbols, pairs, and the empty list.)

S   ::=   d | ()
T   ::=   S | s | (T . T)

Here, d is any atomic datum (archetypically, a numeric constant), and s is any symbol (which is another kind of datum, and not to be confused with a variable which is not a source-code element at all).  I've separated out the atomic data and the empty list into a separate nonterminal S, mnemonic for "Self-evaluating", because these kinds of terms will be treated separately for purposes of evaluation.

All of the terms constructed by the above rules are data, by which I mean, they're irreducible observables; none of those terms can ever occur on the left side of a calculus step.  (Therefore, given the master theorems, the operational theory of those terms is trivial.)  There are just two syntactic contexts that can ever form a redex; I'll use nonterminal symbol A for these, mnemonic for "active":

S   ::=   d | ()
A   ::=   [eval T T] | [combine T T T]
T   ::=   S | s | (T . T) | A

The intent here (to be realized by calculus step rules) is that  [eval T1 T2]  represents scheduled evaluation of term T1 in environment T2, while  [combine T1 T2 T3]  represents scheduled calling of combiner T1 with parameters T2 in environment T3.

There's also one other class of syntax:  computational results that can't be represented by source code.  There are three kinds of these:  environments (which we will clearly need to support our evaluation rules), operatives, and applicatives.  We'll use "e" for environments and "O" for operatives.

O   ::=   [vau x.T] | ...
S   ::=   d | () | e | O
A   ::=   [eval T T] | [combine T T T]
T   ::=   x | S | s | (T . T) | [wrap T] | A

The syntactic form of operative expressions, O, is interesting in itself, and in fact even the inclusion of traditional λ-expressions (which is what you see there, although the operator is called "vau" instead of "λ") is worthy of discussion.  I figure those issues would distract from the focus of this post, though, so I'm deferring them for some future post.  [Those issues arise in a later post, here.]

Here, then, are the rules of the calculus step (omitting rules for forms of operatives that I haven't enumerated above).

[eval S e]   →   S
[eval s e]   →   lookup(s,e)     if lookup(s,e) is defined
[eval (T1 . T2) e]   →   [combine [eval T1 e] T2 e]
[eval [wrap T] e]   →   [wrap [eval T e]]
[combine [vau x.T] V e]   →   T[x ← V]
[combine [wrap T0] (T1 ... Tn) e]   →   [combine T0 ([eval T1 e] ... [eval Tn e]) e]

In the fully expounded vau-calculus, the additional forms of operatives do things like parsing the operand list, and invoking primitives (such as car, and of course $vau).

Under these rules, every redex —that is, every term that can occur on the left side of a calculus step rule— is either an eval or a combine:  reduction occurs only at points where it is explicitly scheduled via eval or combine; and if it is explicitly scheduled to occur at a point in the syntax tree, that reduction cannot be prevented by any surrounding context.

The calculus step rules are, in essence, the core logic of a Lisp interpreter.

This calculus allows us to make much more fluent statements about the evaluation-behavior of terms than mere operational equivalence.  We can say, for example, that two terms T1 and T2 would be indistingusihable if evaluated in any environment, no matter what that environment is (and even though T1 and T2 may not themselves be operationally equivalent).

For all environments e,   [eval T1 e] ≅ [eval T2 e]

Thanks to the definition of ≅, when we say  [eval T1 e] ≅ [eval T2 e], we mean

For all contexts C and observables V,   C[eval T1 e] →* V  iff  C[eval T2 e] →* V

This is evidently not the question Wand's treatment asks with its contextual equivalence.  However, we can also define Wand's relation in this framework.  Let e0 be a standard environment.  Then,

T1∼T2   iff   for all contexts C,  [eval C[T1] e0] ≅ [eval C[T2] e0]

Relation ∼ is Wand's contextual equivalence.  And, indeed, for all source expressions S1 and S2,  S1∼S2  iff  S1 and S2 are syntactically identical.

Finally, note what happens if we omit from this calculus all of the syntax for symbols and lists, along with its associated machinery (notably, eval and environments; the only change this makes to the remaining elements is that we drop the third operand to [combine ...]).

O   ::=   [vau x.T]
S   ::=   d | O
A   ::=   [combine T T]
T   ::=   x | S | A

[combine [vau x.T] V]   →   T[x ← V]

Do you recognize it?  You should.  It's the call-by-value lambda-calculus.

[edit: besides some minor typos here and there, this post had originally omitted the vau-calculus rule for combining an applicative, [combine [wrap T0] ...].