Recently I took a fresh at look at the Go programming language after having last taken a look at it before version 1.0 was released back in 2009. What I’ve found in just a few days is shocking in a really really good way.

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:

From the website: John was a legendary computer scientist at Stanford University who developed time-sharing, invented LISP, and founded the field of Artificial Intelligence.* In March 2011 John launched Project JMC with the objective to make his work more approachable and accessible. The Project JMC team is continuing to help realize his objective. In this site you will find all John’s work, including his social commentary, and acknowledgements of his outstanding contributions and impact.

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?

After watching some of Tim Roughgarden’s videos on sorting algorithms, I thought I’d post an implementation of quick sort in Common Lisp as an example of a sorting algorithm implemented in CL. It’s a simple enough example(at < 20 LOC) that demonstrates one non-imperative approach to algorithm implementation. The complete code can be found here. (defun quick-sort-generic2 (sequence cfun &optional result-type) (if (<= (length sequence) 1) (copy-seq sequence) (flet ((partition (fun array) (list (remove-if-not fun array) (remove-if fun array)))) (let* ((result-type (or result-type 'vector)) (pivot-ind (random (length sequence))) (pivot-val (elt sequence pivot-ind)) (rem-seq (remove pivot-val sequence :start pivot-ind :end (+ 1 pivot-ind))) (part (partition (lambda (x) (apply cfun (list x pivot-val))) rem-seq))) (concatenate result-type (quick-sort-generic2 (car part) cfun result-type) (list pivot-val) (quick-sort-generic2 (cadr part) cfun result-type)))))) * (test-sort) started quick-sort (generic, array) .

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.

Sold out attendance marked this being the second premiere conference for Clojure. What I realized is just how great the people are in this community. No, seriously. There’s far less ego than with many other communities. This is a great sign for the future of Clojure. Particularly because Rich is such a great guy. He even gave a public apology for something or other that he said(on a mailing list) which he felt was not in the spirit of the Clojure community.

Overtone is an open source audio environment being created to explore musical ideas from synthesis and sampling to instrument building, live-coding and collaborative jamming. In this video Sam Aaron gives a fast-paced introduction to a number of key live programming techniques such as triggering instruments, scheduling future events and synth design. Finally, the viewer is shown how a simple musical sequence may be composed and then converted into an intricate Reich phase.

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.

Update : bug-fix when hull was being incorrectly calculated due to there being duplicate points generated in the random set. ClojureScript looks like a solid approach to building applications that target JavaScript VMs. It’s built on top of Google’s Closure Compiler/Library which is very intruiging and is the best approach that they could have taken (now that I’ve a played with it a little). Being new to both Closure and ClojureScript I was curious about what it might feel like to build an application using these tools.

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 …

Programming language wars don’t have to be religious based wars. Programming languages should be rooted in philosophy. The more a programming language is rooted in sound philosophy the more value it has. Over the years, many of the posts on this blog have been regarding some programming language, algorithm or technology. Some posts have highlighted why Lisp is the most powerful and useful programming language paradigm available to man at this point in the history of computer science.

As an example let’s look at an algorithm that’s fairly common : breadth first traversal of a binary tree. Also called level-order traversal. Wikipedia: “In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.” First let’s define a simple node struct and create a tree :

The implementers of existing Ruby VMs have gone the way of C, C++ and Java. There is another possibility. Why not implement Ruby in Common Lisp ? Ok, let’s take the first shot and implement a subset of the Ruby language. Just enough to run some simple contrived numeric benchmarks. The following pseudo BNF describing a minimal subset of Ruby should do (taken from the rubydocs here). PROGRAM : COMPSTMT COMPSTMT : STMT (TERM EXPR)* [TERM] STMT : CALL | EXPR EXPR | ARG CALL : FUNCTION FUNCTION : OPERATION [`(' [CALL_ARGS] `)'] ARG : LHS `=' ARG | ARG `.

Update 2010-06-30 : So just over a day after I posted this entry Google announced that they have acquired ITA. Announcement There was buzz back in April about Google possibly acquiring ITA Software. A few days ago Dan posted that these were just rumors based on a single Bloomberg article. Well it seems that it may be more than just a rumor : The Wall Street journal now has an article regarding the potential acquisition.

“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.

One popular interview question that never dies : write some code to reverse a singly linked-list. Now understanding the problem for interviewees is one thing but getting it right in an imperative language seems to be quite a feat based on my experience as an interviewer. Most take 15-20 minutes to get this completely correct and sometimes even longer. Here’s a quick solution that took me 10 minutes (in C) : #define LIST_SIZE 10000000 #define SHOW_SIZE 5 typedef struct node { struct node* next; int val; } node; int main(int argc, char* argv[]) { int i; long start, end; node* head = malloc(sizeof(node)); node* cur = head; node* cur2 = head; node* prev = NULL; node* next = NULL; // init linked list printf("

;; Calculates the convex hull of a set of points using the Graham scan ;; algorithm. (ns i27.geom.convex-hull (:use [i27.geom.misc :only (angle cross-product)])) (defn presort-points [pts] "Presorts the cartesian points in descending order by angle. The point with lowest y value is last in the vector." (let [pts (distinct pts)] ;; must be distinct or else errors ... (letfn [(find-start [[x1 y1 :as pt1] [x2 y2 :as pt2]] (cond (< y1 y2) pt1 (= y1 y2) (if (< x1 x2) pt1 pt2) true pt2))] (let [pt (reduce find-start pts) npts (remove (fn [[x y :as cpt]] (and (= (first pt) x) (= (last pt) y))) pts)] (conj (apply vector (sort (fn [pt1 pt2] (> (angle pt pt1) (angle pt pt2))) npts)) pt))))) (defn convex-hull "

(defn bucket-sort "Runs in O(n) time." [items] (let [len (count items) mx (apply max items) bucket-size (inc (int (/ mx len))) buckets (reduce (fn [v n] (conj v [])) [] (range (+ bucket-size (/ mx bucket-size))))] (letfn [(distrib-nums [v n] (let [ind (int (/ n bucket-size)) bucket (nth v ind)] (assoc! v ind (conj bucket n))))] (let [pre-buckets (persistent! (reduce distrib-nums (transient buckets) items))] (apply concat (map (fn [bucket] (when (> (count bucket) 0) (insertion-sort bucket))) pre-buckets)))))) Runs slightly faster than Clojure’s built-in sort (at least on integers in the range 0 to 1E6) :

Here’s a molecule viewer using OpenGL in Clojure. Implemented so that I could compare this type of development with Common Lisp (and also with using OpenGL development in C). OpenGL with Clojure can be really fun using Zach Tellman’s Penumbra. Coming at OpenGL from a more functional angle (e.g. not mutating global vars etc.) can be a little different but not difficult for anyone who has done enough functional programming. The code is here.

DISCLAIMER : THIS IS A LANGUAGE RANT. DO NOT READ IF YOUR BPF* IS LESS THAN 0.37. SIDE EFFECTS MAY INCLUDE SEVERE CONFUSION, UNJUSTIFIED ANGER, GASSY DISCHARGE, INCOMPREHENSIBLE DIALOG, ERRATIC DEGRADATION OF CHARACTER AND POSSIBLY A COMPLETE EMOTIONAL MELTDOWN.   Performance is one important aspect that people might want in a language. One language that continually surprises me in this regard is Haskell. Seriously, it’s simply amazing. But performance is only one important consideration when using a language.

* Update 2009-12-27 * Using lists instead of vectors brings the Clojure version down from around 20x to 10X slower than the CL version. One reader correctly stated that when doing performance comparisons between languages and implementations you want the code and data structures to be as identical as possible. “A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted.

A Quine is a program that produces its complete source code as its only output. Because Clojure is a Lisp, it is especially well suited to writing Quines. This is a quine implemented in Clojure. ((fn [x] (list x (list (quote quote) x))) (quote (fn [x] (list x (list (quote quote) x))))) M.C. Escher – Drawing Hands – 1948

A few updates and bug fixes from the first version. You can now play it here. ACHTUNG ! : This requires unrestricted perms so you should probably just grab the code and compile it yourself.

* UPDATED : 2009-09-17 * – rewritten in a functional style that is more idiomatic of Clojure. A nostalgic attempt to try and learn some GUI programming in Clojure. Inspired by Pong in Haskell. Play online here. The computer seems unbeatable(but it’s not thanks to a bug as things get faster). Have fun ! < 200 lines of code : ;;;; ;;;; Pong! ;;;; ;;;; Justin Grant ;;;; 2009/09/12 (ns i27.

Took a shot at implementing a PI digit generator in Clojure using a ‘fast’ algorithm. It seemed like a decent enough excercise to try and understand something about performance in Clojure. MacBook Pro – Intel Core 2 Duo 2.26 GHz – 4GB RAM Java(TM) SE Runtime Environment (build 1.6.0_15-b03-219) Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02-90, mixed mode) Clojure 1.1.0-alpha-SNAPSHOT (Aug 20 2009) git commit f1f5ad40984d46bdc314090552b76471ee2b8d01 Clojure matches the performance of Java in this example.

The previous Common Lisp and Haskell functions to generate the digits of PI where only accurate between 10000 and 20000 digits. The algorithm uses an approximation where we discard a certain number of ‘guard’ digits to get an accurate result. Some background regarding how the number of guard digits is calculated : There is ‘wobble’ in the number of contaminated digits depending on the number of input digits. When only the order of magnitude of rounding error is of interest, ulps(units in the last place) and ε (machine precision) may be used interchangeably, since they differ by at most a factor of β (the ‘wobble’ in the number of contaminated digits).

Thanks to metacircular for pointing out that (floor (/ x y)) can be written as (floor x y) while avoiding the intermediate rational. (defun machin-pi (digits) "Calculates PI digits using fixed point arithmetic and Machin's formula with double recursion" (labels ((arccot-minus (xsq n xpower) (let ((term (floor xpower n))) (if (= term 0) 0 (- (arccot-plus xsq (+ n 2) (floor xpower xsq)) term)))) (arccot-plus (xsq n xpower) (let ((term (floor (/ xpower n)))) (if (= term 0) 0 (+ (arccot-minus xsq (+ n 2) (floor xpower xsq)) term)))) (arccot (x unity) (let ((xpower (floor (/ unity x)))) (arccot-plus (* x x) 1 xpower)))) (let* ((unity (expt 10 (+ digits 10))) (thispi (* 4 (- (* 4 (arccot 5 unity)) (arccot 239 unity))))) (floor thispi (expt 10 10))))) The first 10000 digits again.

Update 2009-07-23 : Faster version in CL and a Haskell version. ——————————————————————————– A trivial approximation using the Leibniz formula. (defun leibniz-pi() (labels ((local-pi(sum n) (if (< n (expt 10 6)) (local-pi (+ sum (/ (expt -1 n) (+ (* 2 n) 1))) (+ n 1)) sum))) (* 4 (local-pi 0f0 0f0)))) And here’s a longer version(but faster and more precise) using Machin’s formula with fixed point arithmetic to x digits.

Here’s an implementation of Emacs Lisp’s MAPCONCAT function for Common Lisp. (defun mapconcat (fun list sep) (when list (let ((~sep (with-output-to-string (*standard-output*) (map nil (lambda (ch) (princ (if (char= #~ ch) "~~" ch))) sep)))) (format nil (format nil "~~A~~{~A~~A~~}" ~sep) (funcall fun (first list)) (mapcar fun (rest list)))))) timed : * (time (mapconcat 'identity *mylist* "-")) Evaluation took: 2.805 seconds of real time 2.746358 seconds of total run time (2.

The last article ended with a challenge hoping that someone would come up with an improved version of the boggle solver that beats my version. Well someone did, they also proved that with this particular algorithm the Lisp version can match C within about 20%. Very good ! Here are the new graphs (note that the first is no longer on a logarithmic scale). The patches have been merged into the

The previous article had some serious traffic yesterday and today. Due to abuse of the moderation system on some sites I’ve been forced to present my response here separately. To the SBCL contributor : Relax, SBCL is still a great Lisp compiler. It always has been and I’m sure it always will be. Your work on the compiler is appreciated. It’s unfortunate that you seem to fit the pontificating arm-chair theoretician stereo-type.

* Update 2009-05-06 : The challenge has been met ! See the new graphs of performance. * myths and legends The myths and legends precede the language. Lisp. (The same holds true for its dialects and derivatives.) Its ‘bizarre’ syntax, its alleged ability to stand up to low level language performance, the unique and powerful abstractions awarded the programmer who even dares to attempt its almost vertical cliff face of learning.

A Lisp version of the code from this article –> http://iam.elbenshira.com/archives/151_integral-calculus-in-haskell/ ********** For those that are unhappy about this not being a Symbolic Integration example then please read Norvig’s “Paradigms of Artificial Intelligence Programming – Case Studies in Common Lisp”, Chapter 8 – Symbolic Mathematics : A Simplification Program, 8.6 – Integration, page 252. http://norvig.com/paip.html ********** (defparameter *small-dx* 0.0001) (defun integrate(f a b) "integrate a function f from a to b"

My curiousity got the better of me tonight. Video behind the link.

Andrew Sorenson is doing some beautiful live “Lisp coding as art” with synthesized sound and OpenGL. Give the video some time to start up or skip ahead (at least 3 minutes).

Before I go any further : let me state upfront that knowing Lisp has changed me as a programmer for the best. It’s been an invaluable experience that I’ve carried into every corner of my career and every other language that I’ve coded with. Now that we have that out of the way let’s move on… There are a number of problems with Common Lisp that go unmentioned in the community.

More info here with pictures. See lispy’s insightful coverage on the talks if you couldn’t make it. One of the highlights was getting to sign a copy of Lisp 1.5 Programmer’s Manual that was then gifted to John McCarthy after the event ! (Richard Gabriel, JonL, Pascal Costanza)

Dan Weinreib’s Common Lisp Implementations: A Survey ALU’s Common Lisp Implementations Building stable and scalable high-volume network servers on open-source common CL implementations

Some Haskell fans seem impressed with better performance for a fibonacci function compared with similar implementations in Ruby and Python. They should be. I may be turning into a Haskell fan myself actually. Here’s why … Read this and this before going on. Impressive. Yea I thought so too until I implemented the same fib function in Lisp and ran it on SBCL. Here it is… (defun print-fib-trec-naive (start end) (format t "

The previous post was pretty grumpy about Python/Django and I was going to write a follow-up about why Ruby is a better language (unfortunately not the platform’s performance just yet but that is soon to change with YARV). For this post to appear more fair about Ruby/Python than the last let’s look at one reason where these don’t come close to Lisp. This is something mentioned less often(but still important) when comparing Lisp with other languages which usually focus on macros and s-exprs.

(This has been around for a while now but it still deserves more linkage.) Anyone who has ever learned to program in Lisp will tell you it is very different from any other programming language. It is different in lots of surprising ways- This comic book will let you find out how Lisp’s unique design makes it so powerful!

Artificial Intelligence An early look at artificial Intelligence. Guests includes Edward Feigenbaum of Stanford University, Nils Nilsson of the AI Center at SRI International, Tom Kehler of Intellegenetics, Herb Lechner of SRI, and John McCarthy of Stanford. Featured demonstrations include Inferential Knowledge Engineering and the programming language LISP. Originally broadcast in 1984. AND Daniel G Bobrow: Common LISP Object Standard (1987)

Regarding the role of Lisp and game development (specifically on the PS2), Andy Gavin has this to say… “Lisp was just the best solution for this job,” comments Gavin. “With leading edge game systems like ours, you have to deal with complicated behaviors and real-time action. Languages like C are very poor with temporal constructs. C is just very awkward for a project like this. Lisp, on the other hand, is ideal.