Augury

I decided randomly to venture out into the world to a book store, in search of Vernor Vinge’s A Fire Upon the Deep and David Zindell’s Neverness. Since I didn’t want to go to the Borders in Silver Spring, the next closest option was Barnes and Noble in Bethesda. On Google Maps there seems to be quite a large parking lot across the street from the B&N so I figure, hey, brilliant, easy parking. Having driven to Bethesda, I find that it’s a meter lot, and not the kind with a machine in the corner that accepts credit cards and such. Since I don’t carry coins on me, I have to drive around to find some other parking. All street side parking is also coin meters, as are the majority of the parking garages (who has coin meters in a parking garage?!). Finally I find one that isn’t metered, it’s got people in booths that you pay. Hooray, I think, I can park here! So I do, and go to B&N, only to discover that they didn’t have the books I wanted, and when I get back to my car and go to pay, I find that this parking garage only accepts cash. Of course, they didn’t bother to say this anywhere, so now I have to go park again, and go find an ATM so I can get cash to pay the stupid parking fee. Fuck Bethesda.

Oh, I did get Vinge’s A Deepness in the Sky and Banks’ Consider Phlebas.

Having rewritten the unifier portion of my proof system, I find that the second time around, the unification process for partially specified items is simpler, and easier to understand. Some background first.

In patterns for the unifier, four sorts of “meta” symbols are available. One of them is a simple metavariable (denoted here with capitals, in Prolog style), which will unify with anything, thus if you have a list:

[X,Y,Z] = [1,2,3] yields { X = 1, Y = 2, Z = 3 ]

Another is a vacuous metavariable, one that doesn’t “record” the unification, denoted by an underscore (think Haskell):

[X,_,Z] = [1,2,3] yields { X = 1, Z = 3 }

The third is sort of like an arbitrary number of vacuous unifications, denoted by ellipsis (…):

[X,Y,...] = [1,2] yields { X = 1, Y = 2 }
[X,Y,...] = [1,2,3] yields { X = 1, Y = 2 }
[X,Y,...] = [1,2,3,4] yields { X = 1, Y = 2 }
etc.

The fourth sort of like variables, in that it captures values, and sort of like ellipsis, in that it spans an arbitrary length, which we’ll call multivariables, and which we’ll denote by a variable with an asterisk (*) in front of it, stealing Ruby notation for a very similar concept:

[X,*Y,Z] = [1,2] yields { X = 1, *Y = [], Z = 2 }
[X,*Y,Z] = [1,2,3] yields { X = 1, *Y = [2], Z = 3 }
[X,*Y,Z] = [1,2,3,4] yields { X = 1, *Y = [2,3], Z = 4 }
etc.

Now, what I discovered in the course of doing this for unordered collections (sets, multisets, and hashes) was that there’s a very general structure to the unification of two such collections, roughly along these lines:

if a.partially_specified? && b.partially_specified?
  # construct a special "conjunct" object c that represents
  # those items which can unify with both a and b and
  # treat a and b as variables that both equal c

elsif a.partially_specified?
  normals = a.reject { |x| x.is_a?(MultiVariable) || x.is_a?(Ellipsis) }

  if normals.empty?
    # take the non-normals of a (a - normals) and order them
    # as a_parts e.g. [*X,*Y,...]
    # find the ways b can be divided into normals.length parts as b_parts
    # including permutations e.g. {1,2} can be divided into 2 parts as:
    #   [{}, {1,2}]  [{1},{2}]  [{2},{1}]  [{1,2},{}]
    # for each of those ways as b_parts, unify each a_parts[i] with
    # b_parts[i] e.g. [*X,*Y] with each of the previous divisions yields
    #    {{ *X = {}, *Y = {1,2} },
    #     { *X = {1}, *Y = {2} },
    #     { *X = {2}, *Y = {1} },
    #     { *X = {1,2}, *Y = {} }}

  else
    # find the ways of choosing normals.length from b,
    # and for each of those ways as bs, unify normal with bs,
    # and then unify (a - normals) with (b - bs)

  end

elsif b.partially_specified?
  # mirror image of a.partially_specified, reuse as
  # Unifier.unify b, a, unifications

elsif a.length == b.length
  # no partial specification, just unify

else
  # no possibility of unification

end

Having stumbled across this pattern, I found that it works pretty much the same, with only minor modifications to account for structural differences, for sets, multisets, and hashes alike. It’s a vast vast improvement over my previous code which, aside from being asymmetric (in that you could only unify patterns (things with variables, etc.) with concrete items with no variables, etc.), was horrendously confused in how it achieved this same sort of unification of partially specified structures.

I commented previously on some impossible syntactic phenomena — that is, phenomena which we either know or very strongly believe to be impossible in a natural language’s syntax. Today I bring you some more such phenomena thanks to Robert Berwick’s 1987 paper Computational Complexity, Mathematical Linguistics, and Linguistic Theory.

Powers of 2

As far as anyone can tell, and as far as basically everyone believes, no language could have a process in which some word or collection of words must show up precisely 2ⁿ times in a sentence, for arbitrary integer n. That includes cases where n is fixed by some other phenomenon. Put another way, there’s no way for a language to require that some word shows up that many times, and every integer n is in principle possible in some sentence or other.

Object control that’s depth-dependent

Sentences like John persuaded Susan to leave display the phenomenon of object control, in which it’s Susan, not John, who is interpreted as the leaver (cf. John promised Susan to leave). It is strongly believed that no language could have this property of object control be dependent on whether or not the structural position of the object (i.e. Susan in this example) is the same depth of embedding as the controlled position (i.e. the subject position of the lower clause).

Unfortunately for LFG (and probably for GPSG and its descendent HPSG), both of these phenomena are perfectly possible.

