¿Cuál es un término para una función que, cuando se llama repetidamente, tiene el mismo efecto que llamar una vez?

96

(Suponiendo un entorno de subproceso único)

Una función que cumple este criterio es:

bool MyClass::is_initialized = false;

void MyClass::lazy_initialize()
{
    if (!is_initialized)
    {
        initialize(); //Should not be called multiple times
        is_initialized = true;
    }
}

En esencia, puedo llamar a esta función varias veces y no preocuparme de que se inicialice MyClassvarias veces

Una función que no cumple este criterio podría ser:

Foo* MyClass::ptr = NULL;

void initialize()
{
    ptr = new Foo();
}

Llamar initialize()varias veces provocará una pérdida de memoria

Motivación

Sería bueno tener una sola palabra concisa para describir este comportamiento para que las funciones que se espera que cumplan este criterio puedan ser debidamente comentadas (especialmente útil cuando se describen funciones de interfaz que se espera que se anulen)

Rufus
fuente
67
Para los votantes cercanos: si bien es cierto que el 99.999% (estimación aproximada) de todas las preguntas de "nombre de esa cosa" están fuera de tema porque no tienen una respuesta objetiva única, correcta, inequívoca y nomenclatura es puramente subjetiva y basada en la opinión, éste lo hace tener una sola,,, respuesta objetiva inequívoca correcta, que fue dada por el propio OP.
Jörg W Mittag
30
Llamando varias veces lo hace tener un efecto, ya que podría haber otro código que cambia 'var' en el medio.
RemcoGerlich
77
¿Por qué se hizo esta pregunta, si el OP sabía la respuesta a la hora de preguntar ? ¿Hay alguna otra razón que no sea la creación de puntos / rep / karma?
dotancohen
13
@dotancohen Q / A estilo de respuesta automática es uno de los conceptos clave en StackExchange.
glglgl
17
@glglgl: Estoy de acuerdo, para preguntas con mérito. ¿Qué mérito tiene esta pregunta? Estoy seriamente preocupado de que comencemos a hacer que cada pregunta CS 101 sea formulada e inmediatamente respondida por el OP, cada término CS preguntado e inmediatamente definido por el OP, y todos los pros y contras del algoritmo básico cuestionados y luego respondidos inmediatamente por el OP ( no necesariamente este OP). ¿Es ese el sitio que queremos que sea la ingeniería de software?
dotancohen

Respuestas:

244

Este tipo de función / operación se llama Idempotente

Idempotence (UK: / ˌɪdɛmˈpoʊtəns /, [1] US: / ˌaɪdəm - /) [2] es propiedad de ciertas operaciones en matemáticas y ciencias de la computación por las cuales se pueden aplicar varias veces sin cambiar el resultado más allá de la aplicación inicial.

En matemáticas, esto significa que si f es idempotente, f ( f (x)) = f (x), que es lo mismo que decir ff = f .

En informática, esto significa que si f(x);es idempotente, f(x);es lo mismo que f(x); f(x);.

Nota: Estos significados parecen diferentes, pero bajo la semántica de estado denotacional , la palabra "idempotente" en realidad tiene el mismo significado exacto tanto en matemáticas como en ciencias de la computación.

Rufus
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
maple_shaft
51

El término preciso para esto (como menciona Woofas ) es idempotencia. Quería agregar que si bien podría llamar func1idempotente a su método, no podría llamarlo una función pura . Las propiedades de una función pura son dos: debe ser idempotente y no debe tener efectos secundarios, es decir, sin mutación de variables estáticas locales, variables no locales, argumentos de referencia mutables o flujos de E / S.

La razón por la que menciono esto es que una función idempotente con efectos secundarios tampoco es buena, ya que técnicamente idempotente se refiere al rendimiento de retorno de la función, y no a los efectos secundarios. Entonces, técnicamente, su func2método es idempotente, ya que la salida no cambia de acuerdo con la entrada.

