17

By definition, a pure function is deterministic + no side effect.

Is there any example for a function which has no side effects, but is non-deterministic? I.e., a function without side effects, but not pure.

To me non-deterministic function comes from randomness. But random generator has side effect. AFAIK random generator's implementation mutates some global state.

EDIT: duplicate with https://stackoverflow.com/q/54992302

Improve this question
29
  • 2
    @JörgWMittag I got the definition of pure = no side effect + deterministic from a book. Is it wrong?
    – Helin Wang
    Commented Oct 26, 2022 at 15:08
  • 1
    What do you mean by "wrong"? If the book says that is the definition, then that is the definition for that book. A different book may or may not have a different definition.
    – Jörg W Mittag
    Commented Oct 26, 2022 at 15:09
  • 3
    @JörgWMittag: Usually a pure function would be one that, in addition to having on side effects always returns the same outputs when given the same inputs. So, for example, a function that returns the current value of a global variable has no side effects (no state is altered etc), but it can return different values at different times, even for the same inputs (and hence is not "pure"). In particular a function with side effects is not necessarily pure.
    – psmears
    Commented Oct 27, 2022 at 10:56
  • 1
    @psmears: At least in the languages and communities that I am familiar with, accessing mutable state is a side-effect. But, as I pointed out in my comment above, it is entirely possible that the book the OP is reading defines those terms differently, and for understanding statements in the book, the only relevant definition is the definition in that book, just like for understanding statements made by me, the only relevant definition of those terms is mine.
    – Jörg W Mittag
    Commented Oct 27, 2022 at 11:08
  • 4
    @JörgWMittag: That is an unusual definition of side effect. Generally a function has a side effect if calling it affects global state - in other words, calling the function vs not calling it makes a difference; you can tell whether it was called or not. Reading global state wouldn't be a side effect under this definition. This matches the standard (non-CS) meaning of "side effect". You may use the term differently, but I believe the definitions I'm giving are more commonly accepted (eg they match the ones in Wikipedia :) ).
    – psmears
    Commented Oct 27, 2022 at 11:25

5 Answers 5

Reset to default
26

A properly working classical computer is, by definition, deterministic. That is, the output of the same series of steps with the same inputs will produce the same result. When we talk about non-determinism in that context, what that typically means (in my experience) is that there are implicit inputs whose state can vary.

If we accept the above, then a non-deterministic function with no side effects might be something like a pseudo-random number generator that uses the system clock time to generate numbers, the distinction being that it doesn't change any state as part of its execution. It's not pure because it depends on state.

I think it's important to reiterate that the actual function is still deterministic. If you changed such a function to accept a time value instead of using the system clock's state, it will produce the same output for the same time value.

