Rationalizating Pure Functions on Kotlin

In an effort to imagine how this could be possible in Kotlin, I’ve come up with this:

NOTE: I’m not advocating this idea, it’s only a thought experiment

Here’s how I imagine it being done:

Add a new pure modifier for functions:

pure fun foo() { /*... */ }

Pure functions may only call other pure functions.
Pure functions may only use pure types.

Here’s an example

pure fun makeGreeting(name: String) : String { // String would have to be a pure type to be allowed.
  val uppercaseName = name.toUpperCase() // toUpperCase() would have to be marked a pure function.
  return "Welcome $uppercaseName!" // Returning pure type, so this would be allowed.
}

Again, I’m not sure I like this idea, but I’m absolutely up for the discussion around the concepts. It just takes me a bit to get out of my “minus 100 points” mode and into a “what if anything goes” mode :wink:

1 Like

“And for local variables within a method scope, val is immutable.”

Edit: I get that the reference itself is immutable; should have clarified that

Is this actually correct? The point I’m hung up on is this:
If I pass an argument to a function, I get that it is of type “val”. This means that I can’t change the underlying state associated to it within the scope of said function. However, if another reference (which happens to be a var) to the same state existed outside of the scope of that function, I don’t see any reason why it couldn’t be changed, thus breaking immutability.

Naturally this wouldn’t be a big deal unless threading was involved, but I don’t really care. State is either immutable or it isn’t.

You’re right but wrong about why.

Maybe it’s just the wording.

Here you say:

It’s true the state could change, but you do not need another reference to exist or to be var.

This is not true.

Here’s an example:

class Cat(var name: String) // This type is mutable
val Bob = Cat("Bob") // here's our val reference. This does NOT mean that "can’t change the underlying state associated to it within the scope of said function"

fun petCat(cat: Cat) {// The cat variable comes in as a `val`
  cat.name = "John Smith" // Here we mutate the val.
}

I take your point that I was incorrect there; thanks for clarifying.

That being said, the above function would not be pure as it changes state of course.

Ok, I did get some input from Roman on twitter which seemed to confirm my hypothesis:

“Make val not var! (and your code will be pure). If you only use vals in your classes, then they are immutable and it is enforced. Pragmatically, the fewer vars you have in your code the better. Ideally, no vars at all.”

source

So in other words, if you’re doing a good job as a programmer, you should be able to ensure immutability by using “val” everywhere.

A var and a val can’t “share the same reference” in the pointer sense, they can only share WHAT they’re referencing. You can’t get a reference to a val (other than by invoking it), you can only get what it references. And once you change that reference, you’re changing YOUR reference, not it.

To give an example.

data class Thing(val immutable: Int)

val a = Thing(0)  // a is immutably referencing an immutable object
var b = a // b is referencing the same object
var b = Thing(1) // a and b are now referencing different objects

Of course if the thing they are referencing is not ITSELF immutable, then you can have an immutable reference to something mutable, which could very easily violate the Pure Function principals and many other things:

data class Thing(var mutable: Int)

val a = Thing(0)  // a is immutably referencing an immutable object

fun doSomething( thing: Thing)
{
   // Black Box that might very well change the value of a.mutable
}

It is important to not mistake val as a guarantee that the entire chain of things it reference is immutable, just that IT is immutable. Such a guarantee is certainly possible in Kotlin and it COULD even exist at the language level (which is kind of the idea of some imutable syntax proposed), but for pure data it’s pretty easy to keep track of that on your own. But when it comes to workflow, truly pure functions and pure function chains can be far more difficult to track.

I understand that point very well. Forgive me if I’m not using the best words, but what I’m talking about is a mutable reference, and an immutable reference, pointing to the same location in memory.

Edit after misunderstanding a point you made

If val a: Int exists and var b: Int exists, then in no situation will changing b change a (talking about actual immutable vals, not delgates/getters). In this specific case that is because a and be were never pointing to the same place in memory, they were only pointing to different places in memory that shared the same value. The same is true if it were val a: Thing and val b: Thing. They were both pointing to different places in memory that THEN was pointing to the same memory where the class data is stored. But in general you shouldn’t be trying to think about things in the memory level with abstract languages. The language contracts are what you should be concerned with.

If we go back to compiler checks: Checking for val-only does still not ensure that an object is immutable. You could still implement the getter as an impure function

val foo: Int = 0
    get() = value++ // I hope value accesses the backing field :)

I still kind of like the idea of adding pure to the possible contracts. Maybe this will be simpler once project valhala adds value types. That way we could restrict pure functions to only take value types as parameters, which would simplify compile time verification of them. That way they might be more restricted than pure functions defined in other languages.


Another idea might be to add trusted functions in the contract

fun pure() {
   contract {
       pure(::doSomething, ::doSomethingElse)
    }
    doSomething()          // this could be defined in java and therefor is not marked as pure, but we trust it
    doSomethingElse()
}

This does not however solve how to stop pure functions from depending on or changing global state.

1 Like

If val a: Int exists and var b: Int exists, then in no situation will changing b change a (talking about actual immutable vals, not delgates/getters). In this specific case that is because a and be were never pointing to the same place in memory, they were only pointing to different places in memory that shared the same value.

I’m talking about the specific situations where and a and b point to the same location in memory. I’m never talking about situations where a and b don’t point to the same location in memory. If there’s something I keep saying that implies otherwise, would you mind pointing it out? I’m not being disingenuous here, really trying to grasp where the disconnect is.

I’ve added a sample to op to demonstrate the situations I’m speaking of, hopefully that will clarify things.

