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 detail 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.
ABC is a programming language that I co-designed here at the CWI. Later it formed the basis of Python.
It 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. They should be primitives of the language.
And so ABC ended up with a very simple, very powerful data architecture: only 5 types:
On top of this, the language is strongly typed but without declarations: types were inferred.
The upshot of this is that by default lists and tables are kept sorted.
If that's what you wanted, great!, less work.
If it doesn't make any difference, well fine.
If that's not what you wanted, there is a little more work you need to do, but not much.
Added to this, since it is central to the kernel of the language, it is really really fast.
(As a result, ABC programs, which were interpreted, sometimes ran faster than equivalent compiled programs)
And programming was much, much, easier.
The aim then was to create a design for XForms that allowed you to specify that a particular structure was to be kept sorted.
Incremental sorting vs periodic sorting