lisp

Visualizing call graphs in lisp using swank and graphviz

Last week I was doing some cleanup work (short holiday weeks are great for paying off technical debt), and was deleting some supposedly unused code. This was a pretty tedious process of running functions like slime-who-calls and slime-who-references, running git grep -i on the command line, and undefining functions in just the right order.

I’ve seen a lot of articles recently on static analysis of code, and spent some time playing with the introspection features of slime to identify unused code (short holiday weeks are also great for following a tangents). I ended up with a slow mudball of code that worked pretty well.

Warning, large images coming up.

The code itself is up on github, but there’s no ASDF system yet, so you have to load it manually:

(require :iterate)
(require :alexandria)
(require :swank)
(load "~/lisp/static-analysis/static-analysis.lisp")
(in-package :static-analysis)

An truncated example:

STATIC-ANALYSIS> (call-graph->dot :alexandria )
digraph g{
subgraph clusterG982{
label="PACKAGE STATIC-ANALYSIS"
G983 [label="ENSURE-PACKAGE-LIST"]
}
subgraph clusterG949{
label="PACKAGE ALEXANDRIA.0.DEV"
...
}
G983 -> G995
...
G951 -> G950
}
NIL

Here’s what it actually looks like:

http://ryepup.unwashedmeme.com/blog/wp-content/uploads/2012/01/wpid-alexandria-graph.png

The code currently scans all loaded code, and puts functions from each package in it’s own graphviz subgraph. The graph for an entire package for all loaded code isn’t really that useful, so I made another function to narrow it down. Here I’m specifying the list of packages to render, and the list of functions to show.

STATIC-ANALYSIS> (->dot (function-call-graph '(:alexandria) '(alexandria:rotate)))
digraph g{
subgraph clusterG1109{
label="PACKAGE ALEXANDRIA.0.DEV"
G1040 [label="ROTATE-HEAD-TO-TAIL"]
G1049 [label="SAFE-ENDP"]
G1054 [label="CIRCULAR-LIST-ERROR"]
G1051 [label="PROPER-LIST-LENGTH"]
G1042 [label="ROTATE-TAIL-TO-HEAD"]
G1041 [label="ROTATE"]
}
G1040 -> G1051
G1051 -> G1049
G1051 -> G1054
G1042 -> G1051
G1041 -> G1040
G1041 -> G1042
}
NIL

http://ryepup.unwashedmeme.com/blog/wp-content/uploads/2012/01/wpid-alexandria-rotate.png

Some systems have very complicated call graphs. At work we do a lot with clsql, and the overall call graph even from one function can get complicated quick:

http://ryepup.unwashedmeme.com/blog/wp-content/uploads/2012/01/wpid-clsql.png

So I added a depth param to keep the graph smaller, let’s say 3:

STATIC-ANALYSIS> (->dot
 (function-call-graph '(:clsql-sys :clsql-sqlite3)
                      '(clsql:map-query)
                      2))

http://ryepup.unwashedmeme.com/blog/wp-content/uploads/2012/01/wpid-clsql-limited.png

Anyhoo, a fun toy, and I had a fun time writing it.

lisp
org2blog

Comments (5)

Permalink

Getting started with Hunchentoot and Talcl websites

This is a short guide to setting up a lisp-powered website with Hunchentoot and Talcl/Buildnode.  Hunchentoot is a web server, Talcl is a templating system, and Buildnode is a CXML helper library Talcl uses.  These are from notes I made while writing an app to help my wife record attendance and student progress for dance classes.

My high-level approach on my hobby projects is to write the user interfaces using mostly pure HTML/Javascript/CSS and jQuery, and then make a RESTful (mostly) API with Hunchentoot’s Easy Handlers that the Javascript front-end calls to perform some operations.  For some reason things like parenscript and cl-who never felt right to me.  Anyhoo, let’s get started.

Foundation

I’m calling this project “Alice”, so time to make the foundation:

