Compositional Semantics and Description Logics

This builds on logical representations of meaning, which set the desiderata, grounded truth in a model, and built first-order logic with events and time. There we could hand-translate a sentence into a formula; here we make the translation mechanical — driven by the parse tree — with the lambda calculus, confront the scope ambiguity that survives it, and meet the tractable description logics that trade some of FOL's power for decidable inference.

Compositionality and the lambda calculus

We can hand-translate sentences, but the goal is to compute a logical form from a sentence automatically, driven by its parse. The principle of compositionality says the meaning of a sentence is a function of the meanings of its parts and the way they combine — so if each grammar rule carries a rule for combining the meanings of its children, a logical form falls out of the parse tree.¹ The obstacle is mechanical: in the tree, a verb's arguments arrive one node at a time, not all at once, yet the predicate $\text{Serves}(x,y)$ takes both at once. We need a way to build a predicate up incrementally, holding a slot open until its filler appears.

That device is the lambda notation.¹ A lambda expression $\lambda x.P(x)$ is a formula $P(x)$ with the variable $x$ marked as an open parameter. Applying it to a term and performing beta-reduction — textually substituting the term for $x$ and dropping the $\lambda$ — closes the slot:

Lambdas nest. $\lambda x.\lambda y.\text{Near}(x,y)$ is a two-slot predicate that takes its arguments one at a time; applying it to $\text{Bacaro}$ reduces to $\lambda y.\text{Near}(\text{Bacaro},y)$, still a lambda expression, which applied to $\text{Centro}$ reduces to $\text{Near}(\text{Bacaro},\text{Centro})$. Turning a multi-argument predicate into a chain of one-argument functions this way is currying, and it is what lets a parse tree feed a predicate its arguments in the order the syntax delivers them.

A syntax-driven derivation

Put the pieces together on Maharani serves vegetarian food. Attach a lambda expression — a semantic attachment — to each node, and combine children by function application, walking the tree bottom-up. The proper noun contributes the constant $\text{Maharani}$. The verb contributes a curried two-slot predicate. The object NP contributes its constant. At the VP node the verb applies to the object; at the S node the result applies to the subject.

Read the steps off the tree. The verb's attachment is $\lambda w.\lambda x.\text{Serves}(x,w)$ — object slot $w$ outermost, so it is consumed first. At the VP, apply it to the object meaning $\text{VegFood}$:

At the S, apply that to the subject meaning $\text{Maharani}$:

Two beta-reductions, driven entirely by the shape of the parse tree, turn a sentence into a checkable logical form. This is the bridge from syntax to semantics: the parser supplies the tree, the lambda attachments supply the glue, and the logical form the model can verify falls out at the root. Learning to produce these attachments and derivations automatically is the subject of semantic parsing.

Quantifier scope ambiguity

Compositionality has a famous complication. When two quantifiers appear in one sentence, the grammar can assemble them in either order, and the two orders mean different things. Every restaurant serves a dish has a reading where a single dish is served by all restaurants ($\exists$ wide) and one where each restaurant serves possibly its own dish ($\forall$ wide):

A single syntactic structure thus underdetermines meaning, so a semantic analyzer must either enumerate scopings or leave scope underspecified for later resolution.

The two readings have different truth values in the same world. For example, take two restaurants $r_1,r_2$ and two dishes $d_1,d_2$, and read the two logical forms above against two candidate $\text{Serves}$ relations.

Model A has each restaurant serving its own dish: $\text{Serves}=\{(r_1,d_1),(r_2,d_2)\}$. The $\forall$-wide reading holds — pick $d_1$ for $r_1$ and $d_2$ for $r_2$, and every restaurant serves some dish. But the $\exists$-wide reading fails: there is no single dish $y$ that both restaurants serve, since $r_1$ serves only $d_1$ and $r_2$ only $d_2$. So Model A separates the readings — it makes the weaker one true and the stronger one false.

Model B adds a shared dish: $\text{Serves}=\{(r_1,d_1),(r_2,d_1)\}$, both restaurants serving $d_1$. Now the $\exists$-wide reading holds — take $y=d_1$, and $\forall x(\text{Restaurant}(x)\Rightarrow \text{Serves}(x,d_1))$ is satisfied — and the $\forall$-wide reading holds too, trivially, because it is the weaker claim.

No model runs the contrast the other way: because a shared dish served by all restaurants is in particular a dish for each restaurant, the $\exists$-wide reading logically entails the $\forall$-wide one. The $\exists$-wide reading is strictly stronger, and a scope-resolution component must respect this asymmetry: committing to $\exists$-wide claims more than the sentence may license, while $\forall$-wide is the safer, weaker reading.

