Tuesday, May 17, 2016

Path & Manner in Valaklwuuxa

How languages describe motion is a particularly interesting subfield of verbal lexicology. In some languages, verbs of motion are even a distinct morphological class. Most of my blog posts on conlanging & linguistics have focused so far on WSL, which has no verbs, and thus no verbs of motion, but since I just started blogging about Valaklwuuxa, which is practically nothing but verbs, this topic suddenly seems relevant!

Conlangery #14 discusses verbs of motion in some depth, but the short version is that there are two major semantic components to motion: the manner in which one moves, and the path or direction along which one does it. Different languages differ in which of these components they encode in verbs, and which they relegate to adverbs, adpositional phrases, or other mechanisms. Germanic languages, for example, tend to encode manner, while Romance languages tend to encode path instead. Since English is a Germanic language with a ton of Romance borrowings, we've got a bit of both- manner verbs like "walk" (go slowly by foot), run (go fast by foot), swim (go by water), drive (go by directing a machine), etc., and path verbs like "ascend" (go up), "traverse" (go across), and "enter" (go into). Russian, in comparison, has verb roots that describe manner, which combine with prefixes for path.

So, how does Valaklwuuxa do it?

Valaklwuuxa has several roots that act a lot like manner verbs. For example:

ketqenda - go slow
petqentqe - go fast
nbatqe - move under one's own power (i.e., for humans, walk; but also applies to flying birds, swimming fish, vehicles, etc.)
lande - drive or ride

But, it also has roots like <tak> "to go along/beside", and <wole> "to move around a circuit", which are clearly path verbs.

And, on a moment's reflection, it seems like there must be both kinds of verbs; when verbs are your only open lexical category, and there's only one preposition, and not many basic adverbs... there's really no choice but to encode both path and manner information in verbs.

There are, however, still ways to determine whether the language is primarily path- or manner-oriented, aside from just looking at a list of lexical entries.

In the case of <ketqenda> and <petqentqe>, while these verbs can be, and are, used to describe motion, they can also be used with a more generic attributive sense. The attributes "fast" and "slow" generally imply motion, but literal displacement over a distance is not always entailed. Thus, one can say, e.g., <xe-petqentqenk!> to mean "I am going quickly!", "I'm hurrying", or just "I am fast!" Similarly, the imperative <(dwu-)petqentqex!> can mean "hurry up!", or "go faster!", but it can also be used in a metaphorical sense similar to "think fast!"

Most of the time when <ketqenda> or <petqentqe> are used with reference to literal motion, they appear in a serial-verb construction with some other verb, as in

dwu-petqentqe takex!
dwu=petqentqe tak=ex
2sg=go.fast go.along=IMP.sg
"Go (along the path) quickly!"

Words like <nbatqe> and <lande>, despite being more prototypical motion-verbs, behave similarly. They are very rarely used as finite verbs by themselves. In fact, they will be used on their own, as the predicate of a clause, almost exclusively in contexts where they are implicitly serialized with another verb, which may not even be a motion verb- and which can radically change the meaning! For example, if someone asked

dwu-valesk?
dwu=val-esk
2sg=cook-2.3sg
"Did you cook it?"

you might answer with

xe-nbatqenk!
xe=nbatqe-nk
1sg=walk-1p
"Yes, I did it myself!"

which is an elliptical form of <xe-nbatqe valesk!> "I cooked it by myself!"

If you want to actually say that someone is walking somewhere, it would be very odd to just say, e.g., <nBale txe nbatqe-la> or <nbatqe txe nBale-la> for "Mary is walking", unless the fact that Mary is travelling has already been established in the discourse and you are just highlighting the fact that she is doing it by walking, as opposed to some other means.

From all this you might get the impression that perhaps "to walk" and "to drive" are just bad glosses, and <nbatqe> and <lande> aren't really motion verbs at all- but that's only half the story! For one thing, something like <xe-nbatqe takend>, assuming that "I" am a adult human, really does mean "I am walking along a path", not just "I am traversing a path by myself", perhaps by awkwardly rolling, or some other means. (If the subject were not an adult human, of course, the translation would change to reflect the "prototypical" mode of movement for whatever the subject is). The phrases <landekwe wole> and <wolekwe lande> are also used somewhat idiomatically to mean "to patrol a perimeter (in/on a vehicle)" or "to drive around a race track" (the first takes an object for the thing you are going around, while the second takes an object for the thing you are riding or driving); again, not "to circumnavigate with help".

Furthermore, while the bare roots are not used much by themselves, there are derived forms which are no longer "verbs of motion" themselves, but depend on the motive meaning of the basic manner verbs. Thus, we have words like <landegwel> (literally "to start travelling by vehicle"), which is used for things like "to set out", "to start the car", "to uncircle to wagons", etc.; and words like <vwenbatqe> (literally "to walk as much as possible"), which is used to mean "to have explored" (and the more derived form <vwenbatqweev> "to be out exploring")- not "to do everything yourself"!

Thus, even though Valaklwuuxa necessarily has motive roots for both path and manner, we can determine from usage patterns that it is in fact primarily a path-oriented language.

Saturday, May 14, 2016

Jelinek & Demers Were Wrong

But not about what everybody else thinks they're wrong about! No, I'm totally on board with whole "Straits Salish has no nouns" thing.

In Predicates and Pronominal Arguments in Straits Salish, Eloise Jelinek and Richard A. Demers make the following assertion:
[F]or a language to lack a noun/verb contrast, it must have only [pronouns] in A-positions (i.e. argument positions). Otherwise, if each root heads its own clause, there would be an infinite regress in argument structure.
This is further footnoted as follows:
We thank an anonymous reviewer for raising the question of whether there might be a language just like Straights Salish, except for having DetPs in A-positions. In such a language, the predicates of which the argumental DetP would be based would in turn have their own DetP argument structure, and so on ad infinitum.
But this is an obvious false dichotomy! Yes, there cannot be a language otherwise like Straits Salish that only allows DetP arguments, because that would lead to infinite regress. But who says that just because you decide to allow DetP arguments, that you must eliminate your base case? You can still use pronominal arguments, or just dropped arguments, to halt the recursion!

