Skip to main content
SpringerLink
Log in

Types as Graphs: Continuations in Type Logical Grammar

  • Published:
Journal of Logic, Language and Information Aims and scope Submit manuscript

Abstract

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, type-logical way to model evaluation order and side effects in natural language. We illustrate with an improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abbott, M., Altenkirch, T., Ghani, G.N., and McBride, C., 2003, “Derivatives of containers,” in TLCA 2003: Proceedings of the 6th International Conference on Typed Lambda Calculi and Applications, Martin Hofmann, ed., pp. 16–30. Lecture Notes in Computer Science. Vol. 2701, Berlin: Springer-Verlag.

    Google Scholar 

  • Aoun, J. and Li, Y.-h. A., 1993, Syntax of Scope. Cambridge: MIT Press.

    Google Scholar 

  • Barendregt, H.P., 1981, The Lambda Calculus: Its Syntax and Semantics. Amsterdam: Elsevier Science.

    Google Scholar 

  • Barker, C., 2002, “Continuations and the nature of quantification,” Natural Language Semantics 10(3), 211–242.

    Article  Google Scholar 

  • Barker, C., 2004, “Continuations in natural language,” in CW’04: Proceedings of the 4th ACM SIG-PLAN Continuations Workshop, Hayo Thielecke, ed., pp. 1–11. Tech. Rep. CSR-04-1, School of Computer Science, University of Birmingham.

  • Barker, C., 2005, “Remark on Jacobson 1999: Crossover as a local constraint,” Linguistics and Philosophy 28(4), 447–472.

    Article  Google Scholar 

  • Belnap, N.D., Jr. 1982, “Display logic,” Journal of Philosophical Logic 11(4), 375–417.

    Article  Google Scholar 

  • Bernardi, R., 2002, Reasoning with polarity in categorial type logic. Ph.D. thesis, Utrecht Institute of Linguistics (OTS), Utrecht University.

  • Bernardi, R., 2003, CTL: In situ binding. http://www.let.uu.nl/$\sim$Raffaella.Bernardi/persona l/q_solutions.pdf.

  • Bernardi, R., and Moot, R. 2001, “Generalized quantifiers in declarative and interrogative sentences,” Journal of Language and Computation 1(3), 1–19.

    Google Scholar 

  • Chomsky, N., 1973, Conditions on transformations. in A Festschrift for Morris Halle, Stephen Anderson and Paul Kiparsky, ed., pp. 232–286. New York: Holt, Rinehart and Winston.

    Google Scholar 

  • Dalrymple, M., ed. 1999, Semantics and Syntax in Lexical Functional Grammar: The Resource Logic Approach. Cambridge: MIT Press.

    Google Scholar 

  • Dalrymple, M., Lamping, J., Pereira, F., and Saraswat, V.A., 1999, “Quantification, anaphora, and intensionality,” in dalrymple-semantics, Chap. 2, pp. 39–89.

  • Danvy, O. and Filinski, A., 1989, “A functional abstraction of typed contexts,” Tech. Rep. Vol. 89/12, DIKU, University of Copenhagen, Den-mark. http://www.daimi.au.dk/ danvy/Papers/fatc.ps.gz.

    Google Scholar 

  • Dowty, D., 1992, ‘Variable-free syntax’ variable-binding syntax, the natural deduction Lambek calculus, and the crossover constraint,” in Proceedings of the 11th West Coast Conference on Formal Linguistics, Jonathan Mead, ed., Stanford, CA: Center for the Study of Language and Information.

    Google Scholar 

  • Dowty, D.R., 1994, “The role of negative polarity and concord marking in natural language reasoning,” in Proceedings from Semantics and Linguistic Theory IV, Mandy Harvey and Lynn Santelmann, ed., Ithaca: Cornell University Press.

    Google Scholar 

  • Felleisen, M., 1987, The calculi of λv-CS conversion: A syntactic theory of control and state in imperative higher-order programming languages. Ph.D. thesis, Computer Science Department, Indiana University. Also as Tech. Rep. 226.

  • Felleisen, M., 1988, “The theory and practice of first-class prompts,” in POPL ’88: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, pp. 180–190. New York: ACM Press.

    Google Scholar 

  • Fischer, M.J., 1972, “Lambda-calculus schemata,” in Proceedings of ACM Conference on Proving Assertions About Programs, vol. 7(1) of ACM SIG-PLAN Notices, pp. 104–109. New York: ACM Press. Also ACM SIG-ACT News 14.

    Google Scholar 

  • Fischer, M.J., 1993, “Lambda-calculus schemata,” Lisp and Symbolic Computation 6(3–4), 259–288.

    Article  Google Scholar 

  • Fry, J., 1997, “Negative polarity licensing at the syntax-semantics interface,” in Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, Philip R. Cohen and Wolfgang Wahlster, ed., pp. 144–150. San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Fry, J., 1999, “Proof nets and negative polarity licensing,” in dalrymple-semantics, Chap. 3, pp. 91–116.

  • Gentzen, G., 1933, Über das Verhältnis zwischen intuitionistischer und klassischer Arithmetik. Galley proof, Mathematische Annalen.

  • Gentzen, G., 1935, Untersuchungen Über das logische Schliessen. Mathematische Zeitschrift 39, 176–210, 405–431. E

    Article  Google Scholar 

  • Gentzen, G., 1969a, The Collected Papers of Gerhard Gentzen, M.E. Szabo, ed., Amsterdam: North-Holland.

    Google Scholar 

  • Gentzen, G., 1969b, “Investigations into logical deduction,” in gentzen-collected, Chap. 3, pp. 68–131.

  • Gentzen, G., 1969c, “On the relation between intuitionist and classical arithmetic,” in gentzen-collected, Chap. 2, pp. 53–67.

  • Girard, J.-Y., Taylor, P., and Lafont, Y., 1989, Proofs and Types. Cambridge: Cambridge University Press.

    Google Scholar 

  • Gödel, K., 1933, “Zur intuitionistischen Arithmetik und Zahlentheorie,” Ergebnisse eines mathematischen Kolloquiums 4: 34–38.

    Google Scholar 

  • Gödel, K., 1965, “On intuitionistic arithmetic and number theory,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Martin Davis, ed., pp. 75–81. Hewlett, NY: Raven Press.

    Google Scholar 

  • Griffin, T.G., 1990, “A formulae-as-types notion of control,” in POPL ’90: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, pp. 47–58. New York: ACM Press.

    Google Scholar 

  • Groenendijk, J. and Stokhof, M., 1991, “Dynamic predicate logic,” Linguistics and Philosophy 14(1), 39–100.

    Article  Google Scholar 

  • de Groote, P., 2001, “Type raising, continuations, and classical logic,” in Proceedings of the 13th Amsterdam Colloquium, Robert van Rooy and Martin Stokhof, ed., pp. 97–101. Institute for Logic, Language and Computation, Universiteit van Amsterdam.

  • Heim, I., 1982, “The semantics of definite and indefinite noun phrases,” Ph.D. thesis, Department of Linguistics, University of Massachusetts.

  • Hepple, M., 1990, “The grammar and processing of order and dependency: A categorial approach,” Ph.D. thesis, Centre for Cognitive Science, University of Edinburgh.

  • Hepple, M., 1992, “Command and domain constraints in a categorial theory of binding,” in Proceedings of the 8th Amsterdam Colloquium, Paul Dekker and Martin Stokhof, ed., pp. 253–270. Institute for Logic, Language and Computation, Universiteit van Amsterdam.

  • Hinze, R. and Jeuring, J., 2001, “Weaving a web,” Journal of Functional Programming 11(6), 681–689.

    Article  Google Scholar 

  • Howard, W.A., 1980, “The formulae-as-types notion of construction,” in To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Jonathan P. Seldin and J. Roger Hindley, ed., pp. 479–490. San Diego, CA: Academic Press.

    Google Scholar 

  • Huang, C.-T.J., 1982, “Logical relations in Chinese and the theory of grammar,” Ph.D. thesis, Department of Linguistics and Philosophy, Massachusetts Institute of Technology.

  • Huet, G., 1997, “The zipper,” Journal of Functional Programming 7(5), 549–554.

    Article  Google Scholar 

  • Jacobson, P., 1999, “Towards a variable-free semantics,” Linguistics and Philosophy 22(2), 117–184.

    Article  Google Scholar 

  • Jacobson, P., 2000, “Paycheck pronouns, Bach-Peters sentences, and variable-free semantics,” Natural Language Semantics 8(2), 77–155.

    Article  Google Scholar 

  • Jäger, G., 2005, Anaphora and Type Logical Grammar, Berlin: Springer-Verlag.

    Google Scholar 

  • Kamp, H., 1981, “A theory of truth and semantic representation,” in Formal Methods in the Study of Language: Proceedings of the 3rd Amsterdam Colloquium, Jeroen A.G. Groenendijk, Theo M.V. Janssen, and Martin B.J. Stokhof, ed., pp. 277–322. Amsterdam: Mathematisch Centrum.

    Google Scholar 

  • Kelsey, R., Clinger, W.D., Rees, J., Abelson, H., Dybvig, R.K., Haynes, C.T., Rozas, G.J., Adams, N.I. IV, Friedman, DP., Kohlbecker, E., Steele, G.L., Bartley, D.H., Halstead, R., Oxley, D., Sussman, G.J., Brooks, G., Hanson, C., Pitman, K.M., and Wand, M., 1998, “Revised5 report on the algorithmic language Scheme,” Higher-Order and Symbolic Computation 11(1), 7–105. Also as ACM SIG/-PLAN Notices 33(9):26–76.

    Article  Google Scholar 

  • Kolmogorov, A., 1925, “O principe tertium non datur,” Mathematicheskij sbornik 32, 646–667.

    Google Scholar 

  • Kolmogorov, A., 1967, “On the principle of excluded middle,” in From Frege to Gödel: A source Book in Mathematical Logic, 1879–1931, Jean van Heijenoort, ed., pp. 414–437. Cambridge: Harvard University Press.

    Google Scholar 

  • Krifka, M., 1995, “The semantics and pragmatics of polarity items,” Linguistic Analysis 25, 209–257.

    Google Scholar 

  • Kroch, A.S., 1974, “The semantics of scope in English,” Ph.D. thesis, Massachusetts Institute of Technology. Reprinted by New York: Garland, 1979.

  • Kuno, S. and Robinson, J.J. 1972, “Multiple wh questions,” Linguistic Inquiry 3, 463–487.

    Google Scholar 

  • Ladusaw, W.A., 1979, “Polarity sensitivity as inherent scope relations,” Ph.D. thesis, Department of Linguistics, University of Massachusetts. Reprinted by New York: Garland, 1980.

  • Lambek, J., 1958, “The mathematics of sentence structure,” American Mathematical Monthly 65(3), 154–170.

    Article  Google Scholar 

  • Landin, P.J., 1966, “The next 700 programming languages,” Communications of the ACM 9(3), 157–166.

    Article  Google Scholar 

  • Landin, P.J., 1998, “A generalization of jumps and labels,” Higher-Order and Symbolic Computation 11(2), 125–143.

    Article  Google Scholar 

  • Linebarger, M.C., 1980, “The grammar of negative polarity,” Ph.D. thesis, Massachusetts Institute of Technology.

  • Meyer, A.R. and Wand, M., 1985, “Continuation semantics in typed lambda-calculi (summary),” in Logics of Programs, Rohit Parikh, ed., pp. 219–224. Lecture Notes in Computer Science Vol. 193, Berlin: Springer-Verlag.

    Google Scholar 

  • Moortgat, M., 1988, Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus. Dordrecht: Foris.

    Google Scholar 

  • Moortgat, M., 1995, “In situ binding: A modal analysis,” in Proceedings of the 10th Amsterdam Colloquium, Paul Dekker and Martin Stokhof, ed., pp. 539–549. Institute for Logic, Language and Computation, Universiteit van Amsterdam.

  • Moortgat, M., 1996, “Generalized quantification and discontinuous type constructors,” in Discontinuous Constituency, Harry C. Bunt and Arthur van Horck, ed., pp. 181–207. Berlin: Mouton de Gruyter.

    Google Scholar 

  • Moortgat, M., 1997, “Categorial type logics,” in Handbook of Logic and Language, Johan F.A.K. van Benthem and Alice G.B. ter Meulen, ed., Chap. 2. Amsterdam: Elsevier Science.

    Google Scholar 

  • Moortgat, M., 2000, Computational Semantics: Lab Sessions. http://www.let.uu.nl/~Michael.Moortgat/personal/Courses/cslab2000s.pdf.

  • Moot, R., 2002, “Proof nets for linguistic analysis,” Ph.D. thesis, Utrecht Institute of Linguistics (OTS), Utrecht University.

  • Morrill, G.V., 1994, Type Logical Grammar: Categorial Logic of Signs. Dordrecht: Kluwer.

    Google Scholar 

  • Morrill, G.V., 2000, “Type-logical anaphora,” Report de Recerca Vol. LSI-00-77-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.

  • Murthy, C.R., 1990, “Extracting constructive content from classical proofs,” Ph.D. thesis, Department of Computer Science, Cornell University. Also as Tech. Rep. TR90-1151.

  • Papaspyrou, N.S., 1998, “Denotational semantics of evaluation order in expressions with side effects,” in Recent Advances in Information Science and Technology: 2nd Part of the Proceedings of the 2nd IMACS International Conference on Circuits, Systems and Computers, Nikos E. Mastorakis, ed., pp. 87–94. Singapore: World Scientific.

    Google Scholar 

  • Plotkin, G,D., 1975, “Call-by-name, call-by-value and the λ-calculus,” Theoretical Computer Science 1(2), 125–159.

    Article  Google Scholar 

  • Postal, P.M., 1971, Cross-Over Phenomena. New York: Holt, Rinehart and Winston.

    Google Scholar 

  • Reinhart, T., 1983, Anaphora and Semantic Interpretation. London: Croom Helm.

    Google Scholar 

  • Restall, G., 2000, An Introduction to Substructural Logics. London: Routledge.

    Google Scholar 

  • Reynolds, J.C., 1998, “Definitional interpreters for higher-order programming languages”, Higher-Order and Symbolic Computation 11(4), 363–397.

    Article  Google Scholar 

  • Shan, C.-c., 2002, “A continuation semantics of interrogatives that accounts for Baker’s ambiguity,” in Proceedings from Semantics and Linguistic Theory XII, Brendan Jackson, ed., pp. 246–265. Ithaca: Cornell University Press.

    Google Scholar 

  • Shan, C.-c., 2004, “Polarity sensitivity and evaluation order in type-logical grammar,” in Proceedings of the 2004 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, Susan Dumais, Daniel Marcu, and Salim Roukos, ed., Vol. 2, pp. 129–132. Somerset, NJ: Association for ComputationalLinguistics.

    Google Scholar 

  • Shan, C.-c. and Barker, C., 2006, “Explaining crossover and superiority as left-to-right evaluation,” Linguistics and Philosophy 29(1), 91–134.

    Article  Google Scholar 

  • Steedman, M.J., 2000, The Syntactic Process. Cambridge: MIT Press.

    Google Scholar 

  • Szabolcsi, A., 1989, “Bound variables in syntax (are there any?),” in Semantics and Contextual Expression, Renate Bartsch, Johan F.A.K. van Benthem, and Peter van Emde Boas, ed., pp. 295–318. Dordrecht: Foris.

    Google Scholar 

  • Szabolcsi, A., 1992, “Combinatory grammar and projection from the lexicon,” in Lexical Matters, Ivan A. Sag and Anna Szabolcsi, ed., pp. 241–269. CSLI Lecture Notes Vol. 24, Stanford, CA: Center for the Study of Language and Information.

    Google Scholar 

  • Szabolcsi, A., 1997, “Strategies for scope taking,” in Ways of Scope Taking, Anna Szabolcsi, ed., Chap. 4, pp. 109–154. Dordrecht: Kluwer.

    Google Scholar 

  • Szabolcsi, A., 2004, “Positive polarity–negative polarity,” Natural Language and Linguistic Theory 22(2), 409–452.

    Article  Google Scholar 

  • Taha, W. and Nielsen, M.F., 2003, “Environment classifiers,” in POPL ’03: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, pp. 26–37. New York: ACM Press.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Linguistics, University of California, San Diego, USA

    Chris Barker

  2. Department of Computer Science and Center for Cognitive Science, The State University of New Jersey, Rutgers

    Chung-chieh Shan

Authors
  1. Chris Barker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chung-chieh Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chris Barker.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barker, C., Shan, Cc. Types as Graphs: Continuations in Type Logical Grammar. JoLLI 15, 331–370 (2006). https://doi.org/10.1007/s10849-006-0541-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10849-006-0541-6

Keywords

Search

Navigation