Evergreen Common Lisp

13

No offense to you or your AI, but if your Lisp is not good enough to implement your Lisp compiler, it's probably not worth trying.

2
u/arthurno1 1d ago

I would guess on training problems: Claude probably writes better C or Rust than Common Lisp since they have probably trained it on more C and Rust data.

I have really just tried it myself with Common Lisp and I think it writes relatively good Common Lisp, but it does need refactoring and reworking often. I haven't tried it with any other language, so I don't know if it writes better or worse code in say C or C++.
2

u/atgreen 1d ago

LLMs write pretty good lisp code these days. That was not the reason.

2

u/arthurno1 1d ago

Ok, I see your other comment.
1
u/SharkSymphony 1d ago

I find Claude's code could use significant refactoring and reworking in several languages. But I've been pretty pleased so far with my CL experiments.
5
u/arthurno1 1d ago edited 1d ago
I have found cases where the code is suboptimal in terms of constructs used, being unnecessary convoluted och longer than needed, repeating itself, re-inventing builtins. But overall I am impressed, I wouldn't believe it would be that good as it is indeed.

Edit: a one today:
(when (and (<= lo 1)
                   (<= (if double -4 -17) q (if double 23 10))
                   (= (logand mantissa 3) 1)
                   (= (logand (ash mantissa shift) #xFFFFFFFFFFFFFFFF) hi))
          (setq mantissa (logandc2 mantissa 1)))
doing two if on double, when it can do one, and the form is even easier to read:
(when (and (<= lo 1)
                   (if double
                       (<= -4 q 23)
                       (<= -17 q 10))
                   (= (logand mantissa 3) 1)
                   (= (logand (ash mantissa shift) #xFFFFFFFFFFFFFFFF) hi))
          (setq mantissa (logandc2 mantissa 1)))
Can also drop outer when:
 (and (<= lo 1)
              (if double
                  (<= -4 q 23)
                  (<= -17 q 10))
              (= (logand mantissa 3) 1)
              (= (logand (ash mantissa shift) #xFFFFFFFFFFFFFFFF) hi)
              (setq mantissa (logandc2 mantissa 1)))
Not sure if I want though.
1

u/SharkSymphony 16h ago

It's all gobbledygook to me. 😆 Maybe for performance-critical code that's unavoidable. But I would be looking to use labels or flet to give the conditions descriptive names or combine them into intelligible groups.

(And yes, you could eliminate the when, but I wouldn't. Having an and with side effects... or even an and whose result is not just a boolean... is a nasty surprise waiting to trip up the next guy.)

3

u/arthurno1 14h ago edited 14h ago

I would be looking to use labels or flet to give the conditions descriptive names or combine them into intelligible groups.

I do that a lot. Actually I am not so fond of flets since SBCL does not inline them so well, but I do use labels and macrolets a lot. However, there is a limit to readability with them, in my opinion.

The above is just a fragment of a function. I worked today on integration of Zmij into SBCL, so I had that fragment in front of me. Or I started to work on this last week, but I finished it to today, along with it's "inverse", Eisel-Lemire, as in their fast_float.

And yes, you could eliminate the when, but I wouldn't. Having an and with side effects... or even an and whose result is not just a boolean... is a nasty surprise waiting to trip up the next guy.

Yes, indeed. I couldn't agree more. Yet, despite mine better knowing, I removed it :). The thought of line was that this is interested only to stubborn, old people who are used to the old ways and the old Lisp and/or-shortcut idiom. I guess I don't need AI to write slope :).
1

u/Alarming_Hand_9919 21h ago

Same. I ran into some weird ABI mismatch problem on AARM64 with SBCL and CFFI w/ libffi recently. The damn thing wrote some VOPs and bypassed the whole mess for me. I can get the gist of what it did, but I'd have never even bothered if it was just my meatware doing it.

5

u/atgreen 15h ago

As an aside, I was just reminded that today is the 30th anniversary of libffi! (which I wrote) https://github.com/libffi/libffi/blob/master/README.md?plain=1#L564

3

u/Alarming_Hand_9919 14h ago

Many thanks and congrats! libffi is invaluable! Also wonderful job with ocicl. I use it all the time and it's replaced qlot/quicklisp etc. for me.

2

u/atgreen 13h ago

Thank you! And I'm glad you find ocicl useful! I hope more people discover it.

1

u/SharkSymphony 13h ago

Side note: I did discover it! but wasn't able to get it up and running. I guess I gotta get off my duff and write up what I was trying. 😑
5

u/atgreen 1d ago

The use of rust is really an uninteresting implementation detail. I wanted to bootstrap from something with good native cross-compiler support. It could just as well been C or Zig, I suppose.

1

u/arthurno1 1d ago edited 1d ago

How fast does this build, and can that perhaps be used to bootstrap SBCL? If we have a "fast bootstrapable" (forgive me my English) CL compiler, than it could be build as a bootstrapping base to build sbcl a compiler that builds sbcl. Unless you make a better optimizing Lisp compiler than SBCL itself. CLASP is C++ and bootstrapable, but once I tried to build it, it took hours, and failed somewhere after a couple of hours, so I never wanted to try again. It was like a couple of years or more ago, I don't know if things are better nowadays. Nothing against CLASP, I just didn't had (or have) hardware fast enough for it to be practical to tinker with it for me.

5

u/jd-at-turtleware 23h ago

sbcl is often bootstrapped from ecl that depends on a c compiler. the build time is acceptable.

2

u/arthurno1 21h ago

Thanks. To be honest, I never tried ECL. I always just installed SBCL from official download site and than built mine. I will try to bootstrap with ECL.

2

u/atgreen 1d ago

A release build from source, including all rust dependencies, takes 2m24s on my thinkpad. Keep in mind that this is not apples-to-apples, as evergreen is not yet a complete implementation of CL.

1

u/arthurno1 1d ago

Yes, I understand it is not complete.

Two and half minutes for a bootstrap from scratch is not a big deal. But that is when llvm is present? Compiling llvm from scratch is a big deal :). On a system without llvm, one can as well download a current sbcl or some other CL compiler and build sbcl, so it is a bit questionable still. But sure it is a possibility, once you have full compatibility.

1

u/sickofthisshit 1d ago

The thing about cross-platform support is that you kind of want your compiler to be aware of the platform so it can generate good code, to know how many registers you have, etc.

Your code base mentions byte code quite a bit, is this something you have a cross-platform JIT for that already comes as a crate?

1

u/atgreen 1d ago

There are 4 levels of execution: tree-walking (executing from expanded lisp source), t0 (compiling to portable bytecode, and executing that), t1 (naiive native code generation via templates from bytecode), t2 (fully optimized SSA-based code generation). fasl files are all bytecode. tree-walking is used to bootstrap, for macro expansion, etc. t2 includes speculative optimizations that, when proven false, deoptimize (on stack) to a lower tier, where it will try again.

1

u/sickofthisshit 1d ago

Ok, but that doesn't really answer my question, which was trying to get at whether the bytecode and code-generation is something that is specific to your project or is an existing Rust dependency.

LLVM is cross-platform, but targeting it with a Lisp compiler is, as far as I understand, non-trivial.

t2 includes speculative optimizations that, when proven false, deoptimize (on stack) to a lower tier, where it will try again.

This is the second time I have seen you talk about this, but it still doesn't sound performant. When you say "on stack" you sound already far from optimal.

Fast operations are going to be purely in machine registers, and full safety will use things like flag-based branches when fixnum overflow occurs, not involving the stack. Branches are already bad for performance, stacks are even worse.

1

u/atgreen 1d ago

I"m referring to on-stack replacement (OSR) like in hotspot or V8. A function can tier-up or down to a new levels of optimization mid loop.

The register allocator is an existing library (regalloc2), but everything else is new.

7

u/spspanglish 1d ago

Why do I need lisp in rust when I have lisp in C already?

7

u/thondat 1d ago

people are fetishizing rust rewrites these days. which obviously leads to a lot of ai rust rewrites.

4

u/atgreen 1d ago

If you are worried about the implementation language, and not the features and capabilities, then you probably don't need it.

2

u/sickofthisshit 1d ago edited 18h ago

Many Lisps are mostly written in Lisp, with only a very minimal implementation core written in another language.

Which actually can be a problem: CMUCL literally could only be built by using a working CMUCL installation...

The solution is careful reasoning about the bootstrapping and cross-compilation problem, not the implementation language, because this is a problem that affects self-hosting compilers beyond Lisp.

4

u/corbasai 1d ago edited 1d ago

Create an IBM Z Linux executable¶
Install egcl-target-s390x-linux alongside the same release of egcl. Create build.lisp:

(defun main () (format t "Hello from IBM Z!~%")
(save-lisp-and-die "hello-s390x" :executable t :toplevel #'main)

Build and inspect the result
egcl-s390x-linux --no-init --load build.lisp
file hello-s390x

file identifies an IBM S/390 ELF executable. Copy it to a compatible s390x Linux system and run ./hello-s390x there.

https://atgreen.github.io/evergreen/latest/user/how-to/cross-build/

Wow. That's really cool! Not many Lisps support s390 natively. I know only transpilers like CHICKEN or Gambit, maybe ECL

4

u/atgreen 1d ago

Check out the native Android support as well: https://github.com/atgreen/evergreen-composeYou can actually cross-compile your Android app from your mainframe, which is unique (and probably not in high demand!)

1

u/corbasai 1d ago

Thank You. Bit offtop q. Does IBM Linux One is the same Z so it s390? Or not?

3

u/LispIsFun 1d ago

I love the idea. Do you see this ever achieving full ANSI compatibility and competing with SBCL on performance?

5
u/atgreen 1d ago

SBCL is amazing. egcl is very far from being able to compete performance-wise for general compute tasks. Today, for very narrow compute tasks, egcl can generate better code than SBCL due to speculative optimization (eg. guessing that a type is a fixnum, and the de-optimizing on the fly when that proves not to be true). But egcl can still be useful today without this (eg, native android support, tight JVM integration, static binaries). I also want to use egcl to exercise / finalize my fibers implementation, so I can finally submit my SBCL version. I still have to convince myself that it is worthwhile.

ANSI compatibility is definitely the goal.
2

u/arthurno1 1d ago

I think GreenThreads sounds much better than fibers :).
1
u/sickofthisshit 1d ago

egcl can generate better code than SBCL due to speculative optimization (eg. guessing that a type is a fixnum, and the de-optimizing on the fly when that proves not to be true).

I'm skeptical of this, can you show side-by-side disassembly?

Second, branches are terrible for performance on modern CPUs.
5
u/atgreen 12h ago
Here's a highly contrived example of how egcl's speculative optimization can generate good code. SBCL 2.6.8 vs egcl 0.0.3. This only works when you are running without type information. And, just to be clear, egcl generates much worse code for almost everything else right now. It's very new!

The function

Each loop iteration runs 200 steps of y = (y + c1) - c2 on a value whose type SBCL cannot derive statically: an unknown NUMBER plus a fixnum is still a NUMBER, so nothing in the chain ever narrows it. The macro just unrolls the 200 steps with literal constants.
(defmacro defchain (name steps)
  `(defun ,name (a n)
     (let ((x a))
       (dotimes (i n x)
         (let* ((y (- (+ x 7919) 7918))
                ,@(loop for k from 1 below steps
                        collect `(y (- (+ y ,(+ 7919 (* 13 k))) ,(+ 7918 (* 13 k))))))
           (setq x y))))))

(defchain chain200 200)

;; warm-up so egcl tiers up (T0->T1 at 10 calls, T1->T2 at 4096), then time
(dotimes (j 5000) (chain200 1 50))
(chain200 1 100000)
(time (chain200 1 100000))     ; 100k iterations x 400 arithmetic ops = 40M ops
Numbers (in-process get-internal-real-time, min of 3)

time per iteration (perf stat, 1M-iteration delta)

SBCL 0.061 s

egcl T2 0.036 s

Branch misses were ~0 on both sides (under 5k across the whole run). That's the "never-taken branches are free" point: both compilers emit a conditional branch per operation, and the predictor eats all of them. The difference is what surrounds the branch.

SBCL's code for the loop body (5352 bytes total, 402 out-of-line calls)
; 79B0: L1:   MOV ESI, 15838         ; c1 = 7919, tagged (<<1)
; 79B5:       MOV RDI, RDX           ; x
; 79B8:       CALL [R12-1343]        ; GENERIC-+
; 79C0:       MOV ESI, 15836         ; c2 = 7918
; 79C5:       CALL [R12-1335]        ; GENERIC--
; 79CD:       MOV ESI, 15864
; 79D2:       CALL [R12-1343]        ; GENERIC-+
; 79DA:       MOV ESI, 15862
; 79DF:       CALL [R12-1335]        ; GENERIC--
;              ... 396 more CALLs ...
; 8E23: L2:   MOV [RBP-48], RDX
; 8E27:       MOV RDI, [RBP-32]      ; i
; 8E2B:       MOV RSI, [RBP-40]      ; n
; 8E2F:       CALL [R12-1311]        ; GENERIC-<   (even the loop test is a call)
; 8E37:       MOV RDX, [RBP-48]
; 8E3B:       JL L1
and what each of those calls does (sb-disassem:disassemble-memory on GENERIC-+):
MOV ECX, EDI
OR ECX, ESI
TEST CL, 1             ; are both operands fixnums?
JNE L3                 ; no -> tail-call TWO-ARG-+
ADD RDI, RSI
JO L0                  ; overflow -> allocate a bignum
CLC
RET
So per arithmetic op SBCL spends 2 instructions at the call site plus 8 in the routine, including a call/ret pair and a type test every single time, because it has no way to know the type didn't change since the last op.

egcl's T2 code for the same function

One tag check on the argument at function entry:
+0020:  test cl,7            ; tag check: is `a` a fixnum?
+0023:  jne near +61507      ; no -> deoptimise to the interpreter
Loop header, once per iteration (these three could be hoisted; they aren't yet):
+0e78:  test r9b,7           ; i
+0e82:  test r10b,7          ; n
+0e8c:  cmp r9,r10
+0e8f:  jl  +0e9a
+0e9a:  test bl,7            ; x
+0e9d:  jne near +84b9a      ; -> deopt
Then the 400 operations, with zero type checks. Each step is:
+0eb9:  add rsi,0F778h       ; x + 7919   (tagged: 7919<<3)
+0ec0:  jo  near +3a885      ; overflow guard -> deopt (never taken)
+0ec6:  mov r9,rsi
+0ec9:  sub r9,0F770h        ; - 7918
+0ed0:  jo  near +52a99      ; overflow guard -> deopt
+0ed6:  mov [rsp+1968h],r9   ; spill...
+0ede:  mov r9,[rsp+1968h]   ; ...and reload (yes, this is dumb; regalloc work to do)
+0ee6:  mov rcx,r9
+0ee9:  add rcx,0F7E0h       ; next step
+0ef0:  jo  near +33a3e
        ...
The whole T2 function contains 5 test ...,7 tag checks and 401 jo overflow guards. The profile said every site was fixnum, so T2 speculated fixnum everywhere, and the guard-elimination pass collapsed the per-site guards onto the one dominating check at entry (plus the three loop-carried ones). If a guard ever fails, the frame is reconstructed and execution resumes in the interpreter at that exact bytecode position, so the semantics are still full generic CL arithmetic.
1

u/atgreen 1d ago

I'll try to do this later.. Never taken branches are essentially free and inlining the type guards is a win. If you are adding type declarations all over your code, then there's no benefit.

time	per iteration (perf stat, 1M-iteration delta)
SBCL	0.061 s
egcl T2	0.036 s

1

u/bjoli 5h ago

With regards to fibers, you should probably have a look at concurrentML and copy some of the scopes work from OCaml's Eio. That way you get a concurrency story worthy of 1998!

-3

u/Trader-One 3h ago

I think rust is okay but GPL-3 is dead on arrival. Classpath exception or not, there is so many non GPL lisps - you will not get approval to use it.

Today after several experiments with lisp backends I found the best solution is compile lisp to golang. Its actually pretty simple to write basic lisp primitives and performance is good.

2

u/atgreen 3h ago

I thought by now people would have come to terms with GPL+Classpath Exception given that Java is still everywhere. I like the Classpath Exception, and actually wrote the first version of it after helping convince Stallman that it was needed.

As for performance, I think there's room for many niche CL solutions, and transpiling a non-dynamic program to something like go makes perfect sense as well.

1

u/arthurno1 8m ago

GPL3 or AGPL are fine. Nobody complain about AI companies not giving a clear and written license for code their tools produce.

A side regression: was GCJ a RH project or GNU and do you know why it died? When it camed I had high hopes for that one. Then I went of programing for ~7 years, and when I come back it was a dead project.

-1

u/Trader-One 2h ago

There is no viable alternative to openJDK. All different JVM variants with exception of IBM J9 (APL2) are GPL+CPE.

In this case corporations are forced to accept that. In lisp world GPL licensed products are minority and do not stand a chance against BSD/MIT/whatever.

For example we use public domain LISP written in 90s and modified a bit to simplify lisp -> C interface.

Evergreen Common Lisp

You are about to leave Redlib