Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Advanced Bug

Callbacks, state machines and cyclic dependencies (former spaghetti thread)

This topic is 5657 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Sometimes I'm really amazed by how programming changed during the last 10 years. New technologies appear so rapidly that I can't keep track of what is going on. Everything has fancy, click-here-and-I'll-do-the-rest interface. Everybody seems to be obsessed with writing millions of lines of code for the next version of some all-in-one, we've-got-all-you-need software. However, I still believe that programming is not about writing fancy, click-once-and-forget, idiot-oriented, idiot-friendly thingies. Sure, they all are necessary, and GUI's can tremendously increase productivity, but there still must exist some simple, reliable, robust underlying low-level infrastructure. And what I'm afraid is - what will happen if programmers will start to apply the principles of high-level user interface programming to low-level system programming. Current Java SDK come with Swing library - a complete set of GUI components completely written in Java heavily using OOP. While the offered functionality is impressive, the principle on which it is based are rather questionable. I started using it by writing a simple text file editor and immediately run into serious problem. My program has two GUI components - a list box for filenames and a text box for editing the contents of file. When user clicked on another filname, changes made to previous file were automatically saved. Selecting the filaname and hitting the DELETE key resulted into deleting the file. At first I wrote the DELETE key handler this way: FILE file = new File(currentDirectory, fileList.getSelectedItem()); file.delete(); fileList.removeItem(fileList.getSelectedIndex()); Unfortunately this doesn't work. The removeItem method removes the currently selected item, resets the selection and immediately calls my selection change handler, which in turn saves the contents of the text box into the current file, which just was deleted, effectively recreating it. Of course this concrete problem can easily be fixed by changing the order of operations in the DELETE key handler. However, imagine a program with dozen of GUI components and multiple levels of such nested callbacks, and you'll see the modern equivalent of the spaghetti code. What actually happens, in my opinion, is that we hava a state machine which tries to do multiple state transitions simultaneously. There are two transitions - the SelectionChanged transition and DeleteFile transition. But writing the program this way we get the following sequence of operations: Initiate the DeleteFile transition - Initiate the SelectionChaged transition BEFORE COMPLETING THE SeletionChanged TRANSITION - after finishing the SelectionChanged transition complete the rest of the DeleteFile transition. I can think of only two possible solutions - a) never execute a callback as a result of some function call, or b) postpone the execution of the secondary callback until the first callback returns. I can formulate it this way: Single Callback Rule If module M1 calls callback C1 in module M2, and module M2 calls function F in module M1 during executing the callback C1, and module M1 must call callback C2 in module M2 as a result of calling function F, then module M1 should only call callback C2 AFTER the callback C1 returns. In other words - callbacks shouldn't be nested. This way program only must ensure that it enters consistent state before returning from callback, and no measures should be taken to allow the program to handle SECONDARY callbacks DURING transition from one state to another. So what's your opinion - is this rule right or wrong, is it universal or not? Also it appears that some OO programmers think that there's no need for the concept of callback, since it is implemented as virtual function and as such is not different from other functions. Are they wrong, and how this Single Callback rule applies to OOP? [edited by - Advanced Bug on April 1, 2003 3:22:02 AM]

Share this post


