5 ms·

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 po

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 https://scheme.com/tspl4/further.html

moonchild 6y ago
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 https://www.youtube.com/watch?v=Wa81OJnlsoI
- pfdietz 6y ago
  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.
  - moonchild 6y ago
    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.
    - pfdietz 6y ago
      Let's go with this restatement. It's one of the features of Common Lisp that things that might be buried in the compiler in other languages are surfaced and made available to the user. This means a great deal of the language's standard functionality can be implemented as if it were in "user space". Macros, readtables, method combinations, setf expanders and generalized places, for example. IMO, if Common Lisp were to be extended (it probably won't be, at least officially, as there's no money for another whack at a standard) I think it would be best even if more "internal" features were surfaced this way, and made available for user extension.
Joker_vD 6y ago
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.
- _emacsomancer_ 6y ago
  > 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
  - bjoli 6y ago
    I don't really understand if you are surprised by that or not. That is the expected behaviour of regular let. Parallel binding. let* is sequential.
    - _emacsomancer_ 6y ago
      I'm not surprised by that. The parent suggested (or I thought that they did) that this was actually the definition for let* . And my point was to show that it does not behave like let* but rather like plain let.
abecedarius 6y ago
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++.
- pjmlp 6y ago
  Thanks for the hint, lots of interesting talks on the conference. https://legacy.cs.indiana.edu/dfried_celebration.html https://legacy.cs.indiana.edu/dfried_celebration.html
- hnlauncher 6y ago
  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-optimizations.html https://robert.ocallahan.org/2020/08/what-is-minimal-set-of-...?
  - abecedarius 6y ago
    Yes, thanks.
tekknolagi 6y ago
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.

moonchild 6y ago

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 https://www.youtube.com/watch?v=Wa81OJnlsoI

pfdietz 6y ago
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.
- moonchild 6y ago
  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.
  - pfdietz 6y ago
    Let's go with this restatement. It's one of the features of Common Lisp that things that might be buried in the compiler in other languages are surfaced and made available to the user. This means a great deal of the language's standard functionality can be implemented as if it were in "user space". Macros, readtables, method combinations, setf expanders and generalized places, for example. IMO, if Common Lisp were to be extended (it probably won't be, at least officially, as there's no money for another whack at a standard) I think it would be best even if more "internal" features were surfaced this way, and made available for user extension.

Joker_vD 6y ago

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.

_emacsomancer_ 6y ago
> 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
- bjoli 6y ago
  I don't really understand if you are surprised by that or not. That is the expected behaviour of regular let. Parallel binding. let* is sequential.
  - _emacsomancer_ 6y ago
    I'm not surprised by that. The parent suggested (or I thought that they did) that this was actually the definition for let* . And my point was to show that it does not behave like let* but rather like plain let.

abecedarius 6y ago

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

pjmlp 6y ago
Thanks for the hint, lots of interesting talks on the conference. https://legacy.cs.indiana.edu/dfried_celebration.html https://legacy.cs.indiana.edu/dfried_celebration.html
hnlauncher 6y ago
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-optimizations.html https://robert.ocallahan.org/2020/08/what-is-minimal-set-of-...?
- abecedarius 6y ago
  Yes, thanks.

tekknolagi 6y ago

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.