---
title: "Compositional Semantics and Description Logics"
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 12
order: 612
summary: >
  How do you compute a logical form from a sentence automatically? This lesson
  builds the compositional machinery: the lambda calculus that assembles a formula
  from a parse tree one beta-reduction at a time, the quantifier-scope ambiguity a
  single syntax tree leaves open, and the decidable description logics — TBox, ABox,
  subsumption, role restrictions — behind the Web Ontology Language, closing with
  how the map from string to logical form can be learned.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "§15.3.3 Lambda Notation; §15.3.4 The Semantics of FOL (scope)"
  - book: Jurafsky
    ref: "§15.5 Description Logics"
---

This builds on [logical representations of meaning](/natural-language-processing/linguistic-structure/logical-semantics),
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.[^jm-lambda] 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**.[^jm-lambda] 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:

$$
\lambda x.\,\text{Restaurant}(x)\;(\text{Maharani}) \;\;\longrightarrow\;\; \text{Restaurant}(\text{Maharani}).
$$

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.

$$
% caption: Currying by lambda application. A two-slot predicate is consumed one
% argument at a time: applying to Bacaro binds x and reveals an inner lambda, which
% applied to Centro yields the fully specified formula. Each step is one
% beta-reduction.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  b/.style={draw, minimum width=50mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[b] (l0) at (0,2.1)  {lambda x. lambda y. Near(x, y)};
  \node[b] (l1) at (0,0.7)  {lambda y. Near(Bacaro, y)};
  \node[b, draw=acc, text=acc] (l2) at (0,-0.7) {Near(Bacaro, Centro)};
  \draw[->, acc, thick] (l0.south) -- (l1.north) node[midway, right, font=\scriptsize] {apply (Bacaro)};
  \draw[->, acc, thick] (l1.south) -- (l2.north) node[midway, right, font=\scriptsize] {apply (Centro)};
  \node[font=\scriptsize, anchor=west] at (3.1,0.7)  {bind x, drop outer lambda};
  \node[font=\scriptsize, anchor=west, text=acc] at (3.1,-0.7) {fully specif\/ied formula};
\end{tikzpicture}
$$

### 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.

$$
% caption: A compositional derivation of the logical form for "Maharani serves
% vegetarian food." Each node carries a lambda semantic attachment; a parent applies
% its head child's function to the other child's meaning. Reading bottom-up, the VP
% binds the object and the S binds the subject, yielding the final formula.
\begin{tikzpicture}[>=stealth, font=\footnotesize, level distance=15mm,
  every node/.style={inner sep=1.6pt, align=center},
  level 1/.style={sibling distance=58mm},
  level 2/.style={sibling distance=30mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[text=acc] (S) {S\\ \scriptsize Serves(Maharani, VegFood)}
    child { node {NP\\ \scriptsize Maharani}
      child { node {\textit{Maharani}} } }
    child { node {VP\\ \scriptsize lambda x. Serves(x, VegFood)}
      child { node {Verb\\ \scriptsize lambda w. lambda x. Serves(x, w)}
        child { node {\textit{serves}} } }
      child { node {NP\\ \scriptsize VegFood}
        child { node {\textit{vegetarian food}} } } };
  \node[font=\scriptsize, text=acc, anchor=north west, align=left] at (-7.4,-4.4)
    {(1) verb: two open slots\\
     (2) VP: apply verb to object, bind w\\
     (3) S: apply VP to subject, bind x};
\end{tikzpicture}
$$

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}$:

$$
\lambda w.\lambda x.\,\text{Serves}(x, w)\;(\text{VegFood}) \;\longrightarrow\; \lambda x.\,\text{Serves}(x, \text{VegFood}).
$$

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

$$
\lambda x.\,\text{Serves}(x, \text{VegFood})\;(\text{Maharani}) \;\longrightarrow\; \text{Serves}(\text{Maharani}, \text{VegFood}).
$$

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](/natural-language-processing/linguistic-structure/constituency-parsing) 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](/natural-language-processing/linguistic-structure/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):

