THE CLAST (Common Lisp Abstract Syntax Trees) Library

One of the most mysterious and underused thing in Common Lisp programming, at least in the opinion of the writer, is that of code walker, often implemented with a function called walk.

However, few portable and usable implementations of such concept exist, despite its obvious usefulness. One simple use of such a functionality would be, as an example, to find the free variables in a given piece of code.

cl-prompt> (find-free-variables '(let ((x 42)) (+ x y)))
(Y)

The function find-free-variables would parse the form and extract the free variables. This is, at best, 1980s stuff, and yet, it is difficult to do in Common Lisp in a lispy way.

The reasons for this state of affairs are many, but two main ones may be cited.

The CLAST library addresses these two concerns, by insisting that an extensive abstract syntax tree library for Common Lisp is useful per se, and by insisting that leveraging the environment machinery is a good thing (despite the lack of implementation support).

Of course, there are other libraries out there that solve similar problems (BESE ARNESI WALKER, CL-WALKER and many other ones, many appeared after the release of the first CLAST); they are all fine libraries but, as usual, this writer suffers from idiosyncrasies and NIH syndrome. Plus, CLAST is released under a BSD license.

The name CLAST is apt, as it reminds us of clastic rocks, i.e., "rocks that are composed of fragments, or clasts, of pre-existing minerals and rock". In other words, Common Lisp rocks!

Abstract Syntax Trees in Common Lisp

The CLAST library provides a number of facilities to produce an abstract syntax tree (AST) of a piece of CL code.

An AST produced by CLAST is a regular "tree" where nodes are instances of subclasses of the FORM class. The ASTs are produced by invoking the PARSE.

cl-prompt> (clast:parse 'x)
#<FREE VARIABLE REF X 24ECDAF7>
NIL

cl-prompt> (clast:parse '(loop for i in '(1 2 3)
                               count (oddp (+ qd i)) into odds))
#<LOOP-FORM  24ECE77F>
NIL

cl-prompt> (clast:free-variables *)
(QD)

CLAST handles all of CL standard forms (at least it tries to), plus some more (e.g., LOOP parsing handles also SQL extensions provided by Lispworks and CLSQL).

Under Lispworks there is also a simple CAPI interface that can be used to see the structure of the AST produced by clast:parse. The following image gives you an idea about what would be the structure of the loop form of the previous example.

CAPI CLAST Form Display

Environment Handling

CLAST relies on the implementation of CLtL2 environment handling functionalities, plus a number a minor extensions (mostly inspired by Allegro Common Lisp implementation). The current interface wraps around the underlying implementation and it includes the following functions: variable-information, function-information, block-information, tag-information, augment-environment, define-declaration, parse-macro and enclose. At the time of this writing, CLAST runs on the following implementations:

CLAST on ABCL should be available "very soon now"(TM).

In order to ensure that CLAST runs on your implementation you must lobby your provider to support the CLtL2 environment functions.

Design Choices and Limitations

The CLAST library makes a best effor to be as comprehensive as possible. Many shortcomings can be pointed at and a few are the consequence of design choices.

As an example, the parsing machinery treats CL operators "as-they-are". This means that even if an operator is marked in the ANSI specification as a macro, a form starting with it will not appear as a macro call in the AST. Think of a form like (dotimes (i 42) (print i)): the resulting instance will be one of the class dotimes-form.

Status

At the time of this writing (May 2020) the library has been in a quite stable and usable state for some time. Bugs and missing bits and pieces are to be found, but in general it can be used for AST handling. You are most welcome to chip in.

Downloads and Repositories

The actual CLAST Project page gives you access to the code in its entirety.

To clone the repository you can issue one command:
git clone git://git.code.sf.net/p/clast/code clast-code

License

The file COPYING that accompanies the library contains a Berkeley-style license. You are advised to use the code at your own risk. No warranty whatsoever is provided, the author will not be held responsible for any effect generated by your use of the library, and you can put here the scariest extra disclaimer you can think of.