I am assuming the implementations/compilers/generated C code (referred to hereinafter as generic, 'interpreter') for most functional programming languages are written in non-pure functional languages.

If this is the case, the underlying interpreter for any given functional programming language exhibits destructive updates and is referentially opaque. Functional constructs are designed to make certain guarantees, such as concurrency and provability.

If the interpreter is indeed an imperative program, how is it able to guarantee the 'no side-effects' properties of pure functional programs? Surely optimisations to functional code by the interpreter include changing the nature of recursive functions to imperative ones? My question is:

How do imperative interpreters still make guarantees about the functional program they are executing without being inherently functional themselves?

  • 13
    Do not confuse a language [specification] and a language implementation. The implementation can do whatever it wants as long as the language rules are upheld; if it violates the rules then it is a flawed implementation.
    – pst
    Commented Apr 18, 2012 at 19:42
  • 6
    How do imperative interpreters still make guarantees about the functional program they are executing without being inherently functional themselves? -- By properly implementing the language specification. @pst is right: your compiler implementation does not have to be functionally pure to guarantee a fully functional language. Commented Apr 18, 2012 at 19:44
  • 1
    If you're using details of how the language is implemented while proving the properties of a program in a given programming language, you're doing something wrong. And if you're not using implementation details in your proof, how could those details possibly affect the provability of whatever you're trying to prove?
    – sepp2k
    Commented Apr 18, 2012 at 19:47
  • 2
    If this was true, we could not program functionally at all. CPUs are not functional.
    – Michael K
    Commented Apr 18, 2012 at 20:36
  • You might want to read VLISP: A verified Implementation of Scheme for some ideas of how such proofs are done. That said, I feel obliged to point out that most simply don't attempt such proofs at all. Commented Apr 18, 2012 at 20:50

7 Answers 7


Everything in your machine runs on a CPU which loads and stores memory words, and performs comparisons and goto-like branches.

Functional programming means that mutation is hidden under the rug, not that it goes away.

It is not feasible, with current technology, for a functional language to be implemented purely all the way down. This is because you cannot keep allocating new hardware. Functional programs generate garbage as they execute, and the implementation has to identify the garbage and then reuse its storage for new objects. That is a form of mutation.

If this mutation is not done, then it means you do not serially re-use memory.

If you do not reuse memory, you have to keep getting new memory from somewhere.

Also, you are not allowed to restart the computer. You must use a new one.

Its CPU has to keep allocating new registers, because you can't load a new value into an existing register. Et cetera.

As you can see, functional programming is a silly pipe dream that is only made possible by the pragmatism of mutation.

There is inherent mutation in functional programming itself (in the abstraction). It's just conveniently ignored.

Fact is that when you construct a new object, the world has changed: there was no such object before, and there is now. Same thing when a new variable binding comes into life.

You can pretend that a whole new universe was allocated which is just like the old one, except for the difference that a new element now exists in it, but that's not reality. (If the old "world" was not mutated/destroyed by the creation of a new object, show me where that old one is.)

Also, in functional programs, object are destroyed all the time! Variable bindings (which are not captured in some closure) go out of scope, and objects fall out of the reachability graph (if there is no mutation, how can something be in a graph in one moment, and be not in that graph the next moment?)

You know that the old copy of the world is not being preserved, because those unreachable objects are stomped over to make new ones.

