UA CS 520 - Principles of Programming Languages

Unformatted text preview:

Lambda CalculusLambda CalculusIntroductory ExampleIntroductory ExampleIntroductory Exampleldots Introductory Exampleldots Introductory Exampleldots Introductory Exampleldots SyntaxSyntaxSyntax --- Function ApplicationSyntax --- Function Applicationldots Syntax --- Function AbstractionSyntax --- Function Abstractionldots VariablesVariablesldots Variablesldots Syntax --- Naming expressionsSyntax --- Multiple ArgumentsSyntax --- Multiple Argumentsldots Syntax --- Multiple Argumentsldots ExamplesExample --- The identity functionExample --- EvaluationExample --- Parsing ExpressionsExample --- Parsing Expressionsldots Example --- Parsing Expressionsldots Example --- Bound/Free VariablesReadings and ReferencesAcknowledgments520—Spring 2005—21CSc 520Principles of ProgrammingLanguages21: Lambda Calculus — IntroductionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—21Lambda CalculusDeveloped by Alonzo Church and Haskell Curry in the1930s and 40s.Branch of mathematical logic. Provides a foundation formathematics. Describes — like Turing machines — thatwhich can be effectively computed.In contrast to Turing machines, lambda calculus doesnot care about any underlying “hardware” but ratheruses simple syntactic transformation rules to definecomputations.[2]520—Spring 2005—21Lambda CalculusA theory of functions where functions are manipulatedin a purely syntactic way.In lambda Calculus, everything is represented as afunction.Functional programming languages are variations onlambda calculus.Lambda calculus is the theoretical foundation offunctional programming languages.“the smallest universal programming language”.Sparse syntax and simple semantics — still, powerfullenough to represent all computable functions.[3]520—Spring 2005—21Introductory Example[4]520—Spring 2005—21Introductory ExampleLet’s look at how a lambda expression is evaluated.You are not expected to understand this, yet.The functionf(x, y, z) = x ∗ y + zlooks like this in lambda calculus:f ≡ (λx.(λy.(λz.add (mul x y) z)))[5]520—Spring 2005—21Introductory Example...Let’s evaluatef(3, 4, 5) = 3 ∗ 4 + 5or, in Scheme> ((((lambda (x)(lambda (y)(lambda (z) (+ (* x y) z))))3) 4) 5)17or, in lambda calculus:((((λx.(λy.(λz.add (mul x y) z))) 3) 4) 5)[6]520—Spring 2005—21Introductory Example...Evaluation is done by substitution. The first step is toreplace x with 3:((((λx.(λy.(λz.add (mul x y) z))) 3) 4) 5) ⇒(((λy.(λz.add (mul 3 y) z)) 4) 5)Next, we replace y with 4:((((λx.(λy.(λz.add (mul x y) z))) 3) 4) 5) ⇒(((λy.(λz.add (mul 3 y) z)) 4) 5) ⇒((λz.add (mul 3 4) z) 5)[7]520—Spring 2005—21Introductory Example...Next, we multiply 3 ∗ 4:((((λx.(λy.(λz.add (mul x y) z))) 3) 4) 5) ⇒(((λy.(λz.add (mul 3 y) z)) 4) 5) ⇒((λz.add (mul3 4) z) 5) ⇒((λz.add 12 z) 5)[8]520—Spring 2005—21Introductory Example...Finally, we replace z by 5 and add:((((λx.(λy.(λz.add (mul x y) z))) 3) 4) 5) ⇒(((λy.(λz.add (mul 3 y) z)) 4) 5) ⇒((λz.add (mul 3 4) z) 5) ⇒((λz.add 12 z) 5)(add12 5)17[9]520—Spring 2005—21Syntax[10]520—Spring 2005—21SyntaxThere are four kinds of lambda expressions:1.variables (lower-case letters)2.predefined constants and operations (numbers andarithmetic operators)3.function applications4.function abstraction (function definitions)expression ::=variable |constant |( expression expression ) |( λ variable . expression )[11]520—Spring 2005—21Syntax — Function ApplicationIn the expression(E1E2)we expect E1to evaluate to a function, either apredefined one like add or mul or one defined byourselves, as a lambda abstraction.For example, in(sqrt 9)sqrtrepresents the constant (predefined) square rootfunction, and 9 it’s argument.[12]520—Spring 2005—21Syntax — Function Application...Most authors leave out parenteses whenever possible.We will assume function application associatesleft-to-right.Example:f A Bshould be interpreted as((f A) B)not(f (A B))[13]520—Spring 2005—21Syntax — Function AbstractionIn(λx.times x x)the λ introduces x as a formal parameter to the functiondefinition.Function application binds tighter than functiondefinition. For example,(λx.A B)should be interpreted as(λx.(A B))not((λx.A) B)[14]520—Spring 2005—21Syntax — Function Abstraction...In other words, the scope of(λx. · · · )extends as far right as possible.For example,(λx.A B C)means(λx.((A B) C))not((λx.(A B)) C)or((λx.A) (B C))[15]520—Spring 2005—21VariablesIn(λx.E)the variable x is said to be bound within E.This is similar to scope in other programminglanguages:{int x;· · ·print x}[16]520—Spring 2005—21Variables...In(λx.square y)the variable y is said to be free.Similar to other programming languages, a free variableis typically bound within an outer scope, like y here:{int y;{· · ·print y}}[17]520—Spring 2005—21Variables...Consider the expression(λx.(λy.times x y))In the inner expression(λy.times x y)xis free, y is bound.Variables can hold any kind of value, includingfunctions.We say functions are Polymorphic — they can takearguments of any type.[18]520—Spring 2005—21Syntax — Naming expressionsWe can give expressions names, so we can refer tothem later:square ≡ (λx.(times x x))≡ means is an abbreviation for.[19]520—Spring 2005—21Syntax — Multiple ArgumentsA lambda abstraction can only take one argument:(λx.(times x x))To simulate multi-argument functions we use currying.The abstraction(λf.(λx.f(f x)))represents a function with two arguments, a function f,and a value x, and which applies f twice to x.[20]520—Spring 2005—21Syntax — Multiple Arguments...Example:(((λf.(λx.f(f x))) sqr) 3) =((λx.sqr(sqr x)) 3) =sqr(sqr 3) =(sqr 9) = 81In the first step, f is replaced by sqr (the squaringfunction).In the second step, x is replaced by 3.[21]520—Spring 2005—21Syntax — Multiple Arguments...Some authors use the abbreviation(λx y z.E)to mean(λx.(λy.(λz.E)))In general, different books on lambda calculus will useslight variations in syntax.[22]520—Spring 2005—21Examples[23]520—Spring 2005—21Example — The identity functionThis(λx.x)is the identity function.The expression((λx.x) E)will return E for any lambda expression E.For example, the expression((λx.x) (sqr 3))will return 9.[24]520—Spring 2005—21Example — EvaluationThe expression(λn.add n 1)is the


View Full Document

UA CS 520 - Principles of Programming Languages

Download Principles of Programming Languages
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Principles of Programming Languages and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Principles of Programming Languages 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?