$$
\exists y\, \text{Dish}(y) \wedge \forall x\, \text{Restaurant}(x) \Rightarrow \text{Serves}(x, y)
\qquad\text{vs.}\qquad
\forall x\, \text{Restaurant}(x) \Rightarrow \exists y\, \text{Dish}(y) \wedge \text{Serves}(x, y).
$$

$$
% caption: Quantifier scope ambiguity in "every restaurant serves a dish." Wide
% "exists" (left) forces one shared dish across all restaurants; wide "for all"
% (right) lets each restaurant have its own dish. One syntax, two logical forms.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % left: one shared dish
  \node[font=\scriptsize, text=acc] at (0,2.2) {exists wide: one shared dish};
  \fill[acc] (0,0) circle (2.6pt);
  \node[font=\scriptsize, anchor=north] at (0,-0.15) {dish};
  \foreach \a in {130,160,190,220} {
    \draw[acc] (0,0) -- ++(\a:1.5);
    \fill[black] ($(0,0)+(\a:1.5)$) circle (2pt);
  }
  \node[font=\scriptsize, anchor=south] at (-1.5,1.15) {restaurants};
  % right: one dish each
  \begin{scope}[xshift=68mm]
  \node[font=\scriptsize, text=acc] at (0,2.2) {forall wide: one dish each};
  \foreach \y in {1.2,0.4,-0.4,-1.2} {
    \fill[black] (-1.3,\y) circle (2pt);
    \draw[acc] (-1.3,\y) -- (0.4,\y);
    \fill[acc] (0.4,\y) circle (2.6pt);
  }
  \node[font=\scriptsize, anchor=east] at (-1.45,1.2) {rest.};
  \node[font=\scriptsize, anchor=west] at (0.55,1.2) {dish};
  \end{scope}
\end{tikzpicture}
$$

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.

