Day in, day out, the semanticist checks types and simplifies terms. Can the digital computer help with these calculations? In fact, modern programming languages offer exactly the modularity features that make it easy to try fragments out and scale them up. To show how, we express so-called extensible interpreters as functional programs and apply the technique to natural-language semantics and logic. Specifically, we work our way from the simply typed lambda calculus and a context-free grammar to CCG and to a dynamic and continuation treatment of quantification and anaphora. Striving to be comprehensible and informative to both linguists and programmers, we use the programming language Haskell without assuming specific knowledge of it.
This course on computational Montagovian semantics has been presented together with Chung-chieh Shan at the North American Summer School on Logic, Language and Information (NASSLLI 2012) < http://nasslli2012.com/courses/lambda-the-ultimate > at University of Texas, Austin, TX, USA, June 18-22, 2012. This five-day course is an extended version of the two-day short course presented at NASSLLI 2010 in Bloomington, IN in June 2010. This page collects the notes for the course in the form of commented Haskell code.
Ideally the course would be a beginning of a beautiful friendship -- or collaboration of natural- and programming-language researchers. At the very least, the course would aid their mutual comprehension.
We have a grander goal in mind. We hope that linguists will draw more advantage of the ideas of side effects, continuations, regions, staging (a.k.a. quotation) and dependent types. These ideas happen to have been developed more in programming language theory and are only recently being consciously applied to natural language semantics. Linguistic applications of these ideas are certain to prompt further development, benefiting the programming language theory as well. We look forward to computer scientists learning from linguists how to build theories of programming language competence . Emotional arguments about ``the best'' programming language should to be replaced by a scientific, predictive theory of how programmers perceive and apply a programming language or its feature.
Slides for the lectures, including the exercises
The map of languages and interpretations
The map of languages and interpretations
Definitions (or, `bookmarks') and CFG-like derivations
Semantic interpretation of a CFG derivation
Same as before, but now with type annotations. The file
CFG2Sem.hs tries to repair way too permissive grammar embedding with semantics: ``Using semantics to fix up syntax''
Preventing bad derivations `at run time'
Introducing type constants; accomplishing the goal that our terms represent all and only valid CFG derivations
Type functions: from syntactic categories to semantic types
Unifying syntax with semantics
We have demonstrated how to interpret syntactic (CFG) derivations in several ways. We apply the same approach to semantic forms, interpreting a semantic formula so to evaluate it in a particular world, to print it out, or to simplify it.
Warm-up: Embedding Propositional Logic, the language of very simple denotations
Another warm-up: embedding pure lambda-calculus, illustrating higher-order abstract syntax (HOAS)
The grammar of the language of denotations, and its many interpretations
Extending the fragment with adjectives and copula for a Rick Perry example from the bootcamp
Interpreting a CFG derivation as a string in Japanese
Adding QNP in the tradition of Montague
Likewise, extending the Japanese interpretation
A different way to add quantification, relying on higher-order abstract syntax (HOAS). We thus attempt a `rational reconstruction' of Montague's general approach of `administrative pronouns', which gave rise to Quantifier Raising (QR).
Implementing de Groote's approach: extending our fragment with pronouns, and the language of denotations with state
A sketch of Combinatorial Categorial Grammar (CCG)
Chung-chieh Shan's implementation of the continuation semantics of
Chung-chieh Shan and Chris Barker. 2006. Explaining crossover and superiority as left-to-right evaluation.
Linguistics and Philosophy 29(1):91-134.
and the tower notation of
Chris Barker and Chung-chieh Shan. 2008. Donkey anaphora is in-scope binding. Semantics and Pragmatics 1(1):1-46.
Closely related to the present course in subject matter (semantics):
The technique of extensible language embeddings is described in the following publications:
oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML