It looks like it might be coming sooner than I thought. I’m sure Shenturions everywhere will find this news incredibly exciting for the future of Shen. I can’t wait to see how things progress.  

*Updated @ 2012-08-31 02:08:58 due to internet pedantry* Previously, previously. According to Wikipedia : In computer science, a Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

It’s been a while since I last posted in this series. Today we look at the disjoint-set data structure, specifically disjoint-set forests and the complementary algorithm : union-find. In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

A Shen type-checked implementation of Quick Sort is even more elegant/terse compared with the CL version posted previously. Pattern-matching and currying make this possible. (tc +) (define filter {(A --> boolean) --> (list A) --> (list A)} _ [] -> [] T? [A | B] -> (append [A] (filter T? B)) where (T? A) T? [_ | B] -> (filter T? B)) (define quick-sort-generic {(list A) --> (A --> A --> boolean) --> (A --> A --> boolean) --> (list A)} [] _ _ -> [] [A | B] L?

Here’s a port of the previous Qi II code to Shen. Run with Hakan Raberg’s 0.1.4 version of shen.clj (Shen implemented in Clojure !). * Accurately calculates N digits of Pi using Machin's formula with fixed point arithmetic and variable guards digits. Depends on the maths library --> http://www.shenlanguage.org/library.html * (tc +) (define arccot- {number --> number --> number --> number --> number --> number} X N XPOWER 0 _ -> 0 X N XPOWER TERM 1 -> (+ (arccot- X (+ N 2) (floor (/ XPOWER X)) (floor (/ XPOWER N)) 0) (floor (/ XPOWER N))) X N XPOWER TERM 0 -> (- (arccot- X (+ N 2) (floor (/ XPOWER X)) (floor (/ XPOWER N)) 1) (floor (/ XPOWER N)))) (define arccot {number --> number --> number} X UNITY -> (let XPOWER (floor (/ UNITY X)) (arccot- (* X X) 1 XPOWER (floor XPOWER) 1))) (define machin-pi {number --> number} DIGITS -> (let GUARD (+ 10 (ceiling (log' DIGITS 10))) UNITY (expt 10 (+ DIGITS GUARD)) (floor (/ (* 4 (- (* 4 (arccot 5 UNITY)) (arccot 239 UNITY))) (expt 10 GUARD))))) (1+) (time (machin-pi 100)) run time: 2.

The first publicly available version of Shen/Kl has been released. The Shen mission is to develop an ultra-portable version of Qi that can run under a wide variety of platforms and which incorporates missing features in Qi such as streams. The targeted platforms are CL, Clojure, NewLisp, Emacs Lisp, ECL, Scheme, Javascript and Python as well as C/C++, DVM, CLR or the JVM. This approach involved rewriting and redesigning Qi to fit within the smallest feasible instruction set.

In this second post in this series we look at an implementation of the always useful Fast Fourier Transform. (FFT) An algorithm for computing the Fourier transform of a set of discrete data values. Given a finite set of data points, for example a periodic sampling taken from a real-world signal, the FFT expresses the data in terms of its component frequencies. It also solves the essentially identical inverse problem of reconstructing a signal from the frequency data.

Update 2011/06/28 : Source has been modified to compile with Shen This is the first in a series of posts that will demonstrate the implementation of many well-known(and less known) data structures and algorithms using a purely functional approach. We will use Qi as our implementation language for a number of reasons : It’s a Lisp : macros, EVAL, hash-tables, property-lists, meta-programming etc. Pattern matching. Optional static type checking. A Turing-complete type system !

Qi is the future of Lisp. It is Lisp with many great features such as pattern-matching, a turing complete static type system (even more powerful than Haskell’s type system) and many others. So in the spirit of PI day, here’s an implementation that calculates PI using Machin’s formula. (define ceiling X -> (CEILING X)) (declare ceiling [number --> number]) (define expt X Y -> (EXPT X Y)) (declare expt [number --> number --> number]) (define floor X Y -> (FLOOR X Y)) (declare floor [number --> number --> number]) (define log X Y -> (LOG X Y)) (declare log [number --> number --> number]) (tc +) (define arccot- {number --> number --> number --> number --> number --> number} X N XPOWER 0 _ -> 0 X N XPOWER TERM 1 -> (+ (arccot- X (+ N 2) (floor XPOWER X) (floor XPOWER N) 0) (floor XPOWER N)) X N XPOWER TERM 0 -> (- (arccot- X (+ N 2) (floor XPOWER X) (floor XPOWER N) 1) (floor XPOWER N))) (define arccot {number --> number --> number} X UNITY -> (let XPOWER (floor (/ UNITY X) 1) (arccot- (* X X) 1 XPOWER (floor XPOWER 1) 1))) (define machin-pi {number --> number} DIGITS -> (let GUARD (+ 10 (ceiling (log DIGITS 10))) UNITY (expt 10 (+ DIGITS GUARD)) (floor (* 4 (- (* 4 (arccot 5 UNITY)) (arccot 239 UNITY))) (expt 10 GUARD)))) And the output …

“Let over Lambda – 50 Years of Lisp” by Doug Hoyte This one had been sitting on my bookshelf for almost a year. “Let Over Lambda is one of the most hardcore computer programming books out there. Starting with the fundamentals, it describes the most advanced features of the most advanced language: COMMON LISP. The point of this book is to expose you to ideas that you might otherwise never be exposed to.