10 ms·

Creating a Common Lisp implementation, part 1 [video]

127 points by zeveb 6y ago

deleted 6y ago
[deleted]
moonchild 6y ago
> communication between programs uses pipes, requiring transitions through the kernel Not if you use shmem. > it's fairly primitive, because all you can pass is a sequence of bytes Assuming you have abi sorted out, you can generally write objects directly to a pipe. If you have indirections in those objects then, again, use shmem. (If you want synchrony, you can write the objects over the pipe but share the memory referred to by those functions.)
- monadic2 6y ago
  This mean OpenMPI, right? Not sure of what other cross platform provider of shmem there is.
  - moonchild 6y ago
    I'm not talking about any particular implementation. You could use openmpi. Or posix/sysv shm. Or whatever win32's equivalent is. Or any other facility—many languages have something like this built into their standard library.
    - monadic2 6y ago
      > I'm not talking about any particular implementation. Sure, but this needs to map to some implementation in the real world to be a meaningful sentiment. Surely you are aware there is zero standard for the functionality you're referring to. This leaves you with recommending OpenMPI, the only reliable cross-platform implementation of the functionality. If you don't care about cross-platform compatibility you might as well just hook straight into syscalls, which is referred to on linux (what you seem to be referring to) as shm.
      - moonchild 6y ago
        > Surely you are aware there is zero standard for the functionality you're referring to. Aside from being patently false—shared memory is standardized by IEEE 1003.1 POSIX[1][2][3] and supported on all modern unices—that's a pretty disingenuous and bad-faith assertion. But anyway: 1. 'shmem' refers generally to the ability of memory pages to mapped into multiple processes' address spaces. The existence (or lack thereof) of any particular implementation does not invalidate the broad point, which refers to a capability which tends to be implemented in some way on arbitrary platforms. Of course, if you want to develop a particular application which uses shared memory, you will want to make decisions about which platforms you want to support and how you want to support them. Of course, this may involve using platform abstraction layer (like openmpi), or building your own, or intentionally tying yourself to a platform or group of platforms. None of that has any bearing on my point, but it does lead to: 2. The functionality referred to in the linked video—that of composing multiple disparate applications with pipes—is one that is uniquely associated with unix. Thus, it is reasonable to assume that any critique of said functionality operates within the framework of unix. And all unices newer than 30 years implement sysv shmem[4]. 1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_shm.h.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy... 2. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_mman.h.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy... 3. https://pubs.opengroup.org/onlinepubs/9699919799/help/codes.html#SHM https://pubs.opengroup.org/onlinepubs/9699919799/help/codes.... 4. https://tldp.org/LDP/lpg/node21.html https://tldp.org/LDP/lpg/node21.html
        dang 6y ago
        Please make your substantive points without swipes like "that's a pretty disingenuous and bad-faith assertion". I know there was something of a provocation, but you'll represent your point of view much better (not to mention not poisoning the commons further) if you ignore that bit. Discussions like this are otherwise so high-quality that they're really worth taking care with. (Also, all of us longtime Lisp programmers should have a horror of what happens when swipes start to take over technical discussions.)
      - dang 6y ago
eatonphil 6y ago
I don't understand the point about tail call optimizations not being a part of C... Sure, but you can just rewrite the tail call into a loop and get the exact effect, no?
- moonchild 6y ago
  I'm not sure what he was talking about, but I can make a guess. According to the sysv abi, every function has to have a stack frame; so for strict conformance (e.g. for unwinding the stack), you should have a stack frame for every function. In practice, this is kinda dumb. Gcc/clang will do TCO (and won't even generate a stack frame if you pass -fomit-frame-pointer). There's no particular reason why the generated code should abide internally by the sysv abi, only that it be able to call external code written according to said abi (and pass callbacks to said external code, but you'd need thunks for that anyway to account for closures).
  - hyperion2010 6y ago
    I just wanted to record for posterity that after 14 years of reading it as fomit frame pointer this is the post where I finally realized that it is -f omit frame pointer. What are are fomit pointers and what do they do!? Well now I know.
    - agumonkey 6y ago
      And now I wonder what -f orce are
  - yvdriess 6y ago
    (for context: -fomit-frame-pointer causes the FP to not be saved on the stack, stack unwinding then relies on DWARF or compiler-internal information to unwind the stack.) I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK. - Only externally linked functions have to conform, so I can understand if TCO does not apply to mutually recursive external functions. Perhaps with LTO it can? - Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call.
