Compiling a Lisp to x86-64: Let expressions • Hacker News Board

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

#21

Post by moonchild » Fri, Oct 02, 2020, 2:04 AM UTC

pfdietz wrote: post #18

moonchild wrote: post #8

Earlier quoted context omitted.

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

That's really not true of Common Lisp implementations. These have many more than 20-30 functions, and they all have to be there because one can obtain them as values and pass those values around (and, in the case of standard generic functions, add new methods for them). There may be specific expansions for calls to particular standard functions when the types of the arguments are known, or when particular keyword and…

Well, of course; many of them will be functions, not macros.

What I mean is, there will only be 20~30 builtins; the rest can be implemented 'in userspace', as it were.

Though specifically in the case of cl, clos might complicate that somewhat, but probably not a ton.

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

#22

Post by timonoko » Fri, Oct 02, 2020, 2:20 AM UTC

dunefox wrote: post #16

timonoko wrote: post #10

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…

And?

Aint I clever? Realized rightaway that forwards JMPs to the next address could have been filled with NOPs instead. But this is not a beauty contest.

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

#23

Post by lioeters » Fri, Oct 02, 2020, 2:37 AM UTC

monadic2 wrote: post #15

lioeters wrote: post #11

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 ¹, 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 learn…

I can't recommend Lisp In Small Pieces enough. I prefer it to SICP.

Appreciate the recommendation! I was able to track down the author's page:

https://pages.lip6.fr/Christian.Queinnec/WWW/LiSP.html

..And someone who updated the book's source code to run on modern Schemes:

https://github.com/appleby/Lisp-In-Small-Pieces

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

#24

Post by ngcc_hk » Fri, Oct 02, 2020, 3:12 AM UTC

Seems good and reading. But it should explain or say it will cover the difference to c if c makes a distinction of statement and expression. And why that matter. Not throw a bone into the sky and assume we know it will later become a space station.

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

#25

Post by pjmlp » Fri, Oct 02, 2020, 5:37 AM UTC

abecedarius wrote: post #12

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…

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 a…

Thanks for the hint, lots of interesting talks on the conference.

https://legacy.cs.indiana.edu/dfried_celebration.html

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

#26

Post by tekknolagi » Fri, Oct 02, 2020, 5:39 AM UTC

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…

Good idea about the TOC.

Re: lambda: it's important to realize that this series is building up incrementally bigger features from nothing. This Lisp compiler won't have a full implementation of closures or even labeled procedures for some time. So right now we're getting used to name binding and using what we have.

While it's possible to generate the same code I did even when rewriting to lambda, you'll probably have to have some kind of strength reduction afterward.

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

#27

Post by tekknolagi » Fri, Oct 02, 2020, 5:40 AM UTC

lioeters wrote: post #11

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 ¹, 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 learn…

I'm so glad you're enjoying them!

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

#28

Post by tekknolagi » Fri, Oct 02, 2020, 5:42 AM UTC

amelius wrote: post #14

I wish these series on compilers would focus more on the harder parts, like JIT compilation or the virtual machine and concurrent garbage collecting.

You're more than welcome to your opinion, but I've explicitly outlined that those are non-goals of this series. Maybe maybe I'll get to caching or optimization.

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

#29

Post by tekknolagi » Fri, Oct 02, 2020, 5:43 AM UTC

ngcc_hk wrote: post #24

Seems good and reading. But it should explain or say it will cover the difference to c if c makes a distinction of statement and expression. And why that matter. Not throw a bone into the sky and assume we know it will later become a space station.

Good point! It's sort of a throwaway comment to handwave away linguistic differences. I'll try to make it better when I have access to a computer.

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

#30

Post by hnlauncher » Fri, Oct 02, 2020, 8:25 AM UTC

abecedarius wrote: post #12

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…

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 a…

By guaranteed optimisations talk, are you referring to this blog post by Robert O'Callahan: https://robert.ocallahan.org/2020/08/what-is-minimal-set-of-...?