4 ms·

Multi-Stage Programming with Splice Variables

54 points by matt_d 1y ago

TimorousBestie 1y ago
This is fascinating. I could see it being very useful for writing SIMD abstraction layers (like Highway or SIMDe) without so much of the cruft.
deleted 1y ago
[deleted]
kldx 1y ago
> For example, instead of a power function that uses a loop, you could generate specialized code like x * x * x * x * x directly. This eliminates runtime overhead and creates highly optimized code. Could anyone explain to me how this is different from templates or parameter pack expansion in C++? I can see the constexpr-ness here is encoded in the type system and appears more composable, but I am not sure if I am missing the point. I looked at the paper but I can't find anything related to C++.
- gsliepen 1y ago
  > Could anyone explain to me how this is different from templates or parameter pack expansion in C++? I don't think it's any different. > I can see the constexpr-ness here is encoded in the type system I also see they introduce new constructs like let$, so it's not just a type system thing. > I looked at the paper but I can't find anything related to C++. I don't think the author needs to compare their code to C++. That said, it looks to me like it is similar to the upcoming C++26's reflection capabilities.
  - naasking 1y ago
    Typically, multistage languages permit program generation at any stage, including runtime. So that would be different than C++.
    - gsliepen 1y ago
      You can get pretty far in C++ though: https://codereview.stackexchange.com/questions/259045/poor-mans-jit-using-nested-lambdas https://codereview.stackexchange.com/questions/259045/poor-m...
      - naasking 1y ago
        This looks like a reinvention of the final, tagless interpreter, which has been a great, common technique in functional languages for awhile: https://okmij.org/ftp/tagless-final/index.html#tagless-final https://okmij.org/ftp/tagless-final/index.html#tagless-final It's an interpreter though, not a JIT. This kind of programming language thing is a bit of a hobby horse of mine, so see the comment I just posted on this for full details: https://codereview.stackexchange.com/questions/259045/poor-mans-jit-using-nested-lambdas/297544#297544 https://codereview.stackexchange.com/questions/259045/poor-m...
perihelions 1y ago
How is this different from a syntactic macro?
- burakemir 1y ago
  Two big differences: - it is typed, and - multi-stage programming can also describe runtime-code generation.
gsliepen 1y ago
> For example, instead of a power function that uses a loop, you could generate specialized code like x * x * x * x * x directly. This eliminates runtime overhead and creates highly optimized code. This is misguided. For decennia now, there is no reason to assume that hand-unrolled code is faster than a for-loop. Compilers optimize this stuff, and they do this even better than mindlessly multiplying x by itself. For example, raising x to the power 6 only needs 3 multiplications, see for example: https://godbolt.org/z/Edz4jjqvv https://godbolt.org/z/Edz4jjqvv While there are definitely use cases for meta-programming, optimization is not one of them.
- naasking 1y ago
  Optimization is absolutely one of them, once you start dealing with higher order programs or programs with sophisticated control flow. Compiler optimizations are not enough to infer the Futamura projections in all cases, for instance. https://okmij.org/ftp/tagless-final/index.html#tagless-final https://okmij.org/ftp/tagless-final/index.html#tagless-final
  - gsliepen 1y ago
    Interesting, I never heard of Futamura projections before. Looking at the definition, it seems like the first projection (specializing an interpreter for given source code) is already handled pretty well by today's compilers, just by unrolling and inlining. And they can go even further and evaluate parts at compile time, see for example https://github.com/IoanThomas/constexpr-chip8 https://github.com/IoanThomas/constexpr-chip8. I can see how the second and third projections are not handled by compiler optimizations though.
- finiteparadox 1y ago
  The point is that compiler optimisations are a black box and not guaranteed. They can be very brittle wrt to seemingly harmless source changes (even something as simple as making an extra intermediate assignment). You are at the mercy of the 'fuel' of the optimisation passes. With staging you get to control exactly what gets inlined/partially evaluated. Of course, to get good results you need to know what to optimise for.
captainbland 1y ago
Does this have practical advantages over JIT runtime optimisation used in e.g the JVM? My assumption is that maybe you can generate optimised code perhaps without as much analytical overhead of the JVM or more specific optimisations (so controlled by the programmer) but honestly the details of how this might compare in practice are a bit over my head.

