Sisäkkäinen toiminto - Nested function

In ohjelmointi , joka on sisäkkäisiä toiminto (tai sisäkkäisen menettely tai alirutiini ) on funktio , joka on määritetty toisen toiminnon, sulkeva toiminto . Yksinkertaisten rekursiivisten laajuussääntöjen vuoksi sisäkkäinen funktio on itsessään näkymätön välittömästi sulkevan funktionsa ulkopuolella, mutta voi nähdä (käyttää) kaikkia paikallisia objekteja (tiedot, toiminnot, tyypit jne.) Välittömästi sulkevasta toiminnostaan ja mistä tahansa toiminnosta s) joka puolestaan sulkee kyseisen toiminnon. Pesiminen on teoriassa mahdollista rajoittamattomaan syvyyteen, vaikka käytännön ohjelmissa käytetään yleensä vain muutamaa tasoa.

Sisäkkäisiä toimintoja käytetään monissa lähestymistavoissa strukturoituun ohjelmointiin , mukaan lukien varhaiset, kuten ALGOL , Simula 67 ja Pascal , ja myös monilla nykyaikaisilla dynaamisilla kielillä ja toiminnallisilla kielillä . Niitä ei kuitenkaan perinteisesti tueta (alun perin yksinkertaisessa) C-kieliryhmässä.

Tehosteet

Sisäkkäiset toiminnot olettavat toiminnon tai lohkon laajuuden . Sisäkkäisen funktion laajuus on sulkeutuvan funktion sisällä, eli sen funktion yhden lohkon sisällä, mikä tarkoittaa, että se on näkymätön kyseisen lohkon ulkopuolella ja myös sulkevan toiminnon ulkopuolella. Sisäkkäinen funktio voi käyttää muita paikallisia toimintoja, muuttujia, vakioita, tyyppejä, luokkia jne., Jotka ovat samassa tai missä tahansa suljetussa laajuudessa ilman nimenomaista parametrien siirtoa, mikä yksinkertaistaa suuresti tietojen siirtämistä sisäkkäiseen funktioon ja sieltä pois. Tämä on yleensä sallittua sekä lukemiseen että kirjoittamiseen.

Sisäkkäiset toiminnot voivat tietyissä tilanteissa (ja kielillä) johtaa sulkemisen luomiseen . Jos sisäkkäinen funktio voi välttyä sulkevalta, esimerkiksi jos funktiot ovat ensimmäisen luokan objekteja ja sisäkkäinen funktio siirretään toiselle funktiolle tai palautetaan sulkufunktiosta, sulkeminen luodaan ja tämän toiminnon kutsut voivat käyttää alkuperäisen toiminnon ympäristöön. Välittömästi sulkevan toiminnon kehyksen on oltava edelleen elossa, kunnes viimeinen viittaava sulkeminen kuolee, eikä sulkeissa viitattuja ei-paikallisia automaattisia muuttujia voida siten jakaa . Tätä kutsutaan funarg -ongelmaksi ja se on keskeinen syy siihen, miksi sisäkkäisiä toimintoja ei toteutettu joillakin yksinkertaisemmilla kielillä, koska se vaikeuttaa merkittävästi koodin luomista ja analysointia, varsinkin kun toiminnot on sisäkkäin eri tasoille ja jaettu eri osille ympäristöään.

Esimerkkejä

Esimerkki Pascal -syntaksista ( ALGOL , Modula 2 , Oberon , Ada jne. Vastaava):

function E(x: real): real;
    function F(y: real): real;
    begin
        F := x + y
    end;
begin
    E := F(3) + F(4)
end;

Toiminto Fon sisäkkäin E. Huomaa, että Eparametri xnäkyy myös F( Fosana E) molemmissa xja yon näkymätön ulkopuolella Eja Fvastaavasti.

Vastaavasti standardissa ML:

fun e (x : real) =
  let
    fun f y = x+y
  in
    f 3 + f 4
  end;

Yksi tapa kirjoittaa sama esimerkki Haskellin syntaksiin:

e :: Float -> Float
e x = f 3 + f 4 where f y = x + y

Sama esimerkki GNU C: n syntaksissa (C laajennettu sisäkkäisfunktioilla):

float E(float x)
{
    float F(float y)
    {
        return x + y;
    }
    return F(3) + F(4);
}

Pikavalinta

Realistisempi esimerkki on tämä pikavalinnan toteutus :

