Version: 2021-04-07
--- >Version: 2021-09-09
33c34 < applications for the web and elsewhere. One of the central aspects of XForms is --- > applications for the web and elsewhere. One of its central aspects is 35,39c36,40 < changes or is changed, its related values specified in invariants get updated < automatically. This is much like how spreadsheets work, though more general. A < major advantage of this approach is that much administrative detail is taken < out of the hands of the programmer, and done automatically: the programmer < specifies the relationships, and the computer does the work. --- > changes or is changed, its related values specified in the invariants get > updated automatically. This is much like how spreadsheets work, though more > general. A major advantage of this approach is that much administrative detail > is taken out of the hands of the programmer, and done automatically: the > programmer specifies the relationships, and the computer does the work. 53,58c54,69 <It was Dijkstra in his seminal book "A Discipline of Programming" [ It was Dijkstra in his seminal book A Discipline of Programming [while statements.
To get a taste for why and how this is, let us briefly examine the < mechanisms used for implementing the map example.
--- >The essential abstraction of the application is that there is a < two-dimensional position of a location in the world, and a value that < represents the magnification or zoom value required; the application then < retains a display of a map centred at that location.
--- >To get a taste for why and how invariants are used, let us briefly examine > the mechanisms used for implementing the map example.
> >The highest-level abstraction of the application is that there is a
> two-dimensional position of a location in the world, (x, y), and a
> value that represents the magnification or zoom value required; the application
> then retains a display of a map centred at that location.
src="http://tile.openstreetmap.org/0/0/0.png" />
< 
/> />
>
> />
zoom changes then
< scale will be updated. If scale or
---
> invariants – statements of required equality: if zoom changes
> then scale will be updated. If scale or
169c184
< The XForms mechanism to update values when there are changes is a fairly < straightforward ordered-graph based dependency algorithm [update1, update2], ordered since < XForms disallows circular dependencies; static analysis can be used for large < parts, though dynamic dependencies are also permitted. Updates are triggered by < changes to dependent values, and updates are then ordered along the dependency < chain and applied.
--- >The advantages of the invariant approach are many and include that you can > far more easily specify the computational intent of a piece of program, and so > the computational intent is therefore much more obvious to the reader of the > code; the computer does more of the (administrative) work, saving the > programmer time; the resulting code is much shorter (typically a quarter of the > length); and production time is greatly reduced: reports of applications > needing only 1/10th of the time have been widespread, but some even more than > that.
> >The XForms invariant mechanism uses a fairly straightforward ordered-graph > based dependency algorithm [update1, href="#update2">update2], ordered since XForms disallows circular > dependencies; static analysis can be used for large parts, though dynamic > dependencies are also permitted. Updates are triggered by changes to dependent > values, and updates are then ordered along the dependency chain and applied. > For example, the graph of dependencies of the map application fragment above > looks like this:
182,184c209,211 < all invariants are up to date. Whenever a change happens, whether by the user, < or by the system as a response to an event, an update occurs, in order < to return the system to stasis. --- > all invariants are up-to-date. Whenever a change occurs, whether caused by the > user, or by the system as a response to an event, an update occurs, in > order to return the system to stasis. 188,190c215,217 <One of the reasons that the XForms dependency graph is so useful is that if > a value changes, only dependent values need be recalculated. Initially (at > least in principle), all values are calculated, but after that, changes only > cause a subset of the values to be updated. Later we will be referring to the > update efficiency, how much work has to be done to restore an > invariant.
> ><action ev:event="xforms-ready"> > <setvalue ref="today" value="local-dateTime()"/> > </action>205,210c243,247 <
The hooks use the XForms event mechanism [events], < that allows different classes of processing events to be caught and responded < to. The events of interest here are twofold: when the content of an element or < attribute changes, and structural changes to an instance when items are < inserted or deleted. Listeners can listen for events that report these changes < and respond in some way. We will see examples of these shortly.
--- >This uses the XForms event mechanism [events], that
> allows different classes of processing events to be caught and responded to,
> such as xforms-ready in the example above.
As an example of such a structural change, suppose we have an array of --- >
The events of interest here are twofold:
>Handlers can listen for events that report these changes and respond in some > way.
> >As a simple example of such a structural change, suppose we have an array of 220c267 < <data size="10" xmlns=""> --- > <data size="10" xmlns=""> 238c285 <
<action ev:event="xforms-value-changed"> --- ><action ev:event="xforms-value-changed"> 271c318 <Structural Invariants
--- >Structural Invariants
273,286c320,335 <The question arises, to what extent, and how, could invariants that affect < structure be introduced into the invariant mechanism, without having to resort < to hooks?
< <The first thing to note is that with the existing XForms invariant bindings, < it doesn't state the invariant, but only how to restore it, and the <
< <calculateattribute contains both the signals that the invariant < needs restoring, as well as the method to restore it.On the other hand, in the two examples above, the signal, the value < changing, is separate from the restore mechanism, the inserts and deletes. This < is possibly a clue to how to integrate the mechanism. Here is a strawman < suggestion:
<<structure ref="value" requires="count(value) = @size"> --- >These examples show that you can use events in order to maintain your own > invariants. The question arises, to what extent, and how, could invariants that > affect structure be introduced into the invariant mechanism, without having to > resort to events?
> >The first thing to note is that the existing XForms invariant bindings don't > state the invariant, but only how to restore it, and that the >
>calculateattribute contains both the signals that indicate that > the invariant needs restoring, as well as the method to restore it.<bind ref="tileX" calculate="floor(../worldX div ../scale)"/>> >On the other hand, in the two structure examples above, the signal (the > value changing) is separate from the restore mechanism (the inserts and > deletes). This is possibly a clue to how the mechanism could be integrated. > Here is a strawman suggestion:
><structure requires="count(value) = @size"> 291,293c340,342 <The boolean
--- >requiresattribute then becomes part of the < dependency algorithm, and the body of thestructureelement < becomes part of the update mechanism.This allows the boolean
295c344 <requiresattribute to become part of > the dependency algorithm, and the body of thestructureelement to > become part of the update mechanism, namely the rebuild part.Requirements
--- >Requirements
297c346 <But while this solves a simple case of structural invariants, there are more --- >
While this solves a simple case of structural invariants, there are more 304,306c353,361 <
But you would also like to say this structure contains the data that < matches the search string. Again a strawman:
<<structure ref="subset" calculate="data[contains(., instance('search')/q)]"/>--- >But apart from repeating controls over a subset of data, you would also like > to be able to say this structure contains the data that matches the search > string. Again a strawman:
><structure ref="subset" > calculate="data[contains(., instance('search')/q)]"/>> >or alternatively
><bind ref="subset" > structure="data[contains(., instance('search')/q)]"/>313,315c368,370 < requirements analysis is "what would be useful to be able to do?". We shouldn't < prematurely optimise by saying it would be inefficient, thus not a good < solution; we should ask what we want to do, and then later work out how to --- > requirements analysis is "what would be useful to be able to do?". We > shouldn't prematurely optimise by saying it would be inefficient, thus not a > good solution; we should ask what we want to do, and then later work out how to 323,325c378,380 < war waged after that about whether recursion was really needed, with whole < books on the subject. Today it would be unthinkable for a programming language < not to support recursion. --- > war waged after that about whether recursion was really needed, and whole books > were written on the subject. Today it would be unthinkable for programming > languages not to support recursion. 337,340c392,403 <Other useful structure invariance functions apart from filter, are < map and reduce, and sorting. These specify very high-level < relationships between structures, but make specifying algorithmic intent very < easy.
--- >Higher-level functions
> >While this paper isn't the place to enumerate all possible data structures > and the invariants that might be applied to them, it is useful to explore some > general invariants over lists, since dynamic data structures using lists are so > inherent to programming, and since they form the basis of so many other > structures.
> >Useful structural invariance functions apart from filter, are map, > reduce (or fold), and sorting. These specify very high-level > relationships between structures, thus making the specification of algorithmic > intent very easy.
343c406 < since something like --- > since an invariant like 349,350c412,415 <It also has some simple versions of reduce, such as
--- >sum(), but < not a generalised one.It also has some specific versions of reduce, such as
352c417 <sum(), > but not a generalised one. However, the most-recent version of XPath has added > these higher-level functions, which allows them to be used in new versions of > XForms.Implementation
--- >Implementation
359,361c424,428 < mechanism. For instance, a map is just a sequence of sub-expressions each < calculating one function application for each element of the sequence of input < values (along with a structural guard on the size). --- > mechanism. > >For instance, a map is just a sequence of sub-expressions each calculating > one function application for each element of the sequence of input values > (along with a structural guard on the size).
365,372c432,433 <Similarly, a reduce can be seen as a tree of reductions. In both these < cases, if a value changes in the middle of the tree or sequence, the other < parts of the assemblage don't have to be recalculated.
< <In this way, you can regard structural invariants as just a higher-level < form of invariant, ones whose purpose are to manage the collection of < lower-level simple invariants; the rebuild phase of the XForms update < mechanism can be treated as a higher-level version of recalculate.
--- >Note that this has an update efficiency of O(1): if a value changes, only > its dependent value needs to be updated.
374,375c435,482 <A description of such an implementation can be found in [views].
--- >Similarly, a reduce can be seen as a tree of reductions. XPath specifies two > reduction functions, fold-left and fold-right. Unfortunately, > at least for XForms, these are computational very specific: you start the > reduction either from the left or the right. However many typical reductions, > such as sum, product, and concatenate, are > directionally neutral, since their underlying dyadic operators (namely +, ×, > and string-join) are associative:
> >>> >a+(b+c) = (a+b)+c
>and we can take advantage of this.
> >For instance, if we regard a fold-left as a graph of dependent > calculations, it would need to be implemented like this:
> >> >
which has an update complexity of O(n). On the other hand, a directionally > impartial fold could be implemented as
> >> >
with an update complexity of only O(log(n)). (Note that both versions have a > space complexity of O(n).)
> >This is a big difference for large lists: while doubling the size of the > list doubles the number of computations for O(n), it only adds one single extra > computation for O(log(n)). Put another way, it involves 100-fold less > computations for a list of length 1000 (10 calculations versus 1000), and 50 > thousand-fold less for a list of length one million (20 calculations versus 1 > million).
> >This is because if a value changes in the middle of the tree or sequence, > the other parts of the assemblage don't have to be recalculated.
> >The upshot of this is that you can regard structural invariants as just a > higher-level form of invariant, ones whose purpose is to manage the collection > of lower-level simple invariants; the rebuild phase of the XForms > update mechanism can be treated as a higher-level version of > recalculate.
> >> >
/>
A description of a similar implementation for a different system can be > found in [views].
388a496,499 >The purpose of this paper has been to initiate discussion on generalising > the XForms invariant mechanism to these higher-level invariants, as input for a > future version of XForms.
> 391,392c502,503 <[xf1] John M. Boyer (ed.), XForms 1.1, W3C, 2009, < https://www.w3.org/TR/xforms11/
--- >[xf1] John M. Boyer (ed.), XForms 1.1, W3C, 2009, href="https://www.w3.org/TR/xforms11/">https://www.w3.org/TR/xforms11/
395c506,507 < https://www.w3.org/community/xformsusers/wiki/XForms_2.0 --- > href="https://www.w3.org/community/xformsusers/wiki/XForms_2.0">https://www.w3.org/community/xformsusers/wiki/XForms_2.0 398,399c510,512 < XML.com, 2018, https://www.xml.com/articles/2018/11/27/introduction-xforms/ < . --- > XML.com, 2018, href="https://www.xml.com/articles/2018/11/27/introduction-xforms/">https://www.xml.com/articles/2018/11/27/introduction-xforms/ > . 401,402c514,515 <[update1] Model Processing, in [xf2] < https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Model_Processing
--- >[update1] Model Processing, in [xf2] href="https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Model_Processing">https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Model_Processing
404,405c517,518 <[update2] Recalculation Sequence Algorithm, in < https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Recalculation_Sequence_Algorithm
--- >[update2] Recalculation Sequence Algorithm, in href="https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Recalculation_Sequence_Algorithm">https://www.w3.org/community/xformsusers/wiki/XForms_2.0#Recalculation_Sequence_Algorithm
411,412c524,525 < 2014, pp 96-102, ISBN 978-0-9926471-1-7, < https://xmllondon.com/2014/xmllondon-2014-proceedings.pdf --- > 2014, pp 96-102, ISBN 978-0-9926471-1-7, href="https://xmllondon.com/2014/xmllondon-2014-proceedings.pdf#page=96">https://xmllondon.com/2014/xmllondon-2014-proceedings.pdf#page=96 415c528,529 < http://www.w3.org/TR/xml-events --- > href="http://www.w3.org/TR/xml-events">http://www.w3.org/TR/xml-events 423,424c537,538 < the Views system, Report CS-R9262, CWI Amsterdam, 1992, < https://ir.cwi.nl/pub/5342/05342D.pdf --- > the Views system, Report CS-R9262, CWI Amsterdam, 1992, href="https://ir.cwi.nl/pub/5342/05342D.pdf">https://ir.cwi.nl/pub/5342/05342D.pdf
