coalton compatibility layer proposal

[c-kloukinas]

A new discussion area to discuss the proposal for introducing a new compatibility layer in coalton, as attempted in this fork.

The main idea was that having a single layer/file that collects all environment-specific code, might help porting coalton to other environments (e.g., abcl, ecl, clasp, etc.).

The aforementioned fork, attempted to do so with mainly two types of macros/functions:

1. good to have but not necessarily required functionality (e.g., locking a package). These add extra safety or inform the environment about some features that it could use to optimize further, but if they're missing the code should still work in any environment.

2. must have functionality - coalton cannot work without this in any environment.

The code in the aforementioned fork is structured in that manner (all of it is inside compat/compatibility-layer.lisp by the way). For type 1 functionality, it offers actions named as try-X or with-X-if-possible. Were these actions to be defined as empty ones, the functionality of coalton shouldn't change - the environment (mainly sbcl, since these are sbcl-heavy) may not be able to check some things (e.g., that a package is not modified by accident or that a type is frozen) or optimize others (e.g., a type check), but OK, other environments (e.g., ccl) will not do that anyway.

For type 2 functionality, actions don't use the try- prefix or the -if-possible suffix, e.g., (get-hash-type), (unset-all-float-traps). These are needed by any environment that coalton would run on and they must be ported to that environment if coalton were to run there at some point.
unset-all-float-traps currently works for sbcl, ccl, ecl, abcl. Same for (hash-combine).

The aforementioned fork has modified almost all source files but these modifications are minimal and one could argue irrelevant, because they're mostly changing instances of #+sbcl (do-x) to instances of (try-X). The only actual changes are in four files (tested with find . -name '*.lisp' | xargs egrep 'compat:' | egrep -v 'compat:(try|with)-'):

./library/hash.lisp:  (compat:hash-combine lhs rhs))
./library/classes.lisp:  (repr :native #.(compat:get-hash-type))
./library/system.lisp:            (compat:get-bytes-consed)))
./library/math/num-defining-macros.lisp:    (compat:get-fixnum-bits))

The aforementioned fork also contains two more files of interest - the modified Makefile and compat/x-build.lisp
These were created in an attempt to mirror as close as possible the Github actions for testing coalton. So doing a COALTON_HOME=$cwd (make cleanall ; make testall; LISP=clozure make testall), should spawn sbcl and ccl instances to check all possible test configurations (x-build stores fasl code in a configuration-specific area).

Finally, there's the file compat/NOTES-coalton-compatibility.txt where I was keeping track of issues - mainly with external package versions. These were quite a thing, especially for enabling future porting to abcl.
First of all, QL's fset doesn't work with abcl - the one from the repo is needed to resolve abcl-specific bugs. But that one fails on sbcl when safety is forced to level 3, so a patched version of it is available here

Second, fiasco:define-test-package doesn't work with abcl. There's a fork of fiasco that works with abcl here - unsure why fiasco didn't adopt this, so beware!

Apart from fset & fiasco, my fork is using the repository versions of named-readtables and misc-extensions . The remaining external packages are what QL provides.

[c-kloukinas]

Just a quick extra note. The current version of the code (i.e., the four file changes and the specific fset, fiasco, named-readtables, misc-extensions packages) allow abcl to pass quite a few tests - 8 fail and 1 ("inliner-tests-1", see coalton.asd) is excluded due to stack overflow. I don't know if the 8 failing tests fail because of abcl not supporting TCO or for other reasons, I only tried to run them on abcl out of curiousity - not an attempt to actually port the code to abcl.

In a past attempt to run the tests on ecl, code broke in src/reader.lisp I remember seeing a patch in the past about that but I didn't apply it as I don't understand why the code breaks (ecl complains about 2 values being returned but the code uses values, so not sure what the issue is) nor wherther the patch resolves the issue (instead of just masking it).

[Jason94]

This all sounds good so far! What are the implementations that the current PR is actively targeting, and how far along is it on getting those to compile and pass the tests?

[c-kloukinas]

The current PR targets sbcl & ccl only.
On my machine, with the specific versions of the external packages it passes all tests.

[Jason94]

Oh, I see. So the current PR isn't actively extending support to cover extra implementations, it's just refactoring the implementation-specific code that already exists to be behind a single compatibility layer, to make it easy to extend later?

[c-kloukinas]

Yes, that's correct, it's mainly refactoring. In some few cases where I could figure out how to do things in another implementation I actually did so.
More specifically:

• get-fixnum-bits has an sbcl and a default (non-sbcl) implementation.
• get-hash-type has a portable implementation (using get-fixnum-bits)
• hash-combine is implemented in a portable way.
• get-bytes-consed is implemented for abcl as well (for anything other than sbcl & abcl it simply returns 0). Its usage depends on the new feature COALTON:HAS-GET-BYTES-CONSED (defined right above it).

Apart from these, unset-all-float-traps is implemented for abcl & ecl as well.

[Jason94]

Also, I'm just posting here from the Discord to keep everything in one place: it's a core requirement that Coalton must always support true, proper tail call elimination. Not just in the recursive case, but in all cases. There is a workaround that the Coalton compiler can implement if it detects that it's targeting an implementation that doesn't support generalized TCO. This is particularly important for targeting ABCL, because ABCL is on the JVM and the JVM does not support TCO at all.

The workaround is, the Coalton compiler could, when it detects a tail call, do this process:

1. Check if the CL environment supports TCE. If it does, leave the tail call alone and let the CL compiler deal with it.

2. If not, check if it's a recursive tail call. If it is, replace it with a loop.

3. If it's not, check it's part of a set of mutual tail calls. If it is, replace them all with a trampoline.

Here's a pretty good explanation of trampolines in Scala. Notably, Scala 3's built-in trampoline type does not require mutually-tail calling functions to be compiled at the same time, which was previously thought to be the main limitation of this technique. Scala requires the user to manually add the tail call return type to make it stack-safe. But because we want Coalton code to be portable across CL implementations that do and do not natively support general TCO, if Coalton detects that the underlying CL implementation does not support TCO, we should compile a non-recursive tail call to use the trampoline automatically. Apparently this is the approach that Kawa Scheme on the JVM takes (with a user-supplied compiler flag), and I think that's the right approach.

The problem with this approach is that it adds a performance cost. The worst-case for this kind of optimization is something like:

(define (foo) 
  (bar))

(define (bar)
  1)

Here, there is obviously no need for a trampoline because calling (foo) will clearly never blow the stack. The trampoline will add a performance overhead for no reason. This could even be true in cases where (bar) does call (foo) somehow, but the programmer knows that the number of mutual calls will be small, and will never blow the stack in practice.

I still think that trampoline-by-default is the right approach, despite this. But we could add a few things to ameliorate this:

1. If functions like (foo) and (bar) are compiled together, and the compiler detects that the tail calls only go in one direction, it can safely decline to make the trampoline optimization.
2. We could add something like a (declare no-trampoline) annotation that tells Coalton to not trampoline. On CL implementations that do support TCO, and never add trampolines in the first place, this declaration is a no-op.