void sort(int *items, int size) {
    void quickSort(int first, int last) {
        void swap(int p, int q) {
            int tmp = items[p];
            items[p] = items[q];
            items[q] = tmp;
        }
        
        int partition() {
            int pivot = items[first], index = first;
            swap(index, last);
            for (int i = first; i < last; i++)
                if (items[i] < pivot)
                    swap(index++, i);
            swap(index, last);
            return index;
        }

        if (first < last) {
            int pivotIndex = partition();
            quickSort(first, pivotIndex - 1);
            quickSort(pivotIndex + 1, last);
        }
    }
    quickSort(0, size - 1);
}

Toinen esimerkki on seuraava Hoare -osioihin perustuvan pikalajittelun toteutus käyttäen C ++ 11 lambda -lausekkeen syntaksia :

template<typename RandomAccessIterator>
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void {
	auto Partition = [&]() {
		//Hoare partition scheme
		auto &Pivot = *Begin;
		auto ForwardCursor = Begin;
		auto BackwardCursor = End - 1;
		auto PartitionPositionFound = false;
		auto LocatePartitionPosition = [&]() {
			while (*ForwardCursor < Pivot)
				++ForwardCursor;
			while (Pivot < *BackwardCursor)
				--BackwardCursor;
			if (ForwardCursor >= BackwardCursor)
				PartitionPositionFound = true;
			else
				Swap(*ForwardCursor, *BackwardCursor);
		};
		//Trivial helper function
		auto MoveOnAndTryAgain = [&]() {
			++ForwardCursor;
			--BackwardCursor;
		};
		//Brief outline of the actual partition process
		while (true) {
			LocatePartitionPosition();
			if (PartitionPositionFound)
				return BackwardCursor + 1;
			else
				MoveOnAndTryAgain();
		}
	};
	//Brief outline of the quicksort algorithm
	if (Begin < End - 1) {
		auto PartitionPosition = Partition();
		Sort(Begin, PartitionPosition);
		Sort(PartitionPosition, End);
	}
}

Tarkoitus

Leksisesti sisäkkäiset funktioiden määritelmät ovat eräänlainen tietojen piilottaminen, ja niistä on hyötyä prosessitehtävien jakamisessa alitehtäviin, joilla on merkitystä vain paikallisesti. Näin vältetään ohjelman muiden osien sotkeminen toimintoihin ja muuttujiin, jotka eivät liity näihin osiin.

Niitä käytetään tyypillisesti aputoimintoina tai rekursiivisina funktioina toisen toiminnon sisällä (kuten yllä olevassa pikaesimerkissä). Tällä on rakenteellinen etu koodin järjestämisessä, vältetään soveltamisalan saastuminen ja myös toimintojen helppo tila jakaminen. Koska sisäkkäisfunktio voi käyttää sulkevan funktion paikallisia muuttujia, tilan jakaminen on mahdollista ilman, että parametreja siirretään sisäkkäiselle funktiolle tai käytetään yleistä muuttujaa , joka yksinkertaistaa koodia.

Kielissä, joissa on sisäkkäisiä toimintoja, toiminnot voivat tavallisesti sisältää myös paikallisia vakioita ja tyyppejä (paikallisten muuttujien , parametrien ja toimintojen lisäksi), jotka on koteloitu ja piilotettu samalla sisäkkäisellä tavalla, millä tahansa syvyyden tasolla. Tämä voi entisestään parantaa koodin jäsentämismahdollisuuksia.

Muut käyttötarkoitukset

Ohjaa virtausta

Sisäkkäisiä toimintoja voidaan käyttää myös strukturoimattomalle ohjausvirralle käyttämällä paluulauseketta yleiselle rakenteettomalle ohjausvirralle. Tätä voidaan käyttää hienompaan hallintaan kuin se on mahdollista muiden kielen sisäänrakennettujen ominaisuuksien kanssa-esimerkiksi se voi sallia for-silmukan ennenaikaisen lopettamisen, jos se breakei ole käytettävissä, tai sisäkkäisen silmukan ennenaikaisen lopettamisen, jos -tasoa breaktai poikkeuksia ei ole saatavilla.

Korkeamman tason toiminnot

Koska useimmilla kielillä toiminnot ovat kelvollisia palautustyyppejä, on mahdollista luoda sisäkkäinen funktio, joka käyttää parametrijoukkoa ulkoisesta funktiosta ja jonka funktio on ulkoisen funktion palautusarvo. Siten on mahdollista palauttaa toiminto, joka on asetettu täyttämään tietty tehtävä, ja sille on annettu vain vähän tai ei lainkaan muita parametreja, mikä voi parantaa suorituskykyä melko merkittävästi.

Vaihtoehdot

