User Tools

Site Tools


t-nh-to-n-lambda-wikipedia

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

t-nh-to-n-lambda-wikipedia [2018/11/17 09:54] (current)
Line 1: Line 1:
 +<​HTML>​ <​br><​div><​p><​b>​ Phép tính Lambda </b> (cũng được viết là <b> λ-calculus </b>) là một hệ thống chính thức trong logic toán học để biểu diễn tính toán dựa trên trừu tượng hàm và ứng dụng sử dụng liên kết và thay thế biến. Nó là một mô hình tính toán phổ quát có thể được sử dụng để mô phỏng bất kỳ máy Turing nào. Nó lần đầu tiên được giới thiệu bởi nhà toán học Alonzo Church trong những năm 1930 như là một phần của nghiên cứu của ông về cơ sở của toán học.
 +</​p><​p>​ Phép tính Lambda bao gồm việc xây dựng các thuật ngữ lambda và thực hiện các phép toán giảm trên chúng. Trong dạng đơn giản nhất của phép tính lambda, các thuật ngữ được xây dựng chỉ sử dụng các quy tắc sau:
 +</p>
 +<table class="​wikitable"><​tbody><​tr><​th>​ Cú pháp </th>
 +<th> Tên </th>
 +<th> Mô tả
 +</​th></​tr><​tr><​td>​ x </td>
 +<td> Biến </td>
 +<td> Một ký tự hoặc chuỗi đại diện cho một tham số hoặc giá trị toán học / logic
 +</​td></​tr><​tr><​td>​ (λx.M) </td>
 +<td> Abstraction </td>
 +<td> Định nghĩa hàm (M là một thuật ngữ lambda). Biến x bị ràng buộc trong biểu thức.
 +</​td></​tr><​tr><​td>​ (M N) </td>
 +<td> Ứng dụng </td>
 +<td> Áp dụng một hàm vào một đối số. M và N là các thuật ngữ lambda.
 +</​td></​tr></​tbody></​table><​p>​ sản xuất các biểu thức như: (λ <i> x </i>. <i> y </i>. (Λ <i> z </i>. (Λ <i> x </i>. <i> zx </i>) (λ <i> yz y </​i>​)) (<i> xy </​i>​)). Dấu ngoặc đơn có thể bị bỏ nếu biểu thức rõ ràng. Đối với một số ứng dụng, có thể bao gồm các thuật ngữ cho các hằng số logic và toán học.
 +</​p><​p>​ Các hoạt động giảm bao gồm:
 +</p>
 +<table class="​wikitable"><​tbody><​tr><​th>​ Hoạt động </th>
 +<th> Tên </th>
 +<th> Mô tả
 +</​th></​tr><​tr><​td>​ (λx.M [x]) → (λy.M [y]) </td>
 +<td> α-chuyển đổi </td>
 +<td> Đổi tên các biến (chính thức) bị ràng buộc trong biểu thức. Được sử dụng để tránh xung đột tên.
 +</​td></​tr><​tr><​td>​ ((λx.M) E) → (M [x:=E]) </td>
 +<td> β-giảm </td>
 +<td> Thay thế biến bị ràng buộc bằng biểu thức đối số trong phần thân trừu tượng
 +</​td></​tr></​tbody></​table><​p>​ Nếu chỉ mục De Bruijn được sử dụng thì chuyển đổi α không còn cần thiết vì sẽ không có xung đột tên. Nếu áp dụng lặp đi lặp lại các bước giảm cuối cùng chấm dứt sau đó theo định lý Church-Rosser nó sẽ tạo ra một dạng beta bình thường.
 +</p>
  
 +
 +<​h2><​span class="​mw-headline"​ id="​Explanation_and_applications">​ Giải thích và ứng dụng </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h2>​
 +<p> Phép tính Lambda là Turing hoàn chỉnh, nghĩa là, nó là một mô hình tính toán phổ quát có thể được sử dụng để mô phỏng bất kỳ máy Turing nào. <sup id="​cite_ref-1"​ class="​reference">​[1]</​sup> ​ Tên gọi của nó, chữ cái lambda Hy Lạp (λ), được sử dụng trong <b> các biểu thức lambda </b> và <b> các thuật ngữ lambda </b> để biểu thị ràng buộc một biến trong một hàm.
 +</​p><​p>​ Phép tính Lambda có thể <i> không được nhập </i> hoặc <i> đã nhập </i>. Trong phép tính lambda đã nhập, các hàm chỉ có thể được áp dụng nếu chúng có khả năng chấp nhận &​quot;​kiểu dữ liệu&​quot;​ của đầu vào đã cho. Tính toán lambda được đánh máy là <i> yếu hơn tính toán lambda không định dạng là chủ đề chính của bài viết này, theo nghĩa <i> tính toán lambda đã nhập có thể diễn tả ít hơn </i> so với phép tính chưa được phân tích, nhưng trên Mặt khác tính toán lambda gõ cho phép nhiều thứ hơn để được chứng minh; trong phép tính lambda được đánh máy đơn giản, ví dụ, một định lý mà mọi chiến lược đánh giá chấm dứt cho mọi thuật ngữ lambda được nhập đơn giản, trong khi việc đánh giá các thuật ngữ lambda chưa được phân loại không cần chấm dứt. Một lý do có nhiều cách tính toán lambda khác nhau đã được mong muốn làm nhiều hơn (của những gì các giải tích untyped có thể làm) mà không từ bỏ việc có thể chứng minh định lý mạnh mẽ về tính toán.
 +</​p><​p>​ Phép tính Lambda có các ứng dụng trong nhiều lĩnh vực khác nhau trong toán học, triết học, ngôn ngữ học <sup id="​cite_ref-2"​ class="​reference">​[2]</​sup><​sup id="​cite_ref-3"​ class="​reference">​[3]</​sup><​sup id="​cite_ref-4"​ class="​reference">​[4]</​sup> ​ và khoa học máy tính. <sup id="​cite_ref-5"​ class="​reference">​[5]</​sup> ​ Phép tính Lambda đã đóng một vai trò quan trọng trong việc phát triển lý thuyết ngôn ngữ lập trình. Ngôn ngữ lập trình chức năng thực hiện phép tính lambda. <sup id="​cite_ref-6"​ class="​reference">​[6]</​sup></​p>​
 +<​h2><​span class="​mw-headline"​ id="​History">​ Lịch sử </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h2>​
 +<p> Phép tính lambda được giới thiệu bởi nhà toán học Alonzo Church vào những năm 1930 như một phần của cuộc điều tra vào <sup id="​cite_ref-7"​ class="​reference">​[7]</​sup><​sup id="​cite_ref-8"​ class="​reference">​[8]</​sup> ​ Hệ thống ban đầu được chứng minh là không nhất quán về mặt logic vào năm 1935 khi Stephen Kleene và JB Rosser phát triển nghịch lý Kleene – Rosser. <sup id="​cite_ref-9"​ class="​reference">​ [9] </​sup>​ <sup id="​cite_ref-10"​ class="​reference">​ [10] </​sup>​ [19659002] Sau đó, năm 1936 Giáo hội đã bị cô lập và xuất bản chỉ là phần liên quan đến tính toán, bây giờ được gọi là phép tính lambda chưa phân loại. <sup id="​cite_ref-11"​ class="​reference">​[11]</​sup> ​ Năm 1940, ông cũng giới thiệu một hệ thống tính toán yếu hơn, nhưng hợp lý, được gọi là lambda <sup id="​cite_ref-12"​ class="​reference">​ [12] </​sup>​ </​p><​p>​ Cho đến những năm 1960 khi mối quan hệ của nó với ngôn ngữ lập trình đã được làm rõ, λ-calculus chỉ là một hình thức. Nhờ Richard Montague và các ứng dụng ngôn ngữ học khác trong ngữ nghĩa của ngôn ngữ tự nhiên, λ-calculus đã bắt đầu tận hưởng một vị trí đáng kính trong cả ngôn ngữ học <sup id="​cite_ref-mm-linguistics_13-0"​ class="​reference">​[13]</​sup> ​ và khoa học máy tính. <sup id="​cite_ref-14"​ class="​reference">​[14]</​sup></​p>​
 +<​h2><​span class="​mw-headline"​ id="​Informal_description">​ Mô tả không chính thức </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ edit <span class="​mw-editsection-bracket">​] </​span></​span></​h2>​
 +<​h3><​span class="​mw-headline"​ id="​Motivation">​ Động lực </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ chỉnh sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h3>​
 +<p> Các hàm có tính toán là một khái niệm cơ bản trong khoa học máy tính và toán học. Phép tính provides cung cấp một ngữ nghĩa đơn giản cho tính toán, cho phép các thuộc tính tính toán được nghiên cứu một cách chính thức. Λ-calculus kết hợp hai đơn giản hóa làm cho ngữ nghĩa này trở nên đơn giản.
 +Việc đơn giản hóa đầu tiên là λ-calculus xử lý các hàm &​quot;​nặc danh&​quot;,​ mà không cho chúng tên rõ ràng. Ví dụ, hàm
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle operatorname {square_sum} (x,​y)=x^{2}+y^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-OP MJX-fixedlimits"><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ q </​mi><​mi mathvariant="​normal">​ u </​mi><​mi mathvariant="​normal">​ a </​mi><​mi mathvariant="​normal">​ r </​mi><​mi mathvariant="​normal">​ e </​mi><​mi mathvariant="​normal">​ _ <!-- _ --> </​mi><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ u </​mi><​mi mathvariant="​normal">​ m </​mi></​mrow><​mo>​ ⁡ <!-- ⁡ --></​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo></​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ operatorname { square ​ _sum} (x, y) = x ^ {2} + y ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6020e0858d923aa15ab308584dac8af2d003b879"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​27.732ex;​ height:​3.176ex;"​ alt=" { displaystyle ​ operatorname {square ​ _sum} (x, y) = x ^ {2} + y ^ { 2}} "/></​span></​dd></​dl><​p>​ có thể được viết lại ở <i> dạng ẩn danh </i> là
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,y)mapsto x^{2}+y^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo></​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup></​mstyle></​mrow>​ { displaystyle (x, y)  mapsto x ^ {2} + y ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​89bf7c479bc1935d1ddd0519cde149591d0e541b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​16.382ex;​ height:​3.176ex;"​ alt=" { displaystyle (x, y)  mapsto x ^ {2} + y ^ {2}} "/></​span></​dd></​dl><​p>​ (được đọc là &​quot;​một bộ <span class="​texhtml mvar" style="​font-style:​italic;">​ x </​span>​ và <span class="​texhtml mvar" style="​font-style:​italic;">​ y </​span>​ là <a href="​http://​en.wikipedia.org/​wiki/​Map_(mathematics)"​ title="​Map (mathematics)">​ được ánh xạ tới <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle x^{2}+y^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 [19659071] { textstyle x ^ {2} + y ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​2acda359ee232e747298436227bc8bee4ef82203"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​7.439ex;​ height:​2.843ex;"​ alt=" { textstyle x ^ {2} + y ^ {2}} "/></​span>​ &​quot;​). Tương tự,
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle operatorname {id} (x)=x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ id </​mi><​mo>​ ⁡ <!-- ⁡ --></​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ operatorname {id} (x) = x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​e64f26d868eb6952a36c600035ede967568c973f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​9.506ex;​ height:​2.843ex;"​ alt=" ​ operatorname {id} (x) = x "/></​span></​dd></​dl><​p>​ có thể được viết lại dưới dạng ẩn danh
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle xmapsto x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x  mapsto x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​033c0ae81eaf4c65cbb0759d7aa2c4f434c00f02"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​6.273ex;​ height:​1.843ex;"​ alt=" x  mapsto x "/></​span></​dd></​dl><​p>​ trong đó đầu vào được ánh xạ đơn giản với chính nó.
 +</​p><​p>​ Cách đơn giản thứ hai là phép tính only chỉ sử dụng các hàm của một đầu vào đơn. Một hàm bình thường yêu cầu hai đầu vào, ví dụ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle operatorname {square_sum} }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-OP MJX-fixedlimits"><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ q </​mi><​mi mathvariant="​normal">​ u </​mi><​mi mathvariant="​normal">​ a </​mi><​mi mathvariant="​normal">​ r </​mi><​mi mathvariant="​normal">​ e </​mi><​mi mathvariant="​normal">​ _ <!-- _ --> </​mi><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ u [196590123] Chức năng { textstyle ​ operatorname {square ​ _sum}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b1452ce7cbdc7fd26d4b880eddf9b28d0c4965a7"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​11.866ex;​ height:​2.009ex;"​ alt=" { textstyle ​ operatorname {square ​ _sum}} "/></​span>​có thể được làm lại thành một hàm tương đương chấp nhận một đầu vào đơn, và khi đầu ra trả về <i> một hàm khác </​i>​lần lượt chấp nhận một đầu vào đơn. Ví dụ,
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (x,y)mapsto x^{2}+y^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo></​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle (x, y)  mapsto x ^ {2} + y ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​89bf7c479bc1935d1ddd0519cde149591d0e541b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​16.382ex;​ height:​3.176ex;"​ alt=" { displaystyle (x, y)  mapsto x ^ {2} + y ^ {2}} "/></​span></​dd></​dl><​p>​ có thể được làm lại thành
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle xmapsto (ymapsto x^{2}+y^{2})}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ y </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ { displaystyle x  mapsto (y  mapsto x ^ {2} + y ^ {2})} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​012fc8f19ed14bf232ee8deefe4ae84dc507875d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​18.962ex;​ height:​3.176ex;"​ alt=" { displaystyle x  mapsto (y  mapsto x ^ {2} + y ^ {2} )} "/></​span></​dd></​dl><​p>​ Phương thức này, được gọi là <a href="​http://​en.wikipedia.org/​wiki/​Currying"​ title="​Currying">​ currying, biến đổi một hàm nhận nhiều đối số thành một chuỗi các hàm với mỗi đối số.
 +</​p><​p>​ Ứng dụng chức năng của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle operatorname {square_sum} }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-OP MJX-fixedlimits"><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ q </​mi><​mi mathvariant="​normal">​ u </​mi><​mi mathvariant="​normal">​ a </​mi><​mi mathvariant="​normal">​ r </​mi><​mi mathvariant="​normal">​ e </​mi><​mi mathvariant="​normal">​ _ <!-- _ --> </​mi><​mi mathvariant="​normal">​ s </​mi><​mi mathvariant="​normal">​ u </​mi><​mi mathvariant="​normal">​ m </​mi></​mrow></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ Chức năng { textstyle ​ operatorname {square ​ _sum}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b1452ce7cbdc7fd26d4b880eddf9b28d0c4965a7"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​11.866ex;​ height:​2.009ex;"​ alt=" { textstyle ​ operatorname {square ​ _sum}} "/></​span>​ cho các đối số (5, 2), sản lượng cùng một lúc
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle ((x,​y)mapsto x^{2}+y^{2})(5,​2)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo></​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ (</​mo><​mn>​ 5 </​mn><​mo></​mo><​mn>​ 2 </​mn><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { kiểu chữ ((x, y)  mapsto x ^ {2} + y ^ {2}) (5,2)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​928ef499250ddf3fae99e9a0e7e81bd4aa57e3b9"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​23.359ex;​ height:​3.009ex;"​ alt=" { textstyle ((x, y)  mapsto x ^ {2} + y ^ {2}) (5,2)} "/></​span>​ </dd>
 +<​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =5^{2}+2^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mo>​ = [19659189] 5 </​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mn>​ 2 </​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { textstyle = 5 ^ {2} + 2 ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​80c505b7a93daffe13a057837fb7071280cda48f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​9.727ex;​ height:​2.843ex;"​ alt=" { textstyle = 5 ^ {2} + 2 ^ {2}} "/></​span>​ </dd>
 +<​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =29}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mo>​ = </​mo><​mn>​ 29 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { textstyle = 29} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d026d595296c5d7351c05ffd86b0ffec19fe88b1"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​4.778ex;​ height:​2.176ex;"​ alt=" { textstyle = 29} "/></​span></​dd></​dl><​p>​ trong khi đánh giá phiên bản đã được yêu cầu thêm một bước
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle {Bigl (}{bigl (}xmapsto (ymapsto x^{2}+y^{2}){bigr )}(5){Bigr )}(2)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-OPEN"><​mo maxsize="​1.623em"​ minsize="​1.623em">​ (</​mo></​mrow></​mrow><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-OPEN"><​mo maxsize="​1.2em"​ minsize="​1.2em">​ (</​mo></​mrow></​mrow><​mi>​ x </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ y </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo stretchy="​false">​) </​mo><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-CLOSE"><​mo maxsize="​1.2em"​ minsize="​1.2em">​) </​mo></​mrow></​mrow><​mo stretchy="​false">​ (</​mo><​mn>​ 5 </​mn><​mo stretchy="​false">​) </​mo><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-CLOSE"><​mo maxsize="​1.623em"​ minsize="​1.623em">​) </​mo></​mrow></​mrow><​mo stretchy="​false">​ (</​mo><​mn>​ 2 </​mn><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { textstyle {  Bigl (} { bigl (} x  mapsto (y  mapsto x ^ {2} + y ^ {2}) { bigr)} (5) { Bigr)} (2)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​951bcb4894272800f3c7e53a20b4fbc1f7c5331d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.838ex; width:​29.81ex;​ height:​4.843ex;"​ alt=" { textstyle { Bigl (} { bigl (} x  mapsto (y  mapsto x ^ {2} + y ^ {2}) { bigr)} (5) { Bigr)} (2)} "/></​span>​ </dd>
 +<dd> <math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =(ymapsto 5^{2}+y^{2})(2)}">​ <span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;">​ <math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =(ymapsto 5^{2}+y^{2})(2)}">​ <​semantics>​ <mrow class="​MJX-TeXAtom-ORD">​ <mstyle displaystyle="​false"​ scriptlevel="​0">​ <mo> = </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ y </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​msup><​mn>​ 5 </​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 [19659068] + </​mo><​msup><​mi>​ y </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ (</​mo><​mn>​ 2 </​mn><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { textstyle = (y  mapsto 5 ^ {2} + y ^ {2 }) (2)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​9e02299d716372384546a46e1ad5cdc117f32949"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​19.276ex;​ height:​3.176ex;"​ alt=" { textstyle = (y  mapsto 5 ^ {2} + y ^ {2}) (2)} "/></​span>​ // định nghĩa <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ đã được sử dụng với <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle 5}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mn>​ 5 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle 5} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​29483407999b8763f0ea335cf715a6a5e809f44b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.162ex;​ height:​2.176ex;"​ alt=" 5 "/></​span>​ trong biểu thức bên trong. Điều này giống như giảm. </dd>
 +<​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =5^{2}+2^{2}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mo>​ = </​mo><​msup><​mn>​ 5 </​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​msup><​mn>​ 2 </​mn><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { textstyle = 5 ^ {2} + 2 ^ {2}} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​80c505b7a93daffe13a057837fb7071280cda48f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​9.727ex;​ height:​2.843ex;"​ alt=" { textstyle = 5 ^ {2} + 2 ^ {2}} "/></​span>​ // định nghĩa của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ đã được sử dụng với <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle 2}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mn>​ 2 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle 2} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​901fc910c19990d0dbaaefe4726ceb1a4e217a0f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.162ex;​ height:​2.176ex;"​ alt=" 2 "/></​span>​. Một lần nữa, tương tự như giảm. </dd>
 +<​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{textstyle =29}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​false"​ scriptlevel="​0"><​mo>​ = </​mo><​mn>​ 29 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { textstyle = 29} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d026d595296c5d7351c05ffd86b0ffec19fe88b1"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​4.778ex;​ height:​2.176ex;"​ alt=" { textstyle = 29} "/></​span></​dd></​dl><​p>​ để đạt được kết quả tương tự.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​The_lambda_calculus">​ Phép tính lambda </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h3>​
 +<p> Phép tính lambda bao gồm một ngôn ngữ của <b> các thuật ngữ lambda </​b>​được định nghĩa bởi một cú pháp chính thức nhất định và một tập hợp các quy tắc chuyển đổi, cho phép thao tác các điều khoản lambda. Các quy tắc chuyển đổi này có thể được xem như một lý thuyết equational hoặc như một định nghĩa hoạt động.
 +</​p><​p>​ Như đã mô tả ở trên, tất cả các hàm trong phép tính lambda là các hàm ẩn danh, không có tên. Chúng chỉ chấp nhận một biến đầu vào, với việc sử dụng currying để thực hiện các hàm với một số biến.
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Lambda_terms">​ Thuật ngữ lambda </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ Cú pháp của phép tính lambda định nghĩa một số biểu thức dưới dạng biểu thức tính toán lambda hợp lệ và một số là không hợp lệ, giống như một số chuỗi ký tự là các chương trình C hợp lệ và một số thì không. Một biểu thức tính toán lambda hợp lệ được gọi là &​quot;​thuật ngữ lambda&​quot;​.
 +</​p><​p>​ Ba quy tắc sau đây đưa ra một định nghĩa quy nạp có thể được áp dụng để xây dựng tất cả các thuật ngữ lambda hợp lệ cú pháp:
 +</p>
 +<p> Không có gì khác là thuật ngữ lambda. Vì vậy, một thuật ngữ lambda là hợp lệ nếu và chỉ nếu nó có thể thu được bằng cách áp dụng lặp đi lặp lại của ba quy tắc này. Tuy nhiên, một số dấu ngoặc đơn có thể được bỏ qua theo các quy tắc nhất định. Ví dụ, các dấu ngoặc đơn ngoài cùng thường không được viết. Xem <i> Ký hiệu </i> bên dưới.
 +</​p><​p>​ Một <b> trừu tượng lambda </b> <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xt} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6c340da553f36c8832a4a6aff7d235dd2acb760a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​4.558ex;​ height:​2.176ex;"​ alt=" ​ lambda xt "/></​span>​ là định nghĩa về ẩn danh chức năng có khả năng lấy một đầu vào đơn <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ và thay thế nó thành biểu thức <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​.
 +Do đó nó định nghĩa một hàm ẩn danh lấy <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow>​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ và trả về <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​. Ví dụ: <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x^{2}+2}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​mn>​ 2 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xx ^ {2} +2} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​775066d410c7fa3072ddad801ac74ad2f0d51bc8"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​10.106ex;​ height:​2.843ex;"​ alt=" ​ lambda xx ^ {2} +2 "/></​span>​ là trừu tượng lambda cho hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(x)=x^{2}+2}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ f </​mi><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​msup><​mi>​ x </​mi><​mrow class="​MJX-TeXAtom-ORD"><​mn>​ 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​mn>​ 2 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle f (x) = x ^ {2} +2} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​36b2fad9afa6bfc8ab4f81a413ebf4e9ba7f9117"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​13.903ex;​ height:​3.176ex;"​ alt=" f (x) = x ^ {2} +2 "/></​span>​ sử dụng thuật ngữ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x^{2}+2}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msup><​mi>​ x [19659067] 2 </​mn></​mrow></​msup><​mo>​ + </​mo><​mn>​ 2 </​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x ^ {2} +2} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​a4c90c2a3ab4bc8c2b353d3dc65962bc35020469"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.505ex; width:​6.387ex;​ height:​2.843ex;"​ alt=" x ^ {2} +2 "/></​span>​ cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t } </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​. Định nghĩa của một hàm có trừu tượng lambda chỉ đơn thuần là &​quot;​thiết lập&​quot;​ hàm nhưng không gọi nó. Sự trừu tượng <a href="​http://​en.wikipedia.org/​wiki/​Free_variables_and_bound_variables"​ title="​Free variables and bound variables">​ liên kết biến <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ trong thuật ngữ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​.
 +</​p><​p>​ Một ứng dụng <b> </b> <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle ts}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ts} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8dec908a9ec2ef3b707b0231f786c20c9f061aaf"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.93ex;​ height:​2.009ex;"​ alt=" ts "/></​span>​ đại diện cho ứng dụng của hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t} [19659294] t "/></​span>​ vào một đầu vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​01d131dfd7673938b947072a13a9744fe997e632"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.09ex;​ height:​1.676ex;"​ alt=" s "/></​span>​nghĩa là, nó đại diện cho hành động gọi hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t } </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​ trên đầu vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​01d131dfd7673938b947072a13a9744fe997e632"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.09ex;​ height:​1.676ex;"​ alt=" s "/></​span>​ để sản xuất <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t(s)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi><​mo stretchy="​false">​ (</​mo><​mi>​ s </​mi><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle t (s)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​abde739dff178e6e78929b3ce6870ec81e3f2d98"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​3.739ex;​ height:​2.843ex;"​ alt=" t (s) "/></​span>​.
 +</​p><​p>​ Không có khái niệm trong phép tính lambda của khai báo biến. Trong một định nghĩa như <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x+y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo>​ + </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda x.x + y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d2d683052bfe9bfd6b91fa645a2d5210d596a969"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​9.044ex;​ height:​2.509ex;"​ alt=" ​ lambda x. x + y "/></​span>​ (nghĩa là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle f(x)=x+y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ f </​mi><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mi>​ x </​mi><​mo>​ + </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle f (x) = x + y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​62f1b4363757a5a6b04d28f679be66ccdcc958cc"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​12.842ex;​ height:​2.843ex;"​ alt=" f (x) = x + y "/></​span>​),​ phép tính lambda xử lý <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ dưới dạng biến không chưa được xác định. Sự trừu tượng lambda <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x+y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo>​ + </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda x.x + y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​d2d683052bfe9bfd6b91fa645a2d5210d596a969"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​9.044ex;​ height:​2.509ex;"​ alt=" ​ lambda x.x + y "/></​span>​ có giá trị về cú pháp, và đại diện cho một hàm bổ sung đầu vào của nó vào <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ chưa được biết.
 +</​p><​p>​ Có thể sử dụng giá đỡ và có thể cần thiết để phân biệt các cụm từ. Ví dụ, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.((lambda x.x)x)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mo stretchy="​false">​ (</​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mi>​ x </​mi><​mo stretchy="​false">​ ) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda x. (( Lambda xx) x)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7aa284718745826bd142338fc1e6110582f46583"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​13.716ex;​ height:​2.843ex;"​ alt=" ​ lambda x. (( Lambda xx) x) "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.(lambda x.x))x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​) </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda x . ( lambda xx)) x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​70591fccd68750f2742e11104d56e124f0a2106f"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​13.716ex;​ height:​2.843ex;"​ alt=" ( lambda x. ( lambda xx)) x "/></​span>​ biểu thị các thuật ngữ khác nhau (mặc dù chúng trùng hợp với cùng một giá trị). Ở đây ví dụ đầu tiên định nghĩa một hàm xác định hàm và trả về kết quả của việc áp dụng x cho hàm con (hàm áp dụng sau đó trả về), trong khi ví dụ thứ hai xác định hàm trả về hàm cho bất kỳ đầu vào nào và sau đó trả về hàm trên ứng dụng của x (hàm trả về sau đó áp dụng).
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Functions_that_operate_on_functions">​ Các hàm hoạt động trên các hàm </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h4>​
 +<p> Trong phép tính lambda, các hàm được coi là &#​39;​các giá trị lớp đầu tiên&#​39;,​ vì vậy các hàm có thể được sử dụng làm đầu vào hoặc được trả về như đầu ra từ các chức năng khác.
 +</​p><​p>​ Ví dụ, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ x </​mi></​mstyle></​mrow>​ { displaystyle ​ lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​537ec33b43915b93dec1c98e433ec7a68bcab6a3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​5.049ex;​ height:​2.176ex;"​ alt=" ​ lambda xx "/></​span>​ đại diện cho hàm nhận dạng, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle xmapsto x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x  mapsto x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​033c0ae81eaf4c65cbb0759d7aa2c4f434c00f02"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​6.273ex;​ height:​1.843ex;"​ alt=" x  mapsto x "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.x)y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xx) y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b0843fde0f55684a922242d745e75e0764bf9b85"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.013ex;​ height:​2.843ex;"​ alt=" ( lambda xx) y "/></​span>​ đại diện cho hàm nhận dạng được áp dụng cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​. Hơn nữa, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.y)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xy)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8a6b3722955a98e2eb07402e0380da6d7739a5da"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​6.684ex;​ height:​2.843ex;"​ alt=" ( lambda xy) [19659095] đại diện cho hàm <b> hằng số </b> <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle xmapsto y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi><​mo stretchy="​false">​ ↦ <!-- ↦ --> </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x  mapsto y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​eb2452f2d32e5424f3db361de033fd49a73f9dcc"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​6.099ex;​ height:​2.176ex;"​ alt=" { displaystyle x  mapsto y} "/></​span>​hàm luôn trả về <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​bất kể đầu vào là gì. Trong phép tính lambda, ứng dụng chức năng được coi là <a href="​http://​en.wikipedia.org/​wiki/​Operator_associativity"​ title="​Operator associativity">​ liên kết trái, sao cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle stx}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ s </​mi><​mi>​ t </​mi><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle stx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​473aae76f793dd8a9acac4583cfea7af033751c0"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​3.26ex;​ height:​2.009ex;"​ alt=" stx "/></​span>​ có nghĩa là <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (st)x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ ( </​mo><​mi>​ s </​mi><​mi>​ t </​mi><​mo stretchy="​false">​) </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle (st) x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​37df60654b0c688f880a89e008bd71eb6cb4fd2e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.069ex;​ height:​2.843ex;"​ alt=" (st) x "/></​span>​.
 +</​p><​p>​ Có một số khái niệm về &​quot;​tương đương&​quot;​ và &​quot;​giảm&​quot;​ cho phép các thuật ngữ lambda được &​quot;​giảm&​quot;​ thành các thuật ngữ lambda &​quot;​tương đương&​quot;​.
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Alpha_equivalence">​ Tương đương Alpha </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h4>​
 +<p> Một dạng tương đương cơ bản, có thể xác định được về các thuật ngữ lambda, là tương đương alpha. Nó nắm bắt trực giác rằng sự lựa chọn cụ thể của một biến bị ràng buộc, trong trừu tượng lambda, không (thường) là vấn đề.
 +Ví dụ, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​537ec33b43915b93dec1c98e433ec7a68bcab6a3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​5.049ex;​ height:​2.176ex;"​ alt=" ​ lambda xx "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda y.y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ y </​mi><​mo>​ </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda yy} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​6491d675717cbe434705e447484c1e267743c672"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​4.7ex;​ height:​2.509ex;"​ alt=" ​ lambda yy "/></​span>​ là các thuật ngữ lambda tương đương alpha và cả hai đều đại diện cho cùng một hàm (hàm nhận dạng).
 +Các thuật ngữ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ không tương đương với alpha, vì chúng là không bị ràng buộc trong trừu tượng lambda.
 +Trong nhiều bài trình bày, thông thường phải xác định các thuật ngữ lambda tương đương alpha.
 +</​p><​p>​ Các định nghĩa sau là cần thiết để có thể xác định giảm beta:
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Free_variables">​ Biến tự do </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h4>​
 +<p> <b> biến tự do </b> của một thuật ngữ là những biến không bị ràng buộc bởi trừu tượng lambda. Tập các biến miễn phí của một biểu thức được định nghĩa một cách tự cảm:
 +</p>
 +<p> Ví dụ, thuật ngữ lambda đại diện cho danh tính <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​537ec33b43915b93dec1c98e433ec7a68bcab6a3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​5.049ex;​ height:​2.176ex;"​ alt=" ​ lambda xx "/></​span>​ không có miễn phí các biến, nhưng hàm <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.yx}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda x.yx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​00b13f7b499f19ada754e7eff1dd71dd0b5a137b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​6.204ex;​ height:​2.509ex;"​ alt=" { displaystyle ​ lambda x.yx} [19659095] có một biến tự do duy nhất, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​.
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Capture-avoiding_substitutions">​ Các thay thế cho phép chụp </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h4>​
 +<p> Giả sử <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle t} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​01d131dfd7673938b947072a13a9744fe997e632"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.09ex;​ height:​1.676ex;"​ alt=" s "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ r </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle r} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0d1ecb613aa2984f0576f70f86650b7c2a132538"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.049ex;​ height:​1.676ex;"​ alt=" r "/></​span>​ là các thuật ngữ lambda và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} [19659243] x "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ là các biến.
 +Ký hiệu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t[x:​=r]}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ r </​mi><​mo stretchy="​false">​] </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle t [x:=r]} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​18e1a37baab228f8a6915d5f6b1cf94c48188a2a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.257ex;​ height:​2.843ex;"​ alt=" t [x:=r] "/></​span>​ ] cho biết thay thế <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ r </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle r} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0d1ecb613aa2984f0576f70f86650b7c2a132538"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.049ex;​ height:​1.676ex;"​ alt=" r "/></​span>​ cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​87f9e315fd7e2ba406057a97300593c4802b53e4"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.33ex;​ height:​1.676ex;"​ alt=" x "/></​span>​ trong <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ ] { displaystyle t} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" t "/></​span>​ theo cách </i> chụp ảnh tránh </i>. Điều này được định nghĩa để:
 +</p>
 +<p> Ví dụ, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.x)[y:​=y]=lambda x.(x[y:​=y])=lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ y </​mi><​mo stretchy="​false">​ ] </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ y </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xx) [y:=y] =  lambda x. (X [y:=y]) =  lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​592caa8aa08c98d5217f7dfec3edcb5cb3521fac"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​39.661ex;​ height:​2.843ex;"​ alt=" ( lambda xx) [y:=y] =  lambda x. (X [y:=y]) =  lambda xx "/></​span>​ và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle ((lambda x.y)x)[x:​=y]=((lambda x.y)[x:​=y])(x[x:​=y])=(lambda x.y)y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​ . </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ y </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mo stretchy="​false">​ (</​mo><​mo stretchy="​false">​ ( </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ y </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ ([19659061] x </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ y </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. [19659061] </​mi><​mo stretchy="​false">​) </​mo><​mi>​ y [19659103] { displaystyle (( lambda xy) x) [x:=y] = (( lambda xy) [x:=y]) (x [x:=y]) = ( lambda xy) y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​3b294b29a663f2b54d066505b5ddafdaab77d635"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​58.063ex;​ height:​2.843ex;"​ alt=" (( lambda xy) x) [x:=y] = (( lambda xy) [x:=y]) (x [x:=y]) = ( lambda xy) y "/></​span>​.
 +</​p><​p>​ Điều kiện làm mới (yêu cầu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b8a6208ec717213d4317e666f1ae872e00620a0d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.155ex;​ height:​2.009ex;"​ alt=" y "/></​span>​ không có trong các biến miễn phí <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle r}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ r </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle r} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0d1ecb613aa2984f0576f70f86650b7c2a132538"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.049ex;​ height:​1.676ex;"​ alt=" r "/></​span>​) là rất quan trọng để đảm bảo rằng sự thay thế không thay đổi ý nghĩa của các hàm.
 +Ví dụ, một thay thế được thực hiện mà bỏ qua các điều kiện làm mới: <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.y)[y:​=x]=lambda x.(y[y:​=x])=lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ y </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ x [19659064]] </​mo><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xy) [y:=x] =  lambda x. (Y [y:=x]) =  lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​28dca32bd1aaa04013520bfac21bba12df0744a5"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​39.661ex;​ height:​2.843ex;"​ alt=" ( lambda xy) [y:=x] =  lambda x. (y [y:=x]) =  lambda xx "/></​span>​. Sự thay thế này biến hàm hằng số <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xy} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​88b2e10a12e276198f384ca3f5da934bdfaedc07"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​4.874ex;​ height:​2.509ex;"​ alt=" ​ lambda xy "/></​span>​ vào danh tính <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ [19659282] x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​537ec33b43915b93dec1c98e433ec7a68bcab6a3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​5.049ex;​ height:​2.176ex;"​ alt=" ​ lambda xx "/></​span>​ bằng cách thay thế.
 +</​p><​p>​ Nói chung, việc không đáp ứng được điều kiện làm mới có thể được khắc phục bằng cách đổi tên alpha bằng một biến mới phù hợp.
 +Ví dụ, chuyển về khái niệm thay thế chính xác của chúng ta, trong <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.y)[y:​=x]}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xy) [y:=x]} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0e113a57c201a6477f5bad7a114f70fe6a378858"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​14.208ex;​ height:​2.843ex;"​ alt=" ( lambda xy) [y:=x] "/></​span>​ trừu tượng lambda có thể được đổi tên bằng biến mới <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle z}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ z </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle z} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​bf368e72c009decd9b6686ee84a375632e11de98"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.088ex;​ height:​1.676ex;"​ alt=" z "/></​span>​để lấy <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda z.y)[y:​=x]=lambda z.(y[y:​=x])=lambda z.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ z </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ y </​mi><​mo>:​ = </​mo><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ z </​mi><​mo>​. </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ y </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ y [19659062]: = </​mo><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ z </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda zy) [y:=x] =  lambda z. (y [y:=x]) =  lambda zx} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7275d0fbddf5e54be2666eb5cb6b7baacaf00d24"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​38.936ex;​ height:​2.843ex;"​ alt=" ( lambda zy) [y:=x] =  lambda z. (y [y:=x]) =  lambda zx "/></​span>​ và ý nghĩa của chức năng được bảo toàn bằng cách thay thế.
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Beta_reduction">​ Giảm beta </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ chỉnh sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h4>​
 +<p> Quy tắc giảm beta nêu rõ rằng một ứng dụng có dạng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.t)s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ t </​mi><​mo stretchy="​false">​) </​mo><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xt) s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​56eb16cb15bc2d59d009c0b86ecd37e9ce6f7991"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​7.458ex;​ height:​2.843ex;"​ alt=" ( lambda xt) s "/></​span>​ giảm xuống còn <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t[x:​=s]}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ s </​mi><​mo stretchy="​false">​] </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle t [x:=s]} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​c69396d99d4f60dbe54641cf62b9864b0a2251e1"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.299ex;​ height:​2.843ex;"​ alt=" t [x:=s] "/></​span>​. Ký hiệu <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.t)sto t[x:​=s]}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ t </​mi><​mo stretchy="​false">​) </​mo><​mi>​ s </​mi><​mo stretchy="​false">​ → <!-- → --> </​mo><​mi>​ t </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x [19659062]: = </​mo><​mi>​ s </​mi><​mo stretchy="​false">​] </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xt) s  t [x:=s]} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8b3ec6af9a3a97d2362dd9473b3b00f414b5323e"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​19.371ex;​ height:​2.843ex;"​ alt=" ( lambda xt) s  t [x:=s] [19659095] được sử dụng để chỉ ra rằng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.t)s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ t </​mi><​mo stretchy="​false">​) </​mo><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xt) s} [19659795] ( lambda xt) s "/></​span>​ beta giảm xuống <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t[x:​=s]}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ t </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ s </​mi><​mo stretchy="​false">​] </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle t [x:=s]} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​c69396d99d4f60dbe54641cf62b9864b0a2251e1"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​8.299ex;​ height:​2.843ex;"​ alt=" t [x:=s] "/></​span>​.
 +Ví dụ, đối với mỗi <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​01d131dfd7673938b947072a13a9744fe997e632"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.09ex;​ height:​1.676ex;"​ alt=" s "/></​span><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.x)sto x[x:​=s]=s}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mo stretchy="​false">​) [19659061] s </​mi><​mo stretchy="​false">​ → <!-- → --> </​mo><​mi>​ x </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ s </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mi>​ s </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle (  lambda xx) s  đến x [x:=s] = s} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​02262c02953e5da0468ebf98f4b38327229bd4c9"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​24.54ex;​ height:​2.843ex;"​ alt=" ( lambda xx) s  thành x [x:=s] = s "/></​span>​. Điều này chứng tỏ rằng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.x}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda x.x} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​537ec33b43915b93dec1c98e433ec7a68bcab6a3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​5.049ex;​ height:​2.176ex;"​ alt=" ​ lambda x.x "/></​span>​ thực sự là danh tính.
 +Tương tự, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.y)sto y[x:​=s]=y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi><​mo stretchy="​false">​) </​mo><​mi>​ s </​mi><​mo stretchy="​false">​ → <!-- → --> </​mo><​mi>​ y </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x [19659062]: = </​mo><​mi>​ s </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda xy) s  thành y [x:=s] = y} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​de42f8231c1e95fb1556e6aee11c40d0000ea008"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​24.257ex;​ height:​2.843ex;"​ alt=" ( lambda xy) s  to y [x:=s] = y "/></​span>​thể hiện rằng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda x.y}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ y </​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​ { displaystyle ​ lambda xy} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​88b2e10a12e276198f384ca3f5da934bdfaedc07"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​4.874ex;​ height:​2.509ex;"​ alt=" ​ lambda xy "/></​span>​ là một hàm liên tục.
 +</​p><​p>​ Phép tính lambda có thể được xem như là một phiên bản lý tưởng của một ngôn ngữ lập trình hàm, như Haskell hoặc Standard ML.
 +Theo quan điểm này, giảm beta tương ứng với một bước tính toán. Bước này có thể được lặp lại bằng các chuyển đổi beta bổ sung cho đến khi không còn ứng dụng nào để giảm. Trong phép tính lambda chưa được phân loại, như được trình bày ở đây, quá trình giảm này có thể không chấm dứt.
 +Ví dụ, hãy xem xét thuật ngữ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Omega =(lambda x.xx)(lambda x.xx)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi mathvariant="​normal">​ Ω <!-- Ω --> </​mi><​mo>​ = </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ ([19659061] λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ​ Omega = ( lambda x.xx) ( lambda x.xx)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​3bfe87ff478d8ea96e37b17523c091fa9812a4ee"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​21.152ex;​ height:​2.843ex;"​ alt=" ​ Omega = ( lambda x.xx) ( lambda x.xx) "/></​span>​.
 +Ở đây <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (lambda x.xx)(lambda x.xx)to (xx)[x:​=lambda x.xx]=(x[x:​=lambda x.xx])(x[x:​=lambda x.xx])=(lambda x.xx)(lambda x.xx)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x [19659347] x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ → <!-- → --> </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo>​ = </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ x </​mi><​mo stretchy="​false">​ [</​mo><​mi>​ x </​mi><​mo>:​ = </​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x [19659062] </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt=" x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​] </​mo><​mo stretchy="​false">​) </​mo><​mo>​ = </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​ ) </​mo><​mo stretchy="​false">​ (</​mo><​mi>​ λ <!-- λ --></​mi><​mi>​ x </​mi><​mo>​. </​mo><​mi>​ x </​mi><​mi>​ x </​mi><​mo stretchy="​false">​) </​mo></​mstyle></​mrow>​ <​annotation encoding="​application/​x-tex">​ { displaystyle ( lambda x.xx) ( lambda x. xx)  đến (xx) [x:=lambda x.xx] = (x [x:=lambda x.xx]) (x [x:=lambda x.xx]) = ( lambda x.xx) ( lambda x.xx)} </​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​ba84bd0baf6c5c33e59226aa42474b36e3046231"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​91.548ex;​ height:​2.843ex;"​ alt=" ( lambda x.xx) (  lambda x.xx)  đến (xx) [x:=lambda x.xx] = (x [x:=lambda x.xx]) (x [x:=lambda x.xx]) = ( l ambda x.xx) ( lambda x.xx) "/></​span>​.
 +Tức là, thuật ngữ này tự giảm trong một bản beta đơn lẻ, và do đó quá trình giảm sẽ không bao giờ chấm dứt.
 +</​p><​p>​ Một khía cạnh khác của phép tính lambda chưa được phân loại là nó không phân biệt giữa các loại dữ liệu khác nhau.
 +Ví dụ, có thể muốn viết một hàm chỉ hoạt động trên các số. Tuy nhiên, trong phép tính lambda không định dạng, không có cách nào để ngăn chặn một hàm được áp dụng cho các giá trị chân lý, các chuỗi hoặc các đối tượng không phải số khác.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Formal_definition">​ Định nghĩa chính thức </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ chỉnh sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h2>​
 +
 +<​h3><​span class="​mw-headline"​ id="​Definition">​ Định nghĩa </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ chỉnh sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h3>​
 +<p> Biểu thức Lambda bao gồm:
 +</p>
 +<​ul><​li>​ biến v <sub> 1 </​sub>​v <sub> 2 </​sub>​...,​ v <sub> n </​sub>​... </li>
 +<li> các ký hiệu trừu tượng lambda &#​39;​λ&#​39;​ và dấu chấm &#​39;​.&#​39;​ </li>
 +<li> dấu ngoặc đơn () </​li></​ul><​p>​ Tập hợp các biểu thức lambda, Λ, có thể được định nghĩa một cách tự cảm:
 +</p>
 +<​ol><​li>​ Nếu x là một biến, thì x ∈ Λ </li>
 +<li> Nếu x là một biến và M ∈ Λ, thì (λx.M) ∈ Λ </li>
 +<li> Nếu M, N ∈ Λ, thì (MN) ∈ Λ </​li></​ol><​p>​ Các thể hiện của quy tắc 2 được gọi là trừu tượng và các trường hợp của quy tắc 3 được gọi là các ứng dụng. <sup id="​cite_ref-15"​ class="​reference">​[15]</​sup></​p>​
 +<​h3><​span class="​mw-headline"​ id="​Notation">​ Ký hiệu </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ chỉnh sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h3>​
 +<p> Để giữ ký hiệu của các biểu thức lambda gọn gàng, các quy ước sau đây thường được áp dụng:
 +</p>
 +<​ul><​li>​ Dấu ngoặc đơn bên ngoài bị giảm: MN thay vì (MN) </li>
 +<li> Ứng dụng được giả định là liên kết bên trái: MNP có thể được viết thay vì ((MN) P) <sup id="​cite_ref-lambda-bound_16-0"​ class="​reference">​ [16] </​sup>​ </li>
 +<li> cơ thể của một trừu tượng kéo dài càng xa càng tốt: λx.MN nghĩa là λx. (MN) và không (λx.M) N </li>
 +<li> Một chuỗi các trừu tượng được ký hợp đồng: λx.λy.λz.N được viết tắt là λxyz. N <sup id="​cite_ref-Selinger_17-0"​ class="​reference">​[17]</​sup><​sup id="​cite_ref-lambda-bound_16-1"​ class="​reference">​[16]</​sup></​li></​ul><​h3><​span class="​mw-headline"​ id="​Free_and_bound_variables">​ Biến tự do và bị ràng buộc </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h3>​
 +<p> Toán tử trừu tượng, is, được cho là ràng buộc biến của nó bất cứ nơi nào nó xuất hiện trong thân trừu tượng. Các biến nằm trong phạm vi trừu tượng được cho là <i> bị ràng buộc </i>. Tất cả các biến khác được gọi là <i> miễn phí </i>. Ví dụ, trong biểu thức <tt> λ <i> y </i>. <i> x </i> <i> x </i> <i> y </​i></​tt>​y là biến bị ràng buộc và x là miễn phí. Cũng lưu ý rằng một biến bị ràng buộc bởi sự trừu tượng &​quot;​gần nhất&​quot;​ của nó. Trong ví dụ sau, sự xuất hiện đơn của x trong biểu thức bị ràng buộc bởi lambda thứ hai: <tt> λ <i> x </i>. <i> y </i> (λ <i> x </i>. <i> z </i> <i> x </i>) </tt>
 +</​p><​p>​ Tập hợp các <i> biến tự do </i> của một biểu thức lambda, M, được ký hiệu là FV (M) và được xác định bằng đệ quy về cấu trúc của các thuật ngữ, như sau:
 +</p>
 +<​ol><​li>​ FV (x) = {x}, trong đó x là một biến </li>
 +<li> FV (λx.M) = FV (M)  {x} </li>
 +<li> FV (MN) = FV (M) ∪ FV ( N) <sup id="​cite_ref-BarendregtBarendsen_18-0"​ class="​reference">​ [18] </​sup>​ </​li></​ol><​p>​ Cụm từ không chứa biến số miễn phí được cho là <i> đã đóng </i>. Các biểu thức lambda khép kín còn được gọi là các combinator và tương đương với các từ trong logic kết hợp.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Reduction">​ Giảm </​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​ [</​span>​ sửa <span class="​mw-editsection-bracket">​] </​span></​span></​h2>​
 +<p> Ý nghĩa của biểu thức lambda được xác định bằng cách biểu thức có thể được giảm. <sup id="​cite_ref-19"​ class="​reference">​ [19] </​sup>​ </​p><​p>​ Có ba loại giảm:
 +</p>
 +<​ul><​li>​ <b> α-conversion </b>: thay đổi các biến bị ràng buộc (<b> alpha </​b>​);​ </li>
 +<li> <b> β-reduction </b>: áp dụng hàm cho đối số của chúng (<b> beta </​b>​);</​li>​
 +<​li><​b>​η-conversion</​b>:​ which captures a notion of extensionality (<​b>​eta</​b>​).</​li></​ul><​p>​We also speak of the resulting equivalences:​ two expressions are <i> β-equivalent</​i>​if they can be β-converted into the same expression, and α/​η-equivalence are defined similarly.
 +</​p><​p>​The term <​i>​redex</​i>​short for <​i>​reducible expression</​i>​refers to subterms that can be reduced by one of the reduction rules. For example, <​tt>​(λ<​i>​x</​i>​.M) N</​tt>​ is a beta-redex in expressing the substitution of N for x in M. The expression to which a redex reduces is called its reduct; the reduct of <​tt>​(λ<​i>​x</​i>​.M) N</​tt>​ is <​tt>​M[<​i>​x</​i>:​=N]</​tt>​.
 +</​p><​p>​If <​tt><​i>​x</​i></​tt>​ is not free in <​tt>​M</​tt><​tt>​λ<​i>​x</​i>​.M <​i>​x</​i></​tt>​ is also an eta-redex, with a reduct of <​tt>​M</​tt>​.
 +</p>
 +<​h3><​span id="​.CE.B1-conversion"/><​span class="​mw-headline"​ id="​α-conversion">​α-conversion</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Alpha-conversion,​ sometimes known as alpha-renaming,<​sup id="​cite_ref-20"​ class="​reference">​[20]</​sup>​ allows bound variable names to be changed. For example, alpha-conversion of <​tt>​λ<​i>​x</​i>​.<​i>​x</​i></​tt>​ might yield <​tt>​λ<​i>​y</​i>​.<​i>​y</​i></​tt>​. Terms that differ only by alpha-conversion are called <​i>​α-equivalent</​i>​. Frequently, in uses of lambda calculus, α-equivalent terms are considered to be equivalent.
 +</​p><​p>​The precise rules for alpha-conversion are not completely trivial. First, when alpha-converting an abstraction,​ the only variable occurrences that are renamed are those that are bound to the same abstraction. For example, an alpha-conversion of <​tt>​λ<​i>​x</​i>​.λ<​i>​x</​i>​.<​i>​x</​i></​tt>​ could result in <​tt>​λ<​i>​y</​i>​.λ<​i>​x</​i>​.<​i>​x</​i></​tt>​but it could <​i>​not</​i>​ result in <​tt>​λ<​i>​y</​i>​.λ<​i>​x</​i>​.<​i>​y</​i></​tt>​. The latter has a different meaning from the original. This is analogous to the programming notion of variable shadowing.
 +</​p><​p>​Second,​ alpha-conversion is not possible if it would result in a variable getting captured by a different abstraction. For example, if we replace <​tt><​i>​x</​i></​tt>​ with <​tt><​i>​y</​i></​tt>​ in <​tt>​λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i></​tt>​we get <​tt>​λ<​i>​y</​i>​.λ<​i>​y</​i>​.<​i>​y</​i></​tt>​which is not at all the same.
 +</​p><​p>​In programming languages with static scope, alpha-conversion can be used to make name resolution simpler by ensuring that no variable name masks a name in a containing scope (see alpha renaming to make name resolution trivial).
 +</​p><​p>​In the De Bruijn index notation, any two alpha-equivalent terms are syntactically identical.
 +</p>
 +<​h4><​span class="​mw-headline"​ id="​Substitution">​Substitution</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h4>​
 +<​p>​Substitution,​ written <span class="​monospaced"><​i>​E</​i>​[<​i>​V</​i>​ :​= <​i>​R</​i>​]</​span>​is the process of replacing all free occurrences of the variable <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced"><​i>​V</​i></​span>​ in the expression <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced"><​i>​E</​i></​span>​ with expression <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced"><​i>​R</​i></​span>​.
 +Substitution on terms of the λ-calculus is defined by recursion on the structure of terms, as follows (note: x and y are only variables while M and N are any λ expression).
 +</p>
 +<​pre><​i>​x</​i>​[<​i>​x</​i>​ :​= N] ≡ N
 +<​i>​y</​i>​[<​i>​x</​i>​ :​= N] ≡ <​i>​y</​i>​if <​i>​x</​i>​ ≠ <​i>​y</​i>​
 +(M<​sub>​1</​sub>​ M<​sub>​2</​sub>​)[<​i>​x</​i>​ :​= N] ≡ (M<​sub>​1</​sub>​[<​i>​x</​i>​ :​= N]) (M<​sub>​2</​sub>​[<​i>​x</​i>​ :​= N])
 +(λ<​i>​x</​i>​.M)[<​i>​x</​i>​ :​= N] ≡ λ<​i>​x</​i>​.M
 +(λ<​i>​y</​i>​.M)[<​i>​x</​i>​ :​= N] ≡ λ<​i>​y</​i>​.(M[<​i>​x</​i>​ :​= N]), if <​i>​x</​i>​ ≠ <​i>​y</​i><​i>​provided</​i>​ <​i>​y</​i>​ ∉ FV(N)
 +</​pre>​
 +<p>To substitute into a lambda abstraction,​ it is sometimes necessary to α-convert the expression. For example, it is not correct for <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced">​(λ<​i>​x</​i>​.<​i>​y</​i>​)[<​i>​y</​i>​ :​= <​i>​x</​i>​]</​span>​ to result in <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced">​(λ<​i>​x</​i>​.<​i>​x</​i>​)</​span>​because the substituted <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced"><​i>​x</​i></​span>​ was supposed to be free but ended up being bound. The correct substitution in this case is <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861301850"/><​span class="​monospaced">​(λ<​i>​z</​i>​.<​i>​x</​i>​)</​span>​up to α-equivalence. Notice that substitution is defined uniquely up to α-equivalence.
 +</p>
 +<​h3><​span id="​.CE.B2-reduction"/><​span class="​mw-headline"​ id="​β-reduction">​β-reduction</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Beta-reduction captures the idea of function application. Beta-reduction is defined in terms of substitution:​ the beta-reduction of <​tt>​ ((λ<​i>​V</​i>​.<​i>​E</​i>​) <​i>​E′</​i>​) </​tt>​ is <​tt><​i>​E</​i>​[<​i>​V</​i>​ :​= <​i>​E′</​i>​]</​tt>​.
 +</​p><​p>​For example, assuming some encoding of <​tt>​2,​ 7, ×</​tt>​we have the following β-reduction:​ <​tt>​((λ<​i>​n</​i>​.<​i>​n</​i>​×2) 7) </​tt>​→<​tt>​ 7×2</​tt>​.
 +</p>
 +<​h3><​span id="​.CE.B7-conversion"/><​span class="​mw-headline"​ id="​η-conversion">​η-conversion</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Eta-conversion expresses the idea of extensionality,​ which in this context is that two functions are the same if and only if they give the same result for all arguments. Eta-conversion converts between <​tt>​λ<​i>​x</​i>​.(<​i>​f</​i>​ <​i>​x</​i>​)</​tt>​ and <​tt><​i>​f</​i></​tt>​ whenever <​tt><​i>​x</​i></​tt>​ does not appear free in <​tt><​i>​f</​i></​tt>​.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Normal_forms_and_confluence">​Normal forms and confluence</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +
 +<​p>​For the untyped lambda calculus, β-reduction as a rewriting rule is neither strongly normalising nor weakly normalising.
 +</​p><​p>​However,​ it can be shown that β-reduction is confluent. (Of course, we are working up to α-conversion,​ i.e. we consider two normal forms to be equal, if it is possible to α-convert one into the other.)
 +</​p><​p>​Therefore,​ both strongly normalising terms and weakly normalising terms have a unique normal form. For strongly normalising terms, any reduction strategy is guaranteed to yield the normal form, whereas for weakly normalising terms, some reduction strategies may fail to find it.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Encoding_datatypes">​Encoding datatypes</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +
 +<​p>​The basic lambda calculus may be used to model booleans, arithmetic, data structures and recursion, as illustrated in the following sub-sections.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Arithmetic_in_lambda_calculus">​Arithmetic in lambda calculus</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​There are several possible ways to define the natural numbers in lambda calculus, but by far the most common are the Church numerals, which can be defined as follows:
 +</p>
 +<​dl><​dd><​tt>​0 :​= λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​x</​i></​tt></​dd>​
 +<​dd><​tt>​1 :​= λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​f</​i>​ <​i>​x</​i></​tt></​dd>​
 +<​dd><​tt>​2 :​= λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​f</​i>​ (<​i>​f</​i>​ <​i>​x</​i>​)</​tt></​dd>​
 +<​dd><​tt>​3 :​= λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​f</​i>​ (<​i>​f</​i>​ (<​i>​f</​i>​ <​i>​x</​i>​))</​tt></​dd></​dl><​p>​and so on. Or using the alternative syntax presented above in <​i>​Notation</​i>:​
 +</p>
 +<​dl><​dd><​tt>​0 :​= λ<​i>​fx</​i>​.<​i>​x</​i></​tt></​dd>​
 +<​dd><​tt>​1 :​= λ<​i>​fx</​i>​.<​i>​f</​i>​ <​i>​x</​i></​tt></​dd>​
 +<​dd><​tt>​2 :​= λ<​i>​fx</​i>​.<​i>​f</​i>​ (<​i>​f</​i>​ <​i>​x</​i>​)</​tt></​dd>​
 +<​dd><​tt>​3 :​= λ<​i>​fx</​i>​.<​i>​f</​i>​ (<​i>​f</​i>​ (<​i>​f</​i>​ <​i>​x</​i>​))</​tt></​dd></​dl><​p>​A Church numeral is a higher-order function—it takes a single-argument function <​tt><​i>​f</​i></​tt>​and returns another single-argument function. The Church numeral <​tt><​i>​n</​i></​tt>​ is a function that takes a function <​tt><​i>​f</​i></​tt>​ as argument and returns the <​tt><​i>​n</​i></​tt>​-th composition of <​tt><​i>​f</​i></​tt>​i.e. the function <​tt><​i>​f</​i></​tt>​ composed with itself <​tt><​i>​n</​i></​tt>​ times. This is denoted <​tt><​i>​f</​i><​sup>​(<​i>​n</​i>​)</​sup></​tt>​ and is in fact the <​tt><​i>​n</​i></​tt>​-th power of <​tt><​i>​f</​i></​tt>​ (considered as an operator); <​tt><​i>​f</​i><​sup>​(0)</​sup></​tt>​ is defined to be the identity function. Such repeated compositions (of a single function <​tt><​i>​f</​i></​tt>​) obey the laws of exponents, which is why these numerals can be used for arithmetic. (In Church&#​39;​s original lambda calculus, the formal parameter of a lambda expression was required to occur at least once in the function body, which made the above definition of <​tt>​0</​tt>​ impossible.)
 +</​p><​p>​One way of thinking about the Church numeral <​tt><​i>​n</​i></​tt>​which is often useful when analysing programs, is as an instruction &#​39;​repeat <​i>​n</​i>​ times&#​39;​. For example, using the <​tt>​PAIR</​tt>​ and <​tt>​NIL</​tt>​ functions defined below, one can define a function that constructs a (linked) list of <​i>​n</​i>​ elements all equal to <​i>​x</​i>​ by repeating &#​39;​prepend another <​i>​x</​i>​ element&#​39;​ <​i>​n</​i>​ times, starting from an empty list. The lambda term is
 +</p>
 +<​dl><​dd><​tt>​λ<​i>​n</​i>​.λ<​i>​x</​i>​.<​i>​n</​i>​ (PAIR <​i>​x</​i>​) NIL</​tt></​dd></​dl><​p>​By varying what is being repeated, and varying what argument that function being repeated is applied to, a great many different effects can be achieved.
 +</​p><​p>​We can define a successor function, which takes a Church numeral <​tt><​i>​n</​i></​tt>​ and returns <​tt><​i>​n</​i>​ + 1</​tt>​ by adding another application of <​tt><​i>​f</​i></​tt>​where &#​39;​(mf)x&#​39;​ means the function &#​39;​f&#​39;​ is applied &#​39;​m&#​39;​ times on &#​39;​x&#​39;:​
 +</p>
 +<​dl><​dd><​tt>​SUCC :​= λ<​i>​n</​i>​.λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​f</​i>​ (<​i>​n</​i>​ <​i>​f</​i>​ <​i>​x</​i>​)</​tt></​dd></​dl><​p>​Because the <​tt><​i>​m</​i></​tt>​-th composition of <​tt><​i>​f</​i></​tt>​ composed with the <​tt><​i>​n</​i></​tt>​-th composition of <​tt><​i>​f</​i></​tt>​ gives the <​tt><​i>​m</​i>​+<​i>​n</​i></​tt>​-th composition of <​tt><​i>​f</​i></​tt>​addition can be defined as follows:
 +</p>
 +<​dl><​dd><​tt>​PLUS :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​m</​i>​ <​i>​f</​i>​ (<​i>​n</​i>​ <​i>​f</​i>​ <​i>​x</​i>​)</​tt></​dd></​dl><​p><​tt>​PLUS</​tt>​ can be thought of as a function taking two natural numbers as arguments and returning a natural number; it can be verified that
 +</p>
 +<​dl><​dd><​tt>​PLUS 2 3</​tt></​dd></​dl><​p>​and
 +</p>
 +<​dl><​dd><​tt>​5</​tt></​dd></​dl><​p>​are β-equivalent lambda expressions. Since adding <​tt><​i>​m</​i></​tt>​ to a number <​tt><​i>​n</​i></​tt>​ can be accomplished by adding 1 <​tt><​i>​m</​i></​tt>​ times, an alternative definition is:
 +</p>
 +<​dl><​dd><​tt>​PLUS :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.<​i>​m</​i>​ SUCC <​i>​n </​i></​tt><​sup id="​cite_ref-21"​ class="​reference">​[21]</​sup></​dd></​dl><​p>​Similarly,​ multiplication can be defined as
 +</p>
 +<​dl><​dd><​tt>​MULT :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.λ<​i>​f</​i>​.<​i>​m</​i>​ (<​i>​n</​i>​ <​i>​f</​i>​)</​tt><​sup id="​cite_ref-Selinger_17-1"​ class="​reference">​[17]</​sup></​dd></​dl><​p>​Alternatively
 +</p>
 +<​dl><​dd><​tt>​MULT :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.<​i>​m</​i>​ (PLUS <​i>​n</​i>​) 0</​tt></​dd></​dl><​p>​since multiplying <​tt><​i>​m</​i></​tt>​ and <​tt><​i>​n</​i></​tt>​ is the same as repeating the add <​tt><​i>​n</​i></​tt>​ function <​tt><​i>​m</​i></​tt>​ times and then applying it to zero.
 +Exponentiation has a rather simple rendering in Church numerals, namely
 +</p>
 +<​dl><​dd><​tt>​POW :​= λ<​i>​b</​i>​.λ<​i>​e</​i>​.<​i>​e</​i>​ <​i>​b</​i></​tt><​sup class="​noprint Inline-Template Template-Fact"​ style="​white-space:​nowrap;">​[<​i><​span title="​This claim needs references to reliable sources. (September 2017)">​citation needed</​span></​i>​]</​sup></​dd></​dl><​p>​The predecessor function defined by <​tt>​PRED <​i>​n</​i>​ = <​i>​n</​i>​ − 1</​tt>​ for a positive integer <​tt><​i>​n</​i></​tt>​ and <​tt>​PRED 0 = 0</​tt>​ is considerably more difficult. The formula
 +</p>
 +<​dl><​dd><​tt>​PRED :​= λ<​i>​n</​i>​.λ<​i>​f</​i>​.λ<​i>​x</​i>​.<​i>​n</​i>​ (λ<​i>​g</​i>​.λ<​i>​h</​i>​.<​i>​h</​i>​ (<​i>​g</​i>​ <​i>​f</​i>​)) (λ<​i>​u</​i>​.<​i>​x</​i>​) (λ<​i>​u</​i>​.<​i>​u</​i>​)</​tt></​dd></​dl><​p>​can be validated by showing inductively that if <​i>​T</​i>​ denotes <​tt>​(λ<​i>​g</​i>​.λ<​i>​h</​i>​.<​i>​h</​i>​ (<​i>​g</​i>​ <​i>​f</​i>​))</​tt>​then <​tt>​T<​sup>​(<​i>​n</​i>​)</​sup>​(λ<​i>​u</​i>​.<​i>​x</​i>​) = (λ<​i>​h</​i>​.<​i>​h</​i>​(<​i>​f</​i><​sup>​(<​i>​n</​i>​−1)</​sup>​(<​i>​x</​i>​)))</​tt>​ for <​tt><​i>​n</​i>​ &gt; 0</​tt>​. Two other definitions of <​tt>​PRED</​tt>​ are given below, one using conditionals and the other using pairs. With the predecessor function, subtraction is straightforward. Defining
 +</p>
 +<​dl><​dd><​tt>​SUB :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.<​i>​n</​i>​ PRED <​i>​m</​i></​tt>,</​dd></​dl><​p><​tt>​SUB <​i>​m</​i>​ <​i>​n</​i></​tt>​ yields <​tt><​i>​m</​i>​ − <​i>​n</​i></​tt>​ when <​tt><​i>​m</​i>​ &gt; <​i>​n</​i></​tt>​ and <​tt>​0</​tt>​ otherwise.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Logic_and_predicates">​Logic and predicates</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<p>By convention, the following two definitions (known as Church booleans) are used for the boolean values <​tt>​TRUE</​tt>​ and <​tt>​FALSE</​tt>:​
 +</p>
 +<​dl><​dd><​tt>​TRUE :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i></​tt></​dd>​
 +<​dd><​tt>​FALSE :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​y</​i></​tt>​
 +<​dl><​dd>​(Note that <​tt>​FALSE</​tt>​ is equivalent to the Church numeral zero defined above)</​dd></​dl></​dd></​dl><​p>​Then,​ with these two λ-terms, we can define some logic operators (these are just possible formulations;​ other expressions are equally correct):
 +</p>
 +<​dl><​dd><​tt>​AND :​= λ<​i>​p</​i>​.λ<​i>​q</​i>​.<​i>​p</​i>​ <​i>​q</​i>​ <​i>​p</​i></​tt></​dd>​
 +<​dd><​tt>​OR :​= λ<​i>​p</​i>​.λ<​i>​q</​i>​.<​i>​p</​i>​ <​i>​p</​i>​ <​i>​q</​i></​tt></​dd>​
 +<​dd><​tt>​NOT :​= λ<​i>​p</​i>​.p FALSE TRUE</​tt></​dd>​
 +<​dd><​tt>​IFTHENELSE :​= λ<​i>​p</​i>​.λ<​i>​a</​i>​.λ<​i>​b</​i>​.<​i>​p</​i>​ <​i>​a</​i>​ <​i>​b</​i></​tt></​dd></​dl><​p>​We are now able to compute some logic functions, for example:
 +</p>
 +<​dl><​dd><​tt>​AND TRUE FALSE</​tt>​
 +<​dl><​dd><​tt>​≡ (λ<​i>​p</​i>​.λ<​i>​q</​i>​.<​i>​p</​i>​ <​i>​q</​i>​ <​i>​p</​i>​) TRUE FALSE →<​sub>​β</​sub>​ TRUE FALSE TRUE</​tt></​dd>​
 +<​dd><​tt>​≡ (λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i>​) FALSE TRUE →<​sub>​β</​sub> ​ FALSE</​tt></​dd></​dl></​dd></​dl><​p>​and we see that <​tt>​AND TRUE FALSE</​tt>​ is equivalent to <​tt>​FALSE</​tt>​.
 +</​p><​p>​A <​i>​predicate</​i>​ is a function that returns a boolean value. The most fundamental predicate is <​tt>​ISZERO</​tt>​which returns <​tt>​TRUE</​tt>​ if its argument is the Church numeral <​tt>​0</​tt>​and <​tt>​FALSE</​tt>​ if its argument is any other Church numeral:
 +</p>
 +<​dl><​dd><​tt>​ISZERO :​= λ<​i>​n</​i>​.<​i>​n</​i>​ (λ<​i>​x</​i>​.FALSE) TRUE</​tt></​dd></​dl><​p>​The following predicate tests whether the first argument is less-than-or-equal-to the second:
 +</p>
 +<​dl><​dd><​tt>​LEQ :​= λ<​i>​m</​i>​.λ<​i>​n</​i>​.ISZERO (SUB <​i>​m</​i>​ <​i>​n</​i>​)</​tt>,</​dd></​dl><​p>​and since <​tt><​i>​m</​i>​ = <​i>​n</​i></​tt>​if <​tt>​LEQ <​i>​m</​i>​ <​i>​n</​i></​tt>​ and <​tt>​LEQ <​i>​n</​i>​ <​i>​m</​i></​tt>​it is straightforward to build a predicate for numerical equality.
 +</​p><​p>​The availability of predicates and the above definition of <​tt>​TRUE</​tt>​ and <​tt>​FALSE</​tt>​ make it convenient to write &​quot;​if-then-else&​quot;​ expressions in lambda calculus. For example, the predecessor function can be defined as:
 +</p>
 +<​dl><​dd><​tt>​PRED :​= λ<​i>​n</​i>​.<​i>​n</​i>​ (λ<​i>​g</​i>​.λ<​i>​k</​i>​.ISZERO (<​i>​g</​i>​ 1) <​i>​k</​i>​ (PLUS (<​i>​g</​i>​ <​i>​k</​i>​) 1)) (λ<​i>​v</​i>​.0) 0 </​tt></​dd></​dl><​p>​which can be verified by showing inductively that <​tt><​i>​n</​i>​ (λ<​i>​g</​i>​.λ<​i>​k</​i>​.ISZERO (<​i>​g</​i>​ 1) <​i>​k</​i>​ (PLUS (<​i>​g</​i>​ <​i>​k</​i>​) 1)) (λ<​i>​v</​i>​.0)</​tt>​ is the add <​tt><​i>​n</​i></​tt>​ − 1 function for <​tt><​i>​n</​i></​tt>​ &gt; 0.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Pairs">​Pairs</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<p>A pair (2-tuple) can be defined in terms of <​tt>​TRUE</​tt>​ and <​tt>​FALSE</​tt>​by using the Church encoding for pairs. For example, <​tt>​PAIR</​tt>​ encapsulates the pair (<​tt><​i>​x</​i></​tt>,<​tt><​i>​y</​i></​tt>​),​ <​tt>​FIRST</​tt>​ returns the first element of the pair, and <​tt>​SECOND</​tt>​ returns the second.
 +</p>
 +<​dl><​dd><​tt>​PAIR :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.λ<​i>​f</​i>​.<​i>​f</​i>​ <​i>​x</​i>​ <​i>​y</​i></​tt></​dd>​
 +<​dd><​tt>​FIRST :​= λ<​i>​p</​i>​.<​i>​p</​i>​ TRUE</​tt></​dd>​
 +<​dd><​tt>​SECOND :​= λ<​i>​p</​i>​.<​i>​p</​i>​ FALSE</​tt></​dd>​
 +<​dd><​tt>​NIL :​= λ<​i>​x</​i>​.TRUE </​tt></​dd>​
 +<​dd><​tt>​NULL :​= λ<​i>​p</​i>​.<​i>​p</​i>​ (λ<​i>​x</​i>​.λ<​i>​y</​i>​.FALSE)</​tt></​dd></​dl><​p>​A linked list can be defined as either NIL for the empty list, or the <​tt>​PAIR</​tt>​ of an element and a smaller list. The predicate <​tt>​NULL</​tt>​ tests for the value <​tt>​NIL</​tt>​. (Alternatively,​ with <​tt>​NIL :​= FALSE</​tt>​the construct <​tt><​i>​l</​i>​ (λ<​i>​h</​i>​.λ<​i>​t</​i>​.λ<​i>​z</​i>​.deal_with_head_<​i>​h</​i>​_and_tail_<​i>​t</​i>​) (deal_with_nil)</​tt>​ obviates the need for an explicit NULL test).
 +</​p><​p>​As an example of the use of pairs, the shift-and-increment function that maps <​tt>​(<​i>​m</​i><​i>​n</​i>​)</​tt>​ to <​tt>​(<​i>​n</​i><​i>​n</​i>​ + 1)</​tt>​ can be defined as
 +</p>
 +<​dl><​dd><​tt>​Φ :​= λ<​i>​x</​i>​.PAIR (SECOND <​i>​x</​i>​) (SUCC (SECOND <​i>​x</​i>​))</​tt></​dd></​dl><​p>​which allows us to give perhaps the most transparent version of the predecessor function:
 +</p>
 +<​dl><​dd><​tt>​PRED :​= λ<​i>​n</​i>​.FIRST (<​i>​n</​i>​ Φ (PAIR 0 0)).</​tt></​dd></​dl><​h2><​span class="​mw-headline"​ id="​Additional_programming_techniques">​Additional programming techniques</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​There is a considerable body of programming idioms for lambda calculus. Many of these were originally developed in the context of using lambda calculus as a foundation for programming language semantics, effectively using lambda calculus as a low-level programming language. Because several programming languages include the lambda calculus (or something very similar) as a fragment, these techniques also see use in practical programming,​ but may then be perceived as obscure or foreign.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Named_constants">​Named constants</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<p>In lambda calculus, a library would take the form of a collection of previously defined functions, which as lambda-terms are merely particular constants. The pure lambda calculus does not have a concept of named constants since all atomic lambda-terms are variables, but one can emulate having named constants by setting aside a variable as the name of the constant, using lambda-abstraction to bind that variable in the main body, and apply that lambda-abstraction to the intended definition. Thus to use <​tt><​i>​f</​i></​tt>​ to mean <​i>​M</​i>​ (some explicit lambda-term) in <​i>​N</​i>​ (another lambda-term,​ the &​quot;​main program&​quot;​),​ one can say
 +</p>
 +<​dl><​dd><​tt>​(λ<​i>​f</​i>​.</​tt><​i>​N</​i><​tt>​)</​tt>​ <​i>​M</​i></​dd></​dl><​p>​Authors often introduce syntactic sugar, such as <​tt>​let</​tt>​to permit writing the above in the more intuitive order
 +</p>
 +<​dl><​dd><​tt>​let <​i>​f</​i>​ = </​tt><​i>​M</​i><​tt>​ in </​tt><​i>​N</​i></​dd></​dl><​p>​By chaining such definitions,​ one can write a lambda calculus &​quot;​program&​quot;​ as zero or more function definitions,​ followed by one lambda-term using those functions that constitutes the main body of the program.
 +</​p><​p>​A notable restriction of this <​tt>​let</​tt>​ is that the name <​tt><​i>​f</​i></​tt>​ is not defined in <​i>​M</​i>​since <​i>​M</​i>​ is outside the scope of the lambda-abstraction binding <​tt><​i>​f</​i></​tt>;​ this means a recursive function definition cannot be used as the <​i>​M</​i>​ with <​tt>​let</​tt>​. The more advanced <​tt>​letrec</​tt>​ syntactic sugar construction that allows writing recursive function definitions in that naive style instead additionally employs fixed-point combinators.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Recursion_and_fixed_points">​Recursion and fixed points</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +
 +
 +<​p>​Recursion is the definition of a function using the function itself. Lambda calculus cannot express this as directly as some other notations: all functions are anonymous in lambda calculus, so we can&#​39;​t refer to a value which is yet to be defined, inside the lambda term defining that same value. However, recursion can still be achieved by arranging for a lambda expression to receive itself as its argument value, for example in  <​tt>​(λ<​i>​x</​i>​.<​i>​x</​i>​ <​i>​x</​i>​) <​i>​E</​i></​tt>​.
 +</​p><​p>​Consider the factorial function <​tt>​F(<​i>​n</​i>​)</​tt>​ recursively defined by
 +</p>
 +<​dl><​dd><​tt>​F(<​i>​n</​i>​) = 1, if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × F(<​i>​n</​i>​ − 1)</​tt>​.</​dd></​dl><​p>​In the lambda expression which is to represent this function, a <​i>​parameter</​i>​ (typically the first one) will be assumed to receive the lambda expression itself as its value, so that calling it – applying it to an argument – will amount to recursion. Thus to achieve recursion, the intended-as-self-referencing argument (called <​tt><​i>​r</​i></​tt>​ here) must always be passed to itself within the function body, at a call point:
 +</p>
 +<​dl><​dd><​tt>​G :​= λ<​i>​r</​i>​. λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × (<​i>​r</​i>​ <​i>​r</​i>​ (<​i>​n</​i>​−1)))</​tt>​
 +<​dl><​dd><​dl><​dd>​with  <tt> <​i>​r</​i>​ <​i>​r</​i>​ <​i>​x</​i>​ = F <​i>​x</​i>​ = G <​i>​r</​i>​ <​i>​x</​i></​tt>​  to hold, so  <​tt><​i>​r</​i>​ = G</​tt>​  and</​dd></​dl></​dd></​dl></​dd>​
 +<​dd><​tt>​F :​= G G = (λ<​i>​x</​i>​.<​i>​x</​i>​ <​i>​x</​i>​) G</​tt></​dd></​dl><​p>​The self-application achieves replication here, passing the function&#​39;​s lambda expression on to the next invocation as an argument value, making it available to be referenced and called there.
 +</​p><​p>​This solves it but requires re-writing each recursive call as self-application. We would like to have a generic solution, without a need for any re-writes:
 +</p>
 +<​dl><​dd><​tt>​G :​= λ<​i>​r</​i>​. λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × (<​i>​r</​i>​ (<​i>​n</​i>​−1)))</​tt>​
 +<​dl><​dd><​dl><​dd>​with  <tt> <​i>​r</​i>​ <​i>​x</​i>​ = F <​i>​x</​i>​ = G <​i>​r</​i>​ <​i>​x</​i></​tt>​  to hold, so  <​tt><​i>​r</​i>​ = G <​i>​r</​i>​ =: FIX G</​tt>​  and</​dd></​dl></​dd></​dl></​dd>​
 +<​dd><​tt>​F :​= FIX G</​tt>​  where  <​tt>​FIX <​i>​g</​i>​ :​= (<​i>​r</​i>​ where <​i>​r</​i>​ = <​i>​g</​i>​ <​i>​r</​i>​) = <​i>​g</​i>​ (FIX <​i>​g</​i>​)</​tt>​
 +<​dl><​dd><​dl><​dd>​so that  <tt> FIX G = G (FIX G) = (λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((FIX G) (<​i>​n</​i>​−1)))) </​tt></​dd></​dl></​dd></​dl></​dd></​dl><​p>​Given a lambda term with first argument representing recursive call (e.g. <​tt>​G</​tt>​ here), the <​i>​fixed-point</​i>​ combinator <​tt>​FIX</​tt>​ will return a self-replicating lambda expression representing the recursive function (here, <​tt>​F</​tt>​). The function does not need to be explicitly passed to itself at any point, for the self-replication is arranged in advance, when it is created, to be done each time it is called. Thus the original lambda expression <​tt>​(FIX G)</​tt>​ is re-created inside itself, at call-point, achieving self-reference.
 +</​p><​p>​In fact, there are many possible definitions for this <​tt>​FIX</​tt>​ operator, the simplest of them being:
 +</p>
 +<​dl><​dd><​tt><​b>​Y</​b>​ :​= λ<​i>​g</​i>​.(λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)) (λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​))</​tt></​dd></​dl><​p>​In the lambda calculus, <​tt><​b>​Y</​b>​ <​i>​g</​i></​tt>​  is a fixed-point of <​tt><​i>​g</​i></​tt>​as it expands to:
 +</p>
 +<​dl><​dd><​tt><​b>​Y</​b>​ <​i>​g</​i></​tt></​dd>​
 +<​dd><​tt>​(λ<​i>​h</​i>​.(λ<​i>​x</​i>​.<​i>​h</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)) (λ<​i>​x</​i>​.<​i>​h</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​))) <​i>​g</​i></​tt></​dd>​
 +<​dd><​tt>​(λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)) (λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​))</​tt></​dd>​
 +<​dd><​tt><​i>​g</​i>​ ((λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)) (λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)))</​tt></​dd>​
 +<​dd><​tt><​i>​g</​i>​ (<​b>​Y</​b>​ <​i>​g</​i>​)</​tt></​dd></​dl><​p>​Now,​ to perform our recursive call to the factorial function, we would simply call <​tt>​(<​b>​Y</​b>​ G) <​i>​n</​i></​tt>,​  where <​i>​n</​i>​ is the number we are calculating the factorial of. Given <​i>​n</​i>​ = 4, for example, this gives:
 +</p>
 +<​dl><​dd><​tt>​(<​b>​Y</​b>​ G) 4 </​tt></​dd>​
 +<​dd><​tt>​G (<​b>​Y</​b>​ G) 4 </​tt></​dd>​
 +<​dd><​tt>​(λ<​i>​r</​i>​.λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × (<​i>​r</​i>​ (<​i>​n</​i>​−1)))) (<​b>​Y</​b>​ G) 4</​tt></​dd>​
 +<​dd><​tt>​(λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((<​b>​Y</​b>​ G) (<​i>​n</​i>​−1)))) 4</​tt></​dd>​
 +<​dd><​tt>​1,​ if 4 = 0; else 4 × ((<​b>​Y</​b>​ G) (4−1))</​tt></​dd>​
 +<​dd><​tt>​4 × (G (<​b>​Y</​b>​ G) (4−1))</​tt></​dd>​
 +<​dd><​tt>​4 × ((λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((<​b>​Y</​b>​ G) (<​i>​n</​i>​−1)))) (4−1))</​tt></​dd>​
 +<​dd><​tt>​4 × (1, if 3 = 0; else 3 × ((<​b>​Y</​b>​ G) (3−1)))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (G (<​b>​Y</​b>​ G) (3−1)))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × ((λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((<​b>​Y</​b>​ G) (<​i>​n</​i>​−1)))) (3−1)))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (1, if 2 = 0; else 2 × ((<​b>​Y</​b>​ G) (2−1))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (G (<​b>​Y</​b>​ G) (2−1))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × ((λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((<​b>​Y</​b>​ G) (<​i>​n</​i>​−1)))) (2−1))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (1, if 1 = 0; else 1 × ((<​b>​Y</​b>​ G) (1−1)))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (1 × (G (<​b>​Y</​b>​ G) (1−1)))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (1 × ((λ<​i>​n</​i>​.(1,​ if <​i>​n</​i>​ = 0; else <​i>​n</​i>​ × ((<​b>​Y</​b>​ G) (<​i>​n</​i>​−1)))) (1−1)))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (1 × (1, if 0 = 0; else 0 × ((<​b>​Y</​b>​ G) (0−1))))))</​tt></​dd>​
 +<​dd><​tt>​4 × (3 × (2 × (1 × (1))))</​tt></​dd>​
 +<​dd><​tt>​24</​tt></​dd></​dl><​p>​Every recursively defined function can be seen as a fixed point of some suitably defined function closing over the recursive call with an extra argument, and therefore, using <​tt><​b>​Y</​b></​tt>​every recursively defined function can be expressed as a lambda expression. In particular, we can now cleanly define the subtraction,​ multiplication and comparison predicate of natural numbers recursively.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Standard_terms">​Standard terms</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Certain terms have commonly accepted names:
 +</p>
 +<​dl><​dd><​span id="​I"/>​ <​tt><​b>​I</​b>​ :​= λ<​i>​x</​i>​.<​i>​x</​i></​tt></​dd>​
 +<​dd><​span id="​K"/>​ <​tt><​b>​K</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i></​tt></​dd>​
 +<​dd><​span id="​S"/>​ <​tt><​b>​S</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.λ<​i>​z</​i>​.<​i>​x</​i>​ <​i>​z</​i>​ (<​i>​y</​i>​ <​i>​z</​i>​) </​tt></​dd>​
 +<​dd><​span id="​B"/>​ <​tt><​b>​B</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.λ<​i>​z</​i>​.<​i>​x</​i>​ (<​i>​y</​i>​ <​i>​z</​i>​) </​tt></​dd>​
 +<​dd><​span id="​C"/>​ <​tt><​b>​C</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.λ<​i>​z</​i>​.<​i>​x</​i>​ <​i>​z</​i>​ <​i>​y</​i></​tt></​dd>​
 +<​dd><​span id="​W"/>​ <​tt><​b>​W</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i>​ <​i>​y</​i>​ <​i>​y</​i></​tt></​dd>​
 +<​dd><​span id="​U"/>​ <​tt><​b>​U</​b>​ :​= λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​y</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​ <​i>​y</​i>​) ​ </​tt></​dd>​
 +<​dd><​span id="​omega"/>​ <​tt><​b>​ω</​b>​ :​= λ<​i>​x</​i>​.<​i>​x</​i>​ <​i>​x</​i>​ </​tt></​dd>​
 +<​dd><​span id="​Omega"/>​ <​tt><​b>​Ω</​b>​ :​= <​b>​ω</​b>​ <​b>​ω</​b>​ </​tt></​dd>​
 +<​dd><​span id="​Y"/>​ <​tt><​b>​Y</​b>​ :​= λ<​i>​g</​i>​.(λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​)) (λ<​i>​x</​i>​.<​i>​g</​i>​ (<​i>​x</​i>​ <​i>​x</​i>​))</​tt></​dd></​dl><​p>​Several of these have direct applications in the <​i>​elimination of lambda-abstraction</​i>​ that turns lambda terms into combinator calculus terms.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Abstraction_elimination">​Abstraction elimination</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +
 +<p>If <​i>​N</​i>​ is a lambda-term without lambda-abstraction,​ but possibly containing named constants (combinators),​ then there exists a lambda-term <​i>​T</​i>​(<​tt><​i>​x</​i></​tt>,<​i>​N</​i>​) which is equivalent to <​tt>​λ<​i>​x</​i>​.</​tt><​i>​N</​i>​ but lacks lambda-abstraction (except as part of the named constants, if these are considered non-atomic). This can also be viewed as anonymising variables, as <​i>​T</​i>​(<​tt><​i>​x</​i></​tt>,<​i>​N</​i>​) removes all occurrences of <​tt><​i>​x</​i></​tt>​ from <​i>​N</​i>​while still allowing argument values to be substituted into the positions where <​i>​N</​i>​ contains an <​tt><​i>​x</​i></​tt>​. The conversion function <​i>​T</​i>​ can be defined by:
 +</p>
 +<​dl><​dd><​i>​T</​i>​(<​tt><​i>​x</​i></​tt><​tt><​i>​x</​i></​tt>​) :​= <​b>​I</​b></​dd>​
 +<​dd><​i>​T</​i>​(<​tt><​i>​x</​i></​tt><​i>​N</​i>​) :​= <​b>​K</​b>​ <​i>​N</​i>​ if <​tt><​i>​x</​i></​tt>​ is not free in <​i>​N</​i>​.</​dd>​
 +<​dd><​i>​T</​i>​(<​tt><​i>​x</​i></​tt><​i>​M</​i>​ <​i>​N</​i>​) :​= <​b>​S</​b>​ <​i>​T</​i>​(<​tt><​i>​x</​i></​tt><​i>​M</​i>​) <​i>​T</​i>​(<​tt><​i>​x</​i></​tt><​i>​N</​i>​)</​dd></​dl><​p>​In either case, a term of the form <​i>​T</​i>​(<​tt><​i>​x</​i></​tt>,<​i>​N</​i>​) <​i>​P</​i>​ can reduce by having the initial combinator <​b>​I</​b><​b>​K</​b>​or <​b>​S</​b>​ grab the argument <​i>​P</​i>​just like β-reduction of <​tt>​(λ<​i>​x</​i>​.</​tt><​i>​N</​i><​tt>​)</​tt>​ <​i>​P</​i>​ would do. <​b>​I</​b>​ returns that argument. <​b>​K</​b>​ throws the argument away, just like <​tt>​(λ<​i>​x</​i>​.</​tt><​i>​N</​i><​tt>​)</​tt>​ would do if <​tt><​i>​x</​i></​tt>​ has no free occurrence in <​i>​N</​i>​. <​b>​S</​b>​ passes the argument on to both subterms of the application,​ and then applies the result of the first to the result of the second.
 +</​p><​p>​The combinators <​b>​B</​b>​ and <​b>​C</​b>​ are similar to <​b>​S</​b>​but pass the argument on to only one subterm of an application (<​b>​B</​b>​ to the &​quot;​argument&​quot;​ subterm and <​b>​C</​b>​ to the &​quot;​function&​quot;​ subterm), thus saving a subsequent <​b>​K</​b>​ if there is no occurrence of <​tt><​i>​x</​i></​tt>​ in one subterm. In comparison to <​b>​B</​b>​ and <​b>​C</​b>​the <​b>​S</​b>​ combinator actually conflates two functionalities:​ rearranging arguments, and duplicating an argument so that it may be used in two places. The <​b>​W</​b>​ combinator does only the latter, yielding the B, C, K, W system as an alternative to SKI combinator calculus.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Typed_lambda_calculus">​Typed lambda calculus</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +
 +<p>A <​b>​typed lambda calculus</​b>​ is a typed formalism that uses the lambda-symbol (<span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle lambda }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​λ<​!-- λ --></​mi></​mstyle></​mrow>​{displaystyle lambda }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​b43d0ea3c9c025af1be9128e62a18fa74bedda2a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.355ex;​ height:​2.176ex;"​ alt="​lambda "/></​span>​) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered (see kinds below). From a certain point of view, typed lambda calculi can be seen as refinements of the <a href="​http://​en.wikipedia.org/​wiki/​Untyped_lambda_calculus"​ class="​mw-redirect"​ title="​Untyped lambda calculus">​untyped lambda calculus but from another point of view, they can also be considered the more fundamental theory and  <​i>​untyped lambda calculus</​i>​ a special case with only one type.<​sup id="​cite_ref-22"​ class="​reference">​[22]</​sup></​p><​p>​Typed lambda calculi are foundational programming languages and are the base of typed functional programming languages such as ML and Haskell and, more indirectly, typed imperative programming languages. Typed lambda calculi play an important role in the design of type systems for programming languages; here typability usually captures desirable properties of the program, e.g. the program will not cause a memory access violation.
 +</​p><​p>​Typed lambda calculi are closely related to mathematical logic and proof theory via the Curry–Howard isomorphism and they can be considered as the internal language of classes of categories, e.g. the simply typed lambda calculus is the language of Cartesian closed categories (CCCs).
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Computable_functions_and_lambda_calculus">​Computable functions and lambda calculus</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<p>A function <​i>​F</​i>:​ <​b>​N</​b>​ → <​b>​N</​b>​ of natural numbers is a computable function if and only if there exists a lambda expression <​i>​f</​i>​ such that for every pair of <​i>​x</​i><​i>​y</​i>​ in <​b>​N</​b><​i>​F</​i>​(<​i>​x</​i>​)=<​i>​y</​i>​ if and only if <​i>​f</​i>​ <​tt><​i>​x</​i></​tt>​ =<​sub>​β</​sub>​ <​tt><​i>​y</​i></​tt>,​  where <​tt><​i>​x</​i></​tt>​ and <​tt><​i>​y</​i></​tt>​ are the Church numerals corresponding to <​i>​x</​i>​ and <​i>​y</​i>​respectively and =<​sub>​β</​sub>​ meaning equivalence with beta reduction. This is one of the many ways to define computability;​ see the Church–Turing thesis for a discussion of other approaches and their equivalence.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Undecidability_of_equivalence">​Undecidability of equivalence</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​There is no algorithm that takes as input two lambda expressions and outputs <​tt>​TRUE</​tt>​ or <​tt>​FALSE</​tt>​ depending on whether or not the two expressions are equivalent. This was historically the first problem for which undecidability could be proven. As is common for a proof of undecidability,​ the proof shows that no computable function can decide the equivalence. Church&#​39;​s thesis is then invoked to show that no algorithm can do so.
 +</​p><​p>​Church&#​39;​s proof first reduces the problem to determining whether a given lambda expression has a <​i>​normal form</​i>​. A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions,​ he constructs a lambda expression <​tt><​i>​e</​i></​tt>​ that closely follows the proof of Gödel&#​39;​s first incompleteness theorem. If <​tt><​i>​e</​i></​tt>​ is applied to its own Gödel number, a contradiction results.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Lambda_calculus_and_programming_languages">​Lambda calculus and programming languages</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<p>As pointed out by Peter Landin&#​39;​s 1965 paper &quot;A Correspondence between ALGOL 60 and Church&#​39;​s Lambda-notation&​quot;<​sup id="​cite_ref-23"​ class="​reference">​[23]</​sup>​sequential procedural programming languages can be understood in terms of the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Anonymous_functions">​Anonymous functions</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +
 +<​p>​For example, in Lisp the &​quot;​square&​quot;​ function can be expressed as a lambda expression as follows:
 +</p>
 +
 +<​p>​The above example is an expression that evaluates to a first-class function. The symbol <​code>​lambda</​code>​ creates an anonymous function, given a list of parameter names, <​code>​(x)</​code>​ – just a single argument in this case, and an expression that is evaluated as the body of the function, <​code>​(* x x)</​code>​. Anonymous functions are sometimes called lambda expressions.
 +</​p><​p>​For example, Pascal and many other imperative languages have long supported passing subprograms as arguments to other subprograms through the mechanism of function pointers. However, function pointers are not a sufficient condition for functions to be first class datatypes, because a function is a first class datatype if and only if new instances of the function can be created at run-time. And this run-time creation of functions is supported in Smalltalk, JavaScript, and more recently in Scala, Eiffel (&​quot;​agents&​quot;​),​ C# (&​quot;​delegates&​quot;​) and C++11, among others.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Reduction_strategies">​Reduction strategies</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +
 +<​p>​Whether a term is normalising or not, and how much work needs to be done in normalising it if it is, depends to a large extent on the reduction strategy used. The distinction between reduction strategies relates to the distinction in functional programming languages between eager evaluation and lazy evaluation.
 +</p>
 +<​dl><​dt>​Full beta reductions</​dt>​
 +<​dd>​Any redex can be reduced at any time. This means essentially the lack of any particular reduction strategy—with regard to reducibility,​ &​quot;​all bets are off&​quot;​.</​dd>​
 +<​dt>​Applicative order</​dt>​
 +<​dd>​The rightmost, innermost redex is always reduced first. Intuitively this means a function&#​39;​s arguments are always reduced before the function itself. Applicative order always attempts to apply functions to normal forms, even when this is not possible.</​dd>​
 +<​dd>​Most programming languages (including Lisp, ML and imperative languages like C and Java) are described as &​quot;​strict&​quot;,​ meaning that functions applied to non-normalising arguments are non-normalising. This is done essentially using applicative order, call by value reduction (see below), but usually called &​quot;​eager evaluation&​quot;​.</​dd>​
 +<​dt>​Normal order</​dt>​
 +<​dd>​The leftmost, outermost redex is always reduced first. That is, whenever possible the arguments are substituted into the body of an abstraction before the arguments are reduced.</​dd>​
 +<​dt>​Call by name</​dt>​
 +<​dd>​As normal order, but no reductions are performed inside abstractions. For example, <​tt>​λ<​i>​x</​i>​.(λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​x</​i></​tt>​ is in normal form according to this strategy, although it contains the redex <​tt>​(λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​x</​i></​tt>​.</​dd>​
 +<​dt>​Call by value</​dt>​
 +<​dd>​Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or lambda abstraction).</​dd>​
 +<​dt>​Call by need</​dt>​
 +<​dd>​As normal order, but function applications that would duplicate terms instead name the argument, which is then reduced only &​quot;​when it is needed&​quot;​. Called in practical contexts &​quot;​lazy evaluation&​quot;​. In implementations this &​quot;​name&​quot;​ takes the form of a pointer, with the redex represented by a thunk.</​dd></​dl><​p>​Applicative order is not a normalising strategy. The usual counterexample is as follows: define <​tt><​b>​Ω</​b>​ = ωω</​tt>​ where <​tt><​b>​ω</​b>​ = λ<​i>​x</​i>​.<​i>​xx</​i></​tt>​. This entire expression contains only one redex, namely the whole expression; its reduct is again <​tt><​b>​Ω</​b></​tt>​. Since this is the only available reduction, <​tt><​b>​Ω</​b></​tt>​ has no normal form (under any evaluation strategy). Using applicative order, the expression <​tt><​b>​KIΩ</​b>​ = (λ<​i>​x</​i>​.λ<​i>​y</​i>​.<​i>​x</​i>​) (λ<​i>​x</​i>​.<​i>​x</​i>​)<​b>​Ω</​b></​tt>​ is reduced by first reducing <​tt><​b>​Ω</​b></​tt>​ to normal form (since it is the rightmost redex), but since <​tt><​b>​Ω</​b></​tt>​ has no normal form, applicative order fails to find a normal form for <​tt><​b>​KIΩ</​b></​tt>​.
 +</​p><​p>​In contrast, normal order is so called because it always finds a normalising reduction, if one exists. In the above example, <​tt><​b>​KIΩ</​b></​tt>​ reduces under normal order to <​i>​I</​i>​a normal form. A drawback is that redexes in the arguments may be copied, resulting in duplicated computation (for example, <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) ((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​)</​tt>​ reduces to <​tt>​((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​) ((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​)</​tt>​ using this strategy; now there are two redexes, so full evaluation needs two more steps, but if the argument had been reduced first, there would now be none).
 +</​p><​p>​The positive tradeoff of using applicative order is that it does not cause unnecessary computation,​ if all arguments are used, because it never substitutes arguments containing redexes and hence never needs to copy them (which would duplicate work). In the above example, in applicative order <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) ((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​)</​tt>​ reduces first to <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​)<​i>​y</​i></​tt>​ and then to the normal order <​tt><​i>​yy</​i></​tt>​taking two steps instead of three.
 +</​p><​p>​Most <​i>​purely</​i>​ functional programming languages (notably Miranda and its descendents,​ including Haskell), and the proof languages of theorem provers, use <​i>​lazy evaluation</​i>​which is essentially the same as call by need. This is like normal order reduction, but call by need manages to avoid the duplication of work inherent in normal order reduction using <​i>​sharing</​i>​. In the example given above, <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) ((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​)</​tt>​ reduces to <​tt>​((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​) ((λ<​i>​x</​i>​.<​i>​x</​i>​)<​i>​y</​i>​)</​tt>​which has two redexes, but in call by need they are represented using the same object rather than copied, so when one is reduced the other is too.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​A_note_about_complexity">​A note about complexity</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​While the idea of beta reduction seems simple enough, it is not an atomic step, in that it must have a non-trivial cost when estimating computational complexity.<​sup id="​cite_ref-24"​ class="​reference">​[24]</​sup>​ To be precise, one must somehow find the location of all of the occurrences of the bound variable <​tt><​i>​V</​i></​tt>​ in the expression <​tt><​i>​E</​i></​tt>​implying a time cost, or one must keep track of these locations in some way, implying a space cost. A naïve search for the locations of <​tt><​i>​V</​i></​tt>​ in <​tt><​i>​E</​i></​tt>​ is <​i>​O</​i>​(<​i>​n</​i>​) in the length <​i>​n</​i>​ of <​tt><​i>​E</​i></​tt>​. This has led to the study of systems that use explicit substitution. Sinot&#​39;​s director strings<​sup id="​cite_ref-25"​ class="​reference">​[25]</​sup>​ offer a way of tracking the locations of free variables in expressions.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Parallelism_and_concurrency">​Parallelism and concurrency</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​The Church–Rosser property of the lambda calculus means that evaluation (β-reduction) can be carried out in <​i>​any order</​i>​even in parallel. This means that various nondeterministic evaluation strategies are relevant. However, the lambda calculus does not offer any explicit constructs for parallelism. One can add constructs such as Futures to the lambda calculus. Other process calculi have been developed for describing communication and concurrency.
 +</p>
 +<​h3><​span class="​mw-headline"​ id="​Optimal_reduction">​Optimal reduction</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<p>In Lévy&#​39;​s 1988 paper &​quot;​Sharing in the Evaluation of lambda Expressions&​quot;,​ he defines a notion of optimal sharing, such that no work is <​i>​duplicated</​i>​. For example, performing a beta reduction in normal order on <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) (II)</​tt>​ reduces it to <​tt>​II (II)</​tt>​. The argument <​tt>​II</​tt>​ is duplicated by the application to the first lambda term. If the reduction was done in an applicative order first, we save work because work is not duplicated: <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) (II)</​tt>​ reduces to <​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) I</​tt>​. On the other hand, using applicative order can result in redundant reductions or even possibly never reduce to normal form. For example, performing a beta reduction in normal order on <​tt>​(λ<​i>​f</​i>​.f I) (λy.(λ<​i>​x</​i>​.<​i>​xx</​i>​) (y I))</​tt>​ yields <​tt>​(λy.(λ<​i>​x</​i>​.<​i>​xx</​i>​) (y I)) I</​tt><​tt>​(λ<​i>​x</​i>​.<​i>​xx</​i>​) (II)</​tt>​ which we know we can do without duplicating work. Doing the same but in applicative order yields <​tt>​(λ<​i>​f</​i>​.f I) (λy.y I (y I))</​tt><​tt>​(λy.y I (y I)) I</​tt><​tt>​I I (I I)</​tt>​and now work is duplicated.
 +</​p><​p>​Lévy shows the existence of lambda terms where there <​i>​does not exist</​i>​ a sequence of reductions which reduces them without duplicating work. The below lambda term is such an example.
 +</​p><​p><​tt>​((λg.(g(g(λx.x))))
 +(λh.((λf.(f(f(λz.z))))
 +(λw.(h(w(λy.y)))))))</​tt>​
 +</​p><​p>​It is composed of three similar terms, <​tt>​x=((λg. ... ) (λh.y))</​tt>​ and <​tt>​y=((λf. ...) (λw.z) )</​tt>​and finally <​tt>​z=λw.(h(w(λy.y)))</​tt>​. There are only two possible beta reductions to be done here, on x and on y. Reducing the outer x term first results in the inner y term being duplicated, and each copy will have to be reduced, but reducing the inner y term first will duplicate its argument z, which will cause work to be duplicated when the values of h and w are made known. Incidentally,​ the above term reduces to the identity function <​tt>​(λy.y)</​tt>​and is constructed by making wrappers which make the identity function available to the binders <​tt>​g=λh...</​tt><​tt>​f=λw...</​tt><​tt>​h=λx.x</​tt>​ (at first), and <​tt>​w=λz.z</​tt>​ (at first), all of which are applied to the innermost term <​tt>​λy.y</​tt>​.
 +</​p><​p>​The precise notion of duplicated work relies on noticing that after the first reduction of <tt>I I</​tt>​ is done, the value of the other <tt>I I</​tt>​ can be determined, because they have the same structure (and in fact they have exactly the same values), and result from a common ancestor. Such similar structures can each be assigned a label that can be tracked across reductions. If a name is assigned to the redex that produces all the resulting <​tt>​II</​tt>​ terms, and then all duplicated occurrences of <​tt>​II</​tt>​ can be tracked and reduced in one go. However, it is not obvious that a redex will produce the <​tt>​II</​tt>​ term. Identifying the structures that are similar in different parts of a lambda term can involve a complex algorithm and can possibly have a complexity equal to the history of the reduction itself.
 +</​p><​p>​While Lévy defines the notion of optimal sharing, he does not provide an algorithm to do it. In Vincent van Oostrom, Kees-Jan van de Looij, and Marijn Zwitserlood&#​39;​s paper <​i>​Lambdascope:​ Another optimal implementation of the lambda-calculus</​i>​they provide such an algorithm by transforming lambda terms into interaction nets, which are then reduced. Roughly speaking, the resulting reduction is optimal because every term that would have the same labels as per Lévy&#​39;​s paper would also be the same graph in the interaction net. In the paper, they mention that their prototype implementation of Lambdascope performs as well as the <​i>​optimised</​i>​ version of the reference optimal higher order machine BOHM.
 +</​p><​p>​More details can be found in the short article About the efficient reduction of lambda terms.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​Semantics">​Semantics</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​p>​The fact that lambda calculus terms act as functions on other lambda calculus terms, and even on themselves, led to questions about the semantics of the lambda calculus. Could a sensible meaning be assigned to lambda calculus terms? The natural semantics was to find a set <​i>​D</​i>​ isomorphic to the function space <​i>​D</​i>​ → <​i>​D</​i>​of functions on itself. However, no nontrivial such <​i>​D</​i>​ can exist, by cardinality constraints because the set of all functions from <​i>​D</​i>​ to <​i>​D</​i>​ has greater cardinality than <​i>​D</​i>​unless <​i>​D</​i>​ is a singleton set.
 +</​p><​p>​In the 1970s, Dana Scott showed that, if only continuous functions were considered, a set or domain <​i>​D</​i>​ with the required property could be found, thus providing a model for the lambda calculus.
 +</​p><​p>​This work also formed the basis for the denotational semantics of programming languages.
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​See_also">​See also</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +
 +
 +<​h2><​span class="​mw-headline"​ id="​References">​References</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<div class="​reflist columns references-column-width"​ style="​-moz-column-width:​ 30em; -webkit-column-width:​ 30em; column-width:​ 30em; list-style-type:​ decimal;">​
 +<ol class="​references"><​li id="​cite_note-1"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Turing,​ A. M. (December 1937). &​quot;​Computability and λ-Definability&​quot;​. <​i>​The Journal of Symbolic Logic</​i>​. <​b>​2</​b>​ (4): 153–163. doi:​10.2307/​2268280. JSTOR 2268280.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=The+Journal+of+Symbolic+Logic&​rft.atitle=Computability+and+%CE%BB-Definability&​rft.volume=2&​rft.issue=4&​rft.pages=153-163&​rft.date=1937-12&​rft_id=info%3Adoi%2F10.2307%2F2268280&​rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2268280&​rft.aulast=Turing&​rft.aufirst=A.+M.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/></​span>​
 +</li>
 +<li id="​cite_note-2"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text">​Coquand,​ Thierry, &​quot;​Type Theory&​quot;,​ <​i>​The Stanford Encyclopedia of Philosophy</​i> ​ (Summer 2013 Edition), Edward N. Zalta (ed.).</​span>​
 +</li>
 +<li id="​cite_note-3"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation book">​Moortgat,​ Michael (1988). <​i>​Categorial Investigations:​ Logical and Linguistic Aspects of the Lambek Calculus</​i>​. Foris Publications. ISBN 9789067653879.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Categorial+Investigations%3A+Logical+and+Linguistic+Aspects+of+the+Lambek+Calculus&​rft.pub=Foris+Publications&​rft.date=1988&​rft.isbn=9789067653879&​rft.aulast=Moortgat&​rft.aufirst=Michael&​rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D9CdFE9X_FCoC&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-4"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFBuntMuskens2008"​ class="​citation">​Bunt,​ Harry; Muskens, Reinhard, eds. (2008), <​i>​Computing Meaning</​i>​Springer,​ ISBN 9781402059575</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Computing+Meaning&​rft.pub=Springer&​rft.date=2008&​rft.isbn=9781402059575&​rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DnyFa5ngYThMC&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-5"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFMitchell2003"​ class="​citation">​Mitchell,​ John C. (2003), <​i>​Concepts in Programming Languages</​i>​Cambridge University Press, p. 57, ISBN 9780521780988</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Concepts+in+Programming+Languages&​rft.pages=57&​rft.pub=Cambridge+University+Press&​rft.date=2003&​rft.isbn=9780521780988&​rft.aulast=Mitchell&​rft.aufirst=John+C.&​rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D7Uh8XGfJbEIC%26pg%3DPA57&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​.</​span>​
 +</li>
 +<li id="​cite_note-6"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation book">​Pierce,​ Benjamin C. <​i>​Basic Category Theory for Computer Scientists</​i>​. p. 53.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Basic+Category+Theory+for+Computer+Scientists&​rft.pages=53&​rft.aulast=Pierce&​rft.aufirst=Benjamin+C.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-7"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Church,​ A. (1932). &quot;A set of postulates for the foundation of logic&​quot;​. <​i>​Annals of Mathematics</​i>​. Series 2. <​b>​33</​b>​ (2): 346–366. doi:​10.2307/​1968337. JSTOR 1968337.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Annals+of+Mathematics&​rft.atitle=A+set+of+postulates+for+the+foundation+of+logic&​rft.volume=33&​rft.issue=2&​rft.pages=346-366&​rft.date=1932&​rft_id=info%3Adoi%2F10.2307%2F1968337&​rft_id=%2F%2Fwww.jstor.org%2Fstable%2F1968337&​rft.aulast=Church&​rft.aufirst=A.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-8"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text">​For a full history, see Cardone and Hindley&#​39;​s &​quot;​History of Lambda-calculus and Combinatory Logic&​quot;​ (2006).</​span>​
 +</li>
 +<li id="​cite_note-9"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Kleene,​ S. C.; Rosser, J. B. (July 1935). &​quot;​The Inconsistency of Certain Formal Logics&​quot;​. <​i>​The Annals of Mathematics</​i>​. <​b>​36</​b>​ (3): 630. doi:​10.2307/​1968646.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=The+Annals+of+Mathematics&​rft.atitle=The+Inconsistency+of+Certain+Formal+Logics&​rft.volume=36&​rft.issue=3&​rft.pages=630&​rft.date=1935-07&​rft_id=info%3Adoi%2F10.2307%2F1968646&​rft.aulast=Kleene&​rft.aufirst=S.+C.&​rft.au=Rosser%2C+J.+B.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-10"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Church,​ Alonzo (December 1942). &​quot;​Review of Haskell B. Curry, <​i>​The Inconsistency of Certain Formal Logics</​i>&​quot;​. <​i>​The Journal of Symbolic Logic</​i>​. <​b>​7</​b>​ (4): 170–171. doi:​10.2307/​2268117. JSTOR 2268117.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=The+Journal+of+Symbolic+Logic&​rft.atitle=Review+of+Haskell+B.+Curry%2C+The+Inconsistency+of+Certain+Formal+Logics&​rft.volume=7&​rft.issue=4&​rft.pages=170-171&​rft.date=1942-12&​rft_id=info%3Adoi%2F10.2307%2F2268117&​rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2268117&​rft.aulast=Church&​rft.aufirst=Alonzo&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-11"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Church,​ A. (1936). &​quot;​An unsolvable problem of elementary number theory&​quot;​. <​i>​American Journal of Mathematics</​i>​. <​b>​58</​b>​ (2): 345–363. doi:​10.2307/​2371045. JSTOR 2371045.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=American+Journal+of+Mathematics&​rft.atitle=An+unsolvable+problem+of+elementary+number+theory&​rft.volume=58&​rft.issue=2&​rft.pages=345-363&​rft.date=1936&​rft_id=info%3Adoi%2F10.2307%2F2371045&​rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2371045&​rft.aulast=Church&​rft.aufirst=A.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-12"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Church,​ A. (1940). &quot;A Formulation of the Simple Theory of Types&​quot;​. <​i>​Journal of Symbolic Logic</​i>​. <​b>​5</​b>​ (2): 56–68. doi:​10.2307/​2266170. JSTOR 2266170.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Journal+of+Symbolic+Logic&​rft.atitle=A+Formulation+of+the+Simple+Theory+of+Types&​rft.volume=5&​rft.issue=2&​rft.pages=56-68&​rft.date=1940&​rft_id=info%3Adoi%2F10.2307%2F2266170&​rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2266170&​rft.aulast=Church&​rft.aufirst=A.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-mm-linguistics-13"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation book">​Partee,​ B. B. H.; ter Meulen, A.; Wall, R. E. (1990). <​i>​Mathematical Methods in Linguistics</​i>​. Springer<​span class="​reference-accessdate">​. Retrieved <span class="​nowrap">​29 Dec</​span>​ 2016</​span>​.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Mathematical+Methods+in+Linguistics&​rft.pub=Springer&​rft.date=1990&​rft.aulast=Partee&​rft.aufirst=B.+B.+H.&​rft.au=ter+Meulen%2C+A.&​rft.au=Wall%2C+R.+E.&​rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DqV7TUuaYcUIC%26pg%3DPA317&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-14"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text">​Alama,​ Jesse &​quot;​The Lambda Calculus&​quot;,​ <​i>​The Stanford Encyclopedia of Philosophy</​i>​ (Summer 2013 Edition), Edward N. Zalta (ed.).</​span>​
 +</li>
 +<li id="​cite_note-15"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFBarendregt1984"​ class="​citation">​Barendregt,​ Hendrik Pieter (1984), <​i>​The Lambda Calculus: Its Syntax and Semantics</​i>​Studies in Logic and the Foundations of Mathematics,​ <​b>​103</​b>​ (Revised ed.), North Holland, Amsterdam, ISBN 0-444-87508-5,​ archived from the original on 2004-08-23</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=The+Lambda+Calculus%3A+Its+Syntax+and+Semantics&​rft.series=Studies+in+Logic+and+the+Foundations+of+Mathematics&​rft.edition=Revised&​rft.pub=North+Holland%2C+Amsterdam&​rft.date=1984&​rft.isbn=0-444-87508-5&​rft.aulast=Barendregt&​rft.aufirst=Hendrik+Pieter&​rft_id=http%3A%2F%2Fwww.elsevier.com%2Fwps%2Ffind%2Fbookdescription.cws_home%2F501727%2Fdescription&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​Corrections.</​span>​
 +</li>
 +<li id="​cite_note-lambda-bound-16"><​span class="​mw-cite-backlink">​^ <​sup><​i><​b>​a</​b></​i></​sup>​ <​sup><​i><​b>​b</​b></​i></​sup></​span>​ <span class="​reference-text"><​cite class="​citation web">&​quot;​Example for Rules of Associativity&​quot;​. Lambda-bound.com<​span class="​reference-accessdate">​. Retrieved <span class="​nowrap">​2012-06-18</​span></​span>​.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=unknown&​rft.btitle=Example+for+Rules+of+Associativity&​rft.pub=Lambda-bound.com&​rft_id=http%3A%2F%2Fwww.lambda-bound.com%2Fbook%2Flambdacalc%2Fnode27.html&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-Selinger-17"><​span class="​mw-cite-backlink">​^ <​sup><​i><​b>​a</​b></​i></​sup>​ <​sup><​i><​b>​b</​b></​i></​sup></​span>​ <span class="​reference-text">​
 +<cite id="​CITEREFSelinger2008"​ class="​citation">​Selinger,​ Peter (2008), <​i>​Lecture Notes on the Lambda Calculus</​i>​ <span class="​cs1-format">​(PDF)</​span><​b>​0804</​b>​ (class: cs.LO), Department of Mathematics and Statistics, University of Ottawa, p. 9, arXiv:<​span class="​cs1-lock-free"​ title="​Freely accessible">​0804.3434</​span>​Bibcode:​2008arXiv0804.3434S</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Lecture+Notes+on+the+Lambda+Calculus&​rft.pages=9&​rft.pub=Department+of+Mathematics+and+Statistics%2C+University+of+Ottawa&​rft.date=2008&​rft_id=info%3Aarxiv%2F0804.3434&​rft_id=info%3Abibcode%2F2008arXiv0804.3434S&​rft.aulast=Selinger&​rft.aufirst=Peter&​rft_id=http%3A%2F%2Fwww.mathstat.dal.ca%2F~selinger%2Fpapers%2Flambdanotes.pdf&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-BarendregtBarendsen-18"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFBarendregtBarendsen2000"​ class="​citation">​Barendregt,​ Henk; Barendsen, Erik (March 2000), <​i>​Introduction to Lambda Calculus</​i>​ <span class="​cs1-format">​(PDF)</​span></​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Introduction+to+Lambda+Calculus&​rft.date=2000-03&​rft.aulast=Barendregt&​rft.aufirst=Henk&​rft.au=Barendsen%2C+Erik&​rft_id=ftp%3A%2F%2Fftp.cs.ru.nl%2Fpub%2FCompMath.Found%2Flambda.pdf&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-19"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​de Queiroz, Ruy J. G. B. (1988). &quot;A Proof-Theoretic Account of Programming and the Role of Reduction Rules&​quot;​. <​i>​Dialectica</​i>​. <​b>​42</​b>​ (4): 265–282. doi:​10.1111/​j.1746-8361.1988.tb00919.x.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Dialectica&​rft.atitle=A+Proof-Theoretic+Account+of+Programming+and+the+Role+of+Reduction+Rules&​rft.volume=42&​rft.issue=4&​rft.pages=265-282&​rft.date=1988&​rft_id=info%3Adoi%2F10.1111%2Fj.1746-8361.1988.tb00919.x&​rft.aulast=de+Queiroz&​rft.aufirst=Ruy+J.+G.+B.&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-20"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFTurbakGifford2008"​ class="​citation">​Turbak,​ Franklyn; Gifford, David (2008), <​i>​Design concepts in programming languages</​i>​MIT press, p. 251, ISBN 978-0-262-20175-9</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Design+concepts+in+programming+languages&​rft.pages=251&​rft.pub=MIT+press&​rft.date=2008&​rft.isbn=978-0-262-20175-9&​rft.aulast=Turbak&​rft.aufirst=Franklyn&​rft.au=Gifford%2C+David&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-21"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite id="​CITEREFFelleisenFlatt2006"​ class="​citation">​Felleisen,​ Matthias; Flatt, Matthew (2006), <​i>​Programming Languages and Lambda Calculi</​i>​ <span class="​cs1-format">​(PDF)</​span>​p. 26, archived from the original <span class="​cs1-format">​(PDF)</​span>​ on 2009-02-05</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Programming+Languages+and+Lambda+Calculi&​rft.pages=26&​rft.date=2006&​rft.aulast=Felleisen&​rft.aufirst=Matthias&​rft.au=Flatt%2C+Matthew&​rft_id=http%3A%2F%2Fwww.cs.utah.edu%2Fplt%2Fpublications%2Fpllc.pdf&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>;​ a note (accessed 2017) at the original location suggests that the authors consider the work originally referenced to have been superseded by a book.</​span>​
 +</li>
 +<li id="​cite_note-22"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text">​Types and Programming Languages, p. 273, Benjamin C. Pierce</​span>​
 +</li>
 +<li id="​cite_note-23"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Landin,​ P. J. (1965). &quot;A Correspondence between ALGOL 60 and Church&#​39;​s Lambda-notation&​quot;​. <​i>​Communications of the ACM</​i>​. <​b>​8</​b>​ (2): 89–101. doi:​10.1145/​363744.363749.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Communications+of+the+ACM&​rft.atitle=A+Correspondence+between+ALGOL+60+and+Church%27s+Lambda-notation&​rft.volume=8&​rft.issue=2&​rft.pages=89-101&​rft.date=1965&​rft_id=info%3Adoi%2F10.1145%2F363744.363749&​rft.aulast=Landin&​rft.aufirst=P.+J.&​rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D363749%26coll%3Dportal%26dl%3DACM&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-24"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Statman,​ R. (1979). &​quot;​The typed λ-calculus is not elementary recursive&​quot;​. <​i>​Theoretical Computer Science</​i>​. <​b>​9</​b>​ (1): 73–81. doi:​10.1016/​0304-3975(79)90007-0.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Theoretical+Computer+Science&​rft.atitle=The+typed+%CE%BB-calculus+is+not+elementary+recursive&​rft.volume=9&​rft.issue=1&​rft.pages=73-81&​rft.date=1979&​rft_id=info%3Adoi%2F10.1016%2F0304-3975%2879%2990007-0&​rft.aulast=Statman&​rft.aufirst=R.&​rft_id=http%3A%2F%2Fieeexplore.ieee.org%2Fxpl%2Ffreeabs_all.jsp%3Farnumber%3D4567929&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​span>​
 +</li>
 +<li id="​cite_note-25"><​span class="​mw-cite-backlink"><​b>​^</​b></​span>​ <span class="​reference-text"><​cite class="​citation journal">​Sinot,​ F.-R. (2005). &​quot;​Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting&​quot;​. <​i>​Journal of Logic and Computation</​i>​. <​b>​15</​b>​ (2): 201–218. doi:​10.1093/​logcom/​exi010.</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=article&​rft.jtitle=Journal+of+Logic+and+Computation&​rft.atitle=Director+Strings+Revisited%3A+A+Generic+Approach+to+the+Efficient+Representation+of+Free+Variables+in+Higher-order+Rewriting&​rft.volume=15&​rft.issue=2&​rft.pages=201-218&​rft.date=2005&​rft_id=info%3Adoi%2F10.1093%2Flogcom%2Fexi010&​rft.aulast=Sinot&​rft.aufirst=F.-R.&​rft_id=http%3A%2F%2Fwww.lsv.ens-cachan.fr%2F~sinot%2Fpublis.php%3Fonlykey%3Dsinot-jlc05&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/><​sup class="​noprint Inline-Template"><​span style="​white-space:​ nowrap;">​[<​i><​span title="​ Dead link since December 2017">​permanent dead link</​span></​i>​]</​span></​sup></​span>​
 +</li>
 +</​ol></​div>​
 +<​h2><​span class="​mw-headline"​ id="​Further_reading">​Further reading</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​ul><​li>​Abelson,​ Harold &amp; Gerald Jay Sussman. Structure and Interpretation of Computer Programs. The MIT Press. <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ISBN 0-262-51087-1.</​li>​
 +<​li>​Hendrik Pieter Barendregt <​i>​Introduction to Lambda Calculus</​i>​.</​li>​
 +<​li>​Henk Barendregt, The Impact of the Lambda Calculus in Logic and Computer Science. The Bulletin of Symbolic Logic, Volume 3, Number 2, June 1997.</​li>​
 +<​li>​Barendregt,​ Hendrik Pieter, <​i>​The Type Free Lambda Calculus</​i>​ pp1091–1132 of <​i>​Handbook of Mathematical Logic</​i>​North-Holland (1977) <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ISBN 0-7204-2285-X</​li>​
 +<​li>​Cardone and Hindley, 2006. History of Lambda-calculus and Combinatory Logic. In Gabbay and Woods (eds.), <​i>​Handbook of the History of Logic</​i>​vol. 5. Elsevier.</​li>​
 +<​li>​Church,​ Alonzo, <i>An unsolvable problem of elementary number theory</​i>​American Journal of Mathematics,​ 58 (1936), pp. 345–363. This paper contains the proof that the equivalence of lambda expressions is in general not decidable.</​li>​
 +<​li>​Alonzo Church, <​i>​The Calculi of Lambda-Conversion</​i>​ (<link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ISBN 978-0-691-08394-0)<​sup id="​cite_ref-26"​ class="​reference">​[1]</​sup></​li>​
 +<​li>​Kleene,​ Stephen, <i>A theory of positive integers in formal logic</​i>​American Journal of Mathematics,​ 57 (1935), pp. 153–173 and 219–244. Contains the lambda calculus definitions of several familiar functions.</​li>​
 +<​li>​Landin,​ Peter, <i>A Correspondence Between ALGOL 60 and Church&#​39;​s Lambda-Notation</​i>​Communications of the ACM, vol. 8, không. 2 (1965), pages 89–101. Available from the ACM site. A classic paper highlighting the importance of lambda calculus as a basis for programming languages.</​li>​
 +<​li>​Larson,​ Jim, <i>An Introduction to Lambda Calculus and Scheme</​i>​. A gentle introduction for programmers.</​li>​
 +<​li>​Schalk,​ A. and Simmons, H. (2005) <i>An introduction to λ-calculi and arithmetic with a decent selection of exercises. Notes for a course in the Mathematical Logic MSc at Manchester University.</​i></​li>​
 +<​li>​de Queiroz, Ruy J.G.B. (2008) &​quot;​On Reduction Rules, Meaning-as-Use and Proof-Theoretic Semantics&​quot;​. <​i>​Studia Logica</​i><​b>​90</​b>​(2):​211–247. doi:​10.1007/​s11225-008-9150-5. A paper giving a formal underpinning to the idea of &#​39;​meaning-is-use&#​39;​ which, even if based on proofs, it is different from proof-theoretic semantics as in the Dummett–Prawitz tradition since it takes reduction as the rules giving meaning.</​li>​
 +<​li>​Hankin,​ Chris, <i>An Introduction to Lambda Calculi for Computer Scientists,</​i>​ <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ISBN 0954300653</​li></​ul><​p>​Monographs/​textbooks for graduate students:
 +</p>
 +<​ul><​li>​Morten Heine Sørensen, Paweł Urzyczyn, <​i>​Lectures on the Curry-Howard isomorphism</​i>​Elsevier,​ 2006, <link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ISBN 0-444-52077-5 is a recent monograph that covers the main topics of lambda calculus from the type-free variety, to most typed lambda calculi, including more recent developments like pure type systems and the lambda cube. It does not cover subtyping extensions.</​li>​
 +<​li><​cite id="​CITEREFPierce2002"​ class="​citation">​Pierce,​ Benjamin (2002), <​i>​Types and Programming Languages</​i>​MIT Press, ISBN 0-262-16209-1</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=book&​rft.btitle=Types+and+Programming+Languages&​rft.pub=MIT+Press&​rft.date=2002&​rft.isbn=0-262-16209-1&​rft.aulast=Pierce&​rft.aufirst=Benjamin&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/>​ covers lambda calculi from a practical type system perspective;​ some topics like dependent types are only mentioned, but subtyping is an important topic.</​li></​ul><​p><​i>​Some parts of this article are based on material from FOLDOC, used with permission.</​i>​
 +</p>
 +<​h2><​span class="​mw-headline"​ id="​External_links">​External links</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​edit<​span class="​mw-editsection-bracket">​]</​span></​span></​h2>​
 +<​ul><​li>​Graham Hutton, Lambda Calculus, a short (12 minutes) Computerphile video on the Lambda Calculus</​li>​
 +<​li>​Helmut Brandl, <i>A Step by Step Introduction into Lambda Calculus</​i></​li>​
 +<​li><​cite id="​CITEREFHazewinkel2001"​ class="​citation">​Hazewinkel,​ Michiel, ed. (2001) [1994]&​quot;​Lambda-calculus&​quot;,​ <​i>​Encyclopedia of Mathematics</​i>​Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4</​cite><​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&​rft.genre=bookitem&​rft.atitle=Lambda-calculus&​rft.btitle=Encyclopedia+of+Mathematics&​rft.pub=Springer+Science%2BBusiness+Media+B.V.+%2F+Kluwer+Academic+Publishers&​rft.date=2001&​rft.isbn=978-1-55608-010-4&​rft_id=https%3A%2F%2Fwww.encyclopediaofmath.org%2Findex.php%3Ftitle%3Dp%2Fl057000&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​li>​
 +<​li>​Achim Jung, <i>A Short Introduction to the Lambda Calculus</​i>​-(PDF)</​li>​
 +<​li>​Dana Scott, <i>A timeline of lambda calculus</​i>​-(PDF)</​li>​
 +<​li>​David C. Keenan, <i>To Dissect a Mockingbird:​ A Graphical Notation for the Lambda Calculus with Animated Reduction</​i></​li>​
 +<​li>​Raúl Rojas, <i>A Tutorial Introduction to the Lambda Calculus</​i>​-(PDF)</​li>​
 +<​li>​Peter Selinger, <​i>​Lecture Notes on the Lambda Calculus</​i>​-(PDF)</​li>​
 +<​li>​L. Allison, <​i>​Some executable λ-calculus examples</​i></​li>​
 +<​li>​Georg P. Loczewski, <​i>​The Lambda Calculus and A++</​i></​li>​
 +<​li>​Bret Victor, <​i>​Alligator Eggs: A Puzzle Game Based on Lambda Calculus</​i></​li>​
 +<​li><​i>​Lambda Calculus</​i>​ on Safalra&#​39;​s Website</​li>​
 +<​li><​i><​cite class="​citation web">&​quot;​Lambda Calculus&​quot;​. </​cite></​i>​PlanetMath<​i>​.<​span title="​ctx_ver=Z39.88-2004&​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&​rft.genre=unknown&​rft.jtitle=PlanetMath&​rft.atitle=Lambda+Calculus&​rft_id=http%3A%2F%2Fplanetmath.org%2F%3Fop%3Dgetobj%26amp%3Bfrom%3Dobjects%26amp%3Bid%3D2788&​rfr_id=info%3Asid%2Fen.wikipedia.org%3ALambda+calculus"​ class="​Z3988"/><​link rel="​mw-deduplicated-inline-style"​ href="​mw-data:​TemplateStyles:​r861714446"/></​i></​li>​
 +<​li>​LCI Lambda Interpreter a simple yet powerful pure calculus interpreter</​li>​
 +<​li>​Lambda Calculus links on Lambda-the-Ultimate</​li>​
 +<​li>​Mike Thyer, Lambda Animator, a graphical Java applet demonstrating alternative reduction strategies.</​li>​
 +<​li>​Implementing the Lambda calculus using C++ Templates</​li>​
 +<​li>​Marius Buliga, <​i>​Graphic lambda calculus</​i></​li>​
 +<​li><​i>​Lambda Calculus as a Workflow Model</​i>​ by Peter Kelly, Paul Coddington, and Andrew Wendelborn; mentions graph reduction as a common means of evaluating lambda expressions and discusses the applicability of lambda calculus for distributed computing (due to the Church–Rosser property, which enables parallel graph reduction for lambda expressions).</​li>​
 +<​li>​Shane Steinert-Threlkeld,​ &​quot;​Lambda Calculi&​quot;,​ <​i>​Internet Encyclopedia of Philosophy</​i></​li>​
 +<​li>​Anton Salikhmetov,​ <​i>​Macro Lambda Calculus</​i></​li></​ul>​
 +
 +<​!-- ​
 +NewPP limit report
 +Parsed by mw1333
 +Cached time: 20181115104842
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.884 seconds
 +Real time usage: 1.190 seconds
 +Preprocessor visited node count: 4022/​1000000
 +Preprocessor generated node count: 0/1500000
 +Post‐expand include size: 74732/​2097152 bytes
 +Template argument size: 2869/​2097152 bytes
 +Highest expansion depth: 12/40
 +Expensive parser function count: 12/500
 +Unstrip recursion depth: 1/20
 +Unstrip post‐expand size: 79330/​5000000 bytes
 +Number of Wikibase entities loaded: 5/400
 +Lua time usage: 0.318/​10.000 seconds
 +Lua memory usage: 5.99 MB/50 MB
 +-->
 +<!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​ 730.712 ​     1 -total
 + ​35.48% ​ 259.260 ​     1 Template:​Reflist
 + ​21.97% ​ 160.544 ​    11 Template:​Cite_journal
 + ​12.44% ​  ​90.896 ​     1 Template:​No_footnotes
 +  9.20%   ​67.249 ​     5 Template:​Isbn
 +  8.19%   ​59.872 ​     2 Template:​Ambox
 +  8.02%   ​58.581 ​     9 Template:​Citation
 +  7.31%   ​53.435 ​     1 Template:​Authority_control
 +  4.04%   ​29.521 ​     2 Template:​Fix
 +  4.01%   ​29.315 ​     1 Template:​Citation_needed
 +-->
 +
 +<!-- Saved in parser cache with key enwiki:​pcache:​idhash:​18203-0!canonical!math=5 and timestamp 20181115104841 and revision id 866654470
 + ​-->​
 +</​div></​pre>​
 + </​HTML> ​
t-nh-to-n-lambda-wikipedia.txt · Last modified: 2018/11/17 09:54 (external edit)