(Gentle) Introduction to λ-Calculus
Copyright © 2018 by . All Rights Reserved.
Learning Outcomes
Copyright By PowCoder代写 加微信 powcoder
by the End of the Lecture, Students that Complete
the Recommended Exercises should be Able to:
Describe the Fundamentals of λ-Calculus Employ β-Reduction to Evaluate a Function Application Explain How Numbers can be Represented Demonstrate How Arithmetic Operations are Possible
Copyright © 2018 by . All Rights Reserved.
Reading and Suggested Exercises
Copyright © 2018 by . All Rights Reserved.
Read the following Chapter(s): None
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
What is a Turing Machine?
Turing Machines and λ-Calculus
Turing Machine is a Definition for an Abstract and Mathematical Model of Computation
a Universal Turing Machine is a Turing Machine that can Simulate any other Turing Machine
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
“…an infinite tape marked out into squares, on each of which a symbol could be printed…”
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
“…at any moment there is one symbol in the machine… the machine can alter the scanned symbol…”
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
“…the tape can be moved back and forth through the machine, this being one of the elementary operations…”
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
it has been Proven that Any Algorithm can be Implemented as a Turing Machine
Turing Machines were Developed to be the Simplest Possible “Computer” that would be Able to Calculate All Possible calculable Functions
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
What is the Significance of the Universal Turing Machine to Computer Science?
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
a System is said to be Turing Complete if it can Simulate a Universal Turing Machine (and thus
a Computing Device or Programming Language that is Turing Complete has the Same Capabilities as any other Turing Complete Machine or Language
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
Turing Machines were Invented by in 1936 to Answer Questions about Computability (specifically the “Entscheidungsproblem”)
Turing Referenced the λ-Calculus introduced by (who actually published a proof of the “Entscheidungsproblem” just Before Turing)
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
Any Computable Function can be Expressed and Evaluated using a Turing Machine or (alternatively) Church’s λ-Calculus
if Turing Machines are considered Hypothetical “Hardware”, then λ-Calculus could be considered Analogous to Hypothetical “Software”
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
What is the Significance of the λ-Calculus to Computer Science?
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
Functional Programming Languages (including Haskell) are Implementations of the λ-Calculus
Copyright © 2018 by . All Rights Reserved.
Copyright © 2018 by . All Rights Reserved.
Turing Machines and λ-Calculus
Why is it Called λ-Calculus?
Turing Machines and λ-Calculus
Church Intended to use Notation 𝑥ො … 𝑥 … but Typesetting Issues changed it to ∧ 𝑥 … 𝑥 … and it was Later Assumed that ∧ was Λ (i.e., Capital λ)
the word “Calculus” just means System of Reasoning (n.b., if you ever took Database Management with me I would teach you Tuple Relational Calculus)
Copyright © 2018 by . All Rights Reserved.
Anonymous Functions
How Many of you have seen Lambdas in Python?
Copyright © 2018 by . All Rights Reserved.
Anonymous Functions
in Python the Procedures used to Organize Code and Reduce Redundancies are known as “Functions” and they are typically Defined using the Keyword def
when a Function will Only be Used Once and can Remain Anonymous, it can be Defined with lambda
Copyright © 2018 by . All Rights Reserved.
Anonymous Functions
faculty_data = [(5326, ‘Collier’), (5127, ‘Lanthier’),
(5332, ‘Hinek’), (5376, ‘Laurendeau’)]
print(faculty_data)
Assuming the Tuples in faculty_data are (Room Number, Last Name),
How do you Sort the List by Room Number?
Copyright © 2018 by . All Rights Reserved.
faculty_data = [(5326, ‘Collier’), (5127, ‘Lanthier’),
(5332, ‘Hinek’), (5376, ‘Laurendeau’)]
print(faculty_data)
faculty_data.sort() print(faculty_data)
How do you Sort the List by Last Name? Copyright © 2018 by . All Rights Reserved.
Anonymous Functions
Anonymous Functions
faculty_data = [(5326, ‘Collier’), (5127, ‘Lanthier’),
(5332, ‘Hinek’), (5376, ‘Laurendeau’)]
print(faculty_data)
faculty_data.sort() print(faculty_data)
faculty_data.sort(key = lambda x: x[1]) print(faculty_data)
Copyright © 2018 by . All Rights Reserved.
Anonymous Functions
Anonymous Functions (or Lambda Abstractions) are Procedures Without Identifiers, Defined using a Syntax that is Similar to λ-Calculus
they are Included in Many Programming Languages (including Python, C++, Java, Haskell, Lisp, Scheme, etc.) typically for Procedures that require Other Procedures as Arguments or Return Values
Copyright © 2018 by . All Rights Reserved.
λ-Calculus Basics a Function in Lambda Calculus is
the Application of a Function to an Argument is (𝝀𝒙.𝑬𝟏)𝑬𝟐
𝑬𝟏 is an Expression that represents the Function Body 𝑬𝟐 is an Expression that represents the Argument
Copyright © 2018 by . All Rights Reserved.
Programmers Recognize the Equivalence of: def foo(a, b): and def foo(x, y):
return a*b return x*y
Unsurprisingly, there is a Rule in λ-Calculus called α-Equivalence for Addressing the Same Issue
e.g., 𝝀𝒙. 𝒙 is α-Equivalent to 𝝀𝒚. 𝒚 Copyright © 2018 by . All Rights Reserved.
λ-Calculus Basics
Function Applications in λ-Calculus are Reduced (i.e., Evaluated) using β-Reduction
the β-Reduction of the Function Application 𝝀𝒙. 𝑬𝟏 𝑬𝟐 will be a Modification of the Expression 𝑬𝟏 in which All Occurrences of 𝒙 appearing in 𝑬𝟏 are Replaced by 𝑬𝟐
λ-Calculus Basics
Copyright © 2018 by . All Rights Reserved.
β-Reduction Replace All Instances of the Variable
in the Expressionwith the Expression 𝝀.
Copyright © 2018 by . All Rights Reserved.
the Simplest Function (that doesn’t just disregard input and return a constant) is the Identity Function
performing β-Reduction on the Application of the Identity Function to an Argument Expression
(𝑦, for instance) simply Results in the Argument again
β-Reduction
Copyright © 2018 by . All Rights Reserved.
β-Reduction Replace All Instances of the Variable 𝒙
in the Expression 𝒙 with the Expression 𝒚
Copyright © 2018 by . All Rights Reserved.
another Simple Function (that might not strike you as particularly useful yet) could be the Function
performing β-Reduction on the Application of this Function to an Argument Expression (𝑦, for instance) would be Two Copies of the Expression 𝑦
β-Reduction
Copyright © 2018 by . All Rights Reserved.
β-Reduction Replace All Instances of the Variable 𝒙
in the Expression 𝒙 𝒙 with the Expression 𝒚
= [𝒚/𝒙] 𝒙 𝒙
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars
the Context-Free Grammar of a Language is a Set
of Production Rules defining Possible “Sentences”
a Production Rule is an Expression of the Form 𝑥→𝑦
used to Indicate that Occurrences of 𝑥 can be Replaced by Occurrences of 𝑦
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars this Grammar is for (Really) Simple English…
𝑠𝑒𝑛𝑡𝑒𝑛𝑐𝑒 𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏 𝑝h𝑟𝑎𝑠𝑒
→ 𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏 𝑝h𝑟𝑎𝑠𝑒
→ 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡 𝑛𝑜𝑢𝑛
→ 𝑖𝑛𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒𝑣𝑒𝑟𝑏
→ 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 𝑣𝑒𝑟𝑏 𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars …this Grammar is for Simple Arithmetic…
𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛
→ 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑜𝑝𝑒𝑟𝑎𝑡𝑜𝑟 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 → ( 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 )
→ − 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars …and this Grammar is for λ-Calculus…
𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑎𝑝𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛
→ 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑎𝑝𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛 → 𝜆 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 . 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛
→ 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛
n.b., “|” is just used to separate alternatives; the 1st rule above is equivalent to:
𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑒𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛
→ 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒
→ 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛
→ 𝑎𝑝𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars λ-Calculus is Left Associative (like Arithmetic)
Parentheses can be used to Enforce Precedence (but there are Implied Parentheses as well)
𝑎𝑏𝑐𝑑= 𝑎𝑏𝑐𝑑= 𝑎𝑏𝑐𝑑= 𝑎𝑏𝑐𝑑 𝑎𝑏(𝑐𝑑)𝑒= 𝑎𝑏 𝑐𝑑 𝑒= 𝑎𝑏 (𝑐𝑑) 𝑒= 𝑎𝑏 (𝑐𝑑) 𝑒
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars
there is Obviously Something Missing from the English and Arithmetic Grammars introduced
simply put, it is Not Possible to Create Sentences in the English Language without Words
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars this Updated Simple English Grammar is…
𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏 𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏 𝑝h𝑟𝑎𝑠𝑒 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡 𝑛𝑜𝑢𝑛
𝑛𝑜𝑢𝑛 𝑖𝑛𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 𝑣𝑒𝑟𝑏 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 𝑣𝑒𝑟𝑏
→ 𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒 𝑣𝑒𝑟𝑏 𝑝h𝑟𝑎𝑠𝑒 → 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡 𝑛𝑜𝑢𝑛
→ 𝑖𝑛𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 𝑣𝑒𝑟𝑏
→ 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑒 𝑣𝑒𝑟𝑏
→ 𝑡h𝑒 → 𝑐𝑎𝑡 → 𝑏𝑖𝑟𝑑 → 𝑠𝑖𝑛𝑔𝑠 → 𝑒𝑎𝑡𝑠
𝑛𝑜𝑢𝑛 𝑝h𝑟𝑎𝑠𝑒
Copyright © 2018 by . All Rights Reserved.
Context-Free Grammars
it might surprise you to learn that, other than choosing different letters for variables, λ-Calculus Does Not Have Any “Words” – Only Functions
Then How can it be Useful?
If λ-Calculus is supposed to be the Foundation of a Programming Language, then where are the Numbers, Boolean Values, Data and Control Structures, etc.?
Copyright © 2018 by . All Rights Reserved.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com