Tärkein vaihtoehto sisäkkäisille funktioille kielillä, joilla niitä ei tueta, on sijoittaa kaikki asiaankuuluvat funktiot ja muuttujat erilliseen moduuliin (tiedostoon) ja paljastaa vain ylätason kääretoiminto julkisesti. C: ssä tämä tehdään yleensä käyttämällä staattisia funktioita kapselointiin ja staattisia muuttujia viestintään. Tämä saavuttaa kapseloinnin ja tilan jakamisen, vaikkakaan ei loogista organisaatiota, jonka funktioiden leksikaalinen sisäkkäisyys antaa, ja siitä tulee erillisen tiedoston hinta. Se ei myöskään ole mahdollista useammalla kuin yhdellä tasolla.

Toinen vaihtoehto on jakaa tila toimintojen välillä toimintoparametrien kautta, useimmiten välittämällä viitteet argumentteina kopiointikustannusten välttämiseksi. C: ssä tämä toteutetaan yleensä osoittimella rakenteeseen, joka sisältää kontekstin. Tämä lisää merkittävästi funktiokutsujen monimutkaisuutta.

Vuonna PHP ja muut kielten anonyymi toiminto on ainoa vaihtoehto: sisäkkäistä toiminto ilmoituksen mukaan ei ole niin tavanomainen tehtävä, vaan sitä vastoin, paikallismuuttujana. Jos haluat käyttää paikallisia muuttujia nimettömässä funktiossa, käytä sulkemista .