drmeister 6y ago
I can testify to a lot of the difficulties Robert Strandh talks about here. We implemented a Common Lisp in C++ that interoperates with C++ (https://github.com/clasp-developers/clasp.git https://github.com/clasp-developers/clasp.git). I ended up implementing a lot more C++ code than I wanted to and then replacing much of it with Common Lisp versions (during startup) because it's easier to maintain and we can use type inference to improve the performance of Common Lisp code while C++ code is 'stuck' with the types you compile it with. Bootstrapping is hard.
- betterunix2 6y ago
  "we can use type inference" Technically you cannot use type inference in Common Lisp, only in a subset of the language. This is not hard to prove: you can embed a language for which general type inference is impossible (i.e. for which some expressions must have explicit type annotations), like System F, in Common Lisp. One of my complaints about Common Lisp is that the type system is really annoying when you have complex types.
  - aidenn0 6y ago
    Type inference isn't all-or-nothing. If you can infer even one type in one block of code, you can generate more efficient code.
  - reikonomusha 6y ago
    > One of my complaints... Then build a language and type system atop, like with Coalton [0]. Lisp is for language building. Even Hindley-Milner was first implemented atop Lisp in 1973 [1]. [0] https://github.com/stylewarning/coalton https://github.com/stylewarning/coalton [1] http://www-public.imtbs-tsp.eu/~gibson/Teaching/CSC4504/ReadingMaterial/GordonMMNW78.pdf http://www-public.imtbs-tsp.eu/~gibson/Teaching/CSC4504/Read...
- dleslie 6y ago
  I like what you're doing, but I really wish you'd provide debs and rpms for x86 and arm; I use common lisp on machines with very little ram, and compiling is too much of a hassle. FWIW, ecl and sbcl are my go-tos.
deleted 6y ago
[deleted]
rgrau 6y ago
This is part of a series that keeps happening in the Online Lisp Meetings that are held (bi?)weekly since the last ELS. Today there's one! https://mailman.common-lisp.net/pipermail/online-lisp-meets/2020-August/000027.html https://mailman.common-lisp.net/pipermail/online-lisp-meets/...
- phoe-krk 6y ago
  Online Lisp Meeting coordinator here for a shameless plug. If you have or do anything that is related to Lisp (any dialect, not just Common Lisp) and that you find interesting and would like to talk about, please let me know about it - this is precisely why the Online Lisp Meetings happen. I'll be glad to host your prerecorded video on Twitch while chat happens along the way and questions are asked and answered during the video - that's the formula that we've tested during this year's European Lisp Symposium (ELS) and what we've found to work rather well. Afterwards, the videos end up on YT on the aforelinked channel. Also, the meetings are held roughly bi-weekly, where the roughness means that there's a week or two of slippage now and then.

127 points by zeveb 6y ago

deleted 6y ago

[deleted]

> communication between programs uses pipes, requiring transitions through the kernel Not if you use shmem. > it's fairly primitive, because all you can pass is a sequence of bytes Assuming you have abi sorted out, you can generally write objects directly to a pipe. If you have indirections in those objects then, again, use shmem. (If you want synchrony, you can write the objects over the pipe but share the memory referred to by those functions.)

monadic2 6y ago
This mean OpenMPI, right? Not sure of what other cross platform provider of shmem there is.
- moonchild 6y ago
  I'm not talking about any particular implementation. You could use openmpi. Or posix/sysv shm. Or whatever win32's equivalent is. Or any other facility—many languages have something like this built into their standard library.
  - monadic2 6y ago
    > I'm not talking about any particular implementation. Sure, but this needs to map to some implementation in the real world to be a meaningful sentiment. Surely you are aware there is zero standard for the functionality you're referring to. This leaves you with recommending OpenMPI, the only reliable cross-platform implementation of the functionality. If you don't care about cross-platform compatibility you might as well just hook straight into syscalls, which is referred to on linux (what you seem to be referring to) as shm.
    - moonchild 6y ago
      > Surely you are aware there is zero standard for the functionality you're referring to. Aside from being patently false—shared memory is standardized by IEEE 1003.1 POSIX[1][2][3] and supported on all modern unices—that's a pretty disingenuous and bad-faith assertion. But anyway: 1. 'shmem' refers generally to the ability of memory pages to mapped into multiple processes' address spaces. The existence (or lack thereof) of any particular implementation does not invalidate the broad point, which refers to a capability which tends to be implemented in some way on arbitrary platforms. Of course, if you want to develop a particular application which uses shared memory, you will want to make decisions about which platforms you want to support and how you want to support them. Of course, this may involve using platform abstraction layer (like openmpi), or building your own, or intentionally tying yourself to a platform or group of platforms. None of that has any bearing on my point, but it does lead to: 2. The functionality referred to in the linked video—that of composing multiple disparate applications with pipes—is one that is uniquely associated with unix. Thus, it is reasonable to assume that any critique of said functionality operates within the framework of unix. And all unices newer than 30 years implement sysv shmem[4]. 1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_shm.h.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy... 2. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_mman.h.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy... 3. https://pubs.opengroup.org/onlinepubs/9699919799/help/codes.html#SHM https://pubs.opengroup.org/onlinepubs/9699919799/help/codes.... 4. https://tldp.org/LDP/lpg/node21.html https://tldp.org/LDP/lpg/node21.html
      - dang 6y ago
        Please make your substantive points without swipes like "that's a pretty disingenuous and bad-faith assertion". I know there was something of a provocation, but you'll represent your point of view much better (not to mention not poisoning the commons further) if you ignore that bit. Discussions like this are otherwise so high-quality that they're really worth taking care with. (Also, all of us longtime Lisp programmers should have a horror of what happens when swipes start to take over technical discussions.)
    - dang 6y ago

eatonphil 6y ago

I don't understand the point about tail call optimizations not being a part of C... Sure, but you can just rewrite the tail call into a loop and get the exact effect, no?

moonchild 6y ago
I'm not sure what he was talking about, but I can make a guess. According to the sysv abi, every function has to have a stack frame; so for strict conformance (e.g. for unwinding the stack), you should have a stack frame for every function. In practice, this is kinda dumb. Gcc/clang will do TCO (and won't even generate a stack frame if you pass -fomit-frame-pointer). There's no particular reason why the generated code should abide internally by the sysv abi, only that it be able to call external code written according to said abi (and pass callbacks to said external code, but you'd need thunks for that anyway to account for closures).
- hyperion2010 6y ago
  I just wanted to record for posterity that after 14 years of reading it as fomit frame pointer this is the post where I finally realized that it is -f omit frame pointer. What are are fomit pointers and what do they do!? Well now I know.
  - agumonkey 6y ago
    And now I wonder what -f orce are
