Chapter 1

Introduction: The Dictionary Problem

Jack and Jill have a problem. They are writing a software program for playing Scrabble and they need a dictionary to look up words. The most natural way to do this is to read in a file of words when the program first starts up. Depending on the size of the dictionary, this file could become quite lengthy, perhaps 50,000 words. Jack's job is to gather the words into a file named words.txt, with one word per line. He starts out with just seven words, planning to add the other 49,993 words tomorrow or the next day (Example 1-1).

Example 1-1. words.txt File

hill
fetch
pail
water
up
down
crown

Meanwhile, Jill starts coding the Java dictionary object. She uses a very straightforward approach. When the Dictionary0 object is created, it will read in the words from the file words.txt and store them in the Vector called "words." A Vector is a variable-length list of items (Example 1-2).

Example 1-2: Dictionary0.java

import java.io.*;
import java.util.*;

class Dictionary0 {
    Vector words = new Vector();
    
    Dictionary0() {
        loadWords();
    }
    
    void loadWords() {
        try {
            BufferedReader f = new BufferedReader(
                 new FileReader("words.txt"));
            String word = null;
            while ((word = f.readLine())!=null) {
                words.addElement(word);
            }
        } catch (Exception e) {
            System.err.println("Unable to read from words.txt");
            // continue with empty dictionary
        }
    }

    public boolean isWord(String w) {
        for (int j=0; j<words.size(); ++j) {
            String w2 = (String) words.elementAt(j);
            if (w.equals(w2)) {
                return true;
            }
        }
        return false;
    }
}

Jill only needs the method isWord to determine whether a word is in the dictionary, which is good enough for her Scrabble game. But she is starting to think that this dictionary object might also be useful in other game programs she would like to write some day. Jill is also thinking that Vector might not be the best way to store the words, and a linear search might not be the best thing to do now, but as a good engineer she knows that she must first get it right, and later she can make it fast. And indeed, she tests the program and everything runs smoothly and fast!

The next day, Jack finishes his job of adding the other 49,993 words to the dictionary, and Jill discovers a major problem when she runs the program. As expected, the linear search is just a bit too slow, but since words are not looked up very often in Scrabble, it isnít too bad. The real problem is that it takes too long to start up the program, because reading in a file with 50,000 words is just too costly.

Jill sighs, but then remembers that the Scrabble game will be distributed as an applet on the Web, and later it will be installed on a Java hand-held game machine, and in neither case will she be able to easily read in the words from a file anyway. So, Jill writes a much simpler and faster program where the words are stored in an initialized array instead of read from a file (Example 1-3).

Example 1-3: Dictionary1.java

class Dictionary1 {
	
	String[] words = {
		"hill",
		"fetch",
		"pail",
		"water",
		"up",
		"down",
		"crown"
	};

	boolean isWord(String w) {
		for (int j=0; j<words.length; ++j) {
			if (w.equals(words[j])) {
				return true;
			}
		}
		return false;
	}
}

The dictionary is part of this program, and the words do not need to be read in when the program starts. Again, she runs and tests her new program and is satisfied with the results.

Like any good software engineer, Jill ponders the difference between her two programs (Figure 1-1):

  1. Performance: The two programs differ in speed. In Dictionary0 the words must be read from a file and stored in a data structure. This computation is performed every time the program is executed. In Dictionary1 this work is done at compile time. The resulting executable is larger and therefore may take more time to load, but in general it is much faster than the first approach (and it will be lightning fast for the Java hand-held game machine). Also, compiler optimizations may provide another performance boost. The words array could be declared final and the compiler could use this information to create faster and shorter code.
  2. Simplicity: Simplicity is in the eye of the beholder. At first glance it would appear that Dictionary1 is simpler, because we don't need the initialization code or the loadWords method. What will Jack think?

Figure 1-1: Dictionary0 and Dictionary1

When Jack gets wind of Jill's changes, he is upset. He has just spent the whole day typing in 49,993 words into the words.txt file. What will Jack do? He certainly won't want to type them in again with quotes and commas. Besides, he likes his simple file a lot better than one cluttered with quotes and commas. Then he gets an idea: just write a program to read the words in the file words.txt, slap on some quotes and a comma, and output the array data for the Dictionary1 program (Figures 1-2 and 1-3). He can reuse the loadWords method from Dictionary0 and just execute the lines:

for (int j=0; j<words.size(); ++j) {

System.out.println(" \""+words.elementAt(j)+"\",");

}

Jack likes this because he can continue using words.txt, and the translation program will create the file that Jill can use for her program. Jill also thinks itís a cool idea, but she doesn't look forward to cutting and pasting the words into her program. So she suggests that, instead of generating a 50,000-line file, why not just generate the whole program, all 50,014 lines? It's only 14 lines longer. And there you have itóthe birth of a program generator (Example 1-4).

Example 1-4: Dictionary1Generator.java

import java.io.*;
import java.util.*;

class Dictionary1Generator {
    static Vector words = new Vector();
    
    static void loadWords() {
        try {
            BufferedReader f =
                new BufferedReader(new FileReader("words.txt"));
            String word = null;
            while ((word = f.readLine())!=null) {
                words.addElement(word);
            }
        } catch (Exception e) {
            System.err.println("Unable to read words from words.txt");
            // continue with empty dictionary
        }
    }
    
    static public void main(String[] args) {
        loadWords();
        
        // Generate Dictionary1 program
        System.out.println("class Dictionary1 {\n");
        System.out.println("    String words = {");
        for (int j=0; j<words.size(); ++j) {
            System.out.println("        \""+words.elementAt(j)+"\",");
        }
        System.out.println("    };");
        System.out.println("\n");
        System.out.println("   public boolean isWord(String w) {");
        System.out.println("     for (int j=0; j<words.length; ++j) {");
        System.out.println("            if (w.equals(words[j])) {");
        System.out.println("                return true;");
        System.out.println("            }");
        System.out.println("        }");
        System.out.println("        return false;");
        System.out.println("   }");
        System.out.println("}");
    }
}

Figure 1-2: The Dictionary1Generator creates Dictionary1.java.

Figure 1-3: Flow diagram with file contents

To fully appreciate the differences between these two approaches, we need the concept of binding time. This is the time at which certain information is determined or bound to a program. Consider the binding time of the dictionary words. In the first case, the words are read at run time. The binding occurs at the time they are read and stored in the Vector. In the second case, they are read in before compile time. This might not seem like a big deal, but it means you must recompile the program if you want to make a change in the words. Program generators introduce a third binding time in addition to the two traditional ones (Figure 1-4).

  1. Generation time: The time at which the program is generated after reading a specification of the program (in this case, the specification is simply the list of words).
  2. Compile time: The time at which the generated program is compiled.
  3. Run time: The time at which the generated program is executed.

Figure 1-4: Binding times

Jill again ponders the differences among her various programs. As before, she observes the interesting way in which some run-time computation is transferred to other times. In particular, the loadWords method has been literally moved out of the run time (in Dictionary0) to generation time (in Dictionary1Generator). This is good, because it means the run time is faster and more optimized for the task.

Both Jack and Jill are happy with the results. Jack can continue adding to words.txt. A new Dictionary1.java program can be regenerated whenever they want. Jill is pleased as well, because she really didn't want Jack touching her program. Besides, having two people modifying the same text file at the same time is asking for trouble.

Jill now concentrates on the somewhat slow linear search. She decides it would be easiest to retain the array and do a binary search on a sorted list of words. So she tells Jack to alphabetize the words. After frowning for a few seconds, Jack mumbles agreement. That makes Jill think a little harder. Perhaps it would be better to let the program generator sort the words. In fact, it would be a lot better, because she isnít sure that words.txt will always be properly sorted. After it has been sorted, how will she know that alphabetical order will be maintained? Just one little slip-up, and her binary search wouldn't work any longer. It would be a lot safer (less error prone) if the program generator sorted the words. Then she would know with more confidence that the words were sorted correctly. Thus, she adds a sortWords method to sort the words after reading them in and before generating the program.

Later that day, she notices that the word "pail" appears twice in the file words.txt. Although this doesn't alter the behavior of the program, it does make the dictionary larger than it needs to be. Jack starts to explain the systematic way he is typing in words which sometimes unfortunately and accidentally leads to duplicate words. Jill doesn't understand, and she decides it is better to simply add one more tweak to her program generator by detecting and removing duplicate words (which is easily done while sorting).

The program generator now has three distinct parts: getting the data, analyzing/transforming it, and generating the program. And this is also the typical structure of other program generators as well. Figure 1-5 illustrates this structure.