Why is it that if you bake your first cake, you’ve never baked a cake before, but if you fake your first orgasm, you’ve had plenty of prior orgasms? And why is it that you can denote each of these objects (the cake and the orgasm) in syntactically parallel ways that reflect the parallel semantics — the first cake you’ve baked, the first orgasm you’ve faked?

is complicated.

That is all.

The following is a list of some imaginable syntactic processes that seem to not be possible in natural language. Some of these have pretty good justifications ideas for why they should be bad (the first two three) while the others don’t.

Counting (non-structure dependent)

Inserting an element after the n-th object of type P, for any choice of P, n, for n > 1.

Example: Form a negative sentence by putting “naht” after the 3rd word in the positive form of the sentence.

The tall boy naht eats pizza. (= the tall boy doesn’t eat pizza)

The very tall naht boy eats pizza. (= the very tall boy doesn’t eat pizza)

Swapping the m-th and n-th object of type P, for any choice of P, m, n.

Example: Form a Y/N question from a statement by swapping the 2nd and 4th words (if they both exist).

The boy saw the girl.

The the saw boy girl? (= Did the boy see the girl?)

Example: Express doubt about a sentence’s truth by swapping the 1st and 3rd NPs (if they both exist).

The boy gave the girl a puppy.

A puppy gave the girl the boy. (= Presumably, the boy gave the girl a puppy.)

Swapping the k-th and the k-th–to–last object of type P (where N is the length of the sentence).

Example: Form a Y/N question from a statement by swapping the first and last words.

The boy saw the girl.

girl boy saw the the. (= Did the boy see the girl?)

Counting (structure dependent)

V–k-th word order, for arbitrary k > 2.

Example: Main verbs go 3rd (preceded by arbitrary phrases in the same clause, as in V2 languages)

John Susan told that he likes pizza yesterday.

John yesterday told Susan that he likes pizza.

Susan John told that he likes pizza yesterday.

Susan yesterday told John that he likes pizza.

Yesterday John told Susan that he likes pizza.

Yesterday Susan told John that he likes pizza.

(all = John told Susan that he likes pizza yesterday.)

Moving k WH items, for arbitrary k > 1.

Example: Multiple WH movement moves at most 2 WH phrases to the front of a sentence when (as many as possible).

Who what bought? (= who bought what?)

who what bought when? (= who bought what when?)

who when bought what? (= who bought what when?)

Pied piping of the k-th phrase above the target of movement.

Example: Form a WH question from a sentence with a (single) WH phrase by pulling the phrase two above it to the front of the sentence.

John bought [the [book [on [the shelf]]]].

[book [on [where]]] John bought [the _]? (= what did John buy the book on?)

Non-local head-head relations

Head-head concord with the a word that is the head of the phrase more than one up from the concord-receiving word.

Example: Inflect for tense on the main verb, not the first main-or-auxiliary verb.

I have eat pizza. (= I have eaten pizza)

I have ate pizza. (= I had eaten pizza)

He have eats pizza. (= He has eaten pizza)

He have ate pizza. (= He had eaten pizza)

Non-linear Word Order Constraints

Cyclic ordering

Example: When more than one of Subject, Direct Object, and Indirect Object appear in a sentence, their order is any cyclic permutation of S-DO-IO.

John gave Susan a puppy

Susan gave a puppy John

A puppy gave Susan John

‘flimp’: to kiss someone allergic to something in particular. as in “John flimped peanuts” = “John kissed someone who is allergic to peanuts”
‘klimp’: to kiss someone in particular who happens to be allergic to peanuts. as in “John klimped Stephen” = “John kissed Stephen, who is allergic to peanuts”

Both of these are impossible — kids (and adults, presumably) cannot learn these verbs, atleast not naturally like they do other verbs. And yet:

‘tlimp’: to kiss someone allergic to peanuts. as in “John was tlimping all last night” = “John was kissing someone who is allergic to peanuts all last night”

Is completely fine.

Why should this be? There’s no solid answer to this question. I think these phenomena could reasonably be described as linguistic dark matter, in analogy to the mysterious unseen matter that speeds up the spin of galaxies.

Pollard and Sag, in 1985, took the Generalized Phrase Structure Grammar model and pared it down, reducing the formalism to a more minimal set of tools in many ways reminiscent of the contemporaneous work in Government and Binding. Where GPSG had just arbitrary rules for production/constraints on local subtrees with arbitrary constraint equations, HPSG has a very small set of rules that license local subtrees with very specific constraints equations, and all variation comes not from having separate rules but from having different properties on the items in the subtree. HPSG was also very lexicalized, in that the general combinatory rules combine and manipulate features that come from the lexical items; nothing is contributed by the tree except the combination of these sets of features into new sets of features. And rather than employing normal constraint equations, HPSG looks more like LFG, in that it employs feature structures represented by AVMs.

Read more »

Metaweb has this Semantic Web database, Freebase, employing an incredibly cool query language called MQL (Metaweb Query Language). The core idea of the database is that you represent knowledge as a massive object graph — objects represent things that you want to store information on, corresponding roughly to the things you would have Wikipedia articles about, and the relationships between objects (and between objects and primitive values like test or numbers) encode the knowledge you want to store about those objects. The programming language Prolog has similar knowledge-representation capabilities, but with subtle differences. Both of these provide extraordinarily interesting takes on interfacing with complex databases, but both also have their limitations.

Read more »

Finally! The GPSG post!

In the early 80’s, a number of syntacticians who desired a form of syntax without all the transformations of Chomsky’s kind of syntax, invented a model called Generalized Phrase Structure Grammar (GPSG). GPSG bares a striking resemblance to LFG, in a great many ways, and as such the description here will be quite short, drawing much on analogies to LFG.

Read more »