Reflections on the Future History of Arming Bears

Table of Contents

1 Reflections on the Future History of Arming Bears

Originally presented on 15-JUN-2020 as a presentation the Online Lisp Meetings Series

A revised version of was presented on <2021-02-04 Thu> for an internal audience at RavenPack.

2 The prehistory of Arming Bears

2.1 Who I was

Although I had been exposed to Common Lisp through working with Daniel Pezley and others in the early 1990s on the "Virtual Reality Operating Systems" VEOS, and its successor MOSES, not much of it really stuck me as particually profound. While I understand the basic concepts of macros and the condition system, I was frankly too inexperienced of a programmer to really appreciate them in context. I did Physics/Math as an undergraduate, thinking somehow that one didn't need "Computer Science" to use computers.

I have been using Emacs as my primary editor since early 1988, mainly so I could look at two files simultaenously on a 1200 baud modem, but basically treated Emacs Lisp as this slightly odd configuration language that I would cargo-cult utility from copying from USENET posts.

I (re)discovered Common Lisp in 2005, having become quite a disillusioned Java programmer. have quit programming if I hadn't found and devoured Peter Seibel's Practical Common Lisp.

2.1.1 Daniel Pezeley had these correction to my memory:

Hey, old man! Has your memory faded or what?!?

    I discovered Common Lisp in 2005; an elisp User since 1987, I
    would have quit programming if I hadn't read Practical Common

Slight correction: re-discovered

You were introduced to CL in second half of 1990 and thumbed through
my first printing edition of CLtL2, then of Digital Press.

The "programmable protocol" planned for VEOS but later specified for
MOSES was based upon the CL macro system, which we discussed on
several occasions, including while en route to Ithaca after Christmas
that year.

Shortly thereafter was our (rejected) SIGGRAPH '91 submission[1] that
bears your name in 2nd position and mentions CL several times as does
the larger set of MOSES papers[2] later that year.

Also, Summer 1991 in Seattle[3] after embedding Xlisp into a fork of
VEOS-- if you ever poked at that as I had asked-- you were using
CL. Xlisp was a Common Lisp implementation, just not ANSI CL since
X3J13 was still ongoing.

Seriously, though-- thanks for the history of ABCL. Keep the faith!





2.2 Me in 2021

In 2021, after working professionaly as a programmer for over three decades, I am a much more experienced coder, perhaps armed with enough lambdas to be dangerous. I've read a lot more of classical Computer Science, and try to keep abreast of contemporary topics. My research interests have switched more to topics in Computer Science than tha of pure Physics, especially those that involve the relationship of computational complexity to the physics we observe in our local pocket of the Multiverse. Sometimes I jokingly refer to myself as a mathematician slumming as a software developer.

2.3 What I found in Armed Bear Common Lisp

ABCL originated as the extension language for a the J Editor, an Emacs-like environment written in entirely in Java started sometime in the late 1990s, apparently written entirely by Peter Graves.

By 2005, Peter Graves announced to the mailing list that he would like would like to have the J editor work well enough to concentrate on XCL. At this point, ABCL was largely the work of Peter and Andras Simon, and very close to a conforming implementation. Notably issing the long form of CLOS method combination, a manual to count as accompanying documentation, and a whole slew of minor ANSI incompatibilies.

Erik Hüelsmman, Ville Voultaine, Alessio Stalla, myself, and later, for a real MOP, Rudolf Schlatte worked over the implementation.

Initially, Erik did most of the heavy lifting fixing major gaps in the implementation as well as the release engineering. Alessio added support for extensible sequences. Ville provided numerous fixes. I sort of hung on for dear life, learning what was broken by reading the Common Lisp HyperSpec. Eventually, I was able to understand things well enough to take over the release engineering, which I continue to do to the present day.

The implementation was close to for suitable values of "close". It wasn't until 2011 that the community was able to declare the implementation as ANSI conforming in Amsterdam at ECLM 2011.

The implementation initially ran on Java 5, and we were able to port to Java 6, Java 7, and Java 8 with minimal effort.

ABCL had no other Java dependencies than Ant to run a buildfile (which I maintained). There was a Lisp hosted build that used a working CL implementation to script Java invocations, but it wasn't so common for a Java developer looking to run ABCL. We retain the lack of other dependencies to this day, so ABCL is addressable as a single, svelte ~10Mib jar file for the full implementation (including the compiler and ASDF). We have an additional collection of useful "Beyond ANSI" extensions consisting of Common Lisp-only code which we call "abcl-contrib" that is packaged separately.

ABCL-CONTRIB is packaged separately to 1) place an upper bound on the download needed to run the basic implementation, and 2) to allow more permissive licensing than the base implementation, which is GPLv2 with a classpath exception clause.

