[HN Gopher] Compiling a Lisp to x86-64: Let expressions
___________________________________________________________________
Compiling a Lisp to x86-64: Let expressions
Author : todsacerdoti
Score : 99 points
Date : 2020-10-01 16:26 UTC (6 hours ago)
(HTM) web link (bernsteinbear.com)
(TXT) w3m dump (bernsteinbear.com)
| timonoko wrote:
| Metoo 1982: C:\nokolisp
| (ncompile (macroexpand '(let ((x 1)) (+ x 1))))
| $09CB:$7188: JMP ?? ; see below
| $09CB:$718B: CALL $0ECD ; CALL ONEARG
| $09CB:$718E: PUSH [$012C]
| $09CB:$7192: MOV [$012C],AX
| $09CB:$7195: JMP ?? ; see below
| $09CB:$7198: PUSH [STACKMARK]
| $09CB:$719C: MOV [STACKMARK],SP
| $09CB:$71A0: MOV AX,[$012C]
| $09CB:$71A3: CALL $0F1D ; CALL NUMVAL
| $09CB:$71A6: MOV BX,$01
| $09CB:$71A9: ADD AX,BX
| $09CB:$71AB: CALL $05C9 ; CALL MAKNUM
| $09CB:$71AE: JMP $2080
| $09CB:$7195: JMP $71B1
| $09CB:$71B1: CALL $7198
| $09CB:$71B4: POP [$012C]
| $09CB:$71B8: JMP $1DA7
| $09CB:$7188: JMP $71BB
| $09CB:$71BB: MOV AX,$04 ; S-object 1
| $09CB:$71BE: CALL $718E
| $09CB:$71C1: JMP $1DA7 (subru:
| eval=$7188, compile=$3B6F)
|
| One pass, but corrects forward jumps afterwards.
| tekknolagi wrote:
| Thanks for posting! I'm the author and can answer any questions
| and receive any constructive criticism.
| anaphor wrote:
| I don't have any questions, but I just started reading it a few
| days ago, and I'm re-implementing it in Nim (which is an
| interesting experience). One issue I ran into right away was
| that my code from step 1 was segfaulting, and the issue was
| that I accidentally called `mprotect` before copying the memory
| into the buffer. Easy mistake to make, so you might want to add
| a warning for people who aren't just copy-pasting the code.
| tekknolagi wrote:
| Excellent! I'm so happy you're following along in another
| language. If you're developing in the open, can I link to it
| somewhere on the series?
|
| It's a good point and I'll try and remember to add a notice
| about order being important later.
| anaphor wrote:
| Once I'm ready I'm planning on throwing it up on github for
| sure. I'll make a note to send you an email with it :)
| tekknolagi wrote:
| Awesome. Looking forward to it.
| emmanueloga_ wrote:
| Critique: the TOC is only shown in first post and not clickable,
| makes it hard to navigate the series. It would also be nice to
| have the TOC repeated in each post.
|
| Question: I saw a chapter about unary functions. In some
| interpreters let bindings are explained as "sugar", or syntactic
| extensions on top of function calls. For instance `let` is not
| present in the core of scheme [1]. So in this way one could
| transform a let binding from: (let ((a 1) (b
| 2)) (+ a b))
|
| to: ((((lambda (a) (lambda (b) (+ a b))) 1) 2)
|
| through: (define-syntax let (syntax-
| rules () [(_ ((x e) ...) b1 b2 ...)
| ((lambda (x ...) b1 b2 ...) e ...)]))
|
| ... then you wouldn't need to compile let bindings, just function
| application, which some people call "desugaring".
|
| I was wondering if this kind of desugaring is used in practical
| lisp compilers or not... without knowing too much about lisp
| compilers, I imagine one reason to not go this way is that it
| could potentially generate way more code than compiling higher
| level concepts like `let` directly.
|
| 1: https://scheme.com/tspl4/further.html
| abecedarius wrote:
| Yes, real compilers do handle `((lambda (x) ...) ...)` as well
| as a `let`, because as a Lisp programmer you want to be able to
| define and use new macros freely, without having to worry too
| much about low-level optimizations. Kent Dybvig gave a talk on
| this sort of thing called the "macro-writer's Bill of Rights".
| It's a similar concept to the recent talk about what
| optimizations need to be guaranteed for "zero-cost abstraction"
| in Rust and C++.
| moonchild wrote:
| Most lisp compilers do exactly as you suggest. Generally, lisp
| is implemented on a small core of maybe 20~30 functions, with
| everything else as macros. If you're curious about how lisps
| are implemented, I recommend checking out this series:
| https://www.youtube.com/watch?v=Wa81OJnlsoI
| Joker_vD wrote:
| Well, you've implemented let* : (let* ((a 1)
| (b a)) (+ a b))
|
| is equivalent to: ((((lambda (a) (lambda (b)
| (+ a b))) a) 1)
|
| And anyway, implementing 'letrec' in C/Asm is really not that
| hard: allocate cells, assign names to them, compute the values.
| Compare that with the machinery of making closures (flat or
| linked?) and function invocation.
|
| I personally prefer to have 'letrec' as a primitive and
| implement non-recursive 'let' on top of it by checking whether
| any newly bound names are referenced from the bound values.
| lioeters wrote:
| Thanks to the author for an enjoyable intellectual journey, it's
| a wonderful series of articles.
|
| Having tried my hand at following the Make a Lisp project 1,
| implementing an interpreter in a couple of languages, it's
| fascinating to see the process of designing the language and
| compiler from the ground up, discussing various tradeoffs for
| simplicity, reasons for internal data structure, etc.
|
| In fact, I think I'm learning more about C99 than Lisp - there's
| something about creating a language (or just following along like
| me), by necessity it leads to the foundations of
| computing/programming, the concepts that make up the basis of all
| languages. It's a perfect (meta)subject for an educational
| project.
|
| 1 https://github.com/kanaka/mal
| amelius wrote:
| I wish these series on compilers would focus more on the harder
| parts, like JIT compilation or the virtual machine and concurrent
| garbage collecting.
| sillysaurusx wrote:
| (lets a 1 b 2 (+ a b)) is such a nice macro. Everything but the
| last expression are bindings.
___________________________________________________________________
(page generated 2020-10-01 23:01 UTC)