Enforcing pure functional style

Is there a way to have the rust compiler enforce pure functionality? Maybe with a cargo directive that disallows any mut keywords? I've been looking into optimizations that are only possible with a functional guarantee and it seems like it might not be hard to implement this in rust.

If there is no such directive currently, can someone point me in the right direction on where to implement it?

There isn't.

That wouldn't be enough.

Such as? I'm pretty sure the prohibition of shared mutability in itself enables most optimizations that rely on values not changing unexpectedly (i.e., local analysis suffices).

5 Likes

If he includes "purity" in his "functional guarantees", then there are obvious ones like memoization.

In which case their definition/specification is wrong and they'll need to re-ask a meaningful question, because purity is not immutability.

I am referring to purity. That each function in the compilation space (including main) is pure, has no side effects and always returns the same value given the same input. I am not an expert in the terminology so I apologize for any confusion.

I guess disallowing mut would not be enough for purity but there is a set of features that if you disallow them, would render rust pure and therefore amenable to some interesting optimizations and guarantees. I understand it will be trickier to implement in reality than in theory but that seems a poor excuse not to at least look into it (speaking for myself, not making demands of the maintainers here).

Here is the general outline of the feature:

  1. A cargo (or maybe just clippy) directive that scans the code for "impurity" and refuses to compile or at least throws a warning that the code is "impure"
  2. A set of compiler optimizations that are only enabled on strictly "pure" code
  3. Maybe a list of guarantees that the code could make once it is confirmed "pure". I am not an expert in functional programming but I understand there are certain correctness promises you can make with "pure" code that you can't make with "impure" code.

What I am asking for, now that I know there is no such feature currently, is for someone more experienced than me in the rust codebase, to point me in the right direction for where I should be looking to implement this feature. I am mostly thinking about how to have cargo read a config flag in cargo.toml that promises that the code is pure, and then parse the code to ensure that is the case, and throw an error if it is not.

You are very much putting the horse before the cart.

That's something which is entirely different from how Rust programs normally work. Rust is built around uniquiness and ownership, but there are no way to even express your idea in the language. &uniq is just an internal implementation detail (and if I remember correctly it's not even used for that in Rust 2021).

Before you would do something like that it would be great to at least create some crates which would be usable in such a mode. Currently these don't exist.

And only after you would successfully create such Rust-without-mutability thingie (probably under different name to not confuse anyone) you may start thinking about compiler for it and ecosystem for it.

I, for one, have no idea why anyone may want to need such a strange thing, but hey, I was wrong before, you may even invent something interesting.

But before you'll rush to change cargo and rustc you have to at least imagine what you are trying to create beyond the vague idea that you may want to force someone to live with merged limitations of functional languages and Rust.

2 Likes

const fns are currently the closest thing to pure functions, although this might change. They are also very limited (e.g. no traits, no allocations etc etc)

Regarding mutability, in Rust &mut references are restricted enough that you don't need to remove them to have purity. You can just see them as equivalent to taking a parameter and returning the corresponding updated value, all of which cannot be hidden because the &mut T is right there in the function signature.

What you need to remove however is any form of internal mutability:

  • UnsafeCell
  • raw pointers
  • static mut

Other operations that need to be removed are:

  • calls to extern functions
  • observing the address of variables
  • anything that is UB in Rust

Now, for the tricky details:

  • under these rules allocations would not be allowed (they modify the global state of the allocator and may involve syscalls or other extern function calls), so you need to special case them;
  • panics can call the global panic hook, which can have side-effects (for example the default one prints to stdout an error message)
  • more in general, calls to generic functions/trait objects/function pointers need to ensure the corresponding functions are also pure.
  • how do you ensure there's no UB? Do you just disallow unsafe and hence every type that internally uses it (e.g. Rc, which is generally very useful in implementing functional paradigms)?
10 Likes

As a first pass approximation of purity, I would disallow the mut keyword, disallow closures that capture variables outside their scope, disallow unsafe code (with a finite list of allowed exceptions mostly from std), and I guess make a different default allocator if the functional flag is set.

