Funarg problem

Inom datavetenskap hänvisar funarg -problemet (funktionsargumentproblem) till svårigheten att implementera förstklassiga funktioner ( fungerar som förstaklassobjekt) i programmeringsspråksimplementeringar för att använda stackbaserad minnesallokering av funktionerna.

Svårigheten uppstår endast om kroppen i en kapslad funktion hänvisar direkt (dvs inte genom att argument skickas) till identifierare definierade i miljön där funktionen är definierad, men inte i miljön för funktionsanropet. En standardlösning är antingen att förbjuda sådana referenser eller att skapa nedläggningar .

Det finns två subtilt olika versioner av funarg-problemet. Funarg- problemet uppåt uppstår genom att returnera (eller på annat sätt sända "uppåt") en funktion från ett funktionsanrop. Det nedåtgående funarg-problemet uppstår när en funktion överförs som en parameter till ett annat funktionsanrop.

Uppåt funarg problem

När en funktion anropar en annan under ett typiskt programs exekvering, måste anroparens lokala tillstånd (inklusive parametrar och lokala variabler ) bevaras för att exekvering ska kunna fortsätta efter att den anropade återvänder. I de flesta kompilerade program lagras detta lokala tillstånd i samtalsstacken i en datastruktur som kallas en stackram eller aktiveringspost . Den här stackramen pushas, ​​eller allokeras, som förspel till att anropa en annan funktion, och poppas, eller avallokeras, när den andra funktionen återgår till funktionen som gjorde anropet. Det uppåtgående funarg-problemet uppstår när den anropande funktionen hänvisar till den anropade/avslutade funktionens tillstånd efter att den funktionen har återvänt. Därför får stackramen som innehåller den anropade funktionens tillståndsvariabler inte avallokeras när funktionen returnerar, vilket bryter mot det stackbaserade funktionsanropsparadigmet .

En lösning på det uppåtgående funarg-problemet är att helt enkelt allokera alla aktiveringsposter från högen istället för stacken och förlita sig på någon form av sophämtning eller referensräkning för att deallokera dem när de inte längre behövs. Hantering av aktiveringsposter på högen har historiskt sett uppfattats som mindre effektiv än på stacken (även om detta delvis motsägs) och har uppfattats innebära betydande implementeringskomplexitet. De flesta funktioner i typiska program (mindre så för program i funktionella programmeringsspråk ) skapar inte funargs uppåt, vilket ökar farhågor om potentiella omkostnader i samband med implementeringen av dem. Dessutom är detta tillvägagångssätt verkligen svårt på språk som inte stöder sophämtning.

Vissa effektivitetsinriktade kompilatorer använder en hybrid metod där aktiveringsposterna för en funktion allokeras från stacken om kompilatorn kan dra slutsatsen, genom statisk programanalys , att funktionen inte skapar några uppåtgående funargs. I annat fall tilldelas aktiveringsposterna från högen.

En annan lösning är att helt enkelt kopiera värdet på variablerna till stängningen vid den tidpunkt då stängningen skapas. Detta kommer att orsaka ett annat beteende i fallet med föränderliga variabler, eftersom tillståndet inte längre kommer att delas mellan stängningar. Men om det är känt att variablerna är konstanta, kommer detta tillvägagångssätt att vara ekvivalent. ML - språken använder detta tillvägagångssätt, eftersom variabler i dessa språk är bundna till värden – dvs variabler kan inte ändras. Java tar också detta tillvägagångssätt med avseende på anonyma klasser, genom att det bara tillåter en att referera till variabler i det omslutande omfånget som är slutgiltiga (dvs konstanta).

Vissa språk tillåter programmeraren att uttryckligen välja mellan de två beteendena. PHP 5.3:s anonyma funktioner kräver att man specificerar vilka variabler som ska inkluderas i stängningen med hjälp av use () -satsen; om variabeln är listad med referens, innehåller den en referens till den ursprungliga variabeln; annars passerar den värdet. I Apples blockblocksfunktioner fångas infångade lokala variabler som standard av värde; om man vill dela tillståndet mellan closures eller mellan closure och outside scope, måste variabeln deklareras med __block modifieraren, i vilket fall den variabeln allokeras på heapen.

Exempel

Följande Haskell -liknande pseudokod definierar funktionssammansättning : 

komponera fg = λx → f (gx)

λ är operatorn för att konstruera en ny funktion, som i det här fallet har ett argument, x , och returnerar resultatet av att först applicera g på x och sedan tillämpa f på det. Denna λ-funktion bär funktionerna f och g (eller pekare till dem) som internt tillstånd.

Problemet i det här fallet finns om funktionen compose allokerar parametervariablerna f och g på stacken. När compose returneras kasseras stackramen som innehåller f och g . När den interna funktionen λx försöker komma åt g , kommer den åt ett kasserat minnesområde.

Funarg problem nedåt

En nedåtgående funarg kan också hänvisa till en funktions tillstånd när den funktionen faktiskt inte körs. Men eftersom, per definition, förekomsten av en nedåtgående funarg ingår i exekveringen av funktionen som skapar den, kan stackramen för funktionen vanligtvis fortfarande lagras i stacken. Icke desto mindre innebär förekomsten av nedåtgående funargs en trädstruktur av stängningar och stackramar som kan komplicera mänskliga och maskinella resonemang om programtillståndet.

Funarg-problemet nedåt komplicerar den effektiva sammanställningen av tail calls och kod skriven i fortsättningspasserande stil . I dessa speciella fall är programmerarens avsikt (vanligtvis) att funktionen körs i begränsat stackutrymme, så det "snabbare" beteendet kan faktiskt vara oönskat.

Praktiska konsekvenser

Historiskt sett har funargproblemet uppåt visat sig vara det svårare. Till exempel programmeringsspråket Pascal att funktioner skickas som argument men inte returneras som resultat; sålunda krävs implementeringar av Pascal för att ta itu med funarg-problemet nedåt men inte det uppåtgående. Modula -2 och Oberon (ättlingar till Pascal) tillåter funktioner både som parametrar och returvärden, men den tilldelade funktionen kanske inte är en kapslad funktion. Programmeringsspråket C undviker historiskt den största svårigheten med funarg-problemet genom att inte tillåta funktionsdefinitioner att kapslas; eftersom miljön för varje funktion är densamma och bara innehåller de statiskt allokerade globala variablerna och funktionerna, beskriver en pekare till en funktions kod funktionen fullständigt. Apple har föreslagit och implementerat en stängningssyntax för C som löser funarg-problemet uppåt genom att dynamiskt flytta stängningar från stapeln till högen efter behov. [ citat behövs ] Java -programmeringsspråket hanterar det genom att kräva att kontext som används av kapslade funktioner i anonyma inre och lokala klasser förklaras slutgiltigt , och kontext som används av lambda-uttryck är faktiskt slutgiltig. C# och D har lambdas (stängningar) som kapslar in en funktionspekare och relaterade variabler.

I funktionella språk är funktioner förstklassiga värden som kan skickas var som helst. Sålunda måste implementeringar av Scheme eller Standard ML ta itu med både uppåt- och nedåtgående funargproblem. Detta åstadkommes vanligtvis genom att representera funktionsvärden som heap-allokerade stängningar, som tidigare beskrivits. OCaml - kompilatorn använder en hybridteknik (baserad på programanalys ) för att maximera effektiviteten. [ citat behövs ]

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Funarg_problem&oldid=1049303645 "