Some Concepts in Functional Languages

Purity, Idempotency, Cacheability, Effects, Tracking

I am relatively new to functional programming. To learn about it, I am building this functional language KernelF — actually, I/we am/are building it because we need an embeddable, extensible functional language as the core of our MPS-based DSLs, but building it also does help me learn functional programming.

The core of KernelF is pure. This means that there are no effects, no (global, observable) state is ever modified. This is nice because it makes KernelF programs easily analyzable. However, in the end, a program that has no effects does not do anything useful, it only heats up the CPU (as I heard Simon Peyton Jones once say). So at some point, you do need effects. The question is: how to you integrate effects into a functional language in a way that does not destroy the benefits of a pure functional language in the first place.

The general answer here is monads and algebraic effects. Yes, I know these words, and I could explain intuitively what they mean. But I won’t. Considering that monads are explained only after three fourths of a 500 page book on category theory , any explanation of mine must necessarily be simplistic. Or wrong. However, in the context of thinking about effects, I did have to clarify a couple of terms around functions. In this post I will explain what I understood. Take it with a grain of salt :-)

Purity

A pure function is one that only depends on its arguments, it has no access to any other mutable data (it may access constant global state). The body can only compute with the arguments, so invoking the function several times with the same arguments must necessarily produce the same result. Pure functions are what we know from math.

For this to be true, the function can also not have access to sources of data, such as a random number generator, a network socket or IO. In addition, successive “same” return values, must be indistinguishable. For example, calling add(3, 4) three times may technically return three different instances of an object that represents 7. However, the client program must not be able to distinguish them. Finally, the function must also not have any additional outputs beyond what is returned; in other words, it must not modify the state of the world.

Cacheable/Memoizable

If a function always returns the same result (or the technically different objects are not semantically different), then subsequent calls to a function with the same argument values do not have to be reexecuted, the result from the first call can be cached. Whether caching makes sense depends on a tradeoff between the effort for reexecution, the memory needs for caching and the performance of the cache lookup. Generally, the more work a function performs, the more useful it is to cache the results and avoid reexecution.

Again, value semantics are essential here, because the caller must not be able to tell the difference between whether the function is cached or reexecuted. If the cache returns a previously computed value, then, of course, that value must not have been modified in the meantime. This requires immutability (“value semantics”) of the data returned by functions. This is the reason why functional programming and immutable data (in the form of persistent data structures) usually appear together.

Effects

An effect is a change to the world. For example, a function might print a string to the console. While you could consider a console as another data structure that might have an undoLastOutput method, effects that actually affect the real world really cannot be undone. To again quote from a talk by Simon Peyton Jones, “you cannot undo a rocket launch” :-)

So let’s dig into this a bit deeper. A function with a (world modifying) effect cannot be cached. Because then the cached invocations would not perform the effect, despite otherwise returning the same result. So if we imagine a runtime system that decides by itself, based on runtime profiling, whether a particular function should be cached or not, it must not ever cache a function with an effect. This is one major reason why we want to make it explicit that a function (potentially) has an effect (note that an imperative programming language implicitly assumes everything to have an effect and thus can cache nothing — unless it performs non-trivial analyses to figure it out anyway). Similarly, a function with a world-reading effect can take the (changing) data from the world as part of its computation; thus, subsequent invocations can return different results. No more purity, no caching.

Idempotency

Consider the following non-pure function:

fun createNewCustomer(id: ID, data: CustomerData) {
if (!database.hasKey(id))
then database.store(id, data)
else false
}

Here, the database is the world (a global variable), the call to store is the effect. Notice how the implementation is defensive: if the customer, as identified by its ID, already exists, the function does nothing. So you can call it any number of times without messing up the global state. A function that behaves this way is called idempotent. Idempotency is very useful in distributed systems where remote calls/packets might get lost. If the called function is idempotent, you can always re-call if you’re in doubt whether the first invocation succeeded or not. I am not so sure where and how I would exploit idempotency in a functional language.

Different Kinds of Effects

So, are all effects equal? Consider a function that adds two values and also outputs a log value:

fun add(a: int, b: int) {
log "adding " + a + " and " + b
a + b
}

Is this function pure? You could argue no, because it has an effect of appending to the log. On the other hand you could say yes, because the log output is not part of the world that is visible to your program; presumably you cannot read from the log, so change of that part of the world is irrelevant. In some sense, the log is “observing” the program’s execution rather than being something that the program modifies intentionally. If we cached this function, then the log output would only be written during the first (non-cached) execution. If you switched off caching, the log would be written for every invocation. However, this might be exactly the point of the log in the first place: find out if caching works. So in that sense, logging is not an effect (you care about).

Here is another example:

fun add(a: int, b: int) pre programMode == active {
a + b
}

In this example, we read from the global state programMode in the precondition. So even if the function body is never executed (because the precondition fails), we do execute the precondition. We obviously do not want to allow modifying global state in the precondition, but we do want to allow read access, because, presumably, the a purpose of the precondition might be to only execute the function if the world is in a particular state. Even if we cached the execution (because the inputs are the same as in a previous invocation), we still want to execute the precondition (and maybe throw an exception and stop program termination if the precondition is not met).

Summing up, we have to distinguish between different kinds of effects. Expressions that modify a global data structure that is “observing” in its nature do not constitute an effect. And we have to distinguish between reading mutable state and modifying it.

A more elaborate effect system would also distinguish between the different parts of the world an effect concerns: IO, network, global memory, whatever, the list is potentially endless. A user would have to be able to define their own kinds of effects. I have a vague notion of how this could be implemented, but I don’t quite see the reason for it. If anybody can tell me what I would do with this information, I am all ears.

Totality

A total function is one that terminates with a valid result for all inputs. A function that does not terminate is said to diverge. The above example of the precondition that throws if it is not met is an example of divergence. There are functional languages that are total (where, I guess, the compiler has to somehow show termination even in case of recursion), but the details of this are beyond my current understanding.

Effect Tracking

As mentioned before, a key idea of making effects explicit is to be able to (easily) analyze a program to find out where effects happen, and where they don’t. Parts of programs that have no effects can be cached, reexecuted at will and even parallelised. Because all the inputs are explicit, it is also relatively easy to implement a reactive system where computations are retriggered when an input changes. We will return to this particular use case in a future post.

So how do you track effects? Let us consider the following code:

record Person {
name: string
age: int
}

fun perhapsStoreData(p: Person) {
if p.age > 10 then personDB.store(p) else false
}

perhapsStoreData(Person("Markus", 43)) // 1
perhapsStoreData(Person("Peter", 5)) // 2

Let's assume thatdb.store is an operation that has a modify effect. The question is: does the function perhapsStoreData have an effect or not? As its name suggests, it depends on the particular p passed as an argument. So of the two calls to perhapsStoreData, the first one has an effect, the second one does not.

This realisation leads to two different styles of effect tracking. In the first one, you perform a data flow analysis of the code along the call graph. It would find out that call number 1 has an effect, and call number 2 does not. A less precise alternative analysis would simply look at the code of a function, see if any of its children has an effect (true in the case of perhapsStoreData), and then determine that the function (potentially) has an effect.

In the latter case you associate the fact that the function (potentially) has an effect with the function, for example, as part of the type (the return type of perhapsStoreData could be effect<boolean>) or you maintain the information separately (you can imagine it as a kind of second return type). In the former case, the function itself does not say anything about effects or not; only a function call, where you know the argument values (potentially through more analysis), gets an effect associated with it. Whether you take the data flow and values into account is a precision property of the analysis. The trade-offs associated with this and other precision properties are discussed in section 4 of the formal methods booklet.

Effect Tracking in KernelF

In KernelF, we use the less precise alternative to keep things simple. We do not mangle the effects with the type, but maintain it separately. By default, an Expression has no effect. If an expression does have an effect, it implements the IMayHaveEffect interface. This interface has a method that returns an EffectDescriptor that has the flags modifiesState and readsState. We propagate effects up along the program hierarchy (a BlockExpression has an effect if any of its child expressions has an effect), as well as along specific edges (a FunctionCall derives its own effect descriptor from the effect descriptor of the called function). The code optionally highlights effects on functions and function calls with the /R, /M and /RM annotations (see below).

A second interface IMayAllowEffect controls at which program locations effects are allowed. Based on the interactions of these two interfaces, the IDE can report errors relating to effects:

The init value of a global constant can have a read effect, but not a modifies effect:

The actions in a state machine must have a modifies effect (“action” kinda suggests that)

In a block expression, an expression that is not assigned to a value and is not the last one in the block must have some kind of effect. Otherwise its value gets lost and the expression should be avoided.

Wrap Up

I hope this clarifies some of the terminology around functions. I am pretty sure I have missed something, so please reply with corrections and additions! In the next post I will discuss how we integrate mutable state as well as transactions into the (functional) KernelF language.