54 points by matt_d 1y ago

This is fascinating. I could see it being very useful for writing SIMD abstraction layers (like Highway or SIMDe) without so much of the cruft.

deleted 1y ago

[deleted]

kldx 1y ago

> For example, instead of a power function that uses a loop, you could generate specialized code like x * x * x * x * x directly. This eliminates runtime overhead and creates highly optimized code. Could anyone explain to me how this is different from templates or parameter pack expansion in C++? I can see the constexpr-ness here is encoded in the type system and appears more composable, but I am not sure if I am missing the point. I looked at the paper but I can't find anything related to C++.

gsliepen 1y ago
> Could anyone explain to me how this is different from templates or parameter pack expansion in C++? I don't think it's any different. > I can see the constexpr-ness here is encoded in the type system I also see they introduce new constructs like let$, so it's not just a type system thing. > I looked at the paper but I can't find anything related to C++. I don't think the author needs to compare their code to C++. That said, it looks to me like it is similar to the upcoming C++26's reflection capabilities.
- naasking 1y ago
  Typically, multistage languages permit program generation at any stage, including runtime. So that would be different than C++.
  - gsliepen 1y ago
    You can get pretty far in C++ though: https://codereview.stackexchange.com/questions/259045/poor-mans-jit-using-nested-lambdas https://codereview.stackexchange.com/questions/259045/poor-m...
    - naasking 1y ago
      This looks like a reinvention of the final, tagless interpreter, which has been a great, common technique in functional languages for awhile: https://okmij.org/ftp/tagless-final/index.html#tagless-final https://okmij.org/ftp/tagless-final/index.html#tagless-final It's an interpreter though, not a JIT. This kind of programming language thing is a bit of a hobby horse of mine, so see the comment I just posted on this for full details: https://codereview.stackexchange.com/questions/259045/poor-mans-jit-using-nested-lambdas/297544#297544 https://codereview.stackexchange.com/questions/259045/poor-m...

perihelions 1y ago

How is this different from a syntactic macro?

burakemir 1y ago
Two big differences: - it is typed, and - multi-stage programming can also describe runtime-code generation.

gsliepen 1y ago

> For example, instead of a power function that uses a loop, you could generate specialized code like x * x * x * x * x directly. This eliminates runtime overhead and creates highly optimized code. This is misguided. For decennia now, there is no reason to assume that hand-unrolled code is faster than a for-loop. Compilers optimize this stuff, and they do this even better than mindlessly multiplying x by itself. For example, raising x to the power 6 only needs 3 multiplications, see for example: https://godbolt.org/z/Edz4jjqvv https://godbolt.org/z/Edz4jjqvv While there are definitely use cases for meta-programming, optimization is not one of them.

naasking 1y ago
Optimization is absolutely one of them, once you start dealing with higher order programs or programs with sophisticated control flow. Compiler optimizations are not enough to infer the Futamura projections in all cases, for instance. https://okmij.org/ftp/tagless-final/index.html#tagless-final https://okmij.org/ftp/tagless-final/index.html#tagless-final
- gsliepen 1y ago
  Interesting, I never heard of Futamura projections before. Looking at the definition, it seems like the first projection (specializing an interpreter for given source code) is already handled pretty well by today's compilers, just by unrolling and inlining. And they can go even further and evaluate parts at compile time, see for example https://github.com/IoanThomas/constexpr-chip8 https://github.com/IoanThomas/constexpr-chip8. I can see how the second and third projections are not handled by compiler optimizations though.
finiteparadox 1y ago
The point is that compiler optimisations are a black box and not guaranteed. They can be very brittle wrt to seemingly harmless source changes (even something as simple as making an extra intermediate assignment). You are at the mercy of the 'fuel' of the optimisation passes. With staging you get to control exactly what gets inlined/partially evaluated. Of course, to get good results you need to know what to optimise for.

captainbland 1y ago

Does this have practical advantages over JIT runtime optimisation used in e.g the JVM? My assumption is that maybe you can generate optimised code perhaps without as much analytical overhead of the JVM or more specific optimisations (so controlled by the programmer) but honestly the details of how this might compare in practice are a bit over my head.