Joy is a purely functional, stack-based concatenative programming language invented by Manfred von Thun. It enables a programming paradigm called tacit programming or point-free style (aka pointless style among haters). Von Thun (2001) gives a very concise Joy-implementation of quicksort in just one line:
[small] [] [uncons [>] split] [swapd cons concat] binrec
Of course this is a hand-picked example that suits the language well. So I thought, what about implementing an algorithm that is more at home in an imperative paradigm, like insertion sort? To add to the challenge, we'll use the stack-based variant of the algorithm described by Ammar (1989).
We get a list of elements as input and use two stacks, which we'll call asc and desc, as auxiliary data structures.
After execution, the function should leave only the sorted input list on the stack.
The Python-like pseudocode for the main loop of the algorithm looks like this:
for element in elements:
if element > top of asc:
while element > top of desc:
move top of desc to asc
push element to desc
else:
move top of asc to desc
while element < top of asc
push element to asc
The following loop invariants must hold: asc contains elements in ascending order, desc contains elements in descending order, and the top of asc is less or equal the top of desc.
If we pop all elements of desc and push them to asc, we should end up with a sorted list.
We start with some auxiliary function definitions.
DEFINE
null_asc == [pop null] nullary;
null_desc == [pop pop null] nullary;
gt_asc == null_asc [true] [[swap first >] nullary] branch;
lt_desc == null_desc [true] [[rolldown first <] nullary] branch;
push_asc == swons;
push_desc == rolldown cons swap;
asc_to_desc == [uncons [swons] dip] dip;
desc_to_asc == rotate uncons [swons] dip rotate.
There are functions for checking whether the stacks are empty, for comparing the top of each stack with the current element, for pushing the current element to one of both stacks and to move elements from one stack to another.
To operate on the right data, we need to carefully manipulate the stack when entering the function and before returning, we need to make sure to leave the stack in a valid state, that is, the descending list should be pushed first, then the ascending list and finally the current element.
The four boolean checks should not consume any elements from the stack, which is ensured by the nullary combinator.
In the greater than and less than checks, an or would be clearer, however, Joy's or is not short-circuit evaluated, so I use the branch combinator.
Probably my functions are not idiomatic at all and there is a way to get rid of half the code by some clever stack manipulations, but this set of definitions does the job and encapsulates the messy part.
With the auxiliary functions in place, we can easily translate the initial pseudocode. Put the two stacks before the input list and then step through the input to collect the elements in the ascending and descending stacks. Finally, combine both stacks into one, which will be the sorted list. Done.
DEFINE
insertion_sort == [[] []] dip
[
gt_asc
[[lt_desc not] [desc_to_asc] while
push_desc]
[[gt_asc not] [asc_to_desc] while
push_asc]
branch
] step
[swons] step.
Alright, maybe a few tests, just to make sure it works.
DEFINE
test_empty == [] insertion_sort null;
test_single == [1] insertion_sort [1] equal;
test_ten == [4 3 9 2 0 6 1 7 8 5] insertion_sort
[0 1 2 3 4 5 6 7 8 9] equal.
[[test_empty]
[test_single]
[test_ten]
] [i] all .
This returns true, so everything seems fine.
Ammar, R. A. (1989). Stack-based sorting algorithms. Journal of Systems and Software, 9(3), 225-239.
Von Thun, M., & Thomas, R. (2001). Joy: Forth’s functional cousin. In Proceedings from the 17th EuroForth Conference.
This page was moved from my old website.