Project : Get Familiar with the scheme

Please do the following two parts from Structure Programming Language : Scheme

Part :1

a. Design a simple struct, a variable, and a set of functions to operate on these in Scheme.

b. Make sure to set the language to scheme ("#lang scheme") at the top

c. Struct

i. Create a structure using the define-struct function that contains an id, description and price for a single item that could be sold at a grocery store.

d. Variable

i. Define a list of struct objects, each with their own id (must start at 1 and count up consecutively), description (simple string stating what it is, e.g. "milk") and price (a positive integer or floating number).

ii. You must have at least 7 objects in the list.

iii. Give a name for this list as you will need to refer to it.

1. I refer to it as the master list in the text below.

e. Functions (5 pts each)

i. lookup

1. Takes an id and a list (which initially should be the list you defined above) as parameters and returns the object from the list that matches the id (hint: use car and cdr functions)

ii. getdesc

1. Takes an id as parameter

2. Uses the lookup function to find the object with that id and returns the description of the object

iii. getprice

1. Takes an id as parameter

2. Uses the lookup function to find the object with that id and returns the price of the object

iv. subtotal

1. Takes a list (of id's) as a parameter

2. Goes through the parameter list and sums up the prices of all objects matching the id's.

Uses getprice on each id in the list

v. total

1. Takes a list (of id's) as a parameter

2. Use the format function to display the subtotal (found by calling the subtotal function you defined) as well as the total (found by using the subtotal plus its tax 11%).

3. Use Scheme's let expression to avoid evaluating the subtotal twice.

a. "Let" is a common tool used in functional languages to define a new scope and any local variables for use inside that scope.

vi. getlist

1. Takes no parameters

2. Returns a list of lists where each inner list is the id, description and price of each object in the master list

3. Since this doesn't take any parameters, you may want to define a helper function that takes a list as a parameter and have getlist call that helper function passing it the master list. This way you can use recursion with the helper function.

f. Test code

i. Write test code for each function

ii. This lets you make sure everything is working correctly.

g. Put comments to your code properly to describe the functionality of each function

h. There are 6 functions. Each worth 5 pts. In order to get full credit, your code must be runnable. In another words, when I run your test code and/or my test code for each function, it should give me the expected results.

Part: 2

a. Fortunately Scheme is really easy to time.

i. Just use the time function

b. However the hard part is finding enough work so the time isn't 0 and we can actually analyze it

c. Therefore you need to create a decently complicated function:

d. Create a function called gettiminglist (10 pts)

i. This function takes the desired length of the list as a parameter

ii. Its job is to create a list of random whole number values (with the amount of values specified by the parameter) that are between 1 and the length of your master list (inclusively).

1. For example, if there are 7 items in your master list with id's from 1 to 7 inclusively and you call this function with a parameter of 10, one possible outcome could be: (1 2 5 3 3 4 6 1 4 7)

iii. Use the length function to get the length of your list, do not hard-coding it

iv. You will have to add one to all the id's in your list as without this, they will go from 0 up to but not including the length of your master list.

e. Now create a helper function called runtime (10 pts)

i. This function will merely call the gettiminglist function passing it an argument of 20000 (that's 20 thousand) and simply passing the returned list to the subtotal function. The subtotal function can then lookup each id in the list and therefore we can time the multiple calls to the lookup function

ii. Call Scheme's time function on the subtotal call as part of the definition of this runtime function

f. Add code line (runtime) five times. It should give you different times Scheme calculates.

g. Run the code and create a table with all the timings including the averages. Put this in a separate document called "timings" and include it with your submission. Your table should resemble the following (with actual times for the # placeholders) (10 pts):

Run	CPU TIME	REAL TIME	GC TIME
1	#	#	#
2	#	#	#
3	#	#	#
4	#	#	#
5	#	#	#
Average	#	#	#

Please do the both parts and let me know if you need further details

Thanks