How Can One Greek Letter Help Us Understand Language? Lambda Calculus 

+12tone Awesome! Glad to hear it. We really like breaking this stuff out and discussing it. ^_^

+Dariusz Pławecki Thanks! And yeah, I think it's that natural languages and computer science / computational linguistics are both concerned with some of the same ideas of representation, complexity, and meaning. Semantics is in many ways mathematics; one of the semantics courses I took in grad school was basically a math class. We'll have more of these sorts of things in the future, too! It'll be fun to talk about this kind of stuff more. ^_^

Yep, it's interesting how much of formal semantics stuff really does come down to computation and math stuff. I don't think that's what I thought of when I thought of semantic growing up (or even early in my linguistics career), but seeing how much you can capture with which paradigm is actually really fascinating, in the way that math can often be. ^_^

+Graoulia Sure! Glad to be able to help. ^_^

Haha, yeah, we do generally try to keep the tone light, but I think we more do references to things than actual jokes. You may be better off that way, though; like a lot of linguistics people, a lot of the jokes that we make (and then edit out) are pretty terrible puns. ^_^

Okay, so let's give this another shot! The lambda calculus can definitely be a tricky thing to wrap your head around, even for those who've been studying linguistics or a while. One reason might be that it solves a problem that most people don't even know about, unless they've spent a lot of time thinking about how functions work. Since our presentation is so informal, it can be hard to see exactly what that problem is, and how the lambda calculus gets around it. So, let's dive into the details a little, and see if things become clearer. First, it's important to realize that expressions like "y=x÷2," "f(x)=x÷2," or even just "x÷2" aren't functions. Instead, they name functions, by briefly describing the relationships that functions represent. But, they're no more functions than a person's name is that person. And like people, a single function can have many names; "y=x-3" is the same as "x=y+3," or even "y+3-x=0." So, a formula like "y=x+1" tells you how to relate one set (to keep things simple, let's say the set of natural numbers, written out as "1, 2, 3, ..." and sometimes abbreviated as ℕ) to another set (again, let's say ℕ). Using this formula, we can quickly determine that 1 is related to 2, 2 is related to 3, 3 is related to 4, et cetera. The expression saves us from having to write out the first set in its entirety, along with the second set and the connections that hold between them. And that's a good thing, because we're talking about three infinitely long lists! After all, addition has no upper limit. But that's what a function really is: an abstract mathematical object made up of three lists. The first list is everything that's going to relate to something else, and it's called the domain. The second list is everything that might have something relating to it, and so it's called the codomain. The last list spells out all the individual connections, one by one, and its called the graph. So, a function is a triple: a domain, a codomain, and a graph. From this point of view, we can see that these lists don't always have to be numbers. A function can be the set of all capital cities, the set of all countries, and a list which tells us which capitals belong with which country. We could (informally) represent this function using the equation "y=the country whose capital is x," or even just "x is the capital of y." With this in mind, we can think about what the difference really is between the equation "y=x÷z" and the lambda expression "λx.λz.x÷z," and it should become clearer that they're more than just different names for the same thing. That first formula is shorthand for a two-place function, because you need to fill in both x and z before you get y, which means its domain is a list not of single numbers, but of pairs of numbers (something like "1 and 1, 1 and 2, 2 and 1, 2 and 2, ..."). And its codomain will be something like the set of rational numbers (abbreviated as ℚ, for quotient), since it'll need to contain both whole numbers and fractions, because we're talking about division (1, 1/2, 2, ...). If we're being precise, this formula expects a pair of numbers as input, and can't function otherwise; it's undefined with respect to single numbers, in the same way that division is undefined with respect to zero. Giving it just a 1 or a 2 is like planning to meet someone at certain time, without ever saying where. Or like a car with an engine but no battery. It just doesn't work. That lambda expression, on the other hand, has a domain of single numbers (say, ℕ again), followed by a codomain of other functions (so, "λz.1÷z, λz.2÷;z, λz.3÷z, ..."). Each number in the domain will be connected with a different function in the codomain (1 relates to λz.1÷z, 2 relates to λz.2÷z, et cetera), and each of those functions will have its very own domain, codomain, and graph. The lambda calculus lets us get meta by putting functions inside the codomains of other functions. It even lets us put functions inside the domains of other functions, which is handy for words like "all" and "some." Getting back to language, it lets us precisely spell out the meanings of transitive verbs (and other, more complicated expressions). We're able to account for how both the verb by itself and the verb combined with an object each have some meaning, as well as how those meanings are related to each other in a regular way. Without the lambda calculus, we'd be left without an easy way to talk about how the meanings of sentences are built up out of the meanings of their parts!

Holy shit, I did not expect a reply. I was merely trying to give vent to my frustration. So you're saying that lambda expressions are pointless for computing actual results (if you HAVE x and y, then you don't need lambda calculus to calculate x/y), instead there are for doing math with the functions themselves? Btw, I never understood why functions are made up of three lists. Well, not lists, because the elements may be uncountable, but three sets/classes. Why do you need anything else than the graphs? The domain is implied by the graphs, since every element in the domain has to be in exactly one graph. The codomain is allowed to be a proper superset of the image, but I've never seen why that would be useful. Otherwise the codomain would also be implied by the graphs.

