DEV Community: Jacek Złydach

Static local variables in Common Lisp

Jacek Złydach — Fri, 10 Jan 2020 23:31:12 +0000

Static local variables are variables with local scope and indefinite extent.
That means, they're accessible only within a specific block of instructions, as if they were regular local variables,
but otherwise they behave like global variables - their memory is allocated just once, and they exist for as long as
they're accessible by the program, retaining their value between subsequent executions of the code that created them.
You may recognize this concept from C/C++:

int test_function() {
  static int counter = 0;
  return counter++;
}

//test:
test_function(); // -> 0
test_function(); // -> 1
test_function(); // -> 2

Static local variables are rarely used, and are becoming increasingly absent in modern programming languages. And for good reasons.
Such variables share the downsides of global variables - they introduce additional hidden state and make the code dangerous to use in
multi-threaded programs. At the same time, they also create another downside: they're lexically scoped to the block of code they're declared in,
meaning they're invisible to the outside world. While a global variable could be explicitly made a part of some module's interface,
a static local variable can't be; it's invisible.

So why did I seek a way to implement them in Common Lisp? It turns out that despite their drawbacks, they're sometimes very useful.
One of such cases is when you want to minimize the number of memory allocations your code does, without impacting its readability.
This is important for writing high-performance software, like video games (and this is where I encountered my own need for these variables).
Static local variables allow a block of code to preallocate its temporary buffers once, avoiding the penalty of repeated reallocation.
Consider:

