2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
Homework 5: Types and Representations [Updated 11/12 7am]
Due Friday by 12pm Points 60 Submitting an external tool Available Nov 1 at 12pm – Nov 15 at 12pm 14 days
Change Logs
11/12 7am: Added a note about the lack of pattern matching in Scheme.
11/12 6am: Removed “functions” in “functions tree-empty, …” because tree-empty might not be a function.
11/11 6pm: Added a note about redefinition of enum order. It’s recommended to compile the provided code for testing.
11/10 10:20pm: Fixed a typo about expr.scm in Problem 1. (expr-eval was missing).
11/10 10pm: Major rewrite that (1) clarified that the exact representations are mainly up to you, though your Problem 1 C program should use union types and all your Problem 2 programs should use binary search trees, (2) greatly expanded the example section, and (3) added some new notes.
The specification stays the same but lots of (possibly private) Piazza discussions were integrated.
11/9 noon: Fixed the typo “usual Scheme feature” in Problem 3 and revised the warning about negative numbers in Standard ML in Bonus Problem.
11/8 8pm: Fixed the typos in Standard ML example in Problem 1 and clarified variable names in the bonus problem.
11/6 7pm: Added a note in Problem 3 for clarification.
Goal
In this assignment, you will write, compare, and reflect upon programs in C, Standard ML, and Scheme. We will use integer expressions and polymorphic binary search trees as the examples.
Note added at 11/10 8pm: It is part of the assignment to design your own representations. As long as you can satisfy the specification, we do not care how you achieve that.
Problem 1: Integer Expressions (24 points)
We are going to consider a tiny portion of integer expressions built from integer literals, variables (represented as strings), negation, addition, subtraction, and multiplication.
Standard ML
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 1/11
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
In expr.sml, define a type expr to represent integer expressions as described above. You should then define the following functions:
val expr_int : int -> expr
(* `expr_int 5` creates a new expression with number 5 *)
val expr_var : string -> expr
(* `expr_var “x”` creates a new expression with variable x *)
val expr_neg : expr -> expr
(* `expr_neg e` creates a new expression representing `~ e` *)
val expr_add : expr -> expr -> expr
(* `expr_add e1 e2` creates a new expression representing `e1
e2` *)
val expr_sub : expr -> expr -> expr
(* `expr_sub e1 e2` creates a new expression representing `e1 – e2` *)
val expr_mul : expr -> expr -> expr
(* `expr_mul e1 e2` creates a new expression representing `e1 * e2` *)
val expr_eval : (string -> int) -> expr -> int
(* `expr_eval env e` evaluates the expression `e`
where `env “x”` gives the value of the variable `x` *)
To repeat, the last function expr_eval takes a function env that assigns values to variables, and uses it to evaluate the expression e. For a variable named var, env var gives the value assigned to the variable var. How these functions should work together to give the correct results is up to you—it is part of the assignment to design the type expr so that everything works. (Therefore, the output of these functions except expr_eval will probably reveal your design and should not be shared with your classmates on Piazza.)
Here are some examples:
expr_eval (fn _ => 3) (expr_add (expr_var “x”) (expr_int 2))
will give the answer 5 because the functional argument (fn _ => 3) means every variable in the expression is assigned with the number 3, and thus the expression generated by expr_add (expr_var “x”) (expr_int 2) (which represents x 2) should evaluate to 5. Here is another example:
should give the answer 4 because the functional argument (fn v => if v = “x” then 1 else 2) means the variable named “x” is assigned with 1 and all other variables are assigned with 2. Thus the expression representing y-(-2) should evaluate to 4. Here is yet another example:
expr_eval (fn v => if v = “x” then 1 else 2) (expr_sub (expr_var “y”) (expr_neg (expr_int
2)))
expr_eval
(fn v => case v of “x” => 1 | “y” => 2 | _ => 3)
(expr_mul (expr_var “x”) (expr_neg (expr_mul (expr_var “y”) (expr_var “z”))))
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 2/11
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
should give the answer ~6 (negative 6 in Standard ML) because the functional argument (fn v => case v of “x” => 1 | “y” => 2 | _ => 3) means the variable named “x” is assigned with 1, the variable named “y” is assigned with 2, and all other variables are assigned with 3. The expression representing x*(~(y*z)) thus evaluates to ~6.
Note:
1. The specification focuses only on expr_eval. We do not care how you implement other functions as long as they type check and give correct results by working with expr_eval. You have the freedom to decide what the type expr should be and how they work together.
2. When you are loading the code in the SML/NJ interpreter, you might see
val expr_var = fn : string -> expr
which means you have correctly defined a function expr_var of type string -> expr. Do not worry about “= fn”. If you are curious, run val x = 1; in the interpreter and compare the output to the above line.
Scheme
In expr.scm, define functions expr-int, expr-var, expr-neg, expr-add, expr-sub, expr-mul, and expr-eval in a similar way.
(expr-eval (lambda (v) 3) (expr-add (expr-var “x”) (expr-int 2)))
; gives 5
(expr-eval
(lambda (v) (if (string=? v “x”) 1 2))
(expr-sub (expr-var “y”) (expr-neg (expr-int 2))))
; gives 4
(expr-eval
(lambda (v) (cond ((string=? v “x”) 1) ((string=? v “y”) 2) (#t 3)))
(expr-mul (expr-var “x”) (expr-neg (expr-mul (expr-var “y”) (expr-var “z”)))))
; gives -6
Note:
1. Scheme does not have built-in support for custom datatypes, and the actual representation in terms of S-expressions is up to you.
2. Some of you are looking for pattern matching in Scheme. Unfortunately, there’s no portable pattern matching in the Scheme standard(s) yet, and many implementations provide their own, incompatible extensions. (What people called Scheme on the Internet might actually be PLT Scheme, which was later renamed to Racket (https://racket-lang.org/new-name.html) to avoid confusion because it is not Scheme.) There are efforts to standardize the extensions about pattern matching (https://srfi.schemers.org/?keywords=pattern- matching) , but they would not go anywhere before the semester ends. What MIT/GNU Scheme has is the portable syntax-rules (https://www.gnu.org/software/mit- scheme/documentation/stable/mit-scheme-ref/Pattern-Language.html) which might be different from what you are looking for, though you can implement pattern matching through it
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 3/11
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 4/11
(http://synthcode.com/scheme/match.scm) if you have mastered Scheme. As for now, you probably want to rely on cond and procedures such as list? and cdr to extract information manually.
C
In expr.c, use union types and pointers to define a structure type struct expr to represent integer expressions as described above. You should then implement the same set of functions in C. Your code will be compiled with the following header: (You do not have to include or submit the header—the automatic grader has its own header file.)
struct expr;
const struct expr* expr_int(int);
const struct expr* expr_var(const char*);
const struct expr* expr_neg(const struct expr*);
const struct expr* expr_add(const struct expr*, const struct expr*);
const struct expr* expr_sub(const struct expr*, const struct expr*);
const struct expr* expr_mul(const struct expr*, const struct expr*);
int expr_eval(int (*)(const char*), const struct expr*);
Examples (added 11/10 10pm):
#include
#include
struct expr;
const struct expr* expr_int(int);
const struct expr* expr_var(const char*);
const struct expr* expr_neg(const struct expr*);
const struct expr* expr_add(const struct expr*, const struct expr*);
const struct expr* expr_sub(const struct expr*, const struct expr*);
const struct expr* expr_mul(const struct expr*, const struct expr*);
int expr_eval(int (*)(const char*), const struct expr*);
/* this will include your source */
#include “expr.c”
int env1(const char* name) {
return 3;
}
int env2(const char* name) {
if (strcmp (name, “x”) == 0) {
return 1;
} else {
return 2; }
}
int env3(const char* name) {
if (strcmp (name, “x”) == 0) {
return 1;
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330
5/11
Note:
1. (Added 11/10 10pm:) You have to use union types in struct expr to save space.
2. You should add the keyword const in appropriate places within your definition of struct expr
so that it is impossible to destructively modify a subexpression without explicit coercion. (In
general, destructive modification is error-prone.)
3. If you are not familiar with C, perhaps you want to read general resources about function
pointers (finding general resources, instead of ones specific to homework, is always encouraged). For example, here’s a page explaning pointers to functions (http://users.cs.cf.ac.uk/Dave.Marshall/C/node12.html#SECTION001230000000000000000) from Language Resources.
4. You might have to allocate memory for new expressions. Do not worry about freeing it up in this homework assignment.
Problem 2: Polymorphic Binary Search Trees (24 points)
We want to explore how binary search trees that are polymorphic in its element type can be implemented.
Standard ML
In tree.sml, define a type constructor ‘a tree to represent polymorphic binary search trees where each internal node holds one element (no data on the leaves). You should then define the following functions:
} else if (strcmp (name, “y”) == 0) {
return 2;
} else {
return 3;
} }
void print_result(int i) { printf(“%i\n”, i); }
int main () {
print_result(expr_eval(env1, expr_add(expr_var(“x”), expr_int(2))));
print_result(expr_eval(env2, expr_sub(expr_var(“y”), expr_neg(expr_int(2)))));
print_result(expr_eval(env3, expr_mul(expr_var(“x”), expr_neg(expr_mul(expr_var(“y”), exp
r_var(“z”))))));
return 0;
}
val tree_empty : ‘a tree
(* `tree_empty` gives the empty tree *)
val tree_member : (‘a -> ‘a -> order) -> ‘a -> ‘a tree -> bool
(* `tree_member cmp x t` tests whether `x` is in the tree `t`, using `cmp` as the order *)
val tree_insert : (‘a -> ‘a -> order) -> ‘a -> ‘a tree -> ‘a tree
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330
6/11
Note:
1. Both tree_member and tree_insert take a comparison function as their first arguments. Suppose cmp is the comparison function. cmp x y gives LESS if x is less than y, EQUAL if they are equal according to the ordering, and GREATER if x is greater than y. The comparison function forms a total order (https://en.wikipedia.org/wiki/Total_order) among elements in the element type, and the type order (https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.order:TY) is a type defined in the Standard ML Basis Library.
2. (Added 11/10 10pm) The comparison function will be consistent across function calls.
3. If the element to be inserted was already in the tree (decided by the comparison function), the original element in the tree should be kept and the same tree should be returned. (It is
okay if nodes are recreated in this case.)
4. The interface does not prevent you from implementing these functions using something
other than the trees, but we will check your code. You need to use binary search trees to earn points.
Examples:
let fun c x y = Int.compare (x, y) in tree_member c 3 tree_empty end
(* false *)
let fun c x y = Real.compare (x, y) in tree_member c 2.0 (tree_insert c 2.0 tree_empty) end
(* true *)
let
fun c x y = String.compare (x, y)
in
tree_member c “x” (tree_insert c “y” (tree_insert c “z” tree_empty))
end
(* false *)
Scheme
In tree.scm, define tree-empty, tree-member, and tree-insert in a way similar to your Standard ML program. Let cmp be the comparison function. (cmp x y) will return the symbol less, equal, or greater depending on whether x is less than, equal to, or greater than y. Here are some examples illustrating the expected usage:
(* `tree_insert cmp x t` inserts `x` into the tree `t`, using `cmp` as the order.
the same tree is returned if `x` is already in the tree *)
(define (num-cmp x y) (cond ((< x y) 'less) ((= x y) 'equal) ((> x y) ‘greater)))
; note: this is just an example. your code cannot assume what the comparison function is.
(tree-member num-cmp 3 tree-empty)
; gives #f
(tree-member num-cmp 2.0 (tree-insert num-cmp 2.0 tree-empty))
; gives #t
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330
7/11
Note that to construct an empty tree, we use tree-empty, not (tree-empty). The latter is to call a function with no arguments.
C
In tree.c, implement the struct tree type and the other functions. The meaning of these functions should be the same as the ones in your Standard ML program, except that now they are in C. Your code will be compiled with this header: (Again, you do not have to include or submit the header—the automatic grader has its own header file.)
#include
struct tree;
enum order {Less, Equal, Greater};
typedef enum order (*cmp_fun)(const void *x, const void *y);
const struct tree* tree_empty();
bool tree_member(cmp_fun, const void*, const struct tree*);
const struct tree* tree_insert(cmp_fun, const void*, const struct tree*);
Note (added 11/11 6pm): C does not allow you to redefine enum order, so it is probably easier to use the following code for testing.
Examples (added 11/10 10pm):
(define (string-cmp x y) (cond ((string? x
y) ‘greater)))
; note: this is just an example. your code cannot assume what the comparison function is.
(tree-member string-cmp “x” (tree-insert string-cmp “y” (tree-insert string-cmp “z” tree-em
pty)))
; gives #f
#include
#include
#include
struct tree;
enum order {Less, Equal, Greater};
typedef enum order (*cmp_fun)(const void *x, const void *y);
const struct tree* tree_empty();
bool tree_member(cmp_fun, const void*, const struct tree*);
const struct tree* tree_insert(cmp_fun, const void*, const struct tree*);
/* this will include your source */
#include “tree.c”
enum order int_cmp(const void *x, const void *y)
{
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 8/11
Note:
1. (Added 11/10 10pm:) You do not have to use union types in struct tree, but you should avoid unnecessary waste of memory space.
2. You should add enough const in your definition of struct tree so that it is impossible to modify a subtree in place without explicit coercion. You might have to create many new nodes to keep the original tree intact.
3. This also means other parts of the program will not modify the trees you construct, and that you could reuse parts of the input when constructing new trees.
4. Again, do not worry about freeing up memory in this assignment.
if (*((int *)x) < *((int *)y)) {
return Less;
} else if (*((int *)x) == *((int *)y)) {
return Equal;
} else {
return Greater;
} }
enum order float_cmp(const void *x, const void *y)
{
if (*((float *)x) < *((float *)y)) {
return Less;
} else if (*((float *)x) == *((float *)y)) {
return Equal;
} else {
return Greater;
} }
enum order string_cmp(const void *x, const void *y)
{
if (strcmp(x, y) < 0) {
return Less;
} else if (strcmp(x, y) == 0) {
return Equal;
} else {
return Greater;
} }
void print_bool(bool b) { fputs(b ? "true\n" : "false\n", stdout); }
int main () {
int three = 3;
float two = 2.0;
print_bool(tree_member(int_cmp, &three, tree_empty()));
print_bool(tree_member(float_cmp, &two, tree_insert(float_cmp, &two, tree_empty())));
print_bool(tree_member(string_cmp, "x", tree_insert(string_cmp, "y", tree_insert(string_c
mp, "z", tree_empty()))));
return 0;
}
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
Problem 3: Reflection (12 points)
In reflection.txt or reflection.pdf (either typeset or legibly written and scanned), reflect upon what you did and answer the following two questions:
1. What does a Standard ML implementation check before running your code that the Scheme implementation does not? What guarantees do you have when your Standard ML code compiles?
2. Similarly, what kind of guarantees do you have about your Scheme program that you would not know about your C program merely by the fact that they compile?
Note (added 11/6 7pm):
You may assume we are using the "safer" subsets of Scheme and C. For example, in Scheme, you are not using set! to destructively modify a list, and in C, you are not using explicit coercion to drop const. Otherwise, there are few things you can say about your C program. The intended solution focuses on data types and representations and only discusses "usual" features in C and Scheme, but feel free to consider more features that could circumstance compile-time checking. If you are not sure whether a feature is considered "safe" or "usual", just include it in your discussion. You are also encouraged to discuss what might have been checked in C but not in Scheme, if any, but this direction is not required.
Bonus Problem: Compilation (10 points)
Extend your solution to Problem 1 with a function that prints the same code to the standard output as the naive compiler in Prolog. (Note: the "true." in the output is from SWI Prolog, not the program itself, so you should not include "true.") You can also use the code in Homework 4 (but without comments) as a guideline.
Note (added 11/8 8pm): You may assume variable names in the input expression only contain of English alphabets and will never collide with intermediate variables (xi). If in doubt, mimic the Prolog program.
The eventual code should be a valid C fragment. To simplify your work, the prefix is always "x" and the index always starts with "0" for each call to the compiler. That is, it is exactly the same as the Prolog program. Do not worry about the exact whitespace format---the output is regarded as correct as long as it admits the same C parse tree.
Standard ML
In addition to what was required in Problem 1, implement expr_compile in expr.sml such that expr_compile e prints out the code. Check out TextIO.print (https://smlfamily.github.io/Basis/text-io.html#SIG:TEXT_IO.print:VAL) and Int.toString (https://smlfamily.github.io/Basis/integer.html#SIG:INTEGER.toString:VAL) . Be careful about
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 9/11
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
negative numbers---you have to print out -1 even though it is written ~1 in Standard ML so all your three programs output identical C code.
val expr_compile : expr -> unit
Scheme
Additionally define a function expr-compile in expr.scm such that (expr-compile e) will print out the translated code.
C
Additionally implement a function expr_compile in expr.c with the same functionality. Here is its declaration:
void expr_compile(const struct expr*);
Reflection
It is encouraged to incorporate your observations into your solution to Problem 3.
Turn in your work
Use GradeScope (down below in a browser or up above in an app) to submit individual files. You will receive a warning if required files are missing.
Grading
The rubrics will be a mix of automatic grading and manual grading, similar to Homework 1 Rubrics but appropriately adapted. It is thus critical to make sure your code compiles and has the correct filenames to earn the perfect score. The checker on GradeScope will detect basic syntax errors, but not correctness. (Technical details: after the deadline, we will upload a new autograder and create new rubrics on GradeScope; the current one only attempts to compile your code.)
Tips for SML/NJ
SML/NJ might refuse to display deeply nested values. Execute the following two assignments to raise its limit:
Control.Print.printDepth := 1000;
Control.Print.printLength := 1000;
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 10/11
2020/11/13 Homework 5: Types and Representations [Updated 11/12 7am]
Autograder Results
Results
Code
Integer expressions in C (0.0/8.0)
Our autochecker cannot find expr.c
Integer expressions in Scheme (0.0/8.0)
Our autochecker cannot find expr.scm
Integer expressions in Standard ML
Your submission compiles.
Polymorphic binary search trees in C (0.0/8.0)
Our autochecker cannot find tree.c
Polymorphic binary search trees in Scheme (0.0/8.0)
https://canvas.umn.edu/courses/193677/assignments/1355641?module_item_id=4917330 11/11