inferring-purity.md

inferring-purity.md

It would be useful to be able to infer whether or not an expression is pure - even in languages with rampant side-effectfulness and mutability, such as JavaScript. Here's my ad-hoc thoughts on how it might be achieved.

Terms

A pure expression is denoted as P -> x - that is, an expression that evaluates to x deterministically. A non pure expression that mutates a value is M[y] -> x, where M is the 'type', y is the mutated value, and x is the return value.

Rules

An expression made up of pure expressions is pure

pureFn(1, 2); //= P -> x
var fn = function(x){ 
  return myFn(1 + x,3)
} //= P -> x

fn(1) //= P -> x

An expression made of impure expressions/statements that only affects transient state is pure

var fn = function(x){
  var o = {};
  o.x = x;    // M[o] -> o
  return o;
} // P -> x

fn(2) // P -> x

An expression made of impure expressions that affects NON-transient state is impure

var o = {};
var fn = function(x){ 
  o.x = x // M[o] -> o
  return o;
} // P -> x

fn(2) // M[o] -> o

An expression that makes a side-effectful call to the environment is impure

alert('yes') // M[x] -> x

As @lambdatoast points out, even + cannot be guaranteed pure, since any value can implement its own .valueOf.

Because of polymorphism more generally, type tracking would be necessary before we could know which actual method was being called statically:

var doubleMap = function(a){ return a.map(function(a, b){ return a + b }) }
var o = { map: function(){ alert('hah') }

doubleMap(o) // M[x] -> x
doubleMap([1, 2, 3]) // P-> x

And, not only that, but we'd have to know that no one monkey-punched after the site of first declaration.