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.