Test if a function is pure

Test function for purity using lexical scope and runtime context.

Pure function: the output of a function is completely determined by its inputs. Running pure function has no side effects.

Example of pure function

1
function add(a, b) { return a + b; }

Example of non-pure function

1
2
var two = 2;
function add2(a) { return a + two; }

Can we determine if a function is pure by inspecting the source code? No, this is equivalent to the halting problem. Instead we can test if a function behaves like a pure one when running the function against the given set of unit tests.

Test engine

To unit test functions, we will the following simple test engine. First we will collect each test function using test(name, cb) method, then we will run all collected unit tests. We will use console.assert statements to verify functionality inside each unit test.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// individual unit tests
var tests = [];
function test(name, cb) {
tests.push({
name: name,
cb: cb
});
}
// running unit tests
function runTests() {
var failed = 0;
tests.forEach(function (test) {
try {
test.cb();
} catch (err) {
console.log('test', test.name, 'failed!');
console.log(err.message);
failed += 1;
}
});
return failed;
}
function isWorking() {
var failed = !!runTests();
console.log('is working?', !failed);
return !failed;
}

We can test functions add and add2 like this:

1
2
3
4
5
6
7
8
9
test('add', function () {
console.assert(add(2, 3) === 5);
});
test('add2', function () {
console.assert(add2(3) === 5);
});
isWorking();
// prints
is working? true

If we change the value of variable two and run unit tests again, we see them failing

1
2
3
4
5
two = 10;
isWorking();
test add2 failed!
false == true
is working? false

Can we determine which function is pure and which is not without changing variable two manually?

To do this we will modify a function using several transforms. To be able to test the modified function we need to first change the way we reference the function inside the unit tests. Then we can apply lexical scope and execution context tests.

Changing function under test

Let us refactor the code a little before proceeding. JavaScript uses lexical scope to find variables. For example inside our unit tests for add function, add variable is located by looking up and outside the unit test's scope (testAdd function)

1
2
3
4
5
6
7
function add(a, b) { return a + b; }
test('add', function testAdd() {
// what is add?
// lexical scope search from this place up
// to above source lines to find it
console.assert(add(2, 3) === 5);
});

Instead of using functions inside unit tests via lexical scope, let us pass all functions to be tested via context object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function runTests(context) {
var failed = 0;
tests.forEach(function (test) {
try {
test.cb(context);
} catch (err) {
console.log('test', test.name, 'failed!');
console.log(err.message);
failed += 1;
}
});
return failed;
}
function isWorking(context) {
var failed = !!runTests(context);
console.log('is working?', !failed);
return !failed;
}
test('add', function (context) {
console.assert(context.add(2, 3) === 5);
});
test('add2', function (context) {
console.assert(context.add2(3) === 5);
});

Our tests then initialize the context object before testing

1
2
3
4
5
6
7
var context = {
add: add,
add2: add2
};
isWorking(context);
// prints
is working? true

We can now replace / change the function and test if it still works using the following function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isPure(context, functionName) {
console.log('checking if function', functionName, 'is pure');
console.assert(typeof context[functionName] === 'function', 'cannot find function', functionName);
var before = isWorking(context);
console.assert(before, 'tests are not working before testing', functionName);
var backup = context[functionName];
// TODO modify context[functionName] somehow
var after = isWorking(context);
console.assert(after, 'tests are not working after testing', functionName);
context[functionName] = backup; // restore original function
}
isPure(context, 'add');
isPure(context, 'add2');
// prints
checking if function add is pure
checking if function add2 is pure

Move the function out of the lexical scope

The first test of function's purity is to take it out of its lexical scope. We can do this by reconstructing it in a new global lexical scope using new Function.

1
2
3
function destroyLexicalScope(fn) {
return new Function('return (' + fn.toString() + ').apply(null, arguments);');
}

This returns a new function that evaluates the given function's source code in new lexical scope.

1
2
3
4
5
6
function add(a, b) { return a + b; }
console.log(destroyLexicalScope(add).toString());
// prints
function anonymous() {
return (function add(a, b) { return a + b; }).apply(null, arguments);
}

The returned function has no access to any variables that used to be accessible to the original function via lexical scope

1
2
3
4
5
6
7
8
9
10
11
12
var two = 2;
function add2(a) { return a + two; }
var add2destroyed = destroyLexicalScope(add2);
console.log(add2(3));
console.log(add2destroyed(3));
// prints
5
undefined:2
return (function add2(a) { return a + two; }).apply(null, arguments);
^
ReferenceError: two is not defined
at add2 (eval at destroyLexicalScope (/src/index.js:53:10), <anonymous>:2:39)

