A function that accepts some value and returns some other value, and doesn't disturb anything outside of the function, has no side effects, and is therefore thread-safe. If you want to consider things like how the way the function executes affects power consumption, that's a different problem.
I am assuming that you're referring to a Turing-complete machine that is executing some sort of well-defined programming language, where the implementation details are irrelevant. In other words, it shouldn't matter what the stack is doing, if the function I'm writing in my programming language of choice can guarantee immutability within the confines of the language. I don't think about the stack when I'm programming in a high-level language, nor should I have to.
To illustrate how this works, I'm going to offer a few simple examples in C#. In order for these examples to be true, we have to make a couple of assumptions. First, that the compiler follows the C# specification without error, and second, that it produces correct programs.
Let's say I want a simple function that accepts a string collection, and returns a string that is a concatenation of all of the strings in the collection separated by commas. A simple, naïve implementation in C# might look like this:
public string ConcatenateWithCommas(ImmutableList<string> list)
{
string result = string.Empty;
bool isFirst = false;
foreach (string s in list)
{
if (isFirst)
result += s;
else
result += ", " + s;
}
return result;
}
This example is immutable, prima facie. How do I know that? Because the string object is immutable. However, the implementation is not ideal. Because result is immutable, a new string object has to be created each time through the loop, replacing the original object that result points to. This can negatively affect speed and put pressure on the garbage collector, since it has to clean up all of those extra strings.
Now, let's say I do this:
public string ConcatenateWithCommas(ImmutableList<string> list)
{
var result = new StringBuilder();
bool isFirst = false;
foreach (string s in list)
{
if (isFirst)
result.Append(s);
else
result.Append(", " + s);
}
return result.ToString();
}
Notice that I've replaced string result with a mutable object, StringBuilder. This is much faster than the first example, because a new string is not created each time through the loop. Instead, the StringBuilder object merely adds the characters from each string to a collection of characters, and outputs the whole thing at the end.
Is this function immutable, even though StringBuilder is mutable?
Yes, it is. Why? Because each time this function is called, a new StringBuilder is created, just for that call. So now we have a pure function that is thread-safe, but contains mutable components.
But what if I did this?
public class Concatenate
{
private StringBuilder result = new StringBuilder();
bool isFirst = false;
public string ConcatenateWithCommas(ImmutableList<string> list)
{
foreach (string s in list)
{
if (isFirst)
result.Append(s);
else
result.Append(", " + s);
}
return result.ToString();
}
}
Is this method thread-safe? No, it isn't. Why? Because the class is now holding state on which my method depends. A race condition is now present in the method: one thread may modify IsFirst, but another thread may perform the first Append(), in which case I now have a comma at the beginning of my string which is not supposed to be there.
Why might I want to do it like this? Well, I might want the threads to accumulate the strings into my result without regard to order, or in the order that the threads come in. Maybe it's a logger, who knows?
Anyway, to fix it, I put a lock statement around the method's innards.
public class Concatenate
{
private StringBuilder result = new StringBuilder();
bool isFirst = false;
private static object locker = new object();
public string AppendWithCommas(ImmutableList<string> list)
{
lock (locker)
{
foreach (string s in list)
{
if (isFirst)
result.Append(s);
else
result.Append(", " + s);
}
return result.ToString();
}
}
}
Now it's thread-safe again.
The only way that my immutable methods could possibly fail to be thread-safe is if the method somehow leaks part of its implementation. Could this happen? Not if the compiler is correct and the program is correct. Will I ever need locks on such methods? No.
For an example of how implementation could possibly be leaked in a concurrency scenario, see here.
