# What is the relationship between lambda calculus and logical form?

I was first introduced to lambda calculus as a way to use syntax to compose the semantic value of a phrase from the semantic values of the components of that phrase.

Lambda calculus does more than that, but I don't understand how it is more than a notation system for logic. (To be clear, I'm not claiming anything other than my limited understanding.)

I thought that lambda calculus any order logic. Untyped lambda calculus works for first-order logic. Typed lambda calculus works for higher-order logics.

An association with lambda calculus and first-order logic comes because implementation of higher-order logic are less common in programming languages. For example, Python's NLTK only allows first order logic. Lambda-prolog implements typed lambda calculus. More people use Python than Prolog. (I am not sure whether more computational linguists use Prolog than Python.)

The question "What is the relation between lambda calculus and LF?" is comparable to "What is the relation between F (any formal system of representation with an 'alphabet' and a set of 'formation rules' that can recursively generate the expressions of LF) and LF?, or even to "What is the relation between a natural language L and the LF of L?, and the answer is rather trivial: the relation is usually understood to be 'representational' (basically: one of 'translation'), i.e., the lambda calculus can (among many other things!) represent the Logical Form of natural languages, as you know very well.

However, what I suppose you want to understand better is under what assumptions and in what sense can lambda calculus be considered a better representational system for the LF of natural languages than, say, Predicate Logic, or Predicate Logic 'enriched' with events (plus tense logic, modal logic, possible words, etc.). Such formal languages are more or less 'powerful' (and more or less flexible and adequate) to represent the semantic structure of natural languages in a 'compositional' way to the extent that they acknowledge the existence of additional 'entities' (events, time intervals, etc., and new variables that can be quantified over).As you know, the most austere ontologies acknowledge only individuals (and sets) as in first-order Pred Logic, but Russell, Church, Reichembach and others 'enriched' that ontology with 'higher types', then Davidson added 'events', and others even more generously acknowledged 'times' or time 'intervals', modalities, propositions, possible worlds, etc. Montague, of course, has it all. You can take 'lambda calculus' as a sort of limit, in this respect, since, in principle, due to the properties of functional analysis, it can acknowledge and operate with an infinite number of types of entities.

