# Parsing with CCGs - lambda part

I am following this video tutorial, starting 6th minute

I would like to parse the following sentence

square blue or round yellow pillow.


For now I am interested in only how square and blue are combined.

square -> ADJ: \lambda x. square(x)
blue -> ADJ: \lambda x. blue(x)


Next step is we raise types:

square -> N/N: \lambda f. \lambda  x. f(x) /\ square (x)
blue ->  N/N: \lambda f. \lambda  x. f(x) /\ blue (x)


Now we create representation for square blue. I indicate substitution by brackets

\lambda x. [ \lambda f. \lambda  x. f(x) /\ blue (x) ] (x) /\ square (x)


Next I simply substitute z for x everywhere outside of square brackets, so that we do not confuse different xs.

\lambda z. [ \lambda f. \lambda  x. f(x) /\ blue (x) ] (z) /\ square (z)


Next I push z into square brackets

    \lambda z.  \lambda  x. z(x) /\ blue (x)  /\ square (z)


This is different from what stated in the lecture:

\lambda z.  \lambda  x. z(x) /\   square (x)  /\   blue (x)


Where did I make a mistake?

square = λf.λx.f(x) ^ square(x)
blue = λg.λy.g(y) ^ blue(y)

square ° blue
(1) = λh.square(blue(h))
(2) = λh.[λf.λx.f(x) ^ square(x)]([λg.λy.g(y) ^ blue(y)](h))
(3) = λh.[λf.λx.f(x) ^ square(x)](λy.h(y) ^ blue(y))
(4) = λh.[λx.[λy.h(y) ^ blue(y)](x) ^ square(x)]
(5) = λh.λx.h(x) ^ blue(x) ^ square(x)


f, g, h are supposed to denote variables of type N (or et); x, y, z of type e.

1. Function composition: φ ° ψ means that for each α, α is mapped to φ(ψ(α)). Since φ ° ψ has the domain of ψ and the codomain of φ, we know the lambda expression corresponding to square ° blue must start with a variable of type N and that a term of type N must follow.

2. Substitute the definitions of square and blue.

3., 4., 5. Function application

• Thank you! I guess function composition with lambda is trickier than with regular functions. – user1700890 May 22 '19 at 18:19

I'll leave the lambdas to you, but you might like to know the syntactic structure. It is a RNR (right node-raising) construction, with "pillow" the raised node. The intonation I think makes that obvious. Thus:

[square blue GAP or round yellow GAP] (pillow), where the noun "pillow" fills the GAP.

"square", "blue", "round", "yellow" are adjectives which modify nouns or modified nouns.

Your computation is correct, and the video simply shows the wrong result.
The order square(x) ^ blue(x) comes from the fact that squared is applied to blue where blue will be substituted for f in the term f(x), which comes before square(x) in the conjunction.
To change the order in which the terms will appear in the conjunction without changing the order in which the terms are applied to each other (of course you could also do the backward composition blue square so square goes in for f in blue, but that wouldn't be in line with the intended forward composition), one could simply change the order of the expressions in the definition of square to

square -> N/N: \lambda f. \lambda  x. square (x) ^ f(x)


which changes the rule for type raising to

\lambda x. g(x) -> \lambda f. \lambda  x. g(x) ^ f(x)


Actually, the entire computation in the video doesn't work out at all:

(λf.[λx.[f(x) ^ square(x)]])(λf.[λy.[f(y) ^ blue(y)]]) reduces to
(λx.[(λf.[λy.[f(y) ^ blue(y)]])(x) ^ square(x)]) which reduces to
(λx.[(λy.[x(y) ^ blue(y)]) ^ square(x)]),
not (λf.[λx.[f(x) ^ square (x) ^ blue (x)]]).

I have no idea how they arrive at this result. This is a definitely a mistake.

• Thank you for reply. Also I believe type raising is not very accurate. It should go from ADJ to NP/N. Even in simplest case blue pillow we apply blue to noun pillow and end up with noun phrase. – user1700890 Apr 29 '19 at 19:25
• @user1700890 No, I the type N/N is okay. blue pillow should only be an N because the corredponding NP would be the blue pillow. Otherweise, you wouldn't be able to combine the result with more adjectives (in theory, you can append an unlimited number of adjectives) or determiners like the, both of which require an input of type N. In general, it is the inherent property of modifiers (which adjectives belong to) that they don't change the syntactic status of the element they combine with, and are therefore always of type X/X: A noun goes in, a noun comes out. – lemontree Apr 29 '19 at 19:34
• You can't use function application to combine N/N and N/N. Instead, you use function composition, which in effect just replaces the f(x) in the meaning of "square" with f(x) ^ blue(x) from "blue". You're basically doing f(g) when it's actually λx.f(g(x)), with x of type N or (et). Or maybe think of square(blue) vs. square(blue(pillow)). – David Vogt May 3 '19 at 23:15
• @user1700890 LaTeX is currently not supported on this site, but you may cast your vote for it here: linguistics.meta.stackexchange.com/questions/509/… – lemontree May 22 '19 at 19:47
• @user1700890 You can just google and copy-paste the unicode symbols. – lemontree May 22 '19 at 20:18