Category Archives: programming

Continuous v.s. Batch: The Census

Log, from Blamo: Civil War Reenactor

Log, from Blamo: Civil War Reenactor

I am enjoying this extremely long blog post about how logs can form the hub for a distributed system, by Jay Kreps from Linked-in.  It’s TLMR “too long, must read?”  It reminds me of my post about listening to the system, but more so.

He has a wonderful example of batch v.s. continuous processing.  A dialectic worthy of its own post at some point.

The US census provides a good example of batch data collection. The census periodically kicks off and does a brute force discovery and enumeration of US citizens by having people walking around door-to-door. This made a lot of sense in 1790 when the census was first begun. Data collection at the time was inherently batch oriented, it involved riding around on horseback and writing down records on paper, then transporting this batch of records to a central location where humans added up all the counts. These days, when you describe the census process one immediately wonders why we don’t keep a journal of births and deaths and produce population counts either continuously or with whatever granularity is needed.

Cute.  My goto example has always been the difference between the annual cycle(s) that arises from agriculture and tax law revisions v.s. the newspaper’s daily cycle in service of the demand for fish wrapping.

jobscalculatedriskBut of course that’s not really continuous, it’s just batch with different cycle times.  And yet I once encountered a continuous system that involved a pipeline across a desert.  Each time the sun would emerge from behind the clouds the pipe would warm up and a vast slug of material would be ejected out the far end into a hastily build holding pit at the refinery.  Maybe slug processing would be a good fall back term for the inevitable emergence of  batches in continuous systems.  Blame the clouds.


Tasty Languages

haggisMy mother, or so I am told, had a device for dealing with that frustrating syndrome where you wake up in the middle of the night and your damn brain decided to tour all the things that are making you anxious.   The trick was to try and enumerate something, for example vegetables in alphabetical order.

So I’ve be trying this out but I needed something to enumerate.  At first I was enumerating foods, and then I started adding constraints.  … gizzards, haggis, intestines, …   Then I started enumerating programing languages: APL, Basic, C, Datalog, …   But it was became fun to try and include a language only if it has some aspect that makes me smile.  For example the function calling weirdness in SL5.   Elang is a layer cake of odd smilies, though then I can’t use E.  R is a must have for how evaluates function arguments.

You might pick Caja[1,2] for C.   And that lead me to recall Dart.  I’ve been meaning to go back and see what’s up with Dart.   This talk is a fascinating entry point into Dart, at least for me.  Google managed to find a good guy, Gilad Bracha, for this design challenge!

For the me the tasty thing in this talk is that they are trying to stand in the middle ground between a dynamically typed language and something, well, something else.

This decades after what Common Lisp did about this problem.  In Common Lisp you can declare that something is, for example, a small integer; but the programming environment can ignore that; it’s just advice.  In fact even in a single language environment how that statement effects things can vary depending on other stuff like optimization settings.   If you implementation ignores the declarations then they practically comments.  I think it was an Algol manual that documented comments by saying “the compiler makes no effort to check the correctness of the comments.”  This wiggle room makes some people’s skin crawl.  And, it’s certainly enticed a lot of engineering effort on the part of Common Lisp implementors.

In fact a Common Lisp programmer can do wonderfully weird things with the type system and declarations.  For example we can define a type that asserts our graphs are acyclic and provide a predicate that we only use in desperate situations.

(defun acyclic-graph-p-for-type (g)  (if *desperate-debug* (acyclic-graph-p g) t))

