Inheritance and polymorphism
Inner classes
Static class members
Arrays (2 dimension)
Recursion
Scanning
Grammars
Parsing and Recursive Descent
Spreadsheet implementation
More on assembly language
Stack
Vector
Postfix evaluation
Applets
Java events (Textfields and Buttons, ActionEvent Listeners)
Model View Architecture
This is another fairly large Toy Box project that introduces spreadsheets. Rather than use a commercial spreadsheet program, this project has the students examine and modify the code of a spreadsheet applet. The program supports cell formulas as well as values. A cell formula is defined using a simple infix assignment language. This is translated with a simple recursive descent parser into postfix form and stored in the cell in question in an assembly language form like the one in SimpleCPU.
The model of the program (the spreadsheet) is separated from the view, and the event structure is sound, with a separate listener for each Java awt component with distinct behavior (One Listener per Component Pattern).
This depends on some earlier introduction to arrays and possibly simple recursive programming.
Here is the library of sources for this project. This should probably be given out complete, but it could be changed into a Fixer Upper or a Fill in the Blanks. If given complete, it can be given in machine readable form, or at least an executable can be made available so the students can exercise it. The scanner is long but simple. It can scan various kinds of things and is useful in other projects (Tool Box). If you have done SimpleCPU, then the students are familiar with the assembly language, but not the execution model. Here we have instruction objects, not functions, and each instruction knows how to execute iteself.
Some time prior to the class in which it is to be discussed, the sources are distributed to students for study. The study should preferably be done in small teams. The instructor can also distribute a list of questions that should be answered about the code. Some of these questions could point to student resource material such as information in the course text on arrays and recursion, for example.
One way to use this is to have the students work in teams of three prior to the first class discussion of this. Have one student in each team responsible for the scanner, one for the gui part, and one for the rest. Each person is to be come the "local expert" on one part of the program and be able to help the rest of that team understand that part. If teams are size four instead of three, then the SpreadsheetCell class with its inner classes can go to one student and the SpreadsheetModel to another. This separates arrays from recursion. If they are already familiar with one of these ideas then this shouldn't be necessary.
The questions should require that they understand and can trace the recursive calls through some simple example. They could also be asked to Reverse Engineer the application, providing a class diagram of the program.
If you have taken the team of three suggestion in the student handout section above, then in class you can have all the scanner "experts" get together (in groups of three or four) and discuss their individual understandings and ask questions of each other. Likewise the other team members will huddle with their counterparts on the other teams.
After a bit, bring the original teams back together for a short session in which each member brings other teams members up to date on what was learned in the expert huddles.
The subsequent lecture can then focus on how it all fits together, though there may be a few questions yet on the parts. Some questions from the instructor can make sure that there are no major misconceptions about the parts.
Add a unary minus. Use ~ for this operator, not -. ~5 means minus 5. (Don't forget to update the grammar)
Add the modulo operator to the language. Use % for this operator. 12 % 5 should yield 2.
Give the program a prettier interface.
Add an additional range function. Choose a good one.
Optimize the operations a bit. What happens if we add zero to something? Can you improve this? Note that here we create a new object to hold the sum. Can we avoid this sometimes.
Add an exponentiation operator. Use ^ for this operator. 2^5 should yield 32. The precedence level of ^ should be higher than that of * and /, but lower than parens. Note that if you permit 2^5^3, that it should group from the right as 2^(5^3). The included operators all group from the left within precedence levels.
Add a logic operator similar to the C++ conditional expression operator ?:. To the left of the ? you need a comparison like a4<3. To the right you need two expressions separated by the colon.
What improvements can you make that will increase the total code size by no more than one page?
Guarantee that recursive programs are caught before they are evaluated.
I think that the idea of a breadth first course should be redefined in terms of projects like this. I think students need to see the breadth of computer science in the first course. I also think they need to work on hard projects in that course. Exercises with this flavor give them some breadth in how computer science is used in the world and also in how sophisticated programs are actually built.
Something like this, if properly used, can foster teamwork. It can also get them used to building things in the context of existing code. Finally it makes them read something more sophisticated than they can build themselves. All of these are very important lessons.
Toy Box, Larger Than Life, Tool Box (Possibly Fixer Upper, Fill in the Blanks, or Reverse Engineer) See http://csis.pace.edu/~bergin/PedPat1.2.html, and http://csis.pace.edu/~bergin/fivepedpat.html for further explanation of these patterns.
Note: The pedagogical pattern Reverse Engineer has not yet been written up. The basic idea is to have students develop a set of design documents from the provided final program. They can use this to get easy familiarity with design documents, to see how a design relates to the final artifact, and also as the basis of extending the program itself.
The major parts of the program are the Applet itself, which has the usual rows and columns view. There are a few buttons. Each "cell" in the view is just a textfield. The cells are arranged in grid layout. There is another textfield for data entry and one for error reporting.
The scanner is a general purpose scanner that will work in this and other projects. It is a class, however, so you need to create a scanner object. There are several constructors, depending on what you want to scan.
The spreadsheet model is a two dimensional array of cell objects. It knows how to evaluate itself, by evaluating all of its cells. It is also responsible for parsing enough of each command to determine what sort of command it is and which cell should complete the parse.
The interesting objects are the spreadsheet cells. These know how to parse expressions representing the value or formula that they should hold. As they parse they create instructions in the simple assembly language discussed in SimpleCPU and store instruction objects in their own program: a vector. Each cell has its own program (or a simple value). Cells also know how to evaluate themselves, by sequentially executing each of the instructions in their program if necessary. The cells share an evaluation stack (static member) for this purpose.
The instruction objects know how to execute themselves using a stack. The language is powerful enough to handle expressions (parenthesized or not, with proper precedence of operators).
The spreadsheet was purposely made a bit awkward to use. (This could be improved by the students).
A cell command is typed into the text field at the bottom of the applet. It has the form
<cellName> = <expression> ;
The semicolon is required. A cell name consists of a letter (either case) followed by some digits where the letter is a legal column name and the digits give a valid row number. As currently set up there are five columns and 10 rows. (The maximum number of columns is 26). Here are two legal commands.
d7 := 5;
a3 := 2 *(d7 + 1);
After each command is entered you need to hit the Accept button. This causes the command to be parsed and one cell updated, but the sheet is not updated or evaluated otherwise. When all commands have been entered, you hit the Evaluate button to see the effect of the commands. There is also a clear button to clear the text input area.
There are also two range function sum and prod. They apply to a range of cells. The following command adds all the cells in a rectangular block.
A9 = sum(B1..C4);