Problema di Funarg - Funarg problem

In informatica , il problema funarg ( problema dell'argomento della funzione) si riferisce alla difficoltà nell'implementare funzioni di prima classe ( funzioni come oggetti di prima classe ) nelle implementazioni del linguaggio di programmazione in modo da utilizzare l' allocazione di memoria basata su stack delle funzioni.

La difficoltà sorge solo se il corpo di una funzione nidificata si riferisce direttamente (cioè non per passaggio di argomenti) a identificatori definiti nell'ambiente in cui la funzione è definita, ma non nell'ambiente della chiamata di funzione. Una risoluzione standard è quella di vietare tali riferimenti o di creare chiusure .

Esistono due versioni leggermente diverse del problema funarg. Il problema del funarg verso l' alto nasce dalla restituzione (o altrimenti dalla trasmissione "verso l'alto") di una funzione da una chiamata di funzione. Il problema di funarg verso il basso nasce dal passaggio di una funzione come parametro a un'altra chiamata di funzione.

Problema funarg verso l'alto

Quando una funzione ne chiama un'altra durante l'esecuzione di un programma tipico, lo stato locale del chiamante (inclusi i parametri e le variabili locali ) deve essere preservato affinché l'esecuzione proceda dopo il ritorno del chiamato. Nella maggior parte dei programmi compilati, questo stato locale è memorizzato nello stack di chiamate in una struttura dati chiamata stack frame o record di attivazione . Questo stack frame viene inviato o allocato come preludio alla chiamata di un'altra funzione e viene estratto o deallocato quando l'altra funzione ritorna alla funzione che ha eseguito la chiamata. Il problema di funarg verso l'alto sorge quando la funzione chiamante si riferisce allo stato della funzione chiamata/uscita dopo che quella funzione è tornata. Pertanto, lo stack frame contenente le variabili di stato della funzione chiamata non deve essere deallocato quando la funzione ritorna, violando il paradigma della chiamata di funzione basata sullo stack .

Una soluzione al problema del funarg verso l'alto consiste nell'allocare semplicemente tutti i record di attivazione dall'heap anziché dallo stack e fare affidamento su una qualche forma di raccolta dei rifiuti o conteggio dei riferimenti per deallocarli quando non sono più necessari. Storicamente, la gestione dei record di attivazione sull'heap è stata percepita come meno efficiente rispetto allo stack (sebbene ciò sia parzialmente contraddetto) ed è stato percepito come una complessità di implementazione significativa. La maggior parte delle funzioni nei programmi tipici (meno per i programmi nei linguaggi di programmazione funzionale ) non creano funarg verso l'alto, aggiungendo preoccupazioni sul potenziale sovraccarico associato alla loro implementazione. Inoltre, questo approccio è davvero difficile nei linguaggi che non supportano la garbage collection.

Alcuni compilatori orientati all'efficienza impiegano un approccio ibrido in cui i record di attivazione per una funzione sono allocati dallo stack se il compilatore è in grado di dedurre, attraverso l' analisi statica del programma , che la funzione non crea funarg verso l'alto. In caso contrario, i record di attivazione vengono allocati dall'heap.

Un'altra soluzione consiste nel copiare semplicemente il valore delle variabili nella chiusura al momento della creazione della chiusura. Questo provocherà un comportamento diverso nel caso di variabili mutabili, perché lo stato non sarà più condiviso tra le chiusure. Ma se è noto che le variabili sono costanti, allora questo approccio sarà equivalente. I linguaggi ML adottano questo approccio, poiché le variabili in quei linguaggi sono legate a valori, ovvero le variabili non possono essere modificate. Java adotta questo approccio anche rispetto alle classi anonime, in quanto consente solo di fare riferimento a variabili nell'ambito di inclusione che sono final(cioè costanti).

Alcuni linguaggi consentono al programmatore di scegliere esplicitamente tra i due comportamenti. Le funzioni anonime di PHP 5.3 richiedono che si specifichi quali variabili includere nella chiusura usando la use ()clausola; se la variabile è elencata per riferimento, include un riferimento alla variabile originale; in caso contrario, passa il valore. Nelle funzioni anonime Blocks di Apple , le variabili locali catturate vengono catturate per impostazione predefinita per valore; se si vuole condividere lo stato tra le chiusure o tra la chiusura e lo scope esterno, la variabile deve essere dichiarata con il __blockmodificatore, nel qual caso quella variabile viene allocata sull'heap.

Esempio

Il seguente pseudocodice simile ad Haskell definisce la composizione della funzione : 

compose f g = λx → f (g x)

λè l'operatore per costruire una nuova funzione, che in questo caso ha un argomento, x, e restituisce il risultato della prima applicazione ga x, quindi dell'applicazione fa quella. Questa funzione λ trasporta le funzioni fe g(o punta ad esse) come stato interno.

Il problema in questo caso esiste se la funzione di composizione alloca le variabili dei parametri fe gsullo stack. Quando viene composerestituito, lo stack frame contenente fe gviene scartato. Quando la funzione interna λxtenta di accedere g, accederà a un'area di memoria scartata.

Problema funarg verso il basso

Un funarg verso il basso può anche riferirsi allo stato di una funzione quando quella funzione non è effettivamente in esecuzione. Tuttavia, poiché, per definizione, l'esistenza di un funarg verso il basso è contenuta nell'esecuzione della funzione che lo crea, lo stack frame per la funzione di solito può ancora essere memorizzato nello stack. Tuttavia, l'esistenza di funarg verso il basso implica una struttura ad albero di chiusure e stack frame che può complicare il ragionamento umano e macchina sullo stato del programma.

Il problema del funarg verso il basso complica la compilazione efficiente di chiamate in coda e codice scritto in stile continuation-passing . In questi casi speciali, l'intento del programmatore è (di solito) che la funzione venga eseguita in uno spazio di stack limitato, quindi il comportamento "più veloce" potrebbe effettivamente essere indesiderabile.

implicazioni pratiche

Storicamente, il problema del funarg verso l'alto si è dimostrato il più difficile. Ad esempio, il linguaggio di programmazione Pascal consente di passare le funzioni come argomenti ma non di restituirle come risultati; quindi sono necessarie implementazioni di Pascal per affrontare il problema del funarg verso il basso ma non quello verso l'alto. I linguaggi di programmazione Modula-2 e Oberon (discendenti di Pascal) consentono funzioni sia come parametri che come valori di ritorno, ma la funzione assegnata potrebbe non essere una funzione annidata. Il linguaggio di programmazione C evita storicamente la principale difficoltà del problema funarg non consentendo l'annidamento delle definizioni di funzione; poiché l'ambiente di ogni funzione è lo stesso, contenente solo le variabili e le funzioni globali allocate staticamente, un puntatore al codice di una funzione descrive la funzione completamente. Apple ha proposto e implementato una sintassi di chiusura per C che risolve il problema del funarg verso l'alto spostando dinamicamente le chiusure dallo stack all'heap, se necessario. Il linguaggio di programmazione Java si occupa di questo richiedendo che il contesto utilizzato dalle funzioni nidificate nelle classi interne e locali anonime sia dichiarato final e il contesto utilizzato dalle espressioni lambda sia effettivamente definitivo. C# e D hanno lambda (chiusure) che incapsulano un puntatore a funzione e le variabili correlate.

Nei linguaggi funzionali , le funzioni sono valori di prima classe che possono essere passati ovunque. Pertanto, le implementazioni di Scheme o Standard ML devono affrontare sia i problemi di funarg verso l'alto che verso il basso. Ciò si ottiene solitamente rappresentando i valori delle funzioni come chiusure allocate nell'heap , come descritto in precedenza. Il compilatore OCaml utilizza una tecnica ibrida (basata sull'analisi del programma ) per massimizzare l'efficienza.

Guarda anche

Riferimenti

link esterno