Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Compiling a Lisp to x86-64: Let expressions

bernsteinbear.com

Post reply on HN
Print view View original

1–10 of 40 posts

Re: Compiling a Lisp to x86-64: Let expressions

#3

Post by anaphor »

tekknolagi wrote: post #2

Thanks for posting! I'm the author and can answer any questions and receive any constructive criticism.

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.

Re: Compiling a Lisp to x86-64: Let expressions

#4

Post by tekknolagi »

anaphor wrote: post #3
tekknolagi wrote: post #2

Thanks for posting! I'm the author and can answer any questions and receive any constructive criticism.

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…

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.

Re: Compiling a Lisp to x86-64: Let expressions

#5

Post by anaphor »

tekknolagi wrote: post #4
anaphor wrote: post #3

Earlier quoted context omitted.

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…

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.

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 :)

Re: Compiling a Lisp to x86-64: Let expressions

#6

Post by tekknolagi »

anaphor wrote: post #5
tekknolagi wrote: post #4

Earlier quoted context omitted.

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.

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 :)

Awesome. Looking forward to it.

Re: Compiling a Lisp to x86-64: Let expressions

#7

Post by emmanueloga_ »

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

Re: Compiling a Lisp to x86-64: Let expressions

#8

Post by moonchild »

emmanueloga_ wrote: post #7

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…

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

Re: Compiling a Lisp to x86-64: Let expressions

#9

Post by Joker_vD »

emmanueloga_ wrote: post #7

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…

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.

Re: Compiling a Lisp to x86-64: Let expressions

#10

Post by timonoko »

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.
Post reply on HN