9 ms·

Compiling a Lisp (2020)

114 points by swatson741 3y ago

dgan 3y ago
It's always amazes me how common lisp is so much more dynamic than, say, python, and is still compiled down to native code, and has running speed in the same ballpark as java/go/c#. Unfortunately it's not a simple language, and has much historical baggage (the standard has mandated Roman literals in formating, really guys?..)
- wegfawefgawefg 3y ago
  I dont think it is uniquely difficult compared to any other programming language. If anyone reading this has given up multiple times trying to learn lisp i encourage to keep trying. Its not really that different than python or javascript (Here me out). At first i genuinely couldnt understand it at all despite being well versed in tons of other languages, but after a few weeks, one day my brain suddenly could read it as if it was c++ or python. It was an instantanious switch. There is a sort of shape translation, like an affine transformation between lisp code and algol family stuff like c, etc. Once your brain sees the shapes of the paragraphs, and the function and class def shapes, you will not feel lisp is really different from the other languages except in form. ( excluding the macros. those are truly unique)
  - pitherpather 3y ago
    > like an affine transformation between lisp code and algol family stuff like c I wonder how far one might go introducing common lisp with parallel examples in javascript and python -- something like a Rosetta Stone approach, also likening ')' and '}' and <dedent>.
    - wegfawefgawefg 3y ago
      Very far. actually thats probably a really good way to do it. lisp for python devs, amd its just basic python shit on the left page, and the clisp version on the right page. We do the same thing for human language books. Ive got a copy of the little prince where the left is in english and the right is in japanese. the bookstore is full of these.
- whartung 3y ago
  Well, the funny thing is that for base Common Lisp, it's less dynamic than you think. The functions and symbols in the core packages (e.g. COMMON-LISP package) are considered fixed and immutable. For example, out of the box, the compiler can assume that things like '+' aren't going to be redefined behind its back. It's assumptions like that can lead to very efficient code. But, at the same time, the core lisp language is actually not very dynamic, its more like your typical, compiled language in that sense. In contrast to say, Scheme, which has no presumptions. Out of the box, naive Scheme compilers can not make such assumptions. So, if you have something like: (set! a (+ x (- y (+ z w)))) The compiler actually has to look up (dispatch) '+' twice! Did '-' change the definition of '+'? Maybe...you don't know. So you can't (again naively) inline anything (not even counting the issues with numeric tower and types of the variables). So, what would ideally be a couple of simple machine instructions turns in to a huge endeavor.
  - pfdietz 3y ago
    If Common Lisp allowed additional methods to be added to + (if they were generic functions, and if the new methods did not override the standard ones) without changing the existing methods, it would be possible to be just as efficient. That's because one could just dispatch as now and instead of erroring if nothing applied, instead check the new methods.
  - davexunit 3y ago
    It is true that in Scheme you can shadow built-ins if you want, but a compiler would have to be extremely naive, perhaps lacking support for macros entirely, to not recognize primitive `+` from a user defined `+`. One of the very first transformations applied to the user program would be alpha conversion, where all user defined variables are replaced with program-unique names. At that point, the compiler would be absolutely sure that `+` is the primitive addition operator and compile it directly as an add primcall.
    - miloignis 3y ago
      I believe it is legal to actually reassign the global builtins, not just shadow them. Proving that a program doesn't do this is difficult to impossible, and I think some schemes give you an option to tell the compiler you won't do it. Chez Scheme has a section in their manual recommending pulling top level declarations into lets that it can analyze locally in order to optimize them.
- deleted 3y ago
  [deleted]
- kagevf 3y ago
  > the standard has mandated Roman literals in formating By the way, in case anyone is wondering what this is, it just means that you can use the FORMAT function to output Roman numbers. (format t "~@r" 4) ;; => IV You can also do: (format t "~r" 4) ;; => four and just interpolating the number would use "d": (format t "The number is: ~d" 4) ;; => The number is: 4
- throwaway93941 3y ago
  > historical baggage (the standard has mandated Roman literals in formating, really guys?..) Come now, it's not _that_ old :) It's just a bit of fun, not really historical baggage...
  - superdisk 3y ago
    I did a code golf competition in college once where we could pick whatever language we wanted per problem. One problem was to format a number as a Roman numeral, and of course I won that one by just calling the built in Lisp function. Good times.
- nerdponx 3y ago
  As far as I understand, the SBCL compiles each function separately, and can fall back to very slow codepaths in doing so. Getting peak performance out of Common Lisp takes some effort.
  - kagevf 3y ago
    Wouldn't that just be while developing using the repl? I would think compile-file would compile the whole file, not just 1 function at a time ...?