Link to post
Share on other sites
Advertisement
Not this again!
You'll get yourself banned at this rate.
Callbacks are used everywhere. Win32 is designed entirely around the idea of callbacks - the WindowProc! Even Win32 controls use callbacks - via the WM_COMMAND message or WM_NOTIFY. Swing isn't doing anything new or unusual. Infact, Swing is better than Win32 since it is totally consistant. In Win32 a selected item change in a list box only notifies the parent if it was initiated via a mouse click / keyboard input; whereas a treeview control will notify the parent when the current selection changes regardless of the source of the change.
I wrote a text editor in Swing that functions exactly like your one (but it had a tree view as well to browse folders). It took a day and a half having never used Swing before and only using on-line references (Sun's website). In total it came to about 600 lines of code (including comments). I started doing the same thing in Win32, got to around 1000 lines of code for a fraction of the functionality.
There's nothing wrong with Swing. Or notifications / callbacks. Billions of lines of code have been written using those ideas.
There's something wrong with you (i.e. you're not working with the system, you're working against it).

Skizz

[edited by - Skizz on March 31, 2003 7:28:41 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Skizz
Callbacks are used everywhere. Win32 is designed entirely around the idea of callbacks - the WindowProc! Even Win32 controls use callbacks - via the WM_COMMAND message or WM_NOTIFY. Swing isn''t doing anything new or unusual.


What I''m saying is not that callbacks are wrong. What I''m saying is that NESTED callbacks might be wrong.

That is, Swing calls my function, my function calls Swing, Swing IMMEDIATELY calls another my function, which now has to deal with the half-completed results of the first function.

At the nesting level of two, it can be managed, but what will happen if you get four or five nested callbacks?

Share this post


Link to post
Share on other sites
quote:
Advanced Bug
So what''s your opinion - is this rule right or wrong, is it universal or not? Also it appears that some OO programmers think that there''s no need for the concept of callback, since it is implemented as virtual function and as such is not different from other functions. Are they wrong, and how this Single Callback rule applies to OOP?


Whether it''s a function pointer or a virtual function, a slot&signal, or first-class functions, they''re all callback mechanisms. What makes it a call-back is what you do with it.

I''m not certain how to solve the problem you face. I have the same problem with a VBA Excel add-in. "Luckily" Delphi has the exact same problem (the VCL actually, so it''s a problem in C++ Builder too!) so my boss and coworkers are well aware of it.

We came up with two options. First, write a COM-AddIn using Visual C++ using MFC and/or the ATL/WTL. Second, using a timer-tick to poll the UI elements and update the screen every 100ms or so. And the second option has its own difficulties (say the user is editing the field that I update, I need to not update it, or at least not interrupt the user). The second option also completely defeats event-driven programming.

There''s a third possibility, but I''m not certain how easy it will be to implement. Do you derive from widget in swing, or attach event handlers? If you attach handlers, it gets even harder, because all the handlers need to have access to common information about the widget. So if you can''t derive from the widget, you need to make a hash-map from the widget to the controller information. If you derive, then you wedge the controller in when you derived class (except there’s no multiple implementation inheritance, so you have to emulate MI using aggregation). The controller would "know" when you are updating it from code, and would filter the event notifications (not call the second level handler when you update it from code). In order for the filter to know when you are updating the widget from code, you have to overtake the functions that change it and set some crappy flag. Then in controller’s event handler, you don’t call your real events handlers if the flag is set. Finally, unset the flag when the overtaken update routines are about to exit. It''s so much work and trouble just to make it work correctly, it just doesn''t seem worth it.

quote:

What actually happens, in my opinion, is that we [have] a state machine which tries to do multiple state transitions simultaneously. There are two transitions - the SelectionChanged transition and DeleteFile transition. But writing the program this way we get the following sequence of operations:


This is an accurate description of the resultant problem due to the equivocation of events problem in the widget kit. The problem would be easily solved by if there were two events, a UserChangedMe, and a CodeChangedMe handler. Then it would be simple since you could ignore the CodeChangedMe events.

...
quote:
Original post by Skizz
Not this again!
You''ll get yourself banned at this rate.


Not banned, but I would prefer better topic descriptions.

quote:

Callbacks are used everywhere. Win32 is designed entirely around the idea of callbacks - the WindowProc! Even Win32 controls use callbacks - via the WM_COMMAND message or WM_NOTIFY. Swing isn''t doing anything new or unusual. In fact, Swing is better than Win32 since it is totally [consistent].


I''d prefer something that works over something that is consistent, and something that both works and is consistent over both of those. Win32 may not be perfectly consistent, but that was preferable to breaking old Win16 code. Besides that, both MFC & the ATL/WTL paper-over the vast majority of the inconsistencies.
And what good is a consistent widget kit, if it just pushes inconsistency into my code?
Now we handle event handlers that need to do two different things, depending upon information that they do not tell us (but must know).

Win32 handles those call-backs significantly different. The only time you receive notifications is when the user actually does something (or if you specifically emulate user input events). Swing does do something unusual. It automatically triggers an event when you change the widget from code, and invokes the same event handler as though the user changed it . This is not conducive to how interactive UIs operate. In the last discussion I described the problem, and showed that it results in an O(n!) increase of redundant event notifications as UI elements are inter-linked. It’s a nightmare to manage.

Again, try to write a program that works like Windows Calc (and exactly like Windows Calc), and the problem will be obvious. Keep in mind that calc is extremely simple, yet it is a nuance to writing using the VCL, Swing, VB, or WinForms, but with the ATL, the WTL, or MFC it is straight-forward.

I''d be interested in hearing how wxWindows, Tcl, etc... handle event notifications if anyone is familiar with other widget kits. In particular, if you know for a fact that a certain widget kit generates changed events due to user code.

Share this post


Link to post
Share on other sites
"Besides that, both MFC & the ATL/WTL paper-over the vast majority of the inconsistencies."

And introduce their own, as well as relying rather too heavily on compile time macros which make changing behaviour at runtime more painful than it should be - one major advantage of the Swing toolkit, everything can be reassigned and redirected on-the-fly with a minimum of hastle and maximum of consistancy.

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
This is an accurate description of the resultant problem due to the equivocation of events problem in the widget kit. The problem would be easily solved by if there were two events, a UserChangedMe, and a CodeChangedMe handler. Then it would be simple since you could ignore the CodeChangedMe events.


Yes, this is the conclusion that we came to in the previous discussion. And I did rewrite the program in C++ using raw Windows API.

However, now I''m trying to generalize the problem, and potentially came up with some universal design principles that could eliminate such problems (or at least allow predicting them). In my opinion, the problem is important enough, because the implementation of objects in C++, Java and C# actually encourages such design, and the problem applies to any event-driven program.


BTW, I just came up with another description of this problem. Callbacks introduce CYCLIC DEPENDENCY. My program depends on the library, which displays the user interface, library depends on my program, which handles the user actions. While callbacks are never called as the result of library calls, there''s no problem, because execution flow never jumps back and forth between them. But if callbacks can be called as the result of library calls, we have typical cyclic dependency problem.

Such description, in my opinion, hints us that the UNIVERSAL solution to this problem could be introducing another component, which breaks the dependency cycle, and is used for communications between the program and library - some kind of a MESSAGE QUEUE.

That leads to another formulation of the Single Callback Rule - EVENT-DRIVEN PROGRAMS MUST USE MESSAGE QUEUES.

(...and implementing them using direct virtual function calls are wrong).


In the context of my file editor that means that my DELETE key handler would have a chance to complete all actions necessary for deleting the file (including resetting the contents of the textBox and setting the currentFile variable to null) before selection change handler is called.

However it is still unclear how this all applies to the problem of initializing mutually dependant controls (for unit converting program, for example). It appears that this problem really requires some specific solution (probably we must specify the order of control initialization, and provide some mechanism that provents the initialization from going in circles).

Share this post


Link to post
Share on other sites
After a quick thinking about your problem, it seems to *me* that there may be a design flaw : it seems that you let the handler implement the functionnality while the handler doesn''t take care about what is going on.

Here is your requirement :
- You have a list combo box that tells the user which file is opened. Changing the selection open another file according to the selected item. A press to the delete key delete the current file and remove it from the file list. Saving is automatic.

- A text box display the current opened file.

Here is what *I* would do :
- I have an object acting as a controler that knows : which file is currently opened, how to open a file, how to delete a file. The implementation of "open a file" checks wether a file is currently opened, and save it if there is one. The implementation of "delete the current file" deletes the current files and updates the controler state so that for it there is no opened file

Now, when the user press delete, the delete handler ask the controller to delete the file, then the change selection listener ask the controller to open an other file.

After the completion of the delete, the controller does not have any opened file to maintain, thus don''t save anything : the problem simply does not exist any more.

Morality : have a good controler ! then you can have any number of nested call-back

----
David Sporn AKA Sporniket

Share this post


Link to post
Share on other sites
quote:
Original post by davidsporn
The implementation of "delete the current file" deletes the current files and updates the controler state so that for it there is no opened file

After the completion of the delete , the controller does not have any opened file to maintain, thus don''t save anything...


If the selection change handler would be called after the completion of the delete it would be easy. The problem is that the seletion change handler will be called during the delete method, at the point when it will delete the list box item. As a result the delete method will depend in an obscure way on the order of the operations.

Share this post


Link to post
Share on other sites
quote:
Original post by davidsporn
The implementation of "delete the current file" deletes the current files and updates the controler state so that for it there is no opened file

After the completion of the delete , the controller does not have any opened file to maintain, thus don''t save anything...


quote:
Original post by Advanced Bug
If the selection change handler would be called after the completion of the delete it would be easy. The problem is that the seletion change handler will be called during the delete method, at the point when it will delete the list box item. As a result the delete method will depend in an obscure way on the order of the operations.


Ok, let''s have a bit of code to make things clear...

The controler looks like that :

  
class Editor{
File CurrentFile_ ;

//ctor, other stuff,...


//open a file

public void openFile(String fileName)
{
if (null != CurrentFile_) saveCurrentFile() ; //saveCurrentFile defined elsewhere in the class

CurrentFile_ = new File(fileName) ;

//open the file and display it in the text box

//...

}

//delete the file

public void deleteCurrentFile()
{
if (null != CurrentFile_) CurrentFile_.delete() ;
CurrentFile_ = null ;
}
}


Now, here is the implementation of the delete key handler (let''s name the controler instance be "controler")


  
public void XXX() //dont remember the function declaration

{
controler.deleteCurrentFile();
fileList.removeItem(fileList.getSelectedIndex());
}


Now the change selection handler.

  
public void XXX() //dont remember the function declaration

{
controler.openFile(fileList.getSelectedIndex()); }



So, did you see what happen ? When the item is removed, firing the change selection callback, the controller has *already* deleted the file and more importantly, cleared it''s CurrentFile_ field, thus preventing an unwanted save.



----
David Sporn AKA Sporniket

Share this post


Link to post
Share on other sites
quote:
Original post by davidsporn

public void XXX()
{
controler.deleteCurrentFile();
fileList.removeItem(fileList.getSelectedIndex());
}



This is what I meant when I said: "depends in an obscure way on the order of operations". It is absolutely not obvious that you must remove the file BEFORE removing the correspoding listbox item.

Sure it solves this concrete problem. But there''s no way to predict where similar problem will show up next time. In general, you should be ready to handle an unexpected callback at any point when you call some library function.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!