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

11–20 of 40 posts

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

#11

Post by lioeters »

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 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.

¹ https://github.com/kanaka/mal

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

#12

Post by abecedarius »

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 abstraction" in Rust and C++.

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

#15

Post by monadic2 »

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.

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

#16

Post by dunefox »

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?

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

#18

Post by pfdietz »

moonchild wrote: post #8
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

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 optional arguments are or are not present.

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

#19

Post by sillysaurusx »

TylerE wrote: post #17
sillysaurusx wrote: post #13

(lets a 1 b 2 (+ a b)) is such a nice macro. Everything but the last expression are bindings.

Why is it nicer than (+ 1 2). What is gained from an extra layer of indirection?

Fewer parens. It was just a trivial example to illustrate the macro.

(lets (a b) (list 1 2) c (+ a 3) (d e f) (some-func a b c) (* d e f))

It destructures automatically. The equivalent traditional macro might look like

(destructuring-bind* [[(a b) (list 1 2)] [c (+ a 3)] [(d e f) (some-func a b c)]] (* d e f))

which is unreadable. And yeah, normally it's indented properly and yada-yada, and people use editor plugins like paredit to make it not such a pain to type, but still. It adds up.

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

#20

Post by _emacsomancer_ »

Joker_vD wrote: post #9
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-recursiv…

> Well, you've implemented let* :

    (let* ((a 1) (b a)) (+ a b))
I think this should just be plain let.

If I do:

     (define-syntax let-
      (syntax-rules ()
        [(_ ((x e) ...) b1 b2 ...)
         ((lambda (x ...) b1 b2 ...) e ...)]))
And then try:

       (let- ((a 2) (b a)) (+ a b))
I get:

     ; a: undefined;
     ;  cannot reference an identifier before its definition
     ;   in module: top-level
Post reply on HN