Gee, Brian, I wish I had seen your question sooner. Since it’s pretty much my
“invention” (for better or worse), I might be able to help.
Inserted: The shortest possible
explanation I can make is that if
normal execution is like throwing a
ball in the air and catching it, then
differential execution is like
juggling.
@windfinder’s explanation is different from mine, and that’s OK. This technique is not easy to wrap one’s head around, and it’s taken me some 20 years (off and on) to find explanations that work. Let me give it another shot here:
- What is it?
We all understand the simple idea of a computer stepping along through a program, taking conditional branches based on the input data, and doing things. (Assume we are dealing only with simple structured goto-less, return-less code.) That code contains sequences of statements, basic structured conditionals, simple loops, and subroutine calls. (Forget about functions returning values for now.)
Now imagine two computers executing that same code in lock-step with each other, and able to compare notes. Computer 1 runs with input data A, and Computer 2 runs with input data B. They run step-by-step side by side. If they come to a conditional statement like IF(test) …. ENDIF, and if they have a difference of opinion on whether the test is true, then the one who says the test if false skips to the ENDIF and waits around for its sister to catch up. (This is why the code is structured, so we know the sister will eventually get to the ENDIF.)
Since the two computers can talk to each other, they can compare notes and give a detailed explanation of how the two sets of input data, and execution histories, are different.
Of course, in differential execution (DE) it is done with one computer, simulating two.
NOW, suppose you only have one set of input data, but you want to see how it has changed from time 1 to time 2. Suppose the program you’re executing is a serializer/deserializer. As you execute, you both serialize (write out) the current data and deserialize (read in) the past data (which was written the last time you did this). Now you can easily see what the differences are between what the data was last time, and what it is this time.
The file you are writing to, and the old file you are reading from, taken together constitute a queue or FIFO (first-in-first-out), but that’s not a very deep concept.
- What is it good for?
It occurred to me while I was working on a graphics project, where the user could construct little display-processor routines called “symbols” that could be assembled into larger routines to paint things like diagrams of pipes, tanks, valves, stuff like that. We wanted to have the diagrams be “dynamic” in the sense that they could incrementally update themselves without having to redraw the entire diagram. (The hardware was slow by today’s standards.) I realized that (for example) a routine to draw a bar of a bar-chart could remember its old height and just incrementally update itself.
This sounds like OOP, doesn’t it? However, rather than “make” an “object”, I could take advantage of the predictability of the execution sequence of the diagram procedure. I could write the bar’s height in a sequential byte-stream. Then to update the image, I could just run the procedure in a mode where it sequentially reads its old parameters while it writes the new parameters so as to be ready for the next update pass.
This seems stupidly obvious and would seem to break as soon as the procedure contains a conditional, because then the new stream and the old stream would get out of sync. But then it dawned on me that if they also serialized the boolean value of the conditional test, they could get back in sync.
It took a while to convince myself, and then to prove, that this would always work, provided a simple rule (the “erase mode rule”) is followed.
The net result is that the user could design these “dynamic symbols” and assemble them into larger diagrams, without ever having to worry about how they would dynamically update, no matter how complex or structurally variable the display would be.
In those days, I did have to worry about interference between visual objects, so that erasing one would not damage others. However, now I use the technique with Windows controls, and I let Windows take care of rendering issues.
So what does it achieve? It means I can build a dialog by writing a procedure to paint the controls, and I do not have to worry about actually remembering the control objects or dealing with incrementally updating them, or making them appear/disappear/move as conditions warrant. The result is much smaller and simpler dialog source code, by about an order of magnitude, and things like dynamic layout or altering the number of controls or having arrays or grids of controls are trivial. In addition, a control such as an Edit field can be trivially bound to the application data it is editing, and it will always be provably correct, and I never have to deal with its events. Putting in an edit field for an application string variable is a one-line edit.
- Why is it hard to understand?
What I have found hardest to explain is that it requires thinking differently about software. Programmers are so firmly wedded to the object-action view of software that they want to know what are the objects, what are the classes, how do they “build” the display, and how do they handle the events, that it takes a cherry bomb to blast them out of it. What I try to convey is that what really matters is what do you need to say? Imagine you are building a domain-specific language (DSL) where all you need to do is tell it “I want to edit variable A here, variable B there, and variable C down there” and it would magically take care of it for you. For example, in Win32 there is this “resource language” for defining dialogs. It is a perfectly good DSL, except it doesn’t go far enough. It doesn’t “live in” the main procedural language, or handle events for you, or contain loops/conditionals/subroutines. But it means well, and Dynamic Dialogs tries to finish the job.
So, the different mode of thinking is: to write a program, you first find (or invent) an appropriate DSL, and code as much of your program in that as possible. Let it deal with all the objects and actions that only exist for implementation’s sake.
If you want to really understand differential execution and use it, there are a couple of tricky issues that can trip you up. I once coded it in Lisp macros, where these tricky bits could be handled for you, but in “normal” languages it requires some programmer discipline to avoid the pitfalls.
Sorry to be so long-winded. If I haven’t made sense, I’d appreciate it if you’d point it out and I can try and fix it.
Added:
In Java Swing, there is an example program called TextInputDemo. It is a static dialog, taking 270 lines (not counting the list of 50 states). In Dynamic Dialogs (in MFC) it is about 60 lines:
#define NSTATE (sizeof(states)/sizeof(states[0]))
CString sStreet;
CString sCity;
int iState;
CString sZip;
CString sWholeAddress;
void SetAddress(){
CString sTemp = states[iState];
int len = sTemp.GetLength();
sWholeAddress.Format("%s\r\n%s %s %s", sStreet, sCity, sTemp.Mid(len-3, 2), sZip);
}
void ClearAddress(){
sWholeAddress = sStreet = sCity = sZip = "";
}
void CDDDemoDlg::deContentsTextInputDemo(){
int gy0 = P(gy);
P(www = Width()*2/3);
deStartHorizontal();
deStatic(100, 20, "Street Address:");
deEdit(www - 100, 20, &sStreet);
deEndHorizontal(20);
deStartHorizontal();
deStatic(100, 20, "City:");
deEdit(www - 100, 20, &sCity);
deEndHorizontal(20);
deStartHorizontal();
deStatic(100, 20, "State:");
deStatic(www - 100 - 20 - 20, 20, states[iState]);
if (deButton(20, 20, "<")){
iState = (iState+NSTATE - 1) % NSTATE;
DD_THROW;
}
if (deButton(20, 20, ">")){
iState = (iState+NSTATE + 1) % NSTATE;
DD_THROW;
}
deEndHorizontal(20);
deStartHorizontal();
deStatic(100, 20, "Zip:");
deEdit(www - 100, 20, &sZip);
deEndHorizontal(20);
deStartHorizontal();
P(gx += 100);
if (deButton((www-100)/2, 20, "Set Address")){
SetAddress();
DD_THROW;
}
if (deButton((www-100)/2, 20, "Clear Address")){
ClearAddress();
DD_THROW;
}
deEndHorizontal(20);
P((gx = www, gy = gy0));
deStatic(P(Width() - gx), 20*5, (sWholeAddress != "" ? sWholeAddress : "No address set."));
}
Added:
Here’s example code to edit an array of hospital patients in about 40 lines of code. Lines 1-6 define the “database”. Lines 10-23 define the overall contents of the UI. Lines 30-48 define the controls for editing a single patient’s record. Note the form of the program takes almost no notice of events in time, as if all it had to do was create the display once. Then, if subjects are added or removed or other structural changes take place, it is simply re-executed, as if it were being re-created from scratch, except that DE causes incremental update to take place instead. The advantage is that you the programmer do not have to give any attention or write any code to make the incremental updates of the UI happen, and they are guaranteed correct. It might seem that this re-execution would be a performance problem, but it is not, since updating controls that do not need to be changed takes on the order of tens of nanoseconds.
1 class Patient {public:
2 String name;
3 double age;
4 bool smoker; // smoker only relevant if age >= 50
5 };
6 vector< Patient* > patients;
10 void deContents(){ int i;
11 // First, have a label
12 deLabel(200, 20, “Patient name, age, smoker:”);
13 // For each patient, have a row of controls
14 FOR(i=0, i<patients.Count(), i++)
15 deEditOnePatient( P( patients[i] ) );
16 END
17 // Have a button to add a patient
18 if (deButton(50, 20, “Add”)){
19 // When the button is clicked add the patient
20 patients.Add(new Patient);
21 DD_THROW;
22 }
23 }
30 void deEditOnePatient(Patient* p){
31 // Determine field widths
32 int w = (Width()-50)/3;
33 // Controls are laid out horizontally
34 deStartHorizontal();
35 // Have a button to remove this patient
36 if (deButton(50, 20, “Remove”)){
37 patients.Remove(p);
37 DD_THROW;
39 }
40 // Edit fields for name and age
41 deEdit(w, 20, P(&p->name));
42 deEdit(w, 20, P(&p->age));
43 // If age >= 50 have a checkbox for smoker boolean
44 IF(p->age >= 50)
45 deCheckBox(w, 20, “Smoker?”, P(&p->smoker));
46 END
47 deEndHorizontal(20);
48 }
Added: Brian asked a good question, and I thought the answer belonged in the main text here:
@Mike: I’m not clear on what the “if (deButton(50, 20, “Add”)){” statement is actually doing. What does the deButton function do? Also, are your FOR/END loops using some sort of macro or something? – Brian.
@Brian: Yes, the FOR/END and IF statements are macros. The SourceForge project has a complete implementation. deButton maintains a button control. When any user input action takes place, the code is run in “control event” mode, in which deButton detects that it was pressed and signifies that it was pressed by returning TRUE. Thus, the “if(deButton(…)){… action code …} is a way of attaching action code to the button, without having to create a closure or write an event handler. The DD_THROW is a way of terminating the pass when the action is taken because the action may have modified application data, so it is invalid to continue the “control event” pass through the routine. If you compare this to writing event handlers, it saves you writing those, and it lets you have any number of controls.
Added: Sorry, I should explain what I mean by the word “maintains”. When the procedure is first executed (in SHOW mode), deButton creates a button control and remembers its id in the FIFO. On subsequent passes (in UPDATE mode), deButton gets the id from the FIFO, modifies it if necessary, and puts it back in the FIFO. In ERASE mode, it reads it from the FIFO, destroys it, and does not put it back, thereby “garbage collecting” it. So the deButton call manages the entire lifetime of the control, keeping it in agreement with application data, which is why I say it “maintains” it.
The fourth mode is EVENT (or CONTROL). When the user types a character or clicks a button, that event is caught and recorded, and then the deContents procedure is executed in EVENT mode. deButton gets the id of its button control from the FIFO and askes if this is the control that was clicked. If it was, it returns TRUE so the action code can be executed. If not, it just returns FALSE. On the other hand, deEdit(..., &myStringVar) detects if the event was meant for it, and if so passes it to the edit control, and then copies the contents of the edit control to myStringVar. Between this and normal UPDATE processing, myStringVar always equals the contents of the edit control. That is how “binding” is done. The same idea applies to scroll bars, list boxes, combo boxes, any kind of control that lets you edit application data.
Here’s a link to my Wikipedia edit: http://en.wikipedia.org/wiki/User:MikeDunlavey/Difex_Article