Abstract Data Types (P/F)
We explore the relationship between algebraic (axiomatic) specification of a (generic) data type and its implementation. You are required to specify the ADT Map1 that supports the following operations described only informally here (Consult Java API description for larger context.)
map: Yields the empty map.
clear: Takes a map m and yields the empty map.
containsKey: Takes a map m and a key k as input, and checks if m has k.
containsValue: Takes a map m and a value v as input, and checks if m has v bound to some key.
equals: Takes two maps m and n as input, and checks if m and n are equivalent, that is, contain similar bindings.
get: Takes a map m and a key k as input, and yields the (latest) value bound to k in m, if present.
isEmpty: Takes a map m as input, and checks if m is empty.
put: Takes a map m, a key k, and a value v as input, and yields a new map that behaves like m except that k is bound to v.
remove: Takes a map m and a key k as input, and yields a new map which has k deleted from m (if it were present).
size: Takes a map m as input, and yields the number of key-value pairs in m. (More precisely, the number of distinct keys bound to values.)
Specify the syntax and semantics of the ADT Map using algebraic (axiomatic) approach.
Give an implementation of the ADT Map in Scheme.
Note: The ADT specs are written in functional style and as such do not support assignments. For example, put(m,k,v) does not change the state of the existing map m. Instead, conceptually, it creates a new map by "cloning'' m and then modifying the copy by inserting the new k-v binding.
What to hand-in?
Submit your well-documented solution in adt.scm (containing algebraic specs of the ADT as comments and a conforming implementation in Scheme). Make sure that the solution files can be loaded and run in Racket without any modification. You must include test calls and expected results.