2025-01-14
I’ve become interested in how MUDs (Multi User Dungeons) parsed commands in natural language, or at least how the best ones did it1. I suppose I’ve always been intrigued by getting the computer to understand things as opposed to just doing them. And I’ve been recreationally thinking about this problem for a couple days now and have arrived at a couple conclusions.
A non-trivial problem of language parsing qua Chomsky is that any number of syntax trees may match a particular sentence, for a variety of reasons, showcasing the manifold types of grammatical ambiguity. For an example, consider the sentence
Alice saw Bob walking away with her binoculars
Which can mean that Alice saw Bob leaving through her binoculars, or that she saw him leaving and he had her binoculars in his possession. This illustrates one type of ambiguity, and while I do not plan on being exhaustive, a different sort of ambiguity arises from word or compound word polysemy, like
The fruit flies like mangoes
Where the sentence changes meaning depending on whether you decide to take “the fruit flies” as referring to the plurality of the fruit fly insects or as a verb phrase about the flight of a fruit.
It is clear to me that there is little hope in attempting to resolve those ambiguities at a syntactical level, not only because the grammar does parse the same sentence in multiple ways, but also because of anomalous phrases such as Chomsky’s
Colorless green ideas sleep furiously
Which I will not go as far as saying they are asemic, owing to texts such as Dell Hymes’ poem:
Hued ideas mock the brain,
Notions of color not yet color,
Of pure, touchless, branching pallor
Of invading, essential Green
In a spell, well-formed (ie. grammatical) sentences must be further resolved before one can extract any measure of meaning from them. There is a set of possible parses \(P(\sigma)\) for any particular sentence, and for each of its trees there may be a plurality of ways of assigning meaning to the particular nouns etc. that comprise it, yielding sensical results.
The reason Chomsky’s sentence is prima facie nonsensical is because the reader is accustomed to non-adversarial semantics; the essential take-away being that sense-making is heavily context-sensitive, and human readers might even struggle with (presumably) non-adversarial phrases such as Heidegger’s “Das Nichts nichtet” or “Nothing Nothings” (for a more in-depth read on possible meanings of this refer to 2).
The rough outline of a parser would be
Take a grammar describing phrase and sentence formation in the relevant language and use it to create a search tree consisting of all possible expansions of the of the start symbol “Sentence”; traverse this tree in some fashion or another and, if you hit a leaf and the token stream is over, that’s a possible parse. And with that, you obtain the set \(P(S)\) I’ve mentioned earlier (realistically you want to process them as they appear rather than batching). Further processing will have to reject or interpret those sentences, this goes well with the GoF’s interpreter pattern idea. Basically, for each successful parse, you have to resolve the sub-trees into the appropriate object types, recursively. Which is to say, a noun phrase must eventually resolve to an object, a verb phrase must resolve to an action, etc.
This process is obviously contextually dependent, but it is even subtler than that: there are manifold reasons for a resolution failure:
And you may want to handle their resolution failures in different ways for the users’ sake. For instance, many-such-objects might result in a dialog showing the many possible actions, while there is no recovery from a no-such-object failure.
From what I can gather from my limited experience speaking to other people, I assume there is a level of complexity associated to each possible interpretation sentences, which is related to the minimum size of context and ancillary explanation required to make it unambiguously determinable among the possible interpretations; but it is not clear how to define this aside from a measure of interpretative effort on the reader’s part.
As I’m writing this, I’ve just realized that I missed a pun reliant of acronyms on an online chat-room owing to different priorities in my own search-tree, which made me realize we perform a manner of semantic exploration implicitly and bail out when the interpretative effort exceeds a presumed level of importance ascribed to the meaning of the sentence in the process of being understood.
Presumably, if the solution to the enumeration of the possible, sensible, valuations is stack-based, one can impose depth-restrictions to simulate our propensity to giving up on making sense of a particular set of words. The novelty and creativity ascribed to making Chomsky’s sentence coherent, for instance, is an example of a deliberate moratorium on giving up on it, together with the “cheat” of being able to craft a context in which it has meaning to begin with.
Which takes us to the bell curve meme, where both extremes understand that the meaning of words isn’t in them.