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

I was introduced to lambda calculus as a notation to express the semantics of a phrase, based on the semantics of its parts.

I am under the impression lambda calculus does more than that, but I don’t know what it does, other than being a notation for logic.

Some things I am aware of:

• I thought that untyped lambda calculus only works for first-order logic, and typed lambda calculus works for higher-order logic.

• The implementation of higher-order logic is less common in programming languages. For example, Python's NLTK only allows first-order logic.

• Lambda-Prolog implements typed lambda calculus.

• (I am not sure whether computational linguists use Prolog or Python more.)

What is their relationship and what is the difference? Does lambda calculus express the logical form of natural language sentences, or does it express first-order logic in general, or any type of logic?

The question “What is the relation between lambda calculus and logical form?" is comparable to the question “What is the relation any formal system of representation and the logical form of natural languages?

The answer then is trivially, that the relation is representational, or, one of translation. Lambda calculus can represent many things, only one of which is the LF of L.

###### Conventions

Let’s denote some natural language as `L`; its logical form as `LF`; and `F` as a formal system with alphabet `A` and a set of formation rules `R`, which can generate the expressions of `LF`.

# Lambda Calculus

In what sense, and when, can lambda calculus be considered a better representational system for the LF of L, than say,

• predicate logic
• predicate logic enriched with events
• predicate logic enriched with tense, modality, and possible worlds

Each of such formal logics have different expressive capabilities. They may vary in their suitability for denoting the semantics of natural languages because they acknowledge different logical entities, like events or time intervals, so they introduce new variables to be quantified over.

### Different logics acknowledge different logical entities

Logics are ontologies, systems expressing what exists. The most austere and restrictive ones acknowledge only elements and sets.

But Russell, Church, Reichembach and others, enriched it with higher types.

Others acknowledged times, time intervals, modalities, propositions, possible worlds, and more. Montague semantics has all of it.

You can take 'lambda calculus' as a limit of expressivity for a formal language - it can acknowledge and interoperate with an infinite number of types of entities.

That means that lambda calculus is a syntactic system for expressing various systems of logic, so it is up to the person at hand to decide what underlying system of logic they will be using it with.

## Lambda calculus is actually a meta-syntax for any type of logic

The enormous advantage of lambda calculus over elementary logics as a metalanguage for LF comes from that, assuming the analyst accepts a very rich ontology such as Frege's, where entities are either functions or objects of any type one chooses to include, it is possible to consider any non-atomic expression e of any L as the product of two factors, a function F and its argument a, and say that F(a) = e.

Since any function can be turned into an argument of a higher-order function - this is called type-shifting, type-raising, and is essentially function composition, the analyst can - recursively - re-analyze functions as arguments, and viceversa, at will, depending on the type of the domains of the functions they may be interested in, in order to exhaustively analyze e into just two factors: a function F, and its argument a.

In other words, it provides a very general, open level of abstraction and flexibility which can accommodate any type of logic, because it’s a way of allowing any system of logic to be expressed as elements and composition of functions on them, regardless of what the particular functions are (ie modal, temporal, epistemic, etc.)

By non-atomic expression, 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).

## Lambda calculus is built on abstract mathematics

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.

• This is an excellent answer, I’m still editing it to make it more readable tho. Halfway done. Jun 21 at 9:14

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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 9:52