52

I'm trying to remember a word, I think it's related to computational or database theory. The closest synonym is atomic but that's not exactly it. Basically it's a kind of computation that should produce the same result even when run multiple times in a row, meaning it doesn't create side effects for itself.

I specifically ran across this word in a Stack Overflow answer about a chmod command (or some other permission related operation).

Hopefully that's enough to go on. Poking around Wikipedia isn't much help.

pdr
  • 53,387
  • 14
  • 137
  • 224
Mark Fox
  • 726
  • 1
  • 5
  • 10
  • 5
    It makes sense to specify whether you pass the same input to every call of operation or run every next operation on results of the previous call. – maxim1000 Apr 05 '13 at 04:34
  • 3
    @maxim1000 Agreed. Judging by the variety of answers, no one is sure which the OP meant. – ford Apr 05 '13 at 06:10
  • The problem here is that the question in the subject is not strictly the same as the question in the body. I answered the one in the subject but, looking again now, I'm pretty sure that's not what the poster wanted. *Edits question, deletes answer* – pdr Apr 05 '13 at 08:59
  • Are you asking about something like a GET request (where the same result is returned every time no matter what), or are you asking about something like the assignment operator (which does have an effect, but repeating the same assignment doesn't change anything)? – Izkata Apr 05 '13 at 13:28

5 Answers5

110

You might be thinking of "Idempotent".

Idempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application.

Matthew King
  • 2,200
  • 1
  • 16
  • 17
  • 17
    Basically, `f` is idempotent IFF `f(f(x)) == f(x)` FORALL `x`. – Jörg W Mittag Apr 05 '13 at 01:34
  • 1
    Interesting limitation of the description - The talk section of the linked page discusses Elevator buttons.. There must be 1000's of behaviors that can be described as "Idempotent" not related to Math or Comp Sci. – mattnz Apr 05 '13 at 06:46
  • From my understanding of the question, that's not at all what the OP is asking, as he doesn't speak of applying the algorithm on the results of the first iteration, but reapplying it on the same source data. Something more like if x=y, then F(x)=F(y) – Joubarc Apr 05 '13 at 07:48
  • 2
    @Joubarc yes idempotent has a slightly looser meaning in computing then the rest of maths, hence it is correct. http://en.wikipedia.org/wiki/Idempotent#Computer_science_meaning – jk. Apr 05 '13 at 09:00
  • I had read the page and I admittedly wasn't convinced at the time; but to be honest it's not concept of idempotence I had a problem with; rather, it was whether the question was about it or not. But now that I read it again, I admit I was wrong (especially given the chmod example which is a good case) – Joubarc Apr 05 '13 at 09:09
  • 1
    @Joubarc That just means it's a function. Operations which on the same input may act differently cannot be called functions from a mathematical standpoint. If in programming they are called functions, the functions that do in fact always give the same output for the same input are called `pure` functions... Well, kinda, they also have to not have any side effect at all. – Paul Stelian Nov 09 '19 at 19:56
13

The general word is Idempotence which applies to both computers and to mathematics. It is not the same thing as Reentrant which it often gets confused with. Idempotence is precisely what you described, Reentrant is basically interruptible with the ability to pick up exactly where you left off.

Purely Functional languages like Haskell are built around the principle of being as close to Idempotent as is possible. The first three letters of the acronym ACID in Database Theory are Idempotence as applied to Databases.

11

You might be looking for a pure function.

As defined in the link, two conditions make a function pure:

  1. The function always evaluates the same result value given the same argument value(s).
  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.
Sebastien Julien
  • 111
  • 2
  • 5
    Purity goes beyond simple idempotence: a pure function cannot have any side effects at all, while an idempotent one can have side effects as long as they don't cause subsequent runs to do different things. For example, a function that uses local mutable variables is not pure, but it is probably idempotent. You could even write a function that uses *global* variables and is still idempotent, as long as you make sure it guards those globals to make it reentrant. – tdammers Apr 05 '13 at 08:00
  • 3
    @tdammers Purity and idempotence are completely orthogonal: a pure function doesn’t have to be idempotent and vice versa. For instance, `f(x) := x + 1` is pure but certainly not idempotent. – Konrad Rudolph Apr 05 '13 at 11:51
4

In linear algebra linear, idempotent functions are called projections. Maybe that's the word you're looking for. :)

http://en.wikipedia.org/wiki/Projection_(linear_algebra)

Sarien
  • 751
  • 4
  • 13
2

Another possibility is deterministic.

In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.

Graham Borland
  • 809
  • 6
  • 7
  • 1
    this has been in just deleted prior answer; comment that challenged this idea was: "This is wrong. For example, the algorithm which swaps two values is perfectly deterministic but running it twice will not produce the same result as running it once." – gnat Apr 05 '13 at 10:13
  • 2
    It's not clear whether or not this answers the original question, because the original question isn't very well phrased, but I've up-voted this reply because the word deterministic might well be the one that someone was searching for when they ended up here. – Richard Whitehead Jun 01 '17 at 08:44
  • If you mutate the input values prior to the next run, how can you claim that you provide the routine with the same exact argument values..? – Hein Haraldson Berg Sep 29 '17 at 10:42