Teaser: CL-Torch!

I have been working for the past few months on CL-Torch, a Common Lisp equivalent of PyTorch.  Like PyTorch, CL-Torch calls LibTorch — the C++ library that does most of the numerics — via FFI.

It's nowhere near done, but I need to set it aside for a few months to work on something else, so I thought I would publish what I have and let people play with it.

Claw

Claw (Common Lisp Auto-Wrap; no relation to OpenClaw, which it preceded by years) is Pavel Korolev's FFI wrapper generator; it includes IFFI, his Intricate Foreign Function Interface, which deals with C++ overloading.  This is what I have used to create CL-Torch.

I had initially looked at SWIG, which had had Common Lisp support until its 4.0 release, but on closer examination it didn't look like a good choice; the Common Lisp generation apparently never worked well.  I then tried C2FFI, and in retrospect, maybe I could have gotten it to work, but it doesn't have any explicit C++ support; I would have wound up with C++ "mangled names" (encoded function names including namespace and parameter type information) in the CL-Torch sources.  Poking around a little more, I found these three blog posts by Pavel introducing Claw.  I also noticed that Pavel already had a Claw-Torch project; although he hadn't gotten very far on it and it was years out of date, it was still the best starting point I had found.

But I didn't realize what I was getting into.  Pavel describes Claw as "BETA quality", emphasizing that it isn't ready for general use, but actually I think even this description is too generous; in the state I found it in, I would describe it as alpha, and early alpha at that.  I spent several weeks fixing and improving it so that it could handle LibTorch, which in fairness, is pretty much a torture test for an FFI generator — it uses features of C++ I didn't even know existed.  One of the most problematic was constructor inheritance.  Did you know constructors could be inherited?  I didn't either, but the feature went in in C++11.  Anyway, LibClang, which Claw uses to analyse the C++ code it's wrapping, doesn't expose inherited constructors in a convenient way; the information is there, but you have to dig it out.  So I had to learn a bunch about the internals of Claw, including libresect, the C library that interfaces directly with LibClang.  This knowledge eventually came in quite handy, though, as I made more fixes and changes to Claw, ultimately dropping 14 PRs on Pavel.  — So far, he hasn't merged any of them, and I don't know whether he's going to, so for CL-Torch, if you want to regenerate the FFI bindings, you'll need to use my forks of Claw and its subprojects cl-resect and libresect.

One significant improvement I made to Claw was to add exception handling.  Exceptions thrown by LibTorch code are caught and automatically translated to Lisp errors.

At the time Pavel wrote Claw, passing structs by value required libffi, which, he noted in a blog post, is quite slow.  So Claw passes all structs by pointer.  I see that efficient passing of structs by value has been recently added to SBCL, but I don't think it's worth modifying Claw to use it, as that would change how the generated wrappers have to be called, and thus wouldn't be portable.

What might be worth doing, eventually, is making IFFI allocate temporary objects on the stack; it currently doesn't.  But for CL-Torch, the benefit is almost certainly going to be undetectable; LibTorch calls, in normal use, spend the vast majority of their time doing tensor arithmetic; allocating and freeing small objects is negligible by comparison.

Anyway, my overall impression of Claw is that, with my improvements, it works pretty well.  If you have another C++ library you'd like to call from CL, I think you should give it a try.  It needs quite a bit more documentation, but if you look at what I've done for CL-Torch, that will give you some clues.  Beyond that, you'll have to do what I did: read the source 😸 

Status

For the purpose of a project like CL-Torch, LibTorch has two major pieces.  One is the tensor arithmetic library ATen (with its lower-level component C10).  This library has over a thousand operations, although many of these are variants of one another; for instance, many operations have both functional and in-place versions, the latter updating one of its argument tensors rather than allocating a new one.  The C++ and Python APIs for these functions are auto-generated from a description file, aten/src/ATen/native/native_functions.yaml.

I have written a generator that produces CL versions of these APIs from the YAML descriptions.  It's not finished — there are cases it doesn't yet handle — but it's currently succeeding on 645 of the 1089 candidate functions, so there is a significant amount of working functionality here.  (In some cases, not all features of the function are supported yet.)  If you just want to do a bunch of tensor arithmetic, there may be enough here to do what you want.  It's not heavily tested, but there are enough tests to reasonably assure me that the code generation is being done correctly, at least in most cases.

