Puntatori a funzione, chiusure e lambda
https://stackoverflow.com/questions/208835
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto solo ora imparando i puntatori a funzione e, mentre stavo leggendo il capitolo K & amp; R sull'argomento, la prima cosa che mi ha colpito è stata, "Ehi, questo è un po 'come una chiusura." Sapevo che questo presupposto è fondamentalmente sbagliato in qualche modo e dopo una ricerca online non ho trovato alcuna analisi di questo confronto.
Quindi perché i puntatori di funzioni in stile C sono sostanzialmente diversi dalle chiusure o dalle lambda? Per quanto posso dire, ha a che fare con il fatto che il puntatore a funzione indica ancora una funzione definita (denominata) in contrapposizione alla pratica di definire anonimamente la funzione.
Perché passare una funzione a una funzione vista come più potente nel secondo caso, in cui è senza nome, rispetto al primo in cui è passata solo una normale funzione quotidiana?
Per favore, dimmi come e perché sbaglio a confrontare i due così da vicino.
Grazie.
Soluzione
Una lambda (o closing ) incapsula sia il puntatore che le variabili. Ecco perché, in C #, puoi fare:
int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
return i < lessThan;
};
Ho usato un delegato anonimo lì come chiusura (la sua sintassi è un po 'più chiara e più vicina a C dell'equivalente lambda), che ha catturato meno di una variabile dello stack nella chiusura. Quando viene valutata la chiusura, continuerà a fare riferimento a lessThan (il cui stack frame potrebbe essere stato distrutto). Se cambio di meno, allora cambio il confronto:
int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
return i < lessThan;
};
lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false
In C, questo sarebbe illegale:
BOOL (*lessThanTest)(int);
int lessThan = 100;
lessThanTest = &LessThan;
BOOL LessThan(int i) {
return i < lessThan; // compile error - lessThan is not in scope
}
sebbene potrei definire un puntatore a funzione che accetta 2 argomenti:
int lessThan = 100;
BOOL (*lessThanTest)(int, int);
lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false
BOOL LessThan(int i, int lessThan) {
return i < lessThan;
}
Ma ora devo passare i 2 argomenti quando lo valuto. Se volessi passare questo puntatore a un'altra funzione in cui lessThan non rientrava nell'ambito, avrei dovuto tenerlo in vita manualmente passandolo a ciascuna funzione della catena o promuovendolo a livello globale.
Sebbene la maggior parte dei linguaggi tradizionali che supportano le chiusure utilizzino funzioni anonime, non è necessario. Puoi avere chiusure senza funzioni anonime e funzioni anonime senza chiusure.
Riepilogo: una chiusura è una combinazione di puntatore a funzione + variabili acquisite.
Altri suggerimenti
Come qualcuno che ha scritto compilatori per le lingue con e senza chiusure "vere", non sono rispettosamente d'accordo con alcune delle risposte sopra. Una chiusura Lisp, Scheme, ML o Haskell non crea una nuova funzione in modo dinamico . Invece riutilizza una funzione esistente ma lo fa con nuove variabili libere . La raccolta di variabili libere è spesso chiamata ambiente , almeno dai teorici del linguaggio di programmazione.
Una chiusura è solo un aggregato contenente una funzione e un ambiente. Nel compilatore Standard ML del New Jersey, ne abbiamo rappresentato uno come record; un campo conteneva un puntatore al codice e gli altri campi contenevano i valori delle variabili libere. Il compilatore ha creato una nuova chiusura (non funzione) in modo dinamico allocando un nuovo record contenente un puntatore allo stesso codice, ma con diversi per le variabili libere.
Puoi simulare tutto ciò in C, ma è un dolore nel culo. Sono popolari due tecniche:
-
Passa un puntatore alla funzione (il codice) e un puntatore separato alle variabili libere, in modo che la chiusura sia suddivisa in due variabili C.
-
Passa un puntatore a una struttura, dove la struttura contiene i valori delle variabili libere e anche un puntatore al codice.
La tecnica n. 1 è l'ideale quando si tenta di simulare un tipo di polimorfismo in C e non si desidera rivelare il tipo di ambiente --- si utilizza un puntatore vuoto * per rappresentare l'ambiente. Ad esempio, guarda le Interfacce e implementazioni C di Dave Hanson . La tecnica n. 2, che ricorda più da vicino ciò che accade nei compilatori di codice nativo per linguaggi funzionali, ricorda anche un'altra tecnica familiare ... Oggetti C ++ con funzioni di membro virtuale. Le implementazioni sono quasi identiche.
Questa osservazione ha portato a un saggio di Henry Baker:
Le persone nel mondo Algol / Fortran si sono lamentate per anni di non aver capito quale possibile utilizzo delle chiusure delle funzioni avrebbe avuto nella programmazione efficiente del futuro. Poi è avvenuta la rivoluzione della "programmazione orientata agli oggetti" e ora tutti i programmi usano le chiusure delle funzioni, tranne che si rifiutano ancora di chiamarle così.
In C non puoi definire la funzione in linea, quindi non puoi davvero creare una chiusura. Tutto quello che stai facendo è passare un riferimento ad un metodo predefinito. Nelle lingue che supportano metodi / chiusure anonime, la definizione dei metodi è molto più flessibile.
Nei termini più semplici, i puntatori a funzione non hanno alcun ambito associato (a meno che non si contenga l'ambito globale), mentre le chiusure includono l'ambito del metodo che li sta definendo. Con lambdas, puoi scrivere un metodo che scrive un metodo. Le chiusure ti consentono di associare "alcuni argomenti a una funzione e di conseguenza ottenere una funzione di livello inferiore." (tratto dal commento di Thomas). Non puoi farlo in C.
EDIT: aggiungendo un esempio (ho intenzione di usare la sintassi di Actionscript-ish perché è quello che ho in mente in questo momento):
Supponi di avere un metodo che utilizza un altro metodo come argomento, ma non fornisce un modo per passare alcun parametro a quel metodo quando viene chiamato? Ad esempio, alcuni metodi che causano un ritardo prima di eseguire il metodo che hai passato (stupido esempio, ma voglio mantenerlo semplice).
function runLater(f:Function):Void {
sleep(100);
f();
}
Ora supponiamo che tu voglia eseguire runLater () per ritardare l'elaborazione di un oggetto:
function objectProcessor(o:Object):Void {
/* Do something cool with the object! */
}
function process(o:Object):Void {
runLater(function() { objectProcessor(o); });
}
La funzione che stai passando a process () non è più una funzione definita staticamente. Viene generato dinamicamente ed è in grado di includere riferimenti a variabili che erano nell'ambito nell'ambito della definizione del metodo. Pertanto, può accedere a "o" e "objectProcessor", anche se quelli non rientrano nell'ambito globale.
Spero che abbia senso.
Chiusura = logica + ambiente.
Ad esempio, considera questo metodo C # 3:
public Person FindPerson(IEnumerable<Person> people, string name)
{
return people.Where(person => person.Name == name);
}
L'espressione lambda non solo incapsula la logica ("confronta il nome") ma anche l'ambiente, incluso il parametro (ovvero la variabile locale) "nome".
Per ulteriori informazioni al riguardo, dai un'occhiata al mio articolo sulle chiusure che ti porta attraverso C # 1, 2 e 3, che mostrano come le chiusure semplificano le cose.
In C, i puntatori a funzione possono essere passati come argomenti a funzioni e restituiti come valori da funzioni, ma le funzioni esistono solo al livello più alto: non è possibile annidare le definizioni delle funzioni tra loro. Pensa a cosa sarebbe necessario per C per supportare le funzioni nidificate che possono accedere alle variabili della funzione esterna, pur essendo in grado di inviare puntatori di funzioni su e giù per lo stack di chiamate. (Per seguire questa spiegazione, dovresti conoscere le basi di come le chiamate di funzione sono implementate in C e in linguaggi molto simili: sfogliare call stack voce su Wikipedia.)
Che tipo di oggetto è un puntatore a una funzione nidificata? Non può essere solo l'indirizzo del codice, perché se lo chiami, come accede alle variabili della funzione esterna? (Ricorda che a causa della ricorsione, potrebbero esserci più chiamate diverse della funzione esterna attiva contemporaneamente). Questo è chiamato problema funarg e ci sono due sottoproblemi: il problema funargs verso il basso e il problema funargs verso l'alto.
Il problema di funarg verso il basso, ovvero l'invio di un puntatore a funzione "in basso nello stack" come argomento per una funzione chiamata, in realtà non è incompatibile con C e GCC supporta le funzioni nidificate come funarg verso il basso. In GCC, quando si crea un puntatore a una funzione nidificata, si ottiene effettivamente un puntatore a un trampolino , un pezzo di codice costruito dinamicamente che imposta il puntatore di collegamento statico e quindi chiama la funzione reale, che utilizza il puntatore di collegamento statico per accedere alle variabili della funzione esterna.
Il problema funargs verso l'alto è più difficile. GCC non impedisce di consentire l'esistenza di un puntatore a trampolino dopo che la funzione esterna non è più attiva (non ha record nello stack di chiamate), quindi il puntatore del collegamento statico potrebbe puntare a immondizia. I record di attivazione non possono più essere allocati su uno stack. La solita soluzione consiste nell'allocarli sull'heap e lasciare che un oggetto funzione che rappresenta una funzione nidificata punti semplicemente il record di attivazione della funzione esterna. Tale oggetto è chiamato chiusura . Quindi la lingua dovrà in genere supportare garbage collection in modo che i record possano essere liberato quando non ci sono più puntatori che li puntano.
Le lambdas ( funzioni anonime ) sono davvero un problema separato, ma di solito un linguaggio che consente le funzioni anonime definite al volo ti permetteranno anche di restituirle come valori di funzione, in modo che finiscano per essere chiusure.
Una lambda è una funzione anonima, definita in modo dinamico . Non puoi farlo in C ... per quanto riguarda le chiusure (o la convinzione delle due), il tipico esempio di lisp sarebbe simile a:
(defun get-counter (n-start +-number)
"Returns a function that returns a number incremented
by +-number every time it is called"
(lambda () (setf n-start (+ +-number n-start))))
In termini di C, si potrebbe dire che l'ambiente lessicale (lo stack) di get-counter viene catturato dalla funzione anonima e modificato internamente come mostra il seguente esempio:
[1]> (defun get-counter (n-start +-number)
"Returns a function that returns a number incremented
by +-number every time it is called"
(lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]>
Le chiusure implicano che alcune variabili dal punto di definizione della funzione sono legate insieme alla logica della funzione, come essere in grado di dichiarare al volo un mini-oggetto.
Un importante problema con C e le chiusure è che le variabili allocate nello stack verranno distrutte all'uscita dall'ambito corrente, indipendentemente dal fatto che una chiusura le indichi. Ciò porterebbe al tipo di bug che le persone ottengono quando restituiscono incautamente puntatori a variabili locali. Le chiusure implicano fondamentalmente che tutte le variabili rilevanti sono o contate nuovamente o oggetti raccolti in un mucchio.
Non mi sento a mio agio nel paragonare lambda alla chiusura perché non sono sicuro che le lambda in tutte le lingue siano chiusure, a volte penso che le lambda siano state appena definite localmente funzioni anonime senza l'associazione di variabili (Python pre 2.1?).
In GCC è possibile simulare le funzioni lambda usando la seguente macro:
#define lambda(l_ret_type, l_arguments, l_body) \
({ \
l_ret_type l_anonymous_functions_name l_arguments \
l_body \
&l_anonymous_functions_name; \
})
Esempio da fonte :
qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
lambda (int, (const void *a, const void *b),
{
dump ();
printf ("Comparison %d: %d and %d\n",
++ comparison, *(const int *) a, *(const int *) b);
return *(const int *) a - *(const int *) b;
}));
L'utilizzo di questa tecnica ovviamente elimina la possibilità che l'applicazione funzioni con altri compilatori ed è apparentemente "indefinita". comportamento così YMMV.
La chiusura cattura le variabili libere in un ambiente . L'ambiente esisterà ancora, anche se il codice circostante potrebbe non essere più attivo.
Un esempio in Common Lisp, in cui MAKE-ADDER restituisce una nuova chiusura.
CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER
CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL
Utilizzando la funzione sopra:
CL-USER 55 > (let ((adder1 (make-adder 0 10))
(adder2 (make-adder 17 20)))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder1))
(print (funcall adder2))
(print (funcall adder2))
(print (funcall adder2))
(print (funcall adder1))
(print (funcall adder1))
(describe adder1)
(describe adder2)
(values))
10
20
30
40
37
57
77
50
60
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment #(77 20)
Nota che la funzione DESCRIBE mostra che gli oggetti funzione per entrambe le chiusure sono uguali, ma ambiente è diverso.
Common Lisp rende sia le chiusure che gli oggetti funzione puri (quelli senza ambiente) sia funzioni e si possono chiamare entrambi allo stesso modo, qui usando FUNCALL .
La principale differenza deriva dalla mancanza di scoping lessicale in C.
Un puntatore a funzione è proprio questo, un puntatore a un blocco di codice. Qualsiasi variabile non stack a cui fa riferimento è globale, statica o simile.
Una chiusura, OTOH, ha il suo stato sotto forma di "variabili esterne", o "valori positivi". possono essere privati ??o condivisi come vuoi, usando l'ambito lessicale. Puoi creare molte chiusure con lo stesso codice funzione, ma istanze di variabili diverse.
Alcune chiusure possono condividere alcune variabili, e quindi può essere l'interfaccia di un oggetto (nel senso di OOP). per renderlo in C devi associare una struttura a una tabella di puntatori a funzione (è quello che fa C ++, con una classe vtable).
in breve, una chiusura è un puntatore a funzione PIÙ un certo stato. è un costrutto di livello superiore
La maggior parte delle risposte indica che le chiusure richiedono puntatori a funzioni, possibilmente a funzioni anonime, ma come Mark ha scritto possono esistere chiusure con funzioni denominate. Ecco un esempio in Perl:
{
my $count;
sub increment { return $count++ }
}
La chiusura è l'ambiente che definisce la variabile $ count . È disponibile solo per la subroutine increment e persiste tra le chiamate.
In C un puntatore a funzione è un puntatore che invocherà una funzione quando lo si fa una deduzione, una chiusura è un valore che contiene la logica di una funzione e l'ambiente (variabili e valori a cui sono legati) e un lambda di solito si riferisce a un valore che in realtà è una funzione senza nome. In C una funzione non è un valore di prima classe, quindi non può essere passata, quindi devi passare un puntatore ad essa, tuttavia nei linguaggi funzionali (come Scheme) puoi passare le funzioni nello stesso modo in cui passi qualsiasi altro valore