(deftype acyclic-graph () (and graph (satisfies #'acyclic-graph-p-for-type))

The reason I found that Dart talk so interesting is the how Gilad deals with the skin crawling issue. He adopts a war weary Eeyore-ish manner.  I can totally relate.  He makes no real effort to argue why this is a useful such a powerful and useful approach.  In fact I’d say he baits his audience into an absence of sympathy.

I’ve done some very fun things with type systems that are analogous to what he is calling optional typing, for example this diagnostic typing I described a while back.

I’ll have to dig some more to see if any of the Caja ideas survived into Dart.  But they are similar, in the sense that there turn out to be many type system like blankets one might want to throw over your program to make you feel more cozy.  And if you insist that on exactly when in the program life cycle, if ever, they are checked (or worse proven) it’s just not as much fun.

The talks also made me sad.  It’s clear there is a lot of language design argot that I haven’t kept up with.

… junket, keratin, …

Using the Referer header in Authentication

My blog got hacked again yesterday.  Luckily my automation caught it within the hour and I cleaned it up a few hours after that.   It remains a mystery how they got in.  (Update: I’m an idiot and there was an extra testing account that was poorly provisioned.)   I can see signs of a short brute force attack attempting to login in the right time frame.  But I doubt that worked.  I have exceptionally obscure passwords, and I use two factor authentication

But this got me thinking about assorted other ways I could make login a bit more secure.  I could limit which IP address are allowed in.  I could require that the client present a cookie.  There are lots of other standard hacks (and they are hacks) for tightening this up.  Rate limiting is always fun.

But I had a fun idea that I want to share.  What required that the login attempt include a Referer header.   It would be a huge inconvenience to route all my login attempts thru one of my private personal pages.

I know, it’s just security by obscurity, but even sightly unusual authentication requirements will frustrate the script kiddies.

We can make it better than that.  What if we embed a one time key into the header?  For example using TOTP, i.e. what Google Authenticator uses for two factor authentication.  That wouldn’t be very hard to implement.  And, if your feeling your oats you could delegate all the authentication to the site you’re routing your access thru.

You could make a browser plugin that injects this authenticating header when ever you visit certain urls.  And, of course, there isn’t any particular reason to use the Referer header at that point.  Obviously a plug-in of that kind could support a helpful scheme for provision the TOTP setup.

Quicklisp new packages, October 2013

Xach has announced the the October 2013 quicklisp release.  Below are short summaries of the new packages.

asdf-package-system 2K -- No license specified?
  No description provided.
  git: git://

ayah-captcha 4K -- MIT
  A simple interface to the API of the play-thru captcha of
  author: Andy Peterson

cl-binaural 4K -- GPL
  Utilities to generate binaural sound from mono
  author: Alexander Popolitov

fgraph 6K -- EUPL V1.1
  No description provided.
  author: Thomas Bartscher

cl-larval 20K -- GPL
  Lisp syntax for assembler for AVR microcontrollers
  author: Alexander Popolitov

cl-ply 10K -- LLGPL
  A library to handle PLY file format which is known as the Polygon File Format or the Stanford Triangle Format in Common Lisp.
  author: Masayuki Takagi

cl-server-manager 5K -- MIT
  Manage port-based servers (e.g., Swank and Hunchentoot) through a unified interface.
  author: Wei Peng

cl-spark 10K -- MIT License
  Generates sparkline string for a list of the numbers.
  author: Takaya OCHIAI

curry-compose-reader-macros 2K -- GPL V3
  reader macros for concise function partial application and composition
  author: Eric Schulte

drakma-async 26K -- MIT
  An asynchronous port of the Drakma HTTP client.
  author: Andrew Danger Lyon

draw-cons-tree 2K -- Public Domain
  Makes and ascii picture of a cons tree
  author: Ported by:CBaggers - Original Author:Nils M Holm

filtered-functions 5K 
  An extension of generic function invocation that add a preprocessing step before the usual dispatch.
  No description provided.
  author: Pascal Costanza

graph 37K -- GPL V3
  Simple library for building and manipulating graphs.
  author: Eric Schulte, Thomas Dye

lisphys 19K -- Specify license here
  Describe lisphys here
  author: Guillaume

mailbox 2K -- MIT
  Simple multithreading mailboxes.
  author: Lucien Pullen

map-set 2K -- BSD 3-clause (See LICENSE)
  Set-like data structure.
  author: Robert Smith

cl-oneliner 3K -- wtfpl
  Given a piece of text, summarize it with a one-liner
  author: mck-

pooler 4K -- MIT
  A generic pooler library.
  author: Abhijit Rao

readable 443K -- MIT
  'Readable' extensions to Lisp s-expresions: curly-infix, neoteric, and sweet expressions
  author: David A. Wheeler
  git: git://

simple-currency 13K -- BSD, 2 clause.
  Currency conversions using data published daily by the European Central Bank.
  author: Peter Wood

smackjack 17K -- MIT
  A small Ajax framework for hunchentoot using parenscript
  author: Andy Peterson

snappy 7K -- New BSD license.  See the copyright messages in individual files.
  An implementation of Google's Snappy compression algorithm.
  author: Robert Brown

spellcheck 2,376K -- MIT
  Peter Norvig's spell corrector.
  author: Mikael Jansson

tagger 1,107K -- No license specified?
  No description provided.

As usual many older packages were revised.

emacs w3m about pages

If you use w3m within emacs you might be interested to know you can do this:

(defun w3m-about-foobar (&rest args)
  "Hang a emacs generated page on this url: about://foobar/"
    (format "<p>This is so exciting, you have %d buffers!</p>"
            (length (buffer-list))))
  (insert "<img src=\"\"/>")

Which means you can build entire pseudo web sites that are local to your emacs :).

I got to wondering about how I might do this because I use w3m to view Lisp documentation[1], and I have this little slime contribution (slime-documentation-search.el) that adds an easy way to search  As you can see if you look there are at least four alternatives to; and I’ve been wondering if I could puzzle out a way to create little website that would let you browse between them.

The trick above looks like it could help, but the obvious approach doesn’t work because w3m doesn’t support iframes.  Exercise for the reader, I guess.

Plot Window #3

Another batch of improvements in plot-window.  Plot-window is not, as yet, intended for other people’s use.    It provides a bridge between Lisp and assorted Javascript widgets.  The original idea was to allow a web page to be used as a display from the Lisp REPL.  So, for example, to enable you to plot data using a Javascript plotting widget.

Most of the changes are internal.  For example I’m toying with a way to manage Parenscript modules (example module here).  I’m also using the LOG4CL, which I highly recommend.

All the widgets have now been factored out into individual examples.  Previously using a widget rewrote the display page entirely.  Now they are inserted at an insertion point.  Here’s a little screen capture…



One project I’ve been doing while unemployeed is to review how the Common Lisp landscape has changed since I was last paying attention. And the big change is the emergance of a rapidly growing pool of libraries (900+) all distributed via Quicklisp.

My current favorite is a library called Optima. Optima adds constructs for doing rich pattern matching. It can match lists, arrays, objects, structs, strings; and if you load fare-quasiquote you can write patterns using backquote.

Let’s build a JavaScript to Parenscript translator. First we can use a Javascript parsing library.

> (ql:quickload '("optima" "fare-quasiquote" "parse-js" "parenscript"))
> (defpackage #:js2ps (:use #:cl #:optima #:parenscript #:parse-js))
> (in-package #:js2ps)
> (pprint (parse-js "a[3] += f(x,y)")))
   (:assign :+ 
      (:sub (:name "a") (:num 3))
      (:call (:name "f")
       ((:name "x") (:name "y")))))))

Then we can write a recursive function using Optima to translate that into parenscript like so:

(defun js2ps (txt)
      ((r (x)
         (match x
           (`(:toplevel ,stms)         `(progn ,@(mapcar #'r stms)))
           (`(:stat ,s)                `(progn ,(r s)))
           (`(:assign :+ ,left ,right) `(incf ,(r left) ,(r right)))
           (`(:call ,func ,args)       `(,(r func) ,@(mapcar #'r args)))
           (`(:name ,name)             (js2ps-name name))
           (`(:num  ,n)                n)
           (`(:sub ,array ,index)      `(aref ,(r array) ,(r index)))
           (eck (error "TBD ~S" eck)))))
    (r (parse-js txt))))

Let’s try it, and then using ps* we can have parenscript translate it back into Javascript.

js2ps> (js2ps "a[3] += f(x,y)")
(progn (progn (incf (aref a 3) (f x y))))
js2ps> (ps* *)
"a[3] += f(x, y);"

You have already noticed that the patterns look just like the code for building the result. Pretty eh?

A complete translator is easy. The fiddly bits arise around handling variable bindings and around what in Parenscript are called @ and chain. There code here that does much of that.

I’ve also used Optima is to scrap web pages. It’s trivial to load and parse an page into an s-expression, just quickload “drakma” and “closure-html”, and then do (parse (http-request url) (closure-html:make-lhtml-builder)). Then let’s say you wanted to know the prices that macbook airs have sold for on ebay.

 (defun snarf-prices (page-sxpr)
  ;; for example: (snarf-prices (fetch-price-page "macbook air 13" 3))
  (labels ((recure (x)
             (match x
               (`(:div ((:class "g-b bidsold") (:itemprop "price"))
                       ,(ppcre "\\$([\\d.]+)" price))
                 (push (parse-number price) result))
               (`(,(satisfies keywordp) _ ,@children)
                (map nil #'recure children)))))
     (recure page-sxpr)
     (nreverse result))))

The second pattern match `(,(satisfies keywordp) _ ,@children) uses two new tricks. The statisfies shows how we can put arbitrary predicates into your patterns, and the _ is a wildcard.

The first pattern shows how to match strings to regular expressions. The pattern (ppcre “\\w*\\$([\\d.]+)” price) would match the string
” $647.10″ and binds price to the string “647.10”.

The code for an earlier version of this page scraping example can be seen here.

One problem with Optima is that it’s a bit addictive. Once you start using it you stop using lots of other techniques. For example I hardly ever use cl-ppcre directly anymore. For example if I want to pluck the host out of some URLs I’ll write: (match url ((ppcre "//([-_.\\w]+)/" host) host)). It also lets me write code in the style of awk or perl, i.e. with a set of pattern matches.

And I should have mentioned, it expands into pretty good raw code. I say pretty good rather than great because it doesn’t currently factor out common subexpressions.

So try it out, you’ll like it.

Quicklisp new packages, June 2013

Summary of the new packages in the new release of Quicklisp.

big-string -- BSD 3-clause (see LICENSE)
  Big strings, similar to Java's StringBuilder.
  author: Robert Smith

cl-css -- MIT-style
  Simple inline CSS generator
  author: Leo Zovic
  git: git://

cl-curlex -- GPL
  Leak *LEXENV* variable from compilation into runtime
  git: git://

enchant -- Public Domain
  Bindings for Enchant spell-checker library

cl-geoip -- WTFPL 2.0
  Wrapper around libGeoIP
  git: git://

cl-performance-tuning-helper -- MIT
  A simple performance tuning helper tool box for Common Lisp
  author: SUZUKI Shingo
  git: git://

tcod -- No license specified?
  Common Lisp bindings for libtcod, a truecolour terminal-emulation
  library written in C.

cl-template -- MIT
  A simple output-agnostic templating system for Common Lisp.
  git: git://

clache -- LLGPL
  A general caching facility for Common Lisp with an API is similar
  to a hash-table.
  author: Tomohiro Matsuyama
  git: git://

clinch -- BSD
  Simple 3d graphics engine for Lisp.
  author: Brad Beer (WarWeasle)
  git: git://

clite -- ISC
  Lite weight testing framework
  git: git://

clobber -- No license specified?
  A alternate approach to persistance based on transaction logging.
  git: git://

delorean -- No license specified?
  Delorean is a time machine for unit tests
  author: Andy Chambers
  git: git://

generators -- BSD
  A common lisp package providing python style generators based
  on delimited continuations
  git: git://

gettext -- GNU Lesser General Public Licence 3.0
  A port of gettext runtime to Common Lisp
  git: git://

inner-conditional -- LLGPL
  Series of macros which optimizes out the inner conditional jumping
  author: Masataro Asai
  git: git://

lowlight -- MIT
  A simple and flexible syntax highlighter
  git: git://

new-op -- No license specified?
  Provides (new <type>) -> new instance of type, and more.
  git: git://

petit.package-utils -- MIT
  petit tool box for packaging
  author: SUZUKI Shingo
  git: git://

policy-cond -- Public Domain
  A macro to insert code based on compiler policy.
  author: Robert Smith

pretty-function -- No license specified?
  Scheme to enable nicer printing of closures and other pure functions.
  git: git://

rectangle-packing -- LLGPL (but he's flexible, so ask)
  Code to pack rectangles into a bigger rectangle.  Useful for
  texture packing for OpenGL.
  git: git://

stmx -- LLGPL
  Composable Software Transactional Memory
  author: Massimiliano Ghilardi
  git: git://

track-best -- Free
  Macros/functions for tracking the best items.

treedb -- MIT
  A hierarchical key-value-database
  git: git://

utilities.print-items -- LLGPLv3; see COPYING file for details.
  This system provides some generic condition classes in
  conjunction with support functions and macros.
  git: git://

weblocks-stores -- LLGPL
  A base for weblocks stores
  author: Olexiy Zamkoviy
  git: git://

weblocks-utils -- Public Domain
  Utils for weblocks framework
  author: Olexiy Zamkoviy
  git: git://

cl-interpol and parenscript

Cl-interpol adds Perl style interpolated strings to Common Lisp. For example:

#?"The result is ${(let ((y 2)) (+ x y))}"
"The result is 42"

Cl-interpol works by defining a reader macro, i.e. #?”…”. For personal reasons I don’t like reader macros so I wrote a quick macro to avoid them.

(defun interp% (str)
  "Avoid the need to use a unique read table."
  (assert (stringp str))
  (with-input-from-string (s str)
    (cl-interpol::interpol-reader s #\? nil)))

(defmacro interpolate (str)
  (interp% str))

Which lets you write:

 (interpolate "{This string appeared in package: ${(package-name *package*)}.}")

Like any self respecting Lisp code cl-interpol avoids interpreting the string at runtime, instead it converts the interpolated string into code. For example that last example expands into:

(with-output-to-string (#:g13131)
  (write-string "This string appeared in package: " #:g13131)
  (princ (progn (package-name *package*)) #:g13131)
  (write-string "." #:g13131))

I started using cl-interpol because somebody suggested it as yet another way to generate HTML. The Lisp community as a few templating languages for this kind of thing.  Who doesn’t?  The more popular of these have mimics in Parenscript.

Parenscript, you will recall, is a thin gloss over Javascript that enables you to write your Javascript using s-expressions which are then converted into Javascript before delivery to the browser.

So I wanted that for cl-interpol as well. So I wrote something that translates the expanded code into parenscript.

As in the example above the output of cl-interpol’s expansion is always a with-output-to-string form, so my hack consists of a parenscript macro for with-output-to-string which then walks the enclosing form converting it into parenscript and then into javascript. For example:

This parenscript:

(let ((x 40)) (interpolate "{How about ${(+ x 2)}.}")))

becomes this javascript:

(function () {
    var x = 40;
    return ['How about ', String(x + 2), '.'].join('');

Cl-interpol has lots of features, and I certainly do not handle things it can do. I’ve only covered cases as I need them. But I’ve found it useful.

More widgets in plot-window.

Here’s another video showing a bit more progress on my hack that allows you to use a browser as a place to display output from your Common Lisp REPL.  I’ve been playing with various javascript widgets.  Here the demo routine shows:

  1. Using JQuery to animate the color of a small rectangle.
  2. A rich WYSIWYG text editor.  This one’s called nicedit.   There are dozens of these.
  3. Mapping via mapstraction, which provides a provider independent mapping widget, in this case I’m using open street maps as a provider.
  4. A tool that does syntax highlighting, i.e. it displays source code with pretty colors.

The initial plot is unchanged from my earlier posting.  You might want to watch this full screen…

Getting these to work isn’t terribly hard, but it’s slightly harder than I’d expected since most of them don’t expect to be loaded dynamically as I’m doing here.

The code running in this demo is in the dev branch over at github, but there is an odd bug I haven’t tracked down yet. Pretty soon I’ll need to change the name 🙂