5 ms·

This presentation is very good! A few days ago, I started thinking how code from a functional language could be converted to imperative code for better performa

This presentation is very good! A few days ago, I started thinking how code from a functional language could be converted to imperative code for better performance, with in-place operations (instead of object regeneration) and a complex (and likely slow) optimizing compiler. However, things like closures, composition at runtime and partial function application just made everything 10x harder.

utterwise 3y ago
> However, things like closures, composition at runtime and partial function application just made everything 10x harder. Closures are just functions with an extra parameter for the environment (free variables). Subsequent passes after desugaring can treat them like any other function. Function composition and currying should also be static transformations. Maybe you made it harder than it has to be?
- tsegratis 3y ago
  If functions are higher order then the distinction between plain functions and closures is retained (unless you treat all functions as closures). This is because the data needs to be passed around in the function pointer. If not higher order then yes, they desugar Implementing these things is maybe easy for you ;) but for myself, doing it well, I would definitely not describe as a walk in the park
  - utterwise 3y ago
    It is true you need to pass the environment around, but if the language you are implementing also has objects or structs then you will need to implement that anyway. My main objection to the grand parent is the idea that functional languages are 10x more difficult to implement than mainstream languages. Maybe that is true for Haskell, but most functional features can be compiled efficiently without much additional complexity. The complexity added by closures for instance would be closer to 1% than 10x.
wiz21c 3y ago
for real "fun", have a look at continuations :-)
perihelions 3y ago
That's the same curiosity that led me here: how much of higher-order functional programming could be implemented as zero-overhead abstractions over a C-like language, and what restrictions on language semantics would be the tradeoff?
- quickthrower2 3y ago
  State monad as a first class language construct might help? You could allow actual mutations inside that and therefore if a lot of computation needs doing it could be more efficient.
- JonChesterfield 3y ago
  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.

utterwise 3y ago

> However, things like closures, composition at runtime and partial function application just made everything 10x harder. Closures are just functions with an extra parameter for the environment (free variables). Subsequent passes after desugaring can treat them like any other function. Function composition and currying should also be static transformations. Maybe you made it harder than it has to be?

tsegratis 3y ago
If functions are higher order then the distinction between plain functions and closures is retained (unless you treat all functions as closures). This is because the data needs to be passed around in the function pointer. If not higher order then yes, they desugar Implementing these things is maybe easy for you ;) but for myself, doing it well, I would definitely not describe as a walk in the park
- utterwise 3y ago
  It is true you need to pass the environment around, but if the language you are implementing also has objects or structs then you will need to implement that anyway. My main objection to the grand parent is the idea that functional languages are 10x more difficult to implement than mainstream languages. Maybe that is true for Haskell, but most functional features can be compiled efficiently without much additional complexity. The complexity added by closures for instance would be closer to 1% than 10x.

wiz21c 3y ago

for real "fun", have a look at continuations :-)

perihelions 3y ago

That's the same curiosity that led me here: how much of higher-order functional programming could be implemented as zero-overhead abstractions over a C-like language, and what restrictions on language semantics would be the tradeoff?

quickthrower2 3y ago
State monad as a first class language construct might help? You could allow actual mutations inside that and therefore if a lot of computation needs doing it could be more efficient.
JonChesterfield 3y ago
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.