Write Yourself a Haskell... in Lisp

For me, the best way to understand something is usually to implement it myself. So when I first started getting serious about Haskell, I implemented (in Common Lisp) a simple lazy functional programming language that used graph rewriting for the interpretation. Then, years later, I mentioned this implementation in a Reddit thread about writing a Lisp interpreter in Haskell (maybe inspired by the well-known Haskell tutorial and this blogpost's namesake). I now decided to clean up that old code, throw out all the unnecessary cruft, and arrive at something easy to understand. The finished interpreter is less than 500 lines of Common Lisp (not including the type checker which will be the subject of my next post).

I should also add that of course we're not going to actually implement Haskell here. As we'll see, the language is a very much simplified model of pure, lazy functional languages. It's actually closer to GHC's Core than Haskell.

The downfall of Soviet microprocessor technology and Lisp

There used to be an old joke about Soviet high-tech, that the downfall of microelectronics technology in the Soviet Union was caused by the finished products not fitting through the factory gate.

I've discovered the exact same problem with Lisp the other day.

The last time I looked for a good binding of GTK+ for Lisp, I came out empty-handed, but now I've discovered a new project called CL-GTK2 that seems really promising. It installed without problems using ASDF-Install (which is, sadly, not a given for most other GTK+ bindings), and even comes with Cairo binding.

So the idea was to rewrite Goblin using Lisp, as an exercise and a test of CL-GTK2's usability. The first playable version, a straight rewrite of the original Python code, came out at about two hundred lines of code. Before making any wild refactorings and adding new features, I've decided to try creating a standalone executable using SBCL and cl-launch, following these instructions.

So it seems deploying standalone executables to end users is still not a realistic option. And no, web apps are not the answer. They may be answers, but to totally different questions.

Eliminating magic strings from ELisp's (interactive)

If you hate magic string API's as much as I do, you'll like this macro replacing Emacs's (interactive) declaration. It allows you to rewrite the following function definition:

into the much cleaner form below:

It currenty only supports :pos, :region and strings entered at the prompt, but the code is trivial to extend to other initializers.

Type inference for CLazy

CLazy now features Hindley-Milner type inference, the type calculus all the cool guys use. For example, given the following recursive definition of map:

the type inference engine of CLazy correctly reconstructs the following type signature:

Still to come: virtual functions like Haskell's typeclasses. The plan is to define abstract functions like (+ a) :: (fun a a a) and collect requirements for functions in the form of "this function has type (fun a b) as long as an overload for (+ a) exists".

CLazy interpreter and compiler

CLazy is my toy functional programming language featuring a Lisp-like syntax, lazy evaluation, and not much else at the moment. To get a taste of it, here's the definition of map in CLazy, using pattern matching:

(deftype list (t)
  nil
  (cons t (list t)))
   
(defun map (f nil)         nil)
(defun map (f (cons x xs)) (cons (f x) (map f xs)))

I've written the interpreter (in Lisp) back in November, and now I had this idea of writing a compiler. This compiler, instead of generating e.g. x86 assembly code, generates C# which is then compiled into .NET IL.

To do the actual code generation, instead of outright outputting text, the compiler (also written in Lisp) generates an s-expr representation of C# code. For example, the code generated for the type list, as defined above, is represented as the following: