--------------------------------------------------------------------------
Software Development    		Fall 2006
CSU 670
--------------------------------------------------------------------------
Assignment 3       		Due date: Sep. 29, 2006

--------------------------------------------------------------------------

This assignment is stored in file $SD/hw/3

in file assign3.txt
--------------------------------------------------------------------------

=========
We reuse the abbreviations already introduced in hw 1.
=========

THEMES: Evolution of Java programs,
          change design, translate to Java

READING:
Read section 12 of TPP: Domain Languages.
   What are the minilanguages that we are using?
   What is our favorite way to define a minilanguage?
Read section 14 of TPP: The power of plain text.
   What kind of knowledge do we keep in plain text?
Read chapter 3: The Basic Tools.
   Are you using one editor that works well on Unix and Windows?
  
This homework requires use of DemeterJ (only a few features) and DJ.

Browse the resource guide at:
 $D/DemeterJava/


Installing:
For this homework, you need DemeterJ. Follow the instructions in:

http://www.ccs.neu.edu/research/demeter/software/docs/install.html

Please note that homework submission is electronic
submission using Blackboard and hardcopy. This will allow the teaching assistant
to run your programs.
In ADDITION, please turn in your answers in hardcopy.
See instructions in previous assignments.


Question 1:
-----------

(This question jointly developed with Jingsong Feng.)

Motivation: Translation between languages / XML

The *.beh files contain Java methods between {{ and }}
that are assigned to various classes. Each *.beh file is of the form:

X{
  {{
     // method 1
     // method 2
     // etc.
  }}
}

Y{
  ...
}
...

and therefore the .beh files are basically 99.99999 % Java code.
When you write your own .beh files,
use your editor to make sure that the parentheses are balanced inside
{{ and }}.



In the lecture we translated bus route descriptions to Scheme make-* expressions.
See
/home/lieber/.www/courses/csu670/f05/examples/BusRoute/BusRoute-scheme

In this homework we translate bus route descriptions to XML documents.

Use the following class dictionary as the definition for the input language.

import edu.neu.ccs.demeter.dj.*;
import java.io.*;

BusRoute = <name> Ident "buses" <buses> List(Bus) "towns" <towns> List(Town).
Bus = <name> Ident <passengers> List(Person).
Town = <name> Ident "busStops" <busStops> List(BusStop).
Person = <name> Ident.
BusStop = <name> Ident <waiting> List(Person).
List(S) ~ "(" {S} ")".
Main = <s> String.

Bus route descriptions in the language are short and your task is to translate them
into longer XML docmuments.

In XML the bus routes have the following format:
(file: busroute.xml)

<?xml version="1.0"?>
<!DOCTYPE busRoute SYSTEM "busRoute.dtd">
<busRoute name="Route1">
   <bus name="Bus45">
     <person name="Dimitrios"/>
     <person name="Viera"/>
   </bus>
   <town name="Boston">
      <busStop name="MassAve">
		<person name="Bryan"/>
		<person name="Mike"/>
      </busStop>
   </town>
   <town name="Cambridge">
      <busStop name="CentralSquare">
	<person name="Alec"/>
	<person name="Matthias"/>
      </busStop>
   </town>
 </busRoute>

The above XML document should be the output for the input below:

 Route1 
 buses (Bus47 (Dimitrios Viera))
 towns (Boston busStops (MassAve (Bryan)) 
       Cambridge busStops (CentralSquare (Alec Matthias)))

The files mentioned below in this hw are in the hw directory (see /xml).

XML has something similar to class dictionaries. They are called 
DTDs and the above XML document satisfies the following DTD:
(file: busRoute.dtd)

<?xml version="1.0"?>
<!ELEMENT busRoute (bus+,town+)>
<!ELEMENT bus (person+)>
<!ELEMENT town (busStop+)>
<!ELEMENT busStop (person+)>
<!ELEMENT person EMPTY>
<!ATTLIST busRoute name CDATA #REQUIRED>
<!ATTLIST bus name CDATA #REQUIRED>
<!ATTLIST town name CDATA #REQUIRED>
<!ATTLIST busStop name CDATA #REQUIRED>
<!ATTLIST person name CDATA #REQUIRED>

This is basically the same information as in our class dictionary with
the exception that the lists must be non-empty in the XML document.

In the following you must use Microsoft Internet Explorer version 5 or later.

The following HTML file, when loaded into Explorer will test whether your XML document
satisfies the DTD.
(file: checker.html)

<html>
<HEAD>
<TITLE> A checker for verifing XML file against its DTD</TITLE>
</HEAD>

<body>
<br>
<br>
<h2>This is a checker for verifing XML file against its DTD.</h2>
<br>

<b>The following is the result for verification:</b>

