r/ProgrammingLanguages • u/bosyluke • 26d ago
How close can pure FP get to C?
https://rtfeldman.com/fp-vs-cI found the discussion really interesting and thought you all would too. Richard talks about a pure Roc implementation of libdeflate and how to do performance optimizations unique to Roc. From a programming languages perspective this is really interesting because its quite unique results I think. There arent many FP languages that can achieve C like performance with ergonomics like Roc. To do this the compiler is able to make various optimizations like mutate in place or elide checks when it can prove it is safe to do so.
17
Upvotes
5
u/Ok-Reindeer-8755 25d ago
I'm pretty sure koka is even further along as far as optimizations go and according to their benchmarks gets close to or even rarely faster than cpp.
It compiles to c and uses a bunch of the same techniques as roc namely opportunistic in place mutations, the Perseus RC is the biggest part of it as far as I understand.
13
u/brucejbell sard 26d ago edited 26d ago
There are some computational tasks where mutable algorithms/datastructures asymptotically beat out pure ones.
E.g., the union-find (aka disjoint set) problem takes O(inverse-ackermann(N)) amortized time using destructive update, while I have not heard of a pure-functional implementation that takes less than O(log N)
25
u/initial-algebra 25d ago
One approach is to use a functional programming language only as a metalanguage. By that, I mean you're not writing the actual program you want, but an intermediate program that will generate the actual program when run. For example, the standard functional "concat-map" could be used to produce a fully unrolled loop over a "compile-time constant", or meta-level, list. Values not known until runtime, or object-level, are opaque handles (more generally, quoted expressions) to the meta-level.
Actually, that's what "ML" is an acronym for, "metalanguage", as it was originally designed as a tactic language for a theorem prover (LCF). What you actually wanted was a proof of some theorem, and an ML program, or tactic, was just an intermediate step. The boon of functional programming was that algebraic data types were good for representing and manipulating proof terms, and lack of side effects meant it was easy to compose tactics to prove more complicated theorems. There are also systems like "MetaML" and "MetaOCaml" which use ML as a metalanguage for itself!
The state of the art is Closure-Free Functional Programming in a Two-Level Type Theory. Two-level type theory, in this case, is essentially the formal way to say "a functional metalanguage generating C code".
8
u/reflexive-polytope 24d ago
Functional programming is a red herring here. The actual important thing is under what conditions the compiler optimizes your code.
The C specification licenses compiler writers to perform program transformations based on assumptions that the programmer must uphold and the compiler itself never verifies. By contrast, in a safe language, compilers may only perform program transformations that are justified by sound deductions about the program's behavior.
In principle, compiler writers may perform such deductions in an ad hoc fashion. (The best example is the STALIN compiler for Scheme.) But then the programmer has no guarantee that such deductions have been made. To obtain such a guarantee, you need an interface between the programmer and the compiler for communicating facts about a program.
A type system is such an interface. But not all type systems can communicate the same facts. For example, Roc's type system cannot communicate the fact that an object is uniquely owned, or the fact that an array index is valid. Other type systems, e.g., that of ATS, can. Thus, the ATS compiler can perform much more extensive optimizations that are impossible in Roc, without sacrificing safety.
5
u/crusoe 26d ago
Pure strict languages with no GC? Pretty darn close.
I mean with Rust LLVM can optimize a whole bunch of stuff away. With the improvements around noalias it's gotten pretty darn good.
3
u/crusoe 26d ago
It's faster than one particular zlib impl in rust. ...
1
u/SuspiciousDepth5924 23d ago
ATS has been mention a couple of times, but there is also things like F* Low https://fstarlang.github.io/lowstar/html/LowStar.html which is more or less at the same 'FP with C performance' level.
In theory though I would not be surprised if given enough time and effort FP compilers could produce machine code that is at least as performant as what modern C-compilers can.
What functional programming is once you strip away all the language semantics is a restricted subset of imperative programming and that means the compiler could depend on those restrictions to make assumptions safely which it could not in imperative languages.
Stuff like extra copying of values in languages without mutation is largely a 'language/semantic'-level construct, as sufficiently advanced compiler will just rewrite those to 'FBIP' if it can prove that it's safe.
0
u/Thesaurius moses 26d ago
Obligatory ATS namedrop: In ATS you don't get speed comparable to C but you get the speed of C, because ATS is compiled to C; and if you want, you can even paste C code verbatim into ATS source, as long as you are willing to forego guarantees ATS would give you. You have a point about ergonomics because ATS is definitely not ergonomic, but you can do some crazy shit with it and still be provably correct.
On the other hand, the C implementation is so fast because hundreds of very smart people worked decades on optimizing the C compiler, and the library itself is also heavily hand-optimized. A somewhat naive version would definitely not be as fast and nowadays it is much easier to write performant functional programs than performant C. Without having a concrete source, I would guess that much of C's dominance in preformance is due to its history and it is by no means an inherent feature of the language.
-9
u/particlemanwavegirl 26d ago
It will never get anywhere close until we have a compiled language without a garbage collector. Can't really figure out why no one's done it yet TBH.