Funarg problem - Funarg problem

I datateknikk , den funarg problem (funksjon argument problem) refererer til vanskeligheten med å implementere førsteklasses funksjoner ( funksjoner som førsteklasses gjenstander ) i et programmeringsspråk implementeringer slik som å bruke stabel baserte minnetildeling av funksjonene.

Vanskeligheten oppstår bare hvis kroppen til en nestet funksjon refererer direkte (dvs. ikke ved å sende argument) til identifikatorer definert i miljøet der funksjonen er definert, men ikke i miljøet til funksjonsanropet. En standardoppløsning er enten å forby slike referanser eller å opprette nedleggelser .

Det er to subtilt forskjellige versjoner av funarg -problemet. Den oppover funarg problemet oppstår fra å returnere (eller på annen måte overføre "oppover") en funksjon fra et funksjonskall. De nedover funarg problem oppstår ved passering av en funksjon som en parameter til en annen funksjonskall.

Oppover funarg problem

Når en funksjon ringer til en annen under en typisk utførelse av et program, må den lokale statusen til innringeren (inkludert parametere og lokale variabler ) bevares for at kjøringen skal fortsette etter at calleen kommer tilbake. I de fleste kompilerte programmer lagres denne lokale tilstanden på anropsstakken i en datastruktur som kalles en stabelramme eller aktiveringspost . Denne stabelrammen skyves eller tildeles som opptak til å ringe til en annen funksjon, og poppes eller deles når den andre funksjonen går tilbake til funksjonen som ringte. Funarg -problemet oppover oppstår når anropsfunksjonen refererer til tilstanden til den kalt/avsluttede funksjonen etter at funksjonen har returnert. Derfor må stabelrammen som inneholder tilstandens variabler for den kalt funksjonen ikke fordeles når funksjonen kommer tilbake, noe som bryter det stabelbaserte funksjonsanropsparadigmet .

En løsning på det oppadgående funarg -problemet er å ganske enkelt allokere alle aktiveringsposter fra haugen i stedet for stabelen og stole på en eller annen form for søppelinnsamling eller referansetelling for å fordele dem når de ikke lenger er nødvendig. Å administrere aktiveringsposter på haugen har historisk sett blitt oppfattet som mindre effektivt enn på stabelen (selv om dette er delvis motsagt) og har blitt oppfattet som å pålegge betydelig implementeringskompleksitet. De fleste funksjoner i typiske programmer (mindre for programmer i funksjonelle programmeringsspråk ) skaper ikke oppadgående funargs, noe som øker bekymringen for potensielle omkostninger forbundet med implementeringen. Videre er denne tilnærmingen virkelig vanskelig på språk som ikke støtter søppelinnsamling.

Noen effektivitetsinnstilte kompilatorer bruker en hybrid tilnærming der aktiveringspostene for en funksjon blir allokert fra bunken hvis kompilatoren er i stand til å utlede, gjennom statisk programanalyse , at funksjonen ikke oppretter funksjoner oppover. Ellers tildeles aktiveringspostene fra haugen.

En annen løsning er å ganske enkelt kopiere verdien av variablene inn i lukkingen på det tidspunktet lukkingen opprettes. Dette vil forårsake en annen oppførsel når det gjelder mutable variabler, fordi staten ikke lenger vil deles mellom nedleggelser. Men hvis det er kjent at variablene er konstante, vil denne tilnærmingen være ekvivalent. De ML språk ta denne tilnærmingen, siden variabler i disse språkene er bundet til verdi dvs. variabler kan ikke endres. Java tar også denne tilnærmingen med hensyn til anonyme klasser, ved at den bare tillater en å referere til variabler i det omsluttende omfanget som er final(dvs. konstant).

