What is this programming style? “Monoid-ic”?

Question

In a moderately old blog post, Conal Elliot makes an interesting (if less than serious) argument that C is a purely functional language, by drawing a parallel between the combination of the C preprocessor and C itself, and that of Haskell's pure expression language and its impure IO action values. It's observed further down that the phase separation between C's components actually makes what cpp does quite different from Haskell, though, so cpp+C is not monadic after all.

In real programming projects, C programmers prefer to minimize their use of cpp as far as possible. The macro language may be capable of amazing things, but it's a fairly hostile programming environment. So as far as I can tell this concept is mostly unexplored from a C perspective.

However, building on the example of C, we could envisage a language where the primary way of programming is for the developer to write a purely functional program which builds a fixed sequence of action values and strings them together into a finished program. Distinct from Haskell's model in that the functional program only exists at "compile time", with a clear separation between the two stages of evaluation and execution; distinct from C's model (or Lisp's) mainly in the emphasis on the "macro" stage as the primary programming tool (and with a macro stage that isn't.. y'know, horrible - rather, it looks and runs like the full-fledged language), with the end program consisting of a fixed sequence of "action" building-blocks that the developer is discouraged (or even prevented) from authoring directly.

• Does this programming paradigm exist? If so, what is it called and what are existing examples of it? Is there any literature on this topic?

("Metaprogramming" is the obvious answer, but that seems too broad and off-target: cpp or C++ templates as they're currently lightly-used also fall under that, while Haskell IO doesn't.)

Answer 1

Turns out the paradigm described (badly) in the question does exist, and is known as "multi-staged programming", "staged metaprogramming", or similar words to that effect. According to this taxonomy, the question is envisaging the "static generator" (as opposed to those systems that use staging for dynamic code generation).

Staged programming is distinct from classic macros in that it implies a deeper understanding by the compiler of the code being processed: macros are traditionally syntactic, the code-as-data being a simple structure of atoms, whereas "MSP" maintains and checks type and scope information, and handles only valid, whole expressions as single values; from these it's able to build well-typed and syntactically valid output. (One could certainly write Lisp/Scheme macros to do this - it's been done - but it's not part of their core functionality.) Staging therefore appears to be more closely related to partial evaluation than to macros.

Knowing what it's called, there are many examples and papers to look at:

• MetaOCaml (OCaml with staging annotations), tutorial introduction
• MetaML (similar work for SML), example
• an explanation courtesy of CS.se
• Mint, an example of MSP working with an imperative output language (in this case, Java)
• tickc, a runtime/dynamic MSP system extending C (not to be confused with the more well-known tcc compiler)

(Hindsight note: in effect, what the question envisaged was using something like MetaML for the metalanguage with C as the output language, running the metalanguage only at compile-time.)