The point would be to get the benefits of functional purity without having to write a new language from scratch. Rust already has a lot of functional flavor, I figured it shouldn't be impossible to give it the extra boost to get full purity, if desired.

Your points are much appreciated, the problem space is clarifying in my mind.

I'm not sure why you wouldn't use a pure functional language then. Chances are it will be more optimized/faster than a pure subset of Rust.

1 Like

Can you elaborate on what these optimisations are?

There's a good chance that it's already quite possible in Rust without needing to make changes to the language or compile code in an exotic mode.

For example, salsa is a framework where you phrase your problem as a series of pure computations ("queries") which call other queries which eventually do things based on inputs. The system tracks all inputs, plus the arguments for a query and their results, and because queries are all pure operations it's possible to say when the results of an entire query tree can be reused because an input change won't make any difference. All inputs and outputs are immutable, so detecting whether something has changed is just a case of holding onto the value and comparing them with Eq.

This system is what makes rust-analyzer so fast, and all because it works with immutable values and pure computations, even if the computations themselves use mutation internally for building up the results.

3 Likes

There are way too many programming languages. Having a way to do functional guarantees in rust would let you write libraries that have functional guarantees that can be used without FFI in regular imperative rust. I can imagine there being a lot of use cases for that. Writing pure functional rust would not benefit from much of the ecosystem (there might be a couple crates that would pass the test but probably not many) but having libraries with provable correctness and (hypothetical) performance advantages seems useful.

For example, writing an encryption function that is guaranteed to be pure seems to me to have a tighter security promise than otherwise. Being able to do that without using ffi is cool.

One example is memoization, which is a runtime optimization that can check if a function has been called with the currently passed value before and just returning the same value as the earlier call without redoing the computation. This is only possible if the function is guaranteed to be pure.

Not really. I just gave you a counter-example, Salsa.

Real-world experience with projects like rust-analyzer and rustc show that it's quite possible to do memoization in Rust without needing explicit language support.

3 Likes

That is very interesting, I did not realize that. I thought salsa was doing something different. Then the only theoretical advantage would be correctness guarantees that I know very little about. I've just heard that with purity guaranteed it is possible to prove a programs correctness. Do you know anything about that? Is this possible with regular rust?

You don't need purity in order to prove a program is correct, it just makes things easier.

For example, this StackOverflow question shows that it is possible to use Coq to prove that a C program is correct, and C is the very opposite of a pure language.

I also came across this project which is automatically converting Rust code to Coq proofs so they can be verified:

5 Likes

Very cool. Thank you. I guess I'll go back to writing toy databases :slight_smile:

Pure functional programming does give you some nice properties, but they are far from guaranteed correctness, so you'll still need to check those crates. On the other hand having to write pure functions in a language that wasn't designed for that will likely mean a bad experience and slower code (for example I would expect lot of boxing, clones and lifetime problems). Don't use languages in ways they weren't designed for.

This is a pretty bad example. If it wasn't pure it would be plain wrong, not just insecure, but being pure doesn't mean it will be correct or secure. For example some cryptographic functions need to take constant time at the cycle level (e.g. no branches) or they might suffer from timing attacks. There's nothing in mainstream pure functional programming that address this because they focus only on the result of a computation, not on its steps.

7 Likes

I did not consider that crypto example. I guess functional programming is less about computational results (provability, performance, etc) and more about developer experience. In that case there would be no reason for a functional flag in rust. Thank you, gentlemen, for taking the time to educate me.

I'm not sure if there are too many programming languages or too few, but creating yet-another-sublanguage is not the way to fix that problem anyway.

Rust have way too many sublanguages already (const, async, etc). Adding yet another one needs serious justification.

I don't know about that. A sublanguage seems like a good idea to me. I never use async/await in rust but if I ever want to I won't have to throw away all of my pre-existing code. A general purpose programming language should be general purpose. I did not realize that functional programming was less a result and more a method but if there are results that are impossible or difficult to achieve in rust, then that should be fixed.

For example if someone wrote a javascript transpiler, or whatever, for rust, that would be cool even if it involved new keywords or whatever. I would be very unlikely to use it but if I ever needed to write some javascript then it would be cool not to have to actually write javascript. The more features the better, I say!