The second major piece of LibTorch is the high-level neural net API.  Here CL-Torch is less far along, but this is also a much easier part to work on.  (I think.  I haven't tested any of the code I've written for this part.)  So if you want to add CL-Torch code for some of this part of the API, I think you should be able to do that.  (You could even try using an LLM for this — I haven't, yet.)  One thing you should know, if you want to work on that, is that there are two levels within this part of LibTorch: the torch::nn::functional:: code is the slightly lower level, that implements the operations of neural-net layers but without keeping state, and in particular, without maintaining trainable parameters.  I have started hand-translating these (they're mostly quite simple) in Code/torch-functional.lisp.

The higher level is the module API, which I have just barely started in Code/torch/modules.lisp.  This API implements parameters and training.  To actually train a network, you'll also need an optimizer; I haven't started on these. 

FSet v2.4.2: CHAMP Bags, and v1.0 of my FSet book!

A couple of weeks ago I released FSet 2.4.0, which brought a CHAMP implementation of bags, filling out the suite of CHAMP types.  🚀  FSet users should have a look at the release page, as it also contained a number of bug fixes and minor changes.

I've since released v2.4.1 and v2.4.2, with some more bug fixes.

But the big news is the book!   It brings together all the introductory material I have written, plus a lot more, along with a complete API Reference chapter.

FSet is now in the state I decided last summer I wanted to get it into: faster, better tested and debugged, more feature-complete, and much better documented than it has ever been in its nearly two decades of existence.  I am, of course, very much hoping that these months of work have made the library more interesting and accessible to CL programmers who haven't tried it yet.  I am even hoping that its existence helps attract newcomers to the CL community.  Time will tell!

 

FSet v2.3.0: Transients!

FSet v2.3.0 added transients!  These make it faster to populate new collections with data, especially as the collections get large.  I shamelessly stole the idea from Clojure.

They are currently implemented only for the CHAMP types ch-set, ch-map, ch-2-relation, ch-replay-set, and ch-replay-map.

The term "transient" contrasts with "persistent".  I'm using the term "persistent" in its functional-data-structure sense, as Clojure does: a data structure is persistent if multiple states of it can coexist in memory efficiently.  (The probably more familiar use of the term is in the database sense, where it refers to nonvolatile storage of data.)  FSet collections have, up to now, all been persistent in this sense; a point modification to one, such as by with or less, takes only O(log n) space and time to return a new state of the collection, without disturbing the previous state.

A transient encapsulates the internal tree of a collection so as to guarantee that it holds the only pointer to the tree; this allows modifications to tree nodes to be made in-place, so long as the node has sufficient allocated space.  Once the collection is built, the tree is in the same format that existing FSet code expects, and can be accessed and functionally updated as usual.

Some quick micro-benchmarking suggests that speedups, for constructing a set from scratch, range from 1.6x at size 64 to as much as 2.4x at size 4096. 

You don't necessarily even have to use transients explicitly in order to benefit from them.  Some FSet builtins such as filter and image use them now.  The GMap result types ch-set etc. also use them.

For details, see the GitLab MR.

FSet v2.2.0: JSON parsing/printing using Jzon

FSet v2.2.0, which is the version included in the recent Quicklisp release, has a new Quicklisp-loadable system, FSet/Jzon.  It extends the Jzon JSON parser/printer to construct FSet collections when reading, and to be able to print them.

On parsing, JSON arrays produce FSet seqs; JSON objects produce FSet replay maps by default, but the parser can also be configured to produce ordinary maps or FSet tuples.  For printing, any of these can be handled, as well as the standard Jzon types.  The tuple representation provides a way to control the printing of `nil`, depending on the type of the corresponding key.

For details, see the GitLab MR.

NOTE: unfortunately, the v2.1.0 release had some bugs in the new seq code, and I didn't notice them until after v2.2.0 was in Quicklisp.  If you're using seqs, I strongly recommend you pick up v2.2.2 or newer from GitLab or GitHub.

 

FSet v2.1.0 released: Seq improvements

 I have just released FSet v2.1.0 (also on GitHub).

This release is mostly to add some performance and functionality improvements for seqs. Briefly:

• Access to and updating of elements at the beginning or end of a long seq is now faster.
• I have finally gotten around to implementing search and mismatch on seqs. NOTE: this may require changes to your package definitions; see below.
• Seqs containing only characters are now treated specially, making them a viable replacement for CL strings in many cases.
• In an FSet 2 context, the seq constructor macros now permit specification of a default.
• There are changes to some convert methods.
• There are a couple more FSet 2 API changes, involving image.

 See the above links for the full release notes.

 UPDATE: there's already a v2.1.1; I had forgotten to export the new function char-seq?.

