XForms is a declarative programming language for writing applications for the web and elsewhere.
One of the strengths of the language is how data is described: types, constraints, and relationships between values declaratively describe the structure, validity, and interconnection of data, as global properties.
A central part of this is invariants that describe relationships between values, such that if a value 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 work is taken out of the hands of the programmer, and left to the computer: the programmer specifies the relationships, the computer does the work.
Sorting data is one of the major tasks of many programs, and this is usually done programmatically: the data is, or becomes, unsorted, and a function is then called to order the data suitably.
On the other hand, being sorted is often just a necessary property of the data for the rest of the program to function properly, which could just be stated declaratively, leaving the work to ensure it remain sorted to the computer.
This paper discusses the issues involved, and how the question was approached when adding declarative sorting to XForms, as well as touching on implementation details and advantages.
Considering the title of this conference, I'm assuming everyone know what declarative techniques are about:
Getting things done by describing what you want, not how to get it.
XForms, first released in 2003, and still being maintained, is a declarative programming language.
In fact, this year 2 new implementations have been announced.
Many examples of huge time and resource savings, for instance John Chelsom's CityHCR health records system, modelled on a failed 10 year/70 programmer Java-based system, that he rewrote singlehandedly in XForms in 3 years.
XForms splits programs into two parts:
Data can have properties assigned, such as
Additionally, and most important, a value may be calculated from other values.
Largely automatically, data values and properties get updated as necessary.
This is like spreadsheets, but way more general.
Intent based
Automatically updated
For instance these are three different presentations of the same control that allows you to select a single value from a list:
ABC is a programming language that I co-designed here at the CWI in the 80's. It formed the basis of Python. [demo]
Still being maintained.
The first implementation of ixml was programmed in it.
New 64 bit implementation with Unicode support to be released shortly.
ABC was designed in an unusual way (for programming languages): as an HCI product.
Programming languages are an interface between humans and computers, so it stands to reason that designing them should be based on HCI principles.
Part of the design included doing requirements analysis, and designing several different type systems, to see which best supported the requirements.
One conclusion: sorting and searching are the bedrock of programming and therefore should be primitives of the language.
And so ABC ended up with a very simple, very powerful data architecture, with only 5 types:
(a, (b, c), d)On top of this, the language is strongly typed but without declarations: types were inferred.
The upshot of this analysis and design is that by default lists and tables are kept sorted.
Added to this, since it is central to the kernel of the language, it is really, really fast.
As a result, ABC programs, which are interpreted, sometimes run faster than equivalent compiled programs, simply because sorting and searching is so fast.
And programming is much, much, easier (typically 10×).
[Demo]
There are two basic methods of sorting in XForms
1. Keeping it sorted as you update the structure
<insert position="after" ref="data[date >= new/date]" origin="new"/>
2. Using an XPath sorting function to sort the whole structure when necessary.
Being sorted is usually a required property of the data you are using, so why not try to do this declaratively.
The aim was to create a design for XForms that allowed you to specify that a particular structure was to be kept sorted, relieving you of any work.
The basic idea is to attach a property to entries, saying that they are sorted.
The default is ascending order, but you can also sort descending.
The sort attribute gives the expression that is used to specify
order:
<bind ref="member" sort="name/family"/> <bind ref="purchase" sort="date" direction="down"/>
Of course, you may want to sort on several fields; you then nest the properties:
<bind ref="entry" sort="date" direction="down">
<bind sort="name"/>
<bind sort="age"/>
</bind>
each bind is lower priority.
What this means is that data with this property is always kept sorted.
Instead of
<insert position="after" ref="data[date >= new/date]" origin="new"/>
I can simply say
<insert ref="data" origin="new"/>
In XForms, a control inherits the properties of the data it is bound to.
A new feature of XForms 2.0 is that controls can add their own properties too, that only apply to the use of the data in the control, but do not propagate back to the data itself.
<output ref="result" relevant=". > 0"/>
In this case the relevance only applies to this control, and not to the data it is bound to. Thus the value will only be visible if the value is positive, but other controls using the same value may still be visible.
Thus controls that bind to nodesets may also carry sorting properties:
<repeat ref="member" sort="name"> <output ref="name"/> </repeat>
In this case the list of members will be output in name order, even if the data is unsorted, or sorted on another property such as date.
Whether something is sorted or not, depends on its 'collation', which is usually a property of how a culture or langauge sorts its values.
For example, in German "Ä" comes between "A" and "B", while in Swedish it comes after "Z".
The default is just the order that characters come in Unicode.
We just took this straight from XPath, a collation property that is a URI pointing to collation details.
http://www.w3.org/2005/xpath-functions/collation/
html-ascii-case-insensitive
The advantages of the declarative approach are:
If you don't know if a set of nodes are sorted, then updating or searching are O(n).
If you know they are ordered, then those operations are suddenly O(log(n)).
This is a big difference for large lists.
If you double the size of the list:
Put another way,
(See my talk at Balisage 2021)
Being sorted is typically just a required invariant of a set of data.
By recognising this as a declarative property, it makes programming considerably simpler.