I'd say you got it! The usefulness of function-valued functions (that is, functions which spit out other functions), and the usefulness of functions that accept other functions as input, will hopefully also become more obvious as we continue to explore semantics in future episodes. To answer your question: none of us are mathematicians, so our response might be a bit speculative, but I would say the domain is included in the definition of a function because of, well, the definition of a function. That is, functions are defined as relations which are both left total and left monogamous, which means that they relate everything in their domain to something (leaving nothing out), and that everything in their domain is related to exactly one thing (and no more). The only way to check whether a relation is left-total is to compare its domain to the left-hand members of the graph, to see whether the sets are identical; if they are, you've got a function! The term "partial function," though something of a contradiction, is used in contrast, and refers to cases where only a proper subset of the domain is related to something. And this distinction actually becomes very useful a bit later on in semantics, when we need to be able to talk about restrictions on the domain. So, I would say you're right about the codomain: it's effectively implied by the graph. And, it seems that some definitions of "function" even leave it out altogether. But the domain is a bit more indispensable, since its totality really is part and parcel of the definition. Without its inclusion, we don't really have a way of distinguishing functions from other kinds of relations. Hope this helps! ^_^

Wha? If anything, it should be the other way around! Let's take the function y=x+1 from {0,1} to {0,1,2}. The graphs would be the set {(0,1), (1,2)}. You can see that the domain {0,1} has exactly the same elements as the first part of the elements in the graphs. And that always has to be the case. The codomain {0,1,2} has to be a superset of the second part of the graphs (the image). In this case it is a proper superset (it has an element that is not in the image) so you do need to define the codomain if you want to make that distinction. However, I wonder what it would be useful for.

Yeah, it does seem pretty wonky. At the very least, linguistic examples make it easier to see why spelling out the domain is useful. Take "x is taller than y," where we're intuitively relating the set of all people to itself. Now, there's definitely going to be at least one person (maybe more) who aren't taller than anyone, and so this relation won't actually be a function in the technical sense; there'll be at least one person (the shortest person) left in the domain that isn't related to anyone in the codomain. Of course, there will also be someone (the tallest person) in the codomain who isn't in the range (or the image, using your terminology). So, it seems equally weird to leave out either set in this case. Maybe someone who knows more about the history of mathematics could shine some light on why the conventions are what they are? Truth is, linguists don't spend *too* much time worrying about the total/partial distinction -- or codomains, for that matter -- except when they need to. ^_^

+Derek Cutsinger We wanted to find a giant iron to put there, but it wouldn't fit! ^_^

+Patrick Staples Your example doesn't have the second quantifier, "some", within a syntactic wh-island which it can't move out of. The video's example does. The point is that when this second quantifier is within a structure like an island where it can't move to be interpreted at the top of the structure then you don't get the ambiguity and this is predicted if we accept quantifier raising as is done in Extensional Semantics which uses lambda calculus.

+N0rmad Yep, this is it! If you change the order around, and you get rid of the island, then the predictions about what ambiguity is expected to show up changes, too.

+Jay Reed IP = Inflectional Phrase en.wikipedia.org/wiki/Inflectional_phrase

+Jay Reed Yep! As +impCaesarAvg said, it's the phrase that's associated with a clause in X' Theory.

+SewdiO What do you mean by this? Can you elaborate?

The way it's shown in this video is misleading. In lambda calculus, you don't have numbers, you have to define a format in which to represent numbers. The standard way of doing it I've seen is something like this: λhs.h(h(h(s))) means 3, λhs.h(h(s)) means 2. There is no significance to this schema other than it makes it easy for us to make functions which convert one number to another. You don't have + - * / in lambda calculus either. The funcitons that describe those operators are derived from a few basic rules about how lambda expressions work.

The church numeral approach, where "λhs.h(h(s))" means 2, does have significance: the number is a function that will make that number of copies of a function that it is applied to, and apply that to the next item in the expression. So, one might be better off referring to λhs.h(h(s)) as "twice," rather than 2. For example, if you have a function "Times3" that accepts one number and returns that number multiplied by 3, the expression "2 Times3 5" would have 2 accept Times3 , return λs.Times3 (Times3 (s)), which reduces to Times3 (Times3 (5)), then Times3(15), then 45. In this way, lambda calculus makes both sense and use of how numbers can act like functions in the right context.

Lambda calculus describes better how the theta roles for verbs and such can come into play in a way that predicate logic simply can't account for. You can also consider entire sentence structure if you think about it in a broad way, like you could have a lambda that takes a sentence and returns the sentence in a question format. Predicate logic can explain in part what sentences are valid, but lambda calculus puts emphasis on how one might construct the sentences in the first place. Also, if you mean in a more broad sense like why does lambda calculus exist, once you get into more advanced functions like the Y-Combinator, you will know how powerful the lambda calculus can be.

Matthew Giallourakis I suppose you're right, it does have some significance, but really it seems it's chosen for convenience and ease to work with with other functions. There's nothing that says we can't use some other schema for natural numbers.