Due Dates

Project is due on Friday January 19, 2007.

Goals

Expand your familiarity with the Scheme programming language.
Use Scheme to build a small application.

Overview

We will use Scheme to build a database to store information about marriages and births in a family. We can call this a “family tree”, but we will use a list data structure.

The basic data structure will be a list called “Family” that consists of two lists, “Marriages” and “Births”. The form of the data will be such as this:

( ( (bill hillary) (george laura) (husband3 wife3) ) ( (hillary chelsea) (george jenna) (laura barbara) ) )

Marriages is a list of husband-wife pairs (lists), and Births is a list of parent-child pairs (lists). Note that a birth may be entered as a child of either parent.

All names will be unique, and all people will be known by a single name.

Functionality

You will create code to implement the following functions:

Function	Arguments	Effect
New	none	Clears the database, and returns Family = ( () () ), a list of 2 null lists.
AddCouple	Family Spouse1 Spouse2	Adds a new couple to the database, and returns a list representing the expanded family tree.
AddChild	Family Parent child	Adds a new child to the database, and returns a list representing the expanded family tree. If this child already exists in the database, AddChild should have no effect.
Children	Family Parent	Returns a list of children of this individual. If the parent does not exist in the database, or the parent has no children, returns an empty list.
Parents	Family Individual	Returns a list of the parents of the individual. If the individual does not exist in the database, or if no parents of the individual are included in the database, returns an empty list.
Siblings	Family Individual	Returns a list of the siblings of the individual. If the individual does not exist in the database, or has no siblings, returns an empty list.
Descendants	Family Individual	Returns a list of all the children, grandchildren, great grandchildren, etc. of the individual. If the individual does not exist in the database, or has no offspring, returns an empty list.

Functions return appropriate lists, but functions do not change any of their arguments. For instance, your function should not affect the "Family" list when the Family list is an argument to the function.

Details

The children of an individual include all children who are paired with the individual in the Births list, and also all children included in Births who are paired with the spouse. For example, (Children Family ‘george) should return (jenna barbara). The order of children is not important for this project.

The parents of an individual include the parent from the pairing of the individual in Births, and the spouse of that parent. For example, (Parents Family ‘chelsea) should return (bill hillary). The order of parents is not important.

To earn a solid B:

Implement all functions, assuming all marriages are monogamous and last a lifetime.

To earn an A:

Implement all functions, assuming that partners may change.

For example, suppose Marriages also includes (bill jennifer), and Births also includes (jennifer jane).

In this case, the children of an individual include all children of all associated spouses. For example, (Children Family ‘bill) should return (chelsea jane), as should (Children Family ‘hillary) and (Children Family ‘jennifer).

Likewise, the parents of an individual include all associated spouses. For example, (Parents Family ‘chelsea) should return (bill hillary jennifer), as should (Parents Family ‘jane).

Obviously, too, (Descendants Family ‘bill) will include chelsea, jane, and all their descendants.

Advice:

For this project you will need to add comments to your routines. Typically, the number of lines of comments will somewhat exceed the number of lines of code. You will benefit from making it exceedingly clear to yourself and others the purpose of each function, the form expected for each argument, and the form of the return value.

Achieve the functionality required for a B first. The level of complexity required for an A is much higher. You can be proud of accomplishing the B-level functionality, so be sure you have achieved that before you attempt the ultimate level of functionality.

You can get a start with this definition of a testFamily, or you can simply create your own.

What you will submit:

Your file family.ss will be the product you will submit for this lab. family.ss will include code for all the specified functions, and for all the supporting functions you create, but not for any initial definition of the Family database (i.e., I will be running your code against my own Family database structure).

To test your code, download the file schemeFamilyDriver.ss. When you load schemeFamilyDriver.ss, first it will load your family.ss file and the testFamily.ss database, and then it will exercise the required functions. If your code is correct, the output should match that in the file schemeFamilyAnswers.ss.

Submit your file family.ss as an attachment to e-mail and send it to me by the end of Friday January 19, 2007.

Good luck!

Carl Reynolds