Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Apr 18 '12 at 20:02

This question came from our site for professional and enthusiast programmers.

12  
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 Apr 18 '12 at 19:42
5  
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. –  Robert Harvey Apr 18 '12 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 Apr 18 '12 at 19:47
1  
If this was true, we could not program functionally at all. CPUs are not functional. –  Michael K Apr 18 '12 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. –  Jerry Coffin Apr 18 '12 at 20:50

6 Answers 6

up vote 10 down vote accepted

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.

share|improve this answer
    
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. –  Evan Plaice Apr 18 '12 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. –  Mason Wheeler Apr 18 '12 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. –  Evan Plaice Apr 18 '12 at 23:02
    
"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 Apr 18 '12 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 Apr 19 '12 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.

share|improve this answer

"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.

share|improve this answer

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++.

share|improve this answer

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!

share|improve this answer
    
Good luck with that =) –  Dan Burton Apr 18 '12 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. –  Mason Wheeler Apr 19 '12 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...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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