Lo más probable es que desee especificar que desea una función pura. Un ejemplo de una función pura podría ser el siguiente:

int func1(int var)
{
    return var + 1;
}

Se puede encontrar más lectura en el artículo de Wikipedia "Función pura" .

Neil
fuente
37
Creo que su definición de idempotencia es demasiado limitada, o dicho de otro modo, está utilizando la definición matemática de idempotencia, no la de programación. Por ejemplo, los métodos HTTP PUTy DELETEse denominan idempotentes precisamente porque ejecutar sus efectos secundarios varias veces tiene el mismo efecto que ejecutarlos solo una vez. Estás diciendo "idempotencia significa f∘f = f", mientras que en programación, queremos decir "ejecutar ftiene el mismo efecto que ejecutar f; f". Tenga en cuenta que puede transformar fácilmente el segundo significado en el primero agregando un parámetro "mundo".
Jörg W Mittag
23
@Neil "Idempotencia es estrictamente un término matemático". No, no lo es, también se usa en redes y sistemas de comunicación / servidor de servidor cliente y se describe como lo describe JörgWMittag. Es un concepto útil porque permite múltiples solicitudes a un servidor / cliente con la misma operación / mensaje sin cambiar lo que ese mensaje original se propuso hacer. Esto es útil cuando tiene una comunicación poco confiable y necesita volver a intentar un comando porque el mensaje del cliente se descartó o la respuesta del servidor sí.
opa
77
Deberías entrar en más detalles sobre la diferencia entre puro e idempotente. Su ejemplo func1 no es idempotente porque func1(1) != func1(func1(1)).
Tezra
55
La pureza y la idempotencia son diferentes. Una función pura no tiene que ser idempotente en sentido matemático (obviamente es idempotente en términos de efectos secundarios, ya que no tiene ninguno). La función idempotente (en sentido de programación) no tiene que ser pura, como en el ejemplo dado por OP. Además, como se mencionó opa, la idempotencia es una propiedad útil con un uso estrictamente diferente de la pureza. Su definición de pureza como "idempotente y sin efectos secundarios" es errónea o al menos engañosa, rechaza.
Frax
55
En el contexto de la programación, no hay "efectos secundarios", pero si fuera a expandir la definición para incluir esto, entonces una función idempotente y una función pura significarían lo mismo. No, no significarían lo mismo en absoluto. Idempotente, no pura: void f(int var) { someGlobalVariable = var; }. Puro, no idempotente: int func1(int var) { return var + 1; }.
JLRishe
6

El término es idempotencia . Observe a continuación que hay una clara diferencia entre una función Idempotente (llamada recursivamente sobre sí misma; segundo bloque de código y la definición matemática) y la idempotencia funcional (llamada repetidamente con la misma entrada secuencialmente; primer bloque de código y, a menudo, el término que se entiende en Programación).

Se dice que una función f con efectos secundarios es idempotente bajo la composición secuencial f; f si, cuando se llama dos veces con la misma lista de argumentos, la segunda llamada no tiene efectos secundarios y devuelve el mismo valor que la primera llamada [cita requerida] (suponiendo que no se llamaron otros procedimientos entre el final de la primera llamada y el inicio de la segunda convocatoria).

Por ejemplo, considere el siguiente código de Python:

x = 0

def setx(n):
    global x
    x = n

setx(5)
setx(5)

Aquí, setx es idempotente porque la segunda llamada a setx (con el mismo argumento) no cambia el estado visible del programa: x ya estaba establecido en 5 en la primera llamada, y nuevamente se establece en 5 en la segunda llamada, manteniendo así el mismo valor Tenga en cuenta que esto es distinto de la idempotencia en la composición de funciones f ∘ f. Por ejemplo, el valor absoluto es idempotente en la composición de funciones:

def abs(n):
    if n < 0:
        return -n
    else:
        return n

abs(-5) == abs(abs(-5)) == abs(5) == 5
Tezra
fuente
3

