Funarg probleem - Funarg problem

In de informatica verwijst het funarg-probleem (functieargumentprobleem) naar de moeilijkheid bij het implementeren van eersteklas functies ( functies als eersteklas objecten ) in programmeertaalimplementaties om op stapels gebaseerde geheugentoewijzing van de functies te gebruiken.

De moeilijkheid doet zich alleen voor als de hoofdtekst van een geneste functie direct (dwz niet door het doorgeven van argumenten) verwijst naar identifiers die zijn gedefinieerd in de omgeving waarin de functie is gedefinieerd, maar niet in de omgeving van de functieaanroep. Een standaardoplossing is om dergelijke verwijzingen te verbieden of om sluitingen te creëren .

Er zijn twee subtiel verschillende versies van het funarg-probleem. Het opwaartse funarg-probleem ontstaat door het retourneren (of anderszins "naar boven") verzenden van een functie uit een functieaanroep. Het neerwaartse funarg-probleem ontstaat door een functie als parameter door te geven aan een andere functieaanroep.

Opwaarts funarg probleem

Wanneer de ene functie een andere aanroept tijdens de uitvoering van een typisch programma, moet de lokale status van de aanroeper (inclusief parameters en lokale variabelen ) worden bewaard om de uitvoering door te laten gaan nadat de aangeroepene terugkeert. In de meeste gecompileerde programma's wordt deze lokale status opgeslagen op de aanroepstack in een gegevensstructuur die een stapelframe of activeringsrecord wordt genoemd . Dit stapelframe wordt gepusht of toegewezen als prelude voor het aanroepen van een andere functie, en wordt gepopt of ongedaan gemaakt wanneer de andere functie terugkeert naar de functie die de aanroep heeft gedaan. Het opwaartse funarg-probleem doet zich voor wanneer de aanroepende functie verwijst naar de status van de aangeroepen/verlaten functie nadat die functie is teruggekeerd. Daarom mag het stapelframe dat de statusvariabelen van de aangeroepen functie bevat, niet worden verwijderd wanneer de functie terugkeert, wat in strijd is met het op stapels gebaseerde functieaanroepparadigma .

Een oplossing voor het opwaartse funarg-probleem is om eenvoudig alle activeringsrecords van de heap in plaats van de stapel toe te wijzen en te vertrouwen op een of andere vorm van garbagecollection of referentietelling om ze ongedaan te maken wanneer ze niet langer nodig zijn. Het beheren van activeringsrecords op de heap werd in het verleden als minder efficiënt beschouwd dan op de stapel (hoewel dit gedeeltelijk wordt tegengesproken) en werd gezien als een aanzienlijke implementatiecomplexiteit. De meeste functies in typische programma's (in mindere mate voor programma's in functionele programmeertalen ) creëren geen opwaartse funargs, wat de bezorgdheid over mogelijke overhead in verband met hun implementatie vergroot. Bovendien is deze aanpak echt moeilijk in talen die het verzamelen van afval niet ondersteunen.

Sommige op efficiëntie gerichte compilers gebruiken een hybride benadering waarbij de activeringsrecords voor een functie uit de stapel worden toegewezen als de compiler door middel van statische programma-analyse kan afleiden dat de functie geen opwaartse funargs creëert. Anders worden de activeringsrecords toegewezen vanaf de heap.

Een andere oplossing is om simpelweg de waarde van de variabelen in de sluiting te kopiëren op het moment dat de sluiting wordt gemaakt. Dit zal een ander gedrag veroorzaken in het geval van veranderlijke variabelen, omdat de toestand niet langer wordt gedeeld tussen sluitingen. Maar als bekend is dat de variabelen constant zijn, is deze benadering equivalent. De ML- talen hanteren deze benadering, aangezien variabelen in die talen gebonden zijn aan waarden, dwz variabelen kunnen niet worden gewijzigd. Java volgt deze benadering ook met betrekking tot anonieme klassen, in die zin dat het alleen mogelijk is om te verwijzen naar variabelen in de omsluitende scope die final(dat wil zeggen constant) zijn.