deleted 3y ago
[deleted]
davexunit 3y ago
As mentioned by the author, "An Incremental Approach to Compiler Construction" [0] is one of the best papers I've ever read and I highly recommend reading it and implementing even just the first few steps. It was the first resource I found that made writing compilers approachable. I made it through about half of the steps (about as many as the author of this post) before setting it aside for awhile. I'd like to pick it back up and keep going sometime. I also recommend writing the compiler in lisp if you already know lisp, rather than C. :) [0] http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
- Jtsummers 3y ago
  https://mitpress.mit.edu/9780262047760/essentials-of-compilation/ https://mitpress.mit.edu/9780262047760/essentials-of-compila... Essentials of Compilation by Siek (Racket and Python versions available) are book-length treatments of that paper's topic.
  - davexunit 3y ago
    Ah, published in 2023! I missed this release. Ordered a copy. Thanks for the link!
  - pjmlp 3y ago
    Now I have to look into these as well for my library. Thanks for the heads up. :) By the way, for the Python folks with a Pi around, this one is also an interesting read to dive into what it means to write a compiler "Writing Interpreters and Compilers for the Raspberry Pi Using Python" https://www.amazon.com/Writing-Interpreters-Compilers-Raspberry-Python/dp/1977509207 https://www.amazon.com/Writing-Interpreters-Compilers-Raspbe...