Kieli (kielet

Tunnettuja kieliä, jotka tukevat leksisesti sisäkkäisiä toimintoja, ovat:

ALGOL- pohjaiset kielet, kuten ALGOL 68 , Simula , Pascal , Modula-2 , Modula-3 , Oberon , Seed7 ja Ada
Nykyaikaiset versiot Lispistä (leksikkäin), kuten Scheme ja Common Lisp
ECMAScript ( JavaScript ja ActionScript )
Tikka
Kotlin (paikalliset toiminnot)
Scala (täysi tuki)
Erilaiset tuet skriptikielillä, kuten Ruby , Python , Lua , PHP ja Perl
GCC tukee C: n sisäkkäisiä toimintoja kielilaajennuksena.
C# alkaen C# 7.0
D kieli, C-liittyvä kieli sisäkkäisiä funktioita.
Fortran , joka alkaa Fortran-90: stä , tukee yhden tason sisäkkäisiä ( SISÄLTYNYT ) aliohjelmia ja toimintoja.
MATLAB (täysi tuki)
Wolframin kieli
Sotilas , YSI

Toiminnalliset kielet

Useimmissa toiminnallisissa ohjelmointikielissä , kuten Scheme, sisäkkäiset toiminnot ovat yleinen tapa toteuttaa algoritmeja, joissa on silmukoita. Luodaan yksinkertainen ( hännän ) rekursiivinen sisäfunktio, joka toimii algoritmin pääsilmukana, kun taas ulkoinen toiminto suorittaa käynnistystoimintoja, jotka on tehtävä vain kerran. Monimutkaisemmissa tapauksissa sisäisesti voidaan luoda useita toisiaan rekursiivisia toimintoja.

Jotkut kielet ilman suoraa tukea

Joillakin kielillä ei ole suoraa syntaktista ja semanttista tukea sisäkkäisten toimintojen toteuttamiseen. Joillekin niistä ajatus sisäkkäisistä funktioista voidaan kuitenkin simuloida jonkin verran vaikeuksilla käyttämällä muita kielirakenteita. Seuraavat kielet voivat arvioida sisäkkäisiä toimintoja vastaavien strategioiden avulla:

C ++
- ennen C ++ 11: sallii luokkien määrittelyn luokissa ja tarjoaa mahdollisuuden käyttää luokkamenetelmiä samalla tavalla kuin yhden tason sisäkkäiset toiminnot (katso Toiminto -objekti C ++: ssa ).
- C ++ 11: stä lähtien: käyttämällä lambda -lausekkeita yllä olevana pikanäytteenä.
Eiffel ei nimenomaisesti salli rutiinien pesimistä. Tämä pitää kielen yksinkertaisena ja mahdollistaa myös tavan käyttää erityistä muuttujaa, Result , (arvon palautus) -funktion tuloksen osoittamiseen.
Visual Basic , käyttämällä nimettömiä menetelmiä tai lambda -lausekkeita.
Java , käyttämällä lambda -lausekkeita (katso Anonymous -toiminnot Javassa ) (Java 8: n jälkeen) tai kiertotapa, joka koostuu nimettömästä luokasta, joka sisältää yhden menetelmän. Myös nimettyä luokkaa, joka on julistettu paikalliseksi menetelmälle, voidaan käyttää.

Toteutus

Sisäkkäisten toimintojen käyttöönotto voi olla enemmän mukana kuin se saattaa näyttää, sillä viittaus sisäiseen funktioon, joka viittaa ei-paikallisiin muuttujiin, luo sulkemisen . Tästä syystä sisäkkäisiä toimintoja ei tueta joillakin kielillä, kuten C, C ++ tai Java, koska tämä vaikeuttaa kääntäjien toteuttamista. Jotkut kääntäjät kuitenkin tukevat niitä kääntäjäkohtaisena laajennuksena. Tunnettu esimerkki tästä on C: n GNU C -toteutus, joka jakaa koodin kääntäjien kanssa, kuten Pascal, Ada ja Modula.

Muiden kuin paikallisten objektien käyttö

On olemassa useita tapoja toteuttaa sisäkkäisiä menettelyjä leksisesti laajuisella kielellä, mutta klassinen tapa on seuraava:

Kaikki muut kuin paikalliset objektit , X, saavutetaan konepinon aktivointikehysten pääsylinkkien kautta. Soittaja C avustaa kutsuttua menettelyä P työntämällä suoran linkin P: n välittömän leksikaalisen kapseloinnin (P) viimeiseen aktivointiin ennen itse puhelua. P voi sitten löytää nopeasti oikean aktivoinnin tietylle X: lle seuraamalla kiinteää lukumäärää (P.syvyys - X.syvyys) linkkejä (yleensä pieni luku).

Soittaja luo tämän suoran linkin (itse) seuraamalla C.depth - P.depth + 1 vanhempaa linkkiä, mikä johtaa (P): n uusimpaan aktivointiin, ja yhdistää sitten tilapäisesti niiden yli suoralla linkillä kyseiseen aktivointiin; linkki katoaa myöhemmin yhdessä P: n kanssa, jolloin sen alla olevat vanhemmat linkit voivat tulla uudelleen käyttöön.

Huomaa, että P näkyy C: llä ja voi siksi kutsua sitä, jos (P) = C / (C) / ((C)) / jne.

Tämä alkuperäinen menetelmä on nopeampi kuin miltä se saattaa näyttää, mutta se on kuitenkin usein optimoitu käytännön nykyaikaisissa kääntäjissä (käyttämällä näyttöjä tai vastaavia tekniikoita).

Toinen tapa toteuttaa sisäkkäisiä toimintoja, joita jotkut kääntäjät käyttävät, on muuntaa ("nostaa") sisäkkäiset toiminnot ei-sisäkkäisiksi funktioiksi (joissa ylimääräiset, piilotetut parametrit korvaavat pääsylinkit) käyttämällä prosessia, joka tunnetaan nimellä lambda lifting välivaiheessa kokoelmassa.

Toimii arvoina

Jotta paikalliset funktiot, joissa on leksisesti laajennettuja ei -paikallisia , välitettäisiin tuloksina, kielen ajonaikaisen koodin on myös implisiittisesti läpäistävä ympäristö (data), jonka funktio näkee kapselointitoimintonsa sisällä, jotta se on tavoitettavissa myös silloin, kun sulkeutumisen nykyinen aktivointi toimintoa ei ole enää olemassa. Tämä tarkoittaa, että ympäristö on tallennettava muulle muistialueelle kuin (myöhemmin palautetut osat) kronologisesti perustuvaan suorituspinoon, mikä puolestaan edellyttää jonkinlaista vapaasti dynaamista muistinvarausta . Monet vanhemmat Algol -pohjaiset kielet (tai niiden murret) eivät siksi salli paikallisten funktioiden, jotka käyttävät ei -paikallisia, siirtämistä palautusarvoina, tai eivät salli toimintoja palautusarvoina ollenkaan, vaikka tällaisten funktioiden välittäminen argumentteina voi silti olla mahdollista.

Ei-suoritettavat pinot

Vähintään yksi sisäkkäisten toimintojen toteutus aiheuttaa No-Execute-pinojen menetyksen (NX-pino) . GCC: n sisäkkäisten toimintojen toteutus kutsuu sisäkkäisiä toimintoja konepinoon asetetun hyppykäskyn kautta ajon aikana. Tämä edellyttää, että pino on suoritettava.

Yksikään suorituspino ja sisäkkäiset toiminnot eivät sulje toisiaan pois GCC: ssä. Jos ohjelman kehittämisessä käytetään sisäkkäistä toimintoa, NX -pino häviää hiljaa. GCC tarjoaa -Wtrampoline -varoituksen varoittaakseen tilasta.

Suojatun kehityksen elinkaaren aikana kehitetyt ohjelmistot eivät usein salli sisäkkäisten toimintojen käyttöä tässä kääntäjässä (GCC) NX -pinojen menetyksen vuoksi.

Languages

In other projects