Purity of numerical algorithms

[berquist]

We had a discussion in #495 about the purity of functions. The argument is that for many algorithms, specifically numerical ones, the implementation should not be pure for performance reasons, specifically memory. While the goal is not to write for performance, an algorithm should be written idiomatically for both 1. the language and (potentially) 2. how it is used. Also, from my experience, while it is easier to reason about the output of a pure numerical function by definition, it is not always easier to read. For algorithms of the scale in this book, this is probably a non-issue.

My proposal was to write all algorithms as being pure, but have text somewhere explaining the difference in the context of numerical algorithms, because it is an important topic not often touched upon.

[jiegillet]

+1. I suggest adding something in the how to contribute page. Maybe add a point after style named purity and explain the reason why we use pure functions here.

[leios]

I think it fits best in the Code style guide as a general principle.

I also agree that we should create a "disclaimer" chapter in place of the current how to contribute chapter (since the functionality of that one has been replaced by the how to contribute wiki). Basically, it would be nice to have some text describing the purpose of the code in the AAA.

[Butt4cak3]

I'm the one who originally pointed out that the current Thomas algorithm implementations aren't pure and I suggested we'd change that. The more I thought about it, the less convinced I became, though. The reason is that it adds a certain degree of complexity to the algorithms and makes them a bit more difficult to understand by reading their code. The code is not as self-explanatory anymore.

So one thing we could do to counteract this is to add some comments in the reference (Julia) code and require other implementations to also include them. I'm thinking of something like what I did in my Thomas algorithm cleanup:

algorithm-archive/contents/thomas_algorithm/code/java/Thomas.java

Lines 2 to 5 in 9ca87e1

	private static double[] thomasAlgorithm(double[] a, double[] b, double[] c, double[] x) {
	int size = a.length;
	double[] y = new double[size]; // This is needed so that we don't have to modify c
	double[] solution = new double[size];

[Yordrar]

I think that the goal of the code sample should be readability over performance as there are a lot of possible ways to optimize code with many of them having some sort of obfuscation. The code should be as readable as possible so that anyone can understand it easily and adapt it to their needs. Now if that means that some functions should be pure and some of them shouldn't, so be it.

[leios]

My understanding here is that we would still like pure functions, but we also more heavily comment these functions to make it more clear what we are doing?

[Yordrar]

@leios well it depends on the algorithm, we can't really say for sure, maybe one is more readable but another one introduces a couple more steps or extra variables

[berquist]

Yes, I think that is a good approach (commenting + adding to how to contribute).