NASSLLI 2012 June 18 - 22

Sign up here for our Mailing List:

Questions? Email us:

Search the site:

  Powered by Google

Lambda: the ultimate syntax-semantics interface

Room: UTC 4.104


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.




We will use the programming language Haskell without assuming specific knowledge of it. It will help if you could install “the Haskell Platform” on your computer ahead of time. You can download it at

The installation seems simple for Windows and Linux; in particular, on Linux you may already find a package called “haskell-platform” ready to be installed. On the Mac, there is also a download available: See also specifically about Xcode. We plan to use the Haskell interpreter “ghci” only, so chances are you need not worry about the "SDK".


Our plan for the course is to talk about syntax (context-free grammars, or CFG), semantics (Simple Theory of Types, or lambda-calculus) and a calculational way of relating the two. We start with a trivial fragment and show how to write derivations and re-interpret them in various ways: to spell them out or to compute a logical formula. We grow our fragments and interpreters in the second lecture: we add quantification, anaphora, subject relative clauses to our natural-language fragment; we add state to the semantic calculus; we add the interpretation of a sentence as an imperative program performing an information “update”. We explain de Groote's dynamic logic analysis of donkey sentences.


  1. Basic fragments for a context-free grammar
  2. Treating the simply typed lambda calculus as an object language
  3. Approaches to quantification
  4. Dynamic logic and donkey anaphora
  5. Scope and inverse linking in continuation semantics



Chung-chieh Shan

Email: ccshan (AT) post (DOT) harvard (DOT) edu


Chung-chieh Shan received his PhD in computer science from Harvard University in 2005. He then joined the faculty of Rutgers University in the department of computer science and the center of cognitive science. Since 2011, he has been visiting the department of linguistics at Cornell University and the department of computer science at the University of Tsukuba.

Oleg Kiselyov

Email: oleg (AT) okmij (DOT) org


Oleg Kiselyov is a Computer Scientist in Monterey, CA. He is interested in language semantics: what phrases may denote, which transformations preserve the meaning and how to apply them systematically. He is particularly interested in binding, quantification, quotation, anaphora and non-determinism. As a computer scientist, by 'languages' he mainly meant formal (programming) languages — but not exclusively.