The University of COMP3259: Principles of Programming Languages
Assignment 2
Yaozhu Sun Instructor
Copyright By PowCoder代写 加微信 powcoder
Deadline: 23:59, 21 March 2022
Table of Contents
Prelude: Recapping Top-Level Functions
1 Pretty Printing, Redux
2 Recursive Functions
3 Function Substitution
4 The Glorious Type Checker
Finale: SNHello!
Your solution must be submitted in a single zip file, named as A2_XXX.zip, with XXX replaced by your UID. Please submit your solution on Moodle before the deadline. Your code should be well-written (e.g. proper indentation, readable names, and type signa- tures). You can test your code using stack test. Please at least make sure your code compiles!
Please do this assignment on your own; if, for a small part of an exercise, you use some- thing from the Internet or were advised by your classmate, please mark and attribute the source in a comment. Do not use publicly accessible code sharing websites for your assignment to avoid being suspected of plagiarism.
Prelude: Recapping Top-Level Functions
So far, we have been playing with a small language in the tutorials that supports arith- metic and logic operations, variable declarations, and so on. However, the ability to define functions is still missing. In Lecture 7, you have been shown how to define a top-level function. Once a function is defined, we can use it anywhere at any times without having to rewrite it. Functions provide an abstraction layer: it encapsulates many instructions into a single name, thus increasing the readability and code reuse of programs.
A function definition consists of a function name, a list of parameters, and a function body. As for the matter of implementation, the syntax of function definitions in our language is as follows:
function fname(p1: t1, p2: t2, …, pn: tn) { body }
Note that each parameter name must be accompanied with a type (Int or Bool for this
assignment). The syntax of function calls is as follows:
fname(e1, e2, …, en)
A program is a sequence of function definitions, followed by a main expression:
function_1
function_2
function_n
expression
Here is an example of a complete program:
function absolute(x: Int) { if (x > 0) x; else -x } function max(x: Int, y: Int) { if (x > y) x; else y } max(absolute(-5), 4) // returns 5
The domain and range of defined functions are limited to the types of Int and Bool, because these are the only types of expression. Such functions are called first-order
functions, in contrast to higher-order functions, which allow functions as arguments and results of other functions (we will cover them in the future).
In order to allow for function definitions, we need to define a new datatype Program: data Program = Program FunEnv Exp
Each program has a function environment, which holds all the function definitions: type FunEnv = [(String, Function)]
The definition above is read as: a function environment consists of bindings between function names and definitions. Each function definition has a list of parameters and a body expression:
data Function = Function [(String, Type)] Exp
To be able to call functions, we need to extend the datatype Exp:
data Exp = …
| Call String [Exp]
If we represent the previous program using the abstract syntax, it will be like:
Program [ (“absolute”,
Function [(“x”,TInt)]
(If (Bin GT
(Lit (IntV 0)))
(Unary Neg (Var “x”))))
Function [(“x”,TInt), (“y”,TInt)]
(If (Bin GT
(Var “y”))
(Var “y”)))
] (Call “max” [Call “absolute” [Lit (IntV (-5))], Lit (IntV 4)])
Pretty scary, right? That’s why we need a new pretty printer!
1 Pretty Printing, Redux
The new pretty printer should be able to handle function definitions. But don’t worry, most parts of the function are done by us, and your job is just to fill in the missing part.
You should have learned how to print a function definition in Lecture 7, but you need to adapt it a bit for our new syntax here. We first print the keyword “function”, followed by the actual function name. Then we add “(” and print the list of parameters. To render parameters, for each pair, we print the parameter name, followed by “: “, and then the type, finally closed by “)”. Printing the function body is trivial, by applying show to it, surrounded by curly braces.
(“foo”, Function [(“x”,TInt), (“y”,TInt)] (Bin Add (Var “x”) (Var “y”)))
The function binding above would be rendered as:
function foo(x: Int, y: Int) { x+y
Question 1. (10 pts.) Complete the definition of showFun in the file Declare.hs.
Below is the output of pretty printing prog1. Your output should be identical to it (including the whitespaces). Just a reminder: stack test can help you check it.
function absolute(x: Int) { if (x > 0) x; else -x
function max(x: Int, y: Int) {
if (x > y) x; else y }
max(absolute(-5), 4)
2 Recursive Functions
After adapting pretty printing, we need to extend our evaluator as well. We use a top-level execution function, as shown in the file Interp.hs:
execute :: Program -> Value
execute (Program funEnv main) = evaluate main [] funEnv
The new environment-based evaluator takes one additional argument (i.e. the function environment):
evaluate :: Exp -> Env -> FunEnv -> Value
We showed the definition of evaluate in Tutorial 4, except for functional calls. In the
case for function calls, the evaluation performs the following steps:
1. Look up the function by name to get its parameters and body.
2. Evaluate the actual arguments to get a list of values.
3. Create a new environment by zipping together the parameter names with the actual
argument values.
4. Evaluate the function body in the new environment.
evaluate (Call fun args) env fenv = evaluate body newEnv fenv where Function xs body = fromJust (lookup fun fenv)
eval x = evaluate x env fenv
newEnv = zip (map fst xs) (map eval args)
An interesting thing to note is that our language supports recursion for free! For example, we can write a factorial function:
function fact(x: Int) {
if (x == 0) 1; else x * fact(x – 1)
fact(5) // returns 120
As we see, fact(5) will evaluate to 120. However, such a recursive function doesn’t always terminate. For example, applying fact to −1 will lead to an endless loop.
Therefore, we want to find out all recursive functions, which potentially result in non- termination. (To simplify the problem, we don’t consider mutual recursion.) We’re going to define a new function recFuns that takes a function environment and returns a list of names of recursive functions:
recFuns :: FunEnv -> [String]
recFuns = error “TODO”
Question 2. (20 pts.) Complete the definition of recFuns in the file Interp.hs. Hint: you can divide this task into three parts:
1. Write a checking function that takes a function name and its body, traverses the syntax tree to find if there is a recursive call to the function name, and returns a Boolean result;
2. Filter the top-level function definitions, keeping those that pass the check above;
3. Map a list of function definitions to a list of function names.
3 Function Substitution
In Lecture 4, we’ve seen another style of implementing an evaluator: by substitution. Thus let’s explore a mixed-style implementation of the evaluator, that is, we still use an environment to evaluate variables, but we substitute away all function calls.
The key insight is that adding top-level functions doesn’t necessarily make our language more expressive. Our language with variable declarations is already expressive enough to handle function calls. All we need is to transform each call site of some function by appropriate Decl expressions. The benefit of this approach is that we don’t need to change the core function of the evaluator from Tutorial 4 because all function calls disappear after substitution.
We start by introducing function substitution, written as: e′⟦f → e[x]⟧
Here, e[x] denotes a function body where only one parameter x occurs (we only discuss single-parameter functions here, but you can easily generalize it to multiple-parameter functions). The whole notation means that in the expression e′, we substitute the func- tion name f with its function body e[x]. Function substitution is defined by induction on the structure of e′ like ordinary substitution. Since f is only used in Call expressions, the only non-trivial substitution is Call:
(Call f e′)⟦f → e[x]⟧ = Decl x (e′⟦f → e[x]⟧) e[x]
By function substitution, we replace the function call by a Decl expression that declares the parameter x to be e′⟦f → e[x]⟧, which expands any further calls to f within e′. With the parameter x declared, we can know the result of the function call from e[x].
For example, if we want to substitute the function call absolute(-5), the result after substitution will be of the form (there is no further absolute calls in the expression -5):
var x = -5;
if (x > 0) x; else -x
Let’s now turn to the implementation of function substitution. In the file Interp.hs, there is a function called fsubst as follows:
fsubst :: (String, Function) -> Exp -> Exp
fsubst (f, Function xs body) e = error “TODO”
It takes a function definition and an expression and returns another expression with no function calls to f. What it does is just like ordinary substitution, except for function calls, where it compares the name of the callee function with f. If they are the same, then it returns an appropriate Decl expression as specified by the formula above, otherwise it recursively substitutes the sub-expressions.
Question 3. (20 pts.) Finish the definition of fsubst in the file Interp.hs. (You need to handle multiple-parameter functions here.)
In the same file, you will see the definition of evaluate’. As you can see, we don’t need to worry about function calls, because expressions should presumably contain no function calls after function substitution. We are still one step away from completion: we need to modify the top-level execution function.
execute’ :: Program -> Value
execute’ (Program funEnv main) = “TODO”
Before calling evaluate’, the new execute’ needs to substitute all the function defini- tions in the main expression.
Question 4. (10 pts.) Finish the definition of execute’.
Hint: For every function definition in funEvn, use fsubst in the main expression. But there is a subtlety: one function can call another function defined before, so the order of function substitution in funEnv matters!
There are disadvantages of course: one disadvantage is that, as with every substitution- based evaluator, it is ridiculously inefficient: quadratically slower than its environment- based counterpart. Another disadvantage is that we lose the ability of writing recursive functions.
4 The Glorious Type Checker
The glorious type checker prevents us doing something crazy, e.g., calling functions that are not even existent, or passing the wrong arguments that are incompatible with the formal parameters.
To augment the type checker to allow type checking top-level functions, we need two steps: 1) type checking function definitions; 2) type checking function calls.
Let’s first see how to type check function definitions. In order to do that, we will have to define another data structure called function type environment to associate function names with their corresponding parameters and return types:
type TFunEnv = [(String, (TEnv, Type))]
After successfully type checking function definitions, we will get a data structure of type TFunEnv, which is needed to type check function calls. So the type checker now will take one additional argument:
tcheck :: Exp -> TEnv -> TFunEnv -> Maybe Type
The function checkFunEnv is used to type check function definitions:
checkFunEnv :: FunEnv -> Maybe TFunEnv
checkFunEnv fds = checkFunEnv’ fds []
For each function, we type check (by using tcheck as before) the function body in the old environments (i.e., the parameters and the function type environment). If the function body type checks, we will get a return type for that function, then we extend the function type environment by one element (the function name, the parameters and the return type). As a result, functions defined later could call the ones defined earlier.
Note that if any one of the function bodies fails to type check, checkFunEnv returns Nothing.
Question 5. (10 pts.) Finish the definition of checkFunEnv’ in the file TypeCheck.hs. As for function calls, we first look up the function name in the function type environment.
If it is not found, we will get Nothing; otherwise, we will get a pair of corresponding
parameters and the return type of the callee function. Then we check if the types of the arguments match the types of the parameters. If it is not the case, we will get Nothing as well; otherwise, we will successfully get the return type.
Question 6. (10 pts.) Complete the definition of tcheck (Call name args).
Now everything is ready to make the glorious type checker! We proceed by first type checking the function definitions (using checkFunEnv). If they type check, we continue by type checking the main expression (using tcheck). If it type checks, we will get True; otherwise, we will get False.
checkProgram :: Program -> Bool
checkProgram (Program fds main) = error “TODO”
Question 7. (10 pts.) Finish the definition of checkProgram according to the explana- tion above.
Question 8. (10 pts.) Does the type checker support recursive function calls? If yes, please show an example with detailed type derivation; otherwise, try to explain why they are not supported and come up with a possible fix to support them.
Your answer to the last question can be written in any form (e.g. hand-written, typeset, or ASCII art). Please remember to pack a soft copy of your answer into the zip file you submit.
Finale: SNHello!
Congratulations if you have managed to finish the assignment!
The interpreter is fully fledged to some extent, but you may not know how to use it as an executable program. In the bundle, you can find a file named Main.hs under the app directory, inside which there is a main function. You don’t need to fully understand the code. It essentially takes the command-line arguments, reads the specified file, does type checking, and finally evaluates the program in the file.
The executable file needs a name. We’re happy to announce that our new-born language is called SNH, which is a recursive acronym for “SNH’s Not Haskell”. To compile SNH, run the following command in the terminal:
> stack build
Under the hood, GHC will compile the source file Main.hs, producing an object file Main.o and an interface file Main.hi, and then it will link the object file to the libraries that come with GHC to produce an executable. Of course, all of these are automatically managed by stack, so you won’t see those intermediate files.
Now you can create a file, say demo.txt, inside which you can write a program in SNH, for example:
function absolute(x: Int) { if (x > 0) x; else -x } function max(x: Int, y: Int) { if (x > y) x; else y } max(absolute(-5), 4)
Save the file and then run the command:
> stack exec snh demo.txt
Hurray! (As a side note, if you want to run the executable snh from anywhere in your shell, run stack install, which will copy the executable to your local bin path.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com