FSet 2 released!

I have just released FSet 2!  You can get it from common-lisp.net or GitHub.  A detailed description can be found via those links, but briefly, it makes the CHAMP implementations the default for sets and maps, and makes some minor changes to the API.

I am already working on 2.1, which will have some performance improvements for seqs.

FSet 2.0 update

Someone asked me what the rationale is for the decision, in my FSet 2.0 release candidate, to have no default default for maps and seqs, so that an out-of-domain lookup will signal an error.  I started to write an answer, but after putting the arguments for and against this change down on the page and mulling them over for a few days, I concluded it was a mistake and decided to reverse it.

So in FSet 2.0, it will still be the case, unless you specify otherwise, that an out-of-domain lookup on a map, or an out-of-bounds lookup on a seq, will simply return nil (with a nil second value).  You do, as before, have the option to specify a different default, and now you also have the option to specify no default, if you want out-of-domain/bounds lookups to signal an error.

I have tagged v2.0.0-rc1. 

This has been a difficult decision that I have changed my mind about a few times.  Let me summarize the arguments for and against the change.  I'll start with some in favor of not having a default default:

• It will be simpler to explain to new FSet users that the map or seq has a default only if explicitly given one.
• Users will supply a default of nil only for those maps and seqs which actually have out-of-domain/bounds lookups done on them.  More maps and seqs will have no default, which will surface cases when an intended invariant, that the lookups are all in-domain, is violated; this will improve the overall robustness of their code.
• Some operations, primarily map-union, map-intersection, and compose, are easier to use when their arguments have no defaults; if they have nil defaults, the function passed in to combine or map values (often specified as a lambda expression) must explicitly handle nil, which is often inelegant.  If there is no default default, fewer people will trip over this speed bump.

Some arguments in favor of a nil default default:

• It's consistent with FSet past practice; having no default default will require migration effort on the part of FSet users.
• It's consistent with the majority of CL collection accessors (assoc, gethash, nth).
• It's consistent with other FSet behaviors, such as that of arb on an empty set, which returns two nil values.

Minimizing migration effort is somewhat desirable, of course, but I try not to overweight it.  There's an old story I once heard about Stu Feldman, the original author of make.  He wrote it and passed it around to his colleagues at Bell Labs.  Pretty soon he realized that the syntax was a dumpster fire, but he didn't want to fix it, the story goes, because he already had ten users.  And now millions of us have to live with it.

So I'm willing to impose some migration pain on existing users, as long as it doesn't seem excessive, if I believe they themselves will be happier in the long run.   It's not that their interests don't count; it's just that future benefits can outweigh present pain.  And in this case, I think the amount of present pain would not have been large; I did the conversion on some of my own code that uses FSet, and it didn't seem very hard.  So all told, the migration argument carried a little weight, but not a huge amount.

As for the CL collection accessors, there is some inconsistency there already.  Sequence accessors — svref, elt, and aref — do signal an error on an out-of-bounds index, except perhaps at safety 0.  (Surprisingly, at least to me, of these only elt is specified to signal an error, but the other two do so also in all the implementations I've tried.)  nth is a funny case; at least in the major implementations, on a positive index greater than or equal to the length of the list, it just returns nil, but on a negative index it signals an error.  The consistency-with-CL argument is thus not quite as strong as it may sound, when CL isn't even completely self-consistent.  Of course, the map accessors assoc and gethash do return nil on an out-of-domain lookup.  All told, again, this argument carries somewhat more weight for me than the migration argument, but it's not overwhelming.

The argument from internal consistency of FSet was the one that tipped the balance for me.  There are other access operations besides lookup that indicate failure by returning a second (or sometimes third) value which is false.  I suppose I could have changed these to signal errors also, but this seemed a bridge too far; in the cases of set and bag operations, there isn't currently a way you could select between the error behavior and the return-nil behavior, the way that the choice of defaults allows you to do for maps and seqs.

I also tried to estimate the frequency of the following two cases:

• In a no-default-default FSet, how often would users have to add an explicit :default nil to prevent undesired lookup errors?
• In a nil-default-default FSet,  how often would users have to add an explicit :no-default or :no-default? t to cause errors on out-of-domain lookups, or for reasons having to do with map-union etc?

Although it's hard to be extremely confident about my estimates without seeing a lot of code others have written against FSet, my experience suggests that the former would be several times as frequent as the latter.  This argument also helps tip the balance toward a nil default default.