(Hello, sorry, this may or may not be on-topic here - please let me know if I should remove it. I asked this question on ProgLangDesign on Stack Exchange and haven’t gotten any answers, and I thought maybe there would be people here who could help me understand better.)
I believe the main purpose of both multi-stage programming (à la MetaOcaml and ppx_stage) and defunctionalization (à la Roc and Rust) is to remove some amount of indirection from compiled code - especially of calls to higher-order functions - although by fairly different approaches, with their own ramifications on a language’s design and implementation. (With MSP the programmer would do by-hand what a defunctionalizing compiler would do automatically.)
Is my understanding correct? If a language already does defunctionalization, are there any further benefits to be had by also supporting MSP?
(For what it’s worth, my question is inspired by reading about Lambda Set Specialization, and it’s implementation in Roc. The paper includes an implementation in OCaml (sort of - they transpile their own language to OCaml).)
Defunctionalization typically refers to a technique to eliminate higher-order functions (ie when you pass functions as arguments) by replacing them by a fixed sum type enumerating the possible closure shapes at every callsite. This requires making a global control flow analysis to get an exhaustive list of all functions that may “flow” to a given callsite.
Multi-stage programming, on the other hand, is a technique for runtime code generation. As such, it is not directly related to defunctionalization, at least superficially.
In fact, the standard example of meta-programming, the power function, is perfectly first-order and does not involve any higher-order construct, so would not benefit from defunctionalization in any obvious manner.
let square x = x * x
let rec power n x =
if n = 0 then 1
else if n mod 2 = 0 then square (power (n/2) x)
else x * (power (n-1) x)
I don’t think multi-stage programming is about using informations known at runtime.
Perhaps you mean compile time.
Let’s take:
let b = a *. (sqrt 2)
Here, sqrt 2 can be computed at compile time. It would be better to avoid the computation during the runtime.
It is a trivial example. Fftw uses multi-stage computing and can generate specialized functions which are fastest in the west
Multi-stage programming is available since 1970 (Forth integrates it naturally). But assembly languages may integrates some (macros, computed constants).
Multi-stage programming, on the other hand, is a technique for runtime code generation. As such, it is not directly related to defunctionalization, at least superficially.
I guess my thought was that what the programmer is primarily doing with runtime code generation, is building up a final program without as much indirection as it might otherwise have, just like a defunctionalizing compiler would do automatically. For example, in the staged version of List.map example in the ppx_stage README, it seems to me to be “stubbing out” exactly the same version of map plus1 that a defunctionalizing compiler would.
In fact, the standard example of meta-programming, the power function, is perfectly first-order and does not involve any higher-order construct, so would not benefit from defunctionalization in any obvious manner.
That’s a very good point, I’m not sure why the power example hadn’t occurred to me. I had the feeling that MSP’s primary usefulness came from providing a mechanism for “defunctionalization by hand”. But this demonstrates that it’s useful beyond that, which answers my question. Thank you!