Let us modify the function by changing its lexical scope and running unit tests

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isPure(context, functionName) {
// same as above
context[functionName] = destroyLexicalScope(backup);
// run unit tests again
var after = isWorking(context);
// console.assert(after, 'tests are not working after testing', functionName);
if (!after) {
console.error('function', functionName, 'is not pure');
}
context[functionName] = backup; // restore original function
return after;
}
// $ node index.js prints
checking if function add is pure
checking if function add2 is pure
test add2 failed!
two is not defined
function add2 is not pure

We can make add2 pure by moving all used variables inside the function

1
2
3
4
function add2(a) { 
var two = 2;
return a + two;
}

Change function's context

Imaging we are testing methods instead of functions

1
2
3
4
var sum = {
add: function add(a, b) { return a + b; },
add2: function add2(a) { return this.add(a, 2); }
};

We would like to detect this.add usage. We can detect this by changing the function's execution context using Function.prototype.bind

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function destroyContext(fn) {
return fn.bind({});
}
function isPure(context, functionName) {
// same as above
var backup = context[functionName];
context[functionName] = destroyContext(backup);
var after = isWorking(context);
if (!after) {
console.error('function', functionName, 'is not pure');
}
context[functionName] = backup; // restore original function
return after;
}
isPure(context, 'add');
isPure(context, 'add2');
// prints
checking if function add is pure
checking if function add2 is pure
test add2 failed!
Object #<Object> has no method 'add'
function add2 is not pure

We can make add2 pure by avoiding this.add

1
2
3
4
var sum = {
add: function add(a, b) { return a + b; },
add2: function add2(a) { return a + 2; }
};

Test against modifying input parameters

One of the possible side effects for non-pure function is modifying its input arguments passed by reference (objects, arrays, functions). For example, the following function addNumbers has side effects because it modifies the passed object.

1
2
3
4
5
function addNumbers(numbers) {
var sum = numbers.a + numbers.b;
numbers.a = 100;
return sum;
}

It is hard to detect such modifications, even by looking at the code coverage after unit tests. A typical unit test would look like this

1
2
3
4
test('add numbers', function () {
var numbers = {a: 10, b: 2};
console.assert(addNumbers(numbers) === 12);
});

The unit test add numbers covers every line of the addNumbers function, yet does not detect the change to numbers input. In order to detect changed numbers object, we need to call addNumbers several times

1
2
3
4
5
test('add numbers', function () {
var numbers = {a: 10, b: 2};
console.assert(addNumbers(numbers) === 12);
console.assert(addNumbers(numbers) === 12); // will detect the problem
});

For our pure test code, we can devise the following strategy: we will deep clone and freeze each argument passed to the function under test. This will test if the function tries to modify the external state via arguments.

I am using recursive deepFreeze and _.cloneDeep functions as utilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// taken from 
function deepFreeze(o) {
if (typeof o !== 'object') { return o; }
var prop, propKey;
Object.freeze(o); // First freeze the object.
for (propKey in o) {
prop = o[propKey];
if (!o.hasOwnProperty(propKey) || !(typeof prop === 'object') || Object.isFrozen(prop)) {
// If the object is on the prototype, not an object, or is already frozen,
// skip it. Note that this might leave an unfrozen reference somewhere in the
// object if there is an already frozen object containing an unfrozen object.
continue;
}
deepFreeze(prop); // Recursively call deepFreeze.
}
return o;
}
var _ = require('lodash');
function destroyReferences(fn) {
return function cutReferences() {
var args = _.toArray(arguments)
.map(_.cloneDeep)
.map(deepFreeze);
return fn.apply(null, args);
}
}
// testing engine
function isPure(context, functionName) {
var backup = context[functionName];
context[functionName] = destroyReferences(backup);
var after = isWorking(context);
...
}

output

checking if function add is pure
checking if function add2 is pure
checking if function addNumbers is pure
done

Hmm, nothing bad happens, but we know addNumbers tries to modify the frozen object. In order for v8 to actually throw an error, we need to declare the strict mode inside addNumbers or as first line in the outer lexical scope.

1
2
3
4
5
6
'use strict';
function addNumbers(numbers) {
var sum = numbers.a + numbers.b;
numbers.a = 100;
return sum;
}