So, of course, I had to conlang this. Not creating a language just like Straits Salish (that would be boring!), but something that has all of the same relevant bits of morphosyntax, but also allows nesting determiner phrases as clause arguments. This is a project I've been thinking about for a good long while, but as I just mentioned the language in another post, I figured this would be a good time to finally blog about it.

The name of the language is given in that other post as "Valaklusha", but that's an English exonym- it's a close approximation of how the name should be pronounced in normal English orthography. The proper romanization of the language's endonym (it's name in itself) is "Valaklwuuxa". I do not promise to be at all consistent in which spelling I use at different times.

This name was inspired by Guugu Yimithirr, which essentially means "language that has yimi", where yimi is the Guugu Yimithirr word for "this". The meaning of yimi is totally irrelevant to the name of the language, but it's a distinctive word that that language has and its neighbors don't. The practice of naming based on some distinctive word occurs in many other languages, and that's what I did with Valaklwuuxa. That name essentially means "about saying lwuuxa", or "how one says lwuuxa" where lwuuxa is the word for "woman" (pronounced /ɬʷu:ʃa/; the whole name is /fa ɬak ɬʷu:ʃa/). If Valakluuxa had a bunch of neighbor languages, presumably their words for "woman" would be different. Extra-fictionally, this came about because I had a hard time deciding which option I liked best for the word for "woman" in the as-yet-unnamed language, so I picked one and told myself that all of its uncreated, theoretical close relative languages have all of the other versions that I didn't pick.

