1.
Write maxrun, a function which returns the length of the longest sublist of negative or non- negative numbers and a list of absolute values of the original list elements. Ensure that this list is in the same order.
To report multiple outputs, use a record. We’ll define this particular output record as run_output:
Template:
Sample Unit Test
type run_output = { length : int;
entries : int list; }
let maxrun (l:int list) : run_output = (** YOUR CODE HERE **)
let out = moveNeg [8; -5; 3; 0; 10; -4] in
if out.length = 3
&& out.entries = [8; 5; 3; 0; 10; 4]
then print_string “Pass” else raise (Failure “OOPS”);
2.
Given the following typed representation of lists which allows only for ints and bools and if an typed expression (texpr), write a check, with the type, val check: texpr -> bool which checks this. Note that the * indicates it’s a tuple, and so we have that texpr is a tuple of a type and an expression. Also, the and keyword allows the definition of expr to see texpr and vice versa. This is called mutual recursion.
type ty = Int | Bool | List of ty type texpr = ty * expr
and expr =
| IntLit of int
| BoolLit of bool | Seq of texpr list
let rec check texpr =
(** YOUR CODE HERE **)
Here’s an example of a well-typed texpr:
and an example of an incorrectly typed texpr (return false):
Note you need to check that
• each tuple is correctly typed
• each list is correctly typed
• nested lists are also correct
• if the Seq has an empty list of texpr, any List type is legal
3.
Note that we can actually infer the type of an texpr. If we see (x, IntLit (8)), we know x should
be an Int. So now write a similar function infer which overwrites any incorrect types. val infer: texpr -> texpr
Note:
• if an empty list is encountered,
• if a list has inconsistent types,
• list order is preserved
negExample from Problem 5 should be inconsistent.
let posExample = (List (List Int),
Seq
[ (List Int, Seq [(Int, IntLit 4); (Int, IntLit 2); (Int, IntLit 0)]);
(List Int, Seq []) ])
let negExample = (List Bool,
Seq
[ (Bool, IntLit 9);
(List Bool, Seq [(Bool, BoolLit false); (Bool, BoolLit true)]); (Bool, BoolLit true) ])
raise (Failure “empty list”)
raise (Failure “inconsistent”)
let infExample = (List Int,
Seq
[ (Int, Seq [(Bool, BoolLit false); (Bool, BoolLit true)]); (Bool, Seq [(Int, BoolLit true)]) ])
in
infer infExample
evaluates to
4.
Old HP Calculators, programming languages like Forth and Postscript, and abstract machines like the Java Virtual Machine all evaluate arithmetic expressions using a stack. For instance, the expression
(2*3)+(3*(4-2))
would be written as
23*342-*+
and evaluated like this (where we show the program being evaluated on the right and the contents of the stack on the left):
(List (List Bool), Seq
[ (List Bool, Seq [(Bool, BoolLit false); (Bool, BoolLit true)]); (List Bool, Seq [(Bool, BoolLit true)]) ])
[]
[2]
[3, 2]
[6]
[3, 6]
[4,3,6] | 2-*+ [2,4,3,6] | -*+ [2,3,6] | *+ [6, 6] | +
[12] |
| 23*342-*+ | 3*342-*+
| * 3 4 2 – * +
| 342-*+ | 4 2 – * +
The goal of the following problems is to write a small interpreter that translates [aexp]s into stack machine instructions.
The instruction set for our stack language will consist of the following instructions:
• SLit n : Push the number [n] on the stack.
• SVar x : Load the identifier [x] from the store and push it on the stack
• SPlus : Pop the two top numbers from the stack, add them, and push the result onto the
stack.
• SMinus : Similar, but subtract.
• SMult : Similar, but multiply.
• SDiv : Similar, but with integer division and raise (Failure “Divide by Zero”)
In OCaml we define the type as:
type sinstr =
| SLit of int
| SVar of string | SPlus
| SMinus
| SMult | SDiv
Click for Exposition
In the following problem, we write a function that can execute a single program represented by a list of stack instructions.
Part A
First we write a function, prog_exec_inst that can execute a single program instructions updating the stack. It should take as input a symbol table, a stack represented as a list of numbers (top stack item is the head of the list), and a program represented as a list of instructions, and it should return the stack after executing the program. A symbol table is a map which returns the variable value given a variable name.
The option type defined: type ‘a option = Some of ‘a | None is a standard library utility that allows us to report if an operation fails to compute. Note that the specification leaves unspecified what to do when encountering an [SPlus], [SMinus], or [SMult] instruction if the stack contains less than two elements. Use the option type to handle these cases by returning None for these unspecified cases. But our interpreter will never emit such a malformed program.
Note that we raise an error when we see a divide by zero but returns None if there is unspecified behavior
Sample Unit Test
let prog_exec_instr (symbol_table: int StringMap.t) (inst : sinstr) (stack : int list) : (int list) option =
(** YOUR CODE HERE **)
module StringMap = Map.Make(String)
let sym_tbl = StringMap.add “X” 3 StringMap.empty in
let stack = prog_exec_instr sym_tbl (SVar “X”) [4] in let stack’ = prog_exec_instr sym_tbl (SMult) [3;4] in if stack = Some [3;4] && stack’ = Some [12]
then print_string “YAY” else raise (Failure “OOPS”); Part B
Now use prog_exec_instr to write prog_exec which evaluates a list of sinstr with a symbol table and returns the int option. Note that if the inputs don’t correspond to an evaluable
expression prog_exec returns None.
Sample Unit Test
let prog_exec (symbol_table: int StringMap.t) (prog : sinstr list) : int option = (** YOUR CODE HERE **)
module StringMap = Map.Make(String)
let sym_tbl = StringMap.add “X” 3 StringMap.empty in let prog = [SLit 4; SVar “X”; SMult] in
if (prog_exec sym_tbl prog) = Some (12)
then print_string “YAY” else raise (Failure “OOPS”);