In general, we prioritized correctness of the implementation over efficiency in our development.

3 abcl-1.6.0: Platform Stablization

In 2017, ORCL announced that JVMs would be released in new six-month cadence. Pushing marketing to the max, ORCL decided to start releasing a major version of the JVM every six months. Certain versions would be designated as LTS, and Java 8 would be declared at its end of life.

But in 2021, the openjdk8 platform is the current EOL'd base commonly used in industry; openjdk11 is the current long time release. Most Linux distributions have switched to using openjdk11 as the base.

The major change in going from openjdk8 to openjdk11 was that the classloader strategy has been deprecated in favor of the new modules abstraction.

The method that abcl-1.5.0's implementation of CL:LOAD thunks down to no longer existed, as the system classloader no longer extended URLClassLoader

We implemented a new strategy that works with modules to "find" things for CL:LOAD. The changes necessary for openjdk11 were surprisingly few.

We retain the old strategy for jar files running it on openjdk{6,7,8}.

4 abcl-1.7.0: The Road to Rigetti

The Rigetti Quantum Virtual Machine depends heavily on OpenBLAS libraries written mostly in Fortran. I wanted to run the quilc/qvm on ABCL.

A perhaps little known feature of ABCL is that it is quite capable of using the Java Native Access library to call into code loaded into the JVM process space via dlopen().

With abcl-1.7.0, I've been able to extend the implemention's creation of arrays specialized on commonly used byte types to use memory allocated outside of the JVM's heap via system interfaces like malloc().

To do this, ABCL has extended CL:MAKE-ARRAY to take an additional keyword vis. :nio-buffer to use a generic contract for byte buffers for which I can use JNA to use an implementation that is backed by malloc()d memory.

The version of CFFI distributed with the latest (2020-06-10) Quicklisp now contains an implementation of CFFI-SYS:MAKE-SHAREABLE-BYTE-VECTOR which utilizes this extension if present in the ABCL runtime.

