Sort.jmc
Download:
Overview:
This sorting program sorts a list, keeping the invariants of sorting separate from procedures.
Any kind of sort program's invariant is equal, basically describing what it means for a list to be sorted. this will never change. Sort programs also contain one or many procedures that achieve the goal of sorting the given list. The problem with most of the programs today is that it's hard to distinguish the two main parts, even hard to tell different procedures apart, even harder to control which combination of procedures to try in the presence of multiple ones. Another setback is that the programs are often not understandable for the same reason. A disorganized amalgam of meanings and optimizations are messy, hard to understand and control.
JOHN programs separate the meaning and optimizations by staying mainly declarative. Meanings are stated in forms of goals possessed by objects. Procedures appear as actions, by some sequence of which these goals can be achieved. They themselves are defined separately and distinguishable from one another. Actions by themselves are not smart to know what their purpose in life is, or when is that purpose achieved. It is the meaning part, the goal, that watches these actions done and takes over when it is satisfied (or unsatisfied).
create AList items.
Below we define what it means for a list to be sorted, also define some qualifications that measure the sortedness of the items in the list:
qualify List sorted if its size < 2.
qualify List sorted if its first <= its second and
its rest sorted = yes.
qualify List unsortedness 0 if its size < 2.
qualify List unsortedness its rest unsortedness if its first <= its second.
qualify List unsortedness 1 + its rest unsortedness if its first > its second.
qualify List nearly-sorted if its unsortedness < 2.
qualify List nearly-reversed if its unsortedness > its size - 2.
qualify List mostly-unsorted if its unsortedness >= 2 and its nearly-reversed = no.
action AList bubble-sort consequence ... action AList selection-sort consequence ... action AList insertion-sort consequence ... action AList merge-sort consequence ... action AList quick-sort consequence ...
All the sort procedures above, designed so that they do only one iteration (step) of the algorithm on each call. This allows us to use a mixtures of algorithms at different steps to accomplish the sorting task.
The good thing about the methodology is that user can explicitly turn any combination of these procedures on or off in achieving a certain goal.
> L1 satisfy sort using quick-sort.
> L1 satisfy sort using quick-sort insertion-sort.
More realistically, we like to dynamically decide the mixture of procedures to use to accomplish the task at hand. JOHN allows optimization definitions for goal to achieve this.
goal-optimization AList sort use insertion-sort if its items nearly-sorted = yes.
goal-optimization AList sort use merge-sort if its items nearly-reversed = yes.
goal-optimization AList sort use quick-sort if its items mostly-unsorted = yes.
It is also possible for optimizations to choose a mixture of procedures, as long as those procedures can be used collaboratively to get to a goal state.
quick-sort first, and after a while the list becomes almost-sorted and insertion-sort is used afterwards:
> make AList L1 [ 43, 91, 43, 8, 55 ].
> L1 satisfy sort.
satisfied at time: 12
satisfied by: [ L1 quick-sort , L1 quick-sort , L1 quick-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort , L1 insertion-sort ]
> L1 items.
[ 8, 43, 43, 55, 91 ]