output

checking if function add is pure
checking if function add2 is pure
checking if function addNumbers is pure
test add numbers failed!
Cannot assign to read only property 'a' of #<Object>
function addNumbers is not pure
done

We cannot assume that a function under test is running in the strict mode, thus it is up to us to detect the modifications to the cloned arguments. We can do this by comparing the objects passed into the function and their state after the function finishes. We only need to clone the arguments without freezing them, since we want the function under test to actualy modify its values.

1
2
3
4
5
6
7
8
9
10
11
12
13
// function addNumbers does NOT use strict mode
function checkChangedArguments(fn) {
return function comparedArguments() {
var args = _.toArray(arguments);
var passed = args.map(_.cloneDeep);
var result = fn.apply(null, passed);
var changed = !_.isEqual(args, passed);
if (changed) {
throw new Error('Function ' + fn.name + ' modifies its arguments');
}
return result;
}
}

output

checking if function add is pure
checking if function add2 is pure
checking if function addNumbers is pure
test add numbers failed!
Function addNumbers modifies its arguments
function addNumbers is not pure
done

The combined purity test

Here is the code for applying a list of transformations to a function and running the test again. We have a list of functions that modify the given function by breaking its environment, or passed arguments. We apply each test individually and run the unit tests. If any tests fail, the function is not pure against the unit test set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var testers = [destroyLexicalScope, destroyContext, destroyReferences, checkChangedArguments];
function isPure(context, functionName) {
console.log('checking if function', functionName, 'is pure');
var backup = context[functionName];
var pureTestFailed = testers.some(function (tester) {
context[functionName] = tester(backup);
var after = isWorking(context);
if (!after) {
console.error('function', functionName, 'is not pure under test', tester.name);
return true;
}
});
context[functionName] = backup; // restore original function
return pureTestFailed;
}

output

checking if function add is pure
checking if function add2 is pure
test add2 failed!
add is not defined
function add2 is not pure under test destroyLexicalScope
checking if function addNumbers is pure
test add numbers failed!
Function addNumbers modifies its arguments
function addNumbers is not pure under test checkChangedArguments
done

We could better target the unit tests to a particular function by using code coverage information, for example see bahmutov/untested.

Higher order functions

Unfortunately, the lexical scope test does not work with higher order functions. A higher order function is a function composed from other functions, for example, a partially applied function is a new function composed wrapping around a given function. For simplicity, let us write partial1 function that applies a single argument

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function partial1(fn, a) {
return function partiallyApplied() {
var rightArguments = Array.prototype.slice.call(arguments, 0);
var args = [a].concat(rightArguments);
return fn.apply(null, args);
};
}
var add10 = partial1(add, 10);
console.log(add10(2)); // 12
test('add10', function (context) {
console.assert(context.add10(2) === 12);
console.assert(context.add10(-1) === 9);
});
isPure(context, 'add10');

output

checking if function add10 is pure
test add10 failed!
a is not defined
function add10 is NOT pure under test destroyLexicalScope
function add10 is pure under test destroyContext
function add10 is pure under test destroyReferences
function add10 is pure under test checkChangedArguments
done

Why does add10 not pass destroyLexicalScope test? Just like other higher order functions, it relies on the the closure variables to work. Notice that the function returned from partial1(add, 10) is the inner part partiallyApplied. This function needs to access variables a and fn declared in function partial1 in order to work. The destroyLexicalScope test is created to specifically detect this case. If we knew the necessary lexical scope from partial1 implementation, we could probably pass it into our test, but this is a question for another day.

Conclusion

Of course this is very simplistic testing. For example, I would like to apply transitivity: functions that only use pure functions are pure themselves. Unfortunately our lexical scope test only copies a single function, destroying the original link to other pure functions. Maybe we can call these functions "pure stand alone functions".

While I cannot check every function yet, I think the above approach can identify lots of small functions that are pure under the given test set. This has value to the developer as this is a measurable number that can be increased via code refactoring.

Looking how some functions passed only some of our tests, we can talk about a purity hierarchy. Some functions will pass all the tests, achieving the purest status. These functions can be safely used anywhere, passed around, etc. Maybe it is hard or impossible to move every function to the purest status. Instead we can drive more functions to achieve some purity. This will lower the coupling in our code, increasing its quality. Then we can keep refactoring functions to move them to the next purity level.

Update

We could fake lexical scope, see this blog post.