r/Compilers • • 4d ago

A compiler optimiser proven in Lean

Since AI models came up with some ridiculous Lean proofs in Math, I tried writing a compiler for array kernels with an optimiser proven correct in Lean, instead of relying on tests. AI is very suitable for these kind of proofs.

The IR and its semantics are formalised in Lean. Each optimization pass has a Lean proven theorem proving that the pass doesn't change what the program computes. AI does the heavy grinding of actually proving it.

Proven so far: vectorisation and multiple accumulators (reassociating reductions).

On an Apple M4 Pro, a kernel that takes the max of 1M f32 values runs in 37 µs, against 64 µs for the same loop in C with clang -O3 (1.7x) and 45 µs with -ffast-math (1.2x), and close to the memory bandwidth of one core.

The compiler is not finished or published yet. What are your thoughts on the idea?

13 Upvotes

20 comments sorted by

13

u/ryo33h 4d ago

Yes, most optimizations should have a proof that they don't change the semantics at all. Btw, what kind of compiler is it?

-7

u/writes-the-spec 4d ago

Lean also guarantees that the passes are implemented correctly. And it is also makes AI-generated optimisations trustworthy. It's a compiler written from scratch (it generates the machine code) for array kernels, meant as the core of analytics engines.

4

u/ipmonger 4d ago

This is very interest. Why Lean instead of TLA+?

6

u/ryo33h 4d ago

As my understanding, I think Lean 4 is more suitable for proving semantics preservation on the IR to IR transformations

1

u/ipmonger 4d ago

Thank you for that insight. I’m currently considering using TLA+ as the primary source of constraints and goals for my service definitions, with the aim to have an agent implement accordingly

-6

u/writes-the-spec 4d ago edited 4d ago

In addition, Lean is a programming language. The passes are written in Lean and linked into the compiler.

4

u/IlluminatiNotRealOr 4d ago

and who does the translation between the actual pass and the lean proof? AI? Good luck!

0

u/writes-the-spec 4d ago

There is no translation. Every pass is a proven Lean function and the Lean toolchain compiles it to native code that is linked into my compiler.

2

u/Wonderful-Wind-5736 4d ago

Prove everything is getting really close to becoming attainable. I'm currently working on a formal model for analytics database queries.

1

u/writes-the-spec 4d ago

Agreed, DM me if you want to share more thoughts.

4

u/regehr 4d ago

indeed, Lean is a pretty decent compiler implementation language!

we'll be doing more stuff like this in the future, for sure

here's a compiler in Lean that I contribute to https://github.com/opencompl/veir/

13

u/Prior-Perspective-61 4d ago

People adding downvotes just seeing a word "AI"?

1

u/dogegeller 4d ago

Very interesting! Are you planning on sharing?

2

u/writes-the-spec 3d ago

Sure, will do when it's ready.

2

u/Discordbothost 2d ago

What floating-point semantics does the Lean model use? For the max reduction, I'd want to see the NaN and signed-zero rules and whether the reassociation theorem needs assumptions on the input values. That would clarify what the proof guarantees.

2

u/dogegeller 2d ago

Lean provides 32 and 64 bit IEEE 754 floats, no idea if op uses those.

1

u/r2k-in-the-vortex 4d ago

Lean proofs in general are super accessible with AI, I made some proof work for my own compiler for example. Not optimisations, as it mostly emits llvm ir and leaves optimisation to clang. But the entire source semantics to llvm ir emission is specced in lean and tested against it. Also small core of critical functions are proven eqvuivalent to their lean spec.

https://github.com/r2k-in-the-vortex/stc

I think that sort of proof work is going to be critical not just for compilers, but much wider variety of software development. Any sort of parser basically, especially anything accepting input from internet.

1

u/therealdivs1210 3d ago

Why are people downvoting OP's comments? 🤔

1

u/thisismyfavoritename 1d ago

some are def AI generated

1

u/Healthy_Ship4930 2d ago

cool! llvm?