4 ms·

All of it. No restrictions on semantics. Existence proof - any compiler that has a first order IR. SML's mlton would be a good example.

perihelions 3y ago
"First order IR" in the sense of "without lambda abstractions"? Then I guess this [0] would be a decent starting point for understanding it? It seems to describe mlton's compiler pass for flattening the higher-order functional parts with some kind of flow analysis. (?) [0] http://www.mlton.org/guide/20130715/References.attachments/CejtinEtAl00.pdf http://www.mlton.org/guide/20130715/References.attachments/C... ("Flow-Directed Closure Conversion for Typed Languages")
- JonChesterfield 3y ago
  First order probably means no passing functions as values. That's somewhat imprecise, passing a function pointer to a function called call or apply seems fine. No passing closures around though. One way to go is compilation to combinators, which are functions that don't have a runtime representation of a lexical environment, aka functions that can be serialised as C without change in semantics. Basically add arguments to represent closed over data and rewrite call sites. On reflection I think continuation capture is a candidate for inherent overhead that cannot be eliminated - at least I can't currently see how to eliminate it - but then C can't do that. There's also the question of runtime cost of error detection, out of bounds etc, which C also doesn't do. You probably need whole program compilation to desugar everything. And I'm essentially claiming a sufficiently smart compiler can make functional languages as fast as imperative, which has dubious empirical support. Stuff like hash tables are hard to express without mutation or overhead. Still, mlton and stalin (r4rs scheme) take a reasonable stab at it. Probably fair to say that with today's compiler tech I'm wrong, but not in a fundamentally unsolvable tomorrow sort of way.

perihelions 3y ago

"First order IR" in the sense of "without lambda abstractions"? Then I guess this [0] would be a decent starting point for understanding it? It seems to describe mlton's compiler pass for flattening the higher-order functional parts with some kind of flow analysis. (?) [0] http://www.mlton.org/guide/20130715/References.attachments/CejtinEtAl00.pdf http://www.mlton.org/guide/20130715/References.attachments/C... ("Flow-Directed Closure Conversion for Typed Languages")

JonChesterfield 3y ago
First order probably means no passing functions as values. That's somewhat imprecise, passing a function pointer to a function called call or apply seems fine. No passing closures around though. One way to go is compilation to combinators, which are functions that don't have a runtime representation of a lexical environment, aka functions that can be serialised as C without change in semantics. Basically add arguments to represent closed over data and rewrite call sites. On reflection I think continuation capture is a candidate for inherent overhead that cannot be eliminated - at least I can't currently see how to eliminate it - but then C can't do that. There's also the question of runtime cost of error detection, out of bounds etc, which C also doesn't do. You probably need whole program compilation to desugar everything. And I'm essentially claiming a sufficiently smart compiler can make functional languages as fast as imperative, which has dubious empirical support. Stuff like hash tables are hard to express without mutation or overhead. Still, mlton and stalin (r4rs scheme) take a reasonable stab at it. Probably fair to say that with today's compiler tech I'm wrong, but not in a fundamentally unsolvable tomorrow sort of way.