En física he escuchado esto referido como una proyección :

una proyección es una transformación lineal P desde un espacio de vector a sí mismo de tal manera que P 2 = P . Es decir, cada vez que P se aplica dos veces a cualquier valor, da el mismo resultado que si se aplicara una vez (idempotente).

Gráficamente, esto tiene sentido si nos fijamos en una caricatura de una proyección vectorial :

ingrese la descripción de la imagen aquí

En la imagen, a 1 es la proyección de a sobre b , que es como la primera aplicación de su función. Las proyecciones posteriores de a 1 sobre b dan el mismo resultado a 1 . En otras palabras, cuando llama a una proyección repetidamente, tiene el mismo efecto que llamarla una vez.

Advertencia justa: nunca he escuchado que esto se use fuera de la física, por lo que a menos que tenga ese tipo de equipo en su equipo, podría confundir a todos.

usuario1717828
fuente
2
De hecho, este es un buen ejemplo concreto de cómo se puede visualizar una función idempotente (matemáticamente, y especialmente en el campo de la geometría vectorial / álgebra lineal). Si bien la "idempotencia" de la función de software es un concepto muy cercano, no creo que los desarrolladores / informáticos usen la palabra "proyección" en este contexto (una "función de proyección" en ingeniería de software preferiría referirse a una función que toma un objeto y devuelve un nuevo objeto derivado de él, o una propiedad de ese objeto, por ejemplo)
Pac0
2
@ Pac0 Oh, está bien. Trabajo al margen entre ciencia y programación, y no me di cuenta de que la palabra ya estaba sobrecargada. Puedo pensar en algunos ejemplos artificiales en el trabajo donde usaría esta terminología, pero ciertamente trabajo con personas que están dispuestas a soportar la jerga científica todos los días :-)
user1717828
3

Es un algoritmo determinista porque dada la misma entrada (en este caso sin entrada), siempre producirá la misma salida.

En informática, un algoritmo determinista es un algoritmo que, dada una entrada particular, siempre producirá la misma salida, con la máquina subyacente pasando siempre por la misma secuencia de estados. Los algoritmos deterministas son, con mucho, el tipo de algoritmo más estudiado y familiar, así como uno de los más prácticos, ya que pueden ejecutarse en máquinas reales de manera eficiente.

Las bases de datos SQL están interesadas en las funciones deterministas .

Una función determinista siempre da la misma respuesta cuando tiene las mismas entradas. La mayoría de las funciones SQL incorporadas en SQLite son deterministas. Por ejemplo, la función abs (X) siempre devuelve la misma respuesta siempre que su entrada X sea la misma.

Una función debe ser determinista si se usa para calcular un índice.

Por ejemplo, en SQLite, las siguientes funciones no deterministas no se pueden utilizar en un índice: random(), changes(), last_insert_rowid()y sqlite3_version().

Stephen Quan
fuente
66
El autor de la pregunta func2es determinista (no hay efectos aleatorios involucrados), pero ya se ha declarado que viola la propiedad que está buscando.
Draco18s
Que el mismo resultado se produzca por repetición no es lo mismo que decir que el mismo resultado se produce al anidar o encadenar. Las funciones deterministas son importantes para el almacenamiento en caché de resultados, más que para la indexación / hash.
mckenzm
3

Además de las otras respuestas, si hay una entrada específica al functon que tiene esta propiedad, es un punto fijo , un punto invariante o un punto fijo de la función. Por ejemplo, 1 a cualquier potencia es igual a 1, entonces (1ⁿ) ⁿ = 1ⁿ = 1.

El caso especial de un programa que se produce como salida es una quine .

Davislor
fuente
Las quines son para el software como los conjuntos de Cantor son para las matemáticas :-). Y, por supuesto, las cuotas no son idempotentes: fallan cuando la salida ya existe o "golpean" el resultado anterior y escriben una salida nueva, aunque idéntica.
Carl Witthoft