Polymorfismi (tietokonetiede)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. maaliskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Polymorfismi ohjelmointikielissä ja tyyppiteoriassa on funktion  kyky käsitellä erityyppisiä tietoja [1] [2] [3] .

Polymorfismia on useita tyyppejä. Christopher Strachey kuvasi vuonna 1967 kaksi pohjimmiltaan erilaista : nämä ovat parametrinen polymorfismi ja ad-hoc polymorfismi , muut muodot ovat niiden alalajeja tai yhdistelmiä. Parametrinen polymorfismi on totta, koska tarkoittaa saman koodin suorittamista kaikille kelvollisille argumenttityypeille, ja ad-hoc-polymorfismi on kuvitteellista, koska on varmistaa mahdollisesti erilaisen suoritettavan koodin kosmeettinen yhtenäisyys kullekin tietylle argumentille [1] [4] . Samalla on tilanteita, joissa on tarpeen käyttää täsmälleen ad-hoc-polymorfismia, ei parametrista [5] . Pätevien tyyppien teoria yhdistää kaikenlaiset polymorfismit yhdeksi malliksi.

Björn Stroustrupille on annettu laajalle levinnyt polymorfismin määritelmä : " yksi rajapinta (ilmoitusluettelona) - monta toteutusta (näihin ilmoituksiin liittyviä määritelmiä) " [6] , mutta vain ad-hoc polymorfismi (imaginaarinen polymorfismi) kuuluu tähän. määritelmä.

Yleistä tietoa

Saman koodin perustavanlaatuinen mahdollisuus käsitellä erityyppisiä tietoja määräytyy kielen tyyppijärjestelmän ominaisuuksien mukaan . Tästä näkökulmasta erotetaan [7] staattinen ei-polymorfinen tyypitys ( Algolin ja BCPL :n jälkeläiset ), dynaaminen tyypitys ( Lisp :n , Smalltalkin , APL :n jälkeläiset ) ja staattinen polymorfinen tyypitys ( ML:n jälkeläiset ). Ad-hoc-polymorfismin käyttö on tyypillisintä ei-polymorfiselle tyypitykselle. Parametrinen polymorfismi ja dynaaminen tyypitys lisäävät koodin uudelleenkäyttöä paljon enemmän kuin ad-hoc-polymorfismi, koska kerran määritetty funktio toteuttaa määritellyn käyttäytymisen ilman päällekkäisyyttä äärettömälle määrälle äskettäin määritellyille tyypeille, jotka täyttävät funktiossa vaadittavat ehdot. Toisaalta joskus on tarpeen tarjota funktiolle erilainen käyttäytyminen parametrin tyypistä riippuen, jolloin tarvitaan erityinen polymorfismi.

Parametrinen polymorfismi on synonyymi tyyppiabstraktiolle [8] . Se on läsnä kaikkialla toiminnallisessa ohjelmoinnissa , jossa sitä yleensä kutsutaan yksinkertaisesti "polymorfismiksi".

Olio -ohjelmointiyhteisössä termi "polymorfismi" tarkoittaa yleensä periytymistä , ja parametrisen polymorfismin käyttöä kutsutaan geneeriseksi ohjelmoimiseksi [9] tai joskus "staattiseksi polymorfismiksi".

Luokitus

Ensimmäistä kertaa polymorfismin lajikkeiden luokittelun suoritti Christopher Strachey .

Jos funktioparametriin liittyy täsmälleen yksi tyyppi, niin tällaista funktiota kutsutaan monomorfiseksi. Monet ohjelmointikielet tarjoavat syntaktisen mekanismin yhden nimen (tunnisteen) määrittämiseksi useille monomorfisille funktioille. Tässä tapauksessa lähdekoodissa on mahdollista kutsua funktiota erityyppisillä todellisilla parametreilla, mutta käännetyssä koodissa kutsutaan eri funktioita (katso menettely ja funktion ylikuormitus ). Strachey kutsui tätä mahdollisuutta "ad-hoc-polymorfismiksi".

Jos funktioparametriin liittyy useampi kuin yksi tyyppi, tällaista funktiota kutsutaan polymorfiseksi . Tietenkin kuhunkin todelliseen arvoon voidaan liittää vain yksi tyyppi, mutta polymorfinen funktio huomioi parametrit ulkoisten ominaisuuksien perusteella, ei niiden omaa organisaatiota ja sisältöä. Strachey kutsui tätä mahdollisuutta "parametriseksi polymorfismiksi".

Myöhemmin luokittelua tarkensi Luca Cardelli [10] korostaen neljää polymorfismityyppiä:

Joissakin töissä parametrinen, ad-hoc- ja alatyyppipolymorfismi erotetaan kolmeksi itsenäiseksi polymorfismin luokkaksi [11] .

Termin "ad hoc" merkityksen kaksijakoisuus (toisaalta - "spontaani, huonosti suunniteltu, tilaisuuteen tehty", toisaalta - "erityinen, järjestetty nimenomaan tiettyyn tarkoitukseen tai tilaisuuteen") on ansaittu jo monta vuotta [5] . Strachey valitsi tämän termin ensimmäisen merkityksen perusteella korostaen, että ad-hoc-polymorfismilla ei ole yhtä systemaattista tapaa päätellä tuloksen tyyppi argumenttien tyypistä, ja vaikka on mahdollista rakentaa tietty joukko sääntöjä kapea hakukirjo, nämä säännöt ovat luonteeltaan spontaaneja sekä sisällöltään että sovelluskontekstiltaan [1] .

Ad-hoc-polymorfismi ei todellakaan ole todellista polymorfiaa [12] . Toimintojen ylikuormitus ei tuota "arvoa, jolla on useita tyyppejä", vaan "merkit, joilla on useita tyyppejä ", mutta tämän symbolin tunnistamat arvot ovat eri (mahdollisesti yhteensopimattomia) tyyppejä. Samoin valu ei ole todellista polymorfismia: operaattori näyttää hyväksyvän monen tyyppisiä arvoja, mutta arvot on muunnettava johonkin esitykseen ennen kuin se voi käyttää niitä, jotta operaattori todella toimii vain yhdellä tyypillä (ts. on yksi tyyppi). Lisäksi paluuarvon tyyppi ei tässä riipu syöteparametrin tyypistä , kuten parametrisen polymorfismin tapauksessa.

Tiettyjen toimintototeutusten määrittäminen eri tyypeille on kuitenkin joissain tapauksissa välttämätöntä, ei sattumaa. Klassisia esimerkkejä ovat aritmeettisten operaatioiden toteutus (fyysisesti erilaiset kokonaisluvut ja liukulukuluvut ) ja tyyppiyhtälö, joilla ei ollut vuosikymmeniin hyväksyttyä yleistä formalisointia. Ratkaisu oli tyyppiluokat , jotka ovat mekanismi tyyppimuuttujien sallittujen arvojen eksplisiittiselle diskreetille laskemiselle staattista lähetystä varten tyyppikerroksessa. Ne yhdistävät kaksi Stracheyn erottamaa polymorfismin lajiketta, mikä " tekee ad-hoc-polymorfismista vähemmän ad hoc " [5] ( pelaamalla kaksinaisuudesta). Tyyppiluokkien yleistäminen edelleen johti hyväksyttyjen tyyppien teorian rakentamiseen , joka formalisoi yhtenäisesti eksoottisimmat tyyppijärjestelmät, mukaan lukien laajennettavat merkinnät ja alatyypit.

Toisin kuin ylikuormitus ja tyyppivalu , alatyyppipolymorfismi on todellista polymorfiaa : alatyyppiobjekteja voidaan käsitellä yhtenäisesti ikään kuin ne kuuluisivat supertyyppeihinsä (mutta tämä ei pidä paikkaansa kielissä, jotka toteuttavat "perinnöllisen polymorfian" valun kautta tyypit ja toimintojen ylikuormitus , kuten C++ :n tapauksessa ). Puhtain on parametrinen polymorfismi : samaa objektia tai funktiota voidaan käyttää tasaisesti eri kirjoituskonteksteissa ilman modifikaatioita, heittoja tai muita ajonaikaisia ​​tarkistuksia tai muunnoksia. Tämä vaatii kuitenkin jonkin verran yhtenäistä tietojen esittämistä (esimerkiksi osoittimien kautta ) [4] .

Polymorfismin perustyypit

Ad-hoc-polymorfismi

Ad-hoc-polymorfismia (useimmiten käännetty venäläisessä kirjallisuudessa "erityispolymorfismiksi" tai "erikoispolymorfismiksi", vaikka molemmat vaihtoehdot eivät aina pidä paikkaansa ) tuetaan monilla kielillä funktioiden ja menetelmien ylikuormituksen kautta ja heikosti kirjoitettuna niitä  myös tyyppivalulla .

Seuraavassa esimerkissä ( Pascal -kieli ) funktiot Addnäyttävät toteuttavan saman toiminnallisuuden eri tyypeillä, mutta kääntäjä määrittelee ne kahdeksi täysin erilaiseksi funktioksi.

ohjelma Adhoc ; funktio Lisää ( x , y : Kokonaisluku ) : Kokonaisluku ; alkaa Lisää := x + y loppu ; toiminto Lisää ( s , t : Merkkijono ) : Merkkijono ; alkaa Lisää := Concat ( s , t ) end ; begin Writeln ( Add ( 1 , 2 )) ; Writeln ( Lisää ( 'Hei, ' , 'Maailma!' )) ; loppua .

Dynaamisesti kirjoitetuissa kielissä tilanne voi olla monimutkaisempi, koska kutsuttavan funktion valinta voidaan tehdä vain ajon aikana.

Ylikuormitus  on syntaktinen mekanismi, joka mahdollistaa eri funktioiden kutsumisen yhdellä tunnisteella [13] . Tyyppivalu  on semanttinen mekanismi, joka suoritetaan argumentin todellisen tyypin muuntamiseksi funktion odotetuksi tyypiksi, jota ilman tapahtuisi tyyppivirhe . Toisin sanoen kun funktiota kutsutaan tyypin castilla, eri tyypeille suoritetaan eri koodi (ennen itse funktion kutsua) [13] .

Parametrinen polymorfismi

Parametrinen polymorfismi mahdollistaa funktion tai tietotyypin määrittämisen geneerisesti, jolloin arvoja käsitellään samalla tavalla niiden tyypistä riippumatta. Parametrisesti polymorfinen funktio käyttää käyttäytymiseen perustuvia argumentteja arvopohjaisten argumenttien sijaan ja käyttää vain tarvitsemiensa argumenttien ominaisuuksia, mikä tekee siitä käyttökelpoisen missä tahansa kontekstissa, jossa objektityyppi täyttää annetut käyttäytymisvaatimukset.

Kehittyneet tyyppijärjestelmät (kuten Hindley-Milner-järjestelmä ) tarjoavat mekanismeja polymorfisten tyyppien määrittämiseen , mikä tekee polymorfisten funktioiden käytöstä helpompaa ja tarjoaa staattisen tyyppiturvan . Tällaiset järjestelmät ovat toisen kertaluvun tyyppisiä järjestelmiä, jotka lisäävät ensimmäisen kertaluvun tyyppisiin järjestelmiin (käytetään useimmissa proseduurikielissä ) tyyppiparametrisoinnin (tyyppimuuttujan avulla ) ja tyyppiabstraktion (niiden eksistentiaalisen kvantifioinnin avulla ). Toisen asteen tyyppisissä järjestelmissä ei ole välitöntä tarvetta tukea primitiivisiä tyyppejä , koska ne voidaan ilmaista kehittyneemmillä tavoilla. [neljätoista]

Klassinen esimerkki polymorfisesta tyypistä on luettelo mielivaltaisista tyyppielementeistä, joille monet Hindley-Milner- kirjoitetut kielet (useimmat staattisesti kirjoitetut toiminnalliset ohjelmointikielet ) tarjoavat syntaktisen sokerin . Seuraava esimerkki havainnollistaa uuden algebrallisen tyypin "parametrisesti polymorfinen lista " ja kaksi funktiota siinä:

datalista a = nolla | _ Miinukset a ( Luettelo a ) pituus :: Lista a - > Kokonaisluku nolla = 0 pituus ( Miinukset x xs ) = 1 + pituus xs kartta :: ( a -> b ) -> Lista a - > Luettelo b kartta f Nolla = Nollakartta f ( Miinukset x xs ) = Miinukset ( f x ) ( kartta f xs )

Kun betonityypit korvataan tyyppimuuttujalla ja niin edelleen, betonityypit rakennetaan vastaavasti ja niin edelleen. Nämä tietyt tyypit voidaan vuorostaan ​​korvata kyseisellä tyyppimuuttujalla uudelleen , jolloin saadaan tyyppejä ja niin edelleen. Tässä tapauksessa kaikille rakennetuille objekteille käytetään samaa ja-funktioiden fyysistä toteutusta . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

Parametrisen polymorfismin rajoitettuja muotoja on saatavilla myös joissakin pakollisissa (erityisesti oliosuuntautuneissa ) ohjelmointikielissä, joissa termiä " yleinen ohjelmointi " käytetään yleisesti viittaamaan siihen. Erityisesti C: ssä tyypittämätön parametrinen polymorfismi tarjotaan perinteisesti käyttämällä tyypittämätöntä osoitinta void* , vaikka myös tyypitetty muoto on mahdollinen. C++-mallien käyttö on pinnallisesti samanlaista kuin parametrinen polymorfismi, mutta semanttisesti toteutettu ad-hoc-mekanismien yhdistelmällä; C++- yhteisössä sitä kutsutaan "staattiseksi polymorfismiksi" (toisin kuin "dynaaminen polymorfismi" ).

Parametrisuus

