4 ms·

> A rather dogged and obnoxious opinion of mine is that the 'optimisation ceiling' for statically-typed, total functional programming languages is significantly

> A rather dogged and obnoxious opinion of mine is that the 'optimisation ceiling' for statically-typed, total functional programming languages is significantly higher than traditional imperative languages with comparably weak type systems. Curious about plans for this. When Haskell use exploded I followed a lot of the blogs talking about it someday being faster than C because purity made compiler reasoning easier and stream fusion and other things were going to change the world, but as time went on idiomatic Haskell never came even close to C. Now having a lot of performance experience I think a major factor is that functional languages insist on using lists for everything, which map poorly to hardware. Looking at your screenshots, it looks like it still employs the list paradigm.

zesterer 4y ago
So... I want to preface this by saying that I'm very, very far from being an expert on this topic. Although Tao's compiler has a MIR optimiser, it only covers the basics (inlining, constant folding + symbolic execution, etc.). I think one of the main reasons that Haskell failed to solve this is actually the same reason that many lower level languages failed: it places too many requirements on data representation. In the case of C/C++ and even (to a lesser extent) modern languages like Rust and Swift, this is because they make promises about representation to the programmer that allow you to circumvent aspects of the language and still write correct code: be it transmutation, casting, field offsets, etc. In the case of Haskell, lists have an entirely arbitrary length and the language makes no effort to constrain this requirement in the type system, meaning that the compiler can only speculatively optimise a list into an unboxed array. In a language with dependent types, it should be possible to constrain the size of a list with the type system, allowing the optimiser to do its job without need for speculative whole-program analysis. The other reason Haskell doesn't quite succeed is monomorphisation (or lack thereof). Haskell's support for first-class higher-ranked types means that the language can't feasibly make promises about monomorphisation, and as a result it needs to revert to boxing and dynamic dispatch far more than it really should. Conversely, Tao is designed to monomorphise in all cases from the start. Rust demonstrates that functional programming (and in particular, programming with higher-order functions) is more than possible to optimise very well, and it does this by promising monomorphisation through the type system, allowing the compiler to aggressively perform static dispatch and inlining. From what I've seen, GHC also fails to pick a lot of low-hanging fruit. The last time I checked (perhaps this has since changed) GHC often struggles with things like TCO and inlining in relatively simple cases as a byproduct of its design (all functions are dynamically dispatched by default, with inlining being a speculative optimisation). I need to do a little more writing about exactly what ideas I have for Tao, but other languages of similar ilk demonstrate that Haskell is very far from the pinnacle of what is possible (for example, Koka's Perceus reference reuse: https://koka-lang.github.io/koka/doc/book.html#why-perceus https://koka-lang.github.io/koka/doc/book.html#why-perceus).
- shadowofneptune 4y ago
  > all functions are dynamically dispatched by default, with inlining being a speculative optimisation Could you please point me to other approaches to inlining? I am also working on a personal language and it could be helpful.
  - zesterer 4y ago
    Rust gives each closure a unique type (see the `Fn` trait: https://doc.rust-lang.org/core/ops/trait.Fn.html https://doc.rust-lang.org/core/ops/trait.Fn.html), allowing the compiler to always statically dispatch to the exact function body at compile-time. That said, this is a rather more explicit approach that won't necessarily fit everything.

zesterer 4y ago

So... I want to preface this by saying that I'm very, very far from being an expert on this topic. Although Tao's compiler has a MIR optimiser, it only covers the basics (inlining, constant folding + symbolic execution, etc.). I think one of the main reasons that Haskell failed to solve this is actually the same reason that many lower level languages failed: it places too many requirements on data representation. In the case of C/C++ and even (to a lesser extent) modern languages like Rust and Swift, this is because they make promises about representation to the programmer that allow you to circumvent aspects of the language and still write correct code: be it transmutation, casting, field offsets, etc. In the case of Haskell, lists have an entirely arbitrary length and the language makes no effort to constrain this requirement in the type system, meaning that the compiler can only speculatively optimise a list into an unboxed array. In a language with dependent types, it should be possible to constrain the size of a list with the type system, allowing the optimiser to do its job without need for speculative whole-program analysis. The other reason Haskell doesn't quite succeed is monomorphisation (or lack thereof). Haskell's support for first-class higher-ranked types means that the language can't feasibly make promises about monomorphisation, and as a result it needs to revert to boxing and dynamic dispatch far more than it really should. Conversely, Tao is designed to monomorphise in all cases from the start. Rust demonstrates that functional programming (and in particular, programming with higher-order functions) is more than possible to optimise very well, and it does this by promising monomorphisation through the type system, allowing the compiler to aggressively perform static dispatch and inlining. From what I've seen, GHC also fails to pick a lot of low-hanging fruit. The last time I checked (perhaps this has since changed) GHC often struggles with things like TCO and inlining in relatively simple cases as a byproduct of its design (all functions are dynamically dispatched by default, with inlining being a speculative optimisation). I need to do a little more writing about exactly what ideas I have for Tao, but other languages of similar ilk demonstrate that Haskell is very far from the pinnacle of what is possible (for example, Koka's Perceus reference reuse: https://koka-lang.github.io/koka/doc/book.html#why-perceus https://koka-lang.github.io/koka/doc/book.html#why-perceus).

shadowofneptune 4y ago
> all functions are dynamically dispatched by default, with inlining being a speculative optimisation Could you please point me to other approaches to inlining? I am also working on a personal language and it could be helpful.
- zesterer 4y ago
  Rust gives each closure a unique type (see the `Fn` trait: https://doc.rust-lang.org/core/ops/trait.Fn.html https://doc.rust-lang.org/core/ops/trait.Fn.html), allowing the compiler to always statically dispatch to the exact function body at compile-time. That said, this is a rather more explicit approach that won't necessarily fit everything.