### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# PROGRAMMING LANGUAGES CSCI 4430

RPI

GPA 3.63

### View Full Document

## 5

## 0

## Popular in Course

## Popular in ComputerScienence

This 34 page Class Notes was uploaded by Ransom Blanda on Monday October 19, 2015. The Class Notes belongs to CSCI 4430 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/224849/csci-4430-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.

## Reviews for PROGRAMMING LANGUAGES

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

CSCl4430 6969 Programming Languages Lecture Notes September 7 2006 24 Sequencing Combinator The normal order sequencing combinator is Seq AziAyiOxziy z where 2 is chosen so that it does not appear free in y This combinator guarantees that x is evaluated before y which is important in programs with side effects Assuming we had a display function sending output to the console an example is Seq display hello display world The combinator would not work in applicative order call by value evaluation because evaluating the display functions before getting them passed to the Seq function would defeat the purpose of the combinator to sequence executioni In particular if the arguments are evaluated right to left execution would not be as expecte i The applicative order sequencing combinator can be written as follows ASeq AziAyiy z where y is a lambda abstraction that wraps the original last expression to evaluate The same example above would be written as follows ASeq display hello Azidisplay world with 1 fresh that is not appearing free in the second expression This strategy of wrapping a lambdacalculus expression to make it a value and delay its evaluation is very useful It enables to simulate call by name parameter passing in languages using call by value The process of wrapping is also called freezing an expression and the resulting frozen expression is called a thank Evaluating a thunk to get back the original expression is also called thawing 25 nConversion Consider the expression Aziziz2 z Using reduction we can take E Arm2 1 and M y In the reduction we only replace the one I that is free in E to get 3 Arm2 We use the symbol 3 to show that we are performing reduction on the expression As another example we may write A112 3 Ayiy2 since arenaming is taking place Another type of operation possible on lambda calculus expressions is called 77conversion eta77reduction when applied from left to right We perform nreduction using the rule AzlE I l E nreduction can only be applied if E is a lambda expression taking a single argument and I does not appear free in Starting with the expression ALQxLIQ I we can perform 77reduction to obtain AziOxzizQ x l ALI Starting with the same expression as before AzlAzizQ z y we can perform 77reduction to obtain Aziziz2 z y l Aziz2 y which gives the same result as reductioni Another example of nreduction follows Arty I l y nreduction can be considered a program optimization For example consider the following Oz de ni tions declare Increment fun X X1 end declare Inc fun X Increment X end Using nreduction we could reduce Inc 6 to Increment 6 avoiding one extrafunction call This compiler optimization is also called inlz39m39ngi nconversion can also affect termination of expressions in applicative order expression evaluation For example the Y reduction combinator has a terminating applicative order form that can be derived from the normal order combinator form by using nconversion see Section 26 26 Recursion Combinator The recursion combinator allows recursion in lambda expressionsi For example suppose we want to implement a recursive version of the factorial operation l ifn0 ni nnill ifngt0 We could start by attempting to write a the recursive function f in the lambda calculus assuming it has been extended with conditionals and numbers f AgAnt n 0 1 n 9 7 n 1 This function does not work yet because it does not receive a single argumenti Before we can input an integer to the function we must input a function to satisfy 9 so that the returning function is the desired factoriali Letls call this function Xi Looking within the function we see that the function X must take an integer and return an integer that is its type is Z A Z The function f will return the proper recursive function with the type Z A Z but only when supplied with the correct function Xi Knowing the input and output types of f we can write the type of f as fZgtZgtZgtZi What we need is a function X that when applied to f returns the correct recursive function We could try applying f to itself ie f f A This does not work because f expects something of type Z A Z but it is taking another f which has the more complex type Z A Z A Z A Z A function that has the correct input type is the identity combinator Azizi Applying the identity function we get f I Aniif n0 1 n I n 1 Aniif n 0 1 n n 17 which is equivalent to 1 if n 0 7M n71 ifngt0 We need to nd the correct expression X such that when X is applied to f we get the recursive factorial function It turns out that the X that works is X Aziginiif n 0 1 n g 7 n I wwwmenmlmuenm wwmw Note that this has a structure similar to the nonterminating expression Azlz I Azlz 1 and explains why the recursive function can keep going X can be de ned as Y where Y is the recursion combinator f X v f Y 103 f The recursion combinator that works for an applicative evaluation order is de ned as Yfi MU Ay r 1 y MU Ayiz 1 y The same combinator that is valid for normal order is Yfi I Mama How do we get from normal ordering to applicative order Use 77expansion that is nconversion in reverse This is an example where 77conversion can have an impact on the termination of an expression 3 HigherOrder Programming Most imperative programming languages eigi Java and C do not allow us to treat functions or procedures as rstclass entities for example we cannot create and return a new function that did not exist before A function that can only deal with data values is called a rstorder function For example Increment whose type is Z A Z can only take integer values and return integer values Programming only with rstorder functions is called rstorder programming If a function can take another function as an argument or if it returns a function it is called a higher order functioni For example the Curry combinator whose type is CurryZgtltZgtZgtZgtZgtZ is a higherorder third order function It takes a function of type Z X Z A Z and returns a function of type Z A Z A Z That is Curry takes a rstorder function and returns a secondorder function The ability to View functions as data is called higherorder programming 31 Currying as a higherorder function Higherorder programming is a very powerful technique as shown in the following Oz example Consider an exponential function Exp as fol ows declare Exp fun B N if N0 then 1 else B Exp B Nl end end And recall the Curry combinator in Oz declare Curry fun F fun X fun Y F X Y end end end We can create a function to compute the powers of 2 Ton by just using declare Ton Curry Exp 2 If we want to create a Square function using Exp we can create a reverse curry combinator RCurry declare RCurry fun F fun X fun Y F Y X end end end where the arguments to the function are simply reversed We can then de ne Square as declare Square RCurry Exp 2 Lisp is a programming language that has demonstrated the use of higherorder programming to an extreme a full Lisp interpreter written in Lisp treats Lisp programs simply as data This allows the interpreter program to be an input to itself 32 Numbers in the A Calculus The A calculus is a Turingcomplete language that is any computable function can be expressed in the pure lambda calculus In many of the examples however we have said assume that the calculus has been extended with numbers and conditionals Let us see one possible representation of numbers in the pure lambda calculus 0 Arm 1 ALALI ln ll That is zero is represented as the identity combinator Each succesive number n1 is represented as a lambda abstraction or procedure that takes any value and returns the representation of its predecessor You can think of zero as a rstorder function one as a secondorder function and so on 11 Oz this would be written declare Zero I declare Succ fun N fun X N end end Using this representation the number 2 for example would be the lambdacalculus expression ALALALI or equivalently in Oz Succ Succ Zero 33 Booleans in the A Calculus Now let us see one possible representation of booleans in the pure lambda calculus lt ruel Az ym lfalsel Azyy Abteb t e That is true is represented as a function that takes two arguments and returns the rst while false is represented as a function that takes two arguments and returns the second if is a function that takes 0 a function b representing a boolean value either true or false 0 an argument t representing the then branch and 0 an argument e representing the else branch and returns either t if b represents true or e if b represents false Let us see an example evaluation sequence for if true 4 5 AbiAtiAei b t e AziAyiz 4 5 Amemmw t e 4 5 Aemmw 4 e 5 Amw 4 5 3 M4 5 4 Note that this de nition of booleans works properly in normal evaluation order but has problems in applicative evaluation order The reason is that applicative order evaluates both the then and the else branches which is a problem if used in recursive computations where the evaluation may not terminate or if used to guard improper operations such as division by zero In Oz the following uncurried de nitions can be used to test this representation declare LambdaTrue fun X Y X end declare LambdaFalse fun X Y Y end declare LambdaIf fun B T E B T E end Exercises 7 77reduce the following A calculus expressions if possible a Aziyiz z b Aziyiy I 8 Use nreduction to get from the applicative order Y combinator to the normal order Y combinatori 9 What would be the effect of applying the reverse currying combinator Rcurry to the function composition combinatori declare Compose fun F G fun X F G X Give an example of using the RCurry Compose functioni H 53 1 Give an alternative representation of numbers in the lambda calculus Hint Find out about Church numerals Test your representation using Zr 11 1 Give an alternative representation of booleans in the lambda calculus Hint One possibility is to use Aziz for true and AziAziz for false You need to gure out how to de ne it Test your representation using Oz 12 i For a given function f7 prove that Y Y CSCl4430 6969 Programming Languages Lecture Notes August 28 2003 1 Scheme Basics ln lambda calculus and Scheme the lines are blurred between functions or code and data For example we may rede ne the multiplication operation define mult We may then use it just as you would the times operation gt 2 3 6 gt mult 2 3 6 Let7s de ne the increment function in Scheme define increment lambda x x 1 Note that in Scheme parentheses are critical The command gt increment increment 1 is valid but adding an extra set of parentheses creates an error gt increment increment 1 Error 3 is not a function This is because the Scheme interpreter always expects the rst item after an open parenthesis to be a function In this case however the statement evaluates to 3 then Scheme tries to nd the function 3 and fails Since Scheme can treat functions as data to other functions we can create a function that composes two other functions gt define compose f g x Applying this to the increment function we can create a function that in crements by two gt define inc2 compose increment increment gt inc2 3 5 2 Currying in Scheme Unlike in lambda calculus functions in Scheme are allowed to take more than one variable The process of currying can then be avoided However it is pos sible to use currying in Scheme if you want to Take for example the de nition of a simple addition function that takes two variables gt define plus lambda x y x y This function is used simply by placing the function name and the two arguments into a set of parentheses gt plus 4 2 6 If we instead want to use currying that is limit the number of arguments to one per function we need to create a function that takes the first argument and returns a function which generates the proper answer when provided with the second argument In Scheme this is coded by gt define plusc lambda x lambda y x y This code more closely resembles the lambda calculus statement Aszm y that uses currying To use the Scheme function we must supply the arguments one at a time If we just provide the first argument we obtain a function gt define plus2 plusc 2 This function will produce the correct output when supplied with the other argument that is the function will perform addition by two gt pluSZ 3 5 gt pluSZ 5 7 You may also supply two arguments to the plusc function one at a time to produce output gt plusc 4 2 6 3 Free and Bound Variables in Lambda Calculus The process of simplifying or reducing in lambda calculus requires clari ca tion The general rule is to nd an expression of the form ME M called a redex and replace the free Is in E with Ms A free variable is one that is not bound to a function de nition For example in the expression AziIQ 1 1 the second I is bound to AI because it is part of the expression de ning that function Which is the function 12 The nal I however is not bound to any function de nition so is considered freer Do not be confused by the fact that the variables have the same name They are in different scopes so they are totally independent of each other An equivalent C program could look like this int fint x return xx int main C int x x x 1 return fx In this example the x in f could have been substituted for y or any other variable name Without changing the output of the programi In the same way the lambda expression AziIQ z l is identical to the expression Ay y2 I 17 since the nal I is unbound or free To simplify the expression Aziziz2 1 1 2 You could let E AziIQ 1 1 and M 2 The only free I in E is the nal one so the correct reduction is AziIQ 2 l The I in 12 is bound so it is not replaced To complicate things further it is possible when performing 6 reduction to inadvertently change a free variable into a bound variable which changes the meaning of the expression In the statement AziAylz y y w7 the second y is bound to Ay and the nal y is free Taking E Aylz y and M y w we could mistakenly arrive at the simpli ed expression Ay y w 9 But now both the second and third y s are bound because they are both a part of of the Ay function de nition This is wrong because one of the y7s should remain free as it was in the original expressioni To get around this we can change the Ay expression to a A2 expression AziAzlz 2 y 1117 which again does not change the meaning of the expression This process is called a renamingi Now when we perform the 6 reduction the original two y variables are not confusedi The result is Here the free y remains free 4 Order of Evaluation There are different ways to evaluate lambda expressions The rst method is to always fully evaluate the arguments of a function before evaluating the function itself This order is called applicative orderi In the expression AziIQ ALI 1 2 the argument Aziz l 2 should be simpli ed rst The result is a Am 2 1 a Am 3 a 32 a 9 Another method is to evaluate the leftmost redex rst A redex is an expression of the form AziE M on which 6 reduction can be performed This order is called normal order The same expression would be reduced from the outside in with E 12 and M ALI l 2 In this case the result is a Am 1 22 a 212 a 9 As you can see both orders produced the same result But is this always the case It turns out that the answer is no for certain expressions whose simpli cation does not terminate Consider the expression It is easy to see that reducing this expression gives the same expression back creating an in nite loop If we expand the expression to Ari z Aztz we nd that the two evaluation orders are not equivalent Using applicative order the I Aztz expression must be evaluated rst but this never terminatesi If we use normal order however we evaluate the entire expression rst with E 3 and M I Aztz Since there are no 17s in E to replace the result is simply 3 It turns out that it is only in these particular nonterminating cases that the two orders may give different results The ChurchRosser theorem also called the con uence property or the diamond property states that if a lambda calculus expression can be evaluated in two different ways and both ways terminate both ways will yield the same result Also if there is a way for an expression to terminate using normal order will cause the termination In other words normal order is the best if you want to avoid in nite loopsi Take as another example the C program int loop C return 100130 int fint x int y C return x int main C return f3 100130 In this case using applicative order will cause the program to hang because the second argument 100130 will be evaluated Using normal order will terminate because the unneeded y variable will never be evaluated Though normal order is better in this respect applicative order is the one used by most programming languages Why Consider the function 11 To nd f42 using normal order we hold off on evaluating the argument until after placing the argument in the function so it yields f42 4242 22 4 and the division needs to be done twice If we use applicative order we get f42 f0 22 47 which only requires one division Since applicative order avoids repetitive com putations it is the preferred method of evaluation in most programming lan guages where short execution time is critical 5 Combinators Any lambda calculus expression with no free variables is called a combinatmt Because the meaning of a lambda expression is dependent only on the bindings of its free variables combinators always have the same meaning independently of the context in which they are used There are certain combinators that are very useful in lambda calculus The identity combinator is de ned as I Azizi It simply returns whatever is given to it For example I 5 ALI 5 5 The application combinator is App Afle 1 and allows you to evaluate a function with an argument For example App m2 3 I Aziz2 3 Aziziz2 z 3 ALIQ 3 9 The sequencing combinator in normalorder evaluation is Seq AziAyi if I y This combinator guarantees that x is evaluated before y which is important in programs with sideeffects Assuming we had a display function sending output to the console an example is Seq display hello display world The if function evaluates the second or third argument only after the rst argument has been evaluated Notice that this combinator only works in normal order evaluationi Why CSCl4430 6969 Programming Languages Lecture Notes August 26 2003 The mathematical notation for de ning a function is with a statement such as frr27 frZ7Z7 where Z is the set of all integers The rst Z is called the domain of the function or the set of values I can take The second Z is called the range of the function or the set containing all possible values of Suppose 12 and 91 z 1 Traditional function composition is de ned as f 09 f9IA With our functions f and g fog fgzgtgt 7 fz17122z1 Similarly g o f 7 y 1 7 912 12 1 Therefore function composition is not commutative ln lambda A calculus we can use a different notation to de ne these same concepts To de ne a function 12 we instead write Ara Similarly for 91 z 1 we instead write Aziz 1 To describe a function application such as 4 we write Am 2 a 22 a 4 The syntax for lambda calculus expressions is 7 variable e 2 1 l Ave 7 lambda expression l e e 7 procedure call The semantics of the lambda calculus or the way of evaluating or simplifying expressions is de ned by the rule The new expression can be read as replace freshl 17s in E with M73 lnformally a fresh I is an I that is not nested inside another lambda expres sion We will cover free and bound variable occurrences in detail in upcoming lecturesi For example in the expression AziIQ 2 E 12 and M 2 To evaluate the expression we replace 17s in E with M to obtain Am 2 a 22 a 4 ln lambda calculus all functions may only have one variable Functions with more than one variable may be expressed as a function of one variable through currymgi Suppose we have a function of two variables expressed in the normal way hzy zy h Z X Z A Z With currying we can input one variable at a time into separate functions The rst function will take the rst argument I and return a function that will take the second variable y and will in turn provide the desired output To create the same function with currying let fZgtZgtZ and gIZHZi That is f maps integers to a function and 9 maps integers to integers The function returns a function ya that provides the appropriate result when supplied with y For example f0 927 where 92y 2 y So f23 y23 23 5 ln lambda calculus this function would be described with currying by ALAin y For function application we nest two application expressions AziAylzy 2 3 We may then simplify this expression using the semantic rule also called beta reduction AziAyiz y 2 3 AyiQ y 3 2 3 5 The composition operation a can itself be considered a function also called higherorder function that takes two other functions as its input and returns a function as its output that is if the rst function is Z A Z and the second function is also Z A Z t en oZgtZXZgtZgtZgtZi We can also de ne function composition in lambda calculusi Suppose we want to compose the square function and the increment function de ned as 2 Aziz and Azizli We can de ne function composition as a function itself with currying by AfiAgiAin g Applying two variables to the composition function with currying works the same way as before except now our variables are functions AfiAgiAin g ALIQ Aziz 1 AgiAziziz2 g Aziz 1 Azizi12 Aziz 1 The resulting function gives the same results as I 1 In the Scheme programming language we can use lambda calculus expres sions They are de ned using a similar syntax To de ne a function we use the code 1ambdax y z expr where additional variables y 2 etc are optional Scheme syntax allows you to have functions of more than one variable The co e 1ambdax x x describes the square functioni Note that even common operations are considered functions and are always used in a pre x format You may de ne variables which may themselves be functions with define a b For example define f 1ambdax x x de nes a function 12 To perform a procedure call7 use the code f x y z Where y7 27 etc are additional parameters that f may require The code f 2 evaluates 4i CSC14430 6969 Programming Languages Lecture Notes September 1st 2005 22 Order of Evaluation There are different ways to evaluate lambda expressions The rst method is to always fully evaluate the arguments of a function before evaluating the function itself This order is called applicative order In t e expression AziIQ Aziz 1 2 the argument Aziz l 2 should be simpli ed rst The result is a Am 2 1 a Am 3 a 32 a 9 Another method is to evaluate the leftmost redex rst A redex is an expression of the form ALE M on which 6 reduction can be performed This order is called normal order The same expression would be reduced from the outside in with E 12 and M Aziz l 2 In this case the result is a Azizl 22 a 212 a 9 As you can see both orders produced the same result But is this always the case It turns out that the answer is no for certain expressions whose simpli cation does not terminatei Consider the expression It is easy to see that reducing this expression gives the same expression back creating an in nite loop If we consider the expanded expression Aziy z Aztz we nd that the two evaluation orders are not equivalent Using applicative order the AL I I Am I expression must be evaluated rst but this never terminatesi If we use normal order however we evaluate the entire expression rst with E y and M z Aztz Since there are no 17s in E to replace the result is simply y It turns out that it is only in these particular nonterminating cases that the two orders may give different results The ChurchRosser theorem also called the con uence property or the diamond property states that if a lambda calculus expression can be evaluated in two different ways and both ways terminate both ways will yield the same resu ti Also if there is a way for an expression to terminate using normal order will cause the termination In other words normal order is the best if you want to avoid in nite loopsi Take as another example the C program int loop C return 100130 int fint x int y return x int main return f3 100130 In this case using applicative order will cause the program to hang because the second argument loop will be evaluated Using normal order will terminate because the unneeded y variable will never be evaluated Though normal order is better in this respect applicative order is the one used by most programming languages Why Consider the function z I To nd f42 using normal order we hold off on evaluating the argument until after placing the argument in the function so it yie ds f42 4242 22 4 and the division needs to be done twice If we use applicative order we get f42 f2 2247 which only requires one division Since applicative order avoids repetitive computations it is the preferred method of evaluation in most programming languages where short execution time is critica 23 Combinators Any lambda calculus expression with no free variables is called a combinator Because the meaning of a lambda expression is dependent only on the bindings of its free variables combinators always have the same meaning independently of the context in which they are used There are certain combinators that are very useful in lambda calculus The identity combinator is de ned as I Azizi It simply returns whatever is given to it For example I 5 Arm 5 5 The identity combinator in Oz can be written declare I fun X X end Contrast it to for example a Circumference function declare Circumference fun Radius 2PIRadius end The semantics of the Circumference function depends on the de nitions of PI and i It is therefore not a combinatori The application combinator is App Afle 1 and allows you to evaluate a function with an argument For example App m2 3 z Aziz2 3 AziOxzizQ z 3 ALIQ 3 9 The sequencing combinator is Seq AziAlexziy z where 2 is chosen so that it does not appear free in y This combinator guarantees that X is evaluated before y which is important in programs with side effects Assuming we had a display function sending output to the console an example is 564 display hello display world 231 Currying Combinator The curryng combinator takes a function and returns a curried version of the function For example it would take as input the Plus function which has the type Plus Z X Z A Z The type of a function defines what kinds of things the function can receive and what kinds of things it produces as output In this case Plus takes two integers Z X Z and returns an integer The definition of Plus in Oz is declare Plus fun X Y XY end The currying combinator would then return the curried version of Plus called PlusC which has the type PlusC Z A Z A Z Here PlusC takes one integer as input and returns a function from the integers to the integers Z A Z The definition of PlusC in Oz is declare PlusC fun X fun Y XY end end The Oz version of the currying combinator which we will call Curry would work as follows Curry Plus PlusCi Using the input and output types above the type of the Curry function is CurryZgtltZgtZgtZgtZgtZi So the Curry function should take as input an uncurried function and return a curried function In Oz we can write Curry as follows declare Curry fun F fun X fun Y F X Y end end end This may seem very much like the de nition of the PlusC functioni But is the PlusC function a combinator No7 because the function is a free variablei Remember that the de nition of a combinator is that it has no free variables In Oz7 the operator is considered a procedure that is de ned in the Number module can be accessed as Number i This operator has a speci c behavior7 making this code speci c7 not universal So it is crucial in the de nition of the currying combinator that the function be changed to a generic function F7 Which can be set to any function you like The Curry function has no free variables7 and therefore is a combinatori Exercises 3 Write a function composition combinator in the A calculusi 4 De ne a curried version of Compose in Oz7 ComposeC7 Without using the Curry combinatori Hint It should look very similar to the A calculus expression from the previous exerciser CSC14430 6969 Programming Languages Lecture Notes August 31st 2006 22 Order of Evaluation There are different ways to evaluate lambda expressions The rst method is to always fully evaluate the arguments of a function before evaluating the function itself This order is called applicative order In the expression AziIQ Aziz 1 2 the argument Aziz l 2 should be simpli ed rst The result is a Am 2 1 a Am 3 a 32 a 9 Another method is to evaluate the leftmost redex rst A redex is an expression of the form ALE M on which 6 reduction can be performed This order is called normal order The same expression would be reduced from the outside in with E 12 and M Aziz l 2 In this case the result is a Azizl 22 a 212 a 9 As you can see both orders produced the same result But is this always the case It turns out that the answer is no for certain expressions whose simpli cation does not terminatei Consider the expression It is easy to see that reducing this expression gives the same expression back creating an in nite loop If we consider the expanded expression Aziy z Aztz we nd that the two evaluation orders are not equivalent Using applicative order the AL I I Am I expression must be evaluated rst but this never terminatesi If we use normal order however we evaluate the entire expression rst with E y and M z Aztz Since there are no 17s in E to replace the result is simply y It turns out that it is only in these particular nonterminating cases that the two orders may give different results The ChurchRosser theorem also called the con uence property or the diamond property states that if a lambda calculus expression can be evaluated in two different ways and both ways terminate both ways will yield the same resu ti Also if there is a way for an expression to terminate using normal order will cause the termination In other words normal order is the best if you want to avoid in nite loopsi Take as another example the C program int loop C return 100130 int fint x int y return x int main return f3 100130 In this case using applicative order will cause the program to hang because the second argument loop will be evaluated Using normal order will terminate because the unneeded y variable will never be evaluated Though normal order is better in this respect applicative order is the one used by most programming languages Why Consider the function z I To nd f42 using normal order we hold off on evaluating the argument until after placing the argument in the function so it yie ds f42 4242 22 4 and the division needs to be done twice If we use applicative order we get f42 f2 2247 which only requires one division Since applicative order avoids repetitive computations it is the preferred method of evaluation in most programming languages where short execution time is critica 23 Combinators Any lambda calculus expression with no free variables is called a combinator Because the meaning of a lambda expression is dependent only on the bindings of its free variables combinators always have the same meaning independently of the context in which they are used There are certain combinators that are very useful in lambda calculus The identity combinator is de ned as I Azizi It simply returns whatever is given to it For example I 5 Arm 5 5 The identity combinator in Oz can be written declare I fun X X end Contrast it to for example a Circumference function declare Circumference fun Radius 2PIRadius end The semantics of the Circumference function depends on the de nitions of PI and i It is therefore not a combinatori The application combinator is App Afle 1 and allows you to evaluate a function with an argument For example App m2 3 z Aziz2 3 AziOxzizQ z 3 ALIQ 3 9 The sequencing combinator is Seq AziAyiOxziy z where 2 is chosen so that it does not appear free in y This combinator guarantees that X is evaluated before y which is important in programs with side effects Assuming we had a display function sending output to the console an example is 564 display hello display world 24 Currying The curryng higherorder function takes a function and returns a curried version of the function For example it would take as input the Plus function which has the type Plus Zgtlt Z AZ The type of a function defines what kinds of things the function can receive and what kinds of things it produces as output In this case Plus takes two integers Z X Z and returns an integer The definition of Plus in Oz is declare Plus fun X Y XY end The currying combinator would then return the curried version of Plus called PlusC which has the type PlusC Z A Z A Z Here PlusC takes one integer as input and returns a function from the integers to the integers Z A Z The definition of PlusC in Oz is declare PlusC The Oz version of the currying combinator which we will call Curry would work as follows Curry Plus PlusCi Using the input and output types above the type of the Curry function is CurryZgtltZgtZgtZgtZgtZi So the Curry function should take as input an uncurried function and return a curried function In Oz we can write Curry as follows declare Curry fun F fun X fun Y F X Y end end end Exercises 3 Write a function composition combinator in the A calculusi 4 De ne a curried version of Compose in Oz7 ComposeC7 Without using the Curry combinatori Hint It should look very similar to the A calculus expression from the previous exercise 5 1 Install MozartOz in your computer 6 1 De ne functions Plus7 PlusC its curried version7 and test therni CSCl4430 6969 Programming Languages Lecture Notes January 27 2005 1 HigherOrder Programming Most imperative programming languages eigi Java and C do not allow us to treat functions or procedures as rstclass entities for example we cannot create and return a new function that did not exist before A function that can only deal with data values is called a rstorder function For example Increment whose type is Z A Z can only take integer values and return integer values Programming only with rstorder functions is called rstorder programming If a function can take another function as an argument or if it returns a function it is called a higher order function For example the Curry combinator whose type is CurryZgtltZgtZgtZgtZgtZi is a higherorder function It takes a function of type Z X Z A Z and returns a function of type Z A Z A Z That is Curry takes a rstorder function and returns a secondorder function The ability to view functions as data is called higherorder programming Higherorder programming is a very powerful technique as shown in the following Oz examplei Consider an exponential function Exp as follows declare Exp fun B N if O then 1 else B Exp B Nl end end And recall the Curry combinator in Oz declare Curry fun F fun X fun Y F X Y end end end We can create a function to compute the powers of 2 Ton by just using declare Ton Curry Exp 2 If we want to create a Square function using Exp we can create a reverse curry combinator RCurry declare RCurry fun F fun X fun Y F Y X end end end where the arguments to the function are simply reversed We can then de ne Square as declare Square RCurry Exp 2 Lisp is a programming language that has demonstrated the use of higherorder programming to an extreme a full Lisp interpreter written in Lisp treats Lisp programs simply as data This allows the interpreter program to be an input to itself 2 Numbers in the ACalculus The A calculus is a Turingcomplete language that is any computable function can be expressed in the pure lambda calculus In many of the examples however we have said assume that the calculus has been extended with numbers and conditionals Let us see one possible representation of numbers in the pure lambda calculus 0 ALI 1 ALALI n 1 That is zero is represented as the identity combinator Each succesive number n1 is represented as a lambda abstraction or procedure that takes any value and returns the representation of its predecessor ln Oz this would be written declare Zero I declare Succ fun N fun X N end end Using this representation the number 2 for example would be the lambdacalculus expression ALALALI or equivalently in z Succ Succ Zero 3 Booleans in the ACalculus Now let us see one possible representation of booleans in the pure lambda calculus lt ruel AziAyiz lfalsel AziAyiy AbiAtiAeib t e That is true is represented as a function that takes two arguments and returns the rst while false is represented as a function that takes two arguments and returns the second if is a function that takes 0 a function b representing a boolean value either true or false 0 an argument t representing the then branch and 0 an argument e representing the else branch and returns either t if b represents true or e if b represents falsei et us see an example evaluation sequence for if true 4 5 AbiAtAeib t e AziAyiz 4 5 At Aemx Ay x t e 4 5 Aerwayi 4 e 5 mam 4 5 3 M4 5 4 Note that this de nition of booleans works properly in normal evaluation order but has problems in applicative evaluation order The reason is that applicative order evaluates both the then and the else branches which is a problem if used in recursive computations where the evaluation may not terminate or if used to guard improper operations such as division by zero In Oz the following uncurried de nitions can be used to test this representation declare LambdaTrue fun X Y X end declare LambdaFalse fun X Y Y end declare LambdaIf fun B T E B T E end Exercises 1 to 9 What would be the effect of applying the reverse currying combinator7 Rcurry7 to the function composition combinatori declare Compose fun F G fun X F G X end end Give an example of using the RCurry Compose function i Give an alternative representation of numbers in the lambda calculus Hint Find out about Church numerals Test your representation using Ozi Give an alternative representation of booleans in the lambda calculus Hint One possibility is to use Aziz for true and AziAziz for false You need to gure out how to de ne it Test your representation using Ozi CSCl4430 6969 Programming Languages Lecture Notes January 24 2005 1 n Conversion Consider the expression Aziziz2 I 3 Using reduction we can take E ALIQ z and M 3 In the reduction we only replace the one I that is free in E to get 3 ALIQ 3 We use the symbol 3 to show that we are performing reduction on the expression As another example we may write A112 3 Ayiy2 since arenaming is taking place Another type of operation possible on lambda calculus expressions is called nconversion eta77reduction when applied from left to right We perform nreduction using the rule AziE I l E nreduction can only be applied if E is a lambda expression taking a single argument and I does not appear free in E Starting with the same expression as before Aziziz2 I 3 we can perform nreduction to obtain ALszizQ z 3 l Aziz2 3 which gives the same result as reductioni In the following example there is no redex but we can perform nreductioni Aziy I l y nreduction can be considered a program optimization For example consider the following Oz de ni tions declare Increment fun X X1 end declare Inc fun X Increment X end Using nreduction we could reduce Inc 6 to Increment 6 avoiding one extrafunction call This compiler optimization is also called inlz39m39ngi nconversion can also affect termination of expressions in applicative order expression evaluation For example the Y reduction combinator has a terminating applicative order form that can be derived from the normal order combinator form by using nconversion see Section 22 2 Combinators Any lambda calculus expression with no free variables is called a combinatmt Because the meaning of a lambda expression is dependent only on the bindings of its free variables combinators always have the same meaning independently of the context in which they are used There are certain combinators that are very useful in lambda calculus The identity combinator is de ned as I Azizi It simply returns whatever is given to it For example I 5 Arm 5 5 The identity combinator in Oz can be written declare I fun X X end Contrast it to for example a Circumference function declare Circumference fun Radius 2PIRadius end The semantics of the Circumference function depends on the de nitions of PI and i It is therefore not a combinatori The application combinator is App 0le I and allows you to evaluate a function with an argument For example App m2 3 z Aziz2 3 Aziziz2 z 3 ALIQ 3 9 The sequencing combinator is Seq AziAyiOxziy z where 2 is chosen so that it does not appear free in y This combinator guarantees that x is evaluated before y which is important in programs with side effects Assuming we had a display function sending output to the console an example is Seq display hello display world 21 Currying Combinator The currying combinator takes a function and returns a curried version of the function For example it would take as input the Plus function which has the type Plus ZX Z AZ The type of a function de nes what kinds of things the function can receive and what kinds of things it produces as output In this case Plus takes two integers Z X Z and returns an integer The de nition of Plus in Oz is declare Plus fun X Y XY end The currying combinator would then return the curried version of Plus called PlusC which has the type PlusC Z A Z A Z Here PlusC takes one integer as input and returns a function from the integers to the integers Z A Z The de nition of PlusC in Oz is declare PlusC fun X fun Y XY end end The Oz version of the currying combinator which we will call Curry would work as follows Curry Plus PlusCl Using the input and output types above the type of the Curry function is CurryZgtltZgtZgtZgtZgtZl So the Curry function should take as input an uncurried function and return a curried function In Oz we can write Curry as follows declare Curry fun F fun X fun Y F X Y end end end This may seem very much like the de nition of the PlusC functionl But is the PlusC function a combinator No because the function is a free variable Remember that the de nition of a combinator is that it has no free variables In Oz the operator is considered a procedure that is de ned in the Number module and can be accessed as Number l This operator has a speci c behavior making this code speci c not universal So it is crucial in the de nition of the currying combinator that the function be changed to a generic function F which can be set to any function you like The Curry function has no free variables and therefore is a combinatorl 2 2 Recursion Combinat or The recursion combinator allows recursion in lambda expressionsl For example suppose we want to implement a recursive version of the factorial operation l ifn0 ni nnill ifngt0 We could start by attempting to write a the recursive function f in the lambda calculus assuming it has been extended with conditionals and numbers f AgAnif n 0 1 n 9 n 1 This function does not work yet because it does not receive a single argumenti Before we can input an integer to the function we must input a function to satisfy 9 so that the returning function is the desired factoriali Letls call this function Xi Looking within the function we see that the function X must take an integer and return an integer that is its type is Z A Z The function f will return the proper recursive function with the type Z A Z but only when supplied with the correct function Xi Knowing the input and output types of f we can write the type of as fZgtZgtZgtZi What we need is a function X that when applied to f returns the correct recursive function We could try applying f to itself ie f f A This does not work because f expects something of type Z A Z but it is taking another f which has the more complex type Z A Z A Z A Z A function that has the correct input type is the identity combinator Azizi Applying the identity function we get f I Aniif n 0 l n I n 1 Aniif n 0 l n n 1D which is equivalent to l ifn 0 7 7M nil ifngt0 We need to nd the correct expression X such that when X is applied to f we get the recursive factorial function It turns out that the X that works is X Aziginiif n 0 l n g 7 n I Aziginiif n 0 l n g 7 n I Note that this has a structure similar to the nonterminating expression Aziz I Aziz 1 and explains why the recursive function can keep going X can be de ned as Y where Y is the recursion combinator f X v f Y 165 f The recursion combinator that works for an applicative evaluation order is de ned as Y Af MU MW 1 9 MU M W 1 y The same combinator that is valid for normal order is Y z Aw I as How do we get from normal ordering to applicative order Use 77expansion that is nconversion in reverse This is an example where 77conversion can have an impact on the termination of an expression Exercises 1 nreduce the following A Calculus expressions7 if possible a Azryrz z b Azryry I 2 Use nreduction to get from the applicative order Y combinator to the normal order Y combinator 3 Prove that Y Y

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.