F# programmingThis is a programming assignment in F#. You can do it alone or in a team two people....

Question

F# programmingThis is a programming assignment in F#. You can do it alone or in a team two people. In the  latter case, you are responsible for contacting other students and form a team. Pay close attention to the specification of each problem and the restrictions imposed on its solution.  Solutions ignoring the restrictions may receive only partial credit or no credit at all. Do not worry about the efficiency of your solution. Strive instead for cleanness and simplicity.  Unnecessarily complicated code may not receive full credit. The grade for the assignment will be given on an individual basis. For team submissions, both  students must also submit an evaluation on how well they and their teammate performed as team  members. Each evaluation is confidential and will be incorporated in the calculation of the grade.  Submission instructions will be provided separately on Piazza. Do the assigned readings before starting attempting this assignment. If you do not, you might find the  assignment exceedingly hard. In this assignment you should still write functional code with no mutable variables or data structures  but you are allowed to use any functions in F#’s List module. Note: Your files must load in F# Interactive with no syntax/type errors. You may receive a zero for  any problem whose code does not load correctly. The PLC language In this assignment we will develop an extension to a variant of the Micro-ML language seen in class.  We will refer to this new language as PLC. The main point of this assignment is to realize that the  core of Micro-ML is powerful enough that we can add many syntactic features, including a rather  different concrete syntax, while maintaining essentially the same abstract syntax and semantics of  Micro-ML. 1 Syntax and Semantics PLC is a statically-typed first order language with integer, Boolean, and list types. A PLC program is a semicolon-separated sequence of function and variable definitions terminated by an expression whose value is the value of the whole program. The syntax of definitions is similar to that in Hw5 except that explicit nesting of blocks is not required anymore and that we use curly braces as delimiters. Concretely, one can write something like (* Listing 1 *) var a = 5; var b = a + 1; fun addB(Int x): Int = x + b; addB(3) as an abbreviation of (* Listing 2 *) { var a = 5; { var b = a + 1; { fun addB(Int x): Int = x + b; addB(3) }}} with both converted internally to the following Micro-ML-like abstract syntax, which is interpreted as in Micro-ML. Let ("a", CstI 5, Let ("b", Prim2 ("+", Var "a", CstI 1), Letfun ("addB", "x", IntT, Prim2 ("+", Var "x", Var "b"), IntT, Call (Var "f", CstI 3)))) The flat and the nested syntax can be mixed together, as for instance in (* Listing 3 *) var a = 5; { var b = a + 1; fun addB(Int x): Int = x + b; addB(3) } which has the same meaning as Listing 1 and 2 above. This means in particular that one can for instance define functions with local variables and local functions as follows (* Listing 4 *) fun f(Int x): Int = { var xx = x * x; fun g(Int y): Int = y + y; g(xx) }; f(10) 2 Type System As with the statically-typed version of Micro-ML, PLC function definitions need to specify the type of their input and their output. A notable new feature is that functions can have zero or more arguments: (* Listing 5 *) fun f0(): Int = 5 ; fun f1(Int x): Bool = 0  1 inputs x1, . . . , xn of respective type t1, . . . , tn are treated as unary functions taking as input a list of type (t1, . . ., tn). The input variables x1, . . . , xn are then introduced as local variables initialized to the corresponding value in the input list. Unary functions, including those originally defined as such, such as f1 in Listing 5, are treated as in Micro-ML. The type system of PLC consists of two simple types, Int and Bool, and all (possibly nested) list types built out of them, with type Nil being the nullary list type. Values of list types are built using parentheses and commas to separate the list components. Note that this is different of how lists are build in F#, using brackets and semicolons. List com- ponents are extracted via expressions e[i], in which e is any expression of list type and i is any numeral such that 1 ≤ i ≤ n where n is the number of e’s elements. Since the abstract syntax of PLC is essentially the same as that of Micro-ML, except for the addition of a constructor for forming lists and one for accessing an item, the type system is essentially the same as the one presented in Chapter 4 of the textbook. To the type rules of Micro-ML we need to add the rules in Figure 1, for list types. A partial implementation of PLC in F# is provided hw6.zip. This includes files for FSLex lexer and FSYacc parser specifications, for type checking, and for program interpretation. File main.fsx contains examples of PLC programs and instructions on how to run then. As in Hw5, command fromString takes a string containing a PLC program, parses it and converts it to abstract syntax when the program is syntactically correct. The command run takes an abstract syntax term, type checks it and, it type-checking is successful, evaluates it and prints its result in the standard output. In this assignment you will complete several aspects of the implementation. 3 ρ ` () : Nil ρ ` e1 : t1 · · · ρ ` en : tn ρ ` (e1, . . . , en) : (t1, . . . , tn) ρ ` e : (t1, . . . , tn) 1 ≤ i ≤ n ρ ` e[i] : ti Figure 1: Typing rules for lists in PLC. ρ is an arbitrary type environment. 1 Parsing A FSYacc parser for PLC is specified in file PlcParser.fsy. The parser uses the abstract syntax defined in file Absyn.fs and the function makeFun defined in file PlcParserAux.fs. 1. The provided parser parses most of the syntax of PLC except that it accepts only nullary function definitions, those with argument (). Extend the definition of the production rule Args to allow also an n-ary argument syntax of the form (t1 x1, . . ., tn xn) for n > 0. Args should return a (possibly empty) list of type/variable pairs. Introduce auxiliary production rules as needed. 2. Function makeFun is used in the production rule for function definitions: LetExpr: Expr { $1 } | VAR NAME EQ Expr SEMIC LetExpr { Let ($2, $4, $6) } | FUN NAME Args RetType EQ Expr SEMIC LetExpr { makeFun $2 $3 $4 $6 $8 } ; makeFun takes as input, in order, the name f of the function, the input parameter list [(t1, x1); ...; (tn, xn)] produced by rule Args, the return type t of f produced by rule RetType, the function body e1, and the expression e2 in which f is used. If the parameter list contains just one argument (i.e., n = 1), makeFun returns the abstract syntax term Letfun (f, x1, t1, e1, t, e2) as in the parser for Micro-ML. If the parameter list is empty, it returns the abstract syntax term Letfun (f, x, ListT [], e1, t, e2) which corresponds to the concrete syntax dec- laration fun f(Nil x): t = e1; e2. If the parameter list has two elements, makeFun returns the abstract syntax term Letfun (f, x, t, e′1, t, e2) with t= ListT [t1; t2] and e ′ 1 = Let(x1, Item(1, x), Let(x2, Item(2, x), e1)), which corresponds to the concrete syntax declaration fun f((t1, t2) x): t = {var x1 = x[1]; var x2 = x[2]; e1}; e2. The behavior for n > 2 is similar but with more nested Let constructors. In all cases, x above is the string "$list". The choice of that name for f ’s input variable is arbitrary but it starts with $ to make sure that it does not coincide with any variables in the PLC program. When n > 1, makeFun uses the auxiliary functions makeType and makeFunAux which respec- tively produce t and e′1 above. Those two functions currently have a dummy (and incorrect) implementation. Replace it with the expected implementation for each of them. 4 2 Type Checking The abstract syntax for PLC’s types is provided by type plcVal in module Absyn: type plcType = | IntT (* Int *) | BoolT (* Bool *) | FunT of plcType * plcType (* type -> type *) | ListT of plcType list (* (type, ..., type) *) An expression of the form FunT (t1, t2) denotes the type t1 -> t2 of (unary) functions with input of type t1 and output of type t2. An expression of the form ListT [] denotes type Nil. An expression of the form ListT [t1; ...; tn] with n > 1 denotes the list type (t1, . . ., tn). The current implementation has a dummy type checker, function PlcChecker.teval, that does nothing and just returns the Nil type (ListT [] in abstract syntax) for any input. You are to replace the current implementation of teval with that of a full type checker for PLC along the lines of the one for Micro-ML

This is a programming assignment in F#. You can do it alone or in a team two people. In the latter case, you are responsible for contacting other students and form a team. Pay close attention to the...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment