Che cos'è "Lambda Lifting"?

Question

Mi sono imbattuto in questo mentre attraverso il sorgente del compilatore Erlang.

Non lo capisco davvero. (vai a capire;)), considerando che ho appena realizzato che c'è una cosa del genere 5 minuti fa).

Perdonami per aver chiesto prima senza prima cercare di capire le ragioni della sua esistenza.

C'è un wikipedia article a riguardo, ma è piuttosto criptico.

Answer 1

Il sollevamento lambda viene utilizzato per trasformare una chiusura in una funzione pura. Passando argomenti aggiuntivi alla funzione, riduci il numero delle sue variabili libere. Mentre si "solleva" il lambda in ambiti sempre più alti, si aggiungono argomenti per accogliere le variabili locali dichiarate in quell'ambito (che sarebbero altrimenti variabili libere). Una volta che il lambda non ha variabili libere, è una pura funzione di "livello superiore".

Naturalmente è possibile farlo solo se si conoscono tutti i siti di chiamata di lambda; in altre parole, solo se il lambda non fugge.

Il vantaggio di un ottimizzatore del compilatore è che le chiusure (ambienti di funzioni) possono essere eliminate. Ciò potrebbe rendere possibile passare gli argomenti nei registri anziché impilarli (o heap) allocandoli come variabili libere.

Answer 2

lambda lifting elimina sostanzialmente le variabili e le inserisce in pure funzioni, semplificando l'esecuzione.

Answer 3

Il sollevamento di Lambda è una tecnica per "elevare" lambda ad un livello superiore (principalmente al livello superiore).

Doug Currie descrive il motivo per cui vorresti farlo.

Ecco qualche esempio di codice (in JavaScript) di come si possa fare ciò manualmente:

function addFive(nr) 
{ 
    var x = 5; 
    function addX(y) 
    { 
    return x + y; 
    } 

    return addX(nr); 
} 

Ora, se non si desidera che questa funzione addX all'interno della definizione di addFive si potrebbe `ascensore' al livello superiore in questo modo:

function addX(y) 
{ 
    return x + y; 
} 

function addFive(nr) 
{ 
    var x = 5; 

    return addX(nr); 
} 

Tuttavia, questo non funziona, dal momento che la variabile x non è più disponibile nel contesto della funzione addX. Il modo per risolvere questo problema è quello di aggiungere un parametro in più formale per la funzione:

function addX(y, x) 
{ 
    return x + y; 
} 

function addFive(nr) 
{ 
    var x = 5; 

    return addX(nr, x); 
} 

---

Aggiunta: Ecco un esempio molto artificiosa di un lambda `fuga'. Dove non sarai in grado di fare la lambda sollevando così facilmente come ho descritto.

function getAddFiveFunc() 
{ 
    var x = 5; 
    function addX(y) 
    { 
    return x + y; 
    } 

    return addX; 
} 

Ora, se qualcuno chiama la funzione getAddFiveFunc, che riceveranno una funzione indietro. Questa funzione potrebbe essere utilizzata in tutti i tipi di posti, ora, se si desidera sollevare la funzione addX, sarà necessario aggiornare tutti quei callites.

Answer 4

Avvertenza: la mia risposta descrive in realtà variabili acquisite diverse dal sollevamento di lambda. Non letto la domanda (è necessario dormire). Ma ho passato un po 'di tempo a scriverlo, quindi sono dispiaciuto di cancellarlo. Lasciato come una comunità WIKI.

Il sollevamento di Lambda, spesso definito come chiusura, è un modo per consentire l'accesso di variabili in ambito all'interno di un'espressione lambda annidata.

È difficile entrare nei dettagli nitidi delle chiusure senza scegliere una lingua particolare. Uno degli effetti collaterali del sollevamento di lambda, in ogni lingua, è che tende ad estendere la durata di una variabile da un ambito locale, di breve durata, a un ambito molto più lungo. Di solito ciò avviene nella forma del trasferimento di una variabile dallo stack all'heap all'interno del compilatore. Questa è un'azione molto specifica del linguaggio e quindi produce implementazioni molto diverse basate sulla lingua.

Mi concentrerò su C# poiché è probabilmente la lingua più comune ai lettori di stack overflow. Iniziamo con il seguente codice.

public Func<int> GetAFunction() { 
    var x = 42; 
    Func<int> lambda1 =() => x; 
    Func<int> lambda2 =() => 42; 
    ... 
    return lambda1; 
} 

In questo esempio sono state create 2 espressioni lambda. In entrambi i casi è assegnato a un'istanza delegata di tipo Func. Tutti i delegati in .Net richiedono che una vera funzione li stia sostenendo da qualche parte. Così sotto la cappa, tutte le espressioni lambda/funzioni anonime in C# vengono tradotte in una definizione di metodo.

Generare una funzione per lambda2 è piuttosto semplice. È una funzione isolata che restituisce solo un valore costante.

public static int RealLambda2() { 
    return 42; 
} 

Generare lambda1 è un po 'più difficile. Una definizione letterale sarebbe simile al seguente

public static int RealLambda1() { 
    return x; 
} 

Questo ovviamente non verrà compilato perché x non è accessibile. Per fare in modo che funzioni, il compilatore C# deve lift la variabile x in una chiusura. Si può quindi restituire un puntatore a una funzione all'interno della chiusura di soddisfare l'espressione delegato

class Closure1 { 
    int x; 
    public int RealLambda1() { 
    return x; 
    } 
} 

Questo è un esempio molto semplice ma dovrebbero auspicabilmente dettaglio tecnica di sollevamento. Il diavolo è sfortunatamente nei dettagli e diventa molto più complesso con lo scenario.