F# programing
Expand the accompanying archive project.zip and put the extracted folder project on your desktop. The folder contains a few files that you will need. Write your solutions as instructed below. Then compress project to a zip archive called projectsol.zip and submit the archive. Make sure you submit the new zip file with your solution, not the original one! The submission policy for the code and the evaluations is the same as with team homework assignments. In particular, only one person per team should submit the code. Note: Your files must compile with no syntax/type errors. You may receive serious penalties for code that does not compile correctly. 1 The PLC Language In this project you will develop in F# an interpreter and related code for an extension of a variation of the PLC language introduced in Hw6. We will also refer to this new language as the PLC language. The language incorporates several of the programming concepts studied during the course. It is purely functional, strict, statically-typed, lexically-scoped, and higher-order. With respect to the version from Hw6, this version of PLC has more features, including a sequence type and related primitive functions. The sequence type of PLC is very similar to the list type of F#, with values consisting of an ordered, immutable series of elements of the same type. Other features include anonymous functions, simple pattern matching, and a print command. Also, the concrete and abstract syntax for PLC types and expressions is slightly different, but mostly very similar to that of micro-ML. Main limitations with respect to real world functional languages, introduced for simplicity, are that there are no commands to read input from the console or files; functions are monomorphic and can be recursive but not mutually recursive; formal parameters of functions must be explicitly typed; recursive functions must declare their return type; and pattern matching is restricted to 1 fun inc (Int x) = x + 1; fun add (Int x, Int y) = x + y; fun cadd (Int x) = fn (Int y) => x + y end; var y = add(3, inc(4)); var x = cadd(3)(7-y); var z = x * 3; fun rec fac (Int n) : Int = match n with | 0 -> 1 | 1 -> 1 | _ -> n * fac(n - 1) end ; print x; print y; x :: y :: z :: fac(z) :: ([Int] []) Figure 1: A PLC program. value comparison, i.e. it amounts to syntax sugar for a series of if-then-else statements. Finally, important basic types such as characters and strings or structured types such as algebraic datatypes and records are missing. Figure 1 contains an example of a PLC program. The program defines a non-recursive first- order function inc of type Int -> Int; a non-recursive first-order function add of type (Int,Int) -> Int; a non-recursive higher-order function highAdd; variables x, y and z; and a recursive first- order function fact. The scope of each of these functions and variables includes the declarations and expressions that follow. In the example, the expressions after the declaration of fact are also separated by semicolons. When used with expressions, semicolon is, as in F#, a right-associative binary operator such that e1 ; e2 evaluates to the value of e2 for all expressions e1 and e2. In the example program, the first expression prints to the console the value of x and y and then returns the list consisting of the values of x, y, z , fact(z) and y. Function highAdd takes an integer x and returns the anonymous function fn (Int y) => x + y end, which in turn takes an integer y and returns the value of x + y. Function fact is the usual factorial function whose input and output values are explicitly declared to be of type Int. In this version of PLC, function declarations must include the output type only if the function is recursive. Declarations of such functions need the rec qualifier after the fun keyword. Since PLC has anonymous functions, declarations of non-recursive functions are in fact syntactic sugar. That is, a program of the form fun f(t x) = e ; e1 is treated as the program var f = fn (t x) => e end ; e1 where f becomes a variable of higher-order type t -> te (with te being the type of e) whose value is the anonymous function fn (t x) => e end. The only true function declarations are those of recursive functions then. 2 var E = ([Int] []); fun reverse ([Int] s) = { fun rec rev ([Int] s1, [Int] s2): [Int] = match s1 with | E -> s2 | _ -> { var h = hd(s1); var t = tl(s1); rev(t, h::s2) } end ; rev(s, E) }; reverse (1::2::3::E) Figure 2: A PLC program with locally defined functions. One restriction on the use of ; is that (variable or function) declarations cannot follow expres- sions unless they are included in a brace-delimited block. For example; 1 - 3; var x = 4; 2 * x is not allowed whereas 1 - 3; {var x = 4; 2 * x} is. In any case, the last argument of ; must be an expression, it cannot be a declaration. Sequences of declarations and expressions enclosed in braces are treated as atomic expressions, which means that they can go anywhere an expression can go. This allows one for instance to declare local variables and functions within another function, as in the program in Figure 3. 2 Types, type annotations and static typing Sequences in PLC are essentially the same as lists in F#, with [] denoting the empty sequence constant and :: denoting the sequence constructor. Note, however, that the empty sequence must be explicitly typed anywhere it occurs, as shown in the programs of Figures 1– 3. The reason is that this makes type checking considerably easier to implement. It is the same reason formal parameters of functions must be explicitly typed and recursive functions must declare their return type. The latter simplifies the type checking of the function’s body, which includes occurrences of the function name (in recursive calls). Since the language is higher-order, we can define and use in it the usual combinators, with the only restriction that they cannot be polymorphic.1 Examples of such functions are provided in Figure 2. The function map is the usual one except that it is restricted to integers sequences as input and as output, and has a more verbose declaration than in F#. 1 This is truly limiting, because now one needs for instance to define a map function for each possible concrete instance, such as (Int -> Int) -> [Int] -> [Int], of the parametric type (’a -> ’b) -> [’a] -> [’a] that map could have if polymorphism was allowed as in F#. This restriction too is to simplify type checking. 3 fun twice (Int -> Int f) = fn (Int x) => f(f(x)) end ; fun rec map (Int -> Int f) : ([Int] -> [Int]) = fn ([Int] s) => if ise(s) then s else f(hd(s)) :: map(f)(tl(s)) end ; fun square (Int x) = x * x ; fun inc (Int x) = x + 1 ; var E = ([Int] []) ; var s1 = map (fn (Int x) => 2*x end) (10::20::30::E) ; var s2 = map (twice(inc)) (s1) ; (s1, s2) Figure 3: A PLC program with higher-order combinators. 2.1 Types and operators The language has the following types and operations on them. Your interpreter should support all of them. Nil type The type Nil, similar to unit in F#, contains a single value. Predefined operators dealing with Nil values are: () : Nil, the only value of this type, and print : t -> Nil, for any type t. The latter function always returns () but has the side effect of printing to the console (standard output) a textual representation of its input value. Boolean type The type Bool is the usual Boolean type. In addition to the constants true and false, it has the predefined operators && : (Bool, Bool) -> Bool for Boolean conjunction and ! : Bool -> Bool for Boolean negation. Two more operators are = and !=, both of type (t, t) -> Bool for any equality type t (see below), respectively for equality and disequality comparison. Integer type The type Int is the usual integer type whose constants are all the numerals. It has the usual infix binary operators +, -, *, /, <, and=""><= with="" the="" expected="" meaning.="" the="" first="" four="" have="" type="" (int,int)="" -=""> Int. The last two have type (Int, Int) -> Bool. The - operator is also unary, with type Int -> Int. List types For any PLC types t1, . . . , tn with n > 1 it is possible to construct lists of type (t1, ..., tn). The list constructor is the multi-arity mixfix operator ( , ..., ). For all n > 0, i ∈ {1, . . . , n} and types t1, . . . , tn, there is also a postfix element selector [i] : (t1, ..., tn) -> ti that returns the ith element of its input list. Function types Functions that take an input of type t1 and produce an output of type t2 have type t1 -> t2. The arrow operator -> is right-associative. Sequence types For any PLC type t it is possible to construct sequences of type [t]. Note that this means that it is possible to construct sequences of sequences, sequences of lists, and so on. The predefined, and polymorphic, operators dealing with sequence values are listed below. • [] : [t], for any type t. The empty sequence of elements of type t. 4 • :: : (t, [t]) -> [t], for any type t. The infix, right-associative sequence construction operator. • ise : [t] -> Bool, for any type t. Returns true if the input sequence is empty and false otherwise. • hd : [t] -> t, for any type t. Returns the head of the input sequence if the input is not empty, and raises an exception otherwise. • tl : [t] -> [t], for any type t. Returns the tail of the input sequence if the input is not empty, and raises an exception otherwise. Equality types These are the types with no occurrences of -> in them. They are defined induc- tively as follows: (i) Bool, Int, and Nil are equality types; (ii) if t is an equality type, so is [t]; (iii) if t1,