(defun process-data ()
  (some-level
   (of-processing
    ;;  ...

    (static-let ((query-results (make-array 40000 :element-type 'double-float :fill-pointer 0)))
      (run-a-query "[... some query data ...]" :into query-results)
      (process-results query-results))

    ;; more code
    )))

The STATIC-LET in the code above allocates a QUERY-RESULTS buffer when the function PROCESS-DATA is first executed; subsequent calls to PROCESS-DATA
will not allocate this memory again, making the code effectively non-consing (i.e. not allocating memory).

Why do it this way, instead of using a global variable (or perhaps a class-scoped slot when writing a method)? Because it keeps the declaration
and initialization close to the code that's using it. The variable is still lexically scoped - code outside of STATIC-LET can't get to it,
which partially mitigates the issue of hidden state (in fact, when not used in multi-threaded context, this code would still technically
count as functional programming).

What about the magic 40000? Is it wise to allocate buffers of predetermined size? The answer is, in performance-critical code, absolutely.
Memory is always finite and most software cannot recover when it runs out. Making buffer size explicit is actually the safer choice,
because it forces you to write your code so that it either stays in fixed bounds or gracefully handles memory outage, giving you predictable
memory usage patterns.

After this lengthy introduction, let's look at how you can make static local variables in Common Lisp.

The implementation

(defmacro static-let (vars &body body)
  "Like `LET', but makes `VARS' static (in C language sense).

A static variable is like a global lexical variable, but accessible only within the scope
of the `BODY' form, and it retains value between executions of the `BODY' form. Initial
value of each binding is evaluated only once, the first time `BODY' is executed.

The macro supports optional type declarations; instead of usual binding form
`(VAR-NAME INITALIZER)', use `(VAR-NAME TYPE INITALIZER)' to get automatic type declarations.

Be careful with this macro, as it creates a new set of static variables each time it's expanded.
This macro is not thread safe. Also, avoid recursive execution of `BODY'.
If a static variable is initialized or set to `NIL', it will be reinitialized the next time
`BODY' is executed."
  (loop
     for entry in vars
     for name = (if (consp entry) (car entry) entry)
     for type = (when (and (consp entry)
                           (caddr entry))
                  (cadr entry))
     for initform = (when (consp entry)
                      (or (caddr entry)
                          (cadr entry)))
     for sym = (gensym (string name))
     collect `(,sym (load-time-value (list nil))) into letforms
     if type
     collect `(type ,type ,name) into declforms
     collect `(unless (car ,sym) (setf (car ,sym) ,initform)) into initforms
     collect `(,name (car ,sym)) into macroletforms
     finally
       (return
         `(let ,letforms
            ,@initforms
            (symbol-macrolet ,macroletforms
              ,@(if declforms
                    `((declare ,@declforms)))
              ,@body)))))

It's a relatively simple macro, though it may take a bit to parse. Like a proper LET-style macro, it supports defining multiple
lexical variables in one block and initialize them with values. As a bonus, the variable form may also look like (NAME TYPE INITIAL-VALUE),
which allows me to provide type declarations for the variables in the same place (I tend to like my Lisp thoroughly typed).

Here's an example macroexpansion:

(macroexpand-1 '(static-let ((test-array (make-array 40000 :element-type 'double-float)))
                 (setf (aref test-array 0) 42)))

;;; =>

(LET ((#:TEST-ARRAY730 (LOAD-TIME-VALUE (LIST NIL))))
  (UNLESS (CAR #:TEST-ARRAY730)
    (SETF (CAR #:TEST-ARRAY730)
            (MAKE-ARRAY 40000 :ELEMENT-TYPE 'DOUBLE-FLOAT)))
  (SYMBOL-MACROLET ((TEST-ARRAY (CAR #:TEST-ARRAY730)))
    (SETF (AREF TEST-ARRAY 0) 42)))

The magic which allows to create a static variable is contained in the LOAD-TIME-VALUE form. Quoting the HyperSpec,
"load-time-value provides a mechanism for delaying evaluation of form until the expression is in the run-time environment; (…)
with the result of this evaluation then being treated as a literal object at run time" (emphasis mine, see full documentation for context).

Key words here are "literal object". Literal objects are usually ones you type directly in the source code, like a "string literal", or
'(a quoted form). The details of handling such objects are a bit complicated, but for this purpose, it's sufficient
to say that at some point before the code is executed, literal objects are instantiated, and from that point on, any place in the source code that refers to
such a literal now refers to the particular instance of it. So, from the point of view of the Lisp runtime, before the above macroexpansion is executed,
(LOAD-TIME-VALUE (LIST NIL) has already been replaced by a reference to a particular empty cons cell. This cons cell is our static local variable.

The rest of the macroexpansion executes normally. There's a test that guards the code setting the CAR of the cons cell to the result of initialization form for our static
variable, which ensures that the initialization happens the first time control flows through this block of code. Then, there's a SYMBOL-MACROLET that ensures our
variable is accessible for both reading and writing under the name given to it in STATIC-LET form (this is the standard Common Lisp idiom for when you want to
make a bit of code present itself as if it was just a variable).

Why the empty cons cell, you may ask? Why not put the initialization form into the LOAD-TIME-VALUE directly? The reason is, the evaluation of that form happens
well before runtime, so if you compile the file (with a COMPILE-FILE call), the actual result of the initialization form may end up encoded in the compiled file.
In our example above, that would be 320KB worth of floats, and in practice this may easily run into hundreds of megabytes of data that will end up
stored in the compiled file (or dumped Lisp image). So instead, STATIC-LET only allocates an empty cons cell, a minimal literal object that can
store a reference to the data initialize at runtime.

(When delivering executables, one must remember to never call the functions using STATIC-LET before dumping the Lisp image; otherwise, the initialized data
will end up being stored in the image file in full form. Also note that this implementation has one caveat: if, at any point, the variable is set to NIL,
it will be reinitialized the next time control goes through STATIC-LET. This behavior deviates from what C/C++ does, and it could be corrected with little extra
work, but I deemed it not worth it.)

Let's verify STATIC-LET works as described:

(defun test-static-let ()

  (format t "~&Executing test.")

  (static-let ((test-counter (progn (format t "~&Allocating counter.")

                                    0))

               (test-array (progn (format t "~&Allocating array.")

                                  (make-array 40000 :element-type 'double-float))))

    (incf test-counter)

    (incf (aref test-array 0))

    (format t "~&Counter: ~A, array's first element: ~A" test-counter (aref test-array 0)))

  (format t "~&Test done."))

(loop

   repeat 3

   do

     (test-static-let))

Executing test.

Allocating counter.

Allocating array.

Counter: 1, array's first element: 1.0d0

Test done.

Executing test.

Counter: 2, array's first element: 2.0d0

Test done.

Executing test.

Counter: 3, array's first element: 3.0d0

Test done.

Alternative approaches

Hanging the static variable off a cons cell allocated by LOAD-TIME-VALUE is what I found to be the best way to implement it, but it's not the only way.
Alternative approaches include:

redefining the entire function using static variables as closure, with static variables being regular lexical variables over which that function closes;
keeping a global hash table for "static" variables, and using unique symbols (generated by GENSYM) as keys;
creating each such variable as DEFVAR, with an unique name generated by GENSYM (an approach taken by with-c-syntax);
attaching the variable into the property list of a symbol generated by GENSYM.

All these approaches have certain drawbacks. The closure approach requires change to the very function definition (a macro can't just hoist
the code it generates into the surrounding context). Global hash table, magic defvars and property lists all are technically accessible
from the outside, and come with small performance penalties. Overall, despite the caveat with NIL values (which is entirely due to my
~~laziness~~ thoughtful engineering decision), I prefer the LOAD-TIME-VALUE approach.

Algebraic Effects - You Can Touch This!

Jacek Złydach — Wed, 24 Jul 2019 12:20:00 +0000

An article by Dan Abramov (of React fame) has been making rounds today on the Internet. It introduces readers to a body of theoretical work called "algebraic effects", providing an overview and a set of examples of how these ideas could be implemented in hypothetical extension to JavaScript.

What jumped at me in this article were two things. First, that the article claims this field of work is still theoretical, "only supported by a few languages that were created specifically to explore that idea" and definitely not production-ready. Second, that I've seen code like the article's examples before - in fact, I write similar code frequently, both in professional and hobby settings. The presented examples are a JavaScript pseudocode version of the Common Lisp's conditions and restarts system.

To be completely honest: I'm not familiar with the body of work under the name of "algebraic effects", though I've learned it has a larger scope than what's described here and in the original article (see remarks at the end of this post). However, Dan's article describes a subset that's in actual, practical use, so this is what this article focuses on.

Conditions and Restarts

Conditions and restarts are kind of like try/throw exception handling you know from more mainstream languages, except much more powerful. It's not meant for just handling errors, but any kind of flow, in which some communication up and down the call stack must occur.

To quote from an excellent introduction in Practical Common Lisp:

The condition system is more flexible than exception systems because instead of providing a two-part division between the code that signals an error and the code that handles it, the condition system splits the responsibilities into three parts--signaling a condition, handling it, and restarting.

(…) you could use the condition system to allow a low-level function to detect a problem while parsing a log file and signal an error, to allow mid-level code to provide several possible ways of recovering from such an error, and to allow code at the highest level of the application to define a policy for choosing which recovery strategy to use.

I won't try to summarize PCL here, but I want to introduce some vocabulary:

condition - is an object that represents some "situation" - i.e. something of note that's happened, but not necessarily an error
signal - quoting from CLHS, "v. to announce, using a standard protocol, that a particular situation, represented by a condition, has been detected"
handler - a function that receives a condition, and can somehow handle it (e.g. by invoking a restart), or decline and just pass the condition on
restart - quoting again, "represents a function that can be called to perform some form of recovery action"

Outside of Lisp, conditions are usually known as exception objects, signaling is done by throw, and restarts and handlers are bundled together as catch & finally blocks.

For more details, head on to the PCL chapter I linked above.

Error handling example

I'm not going to repeat the original article here; it's really worth a read anyway. What I'll do instead is show you how the example from would be done in Common Lisp, where it's not pseudocode but a real, fully supported, ANSI-standardized feature.

;;; Bookkeeping, to make the example compile and run.
(define-condition ask-for-name () ()
  (:documentation "A mock condition that means a name needs to be provided."))

(defun name (user)
  "Reader for name of `USER'."
  (car user))

(defun friend-names (user)
  "Reader for a list of names of friends of `USER'."
  (cdr user))

(defun (setf friend-names) (new-value user)
  "Setter for `FRIEND-NAMES'."
  (setf (cdr user) new-value))

;;; A helper macro wrapping an idiom allowing to do a test and request a new value if test fails.
(defmacro ensure (test place condition)
  "If the `TEST' fails, signal a `CONDITION', with a restart `USE-VALUE' ready for a new value."
  `(restart-case
       (unless ,test
         (signal ,condition))
     (use-value (new-value)
       (setf ,place new-value))))

;;; Implementation of the first example from the original article
(defun get-name (user)
  (let ((name (name user)))
    (ensure (not (null name)) ;Just NAME would suffice, but spelling it out for clarity.
      name
      'ask-for-name)
    name))

(defun make-friends (user-1 user-2)
  (push (get-name user-2) (friend-names user-1))
  (push (get-name user-1) (friend-names user-2)))

(let ((ricky (cons nil nil))
      (bubbles (cons "Bubbles" nil)))
  (handler-bind ((ask-for-name (lambda (c) (use-value "Ricky" c))))
    (make-friends ricky bubbles)
    ;; Let's return the two objects for the sake of REPL output.
    (list ricky bubbles)))

    ;;; REPL output:
    ((NIL "Bubbles") ("Bubbles" "Ricky"))

The part:

if (name === null) { name = perform 'ask name'; }

is implemented by the ensure form, which performs the test and ensures a restart named use-value is in place to externally set the value of a passed place (e.g. variable). This small utility essentially works as a simplified Common Lisp's assert macro, except the latter forces you to specify the new value(s) interactively (in fact, you could rewrite this code to work with Lisp's interactive debugger by changing ensure to assert, and (use-value "Ricky" c) to (continue c).

The handle (effect) { ... } part is entirely handled by handler-bind Common Lisp form - its job is to bind functions to handle particular signals coming from the code it encloses. You can see it matches ask-for-name condition we've defined earlier, and to handle it, it calls use-value. use-value is a Common Lisp built-in for invoking a restart named use-value (it's not an uncommon thing to do), but if such a built-in wasn't provided, you'd rewrite the handler-bind as follows:

(handler-bind ((ask-for-name (lambda (c)
                               (let ((restart (find-restart 'use-value c)))
                                 (when restart
                                   (invoke-restart restart "Ricky"))))))
  (make-friends ricky bubbles)
  ;; Let's return the two objects for the sake of REPL output.
  (list ricky bubbles))

That is, you can find and invoke programmatically any restart that was installed when the condition was signaled. Common Lisp just provides a shorthand, functional interface to common restarts abort, continue, muffle-warning, store-value, and use-value.

Beyond errors

As said before, conditions/restarts system can be used for more than just an error handling. The second example from the article demonstrates something that's essentially dynamic binding for function names, which can be done in Common Lisp in a different way (and arguably should), albeit with some work. Clojure - another Lisp - provides a nice built-in tool for that: with-redefs-fn.

So instead, let me describe an example I initially posted on HN, of how you can use conditions and restarts to implement progress reporting and aborting of a long-running calculation, possibly in interactive / GUI context.

(define-condition progress ()
  ((amount :initarg :amount
           :reader amount
           :documentation "How done is the operation, [0..1]."))
  (:documentation "A condition signaled by long operations that report progress."))

(defun process-partial-data (data)
  (declare (ignore data))
  ;; Some data processing here.
  )

(defun process-data (data)
  (restart-case
      ;; Main flow
      (loop
         ;; Report that we've started
         initially
           (signal 'progress :amount 0)

         ;; Perform the data processing
         with total = (length data)
         for datum in data
         for i below total
         do
           (process-partial-data datum)
           (signal 'progress :amount (/ i total))

         ;; Report that we're done
         finally
           (signal 'progress :amount 1)
           (return :done))
    ;; Restart flow
    (abort-work ()
      (format *trace-output* "Aborting work!")
      :failed)))

The "business meat" of our function is the loop form. You'll notice it reports its progress by signaling a progress condition which, without installed handlers, is essentially a no-op (unlike throwing an exception). The "meat" is wrapped in restart-case form, in order to provide an alternative flow called abort-work.

Let's look at some REPL session logs (-> denotes returned result, to differentiate it from printed output). First, regular use:

CL-USER> (process-data '(1 2 3 4 5 6))
-> :DONE

Let's simulate a GUI progress bar, by actually listening to the progress condition:

CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p)))))
           (process-data '(1 2 3 4 5 6)))

Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Progress: 0.6666667
Progress: 0.8333333
Progress: 1.0
-> :DONE

Let's simulate user pressing a "Cancel" button by assuming that it was clicked around the 50% progress mark. We can do that through invoking the abort-work restart programmatically:

CL-USER> (handler-bind ((progress (lambda (p) (format *trace-output* "~&Progress: ~F~%" (amount p))
                                                (when (>= (amount p) 0.5)
                                                  (invoke-restart 'abort-work)))))
             (process-data '(1 2 3 4 5 6)))
Progress: 0.0
Progress: 0.0
Progress: 0.16666667
Progress: 0.33333334
Progress: 0.5
Aborting work!
-> :FAILED

As pointed out under my original example, in real use you'd want to hide this mechanism under a macro. It's fairy easy to write one, for instance:

(defmacro dolist-with-progress-noted ((datum data return) (&key on-abort) &body body)
  (alexandria:once-only (data)
    (alexandria:with-gensyms (total i)
      `(restart-case
           (loop
              initially
                (signal 'progress :amount 0)

              with ,total = (length ,data)
              for ,datum in ,data
              for ,i below ,total
              do
                ,@body
                (signal 'progress :amount (/ ,i ,total))

              finally
                (signal 'progress :amount 1)
                (return ,return))
         (abort-work ()
           ,on-abort)))))

Now the following code expands to the original example above:

(defun process-data (data)
  (dolist-with-progress-noted (datum data :done)
      (:on-abort (progn (format *trace-output* "Aborting work!") :failed))
    (process-partial-data datum)))

Parting thoughts

On HN thread it's been pointed out that algebraic effects as a concept is larger than what Common Lisp can support. So it might be; I don't know much about the scope of the theoretical work there. The missing ingredient is implied to be "continuations", which are not supported in Common Lisp. However, Scheme family of Lisps has continuations. And apparently conditions. In the highest of Lisp traditions, they should be able to incorporate whatever other clever ideas come out of algebraic effects work.

So, it turns out, you absolutely can touch this, and could for the past 30+ years (or more), in a production-ready environment. I'm happy to see the JavaScript community rediscovering forgotten techniques of the programming art, but before people jump to writing their own DSLs for the JS transpilers, I implore you - please at least take a look at how it has all been done successfully in practical languages, and heed the lessons their communities learned.

(Originally published on my blog. Who do I ask to get dev.to to enable syntax highlighting for Common Lisp code?)