# Multi-stage programming vs. defunctionalization **URL:** \ **Category:** Ecosystem\ **Tags:** metaprogramming, compilation\ **Created:** [August 8, 2024, 2:03am UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106 "2024-08-08T02:03:04Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![nated](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nated/32/6354_2.png) [@nated](https://discuss.ocaml.org/u/nated)\ **Post date:** [August 8, 2024, 2:03am UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106/1 "2024-08-08T02:03:04Z")
(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](https://langdev.stackexchange.com/questions/3996/multi-stage-programming-vs-monomorphization-defunctionalization) 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](https://okmij.org/ftp/ML/MetaOCaml.html) and [ppx\_stage](https://github.com/stedolan/ppx_stage)) and defunctionalization (à la [Roc](https://www.rwx.com/blog/how-roc-compiles-closures) and [Rust](https://rustc-dev-guide.rust-lang.org/backend/monomorph.html)) 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](https://dl.acm.org/doi/pdf/10.1145/3591260), and [it’s implementation in Roc](https://github.com/roc-lang/roc/issues/5969). The paper includes an implementation in OCaml (sort of - they transpile their own language to OCaml).) ---
**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\ **Post date:** [August 8, 2024, 7:11am UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106/2 "2024-08-08T07:11:56Z")
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. ```auto 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) ``` Cheers, Nicolas ---
**Author:** ![Frederic\_Loyer](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/frederic_loyer/32/3472_2.png) [@Frederic\_Loyer](https://discuss.ocaml.org/u/Frederic_Loyer)\ **Post date:** [August 8, 2024, 8:19am UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106/3 "2024-08-08T08:19:53Z")
I don’t think multi-stage programming is about using informations known at runtime. Perhaps you mean compile time. Let’s take: ```auto 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). ---
**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\ **Post date:** [August 8, 2024, 9:38am UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106/4 "2024-08-08T09:38:31Z")
> [@Frederic\_Loyer](#): > > Perhaps you mean compile time. Indeed, sorry for the confusion. (I edited my post to remove the confusing sentence.) Cheers, Nicolas ---
**Author:** ![nated](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nated/32/6354_2.png) [@nated](https://discuss.ocaml.org/u/nated)\ **Post date:** [August 8, 2024, 12:31pm UTC](https://discuss.ocaml.org/t/multi-stage-programming-vs-defunctionalization/15106/5 "2024-08-08T12:31:09Z")
> 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](https://github.com/stedolan/ppx_stage/blob/0b8494d31f8913945e5f69e61b443457fe48028e/README.md#binding) 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!