Transcription
ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edComputational Semantics: Lambda CalculusSemantic AnalysisProblemsOne Solution:λ-CalculusScott FarrarCLMA, University of Washingtonfarrar@u.washington.eduFebruary 24, 20101/37λ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Today’s lectureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.ed1232/37Semantic AnalysisProblemsOne Solution: λ-Calculusλ-calculus and FOLλ-calculus and compositionalityThe semantics of words based on syntactic categorySemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Semantic analysisDefinitionSemantic analysis is the derivation of a semanticrepresentation from a string of words (perhaps marked upwith syntactic structure). In other words, map sentences ofNL onto logical formulas.Map Jim loves Betty to love(JIM, BETTY )There are several competing approaches for doing this, asthere are several competing standards for the right semanticrepresentation (use of event vs. relations).3/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
CompositionalityDefinitionRecall the principle of compositionality: the meaning of acomplex expression is a function of the meaning of its parts.The assumption is that we should be able to assign each“part” a meaning, then build larger structures, guided by thesyntax of the language.The syntax of NL and the syntax of predicate logic aresimilar, but ultimately not one-to-one compatible:translation between the two is a non-trivial task.4/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Event structureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisA sailboat heels.ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category5/37
Event structureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisA sailboat heels. e b [SailBoat(b) HeelingEvent(e) actor (e, b)]ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category5/37
Event structureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisA sailboat heels. e b [SailBoat(b) HeelingEvent(e) actor (e, b)]My sailboat is on the bottom.5/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Event structureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisA sailboat heels. e b [SailBoat(b) HeelingEvent(e) actor (e, b)]My sailboat is on the bottom. e [SpatialLocating (e) theme(e, MYSB) loc(e, SEAFLOOR)]5/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Semantic attachmentsConsider the problem of two-place predicates in anon-event-style semantics: we need to map Jim loves Bettyto something like:ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic Analysislove(JIM, BETTY ).ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category6/37
Semantic attachmentsConsider the problem of two-place predicates in anon-event-style semantics: we need to map Jim loves Bettyto something like:ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic Analysislove(JIM, BETTY ).Let’s assume strict compositionality and say that themeaning of each syntactic constituent contributes to themeaning of the parent constituent. We could come up withsomething like XP.sem to stand for the semantics of someconstituent XP.6/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Semantic attachmentsConsider the problem of two-place predicates in anon-event-style semantics: we need to map Jim loves Bettyto something like:ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic Analysislove(JIM, BETTY ).Let’s assume strict compositionality and say that themeaning of each syntactic constituent contributes to themeaning of the parent constituent. We could come up withsomething like XP.sem to stand for the semantics of someconstituent XP.DefinitionSemantic attachment refers to the adornment of phrasestructure rules with such semantic information.6/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Semantic attachmentsComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category7/37
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic categoryloves(JIM, BETTY )8/37
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic categoryloves(JIM, BETTY )8/37
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic categoryloves(JIM, BETTY )8/37
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic categoryloves(JIM, BETTY )8/37
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semlove.sem love(x, y )loves(JIM, BETTY )8/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semlove.sem love(x, y )NP.sem NNP.semloves(JIM, BETTY )8/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semlove.sem love(x, y )NP.sem NNP.semNNP.sem Betty.sem or Jim.semloves(JIM, BETTY )8/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semlove.sem love(x, y )NP.sem NNP.semNNP.sem Betty.sem or Jim.semBetty.sem BETTYloves(JIM, BETTY )8/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Example: Semantic attachmentsAssume that the symbol stands for the mbda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisS.sem NP.sem VP.semVP.sem V.sem NP.semV.sem love.semlove.sem love(x, y )NP.sem NNP.semNNP.sem Betty.sem or Jim.semBetty.sem BETTYJim.sem JIMloves(JIM, BETTY )8/37ProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edBut what about other examples:Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category9/37
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edBut what about other examples:Semantic AnalysisProblemsBetty is loved by Jim.One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category9/37
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edBut what about other examples:Semantic AnalysisProblemsBetty is loved by Jim.It’s Jim who loves Betty.One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category9/37
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edBut what about other examples:Semantic AnalysisProblemsBetty is loved by Jim.It’s Jim who loves Betty.Betty is the one loved by Jim.9/37One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edBut what about other examples:Semantic AnalysisProblemsBetty is loved by Jim.It’s Jim who loves Betty.Betty is the one loved by Jim.All clues to how the semantic representation might look arefound in the syntactic structure of NL. All this, without evenconsidering the ambiguity problem.9/37One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Analysis problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edThe analysis problem: there is no (elegant) way to fill inthe arguments of formulas at the level of semanticrepresentation, in a way that is consistent with the syntax.In other words, there is no formal means of combining partsinto wholes in standard FOL: .Even with passive verbs for example, we need to getBETTY to fill the second argument position of the predicatelove(x, y ).10/37Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edRepresentation problem: no way to represent the meaningfor some kinds of constituents.Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category11/37
Representation problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edRepresentation problem: no way to represent the meaningfor some kinds of constituents.We can very easily express the meaning of full sentences inplain FOL. We can say that a sentence is true given somestate of the world.John kissed Mary is T just in case John really did kiss Mary.11/37Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edRepresentation problem: no way to represent the meaningfor some kinds of constituents.We can very easily express the meaning of full sentences inplain FOL. We can say that a sentence is true given somestate of the world.John kissed Mary is T just in case John really did kiss Mary.With standard truth-conditional semantics, where thetruth of propositions can either be T or F , such logicalexpressions have a truth value. BUT.11/37Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemWhat about constituents like VPs: kissed Opra. Thesemantics would something like VP.sem, or kiss(x, OPRA)12/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemWhat about constituents like VPs: kissed Opra. Thesemantics would something like VP.sem, or kiss(x, OPRA)12/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemWhat about constituents like VPs: kissed Opra. Thesemantics would something like VP.sem, or kiss(x, OPRA)12/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsBut kiss(x, OPRA) has no truth value. This is becausethere are unbound variables: x has no connection to theUD. Such open sentences are neither T or F .One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemWhat about constituents like VPs: kissed Opra. Thesemantics would something like VP.sem, or kiss(x, OPRA)12/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsBut kiss(x, OPRA) has no truth value. This is becausethere are unbound variables: x has no connection to theUD. Such open sentences are neither T or F .Intuitively however, we know what a NL predicate/VPmeans: e.g., . kissed Opra means something like a “kissing Opra event”, reguardless of who does the kissing.One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Representation problemWhat about constituents like VPs: kissed Opra. Thesemantics would something like VP.sem, or kiss(x, OPRA)12/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsBut kiss(x, OPRA) has no truth value. This is becausethere are unbound variables: x has no connection to theUD. Such open sentences are neither T or F .Intuitively however, we know what a NL predicate/VPmeans: e.g., . kissed Opra means something like a “kissing Opra event”, reguardless of who does the kissing.But we cannot express the meaning of this in FOL givenour current machinery, since we’ll always have anunbound variable.One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
SummaryComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edIn summary then, we have at least two problems forcompositionality:1213/37Analysis problem: No systematic way to use syntax toguide the construction of a semantic representationRepresentation problem: Unsatisfying approach torepresenting the meanings of certain constituents;deriving truth values for certain kinds of constituents isill defined.Semantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Today’s lectureComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.ed12314/37Semantic AnalysisProblemsOne Solution: λ-Calculusλ-calculus and FOLλ-calculus and compositionalityThe semantics of words based on syntactic categorySemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
back to ChurchAlonzo Church created a calculus for describing arbitraryfunctions, called λ-calculus. (It was developed to give afunctional foundation for mathematics.) It wasn’t picked upby mathematicians, but it did become a versatile tool forcomputer scientists.15/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
back to ChurchAlonzo Church created a calculus for describing arbitraryfunctions, called λ-calculus. (It was developed to give afunctional foundation for mathematics.) It wasn’t picked upby mathematicians, but it did become a versatile tool forcomputer scientists.Remember Lisp? The second oldest high-level programminglanguage, and still used today (invented by John McCarthy,1958). Lisp (pure Lisp at least) deals exclusively withfunctions, and functions can be created on the fly andwithout names.15/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
back to ChurchAlonzo Church created a calculus for describing arbitraryfunctions, called λ-calculus. (It was developed to give afunctional foundation for mathematics.) It wasn’t picked upby mathematicians, but it did become a versatile tool forcomputer scientists.Remember Lisp? The second oldest high-level programminglanguage, and still used today (invented by John McCarthy,1958). Lisp (pure Lisp at least) deals exclusively withfunctions, and functions can be created on the fly andwithout names.In Lisp, this expression evaluates to an anonymous function:(lambda (x y) ( x y)), read as “the pair x and y aremapped to x y ”.15/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
back to ChurchAlonzo Church created a calculus for describing arbitraryfunctions, called λ-calculus. (It was developed to give afunctional foundation for mathematics.) It wasn’t picked upby mathematicians, but it did become a versatile tool forcomputer scientists.Remember Lisp? The second oldest high-level programminglanguage, and still used today (invented by John McCarthy,1958). Lisp (pure Lisp at least) deals exclusively withfunctions, and functions can be created on the fly andwithout names.In Lisp, this expression evaluates to an anonymous function:(lambda (x y) ( x y)), read as “the pair x and y aremapped to x y ”.15/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
back to ChurchAlonzo Church created a calculus for describing arbitraryfunctions, called λ-calculus. (It was developed to give afunctional foundation for mathematics.) It wasn’t picked upby mathematicians, but it did become a versatile tool forcomputer scientists.Remember Lisp? The second oldest high-level programminglanguage, and still used today (invented by John McCarthy,1958). Lisp (pure Lisp at least) deals exclusively withfunctions, and functions can be created on the fly andwithout names.In Lisp, this expression evaluates to an anonymous function:(lambda (x y) ( x y)), read as “the pair x and y aremapped to x y ”.Otherwise, we’d have a named function, something like:add(x, y )15/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :16/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :16/37Start with three symbols: , x, and yComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :16/37Start with three symbols: , x, and yTreat each symbol as either a function or argumentComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :16/37Start with three symbols: , x, and yTreat each symbol as either a function or argument x yields ( x)ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :16/37Start with three symbols: , x, and yTreat each symbol as either a function or argument x yields ( x)( x) y yields (( x)y )ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Functions and argumentsMore generally, we can describe what’s going on by assumingthat every expression is either a function or argument. Forinstance, suppose we want to create: ( x y ) :Start with three symbols: , x, and yTreat each symbol as either a function or argument x yields ( x)( x) y yields (( x)y )Thus, when an expression (function) is applied to anotherexpression (argument), a third expression (result) is obtained.16/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
λ-calculus: Formal definitionDefinitionExpressions in the language Λ are composed of:variables {a, b, c, . . . , x, y , z}abstraction symbols: λ and ., the dotparentheses: ( and )λ-terms. T Λ iff one of the following holds:1T is a member of a countable set of variables2T is of the form (MN) where M and N are in Λ.3T is of the form (λX .Y ) where X is a variable and Y isin Λ.Λ is the smallest language with this property.(MN) is called an application and λX .Y is an abstraction.17/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
ExamplesComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsThe following are all examples of λ expressions:One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category18/37
ExamplesComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsThe following are all examples of λ expressions:14λx . xOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category18/37
ExamplesComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsThe following are all examples of λ expressions:18/3714λx . x2λx . y (λ x . z x)One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
ExamplesComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsThe following are all examples of λ expressions:18/3714λx . x2λx . y (λ x . z x)3λx . x (y )One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
ExamplesComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsThe following are all examples of λ expressions:18/3714λx . x2λx . y (λ x . z x)3λx . x (y )One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
λ-calculus and FOLStandard definitions of FOL can be augmented withλ-calculus. The point is that we can use standard FOLformulas as functions and create new FOL bda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category19/37
λ-calculus and FOLStandard definitions of FOL can be augmented withλ-calculus. The point is that we can use standard FOLformulas as functions and create new FOL formulascompositionally.DefinitionIf in some formula a variable is bound by the λ operator, theformula is called a lambda expression.19/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsOne Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
ComputationalSemantics:Lambda Calculusλ-calculus and FOLStandard definitions of FOL can be augmented withλ-calculus. The point is that we can use standard FOLformulas as functions and create new FOL formulascompositionally.Semantic AnalysisProblemsOne Solution:λ-CalculusDefinitionIf in some formula a variable is bound by the λ operator, theformula is called a lambda expression.Syntactically, a λ-expression looks just like any otherquantified expression:λx.red(x) y .boat(y ) z.floats(z)19/37Scott FarrarCLMA, Universityof Washington farrar@u.washington.edλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Application expressionsTo symbolize compositionality, we can create a new formulafrom λx.dog (x) by treating it as a function and thenapplying it to an argument:20/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsλx.dog (x)(FIDO)One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Application expressionsTo symbolize compositionality, we can create a new formulafrom λx.dog (x) by treating it as a function and thenapplying it to an argument:20/37ComputationalSemantics:Lambda CalculusScott FarrarCLMA, Universityof Washington farrar@u.washington.edSemantic AnalysisProblemsλx.dog (x)(FIDO)One Solution:λ-Calculusλ-calculus and FOLλ-calculus andcompositionalityThe semantics ofwords based onsyntactic category
Lambda Calculus Scott Farrar CLMA, University of Washington far-rar@u.washington.edu Semantic Analysis Problems One Solution: -Calculus -calculus and FOL -calculus and compositionality The semantics of words based on syntactic category Today's lecture 1 Semantic Analysis Problems 2 One Solution: -Calculus -calculus and FOL -calculus and .
