4 ms·
Compiling a Lisp to x86-64: primitive functions
- tekknolagi 6y agoThis 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!
- smabie 6y agoThis 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.
- tekknolagi 6y agoI 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!
- jamiek88 6y agoI 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.
- giancarlostoro 6y agoI 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).
- rscho 6y agoThe 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.
- Reelin 6y ago> an LLVM based Lisp or Scheme language Clasp is exactly that! (https://www.cliki.net/Clasp https://www.cliki.net/Clasp) There's also SICL, which includes the Cleavir framework (used by Clasp I think?). (https://cliki.net/SICL 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/ http://terralang.org/)
- moonchild 6y agoMeh, sbcl[1] has an excellent JIT. You don't need a heavyweight AOT, and it kills your compile time. 1. http://sbcl.org/ http://sbcl.org/
- lispm 6y agoSBCL 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.
- pankajdoharey 6y agoSBCL 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.
- moonchild 6y agoSBCL 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!
- lionsdan 6y agoThere'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/ http://www.call-with-current-continuation.org/bones/ https://bitbucket.org/bunny351/bones https://bitbucket.org/bunny351/bones
- tekknolagi 6y agoThis is very cool. Thanks for pointing it out!
- pankajdoharey 6y agoAdding 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-compilation-part-1-an-interpreter/ https://eli.thegreenplace.net/2017/adventures-in-jit-compila... So you can try converting other interpreters to native compilers.
- mtreis86 6y agoI 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.
- pfdietz 6y agoGenerating 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).
- smabie 6y agoOkay, write it yourself? Most things people learn are "solved" problems for somebody.
- macintux 6y agoThis could have started an interesting discussion about the second sentence if you hadn’t led off with the first.
- pfdietz 6y agoI 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?
- macintux 6y agoThe 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.
- timonoko 6y ago#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)
- deleted 6y ago[deleted]
- sitkack 6y agoHow does the stack work? I assume $1DA7 is the outer interpreter loop? What is $3BB0 for?
- timonoko 6y agoThe 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.
- p4bl0 6y agoFor 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.