Mind is getting blown by multi-stage programming! Does anyone know of any simple examples of it being used as a way of doing offline partial evaluation in compilation? Most of the stuff I see is for run-time code generation. 🤔
Conversation
There's this paper about static staging: cs.utexas.edu/users/mckinley
That said, it isn't clear to me what the difference is between typed macros and static staging -- syntactic flexibility vs rigidity?
2
1
I think there is some correspondence, but I don't know. The annoying thing about full spectrum dependent types is that you lose the phase information that is present in traditional languages, so it's hard to compile things like type parameters and constant parameters efficiently.
2
Languages like D, C++ and Zig, Rust etc. get around this with constexpr and monomorphized type parameters, but it always seems rather tacked-on, and you can't seem to get the full expressiveness of dependent types then if you ever need that.
2
Ah, I think I see what you're saying. Have some partial evaluation and do specialization at run time based on the types passed. Is that right? A JIT would solve the problem, no? Is the question about partial evaluation to reduce JITting overhead? Not sure where staging comes in.
1
I want this to be ‘offline’ - ie. at compile time, for systems programming purposes. I also want the programmer to know when they break these optimisations - ie. as a type error.
1
Ok, gotcha'! I didn't get this bit though:
> you can't seem to get the full expressiveness of dependent types then if you ever need that.
constexpr let's you do computations with values at compile time. Dependent type let you do computation with types at run time. Why not both?
1
That’s exactly it! I want both! But I want to generate efficient code without relying on a JIT. Being able opt in to a JIT for runtime stuff would be super neat though.
2
That cannot work generally though. Say you pass a function an Array Int if a runtime arg was 1, Array (Array Int) if it was 2 and so on. You cannot possibly create all specializations ahead of time. It's the same problem as with rank-2 types. Maybe ban polymorphic recursion...
1
Replying to
That seems like a case where you would need some runtime behaviour, and specialization would not be possible which I'm cool with. But I'd like the programmer to know this, potentially by way of the type system/annotations like in this paper:
Quote Tweet
Replying to @brendanzab
Check out this paper for one way of approaching it: "Multi-Stage Programming with Explicit Annotations" citeseerx.ist.psu.edu/viewdoc/downlo