Undecidable definition of pure function

Question

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this:

DEFINITION: A statement is impure if

• it is an assignment, unless it assigns to a local variable
• OR, it evaluates a call to a function, unless that function is pure
• OR, it is a block containing an impure statement

DEFINITION: A function is pure if it doesn't contain any impure statement.

For simplicity, let's ignore assignments altogether and assume that a block is simply an ordered set of statements. (it shouldn't make a difference)

Now, this definition works great until somebody defines a function that refers to itself, e.g.

function fibonacci(n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

or

function f() { return g(); }
function g() { return f(); }

Suddenly, the definition becomes undecidable.

Is this a common logical paradox? How would I modify this definition, so that "by default" a function is considered pure?

Answer 1

This is a computer science question, but as you insist that it is not, let me explain why in an answer: a pure function in a programming language is one whose result is determined solely by the values of its parameters and not by the state of the program when it is called. It is the programming language semantics that define what happens when you call a non-terminating function.

It is unclear whether you intend your definition to be a syntactic condition or a semantic one. If the former then it still "works great" in the presence of loops and recursion, but you have to qualify what it means when the pure function turns out not to terminate. If the latter, then it is already undecidable for while-loops, so recursion isn't introducing a new problem. There is no paradox involved here.

As an aside: Rice's Theorem is something that may interest you.