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.

Abstract

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.

Course reader

PDF (1MB), posted on 2008-06-12.

Revised and tentative schedule

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

   Code: initial.ss, state.ss, exception.ss, control.ss.

   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?

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

   Code: reynolds.ss.

   Exercise: same-fringe and the abstract data type of streams. What’s so special about online update in semantic interpretation then?

3. Donkey anaphora is in-scope binding

   Goal concept: multiple levels of scope taking

   Code: quant.ss.

   Slides: slides-hamburg.pdf.

   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?

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

   Code: quote.ss, final.ss, final-c.ss.

   Exercise: write a denotational semantics for a single piece of mutable state in “final” form.

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