In other words, the destructiveness of functional programming reveals itself by the inability to revisit all past states of computation and inspect every object that was ever created.

  • I wonder if our brains are really an ideal functional execution environment where the 'unlimited hardware' makes up the 90% of mass that we don't use. We do have the ability to conjure up latent memories under very specific conditions almost as if we never really lose memories, we just filter out the majority of it to better focus our perceptual senses. Commented Apr 18, 2012 at 21:04
  • 1
    @Evan: There is no "90% we don't use." That's a misconception. We only ever are using 10% of our brains at any given moment, but which 10% it is depends on what we're doing at the time, and the whole thing gets used on a regular basis. Commented Apr 18, 2012 at 22:49
  • @MasonWheeler Regardless, doesn't it make you wonder. If our brains are optimized to eliminate noise, how much of the information outside of our perceptual limits actually gets lost over time and how much just doesn't get utilized as much over time. Sorry about going way off topic but your question sparked a little imagination. Commented Apr 18, 2012 at 23:02
  • 1
    "the destructiveness of functional programming reveals itself by the inability to revisit all past states of computation and inspect every object that was ever created." No, you could easily do this, given enough memory and processing power. You could just as easily do it in an imperative language: just save a snapshot of the stack before every instruction.
    – Dan Burton
    Commented Apr 18, 2012 at 23:54
  • Yes, which shows you the flipside: given enough processing power and memory it would be practical to turn imperative programming into functional. Every time you assign to a storage location, just clone the world, so you're really constructing something new and not overwriting.
    – Kaz
    Commented Apr 19, 2012 at 0:07

By way of illustration, let's walk through a trivial example of a computer language called "ALL-CAPS." This language has the peculiar quality (and language rule) of only being writable in all capital letters.

Can I write my compiler or interpreter in a language like C#? Of course I can. Does C# use lower-case letters? Of course it does. Can I still require my source input to be all capital letters? Absolutely.

Someone with better deductive logic skills than I can probably logically prove that requiring all caps in your program source code is morally equivalent to requiring purely functional constructs in your source code.


"Functional programming" is an abstraction, just like "Object-oriented programming". Your "interpreter" doesn't have to use objects in order to implement objects. Likewise, it doesn't have to use pure functions in order to implement pure functions.


The guarantees provided by a functional programming language apply to the behavior of programs written in that language, not the implementation itself. "No side effects" means that there are no side effects visible to the program, or that matter to the programmer or user. "Immutability" means that the program's values and/or variables are immutable, not that no data ever changes. "Unlimited lifetime" means that objects aren't deallocated until after they're no longer reachable.

To put it another way, the guarantee is not that a program won't produce side effects when it's run, it's that the language cannot express programs that produce side effects. This enables people and compilers to reason about programs in ways that aren't possible with languages that don't provide the same guarantees. For example, without side effects, a function call can be executed only once if it's called with the same arguments in multiple places, or not at all if the compiler determines its return value isn't used. Its execution can also be deferred until its value is needed with no impact on the behavior of the program; Haskell does this for all computations by default, which lets you do interesting things like pass infinitely long lists around.

All programming language implementations are really only simulating an idealized system on real-world hardware. This applies as much to imperative languages like C and even assembly language or machine code as much as it does to functional languages. For example, a CPU is free to reorder operations, provided the reordering never becomes "visible" within the thread that's being reordered. This becomes apparent when writing multi-threaded code: one must use memory barriers in any code that cares about the order in which operations become visible to other threads.


Since this was tagged as Scala, I'd like to add that Scala is written largely in Scala itself, with very little in Java. Then again, it does use some libraries written in Java, and it runs (mainly) on a JVM that is written mainly in C/C++.


I will now, via the magic of the Internet, demonstrate a pure functional program free of side effects, written in C, a decidedly impure programming language:

int main()
    return 0;

C programs do not create side effects unless you tell them to. Therefore, creating C code without side effects is relatively easy: don't put them in!

  • Good luck with that =)
    – Dan Burton
    Commented Apr 18, 2012 at 23:55
  • 2
    @Dan: And good luck with that in a functional program either. It's impossible to produce a (useful, non-trivial) program that does not depend on side effects, at the very least for input and output. Commented Apr 19, 2012 at 0:03

Well, it's not a contradiction. You can build whatever you like in both paradigms. Guaranty is achieved by testing and proving, and surely, there are implementation bugs in every start.

The interesting thing occurred to me while reading your question was, that almost every language is C powered underneath, lisp, scheme, python...

Not the answer you're looking for? Browse other questions tagged or ask your own question.