cellularmitosis 3y ago
Whoa, what a treasure trove! https://bernsteinbear.com/pl-resources/ https://bernsteinbear.com/pl-resources/
mindcrime 3y ago
I could have sworn it was bernstainbear.com...
dang 3y ago
Related: Compiling a Lisp to x86_64 (2020) - https://news.ycombinator.com/item?id=26631308 https://news.ycombinator.com/item?id=26631308 - March 2021 (31 comments) Compiling a Lisp to x86-64: Labelled procedure calls - https://news.ycombinator.com/item?id=24931577 https://news.ycombinator.com/item?id=24931577 - Oct 2020 (13 comments) Compiling a Lisp: Instruction encoding interlude - https://news.ycombinator.com/item?id=24822534 https://news.ycombinator.com/item?id=24822534 - Oct 2020 (2 comments) Compiling a Lisp to x86-64: Heap allocation - https://news.ycombinator.com/item?id=24746587 https://news.ycombinator.com/item?id=24746587 - Oct 2020 (3 comments) Compiling a Lisp to x86-64: If expressions - https://news.ycombinator.com/item?id=24711072 https://news.ycombinator.com/item?id=24711072 - Oct 2020 (4 comments) Compiling a Lisp to x86-64: Let expressions - https://news.ycombinator.com/item?id=24652842 https://news.ycombinator.com/item?id=24652842 - Oct 2020 (39 comments) Compiling a Lisp: Reader - https://news.ycombinator.com/item?id=24580453 https://news.ycombinator.com/item?id=24580453 - Sept 2020 (27 comments) Compiling a Lisp to x86-64: Primitive binary functions - https://news.ycombinator.com/item?id=24490108 https://news.ycombinator.com/item?id=24490108 - Sept 2020 (1 comment) Compiling a Lisp to x86-64: primitive functions - https://news.ycombinator.com/item?id=24386826 https://news.ycombinator.com/item?id=24386826 - Sept 2020 (29 comments)
nanomonkey 3y ago
I'm a big LISP fan. Clojure syntax is my favorite, but Common lisp's ability to compile to native AND be interpreted is so damn impressive. Over the years I've toyed with running uLisp running on microcontrollers. There has been some work to add macros, and the running of assembly...so of course the next step would be to write a small compiler that can output RISKV and Arm thumb assembler so that I can reproduce the Genera LISP machine on and esp32 or teensy 4.0 driven handheld computer. That's the dream at least.
- samatman 3y ago
  There's an effort afoot to bring this to the Clojure world, with the lovely name jank: https://jank-lang.org https://jank-lang.org
  - nanomonkey 3y ago
    I guess to some extent there is also Ferret (Clojure to C++, https://ferret-lang.org/ https://ferret-lang.org/) and GraalVM if you want to compile Clojure. Thanks for the tip about jank!
ngcc_hk 3y ago
His interpreter series is “sadly” in ocaml. See https://bernsteinbear.com/blog/lisp/00_fundamentals/ https://bernsteinbear.com/blog/lisp/00_fundamentals/ hard to follow using 2 unfamiliar languages.
- tekknolagi 3y ago
  Lol they were written 4 years apart and don't even try to implement the same Lisp. Two different projects for two different learning experiences

114 points by swatson741 3y ago

dgan 3y ago

It's always amazes me how common lisp is so much more dynamic than, say, python, and is still compiled down to native code, and has running speed in the same ballpark as java/go/c#. Unfortunately it's not a simple language, and has much historical baggage (the standard has mandated Roman literals in formating, really guys?..)

wegfawefgawefg 3y ago
I dont think it is uniquely difficult compared to any other programming language. If anyone reading this has given up multiple times trying to learn lisp i encourage to keep trying. Its not really that different than python or javascript (Here me out). At first i genuinely couldnt understand it at all despite being well versed in tons of other languages, but after a few weeks, one day my brain suddenly could read it as if it was c++ or python. It was an instantanious switch. There is a sort of shape translation, like an affine transformation between lisp code and algol family stuff like c, etc. Once your brain sees the shapes of the paragraphs, and the function and class def shapes, you will not feel lisp is really different from the other languages except in form. ( excluding the macros. those are truly unique)
- pitherpather 3y ago
  > like an affine transformation between lisp code and algol family stuff like c I wonder how far one might go introducing common lisp with parallel examples in javascript and python -- something like a Rosetta Stone approach, also likening ')' and '}' and <dedent>.
  - wegfawefgawefg 3y ago
    Very far. actually thats probably a really good way to do it. lisp for python devs, amd its just basic python shit on the left page, and the clisp version on the right page. We do the same thing for human language books. Ive got a copy of the little prince where the left is in english and the right is in japanese. the bookstore is full of these.
whartung 3y ago
Well, the funny thing is that for base Common Lisp, it's less dynamic than you think. The functions and symbols in the core packages (e.g. COMMON-LISP package) are considered fixed and immutable. For example, out of the box, the compiler can assume that things like '+' aren't going to be redefined behind its back. It's assumptions like that can lead to very efficient code. But, at the same time, the core lisp language is actually not very dynamic, its more like your typical, compiled language in that sense. In contrast to say, Scheme, which has no presumptions. Out of the box, naive Scheme compilers can not make such assumptions. So, if you have something like: (set! a (+ x (- y (+ z w)))) The compiler actually has to look up (dispatch) '+' twice! Did '-' change the definition of '+'? Maybe...you don't know. So you can't (again naively) inline anything (not even counting the issues with numeric tower and types of the variables). So, what would ideally be a couple of simple machine instructions turns in to a huge endeavor.
- pfdietz 3y ago
  If Common Lisp allowed additional methods to be added to + (if they were generic functions, and if the new methods did not override the standard ones) without changing the existing methods, it would be possible to be just as efficient. That's because one could just dispatch as now and instead of erroring if nothing applied, instead check the new methods.
- davexunit 3y ago
  It is true that in Scheme you can shadow built-ins if you want, but a compiler would have to be extremely naive, perhaps lacking support for macros entirely, to not recognize primitive `+` from a user defined `+`. One of the very first transformations applied to the user program would be alpha conversion, where all user defined variables are replaced with program-unique names. At that point, the compiler would be absolutely sure that `+` is the primitive addition operator and compile it directly as an add primcall.
  - miloignis 3y ago
    I believe it is legal to actually reassign the global builtins, not just shadow them. Proving that a program doesn't do this is difficult to impossible, and I think some schemes give you an option to tell the compiler you won't do it. Chez Scheme has a section in their manual recommending pulling top level declarations into lets that it can analyze locally in order to optimize them.
deleted 3y ago
[deleted]
kagevf 3y ago
> the standard has mandated Roman literals in formating By the way, in case anyone is wondering what this is, it just means that you can use the FORMAT function to output Roman numbers. (format t "~@r" 4) ;; => IV You can also do: (format t "~r" 4) ;; => four and just interpolating the number would use "d": (format t "The number is: ~d" 4) ;; => The number is: 4
throwaway93941 3y ago
> historical baggage (the standard has mandated Roman literals in formating, really guys?..) Come now, it's not _that_ old :) It's just a bit of fun, not really historical baggage...
- superdisk 3y ago
  I did a code golf competition in college once where we could pick whatever language we wanted per problem. One problem was to format a number as a Roman numeral, and of course I won that one by just calling the built in Lisp function. Good times.
nerdponx 3y ago
As far as I understand, the SBCL compiles each function separately, and can fall back to very slow codepaths in doing so. Getting peak performance out of Common Lisp takes some effort.
- kagevf 3y ago
  Wouldn't that just be while developing using the repl? I would think compile-file would compile the whole file, not just 1 function at a time ...?

deleted 3y ago

[deleted]

davexunit 3y ago

As mentioned by the author, "An Incremental Approach to Compiler Construction" [0] is one of the best papers I've ever read and I highly recommend reading it and implementing even just the first few steps. It was the first resource I found that made writing compilers approachable. I made it through about half of the steps (about as many as the author of this post) before setting it aside for awhile. I'd like to pick it back up and keep going sometime. I also recommend writing the compiler in lisp if you already know lisp, rather than C. :) [0] http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

