Esattamente quali regole devono rispettare una funzione prima di poterla chiamare "idempotente"?

Question

A post from another thread dice che una funzione è detta idempotente se può essere chiamata più volte senza modificare il risultato.

Tuttavia i termini utilizzati (come gli effetti senza effetti e gli stessi risultati restituiti) sono relativamente ambigui. Considerate questo pezzo di codice:

public class test { 

    int x = 0; 
    java.util.Random r = new java.util.Random(); 

    public int F() { 
     return x + 1; 
    } 

    public void F2() { 
     x = r.nextInt(); 
    } 
} 

possiamo dire che F() è idempotente perché le chiamate successive alla F() restituisce lo stesso valore?

O è non idempotent in quanto le chiamate successive alla F() non restituire lo stesso valore se F2() si chiama inbetween?

_{PS: "idempotent", come definito in informatica, non è matematica.}

Answer 1

La funzione non è idempotente. Può restituire risultati diversi. Dato lo stesso input, una funzione idempotente restituisce sempre lo stesso output.

Più esplicitamente, se f() è idempotente (secondo la definizione di informatica), allora:

int result1 = f(x); 
// ... some arbitrary code 
int result2 = f(x); 
assert(result1 == result2); 

Answer 2

ho intenzione di essere in disaccordo con (in realtà, ora vedo che sono d'accordo con loro!) l'altro risponde e dice che, nell'uso più comune della scienza informatica (chiamate di funzione con effetti collaterali, non di programmazione funzionale), una funzione è idempotente se è possibile sostituire in modo sicuro qualsiasi invocazione della funzione chiamando la funzione due volte e mantenendo solo il secondo risultato.

Ad esempio, consideriamo due funzioni per l'eliminazione di un file per nome:

1) una funzione che restituisce il successo se il file non esiste. (Poiché lo scopo di un'operazione di eliminazione è di rendere il file inesistente.)

2) Una funzione che restituisce un errore "file inesistente" se il file non esiste. (Poiché il file non può essere eliminato.)

Il primo è idempotente. Se la chiami e ignori il risultato, puoi chiamarlo di nuovo e ottenere comunque informazioni corrette. Il file non esiste quando hai finito.

Il secondo non è idempotente. Se lo chiami una volta e ignori il risultato, la tua seconda chiamata fallirà, facendoti pensare che non hai cancellato il file.

Una funzione per ottenere l'ora corrente è idempotente in base a questa definizione, anche se il risultato potrebbe essere diverso. Non c'è nulla di male nel chiamare la funzione due volte.

Il concetto è importante nei protocolli client-server. Supponiamo che tu invii un comando e non ricevi alcuna risposta, forse la connessione si interrompe, forse il server si è bloccato. Quindi si invia di nuovo il comando e si ottiene una risposta. Ma al primo comando, era il comando perso o la risposta? Se il comando è idempotente, non importa. Puoi semplicemente usare il risultato.

Se un protocollo garantisce che tutte le operazioni siano idempotenti, il codice di livello inferiore può riprovare operazioni non riuscite, cambiare server e in altro modo cercare di "far funzionare le cose" senza interrompere la semantica delle operazioni.

Ci vuole un po 'di tempo per fare un protocollo idempotente. Ad esempio, potresti chiederti come esegui un'operazione "cancella file". Un modo è assegnare a ciascun file un ID univoco che cambia quando il file viene eliminato e ricreato. Quindi dividi un'eliminazione in due metà. Il primo, "Ottieni ID dal nome" è idempotente e fallisce se il file non esiste. Il secondo, "cancella ID se esiste" è idempotente e ha successo se tu o qualcun altro hai cancellato il file. (L'unica stranezza è che questo non ti dice per certo che sei stato tu a cancellare il file.) La combinazione delle due operazioni idempotenti fornisce l'operazione di cancellazione non idempotente desiderata.

Answer 3

Cercando di riassumere le cose che sono venuti fino in altre risposte e nei commenti:

c'è solo una definizione di "idempotent". Una funzione f è idempotente se e solo se f(f(x)) è uguale a f(x) per tutti x nel dominio f.

C'è più di una definizione di "uguale". In molti contesti, abbiamo un'idea di "equivalenza" che rappresenta l'uguaglianza, e la definizione di "equivalente" potrebbe essere diversa nei diversi contesti.

C'è più di una definizione di "funzione". In matematica (con una costruzione convenzionale teorica dell'insieme), una funzione è un insieme di coppie. Il "dominio" della funzione è l'insieme di tutti gli elementi che appaiono nella prima posizione di una coppia. Nessun elemento del dominio appare nella prima posizione di più di una coppia nella funzione. La "gamma" della funzione è l'insieme di tutti gli elementi che appaiono nella seconda posizione di una coppia. Gli elementi dell'intervallo possono apparire più di una volta. Diciamo che una funzione "mappa" ogni elemento del suo dominio su un particolare elemento del suo intervallo e scriviamo f(x) come "il secondo elemento della coppia in f che ha come primo elemento x".

Quindi, è chiaro che per una funzione essere idempotente, il suo intervallo deve essere un sottoinsieme del suo dominio. Altrimenti, f(f(x)) non ha senso.

In informatica, e in particolare in linguaggi imperativi, una funzione viene spesso definita come una sequenza di istruzioni/istruzioni, insieme ad alcuni input ed output con nome (nella maggior parte delle lingue c'è un solo output). "Chiamare" una funzione è un'operazione imperativa che significa eseguire le istruzioni. Ma le istruzioni in una lingua imperativa possono avere effetti collaterali: possono cambiare le cose oltre alle loro uscite. Questo concetto è assente dalla matematica, così come dalla pura programmazione funzionale.

Queste "funzioni" imperativi, che mi riferirò d'ora in poi come "routine", possono essere riconciliati con la definizione matematica di una funzione in due modi:

1. ignorare gli effetti collaterali, e dire che la routine è una funzione il cui dominio è l'insieme di tutte le possibili combinazioni di valori di argomento e che mappa quelli agli output della routine. Ciò si basa su un debole fondamento teorico se la funzione non è "pura", vale a dire se il suo output dipende dallo stato mutabile oltre i suoi argomenti, o se modifica lo stato oltre le sue uscite. Il motivo è che una funzione matematica per definizione non mappa i suoi input in output diversi in momenti diversi. Né una funzione matematica "cambia" le cose quando "chiama", perché le funzioni matematiche non sono "chiamate" un determinato numero di volte. Semplicemente "sono".

2. incorporano gli effetti collaterali in una funzione matematica che descrive l'effetto che chiamata la routine ha sullo stato completo della macchina, comprese le uscite dalla routine ma anche compresi tutti stato globale e quant'altro. Questo è un trucco standard in CS, e significa che per ogni istruzione, istruzione, chiamata a una routine o qualsiasi altra cosa, esiste una funzione corrispondente che mappa lo stato della macchina prima della chiamata, in seguito allo stato della macchina.

Ora, se applichiamo la definizione di "idempotent" nel caso in cui 1, stiamo valutando se la funzione matematica che una routine particolare è stato progettato per implementare è idempotente. Se la routine fa qualcosa di diverso dall'implementazione di una funzione matematica, ad esempio se ha effetti collaterali, allora siamo su un terreno molto traballante qui e otterremo risultati fuorvianti. Ad esempio, la funzione int f(int i) { puts("hello!"); return i; } potrebbe essere considerata idempotente sulla base del fatto che "è un'implementazione della funzione di identità!". E questo è vero se si ignorano gli effetti collaterali, ma ciò significa che la definizione è inutile per qualsiasi scopo pratico, perché una volta che gli effetti collaterali sono presi in considerazione, l'esecuzione dell'espressione f(f(0)) è una cosa diversa dall'esecuzione dell'espressione f(0). f(f(0)) non è equivalente a f(0) anche se i loro valori di ritorno sono uguali e potremmo sostituirne uno con l'altro se non ci interessa (quella parte di) l'output del programma.

Se applichiamo la definizione di "idempotente" alle funzioni degli stati macchina nel caso 2, stiamo valutando indipendentemente dal fatto che una chiamata alla funzione (con argomenti particolari) sia un'operazione di idempotenza sullo stato della macchina. Quindi la mia funzione f sopra è chiaramente non idempotente: lo stato di una macchina con "ciao! \ N" scritto sul dispositivo di output non è lo stesso di una macchina con "ciao! \ Nhello! \ N" scritto sul suo dispositivo di output. Penso che sia anche chiaro che in questo caso, la tua funzione F è idempotente (sebbene non sia "pura", poiché il suo valore di ritorno dipende da uno stato diverso dai suoi parametri formali, e quindi non è semplicemente un'implementazione di una funzione matematica) e la funzione F2 non è idempotente. Se test fosse immutabile, allora potremmo ragionevolmente iniziare a descrivere F come puro. F2 quindi non sarebbe valido.