Figure 1-5: Structural comparison between Dictionary1Generator and typical program generators

Example 1-5 shows the outline of the generated program, often called a template. The parts in italics describe how to create the variable parts of the generated program. The remaining ordinary text is simply copied to the output.

Example 1-5: Template for Dictionary1 Generator

class Dictionary1 {
	
	String[] words = {
	for each word in words.txt loop
		"word",
	end-loop
	};

	boolean isWord(String w) {
		for (int j=0; j<words.length; ++j) {
			if (w.equals(words[j])) {
				return true;
			}
		}
		return false;
	}
}

1.1 Onward and Upward

Jack and Jill are so comfortable using their program generator that they expand it to solve more and more problems.

  1. Multiple dictionaries: They need lots of different dictionaries for variations in the game, including one for English, one for French, one for place names, and others for poets, priests, and politicians. Some games require multiple dictionaries in the same program, so some provision is made for creating and managing multiple dictionary objects.
  2. Different sets of methods: As Jack and Jill expand their word-game repertory, they find they need other dictionary methods. For Scrabble they needed only the isWord method, but for other games they need a way of enumerating the words, and words that partially match words in the list. They add options to the program generator so that only the methods that are needed will be generated. This keeps their class files lean and mean.
  3. Extended dictionaries: As Jack and Jill's business expands, they add more information to the dictionary so that a wider variety of games can be created. For each word, they add antonyms, synonyms, homonyms, rhymes, and all manner of other relations. Their dictionary is no longer just a list of words. And the generated data structures are now becoming a lot more complex than just an array of Strings.
  4. 4. Performance differences: Jill discovers that, depending on the context, different data structures and searching algorithms are needed. In some cases memory is critical; in others speed is critical. For speed-critical applications she uses hash tables and doesn't care as much about space. For memory-critical applications (such as downloaded applets on low-bandwidth lines or memory-challenged Java hand-held game machines) she employs Huffman encoding to minimize the space needed to store the dictionary (at the expense of a slower dictionary lookup).

With the addition of these variations, the simple program generator grows and evolves into a large, sophisticated piece of software. These variations should also suggest other issues and complexities that need to be addressed when building real-world program generators.

One of the principal issues is simply understanding the set of variations the program generator should support, and how they may change over time. Chapter 2 describes domain engineering, a systematic process for understanding application domains and building tools for supporting software development in the application domain. Domain engineering entails two steps:

 

  1. Domain Analysis: The first step determines what a domain is, and the variations that must be supported.
  2. Domain Implementation: The second step constructs the environment and tools required to support the swift creation of programs within the domain. This step may result in the construction of program generators.

1.2 Other Program Generators

Jack and Jill weren't the first people to conceive of a program generator. Program generators have been used for many years in certain application domains, including, for example:

There are many other specialized areas where gains in efficiency and productivity are possible, but there are no commercially available systems for a variety of reasons, including a smaller niche market or an immature domain that lacks standardized approaches.

If you can't buy the tools you need, then you'll have to build your own, just like Jack and Jill. And isn't this why you're reading this book? This book will show you how to plan, design, and build program generators in a systematic manner. You will also be able to evaluate different approaches and take various shortcuts to reduce the amount of work needed for building such tools.

1.3 Why Use Program Generators?

Letís review the motivations for using (and creating) program generators. In general, the number one reason is increased productivity. Some of the reasons below are evident in the simple dictionary example, but others won't become evident until we look at more complex examples.

1.4 Organization of the Book

Jack and Jill stumbled into program generators and learned by painful experience. You can skip some of those painful experiences, and you can skip around the various chapters of this book (Figure 1-7). Chapters 2, 3, and 4 provide glimpses into Domain Engineering concepts that provide the systematic development framework for program generators. Chapter 5 is an introduction to XML. Chapters 6 and 7 show alternative techniques to program generation. Chapters 8 through 12 focus on program generators, Chapter 8 showing "what to generate" and Chapters 9 to 12 "how to generate." Finally, Chapter 13 is devoted to the relationship between program generators and component-oriented programming.

The story of Jack and Jill continues in Chapter 3. A more substantial example is created called the Play domain. The Play domain language in XML is created in Chapter 5 and then extensively used in Chapters 6 through 12. Visit http://craigc.com for copies of the examples or the latest information about program generators.

Figure 1-7: Book Organization