Assignment 1, CS 152

200 points, due March 5, 1996

Write two programs, one in C and one in Lisp, each of which tests a subprogram that given a filename

1) reads the file, which you may assume consists of (parent,child) pairs in a hierarchy, in the Prolog format described below,

2) constructs an explicit forest of trees to represent the hierarchy, and

3) prints an appropriately indented representation of the resulting forest

Do not worry about the case that a child has at most one parent (in this case you may list the child separately with each parent). You may assume that no parent has more than 10 children.

Your C program should not be in C++. Your Lisp program may be in Logo or Scheme. You need not use advanced concepts of either language or from data structures (e.g, hashing, property lists), or use the most efficient possible algorithm. However I will deduct for gross inefficiency.

You may assume that each file consists of a list of binary relational expressions such as

		 mother(liz,chuck).
More precisely, each expression consists of

There may be any number of carriage return or linefeed characters (but no other characters) between the expressions, before the first expression, and after the last. The predicate names and arguments may contain any printing character except for the comma, the space, the period, and the left or right parenthesis.

For example, the file below

part-of(body,trunk).
part-of(body,head).
part-of(body,arm).
part-of(arm,hand).
part-of(body,leg).
part-of(leg,foot).
part-of(hand,finger).
part-of(foot,toe).
part-of(face,eye).
part-of(face,nose).
part-of(face,mouth).
part-of(head,ear).
would give the following traversal

 body
    trunk
    head
       ear
    arm
       hand
          finger
    leg
       foot
	  toe

 face
    eye
    nose
    mouth

Test on at least the five data files that I have provided on the K: drive (and on the course web page). Note that one of these files is empty. You may assume that each of the files actually exists.