The enormous advantage of lambda calculus over elementary logics as a matelanguage for the compositional representation of natural language LF comes from the fact that, assuming the analyst accepts a very rich ontology (e.g.,Frege's, for example, in which entities are either 'functions' or 'objects' of all types it may be analytically convenient to acknowledge!), it is possible to consider any non-atomic expression 'E' of any NL as the 'product' of two 'factors', a function 'F' and its 'argument' 'a', and say that F yields E if 'applied to' 'a'. What's more, since any function can be trivially turned into an argument of a higher order function ('Type Shifting', 'Type Raising', 'Function Composition'), the analyst can recursively 'reanalyse' functions as arguments (and viceversa!) at will, depending on the type of the 'domains' of the functions he may be interested in acknowledging in order to exhaustively analyze E into just two 'factors', an F and its argument.

And by 'any non-atomic expression E', I literally mean 'any expression', i.e., not just sentences, words, or intermediate phrases of any level of internal complexity (NPs, VPS, APs, AdvPs, PPs, QPs...) but also STRINGS (continuous or not!) of linguistic material that under other analytical approaches (e.g., phrase structure grammar, with its constituency tests) would not be acknowledged as relevant syntactic constituents and therefore would not be eligible to undergo operations (either in syntax or at LF). Actually, since lambda calculus is based on functional analysis and the latter is so powerful a tool, it can in principle be applied even to sub-morphemic units. In other words, 'features' (= [attribute:value] pairs) or even feature-values can also be analysed as 'arguments' (or functions!) if necessary, although, in practice, most syntactic-semantic theories treat minimal 'signs' as unanalysable atoms and seldom or never perform sub-atomic analysis (the event structure of verbs, mainly, excluded).

That makes lambda calculus an extremely powerful and flexible metalanguage for the representation of the 'factors' that compositionally contribute meaning to NL expressions of any level of complexity. You can take the sense of a DP expression like 'the definition of syntactic categories in English' and analyze it into a function 'the definition of syntactic categories in __' and an argument 'English', just as easily as you can take the function to be 'the' and the argument the rest of that DP (the NP), or the function to be 'the definition of syntactic __ in English' and the argument to be 'categories', etc. In principle, given an LF object O you can 'abstract' ANY component C of O and analyse the remainder as a function F( ) = O.

One of the consequences that have attracted more attention is that if lambda calculus is available to compute LF, grammars can be monostratal, i.e., it is possible to compute 'meaning' directly from 'surface syntax'. Thus, constructions that in early PSG or 'Chomskian generative grammar' are supposed to involve 'displacement' (e.g., WH-Movement, Topicalisation, Subject Raising, Extraposition, Right Node Raising, etc.) can be computed as if everything was 'in situ' provided certain kinds of PSG (GPSG, HPSG, etc.) or Categorial Grammar work in tandem with Lambda Calculus to generate syntactic structures and calculate compositional LFs, respectively. Also, since in lambda calculus virtually anything can be treated as a syntactic/semantic 'factor' ('constituent'), coordinative or elliptical constructions (e.g., Gapping, Sluicing, Right Node Raising) that under standard PSG approaches create constituency paradoxes, no longer do in Categorial Grammar cum Lambda Calculus. Mark Steedman's Surface Structure and Interpretation(MIT 1996) or The Syntactic Process (MIT 2000) are authoritative and readable classical statements in this respect. At a more elementary level (and under a Chomskian view of syntax), I. Heim & A. Kratzer's Semantics in Generative Grammar (Blackwell, 1998) is also worth reading.

Of course, all that immense analytical and computational power has its negative side, too: grammars must not only be simple and elegant, but also, and above all, empirically adequate, which means able to generate enough without overgenerating, and, as you can imagine, unrestricted categorial grammar cum lambda calculus overgenerates massively, it acknowledges wildly extravagant LF/semantic entities ('objects' and 'functions') which must ultimately correlate with just as extravagant extralinguistic 'entities', and, needless to say, raises formidable linguistic-theoretic, metaphysical and philosophical issues.

I believe that the lambda calculus is, as you say, a notation system for logic, and for other mathematics. Linguists need to be specially concerned with notation systems for logic, because natural languages are also notation systems for logic, inasmuch as we generally carry out our logical reasoning in a natural language. Thus we are drawn to the study of logical notation.

Nouns and pronouns in natural languages correspond to variables in predicate logic, but some human languages have fewer nouns than others, and there might even be some human languages without nouns. That is a reason to be especially interested in logic systems that can do without variables, like the lambda calculus or combinatory logic.

Here is a background article from Quine on eliminating variables from logical and other formal expressions: Variables Explained Away. It's interesting that he finds himself inventing operators that look a lot like reflexive and passive constructions in natural languages.

Lambda calculus is a way of turning open expressions (that is, expressions with free variables) into functions. For example, λx.x+1 is a function that takes numbers to numbers. λx.x+y is a function from numbers to expressions with one free variable (if the domain of discourse are numbers).

In natural language semantics, lambda calculus can be used to assemble meaning during parsing. The idea is that every word has a meaning (assigned to it in the lexicon) and syntax helps assign meaning to more complex syntactic units. In higher-order logic, the meaning of "Mary obviously loves John" is

obviously(love(Mary,John))

In the lexicon, ||loves||=λx.λy.love(x,y) and ||obviously||=λP.obviously(P). On this view, syntactic composition is function application (hence the name "functionism" for this approach).

Some say that lambda calculus is unwieldy for implementing meaning assembly because it isn't monotonic. But it's a wrong approach to use lambda calculus at the level of surface syntax. (Linguistic) meaning is part of deep syntax, hence it should be assembled there. Deep syntax structures are unordered (or can be viewed as unordered for the purpose of semantic representation) and thus a λ-expression can refer to grammatical functions raher than the order in which syntactic structures are built up. In glue semantics (which uses linear logic) the meaning of "love" is taken to be

λx.λy.love(x,y) : σ(subj) ⊗ σ(obj) ⊸ σ(S)

Thus in glue semantic the meaning of both "John loves Mary" and "Mary John loves" can be assembled using the same rule though in the latter sentence it's the subject what is "attached" first.

However higher-order logic is unwieldy for reasoning as it's more complex and less understood that first-order logic. Davidson, Parsons, Hobbs, and Pietroski (to name just a few) argue that logical forms should be conjunctions of positive literals. On this view, the meaning of "John loves Mary" is the existential closure of

love(e,John,Mary)

or

love(e) ∧ Actor(e,John) ∧ Patient(e,Mary)

where e is an eventuality (also called situation, possible event, or state of affairs). Such logical forms can express everything one can encounter in language (such as quantification and logical connectives) so there's no reason not to use them if it helps elsewhere. And help it does a lot in pragmatically interpreting discourse. Meaning assembly that produces this kind of logical forms can be easily implemented (with or without lambda calculus) in both phrase-based and dependency-based grammar formalisms.

• I've read your answer and I understand about 2/3 of it. I do not understand what "monotonic" and "positive literals" mean, and I have no exposure to Glue semantics. To be frank, I remain rather skepticle about the value of these fields for natural language syntax, since I have yet to see the relevance. First order logic can be helpful when investigating scope and predicate-argument structures, but I have yet to see how the lambda calculus increases my understanding of syntax in a any way. In fact the notion that "every word has a meaning" is demonstrably false in light of idioms. Mar 4 '15 at 8:22
• @TimOsborne It's about semantics, not syntax. The former interacts with the latter though. You've read Bresnan's 2001 book so you should know what monotonic means (she defines it). The main point is that lambda calculus is useful if used correctly. There are a few papers on glue semantics in LFG, HPSG, and TAG (it works with any theory of syntax). It might be interesting for you that glue semantics (with it's "meaning constructors" based on lambda calculus) can be used in DG to implement the syntax-semantics interface. Mar 4 '15 at 8:41
• @"Go read a book about semantics and pragmatics and how they interacts with syntax"? Now you're patronizing me. Not good! Mar 4 '15 at 9:18
• @Atamiri Is Lambda Calculus 'non-monotonic'? Could you explain that a bit, please? It is the first time I notice such a claim in print, and, as a matter of fact, I had always assumed the contrary.
– user6814
Mar 14 '15 at 9:41
• @Atamiri I am also surprised by your claim that it is an error to use Lambda Calculus to compute meanings directly on surface syntax. Montague Grammar, GPSG, HPSG, Generalized Categorial Grammar, etc. all claim exactly the opposite: the crucial advantage of lambda calculus is that it CAN directly apply to the surface structures of natural language and dispenses with such 'artefacts' as 'deep structures', 'displacement', or 'LF' as understood in 'multistratal' grammars like P&P.
– user6814
Mar 14 '15 at 9:52