Per quanto ne so, quando compscis parla di idempotenza in lingue imperative, di solito si parla di se le funzioni degli stati macchina definite dal caso 2, sono o non sono idempotenti. Ma l'uso può variare - se la routine è pura, allora potrebbero parlare se la funzione matematica che rappresenta è idempotente. In un puro linguaggio funzionale non c'è nessuno stato macchina di cui parlare, quindi il caso 2 sarebbe inappropriato, e qualsiasi uso del termine "idempotente" in relazione a una funzione deve essere il caso 1. Le funzioni in puro linguaggio funzionale sono sempre come funzioni matematiche .

Answer 4

Ho anche cercato di capire che cosa significhi realmente l'idempotenza e ho capito che ci sono più definizioni di idempotenzialità che fluttuano intorno. Ci sono due campi che seguono le definizioni, sia la definizione per le funzioni matematiche e di programmazione delle funzioni sia la definizione di informatica.

Definizione matematica: f(f(x)) = f(x) for any value x. In altre parole, una funzione è idempotente se l'effetto della funzione è invariante in composizione.

Definizione di informatica: Una funzione è idempotente se "l'effetto collaterale di N> 0 richieste identiche è lo stesso di una singola richiesta". In altre parole, una funzione è idempotente se l'effetto è invariante rispetto al numero di chiamate.

Ad esempio, eseguire una funzione di incremento definita come int f(int x) { return x+1; }. Questa funzione fallirà la definizione matematica in quanto non è invariante in composizione perché f (f (x))! = F (x). D'altra parte, si adatta la definizione informatica in quanto, come detto Steve McLeod,

int result1 = f(x); 
// ... some arbitrary code 
int result2 = f(x); 
assert(result1 == result2); 

Ora, tornando alla tua domanda, è F() nel tuo esempio idempotente? Sto dicendo sì F() è idempotente ma una sequenza di chiamate potrebbe non esserlo. In base alla definizione di idempotenza del protocollo HTTP/1.1, "è possibile che una sequenza di più richieste non sia idempotente anche se tutti i metodi eseguiti in tale sequenza sono idempotenti".

Ciò è possibile perché è necessario considerare lo stato del programma come un parametro nascosto per la funzione F(). Ad esempio, considera una sequenza di esempio di richieste di F(), F(), F2(), F(). L'ultima richiesta F() non produrrà lo stesso risultato dei primi due, ma va bene perché la richiesta non era identica. È necessario considerare lo stato del programma come un parametro nascosto per la funzione e nell'ultima richiesta, lo stato era che x era uguale a un nuovo valore casuale, ma nelle prime richieste lo stato di x era inizialmente zero.

Fonti:

• Five-Dollar Words for Programmers, Part One: Idempotence
• HTTP/1.1: Method Definitions
• Idempotence Wiki