3

I saw this question that shows it is impossible to programatically determine if a javascript function is pure, but is it sometimes possible to affirm that a function is pure - so something like...

function sq_a(x){ return x * x; }; // no side effects, all variables local
function sq_b(x){ return pow(x, 2); }; // if `pow` is pure, this function is pure
function sq_c(x){ return mathlib.pow(x, 2); }; // not pure, because mathlib.pow could be changed

function definitelyPure(fn){
    if(/* criteria to check if we can know for sure fn is pure */){
        return true;
    } else {
        return false;
    }
}

function isPure(fn){
    if(/* fn is pure */){
        return 0;
    } else if(/* fn might be pure */) {
        return -1;
    } else { // fn is not pure
        return 1;
    }
}

definitelyPure(sq_a); // true
definitelyPure(sq_b); // false
definitelyPure(sq_c); // false

isPure(sq_a); // 0
isPure(sq_b); // -1
isPure(sq_c); // 1

 Clarification:

I know it is not possible to determine if any javascript function is pure as answered in linked to question, but I am asking if it is possible to programatically affirm purity of some functions - as in I expect that it is possible for example sq_a using some code analysis, but I understand it is not possible for sq_b.

I am interested to know if there are any tools out there to do this already, and what criteria determine if it is possible to programatically declare a function as either pure, unknown, or impure.

Community
  • 1
Billy Moon
  • 329
  • 2
  • 5
  • 14

2 Answers2

4

It is possible, in general, to analyse the parse tree of a function and check a set of constraints that ensure we know if the function is definitely pure:

  • If the function only calls other functions that are pure
  • And doesn't reference or modify any global variables

Then it is pure.

There is, however, a problem with doing this in Javascript (and many other dynamic languages), which is that they provide a mutable environment. You state that your function sq_b is pure, but you can't actually prove that unless you can determine the behaviour of all other code that may run before it, because that code may do something like this:

window.nextPowResult = 1;
window.pow = function (a,b) { return nextPowResult ++; }

This changes the behaviour of your function (and any other function that uses pow), and makes it non-pure. Unfortunately, determining whether or not something like this could happen is an undecidable question, so in Javascript specifically we cannot ever be certain that any function is pure, unless we have control over all code that executes in the same context.

Jules
  • 17,614
  • 2
  • 33
  • 63
  • Thanks for your answer - just to clarify, I do not state sq_b is pure, I state that "if `pow` is pure, this function is pure" and "fn might be pure". a, b and c are intended to be examples of a pure, unknown purity and impure function. – Billy Moon Jun 09 '16 at 23:21
  • how about if in the same enclosure, pow is defined as `var pow = ...` so it is not attached to the window and is itself analysable as a pure function (as sq_a should be possible for) for example... perhaps there are times when it could also be programatically determined to be definitely pure..? – Billy Moon Jun 09 '16 at 23:24
  • Yes. I would think that if `pow` is defined in a closure scoped such that it cannot be accessed by any non-pure function, that would allow the analysis to be possible. I would suggest, however, that doing this with a static language is much easier and much more likely to give useful results... :) – Jules Jun 09 '16 at 23:28
  • 1
    well, I am sure browser vendors will replace javascript one day so that our kids will not have to suffer the slings and arrows of dynamic typing in their programming forays, but that is a problem beyond my influence :( – Billy Moon Jun 09 '16 at 23:30
  • 2
    It's not necessary for browser vendors to do that, as Javascript is a perfectly adequate target for compiling code in other languages to... see https://github.com/jashkenas/coffeescript/wiki/list-of-languages-that-compile-to-js – Jules Jun 10 '16 at 06:45
  • 1
    @BillyMoon For the record, this nonsense has nothing to do with dynamic typing. You can break C just as easily with well-placed #defines and pointer arithmetic and whatnot. The real problem is that Javascript (as well as C and C++) does not yet have a standardized, widely-implemented modules system that genuinely isolates one module of code from all other modules. – Ixrec Jun 10 '16 at 08:45
  • Might be worth asking when we have to decide if the function is pure. As it is called? Before the program is run? What we know changes over time. – candied_orange Nov 16 '22 at 21:37
2
var sneaky3 = { 
   valueOf: () => { console.log('look, a side effect'); return 3; } 
}    

>> sq_a(sneaky3) 
look, a side effect
9

As shown above, side effects can happen even in simple arithmetic operations.

Basically, the only operations that can be proven pure are operations on literals using built-in operators, like 2 + 2. This is so limited as to be useless.

JacquesB
  • 57,310
  • 21
  • 127
  • 176