The Impossible Optimization, and the Metaprogramming To Achieve It

27 points by duck_tape

osa1

TLDR: Specializing a regexp interpreter based on constant regexp strings gives you efficient regexp functions.

zupa

This is an area of active research I believe, called staging compilation.

fanf

When I was reading around the literature recently, all the papers I found that use some variant of the term “staged” seemed to be based on the lisp tradition of macros with quasiquote and unquote. I couldn’t find anything that took an approach more like Zig or Mojo. I was hoping for something that connected the dots with dependent types, but type theory is mostly unconcerned with being clear about phase distinctions and which values are erased before run time. I’d love some pointers if you have any.
- zupa
  
  https://github.com/AndrasKovacs has worked out the theory of this, exactly what you are looking for as I understand. Look into his papers and repos, which should contain demos too.
  
  Then there is a language called Csip that implements it in practice, which is work in progress, not production ready yet. It is actively developed even though the github repo seem to be lagging. See https://github.com/faulhornlabs/csip
  
  Edit: ps: these guys come from a Haskell, Idris, Agda background
- andyc
  Hm yeah Zig has two "stages", but it doesn't have partial evaluation, as far as I know
  
  Instead you explicitly mark pieces of code comptime
  
  Back in 2019 I read a bunch about https://scala-lms.github.io/
  
  I didn't actually play with it, but there you can mix code more freely, and you control partial evaluation with type annotations
  
  I think the canonical example for partial evaluation is:
  
  def pow(m, n): .... var x = pow(m, 3) # can you specialize this to 3 multiplications?
  
  But that is just a compiler optimization. Whereas Scala LMS gives you more control over the evaluation, and I think Zig is more strictly "staged"
  
  A big difference is that Zig has a comptime interpreter, like the C++ constexpr interpreter
  
  While I think Scala LMS may take advantage of running on a JIT ... (or maybe I'm getting that confused with Graal, which definitely does)
kryptiskt

This reminded me of Hana Dusikova's compile-time regular expressions for C++: https://compile-time.re

It's a very useful library for performant regexes in C++, as long as you know what you want to match beforehand.