(Side note: While collecting my notes, I was reminded of Lila Sadkin's Tenata, which was presented at LCC2. Tenata and Valaklwuuxa have no real relation, except that Tenata is another language that erases the noun/verb distinction, but it's cool and you should check it out. Tenata is actually much more similar to WSL, which I've blogged about extensively.)

But enough of that! I can get back into interesting bits of lexical semantics later- on to the hard-hitting morphosyntax! I'm just gonna give a brief overview of the important parts here; if you want gory details, see the ever-evolving Google Doc documentation.

Like WSL, Valaklusha, despite being a proof-of-concept engelang, is not a minimal language- it has a lot of accidental complexities, because they are fun and make it more natural-looking. Many of these accidental complexities make it not much at all like a Salish language (which have their own collections of accidental complexities), except in this basic core structure:

The only open-class roots are basically verbs, divided into basic transitives and basic intransitives. There are proclitic pronouns used for subjects, when an explicit subject phrase is missing, and pronominal agreement suffixes for all other arguments. There is one preposition (maybe two, depending on how you analyze it), used to mark certain oblique arguments, and there are a few determiners. Additionally, there are a few basic adverbs, and "lexical suffixes", which is a very Salishan feature.

Verbs show polypersonal agreement with suffixes and hierarchical alignment with a 2p > 1p > 3/4p animacy hierarchy. Further gradations of animacy in non-discourse-participants are unnecessary, because the subject marking clitic (or lack thereof) tells you whether any explicit 3/4p argument is the subject or not. The 3rd person refers to proximate objects or people who are present or may be addressed, while 4th person refers to distal objects and people who are not present or who are otherwise excluded from a conversation. Verbs also take several valence-altering affixes, including passive, antipassive, inverse, and transitivizer suffixes, as well as applicative prefixes.

Aside from the subject clitics, there are no explicit pronouns that can stand as arguments on their own; Valaklusha is essentially obligatorily pro-drop. All other arguments are determiner phrases.

Brief aside for phonology & romanization
I'm about to start quoting actual morphemes from Valaklusha, and some readers may want to know how to actually read those. If you don't care, you can skip this bit.

The phonology is very not Salishan, but it has some fun features I've wanted to play with for a while- notably, clicks. Stops come in a voiced and unvoiced series: the usual p/t/k, b/d/g distinctions, and then a voiced glottal stop and an unvoiced pharyngeal, <g'> and <k'>. Yes, there are apostrophes, but they actually mean something sensible! There are two basic clicks: a dental/alveolar click <tq>, and a lateral click <lq>.
All stops and clicks can, however, be prenasalized, indicated by an n-digraph, for a total of 12 stop and 4 click phonemes. Voiced prenasalized stops, however, are only realized as stops pre-vocalically; in other positions, they become homorganic nasal continuants. There are no phonemic simple nasals, so this creates no risk of homophony.

There is only a single series of fricatives: <l> (/ɬ/, a lateral fricative), <x> (/ʃ/), <s> (/s/), <h> (/θ/), and <v> (/f/). The fricatives and clicks default to unvoiced, but gain voicing between two voiced sounds (i.e., intervocalically, or between a vowel and a voiced stop), in a sort of Old-Englishy way. I chose <v> rather than <f> for that labiodental fricative, however, just because I think it looks nicer.

The phonemic fricative inventory is very front-heavy, so to balance things out /k/ and /g/ undergo allophonic variation and become fricatives in intervocalic positions, thus providing some back-of-the-mouth fricative phones (even though they're not distinctive phonemes), one phonemic voicing distinction between fricative phones, and one unvoiced intervocalic phone.

There are three basic vowels, which come in rounded and unrounded pairs: <a> (/a/ ~ /ɑ/), <e> (/ɛ/ ~ /i/), and <u> (/ɯ/); and <wo> (/ɔ/ ~ /o/), <we> (/ø/ ~ /y/), and <wu> (/u/). The digraph <wo> was chosen instead of <wa> for the low rounded vowel just because I think that the average reader is more likely to remember to pronounce that correctly. The rounded vowels induce rounding-assimilation on preceding consonants and preceding hiatus vowels. This can induce mutation of previously-final vowels during affixation. Rounded vowels can occur in hiatus with each other (in which case the <w> is only written once, as in <lwuuxa>), but unrounded vowels can only occur individually. Identical vowels in hiatus (again, as in <lwuuxa>) are half-long.

There are a bunch of other phonotactic rules, but you only need to know those to make up new words; this should suffice for reading.

Back to morphosyntax

Determiner phrases are formed from an article or other determiner (e.g., demonstrative) followed by a relative or complement clause. Only subjects can be relativized, and relative clauses never contain subject proclitics- any explicit arguments are always objects or obliques. Complement clauses (with one exception) are distinguished from relatives by the presence of a subject clitic. In sentences with explicit subjects, where the subject marking clitic would otherwise be absent, the clitic <he=> is used, which can result in ambiguity in sentences that are conjugated for a 4th person argument.

The quotative determiner <lak> is used to introduce direct quoted speech as the argument of a verb; this determiner can never introduce a relative clause, and no additional clitics are required to mark the complement. Clauses introduced by <lak> can be used as core argument or obliques, without additional marking- thus the possibility that this might be analyzed as a preposition as well.

The language has only one unambiguous preposition (<va>), which is used before a determiner (other than the aforementioned <lak>) to mark obliques. Some verbs (like passivized transitives, or natural semantic ditransitives like "give") assign a specific role to at least one oblique argument, but extra oblique arguments can be added just about anywhere as long as they "make sense"- e.g., for time or locative expressions. If, for example, there were two obliques in a passive clause, one of which refers to a person and one of which refers to a building, nobody's going to be too terribly confused about which one is the demoted agent and which one is the locative.

Aside from subject clitics, any clause can have at most one explicit core argument. This is because the hierarchical alignment system cannot distinguish participants if there are two 3rd or 4th person arguments in the same clause; some languages are fine with this ambiguity, but the typical Salishan approach, copied here, is just to make it ungrammatical- if you need to talk about two 3rd or 4th person referents with explicit determiner clauses, you'll just have to find a way to re-arrange it.

The explicit marking on obliques means that oblique and core arguments can come in any order, and you are thus free to rearrange them in whatever way is most convenient- for example, to minimize center-embedding.

And it gets a whole lot more complicated with serial verb constructions, and tense and aspect and mood and so forth, but those are the bare essentials.

Now I think it's time for some examples!

First, some basics:

le-swetqe /ɬɛ.sʷyǀɛ/
le=swetqe-0
3sg.SUB=man-3sg
"He is a man."

le-nk'ap /ɬɛ.n͡ʡap/
le=nk'ap-0
3sg.SUB=coyote-3sg
"It is a coyote."

Here we have words for "man" and "coyote", but they are not nouns- by themselves, they are intransitive verbs, meaning "to be a man", and "to be a coyote". Also note that the third-person singular subject clitic does not distinguish gender, and the third-person singular intransitive conjugation is null.

le-tupund /ɬɛ.tɯ.pɯn/
le=tupund-0
3sg.SUB=hit.TRANS-3sg.3sg
"It hit(s) it"

Here we see the word for hit, which is transitive, but otherwise behaves identically to the words for "man" and "coyote"- they're all verbs.

tupund txe swetqe-la /tɯ.pɯn tʃɛ sʷy.ǀɛ.ɬa/
tupund-0 txe swetqe-0=la
hit.TRANS-3sg.3sg DEF man-3sg=ART
"The man hit(s) it" / "The hitter is the one who is a man"

Now we have relativized <swetqe> ("to be a man") with the definite article <txe> (ignore the <-la> bit for now- it's complicated). We can also switch this around to get

swetqe ta tupund-la (sʷy.ǀɛ ta tɯ.pɯn.ɬa)
swetqe-0 ta tupund-0=la
man-3sg IND hit-3sg.3sg=ART
"The/A man is a hitter."

which just further confirms that there is no morphosyntactic distinction between <swetqe> and <tupund>- either one can act as a predicate, and either one can act as an argument.

It certainly looks in both cases like that determiner phrase is acting like a non-pronominal argument, either of <tupund> or <swetqe>, especially since the subject clitics are missing! If we put the subject clitic back in along with an explicit determiner phrase, the meaning changes substantially:

le-tupund txe nk'ap-la /ɬɛ.tɯ.pɯn tʃɛ n͡ʡap.ɬa/
le=tupund-0 txe n'kap-0=la
3sg.SUB=hit.TRANS-3sg.3sg DEF coyote-0=ART
"He/it hit/is hitting the coyote."

But with some fiddling one could argue that perhaps there really is a null pronominal argument, and the relative clause isn't actually nested, but just adjacent... so let's go further!

swetqe txe tupund txe nk'ap-la /sʷy.ǀɛ tʃɛ tɯ.pɯn tʃɛ n͡ʡap.ɬa/
swetqe-0 txe tupund-0 txe nk'ap-0=la
man-3sg DEF hit.TRANS DEF coyote-3sg=ART
"The man hit(s) the coyote." / "The one who hit(s) the coyote is a man."

nk'ap txe tupundsa txe swetqe-la /n͡ʡap tʃɛ tɯ.pɯn.sa tʃɛ sʷy.ǀɛ.ɬa/
nk'ap-0 txe tupund-sa-0 txe swetqe-0=la
coyote-3sg DEF hit.TRANS-3sg.3sg DEF man-3sg=ART
"The coyote is/was hit by the man."

Note that we can't actually make <tupund> the main verb in this sentence, because then we'd have both <swetqe> and <nk'ap> left over to use as arguments, and we can't have two 3rd person core arguments in one clause. But here we can clearly see that, in either case, there must be an intransitive relative clause nested inside a transitive relative clause nested inside another intransitive matrix clause- finite, two-level deep recursive nesting, with no pronominal arguments and no noun/verb distinction!
The two determiner phrases can't both be arguments to the initial predicate both because we know that those predicates are intransitive and because we can't have more than one core argument in a clause, so either they are disconnected sentences talking about different things, which is ruled out by the known interpretation, or they are connected in some other way. Furthermore, we have evidence that the intransitive relative clauses must be nested as arguments inside the transitive relative clauses because changing their order radically changes the interpretation and is only marginally grammatical, if you treat the first part as a parenthetical aside with the first half of the sentence missing:

... (swetqe txe nk'ap-la) txe tupund
... (swetqe-0 txe nk'ap-0=la) txe tupund-0
... (man-3sg DEF coyote-3sg=ART) DEF hit.TRANS
"... (and the man is also a coyote), who hit it."

So, bam, take that, Jelinek and Demers. No nouns, DetPs in argument position, finite recursive depth. Booyah.

Stay tuned for more Fun With Valaklusha!

Friday, May 13, 2016

Thoughts on Designing an AI for Hnefatafl

Hnefatafl is an ancient Scandinavian board game part of a family of Tafl games played on varying board sizes and with slightly different rules for win conditions. The unifying thread of Tafl games is that they are played on odd-numbered square boards (between 7x7 and 19x19) with radially symmetric layouts, and feature asymmetric sides- one side has a king, whose goal it is to escape, starting in the center, while the other side has undifferentiated pieces arranged around the edge who goal is to capture the king, and about twice as many of them.

I like playing Hnefatafl, but not a whole lot other people do these days; given the difficulty of finding good partners, I'd like to write an AI for it. This is not something I have done yet, so I'm not sure how well it will actually work, but these are my pre-programming musings on how I might want to approach it:

The basic ground-level approach to game AI is minimax search- you calculate every board position that you can get to from where you are, and every board position your opponent can get to from those positions, and so on, as deep as you can, and then you use some heuristic to figure out which of the resulting positions are "best" (max) for you and "worst" (min) for your opponent, and take the move that has the greatest probability of taking you to good positions later.

All of the pieces in Hnefatafl move like rooks; combined with the large board, this gives the game an extremely large branching factor; i.e., the number of possible positions you can get to in a small number of moves gets very, very big. This makes minimax game trees very difficult to calculate to any useful depth, because it just takes too long and uses too much memory. One simple optimization is to remember states that you've seen before, and what the best move was. Then, whenever you find a state you recognize, you can stop looking deeper, saving time and memory. This works best across multiple games, with the AI learning more states and getting better each time. It only really works well, though, if you can expect to come across repeated board states on a regular basis- something which becomes very unlikely when the total number of possible states is very, very large, as it is for large Tafl boards.

Fortunately, we can exploit symmetries to reduce the number of board states 8-fold: each position can be rotated into 4 orientations, and reflected, and the strategic situation remains the same. If we can define a criterion for choosing a canonical representation for any of these sets of 8 board states, then every time we generate a new possible move, we can put it in canonical form to compare against a database of remembered states and best moves from those states, and we just have to keep track of 3 bits of additional information to remember how to transform the board between internal representation and presentation, so that the board doesn't flip and rotate on-screen in case the states preceding and following a move have different canonical orientations.

Unfortunately, the space of board states is still huge. For a 13x13 board (my personal favorite), there are something the ballpark of 6x10^77 distinct board states, after accounting for symmetry. Some board states are enormously more likely than others, but even so, with such a large search space, the probability of coming across repeated states between multiple games after the first few moves is extremely low, making a database of previously-accumulated "good move" knowledge of marginal utility. So, we need to do better.

As do many board games, Hnefatafl gives rise to a large number of recognizable patterns that take up only a small part of the board, but disproportionately control the strategic situation. Trying to recognize entire boards is kind of dumb, because even if you have figured out the best move from one position already, that will be useless if you later come across a strategically-identical position that happens to one inconsequential piece misplaced by one square. If the AI can recognize parts of boards as conforming to familiar patterns, however, there is less important stuff to memorize, and the memorized knowledge is much more generalizable.

So, how do we recognize patterns? Some patterns involve specific configurations of pieces in specific relative positions, while others just involve having a certain number of pieces that can attack a particular position, regardless of how exactly they are spaced out along a row or a column. To capture both kinds of information, we'll want to keep track of the pieces arranged in a small segment of the board, as well as a count of how many pieces (and of which type) are on each row and column leading out of that section. In my experience, a 4x4 square should be large enough to capture most common and important patterns. Using a 4x4 square means some duplication of storage for smaller patterns, but we can still make use of symmetry to reduce storage requirements and branching factors. There are generally three types of pieces (attackers, defenders, and the king), and generally three types of squares which may have different movement rules associated (normal squares, the king's throne in the center, and goal squares where the king escapes).
Given restrictions on how throne and goal squares can be positioned relative to each other, and the fact there can only ever be one king, there are somewhere between 5380841 and can be positioned relative to goal squares, which reduces the total a good bit, there are something like 3.6x10^11 canonical 4x4 squares. The upper end of that range is still pretty huge, but without doing the detailed calculation, I suspect the exact number is much closer to the lower end. Given that some positions are still much more likely than others, this looks like a range where we can actually expect to come across repeats fairly often, without having to store an impractically large amount of data. Additionally, with this method it becomes possible to share strategic memory across multiple different Tafl variations!

Adding in row-and-column counts of course increases the number of variations; storing the maximum amount of information on row and column dispositions would increase the number of specific varieties by about 3^9 per row and column, plus 11 positions for a square vertically or horizontally, or a total factor of about 25548534 for 4x4 squares on a 13x13 board; smaller boards, of course, would use smaller subsets of that total set.

I'm not sure what the probability distribution of those extra states is, exactly; I suspect that they will be clustered, in which case the large total space is not a huge deal, but we can also probably get fairly good performance with a simplified model, which simply stores which side, if any, controls a particular row or column, and how many pieces that side has on that row or column before you reach an enemy or the edge. Just storing which side has control might give useful performance, which only multiplies the memory space by a factor of 24 regardless of board size (one or the other side or nobody for each of 8 perimeter spaces) but my intuition about the game says that storing counts is actually important. It may take experimenting to see if it's really worth fragmenting the pattern memory in this way.

In any case, this general approach won't capture every strategically-important pattern, but it will get most of them. A few large-scale patterns, like building walls across the board, could be hand-coded, but they might end up being automatically recognized as advantageous just due to the positive influence of many overlapping small sections that are individually recognized as advantageous.

Now, we can use the database of board sections both to evaluate the strength of a particular position without having to search deeper to find out how it turns out in the end, and to remember the best move from a particular familiar position without having to calculate all possible moves or recognize entire boards.

For evaluating positions, pattern segments can be assigned weights depending on their prevalence and proximity to wins and losses- when the AI wins, it can examine all patterns in the series of states for that game, and assign positive values to them, and vice-versa when it loses.

To pick good moves, it should be possible to prove just by looking at a small section of the board that moving certain pieces will always result in a worse position, or always result in a better position, and thus minimize the number of possible moves that need to be calculated to pick that actual best.

Language Without the Clause

Having been playing for a while with WSL (which has no verbs) and Valaklusha, which I have not yet blogged about, which has no nouns, I had a realization that there are some linguistic concepts even more fundamental than the noun/verb distinction which are nevertheless still not essential to communication.

In particular, every language I have ever heard of has something that can be reasonably called a clause (some syntactic structure which describes a particular event, state, or relation) which is usually (though not always) recursively nestable with other clauses to make more complex sentences.

Predicate logic, however, does not have to be analyzed in terms of nicely-bounded clauses in the linguistic sense. (There are things in logic called "clauses", but they're not the same thing.) Predicates describing the completely independent referents of completely independent linguistic clauses can be mixed together in any order you like with no loss of meaning, due to the availability of an effectively infinite number of possible logical variables that you can use to keep things straight. In fact, we can not only get rid of clauses- we can get rid of recursive phrase structure entirely.

There are, of course, practical problems with trying to use an infinite set of possible pronouns in a speakable language. If there weren't, creating good loglangs wouldn't be hard! But even with a relatively small finite set of pronouns representing logical variables, it's possible to create unambiguous logical structures that overlap elements from what would normally be multiple clauses. Thus, we could come up with a language which, rather than using recursive nesting, uses linear overlapping, with no clear boundaries that be used to delimit specific clauses.

After thinking of that, I realized that Gary Shannon's languages Soaloa and Pop are examples of exactly that kind of language, although (as described on that page) they do have an analysis in terms of nested clauses. Eliminating the possibility of a clausal analysis requires something a little more flexible.

A better example is Jeffrey Henning's Fith. It works completely differently from Pop- which should not be surprising! It would be quite surprising to discover that there are only two ways of structuring information, using clauses and not-using-clauses, but that's not how it is. This is not a dichotomy, which means there is a huge unexplored vista of untapped conlanging potential in the organizational territory outside of recursive clause structure land.

Fith is inspired by the programming language FORTH, and is supposed to be spoken by aliens who have a mental memory stack. Some words (nouns) add concepts to the stack, and other words (verbs and such) manipulate the items already on the stack and replace them with new, more complex concepts. If that were all, Fith would look like a simple head-final language, and the stack would be irrelevant- but that is not all! There are also words, called "stack conjunctions" or "stack operators", which duplicate or rearrange (or both) the items already on the stack. Because it can duplicate items on the mental stack, Fith has no need for pronouns, and every separate mention of a common noun can be assumed to refer to a different instance of it- if you meant the same one, you'd just duplicate the existing reference! But more importantly, the existence of stack operators means that components of completely independent semantic structures can be nearly-arbitrarily interleaved, as long as you are willing to put in the effort to use the right sequence of stack operators to put the right arguments in place for each verb when it comes. One can write a phrase-structure grammar that describes all syntactically valid Fith utterances... but it's meaningless. Surface syntax bears no significant relation to semantics at all, beyond some simple linear ordering constraints.

In fact, Fith is a perfect loglang- it can describe arbitrarily complex predicate-argument structures with no ambiguity, and it doesn't even require an arbitrary number of logical variables to do it! Unfortunately, it's also unusable by humans; Fith doesn't eliminate memory constraints, it just trades off remembering arbitrarily-bound pronouns with keeping track of indexes in a mental stack, which is arguably harder. Incidentally, this works for exactly the same reason that combinator calculus eliminates variables in equivalent lambda calculus expressions.

(Side note: the stack concept is not actually necessary for evaluating Fith or combinator calculus- it's just the most straightforward implementation. Some of Lojban's argument-structure manipulating particles actually have semantics indistinguishable from some stack operators, but Lojban grammar never references a stack!)

Having identified two varieties of languages that eschew traditional clauses, here's a sketch of a framework for a third kind of clauseless language:

The basic parts of speech are Pronouns, Common Verbs, Proper Verbs, and Quantifiers; you can throw in things like discourse particles as well, but they're irrelevant to the basic structure. This could be elaborated on in many ways.

Pronouns act like logical variables, but with a twist: just like English has different pronouns for masculine, feminine, and non-human things ("he", "she", and "it"), these pronouns are not arbitrarily assigned, but rather restricted to refer to things in a particular semantic domain, thus making them easier to keep track of when you have a whole lot of them in play in a single discourse. Unlike English pronouns, however, you'd have a lot of them, like Bantu languages have a large number of grammatical genders, or like many languages have a large number of classifiers for counting different kinds of things. In this way, they overlap a bit with the function of English common nouns as well.
In order to allow talking about more than one of a certain kind of thing at the same time, one could introduce things like proximal/distal distinctions.

Verbs correspond to logical predicates, and take pronouns as arguments with variable arity. There might be a tiny bit of phrase structure here, but at least it would be flat, not recursively nestable- and one could treat pronouns as inflections to eliminate phrase structure entirely.
These aren't quite like normal verbs, though- they do cover all of the normal functions of verbs, but also (since they correspond to logical predicates) the functions of nouns and adjectives, and some adverbs. Essentially, they further constrain the identity of the referents of the pronouns that they take as arguments, beyond the lexical semantic restrictions on the pronouns themselves. Common verbs are sort of like common nouns- they restrict the referents of their arguments to members of a certain generic class. Proper verbs, on the other hand, restrict at least one of their arguments to refer to exactly one well-known thing.

Quantifiers re-bind pronouns to new logical variables. They cover the functional range of articles, quantifiers, and pronouns in English. The simplest way for quantifiers to work would be a one-to-one mapping of predicate logic syntax, where you just have a quantifier word combined with a pronoun (or list of pronouns) that it binds. A bit more interesting, however, might be requiring quantifiers to attach to verbs, implicitly re-binding the arguments of the modified verb to the referents which are the participants in the event described by the verb. If that is not done, it might be useful to have "restrictive" vs. "non-restrictive" inflections of verbs, where restrictive verbs limit the domain of the binding quantifiers for their arguments, and non-restrictive verbs merely provide extra information without more precisely identifying (like English restrictive vs. non-restrictive relative clauses).

For very simple sentences, this wouldn't look too weird, except for the pre-amble where you quantify whatever pronouns you intend to use first. But the first thing to notice is that, just like in predicate logic, there is no need for all of the verbs describing the same referent to be adjacent to each other. A sentence in English which has two adjectives describing two nouns could be translated with the translation-equivalent of the nouns all at the front and the translation-equivalent of the adjectives all at the end, with the translation-equivalent of the verb in between. But hey, if you have a lot of agreement morphology, normal languages can sometimes get away with similar things already; although it's not common, separating adjectives from nouns can occur in, e.g., Russian.

Where it gets really weird is when you try to translate a complex sentence or discourse with multiple clauses.
When multiple English clauses share at least one referent, this relation is not indicated by nesting sentences within each other, or conjoining them in series, but by stringing on more verbs to the end, re-using the same pronouns as many times as you like. Occasionally, you stick in another quantifier when you need to introduce a new referent to the discussion, possibly discarding one that is no longer relevant. But, since this can be done re-binding one pronoun at a time while leaving others intact, the discourse can thus blend continuously from one topic into another, each one linked together by the overlap of participants that they have in common, with no clear boundaries between clauses or sentences. If you were very careful about your selection of pronouns, and made sure you had two non-conflicting sets, you could even arbitrarily interleave the components of two totally unrelated sentences without ambiguity!

Note that this does not describe a perfect loglang- the semantic structures it can unambiguously encode are different from those accessible to a language with tree-structured, recursively nested syntax, but they are still limited, due to the finite number of pronouns available at any one time. This has the same effect on limiting predicate logic as limiting the maximum stack depth does in Fith.

When discussing this idea on the CONLANG-L mailing list, some commenters thought that, like Fith, this style of language sounded incredibly difficult to process. But, I am not so certain of that. It definitely has pathological corner cases, like interleaving sentences, but then, so does English- witness garden path sentences, and the horrors of center embedding (technically "grammatical" to arbitrary depth, but severely limited in practice). Actual, cognitively-limited, users would not be obligated to make use of every structure that is theoretically grammatical! And even in the case of interleaved sentences, the ability of humans to do things like distinguishing multiple simultaneous voices, or separate note trains of different frequencies, makes me think it might just be possible to handle, with sufficient practice. Siva Kalyan compared the extremely free word order to hard-to-process Latin poetry, but Ray Brown (although disagreeing that my system sounded much at all like Latin poetry) had this to say on processability:
If it really is like Latin poetry then it certainly is not going to be beyond humans to process in real-time. In the world of the Romans, literature was essentially declaimed and heard. If a poet could not be understood in real-time as the poem was being declaimed, then that poet's work would be no good. It was a world with no printing; every of a work had to be done by hand. Whether silent reading ever occurred is debatable. If you you had the dosh to afford expensive manuscripts, you would have an educated slave reading them to you. What was heard had to be processed in real-time. The fact that modern anglophones, speaking a language that is poor in morphology and has to rely to a large extent on fairly strict word-order, find Latin verse difficult to process in real time is beside the point. Those brought up with it would certainly do so.
And being myself a second-language speaker of Russian, I have to say I am fairly optimistic about the ability of the human mind to deal with extremely free word-order. If I, a native Anglophone, can handle Russian without serious difficulty, I see no reason why the human mind should not be able to handle something even less constrained, especially if it is learned natively. Furthermore, if I think of pronouns like verb agreement inflections in a somewhat-more-complicated-than-usual switch-reference system, where the quantifiers act like switch-reference markers, then it starts to feel totally doable.

There are several devices speakers could use to reduce the load on listeners, like repeating restrictive verbs every once in a while to remind listeners of the current referents of the relevant pronouns. This wouldn't affect the literal meaning of the discourse at all, but would reduce memory load. This is the kind of thing humans do anyway, when disambiguating English pronouns starts to get too complicated.

This system also allows "floating" in the style of Fith, where one binds a pronoun and then just never actually uses it; unlike Fith, though, if the class of pronouns is small enough, it would quickly become obvious that you were intentionally avoiding using one of them, which should make the argument-floating effect more obvious to psychologically-human-like listeners.

Now, to be clear, what I have described thus far is not really a sketch for one single language, but rather a sketch for a general structure that could be instantiated in numerous different ways, in numerous different languages. As mentioned above, pronouns could exist as separate words, or as verb inflections. The components that I've packaged into Pronouns, Quantifiers, and Verbs could be broken up and re-packaged in slightly different ways, cutting up the syntactic classes into different shapes while still maintaining the overall clauseless structure. One could introduce an additional class of "common nouns" which mostly behave like pronouns, and represent logical variables, but have more precise semantics like verbs. This is potentially very fertile ground for developing a whole family of xenolangs with as much variation in them as we find between clause-full human natlangs! And I am feeling fairly confident that a lot of them would end up as something which, sort of like WSL, is still comprehensible by humans even if it could never arise as a human language naturally.

Friday, May 6, 2016

A Programming Language for Magic

Or, The Structure and Interpretation of Demonic Incantations, Part II.

As previously mentioned, a great deal of the training for a magician in the animist, demon-magic world consists of developing the mental discipline to compose precise and unambiguous instructions. Natural human languages are terrible at both precision and disambiguation; legalese is a direct result of this fact, and it still fails. In order to summon demons safely, therefore, a specialized formal language will be required- a programming (or "incantation") language.

Many people criticize FORTH and related languages for being hard to follow when data is passed implicitly on the program stack, but that's not an indictment of the concatenative style- it's an indictment of point-free (or, less charitably "pointless") style; i.e., the avoidance of explicit variable names. Concatenative programs can use explicit variables for convenience, and applicative languages can be written in point-free style as well. This is in fact quite common in Haskell and various LISPs, though the syntax of most mainstream languages makes it less convenient.

Despite both being called "languages", programming languages aren't much like human languages. That is, after all, why we need them- because human languages don't do the job. Conversely, programming languages tend to not play nice with humans' natural language abilities. Nobody likes trying to speak a programming language, or even to write fluently in one. When working out ideas on a whiteboard, or describing an algorithm in a paper, real-world programmers and computer scientists frequently avoid real programming languages and fall back on intuitive "pseudo-code" which sacrifices rigor in exchange for more easily communicating the essential ideas to other humans (or themselves 10 minutes later!), with careful translation into correct, computer-interpretable code coming later.

Now, magicians could work in a similar way, and it makes sense that they frequently would: laboriously working out correct spells in a written incantation language ahead of time, and then executing them by summoning a demon with the simple instruction "perform the task described on this paper". One can even go farther and imagine that, given the effort involved in creating such a spell, that they might be compiled into books for frequent re-use, stored in a university library, such that from then on magicians could execute common useful spells by instructing a demon to, e.g., "execute the incantation on page 312 of volume 3 of the Standard Encyclopedia of Spells as stored on shelf 4A of the Unseen University Library".

But, this is not a universal solution. For many simple spells, the description of where to find them may well be longer and more error-prone than simply reciting the spell itself. And, as any sysadmin could tell you, sometimes it's not worth writing a stored program for one-off tasks; you just need to be able to write a quite bash script on the command-line. For magical purposes, therefore, we'll want a programming language that is optimized for speaking, while retaining the precision of any other programming language.

After some discussion on the CONLANG-L mailing list, I think I have a pretty good idea of (one possibility for) what a "magical scripting language" might look like.

The major problem that I see needing to be solved is parenthesization; one can't be expected to properly keep track of indentation levels in speech, and explicit brackets around everything can get really hard to
keep track of even when you can look at what you're doing on a screen (which is why we have special editors that keep track of bracket-matching for us!)

Ideally, the language would not require explicit parenthesization anywhere, and other "syntactic noise" and boilerplate code would be minimized, so that every token of the language carries as much semantic weight as possible, to make them easier to memorize. This leads me to think that a concatenative, combinator-based language (like FORTH, or the non-programming-language conlang Fith) would be the best base, on top of which "idiomatic" flourishes could be added. Concatenative languages are often called "stack based", but they don't have to be implemented with a stack. They are in fact isomorphic to applicative languages like LISPs (i.e., there is a purely mechanical method for transforming any concatenative program into a fully-parenthesized applicative program and vice-versa), and can equally well be thought of as "data flow" languages, specifying how the outputs of one operation connect up with the inputs of another, and this is in fact a topic I have written about on this blog before.

There is a trade-off between being able to keep track of complex data flow without any explicit variable names, which can get very difficult if certain items are used over and over again, and being required to keep track of lots of temporary or bookkeeping variables (like loop indices). A concatenative language that allows you to define variables when you want, but minimizes extra variables whenever they would constitute "syntactic noise" with minimal semantic value, seems to me the best of both worlds. This should make simple incantations relatively easy to compose on-the-fly, and easy to memorize, as they would be mostly flat lists of meaningful words, similar to natural language.

Once you introduce re-usable variables, however, you have to decide the question of how variables are scoped. Letting all variables have the same meaning everywhere ("global scope") is an extremely bad idea; it makes it very dangerous to try re-using existing spells as components of a new spell, because variable names might be re-used for very different purposes in different sub-spells. If we want to be able to define and re-use sub-spells (i.e., functions, subroutines, procedures, or blocks, in terms of real-world programming languages), there are two major approaches to scoping rules available: dynamic scoping, and static scoping.

Loosely speaking, dynamic scoping means that any variables that are not defined in a function (or block) are the same as variables with the same name that are in-scope at the place where the function was called. This can only be figured out when a function is actually run, hence "dynamic". Static scoping means that any variables not defined in a function (or block) are the same as variables with the same name that are in-scope at the place where the function was defined. This can be figured out by looking at the text of a program without running it, hence "static".

Dynamic scope is generally easier to implement in (some kinds of) interpreters, while static scope is generally easier to implement in compilers, which early on in CS history led to a split between some languages using dynamic scope and some using static scope just because it was easier to implement the language that way. The modern concensus, however, is that dynamic scope is almost always a Bad Idea, because it makes it harder to analyze a program statically and prove that it is correct, whether with an automatic analysis tool or just in terms of being able to look at it and easily understand how the program works, without running it. Nevertheless, dynamic scope does have some legitimate use cases, and some modern languages provide work-arounds to let you enforce dynamic scoping where you really need it.

Scala, for example, simulates dynamic scoping with "implicit arguments", and this really highlights a good argument for dynamic scoping in a spoken programming language. One pain point with most programming languages, which would only be exacerbated in a spoken context, is remembering the proper order for long lists of function arguments. This can be ameliorated by named (rather than positional) arguments, but having to recite the names of every argument every time one calls on a sub-spell seems like a lot of boilerplate that it would be nice to be able to eliminate.

With dynamic scoping, however, you get the benefits of named arguments without having to actually list them either in a function definition (although that might well be a good idea for documentary purposes when spells are written down!) or when calling them. Just use reasonable names in the body of a sub-spell for whatever object that sub-spell is manipulating, and as long as variables with the appropriate names have already been defined when you wish to use a sub-spell, that's all you need. Making sure that those names refer to the correct things each time the sub-spell is called is taken care of automatically.

Examples

So, what might this incantation language actually look/sound like? Let's look first a simple script to do your dishes after a meal:

loop [more-than COUNT-DISHES 0] [let DISH [NEXT-DISH] DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move]

Things that are assumed to built-in to the language are in lower case, while things that are assumed to be magician-defined are in upper case. If every "verb" has fixed arity (so you always know exactly how many arguments it will need- there are no ambitransitives) then you don't need brackets around arguments or special delimiters between statements/expressions. We only need them to delimit "complement clauses"- i.e., blocks of code that are themselves arguments to other operators (in this, case "loop" and "let").

If magicians want to create their own higher-order spells which take other spells as arguments, there's not much to be done about eliminating those brackets. There are transformations in combinator calculus that can be used to remove them, but the results are extremely difficult for a human to follow, and no one would compose them on-the-fly for anything task of significant complexity. We could introduce a macro metaprogramming system that would let magicians define their own clause-delimiter syntax to eliminate cruft or enhance memorability, but then you might have to remember separate syntax for every sub-spell, which could get even worse than having to remember a single set of brackets. This is, in fact, a real problem that the LISP community (among others) deals with- if your language is too powerful, and too expressive, you get fragmentation problems, and end up with extra memory burden trying to keep track of what ridiculous things your co-workers decided to use that power for. It's often easier to enforce consistency.

Still, we can achieve some improvement by adding some "flourishes" to some of the basic, built-in operators in the language, replacing generic brackets with special construct-specific keywords. This is in fact a strategy taken by many real-world programming languages, which use block keywords like "while...wend" or "if...endif" rather than generic brackets for everything. With that alteration made, the spell might look something like this:

while more-than COUNT-DISH 0 loop let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move wend

Now there's a lot of distance between the "loop" and the "wend", which could, in a more complicated spell, make it easy to lose track of, even with the specialized keywords. To help with that, we can do some aggressive let-abstraction- assigning blocks to variables, and then using the short variable name in place of the long literal block definition. That gets us a spell like

let WASHING be let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move in
while more-than COUNT-DISH 0 loop WASHING wend


In some ways, that's better, but now we have the potentially-confusing sequence of nested "let"s ("let ... be let ... be ... in ... in"), and we can't move the second "let" outside the definition of "WASHING" because it actually needs to be re-evaluated, redefining "DISH", every time "WASHING" is called. This wouldn't be a big problem in a written programming language, but it's seriously annoying in speech. There are a few ways it could be fixed; one solution I like is allowing cataphoric variables (which refer to a later definition) in addition to anaphoric variables (which refer to an earlier definition), so we can switch up which structure to use to avoid repetition, and make a choice about which structure is more conceptually appropriate in different kinds of spells. Cataphoric variables are not terribly common in real-world programming languages, but they do exist, as in Haskell's "where"-clauses. Implementing "where" in out magic language, we can write the spell as

while more-than COUNT-DISH 0 loop WASHING wend
where WASHING is let DISH be NEXT-DISH in DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move done


We might also take advantage of dynamic scoping to write the algorithm in a more functional style, mapping over the collection of dishes, like so:

for DISH in DISHES loop WASHING rof
where WASHING is DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move done


or

let WASHING be DISH pickup DISH SINK move WATER DISH use SOAP DISH use DISH CABINET move in
for DISH in DISHES loop WASHING rof


In either case, the nested "let" to define the DISH variable is eliminated by binding a DISH variable in a for-in construct over a collection of DISHES, and relying on dynamic scope to make that variable available in the body of WASHING. Note that this avoids the need for spoken function parameter definitions, although it would be relatively easy to add syntax for them in cases where they do turn out to be useful.

Now, this looks like a pretty straightforward spell, but note that it only works if we assume that things like "pickup", "NEXT-DISH", "use", and so forth have all been rigorously and safely defined ahead of time! These are all actually pretty complex concepts, and in practice demon magic would probably not be used for relatively low-effort, high-descriptive-complexity tasks like washing dirty dishes. But, for magical scripting to be useful, we would a lot of these kinds of everyday things to be pre-defined. And just as *NIX users tend to have opinions about what things they individually want to have available in their command-line environment, and maintain custom .bash_profile/.bashrc files per login account, I imagine that perhaps working magicians carry around phylacteries containing written copies of personally-preferred spells, and begin each incantation by referring to them to establish the appropriate execution environment.