As I said, it’s impossible for val a and var b to point to the same place in memory. Your example is of val a and var b pointing to different places in memory which then point to the same class which itself is not immutable, which I already talked about. If Blin’s sub-components are not immutable then Blin cannot realistically be used in a pure function unless the function just doesn’t look at the mutable sub-components. In Kotlin language, val a being immutable does not imply that a.x is immutable. Which is not to say that it guarantees that it isn’t, either. But regardless, in your example there’s no way for doThing to change x because parameters in Kotlin are immutable. (Not the components of parameters. Again, immutability in Kotlin is only contracted at the root level, not at all subcomponent levels).

I think I understand the confusion here; it’s admittedly probably my usage of pointer/reference jargon which I’m very not fond of due to situations like this.

When I say val a and var b pointing to the same location in memory, I was speaking of them sharing a number which can be used to look up the same object (i.e. they both have unique addresses, both can be used to find the same object or location in memory, which I thought meant that they “point” to it). I’m not saying that I can have a situation where I look up the address of “a”, and it is the same address of “b”. Definitely not trying to say that, because it doesn’t make any sense.

Your example is of val a and var b pointing to different places in memory which then point to the same class which itself is not immutable, which I already talked about.

This is still, and always has been, what I’m (trying) to talk about.

I think both of us should stop talking about the low-level notions of “pointers” in a language that has no concept of them because we’re clearly don’t mean the same thing by “points to”.

In any event, yes, if by “truly immutable” you mean “immutable throughout its entire hierarchy” it is correct to say that this is not enforced by the compiler. This doesn’t mean that pure functions can’t exist in Kotlin (especially considering that if you’re using Basic Types, then immutability is the same as “true immutability” ), just that there is no language framework to track and designate functions as pure.

One question is how safe we want this to be.

For example, even if all references to an object were an immutable type, what’s to stop someone downcasting to a mutable type? Or even if an object had no mutators at all, what’s to stop someone accessing its internals via reflection?

I suspect those aren’t worth protecting against. But I think this could be useful even without ultimate safety. (Compare how type parameter checking can be defeated in similar ways, due to type erasure; but it’s still an extremely useful feature.)

This does sound like a good match for the forthcoming contracts functionality. (I like the idea of contracts, but it sounds far too manual a process right now. Ideally, I think it should be something the compiler could infer for itself; annotations would only be for double-checking, like Java’s @Override annotation or Scala’s @tailrec.)

This is reminding me of the early days of java and arguments about pass by value vs pass by reference on Usenet news groups. I would always clarify it by asking the question, “Does java pass objects by reference or by value?” The answer is neither! Java has absolutely nothing in the language that represents objects. It only has references to objects which are passed by value.

I think the thing missing from this discussion is the idea of const references and const functions from C++. If you had the ability to achieve const correctness you could assure that a function is pure. Achieving const correctness however was always a huge task on C++.

2 Likes

This is a pretty great conversation, thanks all for having it.

For my part, I think adding a pure modifier on a function would be a fantastic idea. This would introduce a compile-time check that passes iff the function depends on other pure functions and types that are immutable ‘to the bottom’.

For val properties declared using get() syntax, the property itself would only be determined as immutable if get() itself were marked pure.

It should additionally be possible to ‘force’ purity using contracts/annotations; both to resolve the Java interop scenarios, as mentioned above, but also to allow for code that introduces non-compile-time verifiable optimizations that are effectively pure (for example memoization via lookup table).

I actually think this modifier could potentially replace the inline modifier, which I have concerns with anyway. Inlining is a compiler technique to make code faster; I don’t think it should be referenced in theoretically declarative code. I see the value in telling the compiler that something doesn’t need to be retained for reflection; but it seems to me like pure plus something like unre (inverse of reified) would together serve the same (and more) purpose.

I also think it would be good to infer purity contractually, where possible, in the same way that auto typing is available by inference.

Have you proposed this to Kotlinlang foundation?

We had a rather heated discussion about purity yesterday. The purity makes sense if everything in the language is pure. Otherwise it introduces a lot of limitations without actual benefits. As for optional purity, it could probably be done with contracts.

1 Like

I would love to see a pure function keyword in Kotlin, it’s one of the best features of the D language and I wish more languages had it.

https://dlang.org/spec/function.html

For calling non-kotlin code, we could either assume everything is impure, or have purity not checked (similar to how null/nonnull works today). And maybe have an annotation that Kotlin understands, like @Pure in pure4j: https://github.com/pure4j/pure4j

1 Like

The purity makes sense if everything in the language is pure. Otherwise it introduces a lot of limitations without actual benefits.

There are actual benefits, though.

For instance, the results of pure functions being invoked on compile-time-constant parameters can be evaluated at compile time. Functions like String.trimIndent (which gets invoked on constant multiline strings, for instance) could be a big win for this.

Use of pure functions may also enable compiler optimizations that wouldn’t otherwise be possible such as allowing this:

val x = pureFunc(42) + pureFunc(42) 

to be simplified to this:

val x = pureFunc(42) * 2

These types of optimizations can get quite complex if a lot of pure functions are being invoked, and can result in a lot of code savings.

I think that the compiler probably can’t do an adequate job of identifying pure functions, and it would be necessary to have a ‘pure’ keyword or something similar so that the user could tell the compiler what things should be treated as pure. In some cases, however, the compiler could identify if a function marked ‘pure’ was doing something fundamentally impure, and could issue an error message. This would be very useful.

Note, by the way, that recent versions of C++ have been introducing a lot of purity-related features involving the ‘constexpr’ keyword (C++11) and ‘consteval’ keywords (C++20).