(defun make-shareable-vector (length &key (element-type '(unsigned-byte 8)))
  "Use memory on the heap for storing a vector of LENGTH with ELEMENT-TYPE

Returns the allocated vector as the first value, and the pointer to
the heap memory as the second.

Only works for 8, 16, 32 bit bytes.
  (let* ((type
           (first element-type))
           (second element-type))
           (ceiling bits-per-byte 8)))
    (unless (subtypep element-type
                      '(or (unsigned-byte 8) (unsigned-byte 16) (unsigned-byte 32)))
      (signal 'type-error :datum element-type
                          :expected-type '(or
                                           (unsigned-byte 8)
                                           (unsigned-byte 16)
                                           (unsigned-byte 32))))
    (let* ((bytes
             (* length bytes-per-element))
             (jss:new "com.sun.jna.Memory" bytes))
             (#"getByteBuffer" heap-pointer 0 bytes))
             (make-array length :element-type element-type :nio-buffer bytebuffer)))
      (setf (gethash static-vector *static-vector-pointer*)

5 abcl-1.8.0: Fixing PATHNAMEs

Sometime there will be ELS paper on my decades old wrangling of pathnames.

URIs are fully supported as targets of read operations.

;;; After we have loaded this system, ensure Quicklisp is loaded
(defun ensure-installation ()
  (when (find :quicklisp *features*)
    (return-from ensure-installation))
  (multiple-value-bind (fasls
                        setup-base setup-source setup-fasl)
    (if (probe-file setup-source)
        ;; First try loading the Quicklisp setup as a compiled fasl if it exists
        (if (probe-file setup-fasl)
                (load setup-fasl)
              ;; The fasl may be invalid (i.e. between abcl versions); if so, load source, and recompile
              (error (e)
                (format *load-verbose* "~&Failed to load Quicklisp setup fasl ~%~t~a~%because:~%~t~a~%" setup-fasl e)
                (when setup-source
                  (format *load-verbose* "Removing Quicklisp setup fasl and recompiling...")
                  (quicklisp/boot/fasls :remove t)
                  (load setup-source)
                  (compile-file setup-source :output-file setup-fasl))))
            ;; compilation only succeeds after Quicklisp has been fully loaded 
            (when (probe-file setup-source)
              (load setup-source)
              (compile-file setup-source :output-file setup-fasl)))
          ;;; Otherwise download Quicklisp and run its installation sequence
              (load "")
            (error (e)
              (warn "Using insecure transport for remote installation of Quicklisp:~&~A~&." e)
              (load "")))
          (uiop:symbol-call :quicklisp-quickstart '#:install
                            :path (merge-pathnames "quicklisp/"
* [r15390-r15406][r15408-r15413][r15422-r15425][r15434-r15458][r15460-15463]
Overhauled JAR-PATHNAME and URL-PATHNAME subtypes of PATHNAME to fully support
recursive addressing of zip within both local and remote zip

6 ABCL 2

6.1 What is ABCL1?

An amazing piece of code that runs more places than you would think. In addition to the java platform compatibility for a large number of implementations (recent forks in the Valley, in China), it does have an interpreter expressed in the Java code that has been successfully booted on the .NET CLR runtime, and other platforms that are to implement enough of the java.lang.* contracts.

And ABCL1 is slow. Slow to start up. Slow to compile. Slow to load things. But once it gets going, due to the ability to have many different GC implementations "pluggable" via the hosting JVM, it can be remarkably efficient. And it can address currently "exotic" processor architectures such as terrabytes of really, really fast memory with hardward support for many simultaneous threads of execution.

6.2 What can't we do with openjdk6/openjdk7/openjdk8

  1. Implement atomic compare and swap operations. Technically, CaS could be implemented in openjdk8, but it would require major rewrites to everything that descends from org.armedbear.lisp.LispObject. openjdk9 introduced an interface for memory references which one may dynamically (and atomically!) switch under an existing reference, and the interface for CaS operations was generally cleaned up to a mature state. openjdk9 and openjdk10 are both EOL'd, so openjdk11 becomes a good baseline target platform.

  1. Utilize improvements in JVM bytecode that have been added, notably support for dynamic method invocation in JSR-292 "Supporting Dynamically Typed Languages".

7 Goals for ABCL2

Target openjdk11 and better, optionally adding features to take advantage of the platform.

7.1 1. Speed (startup, compiling, loading)

7.2 2. Second compiler targeting openjdk8

Re-entrant, generate code for dynamic method sites via invokedynamic instruction.

7.3 3. Use APIs available in openjdk11

Adding atomic compare and Swap operations will "complete" the usabilty of ABCL on terrabyte heaps.

There are other APIs present as well that would be bring features to the platform, most notably continued replacement of basic I/O routines with the abstractions afforded by NIO2

8 What does the ABCL1 compiler produce?

Zipped archives that have a set of Lisp forms to be evaluated to CL:LOAD the artifact.

8.1 How does CL:LOAD work on the ABCL1 compiler artifacts?

  1. Given a CL:PATHNAME, open a stream of bytes from its CL:TRUENAME.

    Such a resource will either contain one or more top-level forms, or be a zip archive. Confusingly, in both of these cases, the CL:PATHNAME will have a PATHNAME-TYPE of "abcl". The case of containing one-or-more top-level forms is currently only used to package the system in system 'abcl.jar'.

      -rw-r--r--      3660   4-Jun-2020  15:21:30  org/armedbear/lisp/time.abcl
      -rw-r--r--      3448   4-Jun-2020  15:21:30  org/armedbear/lisp/time_1.cls
      -rw-r--r--      1150   4-Jun-2020  15:21:30  org/armedbear/lisp/time_2.cls
      -rw-r--r--      1536   4-Jun-2020  15:21:30  org/armedbear/lisp/time_3.cls
      -rw-r--r--      1353   4-Jun-2020  15:21:30  org/armedbear/lisp/time_4.cls
      -rw-r--r--      3231   4-Jun-2020  15:21:30  org/armedbear/lisp/time_5.cls
      -rw-r--r--       883   4-Jun-2020  15:21:30  org/armedbear/lisp/time_6.cls
      -rw-r--r--     16115   4-Jun-2020  15:21:30  org/armedbear/lisp/top-level.abcl
      -rw-r--r--      1565   4-Jun-2020  15:21:30  org/armedbear/lisp/top_level_1.cls
      -rw-r--r--      1385   4-Jun-2020  15:21:30  org/armedbear/lisp/top_level_10.cls
      -rw-r--r--      3402   4-Jun-2020  15:21:30  org/armedbear/lisp/top_level_11.cls
      -rw-r--r--      2861   4-Jun-2020  15:21:30  org/armedbear/lisp/top_level_12.cls
    M Filemode      Length  Date         Time      File
    - ----------  --------  -----------  --------  -------------------------
      -rw-rw-rw-      3229  11-Jun-2020  09:01:44  __loader__._
      -rw-rw-rw-      3714  11-Jun-2020  09:01:44  binding_tmp1U1MRERI_1.cls
      -rw-rw-rw-      2445  11-Jun-2020  09:01:44  binding_tmp1U1MRERI_2.cls
      -rw-rw-rw-      2174  11-Jun-2020  09:01:44  binding_tmp1U1MRERI_3.cls
      -rw-rw-rw-      1433  11-Jun-2020  09:01:44  binding_tmp1U1MRERI_4.cls
    - ----------  --------  -----------  --------  -------------------------
                     12995                         5 files
  2. If the resource is a zip archive, open it, access the forms contained within it.

    (merge-pathnames "__loader__._" zip-archive-pathname)
  3. Read and evaluate the form(s). They perform the actual loading of the fasl.

    The forms present in the loader artifact will be a bunch of SETQs to set up source properties and one or more SYSTEM::GET-FASL-FUNCTION calls which actually loads the classes emitted by the ABCL1 compiler.

    To load a given class, an array of primitive bytes ("byte[]") is loaded into memory from the archive. This array is passed to the java.lang.ClassLoader.defineClass() function to actually instantiate the class in the JVM.

    "; -*- Mode: Lisp -*-"
    (SETQ SYSTEM:*SOURCE* #P"/Users/evenson/quicklisp/dists/quicklisp/software/alexandria-20200427-git/alexandria-1/arrays.lisp")
    (SETQ SYSTEM:*FASL-LOADER* (SYSTEM::MAKE-FASL-CLASS-LOADER "org.armedbear.lisp.arrays_tmpOKDK4UI"))
    (PROGN (SYSTEM:PUT '#1=COPY-ARRAY '#2=SYSTEM::SOURCE (CONS '((:FUNCTION #1# ) "/Users/evenson/quicklisp/dists/quicklisp/software/alexandria-20200427-git/alexandria-1/arrays.lisp" 
    #5# ))) "Returns an undisplaced copy of ARRAY, with same fill-pointer and
    adjustability (if any) as the original, unless overridden by the keyword

9 Strategies to increase speed

9.1 Use a single, valid Java class file instead of current zip archive

The current compiler emits an entire class for each top-level DEFUN form in a given source unit. This simplified constructing the compiler, but for each class, one has to seek() from the beginning to load each class.

With a suitable abstractions, we should be able to instrument all of these top-level forms into a single Java class which can be injected into the JVM in one fell swoop.

9.2 Implement a verified version of our classes

openjdk6 onwards allows "type inference", but the Java class files must contain such information. ABCL1 doesn't.

ABCL1 emits class files whose version is 49.3 (Java 5)

1. Verification by type checking must be used to verify class files
whose version number is greater than or equal to 50.0.

2. Verification by type inference must be supported by all Java Virtual
Machine implementations, except those conforming to the Java ME CLDC
and Java Card profiles, in order to verify class files whose version
number is less than 50.0.

If, and only if, a class file's version number equals 50.0, then if
the type checking fails, a Java Virtual Machine implementation may
choose to attempt to perform verification by type inference (§4.10.2).

We only implement the "type checking" verification. Current JVMs are largely optimized for "type inference". At some point, loading classes via "type checking" will no longer be possible on future JVMS

Should be easier if we have a single class in our emitted fasl representation?

9.3 Speed: Rewrite current compiler to be re-entrant

The ABCL1 compiler

Involves untangling all the lexical and dynamic scope variables that keep its state.

If we re-write it "not to use specials", then we should be able to use multiple parallel threads to perform the loading

10 Implement a new compiler targeting openjdk8 compliant bytecode

Keep the current compiler! Build her younger sister…

I intend to use as much of the work of SICL as possible in the tooling for present in Cleavir.

We should be able to expose dynamic method dispatch to JVM optimizations. By emitting them as JSR-292 invokedynamic operations, we can easily switch call sites in a way that should be ammendable to optimization by JVM byte-code tooling and the JVM implementations they optimize for.

11 Roadmap to ABCL2

ABCL2 is currently scheduled to be released in September 2020.

As of now (June 2020) honestly this is way too ambitious for the given the resources (mainly just me) and amount of work needed.

11.1 What I can plausibly do by September

  1. Implement atomic compare and swap operations
  2. Fork the current compiler, re-writing it to be re-entrant
  3. Implement writing type verification byte code

This would form a decent platform to start figuring out how to use invokedynamic to make switching call sites more efficient. Currently, the biggest win here would be for CLOS method dispatch.

12 Conclusion

Thanks for your attention to this future history of the Armed Bear Common Lisp implementation.

To support the development of ABCL2, please consider a financial donation to the ongoing Armed Bear appreciation campaign being run by the Common Lisp Foundation.

Otherwise, trying out ABCL for yourself is the best kind of support!

13 Colophon

Mark Evenson
Created: 15-JUN-2020
Revised: <2021-02-04 Thu 15:51>

Author: Mark Evenson

Created: 2021-02-04 Thu 15:51