- yvdriess 6y ago
  (for context: -fomit-frame-pointer causes the FP to not be saved on the stack, stack unwinding then relies on DWARF or compiler-internal information to unwind the stack.) I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK. - Only externally linked functions have to conform, so I can understand if TCO does not apply to mutually recursive external functions. Perhaps with LTO it can? - Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call.

drmeister 6y ago

I can testify to a lot of the difficulties Robert Strandh talks about here. We implemented a Common Lisp in C++ that interoperates with C++ (https://github.com/clasp-developers/clasp.git https://github.com/clasp-developers/clasp.git). I ended up implementing a lot more C++ code than I wanted to and then replacing much of it with Common Lisp versions (during startup) because it's easier to maintain and we can use type inference to improve the performance of Common Lisp code while C++ code is 'stuck' with the types you compile it with. Bootstrapping is hard.

betterunix2 6y ago
"we can use type inference" Technically you cannot use type inference in Common Lisp, only in a subset of the language. This is not hard to prove: you can embed a language for which general type inference is impossible (i.e. for which some expressions must have explicit type annotations), like System F, in Common Lisp. One of my complaints about Common Lisp is that the type system is really annoying when you have complex types.
- aidenn0 6y ago
  Type inference isn't all-or-nothing. If you can infer even one type in one block of code, you can generate more efficient code.
- reikonomusha 6y ago
  > One of my complaints... Then build a language and type system atop, like with Coalton [0]. Lisp is for language building. Even Hindley-Milner was first implemented atop Lisp in 1973 [1]. [0] https://github.com/stylewarning/coalton https://github.com/stylewarning/coalton [1] http://www-public.imtbs-tsp.eu/~gibson/Teaching/CSC4504/ReadingMaterial/GordonMMNW78.pdf http://www-public.imtbs-tsp.eu/~gibson/Teaching/CSC4504/Read...
dleslie 6y ago
I like what you're doing, but I really wish you'd provide debs and rpms for x86 and arm; I use common lisp on machines with very little ram, and compiling is too much of a hassle. FWIW, ecl and sbcl are my go-tos.

deleted 6y ago

[deleted]

rgrau 6y ago

This is part of a series that keeps happening in the Online Lisp Meetings that are held (bi?)weekly since the last ELS. Today there's one! https://mailman.common-lisp.net/pipermail/online-lisp-meets/2020-August/000027.html https://mailman.common-lisp.net/pipermail/online-lisp-meets/...

phoe-krk 6y ago
Online Lisp Meeting coordinator here for a shameless plug. If you have or do anything that is related to Lisp (any dialect, not just Common Lisp) and that you find interesting and would like to talk about, please let me know about it - this is precisely why the Online Lisp Meetings happen. I'll be glad to host your prerecorded video on Twitch while chat happens along the way and questions are asked and answered during the video - that's the formula that we've tested during this year's European Lisp Symposium (ELS) and what we've found to work rather well. Afterwards, the videos end up on YT on the aforelinked channel. Also, the meetings are held roughly bi-weekly, where the roughness means that there's a week or two of slippage now and then.