In sommige talen kan de programmeur expliciet kiezen tussen de twee gedragingen. De anonieme functies van PHP 5.3 vereisen dat je specificeert welke variabelen in de afsluiting moeten worden opgenomen met behulp van de use ()clausule; als de variabele met verwijzing wordt vermeld, bevat deze een verwijzing naar de oorspronkelijke variabele; anders wordt de waarde doorgegeven. In de anonieme functies van Blocks van Apple worden vastgelegde lokale variabelen standaard vastgelegd op waarde; als men de status wil delen tussen sluitingen of tussen de sluiting en de externe scope, moet de variabele worden gedeclareerd met de __blockmodifier, in welk geval die variabele op de heap wordt toegewezen.

Voorbeeld

De volgende Haskell- achtige pseudocode definieert functiesamenstelling : 

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

λis de operator voor het construeren van een nieuwe functie, die in dit geval één argument heeft, x, en het resultaat geeft van eerst toepassen gop x, dan daarop toepassen f. Deze λ-functie draagt ​​de functies fen g(of verwijzingen ernaar) als interne toestand.

Het probleem bestaat in dit geval als de compose-functie de parametervariabelen fen gop de stapel toewijst . Wanneer composeterugkomt, wordt het stapelframe met fen gweggegooid. Wanneer de interne functie λxprobeert toegang te krijgen tot g, zal deze toegang krijgen tot een verwijderd geheugengebied.

Neerwaartse funarg probleem

Een neerwaartse funarg kan ook verwijzen naar de status van een functie wanneer die functie niet daadwerkelijk wordt uitgevoerd. Echter, omdat per definitie het bestaan ​​van een neerwaartse funarg is vervat in de uitvoering van de functie die deze creëert, kan het stapelframe voor de functie meestal nog steeds op de stapel worden opgeslagen. Desalniettemin impliceert het bestaan ​​van neerwaartse funargs een boomstructuur van sluitingen en stapelframes die menselijke en machinale redeneringen over de programmastatus kunnen compliceren.

Het neerwaartse funarg-probleem bemoeilijkt de efficiënte compilatie van staartaanroepen en code geschreven in continuation-passing-stijl . In deze speciale gevallen is de bedoeling van de programmeur (meestal) dat de functie in beperkte stackruimte draait, dus het "snellere" gedrag kan eigenlijk ongewenst zijn.

Praktische implicaties

Historisch gezien is het opwaartse funarg-probleem het moeilijkst gebleken. De programmeertaal Pascal staat bijvoorbeeld toe dat functies als argumenten worden doorgegeven, maar niet als resultaten worden geretourneerd; dus implementaties van Pascal zijn nodig om het neerwaartse funarg-probleem aan te pakken, maar niet het opwaartse. De programmeertalen Modula-2 en Oberon (afstammelingen van Pascal) staan ​​functies toe als parameters en als retourwaarden, maar de toegewezen functie is mogelijk geen geneste functie. De programmeertaal C vermijdt historisch gezien de grootste moeilijkheid van het funarg-probleem door niet toe te staan ​​dat functiedefinities worden genest; omdat de omgeving van elke functie hetzelfde is en alleen de statisch toegewezen globale variabelen en functies bevat, beschrijft een verwijzing naar de code van een functie de functie volledig. Apple heeft een sluitingssyntaxis voor C voorgesteld en geïmplementeerd die het opwaartse funarg-probleem oplost door sluitingen dynamisch van de stapel naar de heap te verplaatsen als dat nodig is. De Java-programmeertaal gaat ermee om door te eisen dat de context die wordt gebruikt door geneste functies in anonieme interne en lokale klassen definitief wordt verklaard en dat de context die door lambda-expressies wordt gebruikt, effectief definitief is. C# en D hebben lambda's (sluitingen) die een functieaanwijzer en gerelateerde variabelen inkapselen.

In functionele talen zijn functies eersteklas waarden die overal kunnen worden doorgegeven. Implementaties van Scheme of Standard ML moeten dus zowel de opwaartse als neerwaartse funarg-problemen aanpakken. Dit wordt gewoonlijk bereikt door functiewaarden weer te geven als aan heap toegewezen sluitingen, zoals eerder beschreven. De OCaml- compiler maakt gebruik van een hybride techniek (gebaseerd op programma-analyse ) om de efficiëntie te maximaliseren.

Zie ook

Referenties

Externe links