Scope ambiguity is the semantic cousin of the PP-attachment ambiguity that plagued parsing: in both, one string licenses several structures.

Description logics and semantic networks

FOL is expressive but its full inference is undecidable, and older semantic network representations — nodes for concepts, labeled links for relations — were visually intuitive but semantically vague: a diagram of restaurant types cannot say whether the types are exhaustive or whether one restaurant can belong to two of them.² Description logics (DLs) are a family of decidable subsets of FOL designed to fix exactly this, trading expressiveness for guaranteed tractable inference.

A DL knowledge base splits in two: the TBox holds the terminology — the categories and their relationships — and the ABox holds facts about individuals. Categories are written without a variable ($\text{Restaurant}$, not $\text{Restaurant}(x)$) and denote sets of domain elements. The core TBox statement is subsumption, $C⊑D$ ($C$ is subsumed by $D$), meaning every member of $C$ is a member of $D$ — a plain subset relation on denotations.

Beyond plain subsumption, DLs can define categories with roles (binary relations). Using an existential role restriction, an Italian restaurant is one that, among other things, serves Italian cuisine:

which is the DL rendering of the FOL statement $\forall x\text{ItalianRestaurant}(x)\iff \text{Restaurant}(x)\wedge \exists y\text{hasCuisine}(x,y)\wedge \text{ItalianCuisine}(y)$. A vegetarian restaurant needs a universal restriction too — it serves vegetarian cuisine and only that: $\text{Restaurant}\sqcap \exists \text{hasCuisine}.\text{VegetarianCuisine}\sqcap \forall \text{hasCuisine}.\text{VegetarianCuisine}$. Because these are full definitions (necessary and sufficient conditions, marked $\equiv$), a DL reasoner performs instance checking and subsumption as inference: told that Gondolier is a restaurant serving Italian cuisine, it derives that Gondolier is an Italian restaurant, and derives the implied class hierarchy automatically. This machinery underlies the Web Ontology Language (OWL), the DL used to specify ontologies for the Semantic Web.²

Learning the map to logical form

Hand-written lambda attachments are the classical route from string to formula, and they do not scale — a new domain needs a new lexicon, and ambiguity multiplies the attachments. Three lines of work learn the map from data instead.

Grammar-induction semantic parsing. Zettlemoyer and Collins (2005) learn a Combinatory Categorial Grammar (CCG) whose lexical entries pair a word with both a syntactic category and a lambda-calculus meaning, trained from sentences annotated with their target logical forms.³ The parser searches over CCG derivations and scores them with a log-linear model; learning induces which lambda term each word contributes and how the terms combine. This kept the compositional, model-checkable logical forms of this lesson but replaced the hand-built lexicon with an induced one, and it drove a decade of work on parsing questions into database queries (GeoQuery, ATIS) and into executable programs.

Sequence-to-sequence semantic parsing. Once encoder-decoder networks matured, the logical form was treated as just another output sequence to generate. Dong and Lapata (2016) and Jia and Liang (2016) train an attention-based seq2seq (or sequence-to-tree) model to emit the linearized logical form token by token from the input sentence, with no explicit grammar at all.⁴⁵ Dong and Lapata's Seq2Tree decoder generates the formula's tree structure directly, respecting its bracketing; Jia and Liang add a data-recombination scheme that synthesizes new training examples from a induced grammar to inject a compositional bias the raw seq2seq model lacks. These models reached or beat the CCG parsers on the standard benchmarks while needing far less domain engineering — at the cost of no longer guaranteeing a well-formed formula, which the constrained decoders and grammar biases were introduced to recover.

Broad-coverage meaning: AMR. Abstract Meaning Representation (Banarescu et al. 2013) is a sentence-level graph — not a full logical form — that abstracts away from syntax: nodes are concepts (often PropBank frames), edges are roles, and inflection, articles, and word order are dropped so that paraphrases map to the same graph.⁶ It trades the strict truth-conditional semantics of FOL for annotatability at scale, and it spawned a body of work on AMR parsing (text to graph) that mirrors dependency parsing's transition-based versus graph-based split.

The through-line to today: large pretrained language models now generate logical forms, SQL, or executable code directly from a prompt, folding the parser and the lexicon into one model. What the symbolic machinery of this lesson still supplies is the target — a structure with a denotation that a solver or database can execute and check — and the guarantee that a well-typed formula means exactly one thing.