Parametrisen polymorfismin formalisaatio johtaa parametrisyyden käsitteeseen [ , joka koostuu kyvystä ennustaa ohjelmien käyttäytymistä tarkastelemalla vain niiden tyyppejä. Esimerkiksi jos funktio on tyyppiä " forall a. a -> a", niin ilman ulkoisia välineitä, jotka täydentävät kieltä , voidaan todistaa , että se voi olla vain identtinen . Siksi parametrisyyteen liittyy usein iskulause "theorems for free" ( eng.  theorems for free ). [15] [16] [17]

Tärkeä seuraus tästä  on myös esitysriippumattomuus , mikä tarkoittaa, että abstraktin tyypin funktiot eivät ole herkkiä sen rakenteelle ja tämän tyypin erilaiset toteutukset voivat vapaasti korvata toisiaan (jopa saman ohjelman sisällä) vaikuttamatta näiden funktioiden toimintaan. [18] .

Kehittyneimmät parametrisesti polymorfiset järjestelmät (korkein kohta lambda-kuutiossa ) vievät parametrisyyden ajatuksen siihen pisteeseen, että ne pystyvät täysin todistamaan ohjelmien oikeellisuuden : niiden avulla voidaan kirjoittaa ohjelmia, jotka ovat suunnittelultaan oikein, niin että ohittaminen tyyppiyhdenmukaisuuden tarkistus itsessään takaa , että ohjelman toiminta on oikea .

Tietueen ja muunnelman polymorfia

Erillinen ongelma on parametrisen polymorfismin laajentaminen aggregaattityyppeihin: tyyppien eroteltuihin tuloihin (perinteisesti tietueiksi ) ja tyyppien erottuviin summiin (tunnetaan myös muunnelmatyypeinä ). Erilaiset " tietuelaskokset " ( englanniksi record calculi ) toimivat olio- ja modulaarisen ohjelmoinnin muodollisena perustana [20] .  

val r = { a = 1 , b = tosi , c = "hei" } val { a = n , ... = r1 } = r val r2 = { d = 3,14 , ... = r1 }

Ellipsillä tarkoitetaan tiettyä määrää kirjoitettuja kenttiä, toisin sanoen koodin abstraktiota tietyntyyppisistä tietueista, joita voidaan käsitellä tässä (ja tämän sarjan "pituus" voi myös vaihdella). Polymorfisen pääsyn kokoaminen eri tietueissa eri järjestykseen sijoitettaviin kenttiin on vaikea ongelma sekä toiminnan turvallisuuden hallinnan kannalta kielitasolla että konekoodin suorituskyvyn kannalta. taso. Naiivi ratkaisu voisi olla etsiä sanakirjaa dynaamisesti jokaisen kutsun yhteydessä (ja komentosarjakielet käyttävät sitä), mutta tämä on ilmeisesti erittäin tehotonta. Tätä ongelmaa on tutkittu aktiivisesti useiden vuosikymmenten ajan; on rakennettu monia teoreettisia malleja ja niihin perustuvia käytännön järjestelmiä, jotka eroavat ilmaisuvoimaltaan ja metateoreettiselta monimutkaisuudestaan. Tärkeimmät saavutukset tällä alueella ovat Mitchell Wandin ehdottama in - line polymorfismi ja Atsushi Ohorin rakentama polymorfinen tietuelaskenta . Yleisempi, mutta monissa ominaisuuksissa jälkeen jäänyt malli on tietueiden alatyypitys .   

Tietueiden polymorfismin tuki muodossa tai toisessa voi avata mahdollisuuksia polymorfisessa kielessä, kuten korkeamman asteen viestit ( olio-ohjelmoinnin tehokkain muoto ) , toimintojen saumaton upottaminen tietokantaelementteihin ( SQL ) yleiskäyttöinen kielikoodi ja muut, laajennettavissa olevaan ohjelmointiin asti (eli ohjelmointiin, joka ei sisällä lausekeongelmaa ), joka takaa käsittelemättömien poikkeuksien puuttumisen ohjelmissa ja tietyt metaohjelmoinnin muodot .

Alatyypin polymorfismi

Inkluusiopolymorfismi on alatyypin ja periytymisen yleinen formalisaatio [ 21] . Näitä käsitteitä ei pidä sekoittaa: alatyypit määrittelevät suhteita käyttöliittymätasolla, kun taas periytyminen määrittelee suhteet toteutustasolla [22] .

Alatyyppi ( alatyyppi ) tai alatyyppipolymorfismi ( alatyyppi polymorfismi ) tarkoittaa, että parametrisesti polymorfisen funktion käyttäytyminen on rajoitettu joukkoon tyyppejä, jotka on rajattu supertyyppi-alatyyppi hierarkiaan [23] [10] [24] . Jos esimerkiksi on olemassa tyyppejä , ja , joita rajoittavat suhteet ja , tyypin funktiolla määritetty funktio pystyy myös hyväksymään tyypin tai argumentteja ja sen käyttäytyminen on identtistä. Objektin todellinen tyyppi voidaan piilottaa "mustaksi laatikoksi" ja toimittaa vain pyydettäessä objektin tunnistamista varten. Itse asiassa, jos tyyppi on abstrakti, niin konkreettista objektia ei voi edes olla olemassa (katso abstrakti luokka , mutta ei pidä sekoittaa abstraktiin tietotyyppiin ). Tämä tyyppihierarkia tunnetaan (etenkin Scheme-kielen yhteydessä ) numerotornina , ja se sisältää yleensä useampia tyyppejä. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

Ajatus alatyypitystä motivoi lisäämällä jo kirjoitettujen funktioiden käsiteltävien tyyppien määrää ja siten lisäämällä koodin uudelleenkäyttönopeutta vahvassa kirjoituksessa (eli lisäämällä kirjoitettujen ohjelmien määrää). Tämän antaa subsumtointisääntö : " jos lauseke kuuluu tyyppiin kirjoituskontekstissa ja on tosi , niin se kuuluu myös tyyppiin " [25] [26] . et'Гt'<:tet

Alatyyppisuhteet ovat mahdollisia useissa eri tyyppiluokissa: primitiivityypit (as Integer <: Number), summatyypit , tuotetyypit , funktionaaliset tyypit jne. Lisäksi Luca Cardelli ehdotti käsitettä teholajit ( "teho" lajit ) kuvaamaan alatyypitys [27] : hän nimesi kaikkien sen alatyyppien suvun tyypin voimalajiksi [ 28 ] .

Tietojenkäsittelytieteessä erityinen paikka on tietueiden alatyypit .

Tietueiden alatyypit

Tietueen alatyypitys , joka tunnetaan myös nimellä subsumtio (  katso Barbara Liskovin substituutioperiaate ) , on olio - ohjelmoinnin (OOP) yleisin teoreettinen perustelu [29] [30] [24] [31] (mutta ei ainoa - katso # tietue ja muunnelma polymorfia ).

Martín Abadi ja Luca Cardelli formalisoivat tietueiden alatyypityksen rajoitetun kvantifioinnin avulla parametrisesti polymorfisten tyyppien yli [29] [30] ; kun taas tyyppiparametri asetetaan implisiittisesti [32] .

Tietueiden alatyypeissä erotetaan kaksi lajiketta: leveys ja syvyys.

Leveyden alatyypitys sisältää uusien kenttien lisäämisen tietueeseen . Esimerkiksi:

tyyppi Objekti = { ikä: Int } tyyppi Ajoneuvo = { ikä: Int; nopeus: Int} tyyppi Pyörä = { ikä: Int; nopeus: Int; vaihde: Int; } typeMachine = { ikä: Int; polttoaine: String

Toisaalta voidaan kirjoittaa alatyyppisuhteet Vehicle <: Object, Bike <: Vehicle(ja koska alatyyppi on transitiivinen , niin ja Bike <: Object) ja Machine <: Object. Toisaalta voimme sanoa, että tyypit Vehicle, Bikeja Machine sisältävät (perivät) kaikki tyypin ominaisuudet Object. (Tässä viitataan tyyppijärjestelmän rakenteelliseen semantiikkaan )

Koska tyyppiä pidetään usein intuitiivisesti arvojoukkona, alatyypin kenttien määrän lisääminen voi olla ristiriitaista joukkoteorian näkökulmasta . Todellisuudessa tyypit eivät ole joukkoja [33] , ne on tarkoitettu ohjelmien käyttäytymisen tarkistamiseen, ja alatyypityksen ideana on, että alatyypillä on ainakin supertyyppinsä ominaisuudet, ja siten se pystyy emuloimaan sitä ainakin jossa objektilta odotetaan supertyyppiä [25] . Tai toisin sanoen: supertyyppi määrittelee vähimmäisjoukon ominaisuuksia objektijoukolle, ja sitten tyyppi, jolla on nämä ominaisuudet ja mahdollisesti joitain muita ominaisuuksia, muodostaa tämän joukon osajoukon ja on siksi sen alatyyppi [30] .

Alatyyppisuhteet joukkojen suhteen ovat intuitiivisempia varianttityyppien tapauksessa [34] :

tyyppi Päivä = ma | ti | häät | to | pe | la | aurinko tyyppi Työpäivä = ma | ti | häät | to | pe tyyppi Viikonloppu = la | aurinko

Täällä Workday <: Dayja WeekEnd <: Day.

Kenttien nimeäminen mahdollistaa niiden esiintymisjärjestyksen poistamisen tietueissa (toisin kuin monikot ), mikä mahdollistaa mielivaltaisten suunnattujen asyklisten periytymisgraafien rakentamisen, joka formalisoi usean periytymisen [34] :

tyyppi Auto = { ikä: Int; nopeus: Int; polttoaine: String

Nyt Car <: Vehicleja samaan aikaan Car <: Machine. On myös selvää, että Car <: Object(katso vinoneliön muotoinen perintö ).

Syvyysalatyyppi tarkoittaa, että tiettyjen tietuekenttien tyypit voidaan korvata niiden alatyypeillä:

tyyppi Matka = { veh: Ajoneuvo; päivämäärä: päivä tyyppi Urheilu = { veh: Pyörä; päivämäärä: päivä tyyppi Loma = { veh: Auto; päivämäärä: viikonloppu }

Yllä olevista määritelmistä voimme päätellä , että Sports <: Voyageja Vacation <: Voyage.

Menetelmät tietueen alatyypeissä

Täysi tuki olio-ohjelmointiin edellyttää, että tietuekenttien määrään sisällytetään myös toimintoja , jotka käsittelevät niiden tietuetyyppien arvoja, joihin ne kuuluvat [ 29] [35] . Tällaisia ​​toimintoja kutsutaan perinteisesti " menetelmiksi ". Yleistetty malli tietueiden sitomiseksi menetelmiin on lähetysmatriisi ; Käytännössä useimmat kielet jakavat sen vektoreiksi riveissä tai sarakkeissa - vastaavasti toteuttaen joko luokkapohjaisen organisaation tai menetelmäpohjaisen organisaation [36 ] . Samanaikaisesti tulee erottaa alatyyppien ohitusmenetelmät ( method overriding ) ja alatyyppifunktiot ( functional subtyping ). Ohitusmenetelmät eivät sido niitä funktioiden alityyppisuhteilla, mutta sallivat niiden muuttaa tyyppiallekirjoituksiaan. Tässä tapauksessa kolme vaihtoehtoa ovat mahdollisia: invariantti, kovariantti ja kontravarianssi uudelleenmäärittely, ja kaksi viimeistä käyttävät parametrien alatyyppiä [37] (lisätietoja on kohdassa kovarianssi ja kontravarianssi ). Abadi-Cardelli-laskennassa [29] otetaan huomioon vain muuttumattomat menetelmät, jotka ovat tarpeen turvallisuuden osoittamiseksi .

Monet oliopohjaiset kielet tarjoavat sisäänrakennetun mekanismin funktioiden sitomiseksi menetelmiin , mikä toteuttaa luokkapohjaisen ohjelmien organisoinnin. Kielet, jotka käsittelevät toimintoja ensimmäisen luokan objekteina ja kirjoittavat niitä (katso ensimmäisen luokan funktiot , funktionaalinen tyyppi  - ei pidä sekoittaa funktion palautustyyppiin ) mahdollistavat mielivaltaisen menetelmäpohjaisen organisoinnin, mikä mahdollistaa oliosuuntautuneen suunnittelun ilman suora tuki kielen sivuilta [38] . Jotkut kielet (kuten OCaml ) tukevat molempia.

Kielet, joiden tyyppijärjestelmä perustuu muodolliseen alatyyppiteoriaan ( OCaml , seuraaja ML -projekti ), käsittelevät oliojärjestelmiä ja luokkajärjestelmiä itsenäisesti [39] [40] . Tämä tarkoittaa, että objektityyppi liittyy ensisijaisesti objektiin , ja vain, kun se on erikseen määritetty, objektityyppi liittyy tiettyyn luokkaan. Tässä tapauksessa dynaaminen lähetys suoritetaan objektitasolla, mikä tarkoittaa, että tällaisissa kielissä kahdella samaan luokkaan kuuluvalla objektilla voi yleisesti ottaen olla erilaiset menetelmät. Yhdessä muodollisesti määritellyn moniperinnön semantiikan kanssa tämä antaa välittömän kattavan tuen mixineille .

CLOS toteuttaa koko lähetysmatriisin monimenetelmien avulla , eli dynaamisesti lähetettävien menetelmien avulla, jotka ovat polymorfisia useissa argumenteissa kerralla [41] .

Jotkut kielet käyttävät erikoisia ad-hoc-ratkaisuja. Esimerkiksi C++- kielityyppijärjestelmä mahdollistaa automaattisen tyyppisuorituksen (eli se on heikko ), ei-polymorfinen , emuloi alatyypitystä manifestin periytymisen muuttumattomilla menetelmäallekirjoituksilla , eikä tue tyypin abstraktiota (ei pidä sekoittaa kenttäpiilotuksen kanssa ) . C++ :n periytyminen toteutetaan joukolla ad-hoc-mekanismeja, mutta sen käyttöä kutsutaan kieliyhteisössä "polymorfismiksi" (ja kentän piilottamista kutsutaan "abstraktioksi" [42] ). Periytyskaaviota on mahdollista hallita: vinoneliön muotoista periytymistä C++:ssa kutsutaan " virtuaaliperinnöksi " ja se määritellään eksplisiittisellä attribuutilla ; oletusarvoisesti perityt kentät monistetaan ja niitä käytetään määrätyllä nimellä. Tällaisen kielen käyttö voi olla vaarallista  – ohjelmien vakautta ei voida taata [43] [37] (kieltä kutsutaan turvalliseksi , jos siinä olevat ohjelmat, jotka kääntäjä voi hyväksyä hyvin muotoiltuina, eivät koskaan ylitä sallittu käyttäytyminen dynamiikassa [44] ). virtual

Korkeamman asteen alatyypit

Järjestelmä on järjestelmän F laajennus (ei ole edustettuna lambda-kuutiossa ), joka formalisoi rajoitetun kvantifioinnin tyyppioperaattoreille , laajentaen alatyyppisuhteita suvusta korkeamman suvun tyyppeihin . Järjestelmästä on useita versioita , jotka eroavat ilmaisuvoimaltaan ja metateoreettiselta monimutkaisuudestaan, mutta useimmat pääajatuksista esitti Luca Cardelli [45] . *

Polymorfismin lajikkeiden yhdistelmä

Tyyppiluokat

Tyyppiluokka toteuttaa yhden itsenäisen virtuaalimenetelmien taulukon useille ( yleisesti kvantitatiivisille ) tyypeille. Tällä tavalla tyyppiluokat eroavatolio -ohjelmoinnin luokista , joissa jokaisen objektin ( rajoitettu määrällinen ) mukana on osoitin virtuaaliseen menetelmätaulukkoon [46] . Tyyppiluokat eivät ole tyyppejä, vaan tyyppiluokkia; niiden esiintymät eivät ole arvoja, vaan tyyppejä.

Esimerkiksi [46] :

luokka Num a jossa ( + ), ( * ) :: a -> a -> a kieltää :: a -> a

Tämä ilmoitus kuuluu näin: " Tyyppi akuuluu luokkaan , Numjos sille on määritelty funktiot (+), (*)ja negateannetuilla allekirjoituksilla ."

esiintymä Num Int missä ( + ) = addInt ( * ) = mulInt negatiivinen = negInt esimerkki Num Float jossa ( + ) = addFloat ( * ) = mulFloat negatiivinen = negFloat

Ensimmäinen ilmoitus kuuluu: " Tyypiin on määritetty toimintoja (+)ja (*)vastaavia negateallekirjoituksiaInt ." Toinen lausunto kuuluu samalla tavalla.

Nyt voit kirjoittaa oikein seuraavat funktiot (ja tyyppipäätelmä on pääteltävissä ) :

neliö :: Num a => a -> a neliö x = x * x neliöt3 :: Num a , Num b , Num c => ( a , b , c ) -> ( a , b , c ) neliöt3 ( x , y , z ) = ( neliö x , neliö y , neliö z )

Koska kertolasku on toteutettu fyysisesti eri tavalla kokonaislukujen ja liukulukujen kohdalla , tyyppiluokkien puuttuessa tähän tarvittaisiin jo kaksi ylikuormitettua funktiota squareja kahdeksan ylikuormitettua funktiota squares3, ja todellisissa ohjelmissa, joissa on monimutkaisia ​​tietorakenteita, on paljon enemmän päällekkäistä koodia . Olio -ohjelmoinnissa tämänkaltaiset ongelmat ratkaistaan ​​dynaamisen lähettämisen avulla, johon liittyy lisäkustannuksia. Tyyppiluokka lähettää staattisesti yhdistäen parametriset ja ad-hoc-polymorfismit yhdeksi malliksi [5] . Parametrisen polymorfismin kannalta tyyppiluokalla on parametri ( tyyppimuuttuja ), joka kattaa joukon tyyppejä. Ad-hoc-polymorfismin näkökulmasta tämä joukko ei ole vain diskreetti, vaan myös eksplisiittisesti määritelty toteutustasolle asti. Yksinkertaisesti sanottuna allekirjoitus tarkoittaa, että funktio on parametrisesti polymorfinen , mutta sen parametrin tyyppivalikoima on rajoitettu vain niihin tyyppeihin, jotka kuuluvat tyyppiluokkaan . Tästä johtuen funktio kirjoitetaan ainutlaatuisella tavalla huolimatta kehostaan ​​ylikuormitetun funktion kutsusta. square :: Num a => a -> aNum

Tyyppiluokkien natiivituki otettiin ensimmäisen kerran käyttöön Haskellissa , mutta ne voidaan ottaa käyttöön myös mihin tahansa parametrisesti polymorfiseen kieleen yksinkertaisella esikäsittelyllä [5] ja toteuttaa myös idiomaattisesti (katso esimerkiksi ML-moduulin kieli#Implementing Alternative Models ). Suora tuki voi kuitenkin helpottaa automaattista päättelyä ohjelmien merkityksestä.

Haskellin tasa - arvotyypit on toteutettu tyyppiluokan esiintymänäEq(yleistäen tasa - arvotyyppimuuttujat Standard ML : stä ) :

( == ) :: Eq a => a -> a -> Bool

Vähentääkseen joidenkin käyttäjän määrittämien tyyppien usein ilmeisen välttämättömien ominaisuuksien koodaamista vaivaa, Haskell tarjoaa lisäksi syntaktisen sokerin  , rakenteen deriving, joka on voimassa rajoitetulle joukolle vakiotyyppiluokkia (kuten Eq). (Venäjänkielisessä yhteisössä sen käyttö sekoitetaan usein " perinnön " käsitteeseen johtuen sanan " johdannainen " käännöksen erityispiirteistä.)

Yleiset algebralliset tietotyypit

Polytypismi

Joskus käytetään termiä "polytyypismi" tai "tietotyypin yleistäminen". Pohjimmiltaan polytyypitys viittaa kielen sisäänrakennettuun tyyppikonstruktorin polymorfismin tukeen , joka on suunniteltu yhdistämään ohjelmointirajapintoja ja lisäämään koodin uudelleenkäyttöä . Esimerkki monityypisyydestä on yleistetty kuvioiden sovitusalgoritmi [47] .

Määritelmän mukaan polytyyppifunktiossa " vaikka tietyille tyypeille voi olla rajallinen määrä ad-hoc-haaroja, ei ole ad-hoc-kombinaattoria " [48] .

Polytysointi voidaan toteuttaa käyttämällä yleistä tietotyyppiä tai korkeamman asteen polymorfismia . Haskellin PolyP [49] -laajennus on syntaksirakennelma, joka yksinkertaistaa polytyyppifunktioiden määrittelyä Haskellissa .

Polytyyppifunktio on jossain mielessä yleisempi kuin polymorfinen funktio, mutta toisaalta funktio voi olla polytyypistetty eikä polymorfinen, kuten seuraavien funktiotyyppien allekirjoituksista voidaan nähdä :

pää :: [ a ] ​​​​-> a ( + ) :: Num a => a -> a -> a pituus :: Säännöllinen d => d a -> Int summa :: Säännöllinen d => d Int -> Int

Ensimmäinen funktio ( head) on polymorfinen (parametrisesti polymorfinen ), toinen (infix-operaattori " ) on ylikuormitettu (ad-hoc-polymorfinen), kolmas ja neljäs ovat polytyyppisiä: tyyppimuuttuja niiden määritelmässä vaihtelee tyypin mukaan rakentajat . Samanaikaisesti kolmas funktio ( ) on monityyppinen ja polymorfinen (oletettavasti se laskee "pituuden" jollekin polymorfisten aggregaattityyppien joukolle - esimerkiksi elementtien lukumäärä listoissa ja puissa ), ja neljäs ( ) on monityyppinen, mutta ei polymorfinen (monomorfinen tyyppiluokkaan kuuluvien aggregaattityyppien yläpuolella , jolle se todennäköisesti laskee kokonaislukujen summan, jotka muodostavat tietyn aggregaattityypin objektin). + dlengthsum Regular

Muut

Dynaamisesti tyypitetyt kielet edustavat yhtenäisesti polymorfismin muotoja, jotka muodostavat niissä omanlaisen ideologian ja vaikuttavat sovellettuihin tehtävähajotusmenetelmiin. Esimerkiksi Smalltalkissa mikä tahansa luokka pystyy vastaanottamaan minkä tahansa tyyppisiä viestejä ja joko käsittelemään niitä yksinään (mukaan lukien itsetutkiskelun kautta ) tai välittämään sen toiselle luokalle - mikä tahansa menetelmä on siis muodollisesti parametrisesti polymorfinen, kun taas sen sisäinen rakenne voi haarautua dynaamisen argumenttityypin ehdon mukaan toteuttaen erityistä polymorfismia. CLOS : ssa monimenetelmät ovat samanaikaisesti ensiluokkaisia ​​funktioita , minkä ansiosta voimme pitää niitä sekä rajoitetusti määrättyinä että yleistettyinä ( todellisina polymorfisina ).

Staattisesti polymorfisesti tyypitetyt kielet sitä vastoin voivat toteuttaa polymorfismin muunnelmia ortogonaalisesti (toisistaan ​​riippumattomasti), mikä mahdollistaa niiden monimutkaisen rakentamisen tyyppiturvallisella tavalla. Esimerkiksi OCaml tukee parametrisia luokkia (samankaltaisia ​​ominaisuuksiltaan kuin C++-luokkamalleja , mutta todennettavissa ilman ilmentämistä), niiden leveyden ja syvyyden periytymistä (mukaan lukien useita ), tyyppiluokkien idiomaattista toteutusta (allekirjoitusten kautta - katso vastaava esimerkki ML-moduulikielen käytöstä , rivipolymorfismista , 1:n yläpuolella olevien asteiden parametrisesta polymorfismista (ns. paikallisesti abstraktien tyyppien avulla , jotka toteuttavat eksistentiaalisia tyyppejä ) ja yleistettyjä algebrallisia tietotyyppejä .

Historia

Termi "polymorfismi" tulee kreikasta. πολύς ("paljon") ja μορφή ("muoto, muoto, laite").

Termit "erikoistunut polymorfismi" ja "parametrinen polymorfismi" mainitaan ensimmäisen kerran vuonna 1967 Christopher Stracheyn luentomuistiinpanoissa " Ohjelmointikielten perusteet [ " [1] . Vuonna 1985 Peter Wegner ja Luca Cardelli formalisoivat suojauspolymorfismin alatyyppien ja periytymisen [10] [27] mallintamiseen , vaikka alatyyppien ja periytymisen toteutukset ilmestyivät paljon aikaisemmin, Simula -kielellä vuonna 1967 . Inkluusiopolymorfismi perustuu rajoitettuun kvantifiointiin .

Parametrisen polymorfismin merkinnän λ-laskennan kehityksenä (kutsutaan F-järjestelmäksi ) kuvasi muodollisesti loogikko Jean-Yves Girard [50] [51] ( 1971 ), hänestä riippumatta samanlainen järjestelmä kuvattiin. Tietojenkäsittelytieteilijä John S. Reynolds [52] ( 1974 ).

Ensimmäinen kokonaan polymorfiseen λ-laskentaan perustuva kieli oli ML ( 1973 ); hänestä riippumatta parametriset tyypit toteutettiin Clu :ssa ( 1974 ) [27] . Monet nykyaikaiset kielet ( C++ , Java , C# , D ja muut) tarjoavat parametrityyppejä muodossa, joka on enemmän tai vähemmän lähellä niiden toteutusta Clu:ssa.

Vuonna 1987 Mitchel Wand formalisoi rivipolymorfismin ja tyyppipäätelmän sille [53] ; tällä työllä oli valtava vaikutus tyyppijärjestelmien myöhempään kehitykseen . Samana vuonna Philip Wadler ja Stephen Blot ehdottivat tyyppiluokkia [ ad-hoc-polymorfismin formalisoimiseksi . 

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 Strachey, 1967 .
  2. ↑ Cardelli, 1991 , s. 3.
  3. ↑ Pierce, 2012 , 22.7. Polymorfismi letin kautta, s. 354.
  4. ↑ 1 2 Cardelli, 1985 , s. 6.
  5. ↑ 1 2 3 4 5 Wadler, 1988 , s. 1-2.
  6. ↑ Bjarne Stroustrup . C++-sanasto (19. helmikuuta 2007). Arkistoitu alkuperäisestä 29. kesäkuuta 2018.
  7. ↑ Andrew W. Appel. Standard ML:n kritiikki . - Princetonin yliopisto, 1992.
  8. ↑ Harper, 2012 , 20.1 System F, s. 172.
  9. ↑ Pierce, 2012 , 23.2 Polymorfismin lajikkeet, s. 365.
  10. ↑ 1 2 3 Cardelli, 1985 .
  11. ↑ Mitchell, 2002 , 6.4. Polymorfismi ja ylikuormitus, s. 145-151.
  12. ↑ Cardelli, 1985 , 1.3. Polymorfismin tyypit, s. 6.
  13. ↑ 1 2 Cardelli, 1985 , s. 5-6.
  14. ↑ Cardelli, 1996 , 5 Toisen asteen tyyppijärjestelmät, s. 25.
  15. ↑ Harper, 2012 , 20.3 Yleiskatsaus parametreihin, s. 177.
  16. ↑ Harper, 2012 , 49 Parametricity, s. 495-508.
  17. ↑ Pierce, 2012 , 23.9 Parametricity, s. 384-385.
  18. ↑ Harper, 2012 , 21.4 Edustuksen riippumattomuus, s. 188.
  19. ↑ Pierce, 2012 , 30.5 Jatkossa: Riippuvaiset tyypit, s. 489-493.
  20. ↑ Reynolds, 1998 , 16. Alatyypit ja leikkaustyypit. Bibliografiset huomautukset, s. 376.
  21. ↑ Cardelli, 1985 .
  22. ↑ Mitchell, 2002 , 10.2.6 Periytys ei ole alatyypitystä, s. 287.
  23. ↑ Cardelli, 1991 .
  24. ↑ 1 2 Pierce, 2012 , 15 alatyypit, s. 193.
  25. ↑ 1 2 Pierce, 2012 , 15. Alatyypit, s. 193.
  26. ↑ Harper, 2012 , 23.1. Subsumtio, s. 208.
  27. ↑ 1 2 3 Pierce, 2012 , 1.4 Lyhyt historia, s. 11-13.
  28. ↑ Cardelli, 1991 , 6. Voimalajit, s. 32.
  29. ↑ 1 2 3 4 Abadi, Cardelli, 1994 .
  30. ↑ 1 2 3 Cardelli, 1985 , 6. Rajoitettu määrä, s. 28.
  31. ↑ Minsky kääntänyt DMK, 2014 , Alatyypit, s. 259.
  32. ↑ Cardelli, 1985 , s. 9.
  33. ↑ Harper, 2012 , luku 16. Rekursiiviset tyypit, s. 132.
  34. ↑ 1 2 Cardelli, 1991 , s. 35-37.
  35. ↑ Cardelli, 1985 , 2.3. Perustyypit, strukturoidut tyypit ja rekursio, s. 12-14.
  36. ↑ Harper, 2012 , luku 25. Dynamic Dispatch, s. 229.
  37. ↑ 1 2 Joyner, 1996 , 3.38 Signature Variance, s. 35.
  38. ↑ Olio-ohjelmointi vakio-ML:ssä . Haettu 11. maaliskuuta 2016. Arkistoitu alkuperäisestä 14. tammikuuta 2016.
  39. ↑ Minsky kääntänyt DMK, 2014 , luku 11. Objektit, s. 253.
  40. ↑ ML2000-työryhmä. ML2000:n periaatteet ja alustava suunnittelu . – 1999.
  41. ↑ Castagna, Ghelli, Longo. Laskenta ylikuormitetuille funktioille alatyypeillä  // Tiedot ja laskeminen. - Akateeminen lehdistö, 1995. - T. 117 , nro. 1 . - S. 115-135 . - doi : 10.1006/inco.1995.1033 .
  42. ↑ Joyner, 1996 , 2.8 Kapselointi, s. kahdeksan.
  43. ↑ Mitchell, 2002 , 6.2.1 Tyyppiturvallisuus, s. 132-133.
  44. ↑ Harper, 2012 , luku 4. Statiikka, s. 35.
  45. ↑ Pierce, 2012 , 31. Korkeamman asteen alatyypit, s. 495.
  46. ↑ 12 Wadler , 1988 , s. 3.
  47. ↑ Johan Jeuring. Monimuotoinen kuviosovitus  // FPCA. - 1995. - doi : 10.1.1.36.5645 .
  48. ↑ Ralf Lammel ja Joost Visser, "Typed Combinators for Generic Traversal", teoksessa Practical Aspects of Declarative Languages: 4th International Symposium (2002), s. 153.
  49. ↑ Patrik Jansson, Johan Jeuring. PolyP - Monimuotoinen ohjelmointikielen laajennus . - Sigplan SPPL, 1997.
  50. ↑ Girard - Tyyppiteorian laajennus, 1971 .
  51. ↑ Girard - Korkeamman asteen laskenta, 1972 .
  52. ↑ Reynolds, 1974 .
  53. ↑ Sauva, 1987 .

Kirjallisuus

  • Christopher Strachey. Ohjelmointikielten peruskäsitteet  . - 1967. Arkistoitu 12. elokuuta 2017.
    • Uudelleenjulkaistu: Christopher Strachey. Ohjelmointikielten peruskäsitteet  // Korkeamman asteen ja symbolinen laskenta  . - 2000. - Voi. 13 . - s. 11-49 . - doi : 10.1023/A:1010000313106 .
  • Jean-Yves Girard. Une Extension de l'Interpretation de Gödel à l'Analysis, et son Application à l'Élimination des Coupures dans l'Analysis et la Théorie des Types  (ranska)  // Proceedings of the Second Scandinavian Logic Symposium. - Amsterdam, 1971. - P. 63-92 . - doi : 10.1016/S0049-237X(08)70843-7 .
  • Jean-Yves Girard. Interprétation fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur  (ranska) . — Université Paris 7, 1972.
  • John C. Reynolds. Kohti tyyppirakenteen teoriaa // Tietojenkäsittelytieteen luentomuistiinpanot . - Paris: Colloque sur la programmation, 1974. - Vol. 19 . - S. 408-425 . - doi : 10.1007/3-540-06859-7_148 .
  • Luca Cardelli , Peter Wegner. Tyyppien, tietojen abstraktion ja polymorfismin ymmärtämisestä //ACM Computing Surveys. - New York, USA:ACM, 1985. -17,no. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.
  • Robert Harper . Standard ML:n esittely. - Carnegie Mellon University, 1986. - ISBN PA 15213-3891.
  • Käännös venäjäksi: Robert Harper . Standard ML:n esittely. - Carnegie Mellon University, 1986. - 97 s. — ISBN PA 15213-3891.
  • Mitchell Wand . Täydellinen tyyppipäätelmä yksinkertaisille objekteille // In Proc. Toinen IEEE-symposiumi logiikasta tietojenkäsittelytieteessä. - 1987. -s. 37-44.
  • Philip Wadler, Stephen Blott. Kuinka tehdä ad hoc -polymorfismista vähemmän ad hoc  . – 1988.
  • Luca Cardelli . Tyypillinen ohjelmointi // IFIP State-of-the-Art -raportit. - New York: Springer-Verlag, 1991. -Iss. Ohjelmointikäsitteiden muodollinen kuvaus. -s. 431-507.
  • Martin Abadi, Luca Cardelli . Objektityyppien  semantiikka . — LICS , 1994.
  • Luca Cardelli . Tyyppijärjestelmät (englanti) // Tietojenkäsittelytieteen ja -tekniikan käsikirja. - CRC Press, 1996.
  • John C. Reynolds. Ohjelmointikielten teoriat . - Cambridge University Press, 1998. - ISBN 978-0-521-59414-1 (kovakantinen), 978-0-521-10697-9 (nidottu).
  • Benjamin Pierce. Tyypit ja ohjelmointikielet  . - MIT Press , 2002. - ISBN 0-262-16209-1 .
    • Käännös venäjäksi: Benjamin Pierce. Ohjelmointikielien tyypit . - Dobrosvet , 2012. - 680 s. — ISBN 978-5-7913-0082-9 .
  • John C. Mitchell Ohjelmointikielten  käsitteet . - Cambridge University Press, 2002. - 540 s. - ISBN 978-0-521-78098-8 .
  • Minsky, Madhavapeddy, Hickey. Real World OCaml: Funktionaalinen ohjelmointi  massoille . - O'Reilly Media, 2013. - 510 s. — ISBN 9781449324766 .
    • Käännös venäjäksi: Minsky, Madhavapeddy, Hickey. Ohjelmointi OCaml-kielellä . - DMK, 2014. - 536 s. — (Toimintaohjelmointi). - ISBN 978-5-97060-102-0 .