Noen språk lar programmereren eksplisitt velge mellom de to atferdene. PHP 5.3s anonyme funksjoner krever at en angir hvilke variabler som skal inkluderes i nedleggelsen ved å bruke use ()klausulen; hvis variabelen er oppført etter referanse, inkluderer den en referanse til den opprinnelige variabelen; ellers passerer den verdien. I de anonyme funksjonene til Apples Blocks er fangede lokale variabler som standard fanget opp etter verdi; Hvis man ønsker å dele tilstanden mellom nedleggelser eller mellom lukkingen og det ytre omfanget, må variabelen deklareres med __blockmodifikatoren, i så fall tildeles den variabelen på haugen.

Eksempel

Følgende Haskell -lignende pseudokode definerer funksjonssammensetning : 

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

λer operatøren for å konstruere en ny funksjon, som i dette tilfellet har ett argument x, og returnerer resultatet av først å søke gpå x, deretter søke fom det. Denne λ -funksjonen bærer funksjonene fog g(eller pekene til dem) som intern tilstand.

Problemet i dette tilfellet eksisterer hvis skrivefunksjonen tildeler parametervariablene fog gpå bunken. Når den composereturneres, inneholder stabelrammen som er fog gkastes. Når den interne funksjonen λxprøver å få tilgang g, får den tilgang til et kassert minneområde.

Nedover funarg problem

En nedadgående funarg kan også referere til en funksjons tilstand når den funksjonen faktisk ikke utføres. Imidlertid fordi eksistensen av en nedadgående funarg per definisjon er inneholdt i utførelsen av funksjonen som lager den, kan stabelrammen for funksjonen vanligvis fortsatt lagres på bunken. Ikke desto mindre innebærer eksistensen av nedadgående funargs en trestruktur av nedleggelser og stabelrammer som kan komplisere menneskelig og maskinell resonnement om programtilstanden.

De nedover funarg problem kompliserer effektiv samling av halen samtaler og kode skrevet i fortsettelsen-bestått stil . I disse spesielle tilfellene er hensikten med programmereren (vanligvis) at funksjonen skal kjøres i begrenset stabelplass, så den "raskere" oppførselen kan faktisk være uønsket.

praktiske implikasjoner

Historisk sett har det oppadgående funarg -problemet vist seg å være det vanskeligere. For eksempel tillater programmeringsspråket Pascal at funksjoner kan sendes som argumenter, men ikke returneres som resultater; Derfor kreves implementering av Pascal for å løse det nedadgående funarg -problemet, men ikke det oppover. Programmeringsspråkene Modula-2 og Oberon (etterkommere av Pascal) tillater funksjoner både som parametere og returverdier, men den tildelte funksjonen er kanskje ikke en nestet funksjon. Den programmeringsspråket C historisk sett unngår hovedvanskeligheten av funarg problemet ved å ikke tillate funksjonsdefinisjoner for å være nestet; Fordi miljøet for hver funksjon er det samme, som bare inneholder de statisk tildelte globale variablene og funksjonene, beskriver en peker til en funksjonskode funksjonen fullstendig. Apple har foreslått og implementert en stengesyntaks for C som løser funarg -problemet oppover ved dynamisk å flytte nedleggelser fra stabelen til haugen etter behov. De Java programmeringsspråk avtaler med det ved å kreve at sammenhengen brukes av nestede funksjoner i anonyme indre og lokale klasser bli erklært endelig , og kontekst brukes av lambda-uttrykk være effektivt endelig. C# og D har lambdas (nedleggelser) som innkapsler en funksjonspeker og relaterte variabler.

I funksjonelle språk er funksjoner førsteklasses verdier som kan overføres hvor som helst. Dermed må implementeringer av Scheme eller Standard ML løse både opp og ned funarg problemer. Dette oppnås vanligvis ved å representere funksjonsverdier som haug-tildelte nedleggelser, som tidligere beskrevet. Den Objective Caml kompilatoren benytter en hybrid teknikk (basert på programanalyse ) for å maksimere effektiviteten.

Se også

Referanser

Eksterne linker