Typed Lisp adventure

After having been inspired by overtone and extempore to try out a Lisp dialect for DSP coding I wondered if it would be possible to use a Lisp language directly in synth plugins without a host environment.

My second (or third) language in daytime programming is Clojure, which I am very content with, so I wanted to use something similar in my “freetime” for DSP programming. I initally tried some Scheme dialects such a Chicken, Gambit and Bigloo, but became a little annoyed by the verbose syntax and the lack of proper abstractions for collection like types.

On GitHub I stumbled upon a few statically typed Lisp dialects and was especially convinced by looking at extempore that writing a statically typed LISP was possible and for some programming domains even useful. So I decided to write something similar like extempore, but with Clojure syntax instead of Scheme and without a host environment but gcc based compilation instead. I named the exercise symbol.

I considered using LLVM as the compilation backend briefly, but found especially closure handling too difficult to handle, since I hadn’t any prior experience in compiler programming. I went with using C++11 as the target language since it has some nice features such as templates, closures, direct C bindings and fast compilers.

Next I began to sketch the architecture for my language compiler. After a few iterations and studying various Clojure/script compilation projects I went with

  • reading via a customized Clojure Lisp reader
  • macro expansion, using Clojure macros
  • form normalization via various function based rules
  • type inference using core.logic
  • serialization to C++
  • compilation via g++

The most challenging part was probably the type inference. Having used logic programming actively 10 years ago it was a little difficult to get into logic programming concepts again, but after a few core.logic performance issues, most things went quite smoothly.

I was able to infer variable types based on assignments and function argument and return types via body expressions using a simplified version of the type inference. In addition to Hindley-Milner type inference I also extended the set of literals of the syntax via a custom reader to support integer and float literals in addition to ones Clojure supports.

I was quite successful with porting simple extempore examples to symbol, but struggled with more complex programs. I also couldn’t decide whether to include garbage collection or not. Using smart C++ pointers might have been a good alternative, but might have been difficult for type inference, so I continued with raw pointers and without garbage collection.

I tried to use C++ bindings directly via gccxml which dumps the intermediate format of the gcc compilation via XML, but had some issues with it. gccxml doesn’t support templates and the XML format was difficult to transform into a form that was compatible with the types of the type inference.

Another difficult issue was to map both stack and heap allocation to the minimal syntax of symbol. After a while I gave up and began to use C++ directly for DSP programming. All in all this was a really interesting experience to sketch a new language, or better a compilation chain, since what I did could also be described as mapping a subset of Clojure syntax to C++. I might continue with symbol once I am more familiar with C++, but for now it’s suspended.

Various syntax examples are available here.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s