Thursday, January 5, 2017

Lisp, L stands for Leverage

There's seems to be a lot of confusion among non Lispers about the reasons why so many otherwise seemingly intelligent coders swear by this funny looking curiosity from the 70's. And the name keeps popping up; from Emacs, that's primarily coded in it's own flavor of Lisp; to JavaScript that borrows most of it's power from Lisp.


It's about Leverage, period. Lisp was created to make it possible to solve very complex problems, problems so complex that holding back any power from users would have rendered the result useless. The designers of Lisp went all in to provide the best tool set they could imagine for solving the most complex problems they could imagine, and mostly managed to leave egos on the shelf while doing so. The reason it isn't changing much is because it's a masters tool set, forged from an ocean of experience; the types of software people build in Lisp change at least as fast as the rest of the world.


Memoization is the idea that it might be worthwile to cache the results of an expensive, potentially parameterized computation. This rest of this post describes an implementation of general purpose memoization in Common Lisp.


To begin with, we need somewhere to index memoized results on computation and parameters. A closure would do for simple cases, but in more complex scenarios user code commonly needs more control over the cache. We could give up and pass contexts around explicitly; but in Lisp circles this kind of manual, repetitive work is generally frowned upon. Instead, we will store the context in a special variable. Special variables are global variables done right. Binding one affects the entire call stack originating from the binding, regardless of depth; and nothing else. We provide a default binding to make simple trivial.


Next question is how to model parameterized computations. The obvious answer is to use functions, and we will provide a functional interface either way; but we can generalize that further with a macro. This allows specifying a condition and handing back flow control to user code.

Given the macro, implementing a functional interface on top is effortless:


A full implementation of these ideas and more may be found here.

peace, out