[HN Gopher] Compiling a Lisp (2020)
___________________________________________________________________
Compiling a Lisp (2020)
Author : swatson741
Score : 87 points
Date : 2024-02-01 15:23 UTC (7 hours ago)
(HTM) web link (bernsteinbear.com)
(TXT) w3m dump (bernsteinbear.com)
| dgan wrote:
| 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 wrote:
| 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)
| whartung wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| p_l wrote:
| Scheme always felt less dynamic than Common Lisp to me,
| with less repl-messing capability.
|
| Both Scheme and CL let's you completely shadow any symbol
| in a given compilation unit, however.
| vindarel wrote:
| for those wanting generic +, equality and comparison in CL,
| there's a nice library: https://alex-gutev.github.io/generic-
| cl/
| pfdietz wrote:
| What would be nice is a way of having that generic +, but
| making it as efficient as builtin + on the standard numeric
| types. CL implementations do not currently have that
| capability (except perhaps if they make builtin + rather
| slow).
| taeric wrote:
| I'm guessing there are very few people out there that think
| of programs as that dynamic? Especially considering that the
| message you are quoting started from python, how does it
| compare there?
|
| I'm also curious to know why I would want something that was
| so dynamic that + could be redefined on me.
| Turing_Machine wrote:
| One that comes immediately to mind is that you might want +
| to handle vectors as well as scalars. Something like:
| (define scalar-sum +) (define (+ . arguments)
| (if (vectors? 'arguments) (vector-sum
| 'arguments) (apply scalar-sum arguments)))
| vectors? and vector-sum not shown for clarity.
|
| Edit: or maybe you want any sum in excess of (say) $5,000
| to alert a manager. (define old-plus +)
| (define (+ . args) (let ((value (apply old-plus
| args))) (if (> value 5000)
| (begin (alert-manager)
| value) value)))
|
| The nice thing here is that this Just Works anywhere +
| appears in the code. You don't need to put the conditional
| and the call to alert-manager everywhere you're calculating
| a sum. Of course, in a real implementation you'd want to
| pass stuff to alert-manager like what module you're in, the
| transaction number, etc.
| taeric wrote:
| Fair, I should have tried to use my imagination there.
| Basically operator overloading? I forgot that generic
| functions are different beasts, and I've rarely had need
| for this, myself.
| kazinator wrote:
| > _For example, out of the box, the compiler can assume that
| things like '+' aren't going to be redefined behind its
| back._
|
| Because it is undefined behavior to do so.
| kagevf wrote:
| > 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
| davexunit wrote:
| 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
| Jtsummers wrote:
| 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 wrote:
| Ah, published in 2023! I missed this release. Ordered a copy.
| Thanks for the link!
| cellularmitosis wrote:
| Whoa, what a treasure trove! https://bernsteinbear.com/pl-
| resources/
| mindcrime wrote:
| I could have sworn it was bernstainbear.com...
| dang wrote:
| Related:
|
| _Compiling a Lisp to x86_64 (2020)_ -
| 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 - Oct 2020 (13
| comments)
|
| _Compiling a Lisp: Instruction encoding interlude_ -
| 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 - Oct 2020 (3
| comments)
|
| _Compiling a Lisp to x86-64: If expressions_ -
| 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 - Oct 2020 (39
| comments)
|
| _Compiling a Lisp: Reader_ -
| 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 - Sept 2020 (1
| comment)
|
| _Compiling a Lisp to x86-64: primitive functions_ -
| https://news.ycombinator.com/item?id=24386826 - Sept 2020 (29
| comments)
| nanomonkey wrote:
| 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.
___________________________________________________________________
(page generated 2024-02-01 23:00 UTC)