Composing meanings as programs
This wiki page is for Chung-chieh Shan’s course at the 2008 European Summer School in Logic, Language, and Information, in Hamburg, Germany. It is an advanced course on language and logic in week 1 (August 4–8) at 9:15–10:45am.
The meaning of expressions can be characterized either denotationally, by mapping them to a separate domain of values, or operationally, by mapping them to themselves. Drawing on a tight link between denotation and operation in programming languages, a growing literature in natural language semantics proposes dynamic accounts for various linguistic phenomena. This course surveys these accounts, with emphasis on two themes: first, the correspondence between notions of context and cases of apparent noncompositionality; second, building computational intuition through suggested lab exercises.
PDF (1MB), posted on 2008-06-12.
Revised and tentative schedule
Denotational, operational, and axiomatic semantics
Goal concept: evaluation order
Denotations are supposed to be adequate in obeying Leibniz’s law (compositionality), and ideally also fully abstract. Reduction rules and evaluation contexts in operational semantics are the oriented version of equations and congruence rules in axiomatic semantics. Two notions of side effects coincide: apparent noncompositionality, which a linguist might find semanticky, and manipulating context, which a linguist might find syntacticky.
Exercise: Combine state with exception.
Exercise: Write a denotational and operational semantics for a grammar that generates “Alice loves Bob”. How to add anaphora?
Question: Is transformational grammar an operational semantics?
From denotational to operational semantics by the continuation-passing-style transformation and defunctionalization
Goal concept: continuation
The very name of Reynolds’s definitional interpreters suggests connecting competence to performance. Example: an abstract machine for amb (related to nondeterminism and existential quantification in dynamic semantics). In general, continuations can emulate side effects such as mutable state.
Exercise: same-fringe and the abstract data type of streams. What’s so special about online update in semantic interpretation then?
Donkey anaphora is in-scope binding
Goal concept: multiple levels of scope taking
Exercise: convert a derivation of a donkey sentence between tower and linear notation. Can we handle functional and modal subordination? How to incorporate Stone’s insight about E-type analyses?
Syntax and semantics are multiple typed interpretations implementing the same signature
Goal concept: metacircularity
Abstract categorial grammar. Abstract data types. Normalization by evaluation. Example: the pronunciation and truth conditions of quantificational sentences.
Exercise: write a denotational semantics for a single piece of mutable state in “final” form.
Quotation and hyperintensionality reify syntax and processing as semantics
Goal concept: metaprogramming
The essence of dynamic semantics is to reify and grammaticalize processing in semantics and syntax, ideally in an iterable way as in a theory of mind.
Exercise: quantification in MetaScheme.