Fall 2025                         Assignment  2                            Prasad
Abstract Data Types: Specification and Implementation

• NOTE: Choose language R5RS in Racket IDE for developing and running Scheme programs. Test your functions thoroughly.
• You must use the function name specified in the question. Using a different name will not run the related tests and you will lose points.
• The Scheme lectures covering the material are adequate for doing this assignment.
  

Algebraic Specification and Scheme Implementation  (For pacing yourself: October 7,  2025; 11:59pm)

We explore the relationship between algebraic (axiomatic) specification of a (generic) data type and its implementation. You are required to specify the ADT Map¹ that supports the following operations described only informally here (Consult Java API description for a larger context.)  Specifically, you may use K for type of keys and V for type of values, for brevity. (Note also that type names begin with upper case letter, while variable names begin with lower case letter.)

• emap: Yields the empty map.
• get: Takes a map m and a key k as input, and yields the value bound to k in m.
• 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.

1. Specify the syntax and semantics of the ADT Map using algebraic (axiomatic) approach.
2. 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 develop?

Create well-documented solution to the problem in asg2.rkt (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 as comments. 

You are encouraged to work in teams of  upto TWO given the simplicity of the assignment. Avoid the temptation of copying the solution from online or other sources. This will help you better prepare for the exam and for the rest of the course. (We were tempted to make it individual assignment but later decided to allow two members per team to promote some healthy dicussion.)

Footnotes

... Map¹

Reference: java.util.Map

What to turn in?    
     
        You may turn-in your well-documented solution including test cases (with good coverage) and answers you obtain as comments in a single runnable Racket file asg2.rkt on Pilot under Dropbox > Assignment 2.  Make sure that the file is in a form that one can load and run in Racket IDE without any modification.