<br>
<script language="JavaScript">
	var filename="busroute.xml"
	var xmlDoc = new ActiveXObject("Microsoft.XMLDOM")
	xmlDoc.async="false"
	xmlDoc.validateOnParse="true"
	xmlDoc.load(filename)

	if(xmlDoc.parseError.errorCode!=0){
		document.write("<br>This xml file "+filename+" is invalid.")
		document.write("<br>Error Code: ")
		document.write(xmlDoc.parseError.errorCode)
		document.write("<br>Error Reason: ")
		document.write(xmlDoc.parseError.reason)
		document.write("<br>Error Line: ")
		document.write(xmlDoc.parseError.line)
	}
	else{
		document.write("<br>The xml file "+filename+" is valid.")
	}
</script>

</body>
</html>

The following HTML file, when loaded into IE, will process your XML document and compute
the names of the people waiting at the bus stops.
(file: xpath.html)

<html>

<body>

<h2>This page is to demonstrate use XPath to query data in xml file:</h2> <br>

<script language="javascript">
	var xmlDoc=new ActiveXObject("Microsoft.XMLDOM")
	xmlDoc.async="false"
	xmlDoc.load("busroute.xml")

	var nodes=xmlDoc.selectNodes(".//busStop//person")
	var length=nodes.length
	if(length==0){
		document.write("There is no person waiting in the busstops in this busroute")
	}
	else{
		document.write("There are "+length +" persons waiting in the busStops, their names are:<br><br><ui>")

		for (var i=0; i < length; i++) {
		  document.write("<li>"+nodes(i).attributes.item(0).text+"</li>")
		}
		document.write("</ui>")
	}
</script>

</body>
</html>

Use a visitor to do the translation.
Use the visitor with the traversal
that visits the entire BusRoute-object.

Turn in the modified directory  
that contains your new visitor.

The directories must contain your test inputs and a README file that contains
appropriate documentation how to use your directory.

Remember:

Before you zip up a directory generated by demeterj, run "demeterj clean".



=================== Some technicalities
DemeterJ has a project file facility
which works pretty much the same on any platform (the file paths need to be
adjusted from platform to platform). Typically, the project file is
called

program.prj

A default program.prj file is generated by "demeterj new". 

If you use DemeterJ on a PC with Windows and you copy my
program.prj, make sure you change the / to \ in the file paths.
Also, you need to replace javacc by javacc.bat.


Question 2:
-----------

This homework is jointly prepared with Ahmed Abdel Mohsen.

Consider all relations R<=3 of arity 0, 1, 2 and 3 over {0,1}.
For example, for arity 3, a sample relation is:

X1 X2 X3 R166
0  0  0  0
1  0  0  1
0  1  0  1
0  0  1  0
1  1  0  0
1  0  1  1
0  1  1  0
1  1  1  1

Note that: (166)10 = (10100110)2 {compare this to the column R166}

How many elements does R<=3 contain? 

Consider now a subset A of those relations, e.g. {R17, R19, R37}
and a weighted CSP(A) formula f with variable x.

1. Compute how many weighted relations of each kind f contains. The weight of a relation
   is the weight of the constraint containing it.

2. The same for f[x=0], i.e., the reduced formula where x is 0.

3. The same for f[x=1]

The reason why this homework is interesting is that this kind of computation is 
needed to "almost" solve the 1 000 000 million dollar P=NP problem. 

http://www.claymath.org/millennium/

This kind
of relation manipulation algorithm will lead to a performance guarantee t[A] (0<=t<=1) in polynomial time.
If we could achieve t[A] + 1/(1 trillion) in polynomial time, we would earn 1 000 000 
million dollars.

The paper: 
http://www.ccs.neu.edu/home/lieber/p-optimal/partial-sat-II/Partial-SAT2.pdf
contains further details about we are going to use the computation done
in this homework in algorithm MAXMEAN.
This is not required reading, only if you are curious.

Example:

Let R39 (the number 39 is arbitrary):

000 0
100 1
010 1
001 1
110 0
101 0
011 0
111 0

Consider the CSP({R39}) formula f:

11 : R39(x x2 x3)
21 : R39(x2 x3 x4)

f contains R39 32 times.

The reduced formula f[x=0]

11 : R73(x2 x3)
21 : R39(x2 x3 x4)

where R73 (again the number 73 is arbitrary) is defined by:

00 0
10 1
01 1
11 0

f[x=0] contains R39 21 times and R73 11 times.

Come up with your own class dictionary. Of course,
you may reuse class dictionaries from the lectures or from
earlier assignments.

Use DemeterJ to test your class dictionary for syntactic and semantic
correctness:

1. Install DemeterJ
2. demeterj new
3. put your class dictionary into program.cd
4. put above example into program.input
5. In method Main.main in program.beh, remove "Main m = parse(System.in);"
   then add "Start m = Start.parse(System.in);"
6. demeterj test
     should not give syntax or semantic errors on the class dictionary
     or compilation errors from the Java compiler.

The programming part we will do in a future home work.
You only need to turn in the class dictionary to represent the input
objects and the output objects.

Describe in addition the auxiliary data structures you will need to 
implement the computation.

======================
System help:

When you think DemeterJ behaves unexpectedly, use

demeterj clean

which will remove all the generated code.