English as a programming language?Yiannis N. MoschovakisUCLA and University of AthensESSLLI, 21 July, 2009cf. Richard Montague (1970) English as a formal languageEverything is not like everything else!1960 Seminar on the Theory of Knowledge with the authors ofA Logical Calculus of the Ideas Immanent in Nervous Activity,by Warren McCulloch and Walter Pitts, 1943Student: Isn’t this very much like that, which we studied last week?McCulloch: Many things are like many other things—and it isuseful to note this when we first encounter them;to understand a phenomenon more deeply, however, you shouldfocus on how it differs from similar phenomenaLesson: Not everything is like everything els e!Q: Is there a substantial common (or similar) important featureof natural and formal or programming languageswhich helps us understand them better?Yiannis N. Moschovakis: English as a programming language? 1/22How I got i nto this businessScott’s denotational semantics for programming languages:program Pden−−−−−−−−−→−−−−−−−−−→impls−−−−−−−−−→value(P)Correct implementations compute the independent denotationTarski-type value conditions vs implementation rulesA program expresses an algorithm; where is it?program P −−−−→ algorithm(P)den−−−−−−−−−→−−−−−−−−−→impls−−−−−−−−−→value(P)Frege: sentence A −−−−→ sense(A) −−−−→ den(A)Yiannis N. Moschovakis: English as a programming language? 2/22The talk in sl ogan formThe meaning of a term is the algorithm which computes its denotationMeanings are algorithms?It depends on what the meaning of the word ’is’ isIn mathematics, we say:A point in the plane is a pair (x, y) of real numbers(and worse, (x, y) = {{x}, {x, y}}!)but Euclid did OK without “knowing” this!The plane can be faithfully modeled by the Cartesian product R × RandMeanings can be faithfully modeled by algorithms(meaning abstract, not necessarily implementable algorithms)Yiannis N. Moschovakis: English as a programming language? 3/22Frege on sense (which he did not define)“[the sense of a sign] may be the common property of manypeople” Meanings are public (abstract?) objects“The sense of a proper name is grasped by everyone who issufficiently familiar w ith the language . . . Comprehensive knowledgeof the thing denoted . . . we never attain”Speakers of the language know the meanings of terms“The same sense has different expressions in different languages oreven in the same language”“The difference between a translation and the original text shouldproperly not overstep the [level of the idea]”Faithful translation should preserve meaningsense(A) ∼ the part of the semantic value of A which is preservedunder faithful translationYiannis N. Moschovakis: English as a programming language? 4/22Outline(1) Formal Fregean semantics(2) Meaning and synonymy(3) What are the objects of belief? (Local synonymy)(4) The decision problem for synonymySense and denotation as algorithm and value (1994)A logical calculus of meaning and synonymy (2006)Two aspects of situated meaning (with E. Kalyvianaki (2008))Posted in www.math.ucla.edu/∼ynmYiannis N. Moschovakis: English as a programming language? 5/22The methodology of formal Fregean semanticsIAn interpreted formalized language L is selectedIThe rendering operation on a fragment of natural language:natural language expression + informal conte xtrender−−−→ formal expression + stateISemantic values (denotations, meanings, etc.) are definedrigorously for the formal expressions of L and assigned tonatural language expressions via the rendering operationIMontague: L should be a higher type language(to model co-ordination, co-indexing, . . . )IClaim: L should have programming constructs(to model co-indexing, self-reference, meanings, . . . )Yiannis N. Moschovakis: English as a programming language? 6/22The typed λ-calculus with recursion Lλr(K ) - typesAn extension of the typed λ-calculus, into which Montague’sLanguage of Intensional Logic LIL can be easily interpreted (Gallin)Basic types b ≡ e | t | s (entities, truth values, states)Types: σ :≡ b | (σ1→ σ2)Abbreviation: σ1× σ2→ τ ≡ (σ1→ (σ2→ τ))Every non-basic type is uniquely of the formσ ≡ σ1× · · · × σn→ bYiannis N. Moschovakis: English as a programming language? 7/22The typed λ-calculus with recursion Lλr(K ) - syntaxConstants: A finite set K of typed constants (run, cow, he, the , every)he : (s → e)? Pure variables: vσ0, vσ1, . . . , for each type σ (v : σ)? Recursive variables: pσ0, pσ1, . . . , for each type σ (p : σ)Terms – with assumed type restrictions and assigned types (A : σ)A :≡ v | p | c | B(C) | λ(v )(B)|? A0where {p1:= A1, . . . , pn:= An}C : σ, B : (σ → τ) =⇒ B(C ) : τv : σ, B : τ =⇒ λ(v)(B) : (σ → τ )A0: σ =⇒ A0where {p1:= A1, . . . , pn:= An} : σAbbreviation: A(B, C, D) ≡ A(B)(C)(D)Yiannis N. Moschovakis: English as a programming language? 8/22Lλr(K ) - denotational semantics• We are given basic sets Ts, Teand Tt⊆ Tefor the basic typesTσ→τ= the set of all functions f : Tσ→ TτPb= Tb∪ {⊥} = the “flat poset” of TbPσ→τ= the set of all functions f : Tσ→ PτIvσivaries over Tσ, the total objects;Ipσivaries over Pσ, the partial objectsTσ⊆ Pσand Pσis a complete poset (with the pointwise ordering)• We are given an object c : Pσfor each constant c : σIIf A : σ and π is a type-respe cting assignment to the variables,then den(A)(π) ∈ Pσ(values are partial objects)IRecursive terms are interpreted by t he taking ofleast-fixed-pointsYiannis N. Moschovakis: English as a programming language? 9/22Rendering natural language i n Lλr(K )˜t ≡ (s → t) (type of Carnap intensions)˜e ≡ (s → e) (type of individual concepts)Abelard loves Eloiserender−−−→ loves(Abelard,Eloise) :˜tObama is the presidentrender−−−→ eq(Obama,the(president)) :˜tHe is the presidentrender−−−→ eq(He,the(president)) :˜tliarrender−−−→ p where {p := ¬p} : ttruthtellerrender−−−→ p where {p := p} : tAbelard, Eloise, Obama, He : ˜epresident : ˜e →˜t, eq : ˜e × ˜e →˜t¬ : t → t, the : (˜e →˜t) → ˜eden(liar) = den(truthteller) = ⊥Yiannis N. Moschovakis: English as a programming language? 10/22Co-ordination and co-indexing in Lλr(K )John stumbled and John fellrender−−−→