Discussion
I added a sort function. After reading up on sort algorithms, and trying out a quicksort version, I went with mergesort. It's a little slower than quicksort but it's stable, which is often important. And super simple to implement.
Also, since my comparison operators are polymorphic, sort automatically works on all of numbers, characters, strings, and atoms.
Was reading an old INTERLISP manual and came across nlambda - like lambda but the resulting closure does not evaluate its arguments. lmin already has the necessary code to run such closures, but does not have a way to create them. Adding nlambda would be trivial.
Do more modern lisps have some other way to do this?
While writing nlambda versions of control structures like (while) and (until), I ran into an issue - in order to evaluate its arguments properly, nlambda must use dynamic scope, not lexical scope. This wasn't an issue in INTERLISP because it only had dynamic scope.
This makes me considerably less excited about nlambda, and I may back out the changes.
Install bonfire.cafe
Get the full app experience
My implementation of mergesort was doing a lot of list appends, which I'm sure were O(1) in Johnny von Neumann's original version back in 1945 but in LISP they are O(n), and doing them n times makes it O(n^2) just for list shuffling. Bad.
So I made a version that does list-prepends, a.k.a. cons, and then reverses the lists at the end. Reverse is O(n) so that's n*O(1) + O(n), which is still O(n).
Testing the two versions on a list of 1000 random numbers, the prepend one is 12 times faster!