Problema Funarg - Funarg problem

În informatică , problema funarg ( problema argumentului funcției) se referă la dificultatea de a implementa funcții de primă clasă ( funcții ca obiecte de primă clasă ) în implementările limbajului de programare, astfel încât să se utilizeze alocarea de memorie bazată pe stivă a funcțiilor.

Dificultatea apare numai dacă corpul unei funcții imbricate se referă direct (adică nu prin trecerea argumentelor) la identificatorii definiți în mediul în care funcția este definită, dar nu în mediul apelului de funcție. O rezoluție standard este fie să interzică astfel de referințe, fie să creeze închideri .

Există două versiuni subtil diferite ale problemei funarg. Problema funarg ascendentă apare din returnarea (sau transmiterea în alt mod) a unei funcții dintr-un apel de funcție. Problema funarg descendentă apare din trecerea unei funcții ca parametru către o altă funcție de apel.

Problema funarg în sus

Când o funcție sună pe alta în timpul execuției unui program tipic, starea locală a apelantului (inclusiv parametrii și variabilele locale ) trebuie păstrată pentru ca executarea să poată continua după revenirea apelantului. În majoritatea programelor compilate, această stare locală este stocată în stiva de apeluri într-o structură de date numită cadru de stivă sau înregistrare de activare . Acest cadru de stivă este împins, sau alocat, ca preludiu la apelarea unei alte funcții, și este popped, sau dealocate, atunci când cealaltă funcție revine la funcția care a efectuat apelul. Problema funarg în sus apare atunci când funcția apelantă se referă la starea funcției apelate / ieșite după revenirea acelei funcții. Prin urmare, cadrul stivei care conține variabilele de stare ale funcției apelate nu trebuie să fie repartizat la revenirea funcției, încălcând paradigma apelului funcției bazate pe stivă .

O soluție la problema funarg în sus este să alocați pur și simplu toate înregistrările de activare din grămadă în loc de stivă și să vă bazați pe o formă de colectare a gunoiului sau numărarea referințelor pentru a le deloca atunci când nu mai sunt necesare. Gestionarea înregistrărilor de activare pe heap a fost, în mod istoric, percepută ca fiind mai puțin eficientă decât pe stack (deși acest lucru este parțial contrazis) și a fost percepută ca impunând o complexitate semnificativă de implementare. Majoritatea funcțiilor din programele tipice (mai puțin pentru programele în limbaje de programare funcționale ) nu creează funarg-uri ascendente, adăugând îngrijorări cu privire la potențialul cost suplimentar asociat cu implementarea lor. În plus, această abordare este cu adevărat dificilă în limbile care nu acceptă colectarea gunoiului.

Unele compilatoare orientate spre eficiență utilizează o abordare hibridă în care înregistrările de activare pentru o funcție sunt alocate din stivă dacă compilatorul este capabil să deducă, prin analiza statică a programului , că funcția nu creează funcții ascendente. În caz contrar, înregistrările de activare sunt alocate din heap.

O altă soluție este să copiați pur și simplu valoarea variabilelor în închidere în momentul creării închiderii. Acest lucru va provoca un comportament diferit în cazul variabilelor modificabile, deoarece starea nu va mai fi împărțită între închideri. Dar dacă se știe că variabilele sunt constante, atunci această abordare va fi echivalentă. În ML limbi iau această abordare, deoarece variabile în aceste limbi sunt legate la valorile adică variabile nu pot fi schimbate. Java ia, de asemenea, această abordare în ceea ce privește clasele anonime, în sensul că permite doar să se facă referire la variabilele din domeniul de conținut care sunt final(adică constante).

Unele limbi permit programatorului să aleagă în mod explicit între cele două comportamente. Funcțiile anonime ale PHP 5.3 necesită una pentru a specifica ce variabile să includă în închidere folosind use ()clauza; dacă variabila este listată prin referință, aceasta include o referință la variabila originală; în caz contrar, trece valoarea. În funcțiile anonime ale blocurilor Apple , variabilele locale capturate sunt implicit capturate de valoare; dacă se dorește partajarea stării între închideri sau între închidere și domeniul de aplicare exterior, variabila trebuie declarată cu __blockmodificatorul, caz în care variabila respectivă este alocată pe heap.

Exemplu

Următorul pseudocod de tip Haskell definește compoziția funcției : 

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

λeste operatorul pentru construirea unei noi funcții, care, în acest caz, are un argument x, și returnează rezultatul aplicării mai întâi gla x, apoi aplicării fla aceasta. Această funcție λ poartă funcțiile fși g(sau indicii către ele) ca stare internă.

Problema în acest caz există dacă funcția compune alocă variabilele parametrilor fși gpe stivă. Când composese întoarce, cadrul stivei conține fși geste eliminat. Când funcția internă λxîncearcă să acceseze g, va accesa o zonă de memorie abandonată.

Problema funarg în jos

Un funarg descendent se poate referi și la starea unei funcții atunci când acea funcție nu se execută de fapt. Cu toate acestea, deoarece, prin definiție, existența unui funarg descendent este conținută în executarea funcției care îl creează, cadrul stivei pentru funcție poate fi de obicei stocat în stivă. Cu toate acestea, existența funarg-urilor descendente implică o structură în arbore de închideri și cadre de stivă care poate complica raționamentul uman și al mașinii despre starea programului.

Problema funarg în jos complică compilarea eficientă a apelurilor de cod și a codului scrise în stilul de continuare-trecere . În aceste cazuri speciale, intenția programatorului este (de obicei) ca funcția să ruleze într-un spațiu limitat de stivă, astfel încât comportamentul „mai rapid” poate fi de fapt nedorit.

implicatii practice

Din punct de vedere istoric, problema funarg ascendentă sa dovedit a fi cu atât mai dificilă. De exemplu, limbajul de programare Pascal permite funcțiilor să fie transmise ca argumente, dar nu returnate ca rezultate; astfel, implementările lui Pascal sunt necesare pentru a aborda problema funarg descendentă, dar nu și cea ascendentă. Cele Modula-2 și Oberon limbaje de programare (Pascal) descendenților permit funcții atât ca parametri și valori de retur, dar funcția atribuită nu poate fi o funcție imbricată. Limbajul de programare C evită punct de vedere istoric principala dificultate a problemei funarg nu permite definiții de funcții să fie imbricate; deoarece mediul fiecărei funcții este același, conținând doar variabilele și funcțiile globale alocate static, un indicator către codul unei funcții descrie complet funcția. Apple a propus și a implementat o sintaxă de închidere pentru C care rezolvă problema funarg în sus prin deplasarea dinamică a închiderilor din stivă în grămadă, după cum este necesar. În limbajul de programare Java se ocupă cu ea prin solicitarea context , este utilizat de către funcțiile imbricate în clasele interne și locale anonime să fie declarate definitive , și contextul folosit de expresii lambda fi efectiv finală. C # și D au lambdas (închideri) care încapsulează un indicator de funcție și variabile conexe.

În limbajele funcționale , funcțiile sunt valori de primă clasă care pot fi transmise oriunde. Astfel, implementările Scheme sau Standard ML trebuie să abordeze atât problemele funarg în sus, cât și în jos. Acest lucru se realizează, de obicei, prin reprezentarea valorilor funcției ca închideri alocate heap , așa cum a fost descris anterior. OCaml compilator utilizează o tehnică hibrid (bazat pe analiza de program ) pentru a maximiza eficiența.

Vezi si

Referințe

linkuri externe