Compiling a Lisp to x86-64: primitive functions | Hacker News Reader

Compiling a Lisp to x86-64: primitive functions

bernsteinbear.com

126 pointstekknolagi29 comments

There's also Bones, an R5RS Scheme that compiles to x86_64 assembly (from the Chicken Scheme creator).

http://www.call-with-current-continuation.org/bones/

This is very cool. Thanks for pointing it out!

Adding to that Eli Bendersky has a very good 4 part tutorial on writing a JIT from scratch https://eli.thegreenplace.net/2017/adventures-in-jit-compila... So you can try converting other interpreters to native compilers.

This is part of a series I'm writing about compiling a small Lisp directly to x86-64 machine code. Let me know what you think!

This is great. Most Lisp implementation involve building a trivial interpreter, but rarely does anyone show how to build a real native compiler.

Great work, I especially like the use of C instead of a higher level language.

I think that's because it's more finicky and a longer implementation. Of course, if you build a small interpreter that you can then use to write a Lisp compiler in Lisp... you've got it made!

I love how we can bootstrap.

I’m getting interested in bare metal, I.e. no OS, booting direct to app, development.

These compilers are a goldmine of info.

For those who like me were not sure that the `calloc` call would necessarily allow to tag the returned pointer, I found the explanation in a previous post of this article series:

> It’s important to note that we can only accomplish this tagging scheme because on modern computer systems the lower 3 bits of heap-allocated pointers are 0 because allocations are word-aligned — meaning that all pointers are numbers that are multiples of 8. This lets us a) differentiate real pointers from fake pointers and b) stuff some additional data there in the real pointers.

It's what I suspected, but I didn't know that it was actually safe to assume that.

I always wondered why we rarely see more efforts like an LLVM based Lisp or Scheme language, especially when some projects like Racket are looking to improve performance by switching their runtimes (and I assume other benefits that come from consolidating underlying programming efforts across multiple projects).

The main driver for Chez-based Racket was to have a Scheme runtime. Performance was an afterthought, but was anticipated due to the excellent performance of Chez and the superior expertise of many Racketeers with Scheme compared to C.

The macro expander was a particularly desirable part to have in Scheme, as it since allowed more people to contribute to this complex but crucial component.

> an LLVM based Lisp or Scheme language

Clasp is exactly that! (https://www.cliki.net/Clasp)

There's also SICL, which includes the Cleavir framework (used by Clasp I think?). (https://cliki.net/SICL)

And there are also other non-Lisp languages that manage to attain similar levels of "meta" power and expressiveness. Terra is one example; it uses LLVM. (http://terralang.org/)

Meh, sbcl[1] has an excellent JIT. You don't need a heavyweight AOT, and it kills your compile time.

1. http://sbcl.org/

SBCL provides AOT compiler. A file to machine code compiler and a Lisp form to in-memory machine code compiler.

It's not a JIT compiler.

SBCL has JIT'ing capabilities sb-fasteval. Essentially as long as you can generate machine code, putting it to memory and making that piece of memory executable is all you need to JIT.

SBCL compiles lisp code, assembles it in-memory and executes it directly. That's a JIT in my book. It can also dump that code to a file ahead-of-time to be run later—true—even better! More flexibility!

Whether code is written to a file or just executed in memory is irrelevant. JIT compilers compile code at run time, and may also recompile the already compiled code again to optimize it based on run-time analysis. SBCL however has distinct compile-time and run-time.

For example, you have a function that does a bunch of math without knowing the types of the arguments. A JIT compiler can first compile it with generic math, but later observe that it's almost always called with fixnums, and choose to create a specialized implementation for fixnums. SBCL relies on the programmer to implement and call the optimized version when appropriate.

That's what in the Lisp context might be called 'incremental in-memory machine-code compilation'. The compiler can take individual forms and create in-memory machine code. The interface to that is the function COMPILE.

It's then often used in the READ EVAL PRINT LOOP. The EVAL function is then implemented by first compiling the source code passed (SBCL compiles it to machine code) and then calling the compiled code. This is then a tiny AOT compilation step in each REPL usage. That feature (REPL default incremental AOT machine code compilation) is available in some Lisp implementations at least since the 80s - but I don't know if it was used even earlier. Might be. Often interpreters were used in the REPL -> one of the reasons was reduced latency. Popular always compiling REPLs used a fast (and thus a bit dumb) compiler, then.

Why should this not be called JIT in the SBCL case? Because even in this case, where the user enters code to a running Lisp, usually all of the source code (not byte code -> SBCL does not use a byte code engine) is unconditionally compiled to machine code before (!) it gets executed.

What people usually (outside of Lisp) experience as a JIT compiler is actually something like a combination of an AOT byte code compilation step and runtime JIT machine code generation - usually under control of some byte code engine, which decides when and what to compile. SBCL does not do the moral equivalent of that.

Now SBCL also has an optional source code (-> not byte code) interpreter, which might do fancy stuff when used.

I've been working on a lisp that's strongly typed and basically only has functions that are the llvm C API, including JIT. With that you can build macros, type systems, etc. Basically much of the code you write as a user can be what's typically implemented (in predetermined ways) in the compiler in other languages.

This sounds interesting is any of this public or publicly blogged about?

I'd love to make it public when it is a bit more thorough. Right now it's just local. I really wanted to get to the point that it's self-hosted before going public, but naturally that's a little involved since it does involve building everything up from assembly (llvm IR). But it's fairly straightforward, albeit time consuming, to build simple abstractions on top of each other to implement features typically present in high-level languages.

#METOO from 1982:

    C:\>nokolisp                              
                                          
    1> (comp-debug t)                         
    t                                         
                                          
    2> (ncompile ’(plus a 1))                
                                          
    $O9CB:$7149: MOV AX, [$01BA]              
    $O9CB:$714C: CALL $0F1D ; CALL NUMVAL     
    $O9CB:$714F: MOV BX,$01                   
    $O9CB:$7152: ADD AX,BX                    
    $O9CB:$7154: CALL $05C0 ; CALL MAKNUM     
    $O9CB:$7157: JMP $1DA7                    
                                          
    (subru: eval=$7149, compile=$3BB0)

How does the stack work?

I assume $1DA7 is the outer interpreter loop?

What is $3BB0 for?

The stack is regular 16 bit CPU-stack. Unlike most or all others, i was using the CPU stack for Lisp-nodes. The garbage collector made many errors when marking data from CPU stack. But it does not matter, with 16 bits you can have 65000 nodes, enough for all eternity.

JMP $1DA7 is basically return-from-closure.

(subru: eval=$7149, compile=$3BB0) means that compiled functions are treated differently, when called from intrepreter and compiler. It was direct machine-code CALL in compiled code.

I am really enjoying this series, thanks. I've read PAIP by Norvig which includes a compiler, but this is a whole different perspective, being straight to machine code.

Generating code from Lisp is a well-solved problem.

I'd like to see the capability of recompiling functions while they have live stack frames, and this just working (within defined limits).

Okay, write it yourself?

Most things people learn are "solved" problems for somebody.

This could have started an interesting discussion about the second sentence if you hadn’t led off with the first.

I don't think we'll see radical improvements in Common Lisp compilers (the Lisp dialect I am most familiar with) for conventional AoT compilation. Sure, there are incremental improvements that can be made.

Perhaps you could start an interesting discussion on how you see that first sentence being wrong?

The first sentence wasn't wrong, but it came across as snarky. Very little on HN is original research; that doesn't mean anyone who creates something they find interesting should be slapped down.

Reply on news.ycombinator.com