Sign up for the mailinglist csu670@lists.ccs.neu.edu and
use it for communication with the class.
Check the archive of this mailing list to get many of your
questions about Eclipse and other
course topics answered
(
CSU 670 Mailinglist Subscription
).
THEME: Software Development
for Constraint Satisfaction Problems Using Templates
Learn basics of XML by studying Demeter example:
You learn about data type definitions (DTDs) and schemas, documents and
Java code generation from XML DTDs or schemas.
You learn the basics of Eclipse.
Eclipse is award-winning open-source technology that has strong backing by many companies, including IBM. Use the Eclipse IDE to browse through the files to understand what the program is doing, maybe using different perspectives. Also use Eclipse to develop your own programs. The reason is that later in the course you will add a plug-in to Eclipse and it will be very helpful to know how Eclipse works before you add your own plug-in. Check Eclipse Information to learn about Eclipse installations.
On the WWW,
SD = http://www.ccs.neu.edu/home/lieber/courses/csu670/f06
DemJ = http://www.ccs.neu.edu/research/demeter/DemeterJava
DJ = http://www.ccs.neu.edu/research/demeter/DJ
D = http://www.ccs.neu.edu/research/demeter/
The directory containing administrative information and homeworks is: $SD
Course number: CSU 670
Name:
Account name:
Name: (unless you work individually)
Account name:
Assignment number:
Date:
Do NOT include your student id number in any work you submit because some of your work may be put on the web and you don't want your social security number visible.
READING:
Read chapters 1, 3 and 4 of the AP book.
Read: chapter 1: A Quick Tour of Java in the Java book by Arnold/Gosling
or
the approximately equivalent information in your favorite Java book.
Skim read the following:
$DemJ/forReadersAPBook/APbookWithDJ.html
$DemJ/forReadersAPBook/APbookWithDemJava.html
$DemJ/forReadersAPBook/simple-example.txt
About UML class diagrams at www.rational.com/uml
About XML: http://www.xml.com/axml/axml.html
(XML = eXtensible Markup Language is a W3C Recommendation,i.e., it
is a standard.)
Read about the Law of Demeter: Read section 26: "Decoupling and the Law of Demeter" in the text book The Pragmatic Programmer (TPP). Consider the Challenges question on page 142 and compare with your D*J experiences you make in this course.
The following is from the wiki page shown below:
You can play with yourself.
You can play with your own toys (but you can't take them apart),
You can play with toys that were given to you.
And you can play with toys you've made yourself.
For more information:
http://c2.com/cgi/wiki?LawOfDemeter
This homework is about reverse
engineering of Java programs into an object-oriented
design.
Reverse engineering means to figure out the design from the program
text.
In this particular situation, the documentation for the program has been "lost" intentionally.
You will learn
how difficult it is to understand an undocumented program, even if it is small.
Consider the Java program in directory
$SD/hw/1/max-sat/gen.
The files in directory $SD/hw/1/dir with suffix *.java make up the program.
The last 4 lines in file "prepare" show how to compile and run.
To compile and run, please put the rt.jar file into your class path. See:
http://www.ccs.neu.edu/research/demeter/software/docs/install.html
If you use the CCS .software file, use: CLASSPATH=.:/proj/demsys/demjava/rt.jar
Run "resoft" after the change.
Turn in the output produced by running the program you compiled.
Note: The files in dir have been generated by DemeterJ from short higher level files
that comprise the "documentation" that you have to find.
While you study the Java programs, you also
learn how DemeterJ generates code.
The code generation process is similar
to the code generation process described in JSR 31, now implemented in JAXB
by SUN. This Demeter-like code generation capability is now a part
of the latest Java Web Services Developer Pack.
http://www.ccs.neu.edu/research/demeter/technology-transfer/XML/index2.html.
So we have the following correspondences:
XML Document type definition or schema :: program.cd (class dictionary. NOT GIVEN; YOU DRAW IT (by hand or using Eclipse with the OMONDO plug-in))
XML document :: program.input (sentence)
The following file gives you information on the code generation process:
http://www.ccs.neu.edu/research/demeter/DemeterJava/quick-help/TABLE-OF-CONTENTS.txt
Start your reverse engineering effort with file Formula.java.
Answer the following questions:
1. Draw a UML class diagram for the Java source files in $SD/hw/1/dir. (For information on UML, see http://www.rational.com/uml/)
Turn in a picture of the UML class diagram. Use your favorite drawing tool to create it and turn in the file that your drawing tool (maybe a pen) produces.
Your UML class diagram will contain directed associations. A directed association looks like:
-------- -------- | A | 1 | B | | | ----------------->| | -------- x --------
A is the source class, B the target class and x is the name of the role.
In the Java implementation, A and B are classes and A has an instance
variable x of class B.
Association is a synonym for relation. The directed association above
presents a binary relation. You think of it as a set of pairs, namely (A-object,B-object)
pairs. A natural way to implement such a relation is to store the B-object
which is
associated with a given A-object in the instance variable x of the
A-object.
The name "association" comes from the OMT method. It has found its way into the UML vocabulary.
Do not put methods and their signatures into your UML class diagram
unless you use a tool to automatically produce the diagram.
==============
2. Describe the behavior of the program in English.
Try to summarize the program as much as possible. Do not just translate
each line in the program into
English.
Try to describe the
overall behavior of the methods.
Here is a start: When
cd dir
cd classes
java Main < ../program.input
runs, the Java virtual machine executes the byte code in file Main.class.
This code will execute function Main.main which creates a Formula-object from
file program.input using a parser whose functioning
will not be explained here; the parser is automatically generated by a
parser generator called ...
----------
In the following we explain the behavior of print() ...
NOTE ABOUT PART A:
You need to study the generated Java code (in the dir directory) although it might be confusing. Also keep in mind that there are several ways to generate the code and you see here only one way. For example in the JAXB approach by SUN mentioned earlier there is a separate file that allows you to control the details of code generation. DemeterJ uses a fixed method.
You are asked to wade through a tremendous amount of Java code.
When you study the Java code keep in mind that it must be very regular since it is produced from a small amount of information. Also keep in mind that not all generated code is actually used by the simple application programs. You have to focus only on the code which is used.
Writing simple interpreters
As a general rule for the course, if you need a more detailed
explanatuion of a concept, look it up on wikipedia.org.
For example, search for "conjunctive normal form" or
for "Law of Demeter".
Part B.1:
=========================================================
Write a program that solves:
Input:
1. a propositional logic conjunctive normal form where
each clause has a positive real weight and
2. an assignment J to the variables.
Output:
The total weight of the clauses satisfied by J.
Example:
a or not b or c or not d : 3
and
a or b or not c : 4
and
not a : 100
Assignment: J = a=true, b=c=d=false
The weight is 7.
Find a better assignment that has a higher weight.
Turn in your program and test cases with output.
Turn in a maximum assignment for the above example.
Part B.2:
===========================================================
Write a program that solves:
Input:
1. a system of equations of the form x1+x2+x3=1 where
each equation has a positive real weight.
The variables in the equations only assume values 0 and 1. + is ordinary addition.
2. An assignment J to the variables.
Output:
The total weight of the equations satisfied by J.
Example:
x1 + x2 + x3 = 1 : 20
x1 + x2 + + x4 = 1 : 20
x1 + x3 + x4 = 1 : 20
x2 + x3 + x4 = 1 : 100
Assignment: J = x1=1, x2=x3=x4=0
The weight is 60.
Find a better assignment that has a higher weight.
Turn in your program and test cases with output.
Turn in a maximum assignment for the above example.
This problem is also called the PE3SAT problem or the
Exact 3-Satisfiability (XSAT) problem
or the One-in-three Satisfiability problem.
Part B.3:
===============================================================
An important doctrine in software development is to avoid code duplication.
Identify code pieces in the solutions for A and B that are similar and that
could be abstracted out.
Turn in a discussion of the code duplications.
Part B.4:
===============================================================
In the future we want to implement an optimization program that
finds an assignment of maximum weight or close to maximum weight.
To implement the optimization program, we will need the following
subroutine:
Input:
1. a polynomial
(lambda x (f x))
in one variable with real coefficients.
2. a value v for the variable
Output:
(f v)
Example:
polynomial f = 4 * x^3 + 5 * x^2 + 7
(f 2) = 4 * 8 + 5 * 4 + 7 = 59
Turn in your program and test cases with output.
Part B.5:
=================================================================
Parts A,B and D are all about writing interpreters for little languages.
Apply the principles about writing interpreters that you learned in
Principles of Programming Languages or in Fundamentals of Computer Science.
Discuss at least one principle or recipe that you applied.
Turn in your discussion.
==================
General rules:
You are responsible for choosing suitable data structures and algorithms.
Use your programming language of choice. In the lectures we will use Java.
Your algorithms should use computing resources wisely because we want to apply
them later to large problem instances.
http://www.ccs.neu.edu/research/demeter/DJ/
and get a basic understanding of the package.
Find the unknowns in the following Java program: The program prints the city where an employee lives. You should find the UNKNOWNs by using knowledge from your Java book and by what is in the DJ package documentation. Only after you have found all the UNKNOWNs you may want to run the Java program.
// Main.java
import edu.neu.ccs.demeter.dj.*;
class Main {
static public void main(String args[]) throws Exception {
// Build object
Employee e = new Employee(
new UNKNOWN1(
new UNKNOWN2(
new UNKNOWN3(
new String("Boston")))),
new UNKNOWN4(),
new Date());
ClassGraph cg = buildClassGraph();
System.out.println("City where Employee lives");
System.out.println(e.get_city(cg));
System.out.println("City where Employee lives: UNKNOWN5 ");
System.out.println(e.UNKNOWN6.UNKNOWN7.city.UNKNOWN8);
System.out.println("DONE");
}
public static ClassGraph UNKNOWN9() {
ClassGraph cg=new ClassGraph(true,false);
// true: include all fields
// false: do NOT include all non-void no-argument methods
System.out.println("The UNKNOWN10 version is: " + cg.getVersion());
System.out.println("UNKNOWN11" + "=============================");
System.out.println(cg);
System.out.println("end class graph " + "=============================");
return cg;
}
}
//
import edu.neu.ccs.demeter.dj.*;
class UNKNOWN12 {
UNKNOWN13(PersonalInfo personalInfo_, Date d, Date a) {
personalInfo = UNKNOWN14;
departure = UNKNOWN15;
arrival = UNKNOWN16;
}
PersonalInfo personalInfo;
Date arrival;
Date departure;
String get_city(ClassGraph cg) {
return (String) cg.UNKNOWN17(this,
"from Employee through City to java.lang.String");
}
}
// PersonalInfo.java
import edu.neu.ccs.demeter.dj.*;
class PersonalInfo {
Address address;
PersonalInfo(Address address_) {
address = address_;
}
}
// Address.java
import edu.neu.ccs.demeter.dj.*;
class Address {
Address(City city_) {
city = city_;
}
City city;
}
// City.java
import edu.neu.ccs.demeter.dj.*;
class City {
City(String name_) {
name = name_;
}
String name;
}
// Date.java
class Date {
}
The DJ version is: DJ version 0.8.2
To provide the answers,
use the file $SD/hw/1/UNKNOWNs
An UNKNOWN may be multiple words.
WHERE
Bring your hw solutions to class or put them into the mail box of the
teaching assistant.
ONE SUBMISSION ONLY PER HOMEWORK
Please submit only once when you are done or on the due date. Submit
a partial solution if you did not complete.
If it is due on day x, it means at the beginning
of class on that day.
For late homework we will deduct 20% per day late, unless you present
a very good reason to the teaching assistant.
1. What kind of preparation do I need
for this course?
Experience with object-oriented design and programming and theory of
computation are the prerequisites.
If you have not taken the equivalent of
(COM 1204 or CSU370) AND (COM 1350 or CSU390)
see the instructor immediately.
You also need to be prepared to practice pair programming
http://www.pairprogramming.com/
Pair programming requires the patience to collaborate with a fellow student towards a common goal:
to both understand how to solve a specific software development problem.
Pair-programming does not mean
that one does the work and the other one watches. Pair-programming is an active collaboration where you frequently switch roles (who types and who supervises; who looks something up; etc.).
You are encouraged to do all homeworks and the project practicing pair programming. Pair programming teams turn in only one solution with both names on it. Keep the same partner throughout the course.
Please keep time logs by creating a file in your home directory ~/courses/csu670/timelog.txt where you keep a record for each homework and project. Indicate how much time you spent in each role and what you worked on and what you delivered. You select the roles.
2. What am I going to do if I join the
class late?
All messages which I send to the class are archived.
If you join the class late,
join the csu670 mailing list and read that archive to get up-to-date.
3. How to download DJ and DemeterJ
The instructions for downloading DJ and DemeterJ are at: http://www.ccs.neu.edu/research/demeter/software/docs/install.html
4. Where can I find the instructions
for DemeterJ?
DemeterJ is not needed for this homework, but if you are curious,
the instructions are at URL:
http://www.ccs.neu.edu/research/demeter/DemeterJava/
5. How can I do my homework on my own computer? If you want to do your homework on your own computer, you need a Java development environment on your PC or workstation and Internet access. In each class usually several students use Windows or Linux to do their homework on their own machine. But you are responsible for installing the necessary software on your own machine.