$$
% caption: Two models for "every restaurant serves a dish." Model A (each restaurant
% its own dish) makes the forall-wide reading TRUE but the exists-wide reading FALSE,
% separating them. Model B (both restaurants share dish d1) makes exists-wide TRUE,
% and forall-wide follows. Exists-wide entails forall-wide but not the reverse, so no
% model can make exists-wide true while forall-wide is false.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ent/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize},
  vtrue/.style={draw=acc, text=acc, minimum width=34mm, minimum height=7mm, align=center, font=\scriptsize},
  vfalse/.style={draw=red, text=red, minimum width=34mm, minimum height=7mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- Model A ----
  \node[font=\scriptsize\bfseries] at (1.5,3.4) {Model A: own dish each};
  \node[ent] (a-r1) at (0,2.4) {r1};
  \node[ent] (a-r2) at (0,0.9) {r2};
  \node[ent] (a-d1) at (3,2.4) {d1};
  \node[ent] (a-d2) at (3,0.9) {d2};
  \draw[->, acc, thick] (a-r1) -- (a-d1);
  \draw[->, acc, thick] (a-r2) -- (a-d2);
  \node[font=\scriptsize, anchor=west, text=black] at (-0.9,-0.15) {Serves = (r1,d1), (r2,d2)};
  \node[vtrue]  at (1.5,-1.1) {forall-wide: TRUE};
  \node[vfalse] at (1.5,-1.95) {exists-wide: FALSE};
  % ---- Model B ----
  \begin{scope}[xshift=68mm]
  \node[font=\scriptsize\bfseries] at (1.5,3.4) {Model B: one shared dish};
  \node[ent] (b-r1) at (0,2.4) {r1};
  \node[ent] (b-r2) at (0,0.9) {r2};
  \node[ent] (b-d1) at (3,1.65) {d1};
  \node[ent] (b-d2) at (3,0.0) {d2};
  \draw[->, acc, thick] (b-r1) -- (b-d1);
  \draw[->, acc, thick] (b-r2) -- (b-d1);
  \node[font=\scriptsize, anchor=west, text=black] at (-0.9,-0.75) {Serves = (r1,d1), (r2,d1)};
  \node[vtrue] at (1.5,-1.6) {exists-wide: TRUE};
  \node[vtrue] at (1.5,-2.45) {forall-wide: TRUE};
  \end{scope}
\end{tikzpicture}
$$

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](/natural-language-processing/linguistic-structure/constituency-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.[^jm-dl] **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 \sqsubseteq D$ (_$C$ is subsumed by $D$_), meaning every
member of $C$ is a member of $D$ — a plain subset relation on denotations.

$$
% caption: A subsumption hierarchy (ontology) in the restaurant domain. Each link
% C -> D asserts C is subsumed by D, so every Italian, Chinese, or Mexican
% restaurant is a Restaurant, and every Restaurant is a Commercial Establishment.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  n/.style={draw, minimum width=24mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n, draw=acc, text=acc] (ce) at (0,2.4) {Commercial\\Establishment};
  \node[n] (r) at (0,0.6) {Restaurant};
  \node[n] (it) at (-4.2,-1.4) {Italian\\Restaurant};
  \node[n] (ch) at (0,-1.4)    {Chinese\\Restaurant};
  \node[n] (mx) at (4.2,-1.4)  {Mexican\\Restaurant};
  \draw[->, acc, thick] (r) -- (ce);
  \draw[->, acc, thick] (it) -- (r);
  \draw[->, acc, thick] (ch) -- (r);
  \draw[->, acc, thick] (mx) -- (r);
\end{tikzpicture}
$$

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:

$$
\text{ItalianRestaurant} \equiv \text{Restaurant} \sqcap \exists\,\text{hasCuisine}.\text{ItalianCuisine},
$$

which is the DL rendering of the FOL statement $\forall x\, \text{ItalianRestaurant}(x)
\Leftrightarrow \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.[^jm-dl]

## 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.[^zc2005] 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.[^dl2016][^jl2016] 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.[^amr2013] 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.

[^jm-lambda]: **Jurafsky & Martin**, §15.3.3 — Lambda Notation: $\lambda$-expressions, $\lambda$-reduction, currying (Church 1940, Schönfinkel 1924), and the role of $\lambda$-notation in incrementally gathering a predicate's arguments from a parse tree for compositional semantic analysis.
[^jm-dl]: **Jurafsky & Martin**, §15.5 — Description Logics: the vagueness of semantic networks, DLs as decidable FOL subsets, TBox/ABox, subsumption ($\sqsubseteq$), role restrictions, definitional ($\equiv$) categories, subsumption and instance checking as inference, and OWL / the Semantic Web.
[^zc2005]: **Zettlemoyer & Collins (2005)**, "Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars," UAI 2005. Induces a CCG lexicon pairing words with syntactic categories and lambda-calculus meanings, scored by a log-linear model, trained from sentences paired with logical forms (GeoQuery, ATIS).
[^dl2016]: **Dong & Lapata (2016)**, "Language to Logical Form with Neural Attention," ACL 2016. Attention-based encoder-decoder (`Seq2Seq` and hierarchical `Seq2Tree`) that generates a linearized logical form directly from the sentence with no explicit grammar, the Seq2Tree variant respecting the formula's tree structure.
[^jl2016]: **Jia & Liang (2016)**, "Data Recombination for Neural Semantic Parsing," ACL 2016. A sequence-to-sequence semantic parser augmented with a data-recombination scheme that synthesizes new (utterance, logical-form) training pairs from an induced grammar, injecting a compositional bias into the neural model.
[^amr2013]: **Banarescu et al. (2013)**, "Abstract Meaning Representation for Sembanking," Linguistic Annotation Workshop 2013. AMR: a rooted, directed sentence-level graph of concepts (often PropBank frames) and role edges that abstracts away inflection, articles, and word order, mapping paraphrases to the same graph; the basis for later transition-based and graph-based AMR parsers.