Jtsummers 3y ago
https://mitpress.mit.edu/9780262047760/essentials-of-compilation/ https://mitpress.mit.edu/9780262047760/essentials-of-compila... Essentials of Compilation by Siek (Racket and Python versions available) are book-length treatments of that paper's topic.
- davexunit 3y ago
  Ah, published in 2023! I missed this release. Ordered a copy. Thanks for the link!
- pjmlp 3y ago
  Now I have to look into these as well for my library. Thanks for the heads up. :) By the way, for the Python folks with a Pi around, this one is also an interesting read to dive into what it means to write a compiler "Writing Interpreters and Compilers for the Raspberry Pi Using Python" https://www.amazon.com/Writing-Interpreters-Compilers-Raspberry-Python/dp/1977509207 https://www.amazon.com/Writing-Interpreters-Compilers-Raspbe...

cellularmitosis 3y ago

Whoa, what a treasure trove! https://bernsteinbear.com/pl-resources/ https://bernsteinbear.com/pl-resources/

mindcrime 3y ago

I could have sworn it was bernstainbear.com...

dang 3y ago

Related: Compiling a Lisp to x86_64 (2020) - https://news.ycombinator.com/item?id=26631308 https://news.ycombinator.com/item?id=26631308 - March 2021 (31 comments) Compiling a Lisp to x86-64: Labelled procedure calls - https://news.ycombinator.com/item?id=24931577 https://news.ycombinator.com/item?id=24931577 - Oct 2020 (13 comments) Compiling a Lisp: Instruction encoding interlude - https://news.ycombinator.com/item?id=24822534 https://news.ycombinator.com/item?id=24822534 - Oct 2020 (2 comments) Compiling a Lisp to x86-64: Heap allocation - https://news.ycombinator.com/item?id=24746587 https://news.ycombinator.com/item?id=24746587 - Oct 2020 (3 comments) Compiling a Lisp to x86-64: If expressions - https://news.ycombinator.com/item?id=24711072 https://news.ycombinator.com/item?id=24711072 - Oct 2020 (4 comments) Compiling a Lisp to x86-64: Let expressions - https://news.ycombinator.com/item?id=24652842 https://news.ycombinator.com/item?id=24652842 - Oct 2020 (39 comments) Compiling a Lisp: Reader - https://news.ycombinator.com/item?id=24580453 https://news.ycombinator.com/item?id=24580453 - Sept 2020 (27 comments) Compiling a Lisp to x86-64: Primitive binary functions - https://news.ycombinator.com/item?id=24490108 https://news.ycombinator.com/item?id=24490108 - Sept 2020 (1 comment) Compiling a Lisp to x86-64: primitive functions - https://news.ycombinator.com/item?id=24386826 https://news.ycombinator.com/item?id=24386826 - Sept 2020 (29 comments)

nanomonkey 3y ago

I'm a big LISP fan. Clojure syntax is my favorite, but Common lisp's ability to compile to native AND be interpreted is so damn impressive. Over the years I've toyed with running uLisp running on microcontrollers. There has been some work to add macros, and the running of assembly...so of course the next step would be to write a small compiler that can output RISKV and Arm thumb assembler so that I can reproduce the Genera LISP machine on and esp32 or teensy 4.0 driven handheld computer. That's the dream at least.

samatman 3y ago
There's an effort afoot to bring this to the Clojure world, with the lovely name jank: https://jank-lang.org https://jank-lang.org
- nanomonkey 3y ago
  I guess to some extent there is also Ferret (Clojure to C++, https://ferret-lang.org/ https://ferret-lang.org/) and GraalVM if you want to compile Clojure. Thanks for the tip about jank!

ngcc_hk 3y ago

His interpreter series is “sadly” in ocaml. See https://bernsteinbear.com/blog/lisp/00_fundamentals/ https://bernsteinbear.com/blog/lisp/00_fundamentals/ hard to follow using 2 unfamiliar languages.

tekknolagi 3y ago
Lol they were written 4 years apart and don't even try to implement the same Lisp. Two different projects for two different learning experiences