The XForms Computation Engine: Rationale, Theory and Implementation Experience

J. Boyer (Canada) and M. Honkala (Finland)


XForms, XFDL, recalculation,topological sorting, depth-first search.


This paper reports on successful efforts to change the W3C's next-generation Web forms working draft specification, XForms, from a computation engine architecture based on form-author-specified recalculation order to an automated determination of recalculation order based on optimal graph algorithms. We trace the historical beginnings of these algorithms from Knuth and Tarjan to their first known applications in electronic spreadsheets and XFDL (the first XML-based electronic forms vocabulary). The algorithms are then presented in the context of a detailed example. Also included are the implementation details that were necessary to add the new XForms computation engine to the open-source X-Smiles web browser. When compared to an implementation of the earlier approach, running times were reduced from seconds to instantaneity on forms typical of those being developed for complex business processes. Finally, the paper discusses some of the technical challenges encountered when rationalizing the graph algorithms with the general properties of XPath and with a specific implementation of XPath.

Important Links:

Go Back