(quickproject:make-project "~/lisp/alice/" :depends-on '(:iterate :alexandria :talcl :hunchentoot :buildnode))

I generally always include iterate and alexandria, and we’ll want a few things from buildnode directly so we’re depending on that separately from talcl.  Quickproject makes all my files, and I’m good to start.

Here’s the basic goal:

 

I want to have my templates stored in .tal files, and hunchentoot will need a place to look for static files, so we start with a few new directories: “www” for hunchentoot and “templates” for tal.  To easily get paths to these, I added a helper function:

(defun resource-path (path)
  "looks up path relative to whereever this asdf system is installed.  Returns a truename"
  (truename (asdf:system-relative-pathname :alice path)))

Hunchentoot

Now the fun begins. Next is a function to start the hunchentoot acceptor (which will handle listening on a port and dispatching requests) AND configure the static file handling I wanted.

(defvar *acceptor* nil "the hunchentoot acceptor")
(defun start-server (&optional (port 8888))
  (setf *acceptor* (make-instance 'hunchentoot:acceptor :port port))  
  ;; make a folder dispatcher the last item of the dispatch table
  ;; if a request doesn't match anything else, try it from the filesystem
  (setf (alexandria:last-elt hunchentoot:*dispatch-table*)
	(hunchentoot:create-folder-dispatcher-and-handler "/" (resource-path "www")))
  (hunchentoot:start *acceptor*))

By having the folder-dispatcher-and-handler as the last item in hunchentoot’s *dispatch-table*, it will only bail to the filesystem if no other handlers match. Hunchentoot has a *default-handler* mechanism, but it is limited; default-handlers do not have access to any request information.

Now I toss a stub style.css into my www/ directory, call start-server, then can load http://localhost:8080/style.css in my browser.  Great, the right half of my desired flowchart is done.  Now the Talcl part.

Talcl

Talcl reads template files, compiles them into lisp functions that accept a tal enviroment.  The tal environment is a set of key/value pairs that will fill in the templates.  Talcl has a bunch of features to handle writing to streams, but for now I’ll just generate strings and pass them to hunchentoot.

(defvar *tal-generator*
  (make-instance 'talcl:caching-file-system-generator
		 :root-directories (list (resource-path "templates"))))

The tal generator maps template names to template files, compiling the templates if needed. There are a few different classes that can be used here, but this one checks file dates and recompiles only if the file is newer.

(defun render-page (template &optional tal-env)
  "renders the given template" 
  (talcl:document-to-string
   (buildnode:with-html-document
     (talcl:tal-processing-instruction *tal-generator* template tal-env))))

This helper function takes the template name and the optional tal environment, and returns a string of the final output. Talcl deals in XML, but HTML is not XML so I use the buildnode:with-html-document macro to resolve the mismatches (eg: <script src=…></script> instead of <script/>). According to Talcl examples, there are several ways to get your tal content into an XML document, and tal-processing-instruction is the fastest.

(hunchentoot:define-easy-handler (home :uri "/") ()
  (render-page "home.tal"
	       (talcl:tal-env 'course (current-course))))

This adds a handler to hunchentoot’s table, and should get us going down the left branch of my flowchart.  The tal-env call is creating the tal environment where the compile template function will look for substitutions.  I think of these like keyword arguments for the template.  In this case, I’m pulling some course information and passing it to home.tal.

Tal Templates

The last complicated bit is the tal templates themselves. There are some good examples in the talcl repository.   I want one tal file to be the main site template, a frame around whatever content I’m trying to show with all the html,head,body tags.  Then I’ll have one tal file for each major UI element.

The overall site template will be in templates/template.tal:

<html lang="en" 
 xmlns:tal="http://common-lisp.net/project/bese/tal/core"
 tal:in-package=":alice">
 <head>
 <meta charset="utf8"/>
 <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.6.1/jquery.min.js"/>
 <script src="/script/alice.js"/>
 <link rel="stylesheet" href="/css/style.css" type="text/css" />
 </head>
 <body>
 <span id="body">$body</span>
 </body>
</html>

Since this is XML, we need some xmlns noise at the top, but we can use XMLisms like “<script/>”.  The key things to note here:

  • tal:in-package=":alice" – need to tell Tal where it should be evaluating
  • $body – this is one way to substitute values into the template. Talcl will look for a symbol 'alice::body in it’s tal environment

So that’s our main template file, now for the home.tal file:

<tal:tal xmlns:tal="http://common-lisp.net/project/bese/tal/core"
 xmlns:param="http://common-lisp.net/project/bese/tal/params"
 tal:in-package=":alice">
 <tal:include tal:name="template.tal">
  <param:body>
   <button>Start Jam Class</button><br/>
   <tal:loop tal:var="c" tal:list="(classes course)">
    <a href="class?name=$(name c)">Start $(name c) Class</a>
   </tal:loop>
  </param:body>
 </tal:include>
</tal:tal>

I have the same xmlns noise, but have a new one namespace, param.  This is the xml namespace tal uses to pass information from one template to another. The top level XML node is a “tal:tal” node, which does not render any output.  I include template.tal to get our main template, passing it the UI for this page in a param:body.  This adds 'alice::body to the tal environment, with the XML contents as the value, then template.tal is called.  I use some fancier tal statements to loop over all the dance classes in the given course and make a link to each one.

Performance

Happy hacking!

lisp

Comments (5)

Permalink

Title cards for videos with Common Lisp

Xach posted recently about Fighting blog spam with Common Lisp as a short example of using lisp to solve everyday programming problems.  Here’s one I made last weekend.

The Problem:

My wife belly dances, and we frequently do some light video editing before posting things to youtube.  One of the annoying chores is making title cards, usually white text on a black background that we put at the beginning and end of each video to state time, place, etc, and then fade in/out.  An example:

Text should be large enough to fill the screen, centered, and all the same size.  For awhile I made these in Gimp, then made them in HTML and took screenshots, and finally said screw it and wrote a small helper program.  I don’t know how to use Gimp effectively, and jiggling font sizes in HTML is a pain.  I’m sure there are better solutions, but it was faster (and more fun) for me to write some lisp.

The Solution:

To make title cards, I wrote a little program called “Titler”.

Like Xach’s project, I started with (quickproject:make-project "~/src/lisp/titler/" :depends-on '(vecto iterate))

From there I banged away at it for a little while, found some .ttf files on my system and got the basic generation done using vecto’s string drawing functions. The only tricky bit was to determine the optimal font size. Vecto provides a string-bounding-box function that will give you pixel dimensions for a given string at a given font size. I made a function that uses newton’s method to iteratively try different font size values until we get one that fits on the title card and takes up more than 75% of the width. I’m almost positive there are corner cases where my implementation won’t converge on a solution, but it works pretty well for now.

For the next video I can make easy titles:

(make-title "www.ShamblingShimmies.com

May 26, 2011
Sun Center
Gainesville, FL" 640 480)

Code is at https://github.com/ryepup/titler, and you can see the results (and my wife fire dancing) at http://youtu.be/Wicy0B7Ol5Q.

lisp

Comments (3)

Permalink

coroutines in common lisp with bordeaux-threads

Turns out threads are a lot easier without beer and after a good nights sleep.  Following up on last night’s defeat (see coroutines in common lisp), I re-read the documentation this morning and got my locks sorted out.

I now use one lock and two condition variables (CV).  From the bordeaux-threads API docs:

A condition variable provides a mechanism for threads to put themselves to sleep while waiting for the state of something to change, then to be subsequently woken by another thread which has changed the state.

I thought of these CVs like events in Java/C#/Javascript.  Telling one thread to CONDITION-WAIT on a CV is kinda like telling it to listen to that event, and have another thread CONDITION-NOTIFY on a CV is kinda like firing the event.  It took me a long time to understand the importance of CONDITION-WAIT atomically releasing a lock, and reacquiring it before continuing execution in that thread.  That mechanism let me coordinate some sequential execution between the threads, eliminating the race conditions that beat me last night.

I also added the ability to send a value into the coroutine by setting the return value of yield.

I used one CV to tell the coroutine it should run to the next yield, and another CV for the coroutine to tell the caller that a value was ready for it.  I had a few let bindings for my shared memory, closing variables into both the coroutine and caller functions.  The coroutine doesn’t spawn a new thread until the first time it’s funcalled.  I have a somewhat poor mechanism for determining if the coroutine is done; you specify a sigil value and the coroutine yields that as the final value (kind of like eof-value in stream reading functions).  I tried to use thread-alive-p, but ran into race conditions.  I have a few ideas for how to improve that.

Here’s the latest make-coroutine macro and test function:

(defmacro make-coroutine ((&key (coroutine-done-value :done))
			  &body body)
  (alexandria:with-gensyms ((yield-cv "there a value ready for pickup")
			    (run-cv "coroutine should run")
			    (lock "lock")
			    (val "shared memory")
			    (yield-result "return value of yield in the corouting")
			    (thrfn "thread function body"))
    `(let* ((,yield-cv (bordeaux-threads:make-condition-variable
			 :name "yield"))
	    (,run-cv (bordeaux-threads:make-condition-variable
			 :name "run"))
	    (,lock (bordeaux-threads:make-lock "coroutine lock"))
	    ,val ,yield-result
	    (,thrfn (lambda ()	  
		      (flet ((yield (&optional n)
			       (setf ,val n)
			       ;;signal that a value is ready for pickup
			       (bordeaux-threads:condition-notify ,yield-cv)
			       ;;wait for a chance to run
			       (bordeaux-threads:condition-wait ,run-cv ,lock)
			       ,yield-result))
			(bordeaux-threads:acquire-lock ,lock)
			,@body
			(yield ,coroutine-done-value)
			(bordeaux-threads:release-lock ,lock)))))

       ;;function to pull values from the coroutine
       (let ((alive-p T) thr)
	 (lambda (&key (send nil send-suppliedp))
	   (when alive-p
	     (bordeaux-threads:with-lock-held (,lock)
	       (if thr
		   (bordeaux-threads:condition-notify ,run-cv)
		   (setf thr (bordeaux-threads:make-thread
			      ,thrfn :name "coroutine")))
	       
	       (bordeaux-threads:condition-wait ,yield-cv ,lock)

	       (setf ,yield-result
		     (if send-suppliedp send ,val))

	       (when (eql ,coroutine-done-value ,val)
		 (setf alive-p nil)
		 (bordeaux-threads:condition-notify ,run-cv))
	       ))
	   ,val)))))

(defun coroutine-test ()
  (let ((cor (make-coroutine (:coroutine-done-value :done)
	       (yield 1)
	       (yield)
	       (yield 4)))
	(cor2 (make-coroutine ()
		(yield (yield (yield 4)))
		)))
    
    (assert (eql 1 (funcall cor)) )
    (assert (null (funcall cor)))
    (assert (eql 4 (funcall cor)))
    (assert (eql :done (funcall cor)))
    (assert (eql :done (funcall cor)))

    (assert (eql 4 (funcall cor2)))
    (assert (eql 4 (funcall cor2 :send 6)))
    (assert (eql 6 (funcall cor2)))
    (assert (eql :done (funcall cor2)))))

I’ll probably play with it more tonight, maybe put together a stand-alone repo / library.

fun
lisp

Comments (32)

Permalink

coroutines in common lisp

After spending awhile in python land, I wanted to have “yield” in lisp.  After a month or so of stewing, I decided to dive in tonight.  My first stab uses threads, not continuations to accomplish this.  I made that choice partially because I find the arnesi library intimidating (arnesi has continuations in there somewhere), and partially because I wanted to more practice with threads.

I ended up futzing with bordeaux-threads for a few hours, and eventually punted and used a library that had already solved these problems.  My basic test function was:

In retrospect, this may have been a bit pathological.  Virtually no time was spent anywhere, and so everything was happening pretty much at once.

My basic threading approach was to make a reader/writer pair:

  1. run the coroutine (writer) in a thread, and lexically bind yield using a flet such that calling yield set shared memory (with the appropriate locks)
  2. build a lambda (reader) that, when funcalled, waits for the thread to have a value ready, pulls it from shared memory and returns it (with the appropriate locks)

The “with the appropriate locks” bit killed me.  I spent a lot of time in deadlock, and had race conditions everywhere.  I ran into these issues:

  • race condition during startup where the writer thread would start too slowly, missing the notify from the reader to give me a value, and then get stuck waiting for the reader to notify
  • race condition at the end of the coroutine, where the writer thread wouldn’t die fast enough, and the reader would get stuck waiting for the writer to notify
  • many cases where I wanted to CONDITION-WAIT in one thread before I CONDITION-NOTIFY in another, but kept getting it backward.  Adding more layers of locks/condition variables seemed to just defer the problem to another level.

My initial bordeaux-threads version worked great if I ran it from the REPL (with 1+ second pauses for me to run the commands), but the race conditions screwed me when I put it all together.

After a few hours (and a few beers) of debugging, I decided to look at how chanl did it, which rapidly degraded into a chanl-based implementation.  This, of course, took 10m to write and worked great:

For reference, my last broken bordeaux-threads version was:

Fun stuff! Good to know I suck at threads, maybe I’ll take another try with less beer later. At least now I can browse simpy source with less envy.

lisp

Comments (4)

Permalink

more heat-maps using vecto and ch-image

This is a follow-up to my post last year about simplistic heat-maps using Vecto. To recap, I’m trying to make heat maps for google maps overlays.

Here’s how it works in a nutshell:

  1. From javascript I pass to the server the lat/lng region currently shown on the google map, and what size heat map to generate, in pixels.
  2. lisp pulls weights from my database within the given lat/lng region
  3. lisp iterates over the db results, mapping lat/lng to x/y coordinates for the final heat map image
  4. lisp uses the list of mapped (x y weight) to draw the heat map in png
  5. javascript throws the png on top of the google map

I tried a few things based upon the comments I got back from the helpful lisp community.

  • used zpng to get direct pixel access, and calculated each pixel’s color using a weighted average of nearby points using distance.  This didn’t produce good images, and was pretty slow.
  • used zpng to get direct pixel access, and calculated each pixel’s color using the gravity formula against nearby points.  This didn’t produce good images, and was very slow.

I did some more research and learned about the Generic Mapping Tools and bicubic interpolation. The GMT is a set of C programs, similar to the Imagemagick suite.  GMT showed one way to draw heat maps in the Image Presentations tutorial.  It spoke of gridded data sets, and that gave me one more vecto-based idea: split the desired heat-map into a grid and color each square in the grid based upon an average of the weights mapped in that square.  This is a neat effect, but not what I was going for:

This is reasonably fast, taking about 1 second on my dev server.  To quickly find what weights belong in which grid square, I make a spatial index of all the weights, using an r-tree from the spatial-trees library.

The next method I tried was to use interpolation to get a smooth look.  I found Cyrus Harmon‘s ch-image library supports image interpolation, and got to it.  As Patrick Stein noted elsewhere, ch-image isn’t easy to install.  It’s not asdf-installable, and the project page doesn’t list all its dependencies.  For future reference, here’s what I think I needed to install it:

(asdf-install:install "http://cyrusharmon.org/static/releases/ch-asdf_0.2.14.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-util_0.3.10.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/smarkup_0.4.2.tar.gz")
(asdf-install:install "http://mirror.its.uidaho.edu/pub/savannah/cl-bibtex/cl-bibtex-1.0.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/clem_0.4.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-image_0.4.1.tar.gz")

Armed with ch-image, now the drawing process becomes:

  1. draw a small image, coloring pixels based upon weights
  2. enlarge the small image with interpolation

The first step is very similar to the code I wrote to make the grid version above.   Instead of drawing a rectangle, I draw a pixel using ch-image’s pixel access functions.  This was a little weird because ch-image’s coordinate system has 0,0 at the top left of the image.  I’m still not sure how to best choose the size of this smaller image, but ultimately it should depend on my data.  For now I just have it hard-coded be 20x smaller than the desired size:

Yep, that’s pretty small.  Applying a transform to scale it up to the desired size using bilinear interpolation yields:

It looks pretty good and takes about a half-second to draw.  If you click into the larger version, you can see some discontinuities in there, which is a well-known result of bilinear interpolation.  However, based upon other graphics I’ve seen, what I really want is bicubic interpolation.  Luckily, ch-image has this built in:

Oops, maybe not so luckily.  I can certainly see the kinds of look I’m wanting in all the garbled stuff, but ch-image is freaking out somewhere there.

Bilinear it is!  Here’s a screenshot of the overlay in place on the map:

It’s pretty fast, and looks pretty nice, and is fairly close to the look I wanted.  I probably still have some off-by-one errors somewhere, and need to check the git repos for the ch-* libs to see if there might be newer versions than the tarballs I installed.  I still count this as great progress for 5 hours of coding and research.  Huzzah for the much-maligned lisp libraries!

adw-charting
gainesville-green
lisp
vecto

Comments (1)

Permalink

simplistic heat-maps using Vecto

I stole some time from my increasing non-technical workload to play with generating heat-maps of residential energy consumption in my http://gainesville-green.com project.  The initial results are promising:

There are a few neat things going on here.  I’ve got a url handler in my lisp that looks to the query string for lat-lng bounds, image size, and some other variables to generate a PNG file.   I pass that URL to a Google Maps API GGroundOverlay to put the image onto the map.  Add some javascript event glue and I can do cool things like automatically regenerate the heat map overlay when you zoom/pan the map around, and display an animated heat map showing consumption over the course of the year.  There’s still a lot of UI interaction to sort out, but I think it’s a nice approach.

The heat map itself is generated using Vecto, and I think I’m doing it wrong.  I jump through some hoops to map lat-lng to image pixel coordinates, pull from the database, and end up with a list of (x y weight) tuples, with the weight being a number between 0.0 and 1.0 representing the relative consumption of the home that should be at pixel x,y in the result image.  Then I start painting, which is where I think I should be doing more math.  For each point, I pick a color between green and red based on the weight, using the handy cl-colors library to interpolate:

(defun find-color (percent)
  (if (> .5 percent)
      (cl-colors:rgb-combination cl-colors:+green+ cl-colors:+yellow+ (* 2 percent))
      (cl-colors:rgb-combination cl-colors:+yellow+ cl-colors:+red+ (* (- percent .5) 2))))

I actually have to go from green->yellow, then yellow->red, with some goofy adjustments to the percent to make the interpolation work out.  Once I have that, then I have my color, and my pixel, so I can start drawing.  To get a smoother look, for each point I draw concentric circles with different radius and opacity, so each individual data point is rendered like this:

This is enlarged to show some of the blockiness, it ends up looking pretty nice when they are small.  Here’s the actual function:

(defun draw-point (x y color max-radius)
  (iterate (for r from max-radius downto 1 by (max 2 (round (/ max-radius 6))))
	   (for alpha = (/ 1 r))
	   (vecto:set-rgba-fill (cl-colors:red color)
				(cl-colors:green color)
				(cl-colors:blue color)
				alpha)
	   (vecto:centered-circle-path x y r)
	   (vecto:fill-path)))

Max-radius determines how large the largest circle is, and is calculated based on how many points I’m drawing.

There are a few drawbacks to this approach.  First, it’s slow.  Drawing operations aren’t exactly cheap, especially when messing with alpha channels.  It takes me around 5s for 578 data points, which is fine for offline tasks, but on a web-app it needs to be super zippy or you fickle internet folk will close the tab. I also want it to be easy to show animations, so generating a bunch of them quickly would be nice.  The time spent increases fairly linearly with data points, and I’d like to be able to render heat maps for large areas with tens of thousands of data points.  Profiling shows practically all of my time and bytes consed are spent in the draw-point function. UPDATE: after more profiling, vecto:fill-path is most of my time, which makes sense.

Second, I have to be really careful to draw these points from lowest weight to highest weight, because I want red dots to be painted on top of green dots.  It seems like I should decide what color each pixel should be, then draw it once, rather then accumulating the right color in the image canvas.  Right now there’s also some bug with drawing lots of data points, I just get a big green image, when I would expect some reds or yellows.

Another issue is for apartments I have coordinates for the apartment complex, but not each individual unit.  This makes some funny results, like the big orange blob on the right side of the screenshot above where I’ve painted a few dozen points on top of each other.

I did some googling on heat-map algorithms, and found some actionscript and java code, but the actionscript was using a similar approach and the java was incomprehensible.  I think I’ll try making a big array for the result image, and calculating an average weight for each pixel, then loop through that and draw once.  I’m also going to try calculating the weights using magnetic field strength or gravity math.  I think that approach will end up faster, look nicer, and should be a fun problem.

gainesville-green
lisp
vecto

Comments (6)

Permalink

Brian’s functional brain in lisp

Last week I saw a breathless headline on proggit about clojure and Brian’s functional brain: http://blog.bestinclass.dk/index.php/2009/10/brians-functional-brain/, written by Lau.

As a Common Lisp programmer, Clojure irritates me for various irrational reasons.  As an exercise in breaking those down, I ported Lau’s 67 line program (which had no comments) to CL running on SBCL using asdf-installable libraries.  I used lispbuilders-sdl for display and pcall for concurrency.  I ended up with 115 lines, including comments and some significant differences in the program.

I went through a few revisions, initially trying to transliterate the code, looking at the fine clojure API docs to figure out what different things did.  Then I gave up on that wrote more idiomatic (at least for me) lisp, but still resisted the urge to use iterate of alexandria.  I wanted to have code that was as close to the bare language as possible, so I could make an apples-to-apples comparison.  Now that the exercise is done, I think that goal was unattainable.  It’s close, but the differences in the languages are significant, so it’s not an great comparison.

After the first round, I started diverging more from the Lau’s version, looking for higher FPS and nicer lisp.  I ended up with a few major differences:

  1. I used a 2D array to represent the world, the Lau used a single long vector and I didn’t quite understand how it was determining adjacency
  2. I had a lot more functions to abstract out that data structure choice (ie: instead of calling aref everywhere, I made a get-cell function)
  3. Lau called pmap function to calculate each cell’s next value in parallel, and I used pcall to calculate the next whole world state while the main thread rendered.
  4. Lau drew boxes for each rendering loop, I made two SDL surfaces up front and blitted them in at the right spots

I spent a little under 4 hours playing with it, and a lot of that was reading documentation.  I don’t think any conclusions can be made from this for a “common lisp vs clojure” flame war, these are both fairly throw-away pieces of code.  I have no doubt that any experiences lisper or clojurer would find a lot of obvious improvements.

Some of my observations along the way:

  1. getting the lisp libraries to work (which I’ve done in the past) is probably harder than getting clojure working and using java libs.
  2. java libs look like a pain in the ass.  This softens the “and you can use java libs!” selling point of clojure for me.  They’re still java libs.
  3. The places where clojure calls java are kinda ugly, it’s a square peg in a round hole.
  4. clojure has a ton of lazy-evaluation semantics built into the language.  In this case, that seemed to be a bad thing, and most of Lau’s code was calling some wrapper function to say “no really, I want you to actually do this”.
  5. Clojure has more syntax than I thought, using # % [ ] _ to mean different things (maybe in different contexts?).
  6. I’m not sure how the STM features I’ve heard a lot about come into play here, if at all.
  7. I should be asdf loading my libs in a nicer way, right now you need to evaluate those first lines, and then compile the file.  I didn’t have the motivation to create an .asd file or finally learn how to use eval-when properly.
  8. I like long, descriptive function names.  Some of the ones from clojure irriated me: doall, doto.  It reminds me of arc a little.
  9. I was confused by the per-cell parallelism in the clojure version (I think clojure uses native threads in a threadpool).  Pcall does the same thing, but I figured I’d be spending more time context switching than calculating, and it was getting late.

Anyhoo, a fun sunday evening.

Code is on github: http://github.com/ryepup/sandbox/blob/master/brain.lisp

cellular automata
clojure
lisp

Comments (4)

Permalink

talking usb-serial to my arduino from lisp (sbcl) on linux

I got an arduino microcontroller a little while ago, and have played with it a little but found it’s C/C++ development environment annoying.  I wanted to control it from lisp, and that meant serial IO.  Many other languages have special serial libraries you can use, where you instatiate a Serial object with configuration like baud, parity, etc.  John Wiseman wrote arduino_serial.py that shows this pattern.

I searched around for lisp options, and came up with a few options:

  1. open /dev/ttyUSB0 directly (from a comp.lang.lisp thread)
  2. use a FFI wrapper around libusb (from a comp.lang.lisp thread)
  3. use sb-ext:run-program to call out to python/C/whatever to deal with the serial port (we do something similar at work to render trac wiki markup to HTML in lisp)
  4. write a small C program and FFI to that (was tempting for the experience)

After much trial and error and some advice from the helpful folks on #lisp, I got method #1 working tonight.  I was able to read from arduino pretty easily, but I needed to issue this magic stty command before I could write:

stty -F /dev/ttyUSB0 9600 raw -parenb -parodd cs8 -hupcl -cstopb clocal

I had been curious how lisp (or my underlying linux) would know what baud, parity, etc to use, and it makes perfect sense that I need to set these first.  After that, the lisp side ends up pretty simple.  It took a little tweaking to find the right :direction, :if-exists, and :external-format arguments.

(with-open-file (stream "/dev/ttyUSB0"
			:direction :io
			:if-exists :overwrite
			:external-format :ascii)
  (format stream "hello")
  (read-line stream))

Disorganized source is available at http://github.com/ryepup/arduino-experiments.  I have a few servos laying around, maybe this weekend I’ll have time to get lisp moving around the real world.

My dream goal is to have lisp controlling motors that are spinning mirrors to reflect a laser in very particular patterns.  I’d use this on halloween decorations for starters, combining with fog machine/dry ice to create nifty patterns and make people wonder how the hell I did it.  Maybe, if I have the willpower to see that through, then I’ll also hook up a USB camera (using cl-v4l2) and get lisp to track and hightlight objects, augmented-reality style.  That’d be great for table-top games, being able to overlay terrain or effects on a grid mat.

arduino
fun
lisp

Comments (18)

Permalink

new adw-charting release (finally)

Version 0.8 is up on http://common-lisp.net/project/adw-charting/

In this release:

  1. docs that actually match the code – this was the vast majority of recent work
  2. the adw-charting gallery – I’ll be loading this up with more examples as time goes on
  3. separate google / vecto rendering backends
  4. tons of bug fixes
  5. code that sucks less – a lot of this code is from my earlier lisping days, and I’ve learned a lot since then.  Uses more loop / iterate / dolist and less mapcar.  There’s still a lot of spaghetti, but there’s less than before.

Latest tarball is http://common-lisp.net/project/adw-charting/adw-charting.tar.gz.

Have fun, kids!

adw-charting
lisp

Comments (1)

Permalink