University of Arizona, Department of Computer ScienceCSc 520 — Assignment 2 — Due noon, Wed Feb 16 — 10%Christian CollbergFebruary 7, 20051 IntroductionThe purpose of this assignment is to become familiar with Lambda Calculus and Haskell programming.Every function should be commented. At the very least, the comments should state what the function does,which arguments it takes, and what result it produces.This assignment is graded out of 100. It is worth 10% of your final grade.2 Lambda Calculus [20 points]Solve problems 1,2, and 3 on page 146–147 in Syntax and Semantics of Programming Languages, by KenSlonneger and Barry Kurtz.For problem 2 show the steps in which the substitutions are carried out, as shown in page 146 in Slonnegerand Kurtz.Hand in your results in as a text file called theory. Use “L” to signify the lambda operator.3 Set operations [30 points]In the next section we will need operations on sets. So, start by giving Haskell definitions for member, union,and delete.1. Implement the operation member x l, where x is an arbitrary type and l a list of this type:[10 points]member :: (Eq a) => a -> [a] -> Boolmember x l = ...The “(Eq a) =>” part of the signature just means that member can only work on types for whichequality is defined.Don’t use recursion for this function! (Hint: use some combination of or and map.)1Examples:> member 1 []False> member 2 [1,2,3]True> member "hoi" ["hi","hoi","hej"]True2. Define a function union a b that implements set union: [10 points]union :: (Eq a) => [a] -> [a] -> [a]union a b = ...Examples:> union [] [][]> union [1] [1][1]> union [1] [1,2][1,2]> union [1,3] [1,2][3,1,2]For this and other functions in this assignment you will find it convenient to use the following syntax:fun :: ....fun arg1 arg2 ... argM| condition1 = expr1| condition2 = expr2...| conditionN = exprN| otherwise = exprOHere, each condition is evaluated until one evaluates to True, after which the corresponding expressionis evaluated and its value returned.3. Define a function delete a b that removes all occurences of b from the list a: [10 points]delete :: Eq a => [a] -> a -> [a]delete l x = ...Examples:> delete [1,2,3,3,2] 4[1,2,3,3,2]> delete [1,2,3,3,2] 1[2,3,3,2]> delete [1,2,3,3,2] 3[1,2,2]> delete [1,2,3,3,2] 2[1,3,3]2You should download lambda.hs from the class home page: http://www.cs.arizona.edu/~collberg/Teaching/520/2005/Assignments/lambda/hs. To run your program on lectura, do:> /usr/local/hugs98/bin/hugs> :load lambda.hs> showLExpr e1"5"4 Lambda Expressions in HaskellIn the remainder of this assignment we are going to manipulate lambda expressions. These are defined inHaskell like this:data LExpr = Const Int |Var String |Comb LExpr LExpr |Abstr String LExprshowLExpr :: LExpr -> StringshowLExpr (Const n) = show nshowLExpr (Var v) = vshowLExpr (Comb e1 e2) = "(" ++ (showLExpr e1) ++ " " ++ (showLExpr e2) ++ ")"showLExpr (Abstr v e) = "(lambda " ++ v ++ " . " ++ (showLExpr e) ++ ")"Note the similarity between this definition of a Lambda expression and the one given on page 141 of Slonnegerand Kurtz.Using this definition we can define some lambda expressions:e1 = (Const 5)e2 = (Var "v")e3 = (Comb (Const 5) (Var "v"))e4 = (Abstr "v" (Var "v"))e5 = (Abstr "v" (Comb (Var "v") (Var "v")))e6 = (Abstr "y"(Comb(Abstr "f" (Comb (Var "f") (Var "x")))(Var "y")))and print them out:> showLExpr e1"5"> showLExpr e33"(5 v)"> showLExpr e4"(lambda v . v)"> showLExpr e5"(lambda v . (v v))"> showLExpr e6"(lambda y . ((lambda f . (f x)) y))"5 Free Variables [20 points]Implement the function fv efv :: LExpr -> [String]that returns the set of free variables in a lambda expression. The result should be a list of strings. Thealgorithm is given on page 145 of Slonneger and Kurtz:• The free variables of an expression E, FV(E) is computed as1. FV(c) = ∅ for any constant c.2. FV(x) = {x} for any variable x.3. FV((E1E2)) = FV(E1) ∪ FV(E2).4. FV((λx.E)) = FV(E) − {x}.Examples:> fv e6["x"]> fv e1[]> fv e2["v"]6 Substitutions [30 points]Implement the function subst E v E1that performs the substitution E[v → E1]. The result should be anew lambda expression. The algorithm is given on page 146 of Slonneger and Kurtz:a) v[v → E1] = E1for any variable vb) x[v → E1] = x for any variable x 6= vc) c[v → E1] = c for any constant cd) (E1E2)[v → E3] = (E1[v → E3] E2[v → E3])4e) (λv.E)[v → E1] = (λv.E)f) (λx.E)[v → E1] = (λx.E[v → E1]), when x 6= v and x 6∈ FV(E1)g) (λx.E)[v → E1] = (λz.E[x → z][v → E1]), when x 6= v and x ∈ FV(E1) where z 6= v and z 6∈FV((E E1))Here’s the beginning of the subst-function and a function testSubst that can be used to test subst:-- The expression-- subst e v e1-- performs the substitution-- e[v->e1]-- where e and e1 are lambda exressions-- and v is a (string) variable.subst :: LExpr -> String -> LExpr -> LExprsubst (Const x) _ _ = (Const x).....testSubst :: LExpr -> String -> LExpr -> StringtestSubst e v e1 = (showLExpr e) ++ "[" ++ v ++ "->" ++(showLExpr e1) ++ "] ==> " ++(showLExpr (subst e v e1))This is the example worked on page 146 of Slonneger and Kurtz:> testSubst e6 "x" (Comb (Var "f") (Var "y"))"(lambda y . ((lambda f . (f x)) y))[x->(f y)] ==> (lambda x1 . ((lambda x1 . (x1 (f y))) x1))"Note that the result is different from what’s in the book, due to how new fresh variables are chosen in theg)-part of the algorithm.As part of your implementation you may want to define a functionfresh :: [String] -> Stringwhich, given a set of variables returns a new (“fresh”) variable not in the set.7 Submission and AssessmentThe deadline for this assignment is noon, Wed Feb 16. You should submit the assignment (a text-file contain-ing the function definitions) electronically using the Unix command pturnin cs520.2 theory lambda.hsq.This assignment is worth 10% of your final grade.Don’t show your code to anyone, don’t read anyone else’s code, don’t discuss the details ofyour code with anyone. If you need help with the assignment see the instructor or
View Full Document
Unlocking...