Question 1: 33 points
Topic: inductively defined data and functions
=============================================

You may answer this question in any programming language,
be it Scheme or Java or DemeterJ or your language 
of choice. 

You write the data structures/grammar (=schema)
as well as the program for the functions
source, target and well_formed.
Your grammar must be LL(1).

Consider traversal programs, called path specs,
that are defined inductively as follows:

DEFINITION OF PATH SPEC:
A path spec is either simple or compound. 
A simple path spec consist of two nodes, called source and target.
A compound path spec is either a join or a merge.
Both a join and a merge path spec consist
of two path specs, called first and second.

Write the functions incrementally:
First for simple path specs, then for join path specs,
and then for merge path specs.

We choose a suitable syntax for representing 
path specs.

Examples: 

A simple path spec:
-> A B 

A join path spec:
(join (join -> A K -> K Q) -> Q Z)

A merge path spec:
(merge (join -> A B -> B C) 
       (join -> A Q -> Q C))

DEFINITION OF SOURCE OF PATH SPEC:
We inductively define the notion of source for a path spec.
The source of a simple path spec is the source node.
The source of a join path spec is the source of the first path spec.
The source of a merge path spec is the source of the first path spec.

Examples: 

A simple path spec:
source of -> A B is A.

A join path spec:
source of (join -> A K -> K Q) is A.

A merge path spec:
source of 
(merge (join -> A B -> B C) 
       (join -> A Q -> Q C))
is A.

DEFINITION OF TARGET OF PATH SPEC:
We inductively define the notion of target for a path spec.
The target of a simple path spec is the target node.
The target of a join path spec is the target of the second path spec.
The target of a merge path spec is the target of the first path spec.

Examples: 

A simple path spec:
target of -> A B is B.

A join path spec:
target of (join -> A K -> K Q) is Q.

A merge path spec:
target of 
(merge (join -> A B -> B C) 
       (join -> A Q -> Q C))
is C.

DEFINITION OF WELL_FORMED FOR PATH SPEC:
We inductively define the notion of well-formedness
for a path spec.
A simple path is always well-formed.
A join path spec is well-formed if the two constituent
path specs, called first and second are well-formed
and if first and second have a meeting point, i.e.,
the target of first must be the source of second.
A merge path spec is well-formed if the two constituent
path specs, called first and second are well-formed
and if source of first = source of second 
and if target of first = target of second.

Examples: (from the actual execution of a program)

(join	
	(join	
		->A K
		->K Q
	)
	->Q Z
) 
above path spec is well formed true

(join	
	->A K
	->K Q
) 
above path spec is well formed true

->A K 
above path spec is well formed true

->K Q 
above path spec is well formed true

->Q Z 
above path spec is well formed true

(join	
	(join	
		->A K1
		->K Q
	)
	->Q Z
) 
above path spec is well formed false

(join	
	->A K1
	->K Q
) 
above path spec is well formed false

->A K1 
above path spec is well formed true

->K Q 
above path spec is well formed true

->Q Z 
above path spec is well formed true

(merge	
	(join	
		->A B
		->B C
	)
	(join	
		->A Q
		->Q C
	)
) 
above path spec is well formed true

(join	
	->A B
	->B C
) 
above path spec is well formed true

->A B 
above path spec is well formed true

->B C 
above path spec is well formed true

(join	
	->A Q
	->Q C
) 
above path spec is well formed true

->A Q 
above path spec is well formed true

->Q C 
above path spec is well formed true

(merge	
	(join	
		->A B
		->B C
	)
	(join	
		->A Q
		->Q D
	)
) 
above path spec is well formed false

(join	
	->A B
	->B C
) 
above path spec is well formed true

->A B 
above path spec is well formed true

->B C 
above path spec is well formed true

(join	
	->A Q
	->Q D
) 
above path spec is well formed true

->A Q 
above path spec is well formed true

->Q D 
above path spec is well formed true

Write the programs in the order indicated by the following table:

	source target well_formed
simple    1      4        7
join      2      5        8
merge     3      6        9

Points:

1-3: 3 points each: 9
4-6: 3 points each: 9
7-9: 5 points each:15