Improve this answer
17
  • 30
    You don't need a pseudo-random number generator, just a function that returns the system clock. I think that's the minimal example for a non-deterministic function without side effects.
    – Rainer P.
    Commented Oct 27, 2022 at 11:16
  • 1
    Ah, I see. I explained my point poorly, then. I wasn't arguing that a true-random sample would reduce the number of implicit inputs, but rather that it is genuinely nondeterministic / unpredictable (even in theory), whereas the system clock's value is fully determined by its value at the previous nanosecond (or whatever precision). (Of course, in practice, in order to actually make that prediction, we'd need a second clock of at least as high a precision, but we could still make certain statements like "It'll be higher than it was last time", which can't be done at all for Cesium, etc.).
    – Ray
    Commented Oct 27, 2022 at 18:31
  • 1
    @Ray I get what you are saying. The point of the answer is that all computation in a classical computer is deterministic. When we say a function is 'non-deterministic' (meaning the same function inputs do not always return the same results) what we really mean is that there are other 'hidden' inputs not given as function parameters. The system clock example is just one of many possible sources of input. I chose it because it's ubiquitous.
    – JimmyJames
    Commented Oct 27, 2022 at 19:35
  • 1
    @Ray If the system clock has a different oscillator than the CPU, then the exact value read can depend on micrscopic zone temperature variations that cause slew between the two oscillators. These depend on quantum effects that are believed to be truly random. You can "mine" this on real computers by sampling the TSC (high speed clock) when a packet arrives over the network because the network card has its own oscillator.
    – David Schwartz
    Commented Oct 27, 2022 at 19:56
  • 3
    "there are implicit inputs whose state can vary" -- oh boy are there a lot of those cases. Sneaky, sneaky cases, like DateTime.Parse("1/1/2022") in C#, which uses the current culture to interpret which number is the month, and which number is the day. Any function that defaults to some system preference would seem to be deterministic on a single system, but non-deterministic across different systems, when in fact it is always non-deterministic. I can change my date/time preferences, and now my assumptions in code are wrong.
    – Greg Burghardt
    Commented Oct 28, 2022 at 12:54
38

Of course this depends on the definitions. Let's drop "pure" which has a definition in your question that clearly makes non-deterministic pure functions impossible as being deterministic is a requirement for being pure. Let's instead assume these simple definitions:

  • A function is deterministic if its output strictly depends on its inputs, i.e. it will never return different results if called with the same parameters.
  • A function is side-effect-free if it does not effect any outside state, i.e. there is no external state that could tell you whether the function was called or not.

So a side-effect-free nondeterministic function would need to access external state that is modified not by itself but by something else in its environment. For example, a function that returns the current temperature in my room would be side-effect-free (it does not change it) but nondeterministic (you don't know which result it will return when you call it again at another time).

By your definition, such a function isn't pure as it depends on other data besides its parameters.

Improve this answer
2
  • 6
    As a further clarification, note that pseudo-random number generators return a sequence of numbers. They maintain some state because they must remember which number in the sequence to return next, and are therefore not "side-effect-free" functions. But true random number sources take as their input some form of white noise or pink noise, in the form of, say, a thermal junction or an alpha particle radioactive source. That is a form of external state, not modified by the function. Of course, you could say the same about any function that reads the state of some mechanical device.
    – Robert Harvey
    Commented Oct 26, 2022 at 19:31
  • 7
    @RobertHarvey, I wouldn't veer into philosophy of physics. There is no known mechanism of determination for those processes, but science has certainly not found that they are "entirely non-deterministic".
    – Steve
    Commented Oct 26, 2022 at 21:48
13

There is no need to use some special hardware like a clock or sensors to give an example.

The point is, any function which return value can be influenced by a side effect of other functions is non-deterministic. Still, such functions don't need to have any side-effects by themselves.

Just as simple as

 int myVariable;   // outer scope (!), 
                   // will be changed somewhere else in the program

 int MyFunction(){ return myVariable; }

Based on this, I am sure you can now construct arbitrary non-deterministic, side-effect free functions by yourself, they just have to rely on some stateful variable outside the local scope of the function.

Improve this answer
11
  • If a function calls one that has side effects, the function itself has side effects. I do not think this answers the question. Otherwise calling File.WriteAllText() does not have side effects, because it simply calls some OS function (which has the side effects).
    – Tvde1
    Commented Oct 27, 2022 at 10:41
  • 3
    @Tvde1: that is not what I wrote, maybe you read my answer again.
    – Doc Brown
    Commented Oct 27, 2022 at 11:06
  • 1
    @Tvde1 This answer isn't saying that this function should call one that has side effects, only that a function without side effects might be affected by others that do have side effects that were called earlier at some point in the system. A function that returns the number of cached objects is such an example: while the function itself has no side effects (it simply returns the number of cached objects), other functions can add or remove things from the cache, thus making our example-function non-deterministic.
    – T. Sar
    Commented Oct 27, 2022 at 13:11
  • 1
    @Tvde1 It depends on your definitions. If you consider the entire memory state of the program to be "input", then you're right. But if you're just talking about the function's explicit parameters, then myVariable isn't an input.
    – Barmar
    Commented Oct 27, 2022 at 14:01
  • 4
    @Tvde1: scope matters, otherwise the whole term "side-effect" makes no sense.
    – Doc Brown
    Commented Oct 27, 2022 at 14:17
1

Pure functions are modelled after functions in mathematics (hence pure), which are, fundamentally, just sets of pairs (with some restrictions). Anything that cannot be thought of as a lookup in some (potentially infinite) collection of pairs is, in this sense, impure.

The definition that pure functions are deterministic and without side effects depends on the meanings of "deterministic" and "side effects", which are usually distinct from what programming languages define. This distinction is useful mainly for one thing, crucial to functional languages: you can seamlessly cache the output of the function for the given input, i.e. memoize the function.

A deterministic function does not really have to be predictable in a sense that you can find out the result without ever calling the function, but once you have it, it will never change unless the arguments change. A function which returns the startup time of your program is deterministic, because it never changes during the run-time of the program (context matters here). A function which returns the current weather at the precise point in time it is called is not deterministic (if your program doesn't happen in an instant), but if the time (and location) is an argument, it is deterministic. Even a true random number generator can be deterministic here if you give it an increasing counter (but it is obliged to return the old value for an unchanged counter). Even reading a file or downloading it from web can be deterministic if you cache the result based on the location. See fn:json-doc for example.

The second restriction is that the result (including changes in by-ref arguments) should be the only observable effect of the function. This doesn't mean that the function cannot change any state, but such change must be effectively hidden to the outside world. Caching a value must definitely change some state (to store the value), but if you don't have any way of knowing that, the cache behaves as it was pre-filled with the correct values from the beginning of the program. This is also complementary to the first restriction ‒ if a function modifies externally observable state, another function that reads the state can no longer be deterministic. If there is no such function, then it doesn't matter whether the first function modifies something, as it is not observable. By this token, all deterministic functions in the previous paragraph are also side effect-free, with the exception of sending a web request (which could have side effects). This also depends on what you choose as the environment and what counts as observing: a whole program can have side effects, but its individual functions can all be pure; and using reflection usually does not count as breaking the purity of caching functions.

Based on these definitions, there are a lot of functions that are non-deterministic but without side effects: reading from any sort of sensor, reading from a dynamic web page, reading from a port or a changeable file, getting a (pseudo-)random number (if a non-deterministic function has a side effect only on itself, then it's not really a side effect) etc. All of these functions can also be made deterministic if you "bind" them to something, i.e. a counter, time and so on.

Improve this answer
4
  • "Even reading a file or downloading it from web can be deterministic if you cache the result based on the location." The act of caching itself makes the function non-deterministic. A deterministic function runs the same exact steps for the same input. If you run it twice and it does different steps each time (read: goes into a different decision branch because of the cache), then it isn't deterministic.
    – T. Sar
    Commented Oct 27, 2022 at 13:19
  • @T.Sar That depends on the definition of "deterministic". For practical purposes, it doesn't matter whether it performs the exact same steps each time, only whether the result is the same or not. For outside code, the function is a black box anyway and it doesn't matter what it does (especially not if it's pure). See the linked XPath function listing for the meaning of "deterministic" I use here.
    – IS4
    Commented Oct 27, 2022 at 20:23
  • 'For practical purposes, it doesn't matter whether it performs the exact same steps each time" It can absolutely matter in some cases, specially in time-sensitive or high-security contexts. A pure function that stores values inside itself has a different set of implications than one that doesn't, and while it is true that for most applications this won't make a difference, it doesn't make the function deterministic - at least, not in the more usual sense of the world. That said, I agree it boils down to the definition of deterministic.
    – T. Sar
    Commented Oct 27, 2022 at 21:10
  • @T.Sar Yeah, I agree that the run-time of a function or other observable/measurable effects (space requirements and allocations) can matter too, but then I think it's either a side effect or a "result" of the function, once it is something you care about.
    – IS4
    Commented Oct 27, 2022 at 21:49
-1

Any function whose result is dependent on state outside the computer, i.e. functions that read from external devices -- the network, monitoring equipment, user input. results.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.