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-baed system, that he rewrote singlehandedly in XForms in 3 years.
XForms splits programs into two:
Data can have properties assigned, such as
Additionally, the value may be calculated from other values.
Largely automatically, data values get updated as necessary.
This is like spreadsheets, but way more general
This is an XForms program of about 50 lines of XForms
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 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×).
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 field that it should be kept sorted
on:
<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.
A new feature of XForms 2.0 is that controls can carry 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 at other controls using the same value it may still be visible.
<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 of birth, or date of joining.
Whether something is sorted or not, depends on its 'collation', which is usually a property of how a culture 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:
(See my talk at Balisage 2021)
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,