Starting from:
$30
Homework 3 Solution
Please submit the answers to your questions in three distinct files. The files should be named a3q1.txt, a3q2.txt and a3q3.txt. Please do not add anything to these file names! I don’t need your name, my name, the course title or number or date. Please use exactly the function names asked for in each question. Of course, you may use auxiliary functions called whatever you want. Please test your programs before submitting them. We will give you zero for the entire assignment if it becomes clear that you did not bother to run your code even once before submitting it. This happens, for example, when you just copy the code from your friend and make obvious typos that show that you never tried to execute the code. I will be very harsh with people who write divergent programs and don’t try to test them. Of course, some programs diverge because of subtle bugs despite your best efforts; I will be very sympathetic in that case. Other programs diverge because you made an obvious error and then never tested the code; most likely you copied the code from a friend at the last minute and introduced typos. If you did this — you know who you are (so do I) — I will take severe measures. Also some of you seem not to know that one uses (* ... *) for comments in SML. I found comments thrown into the code without any indication that these were comments. This causes our grading program to crash. Assignments submitted like that will be tossed out and you will be given zero.
[Question 1. 20 points] We can define linked lists as follows:
datatype ’a rlist = Empty | RCons of ’a * ((’a rlist) ref)
Implement a SML function insert which inserts an element into a sorted linked list and preserves the sorting. The type should be
insert:(’a * ’a - bool) * ’a * (’a rlist) ref - unit
Insert takes in three arguments: A comparison function of type ’a * ’a - bool, an element of type ’a and a linked list l of type (’a rlist) ref. Your function will destructively update the list l. Please note the types carefully, especially which things are references and which are not. Here is the code I used to test the program.
fun display Empty = nil | display (RCons(h, rt)) = h :: (display(!rt))
1
fun less(x,y) = (x < y)
fun show (ref Empty) = (print("\n")) | show (ref (RCons(h,rt))) = (print(Int.toString(h)^","); show(rt))
val foo = ref (RCons(1, ref (RCons(2, ref Empty))))
You may find the display and show functions useful. Note that one of them takes a ref to a list while the other one takes a list. Here are examples of the code in action:
display (!foo); val it = [1,2] : int list - insert(less,5,foo); val it = () : unit - show foo; 1,2,5, - insert(less, 3, foo); val it = () : unit - show foo; 1,2,3,5,
The program is short (5 lines or less) and easy to mess up. Please think carefully about when you are using a reference and when you are using the actual list. Remember SML requires explicit dereferencing.
[Question 2. 40 points] In class, we have shown you a program which mimics transactions done on a bank account. For this we have first defined a data-type for transactions:
datatype transactions = Withdraw of int | Deposit of int | Check_balance
Then, we defined a function make account which generates a bank account when given an opening balance.
In this exercise, you are asked to modify this code and generate a password protected bank account. Any transaction on the bank account should only be possible, if one provides the right password. For this, implement the function make protected account. This function takes in the opening balance as a first argument and the password as a second, and will return a function which when given the correct password and a transaction will perform the transaction. One crucial difference to be noted right away is that in the new code I want you to print the balance on the screen instead of returning it as a value.
val make_protected_account = fn : int * string - string * transactions - unit
Now, two things may go wrong. The password could be incorrect and the amount to be
2
withdrawn could be too big. In these cases I want you to raise exceptions. Here are the exceptions:
exception wrongPassword exception overDrawn of int
If the password is incorrect and the transaction is denied, raise an appropriate exception. Similarly, when the amount to be withdrawn is too large raise an exception with the argument being the balance remaining. I have written an exception handler for you. I want you to fill in the missing pieces of code in the program below:
fun make_protected_account(opening_balance: int, password: string) = let val balance = ref opening_balance val passwd = password in let val acc = <deleted code in fn (pw:string, t: transactions) = (acc(pw,t) handle wrongPassword = print("wrong Password.\n") | (overDrawn n) = print ("Insufficient funds for this transaction. The balance is "^Int.toString(n)^"\n")) end end
Here are examples of the code in action:
val make_protected_account = fn : int * string - string * transactions - unit val it = () : unit - val prakash_acc = make_protected_account(10000,"Morgoth"); val prakash_acc = fn : string * transactions - unit - prakash_acc("Morgoth",Check_balance); The balance is 10000 val it = () : unit - prakash_acc("Sauron",Check_balance); wrong Password. val it = () : unit - prakash_acc("Morgoth",Deposit(1729)); The new balance is 11729
3
val it = () : unit - prakash_acc("Morgoth",Withdraw(4104)); The new balance is 7625 val it = () : unit - prakash_acc("Morgoth",Withdraw(8000)); Insufficient funds for this transaction. The balance is 7625 val it = () : unit
For those of you retieving old solution sets from the internet and turning them in: this superficially looks similar to an assignment from many years ago but is different in several ways. If you submit the old solution I will know you have cheated and I will report you to the Associate Dean for further disciplinary action.
[Question 3. 40 points] We use the following datatype to encode terms of miniML. In this exercise we will implement the function free list which computes the set of free variables in a miniML term. The only subtleties in the syntax below are in the Let and Fun terms.
datatype exp = Nat of int | Plus of exp * exp | Minus of exp * exp | Mult of exp * exp | If of exp * exp * exp | Bool of bool | And of exp * exp | Not of exp | Eq of exp * exp | Lte of exp * exp | Var of string | Let of exp * (string * exp) | Fun of string * string * exp | Apply of exp * exp
The miniML term let x = e1 in e2 is written in terms of the above datatype as Let(e1,(‘‘x’’,e2)). Thus, the variable is nearer the expression that it is binding. Variables are normally written using the Var constructor but in the binding occurrences we omit this constructor and just write the string. In the case of functions, the miniML expression fun foo(n) = body is rendered Fun(‘‘foo’’,’’n’’,body).
Here are some examples of miniML terms written using the above datatype.
val ex1 = Let(Nat(5),("a",(Plus(Var("a"),Nat(2))))) val ex2 = Plus(Var("a"),Nat(2)) val ex3 = Let(Var("y"),("x",Plus(Var("x"),Var("z")))) val ex4 = Let(Nat(3),("z",(Let(Nat(2),("y",ex3))))) val ex5 = Fun("fac","n",If(Eq(Var("n"),Nat(0)),Nat(1), Mult(Var("n"),(Apply(Var("fac"),(Minus(Var("n"),Nat(1)))))))) val ex6 = Fun("f","n",Plus(Nat(3),Var("n"))) val ex7 = Fun("g","n",If(Eq(Var("n"),Nat(0)),Nat(0), Plus(Nat(1),Apply(Var("g"),(Minus(Var("n"),Nat(1)))))))
Implement the function free list of type exp - string list The best way to do this is to write a recursive program without worrying about having multiple copies of a variable, then use a function to remove duplicates from the list. Here is what I got when I ran the program.
4
val remove = fn : ’’a * ’’a list - ’’a list val free_list = fn : exp - string list val ex1 = Let (Nat 5,("a",Plus (#,#))) : exp val ex2 = Plus (Var "a",Nat 2) : exp val ex3 = Let (Var "y",("x",Plus (#,#))) : exp val ex4 = Let (Nat 3,("z",Let (#,#))) : exp val ex5 = Fun ("fac","n",If (Eq #,Nat #,Mult #)) : exp val ex6 = Fun ("f","n",Plus (Nat #,Var #)) : exp val ex7 = Fun ("g","n",If (Eq #,Nat #,Plus #)) : exp val it = () : unit - free_list ex1; val it = [] : string list - free_list ex2; val it = ["a"] : string list - free_list ex3; val it = ["y","z"] : string list - free_list ex4; val it = [] : string list - free_list ex5; val it = [] : string list - free_list ex6; val it = [] : string list - free_list ex7; val it = [] : string list
[Question 1. 20 points] We can define linked lists as follows:
datatype ’a rlist = Empty | RCons of ’a * ((’a rlist) ref)
Implement a SML function insert which inserts an element into a sorted linked list and preserves the sorting. The type should be
insert:(’a * ’a - bool) * ’a * (’a rlist) ref - unit
Insert takes in three arguments: A comparison function of type ’a * ’a - bool, an element of type ’a and a linked list l of type (’a rlist) ref. Your function will destructively update the list l. Please note the types carefully, especially which things are references and which are not. Here is the code I used to test the program.
fun display Empty = nil | display (RCons(h, rt)) = h :: (display(!rt))
1
fun less(x,y) = (x < y)
fun show (ref Empty) = (print("\n")) | show (ref (RCons(h,rt))) = (print(Int.toString(h)^","); show(rt))
val foo = ref (RCons(1, ref (RCons(2, ref Empty))))
You may find the display and show functions useful. Note that one of them takes a ref to a list while the other one takes a list. Here are examples of the code in action:
display (!foo); val it = [1,2] : int list - insert(less,5,foo); val it = () : unit - show foo; 1,2,5, - insert(less, 3, foo); val it = () : unit - show foo; 1,2,3,5,
The program is short (5 lines or less) and easy to mess up. Please think carefully about when you are using a reference and when you are using the actual list. Remember SML requires explicit dereferencing.
[Question 2. 40 points] In class, we have shown you a program which mimics transactions done on a bank account. For this we have first defined a data-type for transactions:
datatype transactions = Withdraw of int | Deposit of int | Check_balance
Then, we defined a function make account which generates a bank account when given an opening balance.
In this exercise, you are asked to modify this code and generate a password protected bank account. Any transaction on the bank account should only be possible, if one provides the right password. For this, implement the function make protected account. This function takes in the opening balance as a first argument and the password as a second, and will return a function which when given the correct password and a transaction will perform the transaction. One crucial difference to be noted right away is that in the new code I want you to print the balance on the screen instead of returning it as a value.
val make_protected_account = fn : int * string - string * transactions - unit
Now, two things may go wrong. The password could be incorrect and the amount to be
2
withdrawn could be too big. In these cases I want you to raise exceptions. Here are the exceptions:
exception wrongPassword exception overDrawn of int
If the password is incorrect and the transaction is denied, raise an appropriate exception. Similarly, when the amount to be withdrawn is too large raise an exception with the argument being the balance remaining. I have written an exception handler for you. I want you to fill in the missing pieces of code in the program below:
fun make_protected_account(opening_balance: int, password: string) = let val balance = ref opening_balance val passwd = password in let val acc = <deleted code in fn (pw:string, t: transactions) = (acc(pw,t) handle wrongPassword = print("wrong Password.\n") | (overDrawn n) = print ("Insufficient funds for this transaction. The balance is "^Int.toString(n)^"\n")) end end
Here are examples of the code in action:
val make_protected_account = fn : int * string - string * transactions - unit val it = () : unit - val prakash_acc = make_protected_account(10000,"Morgoth"); val prakash_acc = fn : string * transactions - unit - prakash_acc("Morgoth",Check_balance); The balance is 10000 val it = () : unit - prakash_acc("Sauron",Check_balance); wrong Password. val it = () : unit - prakash_acc("Morgoth",Deposit(1729)); The new balance is 11729
3
val it = () : unit - prakash_acc("Morgoth",Withdraw(4104)); The new balance is 7625 val it = () : unit - prakash_acc("Morgoth",Withdraw(8000)); Insufficient funds for this transaction. The balance is 7625 val it = () : unit
For those of you retieving old solution sets from the internet and turning them in: this superficially looks similar to an assignment from many years ago but is different in several ways. If you submit the old solution I will know you have cheated and I will report you to the Associate Dean for further disciplinary action.
[Question 3. 40 points] We use the following datatype to encode terms of miniML. In this exercise we will implement the function free list which computes the set of free variables in a miniML term. The only subtleties in the syntax below are in the Let and Fun terms.
datatype exp = Nat of int | Plus of exp * exp | Minus of exp * exp | Mult of exp * exp | If of exp * exp * exp | Bool of bool | And of exp * exp | Not of exp | Eq of exp * exp | Lte of exp * exp | Var of string | Let of exp * (string * exp) | Fun of string * string * exp | Apply of exp * exp
The miniML term let x = e1 in e2 is written in terms of the above datatype as Let(e1,(‘‘x’’,e2)). Thus, the variable is nearer the expression that it is binding. Variables are normally written using the Var constructor but in the binding occurrences we omit this constructor and just write the string. In the case of functions, the miniML expression fun foo(n) = body is rendered Fun(‘‘foo’’,’’n’’,body).
Here are some examples of miniML terms written using the above datatype.
val ex1 = Let(Nat(5),("a",(Plus(Var("a"),Nat(2))))) val ex2 = Plus(Var("a"),Nat(2)) val ex3 = Let(Var("y"),("x",Plus(Var("x"),Var("z")))) val ex4 = Let(Nat(3),("z",(Let(Nat(2),("y",ex3))))) val ex5 = Fun("fac","n",If(Eq(Var("n"),Nat(0)),Nat(1), Mult(Var("n"),(Apply(Var("fac"),(Minus(Var("n"),Nat(1)))))))) val ex6 = Fun("f","n",Plus(Nat(3),Var("n"))) val ex7 = Fun("g","n",If(Eq(Var("n"),Nat(0)),Nat(0), Plus(Nat(1),Apply(Var("g"),(Minus(Var("n"),Nat(1)))))))
Implement the function free list of type exp - string list The best way to do this is to write a recursive program without worrying about having multiple copies of a variable, then use a function to remove duplicates from the list. Here is what I got when I ran the program.
4
val remove = fn : ’’a * ’’a list - ’’a list val free_list = fn : exp - string list val ex1 = Let (Nat 5,("a",Plus (#,#))) : exp val ex2 = Plus (Var "a",Nat 2) : exp val ex3 = Let (Var "y",("x",Plus (#,#))) : exp val ex4 = Let (Nat 3,("z",Let (#,#))) : exp val ex5 = Fun ("fac","n",If (Eq #,Nat #,Mult #)) : exp val ex6 = Fun ("f","n",Plus (Nat #,Var #)) : exp val ex7 = Fun ("g","n",If (Eq #,Nat #,Plus #)) : exp val it = () : unit - free_list ex1; val it = [] : string list - free_list ex2; val it = ["a"] : string list - free_list ex3; val it = ["y","z"] : string list - free_list ex4; val it = [] : string list - free_list ex5; val it = [] : string list - free_list ex6; val it = [] : string list - free_list ex7; val it = [] : string list
1 file (72.5KB)
