Polimorfizmus (számítástechnika)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 25-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

A polimorfizmus a programozási nyelvekben és a típuselméletben  egy függvény azon képessége, hogy különböző típusú adatokat dolgozzon fel [1] [2] [3] .

A polimorfizmusnak többféle típusa van. Két alapvetően különbözőt írt le Christopher Strachey 1967 - ben : ezek a parametrikus polimorfizmus és az ad-hoc polimorfizmus , a többi alak pedig ezek alfajai vagy kombinációi. A paraméteres polimorfizmus igaz, mert azt jelenti , hogy ugyanazt a kódot kell végrehajtani minden érvényes argumentumtípushoz, és az ad-hoc polimorfizmus képzeletbeli, mert célja, hogy biztosítsa a potenciálisan különböző végrehajtható kódok kozmetikai egységességét minden egyes argumentumtípushoz [1] [4] . Ugyanakkor vannak olyan helyzetek, amikor pontosan ad-hoc polimorfizmust kell alkalmazni, nem parametrikusan [5] . A minősített típusok elmélete mindenféle polimorfizmust egyetlen modellben egyesít.

A polimorfizmus széles körben elterjedt meghatározása Björn Stroustrupnak tulajdonítható : " egy interfész (deklarációk listájaként) - sok implementáció (ezekhez a deklarációkhoz kapcsolódó definíciók) " [6] , de csak az ad-hoc polimorfizmus (képzeletbeli polimorfizmus) tartozik ebbe a körbe. meghatározás.

Általános információk

Ugyanazon kód alapvető lehetőségét különböző típusú adatok feldolgozására a nyelv típusrendszerének tulajdonságai határozzák meg . Ebből a szempontból megkülönböztetünk [7] statikus nem polimorf tipizálást ( Algol és BCPL leszármazottai ), dinamikus tipizálást ( Lisp , Smalltalk , APL leszármazottai ) és statikus polimorf tipizálást ( ML leszármazottai ). Az ad-hoc polimorfizmus alkalmazása leginkább a nem polimorf tipizálásra jellemző. A paraméteres polimorfizmus és a dinamikus tipizálás sokkal többet növeli a kód újrafelhasználását , mint az ad-hoc polimorfizmus, mivel az egyszer definiált függvény a megadott viselkedést duplikáció nélkül valósítja meg végtelen számú újonnan definiált típusnál, amelyek kielégítik a függvényben megkövetelt feltételeket. Másrészt néha szükségessé válik a függvény más viselkedésének biztosítása a paraméter típusától függően, és ilyenkor speciális polimorfizmusra van szükség.

A paraméteres polimorfizmus a típusabsztrakció szinonimája [8] . Mindenütt jelen van a funkcionális programozásban , ahol általában egyszerűen "polimorfizmusnak" nevezik.

Az objektum-orientált programozói közösségben a "polimorfizmus" kifejezés általában öröklődést jelent , a parametrikus polimorfizmus használatát pedig általános programozásnak [9] , vagy néha "statikus polimorfizmusnak" nevezik.

Osztályozás

A polimorfizmus fajtáinak osztályozását először Christopher Strachey végezte .

Ha egy függvényparaméterhez pontosan egy típus tartozik, akkor az ilyen függvényt monomorfnak nevezzük. Sok programozási nyelv szintaktikai mechanizmust biztosít egyetlen név (azonosító) hozzárendelésére több monomorf függvényhez. Ebben az esetben a forráskódban lehetővé válik egy függvény meghívása különböző típusú tényleges paraméterekkel, de a lefordított kódban valójában más függvények hívódnak meg (lásd eljárás és függvény túlterhelés ). Strachey „ad-hoc polimorfizmusnak” nevezte ezt a lehetőséget.

Ha egy függvényparaméterhez egynél több típus tartozik, akkor az ilyen függvényt polimorfnak nevezzük . Természetesen minden tényleges értékhez csak egy típus rendelhető, de egy polimorf függvény a paramétereket külső tulajdonságok alapján veszi figyelembe, nem a saját szervezetét és tartalmát. Strachey ezt a lehetőséget "paraméteres polimorfizmusnak" nevezte.

Később az osztályozást Luca Cardelli [10] finomította , kiemelve a polimorfizmus négy típusát:

Egyes munkákban a parametrikus, ad-hoc és altípusú polimorfizmust a polimorfizmus három független osztályaként különböztetik meg [11] .

Az "ad hoc" kifejezés jelentésének kettőssége (egyrészt - "spontán, rosszul kitalált, alkalomból készült", másrészt - "különleges, kifejezetten adott célra vagy alkalomra rendezett") évek óta megérdemelt [5] . Strachey ezt a kifejezést az első jelentés alapján választotta, hangsúlyozva, hogy az ad-hoc polimorfizmus esetén nincs egyetlen szisztematikus módszer arra, hogy az érvek típusából következtessen az eredmény típusára, és bár lehetséges egy bizonyos szabályrendszer felépítése szűkítik a keresési spektrumot, ezek a szabályok spontán jellegűek, mind tartalmilag, mind alkalmazási kontextusban [1] .

Valójában az ad-hoc polimorfizmus nem valódi polimorfizmus [12] . A függvénytúlterhelés nem "több típusú értéket" eredményez, hanem "több típusú karaktert ", de az ezzel a szimbólummal azonosított értékek különböző (potenciálisan inkompatibilis) típusúak. Hasonlóképpen, az öntés nem valódi polimorfizmus: úgy tűnik, hogy az operátor sokféle értéket elfogad, de az értékeket át kell alakítani valamilyen reprezentációra, mielőtt használni tudná őket, hogy az operátor ténylegesen csak egy típussal működjön (pl. egy típusa van). Ráadásul a visszatérési érték típusa itt nem függ a bemeneti paraméter típusától , mint a parametrikus polimorfizmus esetében.

A különböző típusú függvények konkrét implementációinak meghatározása azonban bizonyos esetekben szükségszerűség, nem pedig véletlen. Klasszikus példák erre az aritmetikai műveletek (az egész számok és a lebegőpontos számok fizikailag eltérő ) és a típusegyenlőség megvalósítása, amelyeknek évtizedekig nem volt elfogadott univerzális formalizálása. A megoldást a típusosztályok jelentették, amelyek egy mechanizmus a típusváltozók megengedett értékeinek explicit diszkrét felsorolására a típusrétegben történő statikus elküldéshez. Összehozzák a Strachey által szétválasztott polimorfizmus két változatát, „ az ad-hoc polimorfizmust kevésbé ad hoc ” [5] ( a kettősségre játszva ). A típusosztályok további általánosítása a minősített típusok elméletének megalkotásához vezetett , amely egységesen formalizálja a legegzotikusabb típusrendszereket, beleértve a bővíthető jelöléseket és az altípusokat.

Ellentétben a túlterheléssel és a típusöntéssel , az altípus - polimorfizmus valódi polimorfizmus: az altípus-objektumok egységesen manipulálhatók, mintha a szupertípusukhoz tartoznának (de ez nem igaz azokra a nyelvekre, amelyek az "öröklődés útján történő polimorfizmust" öntéssel valósítják meg típusok és funkciók túlterhelése , mint a C++ esetében ). A legtisztább a parametrikus polimorfizmus : ugyanaz az objektum vagy függvény egységesen használható különböző gépelési kontextusokban, módosítások, öntések vagy bármilyen más futásidejű ellenőrzés vagy átalakítás nélkül. Ehhez azonban szükség van az adatok valamilyen egységes ábrázolására (például mutatókon keresztül ) [4] .

A polimorfizmus alaptípusai

Ad-hoc polimorfizmus

Az ad-hoc polimorfizmus (az orosz szakirodalomban leggyakrabban „speciális polimorfizmusnak” vagy „specializált polimorfizmusnak” fordítják, bár mindkét lehetőség nem mindig igaz ) számos nyelven támogatott funkció- és módszer-túlterhelés révén , valamint gyengén tipizált típusöntéssel  is . _

A következő példában ( Pascal nyelv ) a függvények Addúgy néznek ki, mintha ugyanazt a funkcionalitást valósítanák meg különböző típusokon, de a fordító két teljesen különböző függvényként határozza meg őket.

program Adhoc ; függvény Add ( x , y : Integer ) : Integer ; kezdődik Add := x + y end ; function Add ( s , t : String ) : String ; begin Add := Concat ( s , t ) end ; begin Writeln ( Add ( 1 , 2 )) ; Writeln ( Add ( 'Hello, ' , 'Világ!' )) ; vége .

A dinamikusan tipizált nyelvekben a helyzet bonyolultabb lehet, mivel a meghívandó függvény kiválasztása csak futás közben lehetséges.

A túlterhelés  egy szintaktikai mechanizmus, amely lehetővé teszi különböző függvények egyetlen azonosítóval történő meghívását [13] . A típusöntés  egy szemantikai mechanizmus, amelyet az argumentum tényleges típusának a függvény várt típusává alakítására hajtanak végre, amely nélkül típushiba lépne fel . Azaz ha egy függvényt típuscasttal hívunk meg, akkor a különböző típusokhoz más-más kód fut le (magának a függvénynek a meghívása előtt) [13] .

Paraméteres polimorfizmus

A paraméteres polimorfizmus lehetővé teszi egy függvény vagy adattípus általános meghatározását, így az értékeket típusuktól függetlenül azonos módon kezelik. A parametrikusan polimorf függvény nem értékalapú, hanem viselkedés alapú argumentumokat használ, csak a számára szükséges argumentumok tulajdonságaihoz fér hozzá, így bármilyen környezetben használható, ahol az objektumtípus megfelel az adott viselkedési követelményeknek.

A fejlett típusú rendszerek (például a Hindley-Milner rendszer ) olyan mechanizmusokat biztosítanak a polimorf típusok meghatározásához , amelyek kényelmesebbé teszik a polimorf függvények használatát, és statikus típusbiztonságot nyújtanak . Ilyen rendszerek a másodrendű típusú rendszerek, amelyek az elsőrendű típusú (a legtöbb procedurális nyelvben használatos ) rendszerhez adják hozzá a típusparaméterezést (típusváltozó segítségével ) és a típusabsztrakciót ( ezek feletti egzisztenciális kvantifikáció segítségével ). A másodrendű típusú rendszerekben nincs azonnali szükség a primitív típusok támogatására , mivel ezek fejlettebb eszközökkel fejezhetők ki. [tizennégy]

A polimorf típus klasszikus példája tetszőleges típusú elemek listája , amelyekhez sok Hindley-Milner típusú nyelv (a legtöbb statikusan tipizált funkcionális programozási nyelv ) szintaktikai cukrot biztosít . A következő példa egy új algebrai típusú "parametrikusan polimorf lista " és két függvény definícióját mutatja be:

adatok Lista a = nulla | Hátrányok a ( lista a ) hossz :: a lista -> Egész hossz Nil = 0 hosszúság ( Cons x xs ) = 1 + hosszúság xs térkép :: ( a -> b ) -> List a -> List b map f Nil = Nulla térkép f ( Cons x xs ) = Cons ( f x ) ( map f xs )

Ha a betontípusokat típusváltozóval helyettesíti , és így tovább, a betontípusok megépülnek, és így tovább. Ezeket a bizonyos típusokat viszont újra be lehet cserélni az adott típusváltozóba , típusokat hozva létre , és így tovább. Ebben az esetben az összes felépített típusú objektumhoz a és függvények ugyanaz a fizikai megvalósítása lesz használva . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

A parametrikus polimorfizmus korlátozott formái bizonyos kötelező (különösen objektum-orientált ) programozási nyelvekben is elérhetők, ahol általában az " általános programozás " kifejezést használják rá. Különösen a C nyelvben a tipizálatlan parametrikus polimorfizmust hagyományosan egy tipizálatlan mutató void* használatával biztosítják , bár lehetséges a tipizált forma is. A C++ sablonok használata felületesen hasonlít a parametrikus polimorfizmushoz, de szemantikailag ad-hoc mechanizmusok kombinációjával valósítják meg; a C++ közösségben "statikus polimorfizmusnak" nevezik (szemben a "dinamikus polimorfizmussal" ).

Parametrikus

A parametrikus polimorfizmus formalizálása elvezet a parametricitás fogalmához , amely abból áll, hogy képesek vagyunk előre jelezni a programok viselkedését, ha csak a típusukat nézzük. Például, ha egy függvény " forall a. a -> a" típusú, akkor a nyelvet kiegészítő külső eszközök nélkül igazolható , hogy csak azonos lehet . Ezért a parametricitást gyakran a "tételek ingyen" ( eng.  theorems for free ) szlogen kíséri . [15] [16] [17]

Ennek fontos következménye a  reprezentációs függetlenség is , ami azt jelenti, hogy egy absztrakt típus feletti függvények érzéketlenek annak szerkezetére, és az ilyen típusú különböző implementációk szabadon helyettesíthetik egymást (akár ugyanazon a programon belül is), anélkül, hogy ezek a függvények viselkedését befolyásolnák. [18] .

A legfejlettebb parametrikusan polimorf rendszerek ( a lambda-kocka legmagasabb pontja ) a paraméterezés gondolatát egészen addig a pontig viszik, hogy teljes mértékben igazolni tudják a programok helyességét : lehetővé teszik olyan programok megírását, amelyek tervezésüknél fogva helyesek, így az átadás a típuskonzisztencia-ellenőrzés önmagában garantálja a program helyes működését.várható [19] .

Rekord és variáns polimorfizmus

Külön probléma a parametrikus polimorfizmus kiterjesztése aggregált típusokra: a típusok megkülönböztetett szorzataira (hagyományosan rekordoknak ) és a típusok megkülönböztetett összegeire (más néven variáns típusokra ). Az objektum-orientált és moduláris programozás formális alapjául különféle „ rekordkalkulus ” ( angolul record calculi ) szolgál [20] .  

val r = { a = 1 , b = igaz , c = "helló" } val { a = n , ... = r1 } = r val r2 = { d = 3,14 , ... = r1 }

Az ellipszis bizonyos számú beírt mezőt jelent, vagyis a kód egy adott típusú rekordtól való absztrakcióját , amely itt feldolgozható (és ennek a sorozatnak a „hossza” is változhat). A különböző rekordokban eltérő sorrendben elhelyezhető mezők polimorf hozzáférésének összeállítása nehéz probléma, mind a nyelvi szintű műveletek biztonságának ellenőrzése , mind a gépi kód teljesítménye szempontjából. szint. Naiv megoldás lehet minden hívásnál dinamikusan megkeresni a szótárt (és a szkriptnyelvek ezt használják), de ez nyilvánvalóan rendkívül nem hatékony. Ezt a problémát több évtizede aktívan tanulmányozták; számos elméleti modell és ezekre épülő gyakorlati rendszer épült, amelyek kifejezőerőben és metaelméleti bonyolultságban különböznek egymástól. A legfontosabb vívmányok ezen a területen a Mitchell Wand által javasolt in-line polimorfizmus és az Atsushi Ohori által készített polimorf rekordszámítás . Egy elterjedtebb, de sok jellemzőben lemaradt modell a rekordok altípusa .   

A rekord polimorfizmus ilyen vagy olyan formában történő támogatása lehetőségeket nyithat meg egy polimorf nyelvben, mint például a magasabb rendű üzenetek (az objektum-orientált programozás legerősebb formája ), a műveletek zökkenőmentes beágyazása adatbázis - elemekre ( SQL ) általános célú nyelvi kód és mások, egészen a bővíthető programozásig (vagyis az kifejezési problémától mentes programozásig ), garantálva a kezeletlen kivételek hiányát a programokban, és a metaprogramozás bizonyos formáit .

Altípus polimorfizmus

Az inklúziós polimorfizmus az altípus és az öröklődés [21] általánosított formalizálása. Ezeket a fogalmakat nem szabad összekeverni: az altípusok az interfész szintjén, míg az öröklődés a megvalósítás szintjén [22] definiálják a kapcsolatokat.

Az altípus ( altípus ) vagy altípus polimorfizmus ( altípus polimorfizmus ) azt jelenti, hogy a parametrikusan polimorf függvény viselkedése egy szupertípus -altípus hierarchiában határolt típushalmazra korlátozódik [23] [10] [24] . Például, ha vannak , és típusok , amelyeket a és relációk korlátoznak , akkor a típuson definiált függvény képes lesz a vagy típusú argumentumokat is elfogadni , és viselkedése azonos lesz. Az objektum tényleges típusa elrejthető "fekete dobozként", és csak az objektum azonosítására vonatkozó kérésre biztosítható. Valójában, ha egy típus absztrakt, akkor az adott típusú konkrét objektum nem is létezhet (lásd absztrakt osztály , de nem tévesztendő össze az absztrakt adattípussal ). Ez a típushierarchia (különösen a Scheme nyelv kontextusában ) számtorony néven ismert , és általában több típust is tartalmaz. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

Az altípusozás gondolatát a már megírt függvényekkel kezelhető típuskészlet növelése motiválja, és ezáltal erős gépelés esetén a kód újrafelhasználási aránya (azaz a begépelt programok készletének növelése ). Ezt a szubszumkciós szabály biztosítja : " ha egy kifejezés típushoz tartozik egy gépelési környezetben , és igaz , akkor az is a típushoz tartozik " [25] [26] . et'Гt'<:tet

Az altípus-kapcsolatok a típuskategóriák széles skálájában lehetségesek: primitív típusok (as Integer <: Number), összegtípusok , terméktípusok , funkcionális típusok stb. Ezen túlmenően Luca Cardelli javasolta a hatványfajták ( „ hatalom” típusok ) fogalmát a leírásra. altípus [27] : a típus [ 28 ] hatalmi fajtájaként az összes altípusának nemzetségét nevezte meg .

A számítástechnikában különleges helyet foglal el a rekordokon történő altípusozás .

A rekordok altípusa

Az objektum-orientált programozás (OOP) [29] [30] [24] [31] legáltalánosabb elméleti indoklása a rekordaltípus , más néven szubszumkció ( lásd Barbara Liskov  helyettesítési elvét ) [ 29] [30] [24] [31] (de nem az egyetlen – lásd # rekord és variáns polimorfizmus ).

Martín Abadi és Luca Cardelli formalizálta a rekordok altípusát a paraméteresen polimorf típusok feletti korlátozott kvantifikációval [29] [30] ; míg a típus paraméter implicit módon van beállítva [32] .

A rekordok altípusának meghatározásánál két fajtát különböztetünk meg: szélességben és mélységben.

A szélesség altípusa új mezők hozzáadását jelenti egy rekordhoz . Például:

type Object = { kor: Int } típus Jármű = { kor: Int; sebesség: Int} típus Kerékpár = { kor: Int; sebesség: Int; fogaskerék: Int; } typeMachine = { age: Int; üzemanyag: húr

Egyrészt felírható a Vehicle <: Object, Bike <: Vehicle(és mivel az altípusozás tranzitív , akkor és Bike <: Object) és Machine <: Object. Másrészt azt mondhatjuk, hogy típusok Vehicle, Bikeés Machine tartalmazzák (öröklik) a típus összes tulajdonságát Object. (Itt a típusrendszer szerkezeti szemantikája van benne )

Mivel egy típust gyakran intuitív módon értékek halmazának tekintenek, az altípus mezőinek számának növelése halmazelméleti szempontból ellentétes lehet az intuitív hatásokkal . A valóságban a típusok nem halmazok [33] , hanem a programok viselkedésének ellenőrzésére szolgálnak, és az altípusozás lényege az, hogy egy altípus legalább a szupertípusának tulajdonságaival rendelkezik, és így legalább emulálni tudja. ahol egy objektum szupertípusra számít [25] . Vagy más szóval: egy szupertípus meghatározza az objektumok egy minimális tulajdonságkészletét, majd egy típus, amely rendelkezik ezekkel a tulajdonságokkal és esetleg még néhány más tulajdonsággal, ennek a halmaznak egy részhalmazát képezi, és ezért az altípusa [30] .

Az altípus-kapcsolatok halmazok tekintetében intuitívabbak a változattípusok esetében [34] :

típus Nap = hétfő | ked | esküvő | cs | péntek | ült | nap típus Munkanap = hétfő | ked | esküvő | cs | fri típus WeekEnd = szombat | nap

Itt Workday <: Dayés WeekEnd <: Day.

A mezők elnevezése lehetővé teszi, hogy elvonatkoztassunk a rekordokban való előfordulásuk sorrendjétől (ellentétben a sorokkal ), ami lehetővé teszi tetszőleges irányított aciklikus öröklődési gráfok felépítését, formalizálva a többszörös öröklődést [34] :

típus Autó = { kor: Int; sebesség: Int; üzemanyag: húr

Most Car <: Vehicleés ugyanabban az időben Car <: Machine. Az is nyilvánvaló, hogy Car <: Object(lásd rombusz alakú öröklődés ).

A mélységi altípusok azt jelentik, hogy az adott rekordmezők típusai helyettesíthetők altípusaikkal :

type Voyage = { veh: Jármű; dátum: nap típus Sport = { veh: Bike; dátum: nap típus Nyaralás = { veh: Autó; dátum: hétvége }

A fenti definíciókból arra következtethetünk , hogy Sports <: Voyageés Vacation <: Voyage.

Módszerek rekordaltípusokban

Az objektum-orientált programozás teljes körű támogatása azt jelenti, hogy a rekordmezők számába olyan funkciókat is bele kell foglalni, amelyek feldolgozzák azon rekordtípusok értékeit, amelyekhez tartoznak [29] [35] . Az ilyen függvényeket hagyományosan " metódusoknak " nevezik. A rekordok metódusokhoz való kötésének általánosított modellje a küldési mátrix ; a gyakorlatban a legtöbb nyelv sorokban vagy oszlopokban lévő vektorokra bontja – rendre osztály-alapú vagy módszer-alapú szervezetet valósít meg [36 ] . Ugyanakkor különbséget kell tenni az altípusok felülbíráló metódusai ( metódus felülbírálata ) és az altípus- függvények ( functional subtyping ) között. A felülbíráló metódusok nem kötik őket altípus-kapcsolatokkal a függvényeken, hanem lehetővé teszik a típusaláírásuk megváltoztatását. Ebben az esetben három lehetőség lehetséges: invariáns, kovariáns és kontravariáns újradefiníció, az utolsó kettő pedig a paramétereik altípusát használja [37] (további részletekért lásd a kovariancia és kontravariancia című részt ). Az Abadi-Cardelli-számítás [29] csak invariáns módszereket vesz figyelembe, ami a biztonság bizonyításához szükséges .

Sok objektum-orientált nyelv beépített mechanizmust biztosít a függvények metódusokba való kötésére , így valósítja meg a programok osztályalapú szervezését. Azok a nyelvek, amelyek a függvényeket első osztályú objektumként kezelik és begépelik (lásd első osztályú függvények , funkcionális típus  - nem tévesztendő össze a függvény visszatérési típusával ) tetszőleges metódus alapú szervezést tesznek lehetővé, amely lehetővé teszi az objektumorientált tervezést közvetlen támaszték a nyelv oldalairól [38] . Egyes nyelvek (például az OCaml ) mindkettőt támogatják.

A formális altípus-elméletre épülő típusrendszerű nyelvek ( OCaml , az utóda ML projekt) egymástól függetlenül kezelik az objektumrendszereket és az osztályrendszereket [39] [40] . Ez azt jelenti, hogy az objektumtípus elsődlegesen egy objektumhoz van társítva , és csak akkor van társítva egy bizonyos osztályhoz, ha kifejezetten meg van adva. Ebben az esetben a dinamikus diszpécser objektumszinten történik, ami azt jelenti, hogy ilyen nyelvekben két azonos osztályba tartozó objektum általában eltérő metóduskészlettel rendelkezhet. A többszörös öröklődés formálisan meghatározott szemantikájával együtt ez azonnali átfogó támogatást ad a mixineknek .

A CLOS a teljes diszpécsermátrixot multimetódusokon keresztül valósítja meg , vagyis olyan dinamikusan elküldött metódusokon, amelyek egyszerre több argumentumban polimorfak [41] .

Egyes nyelvek sajátos ad-hoc] megoldásokat alkalmaznak. Például a C++ nyelvi típusrendszer automatikus típusöntést biztosít (azaz gyenge ), nem polimorf , emulálja az altípust manifeszt öröklődésen keresztül invariáns metódus-aláírásokkal, és nem támogatja a típusabsztrakciót (nem összetévesztendő). mezei rejtéssel ) . A C++- ban az öröklődést egy sor ad-hoc mechanizmus valósítja meg, azonban használatát a nyelvi közösségben „polimorfizmusnak” nevezik (a mezőrejtőzést pedig „absztrakciónak” [42] ). Lehetőség van az öröklődési gráf vezérlésére: a rombusz alakú öröklődést C++-ban " virtuális öröklődésnek " nevezik , és egy explicit attribútum határozza meg ; alapértelmezés szerint az örökölt mezők megkettőződnek, és minősített névvel érhetők el. Egy ilyen nyelv használata nem biztonságos  - nem garantálható a programok stabilitása [43] [37] (egy nyelvet biztonságosnak nevezünk , ha a benne lévő programok, amelyeket a fordító jól formáltként el tud fogadni, soha nem lépnek túl a dinamikában megengedett viselkedés [44] ). virtual

Magasabb rendű altípusok

A rendszer az F rendszer kiterjesztése (nem szerepel a lambda-kockában ), amely korlátozott kvantifikációt formalizál a típusoperátorokkal szemben , kiterjesztve az altípus-kapcsolatokat a nemzetségről a magasabb nemzetség típusaira . A rendszernek számos változata létezik , amelyek kifejezőerőben és metaelméleti összetettségben különböznek egymástól, de a legtöbb fő gondolatot Luca Cardelli [45] fogalmazta meg . *

A polimorfizmus fajtáinak kombinációja

Típus osztályok

A típusosztály egyetlen független virtuális metódustáblát valósít meg sok ( univerzálisan számszerűsített ) típushoz. Ily módon a típusosztályok eltérnekaz objektum-orientált programozás osztályaitól , ahol minden ( korlátozott kvantifikált ) típusú objektumot egy virtuális metódustáblára mutató mutató kísér [46] . A típusosztályok nem típusok, hanem típuskategóriák; példányaik nem értékek, hanem típusok.

Például [46] :

osztály Num a ahol ( + ), ( * ) :: a -> a -> a tagadás :: a -> a

Ez a deklaráció így hangzik: " Egy típus akkor atartozik egy osztályhoz , Numha (+), (*)és függvények vannak definiálva rajta negatea megadott aláírásokkal ."

példány Num Int ahol ( + ) = addInt ( * ) = mulInt negate = negInt példány Num Float ahol ( + ) = addFloat ( * ) = mulFloat negálás = negFloat

Az első deklaráció a következő: " Vannak függvények (+)és (*)megfelelő negatealáírások, amelyek a típuson belül vannak meghatározvaInt ." A második állítás is hasonlóan hangzik.

Most már helyesen beírhatja a következő függvényeket (és a típuskövetkeztetés eldönthető ):

négyzet :: Num a => a -> a négyzet x = x * x négyzetek3 :: Num a , Num b , Num c => ( a , b , c ) -> ( a , b , c ) squares3 ( x , y , z ) = ( négyzet x , négyzet y , négyzet z )

Mivel a szorzási művelet fizikailag eltérően valósul meg egész számok és lebegőpontos számok esetén, típusosztályok hiányában itt már két túlterhelt függvényre squareés nyolc túlterhelt függvényre lenne szükség squares3, a valós, összetett adatszerkezetű programokban pedig sokkal több a duplikált kód. . Az objektum-orientált programozásban az ilyen jellegű problémákat dinamikus elküldéssel oldják meg , a hozzá tartozó többletköltséggel. A típusosztály statikusan diszpéciál, egyetlen modellbe hozva a parametrikus és az ad-hoc polimorfizmusokat [5] . A parametrikus polimorfizmus szempontjából egy típusosztálynak van egy paramétere ( a type változó ), amely egy típushalmazt ölel fel. Az ad-hoc polimorfizmus szempontjából ez a halmaz nem csak diszkrét, hanem a megvalósítás szintjéig kifejezetten meghatározott is. Egyszerűen fogalmazva, az aláírás azt jelenti, hogy a függvény parametrikusan polimorf , de paraméterének típusai csak azokra a típusokra korlátozódnak, amelyek a típusosztályba tartoznak . Emiatt a függvény egyedi módon kerül beírásra, annak ellenére, hogy a testéből hívják a túlterhelt függvényt. square :: Num a => a -> aNum

A típusosztályok natív támogatása először a Haskellben valósult meg , de egyszerű előfeldolgozással [5] is bevezethetők bármilyen parametrikusan polimorf nyelvbe, és idiomatikusan is implementálhatók (lásd például az ML modul nyelve#Implementing Alternative Models ). A közvetlen támogatás azonban megkönnyítheti a programok jelentésével kapcsolatos automatikus érvelést .

Az egyenlőségtípusok a Haskellben egy típusosztály példányaiként valósulnak meg ( egyenlőségi típusú változókEq általánosításaa Standard ML -ből ) :

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

A felhasználó által definiált típusok néhány gyakran nyilvánvalóan szükséges tulajdonságának kódolásával járó nehézségek csökkentése érdekében a Haskell emellett szintaktikai cukrot is biztosít  , egy olyan konstrukciót deriving, amely korlátozott számú szabványos típusosztályra (például Eq) érvényes. (Az orosz nyelvű közösségben a „ származik ” szó fordításának sajátosságai miatt a használatát gyakran összekeverik az „ öröklődés ” fogalmával .)

Általános algebrai adattípusok

Politipizmus

Néha használatos a „politipizmus” vagy az „adattípus-általánosítás” kifejezés. A politipizálás lényegében a nyelv beépített támogatására utal a típuskonstruktor polimorfizmusra , amely a programozási felületek egységesítésére és a kód újrafelhasználásának növelésére szolgál . A politipizmusra példa az általánosított mintaillesztési algoritmus [47] .

Definíció szerint egy politípus függvényben „ bár lehet, hogy bizonyos típusokhoz véges számú ad-hoc ág létezik, nincs ad-hoc kombinátor ” [48] .

A politipizálás megvalósítható általános adattípus vagy magasabb rangú polimorfizmus használatával . A Haskell PolyP [49] kiterjesztése egy szintaktikai konstrukció, amely leegyszerűsíti a Haskell politípus függvényeinek meghatározását .

A politipikus függvény bizonyos értelemben általánosabb, mint egy polimorf függvény, másrészt azonban egy függvény lehet politípusos, és nem polimorf, amint az a következő függvénytípus -aláírásokból látható :

fej :: [ a ] ​​​​-> a ( + ) :: Num a => a -> a -> a long :: Regular d => d a -> Int sum :: Regular d => d Int -> Int

Az első függvény ( head) polimorf (parametrikusan polimorf ), a második (az infix operátor „ ”) túlterhelt (ad-hoc-polimorf), a harmadik és a negyedik politípusos: a típusváltozó definíciójában típusonként változik konstruktorok . Ugyanakkor a harmadik függvény ( ) politípusos és polimorf (feltehetően a polimorf aggregátumtípusok valamelyik halmazának "hosszát" számítja ki - például a listákban és a fákban lévő elemek számát ), a negyedik ( ) pedig politípusos, de nem polimorf (a típusosztályhoz tartozó aggregátumtípusok feletti monomorf , amelyhez valószínűleg egy adott aggregátumtípus objektumát képező egész számok összegét számítja ki). + dlengthsum Regular

Vegyes

A dinamikusan tipizált nyelvek egységesen a polimorfizmus különböző változatait képviselik, amelyek sajátos ideológiát alkotnak bennük, és hatással vannak az alkalmazott feladatbontási módszertanokra. Például a Smalltalk -ban bármely osztály képes bármilyen típusú üzenetet fogadni, és vagy önmagában feldolgozni (beleértve az introspekciót is ), vagy továbbítani egy másik osztálynak - így bármely metódus formálisan parametrikusan polimorf, míg belső szerkezete elágazhat a dinamikus argumentumtípus feltétele szerint, speciális polimorfizmust megvalósítva. A CLOS -ban a multimetódusok egyidejűleg első osztályú függvények , ami lehetővé teszi számunkra, hogy korlátozottan kvantifikáltnak és általánosítottnak ( igazi polimorfnak ) tekintsük őket .

Ezzel szemben a statikusan polimorf típusú nyelvek ortogonálisan (egymástól függetlenül) képesek a polimorfizmus különböző változatait megvalósítani, lehetővé téve azok bonyolult, típusbiztos módon történő felépítését. Például az OCaml támogatja a parametrikus osztályokat (a C++ osztálysablonokhoz hasonló képességekkel , de példányosítás nélkül ellenőrizhető), szélességük és mélységük öröklődését ( többször is ), típusosztályok idiomatikus megvalósítását (aláírásokon keresztül - lásd a megfelelő példát az ML modulnyelv használatára , a soros polimorfizmusra , az 1 feletti rangok parametrikus polimorfizmusára (az egzisztenciális típusokat megvalósító ún. lokálisan absztrakt típusok segítségével ) és az általánosított algebrai adattípusokra .

Történelem

A "polimorfizmus" kifejezés a görögből származik. πολύς ("sok") és μορφή ("forma, forma, eszköz").

A „specializált polimorfizmus” és a „paraméteres polimorfizmus” kifejezéseket először 1967 -ben említik Christopher Strachey „ A programozási nyelvek alapjai [ ” [1] című előadási jegyzeteiben . 1985 -ben Peter Wegner és Luca Cardelli formalizálta az elzáródási polimorfizmust az altípusok és az öröklődés [10] [27] modellezésére , bár az altípusok és az öröklődés implementációi jóval korábban, a Simula nyelven 1967 -ben jelentek meg . Az inklúziós polimorfizmus korlátozott mennyiségi meghatározáson alapul .

A parametrikus polimorfizmus jelölését a λ-kalkulus továbbfejlesztéseként (úgynevezett F-rendszer ) formálisan Jean-Yves Girard [50] [51] ( 1971 ) logikus írta le, tőle függetlenül egy hasonló rendszert írt le. John S. Reynolds informatikus [52] ( 1974 ).

Az első teljesen a polimorf λ-kalkuluson alapuló nyelv az ML volt ( 1973 ); tőle függetlenül parametrikus típusokat valósítottak meg Clu -ban ( 1974 ) [27] . Számos modern nyelv ( C++ , Java , C# , D és mások) paraméteres típusokat biztosít olyan formában, amely többé-kevésbé közel áll a Clu-ban való megvalósításukhoz.

1987-ben Mitchel Wand formalizálta az inline polimorfizmust és típuskövetkeztetést [53] ; ez a munka óriási hatással volt a típusrendszerek későbbi fejlesztésére . Ugyanebben az évben Philip Wadler és Stephen Blot típusosztályokat javasolt az ad-hoc polimorfizmus formalizálására . 

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 Strachey, 1967 .
  2. ↑ Cardelli, 1991 , p. 3.
  3. ↑ Pierce, 2012 , 22.7. Polimorfizmus a leten keresztül, p. 354.
  4. ↑ 1 2 Cardelli, 1985 , p. 6.
  5. ↑ 1 2 3 4 5 Wadler, 1988 , p. 1-2.
  6. ↑ Bjarne Stroustrup . C++ szószedet (2007. február 19.). Az eredetiből archiválva : 2018. június 29.
  7. ↑ Andrew W. Appel. A Standard ML kritikája . – Princetoni Egyetem, 1992.
  8. ↑ Harper, 2012 , 20.1 System F, p. 172.
  9. ↑ Pierce, 2012 , 23.2. A polimorfizmus fajtái, o. 365.
  10. ↑ 1 2 3 Cardelli, 1985 .
  11. ↑ Mitchell, 2002 , 6.4. Polimorfizmus és túlterhelés, p. 145-151.
  12. ↑ Cardelli, 1985 , 1.3. A polimorfizmus fajtái, p. 6.
  13. ↑ 1 2 Cardelli, 1985 , p. 5-6.
  14. ↑ Cardelli, 1996 , 5 Másodrendű típusrendszerek, p. 25.
  15. ↑ Harper, 2012 , 20.3 Parametrikus áttekintés, p. 177.
  16. ↑ Harper, 2012 , 49 Parametricity, p. 495-508.
  17. ↑ Pierce, 2012 , 23.9 Parametrikusság, p. 384-385.
  18. ↑ Harper, 2012 , 21.4 Képviselet függetlensége, p. 188.
  19. ↑ Pierce, 2012 , 30.5 Továbblépve: Függő típusok, p. 489-493.
  20. ↑ Reynolds, 1998 , 16. Altípusok és metszettípusok. Bibliográfiai jegyzetek, p. 376.
  21. ↑ Cardelli, 1985 .
  22. ↑ Mitchell, 2002 , 10.2.6. Az öröklődés nem altípus, p. 287.
  23. ↑ Cardelli, 1991 .
  24. ↑ 1 2 Pierce, 2012 , 15 Altípusok, p. 193.
  25. ↑ 1 2 Pierce, 2012 , 15. Altípusok, p. 193.
  26. ↑ Harper, 2012 , 23.1. Feltétel, p. 208.
  27. ↑ 1 2 3 Pierce, 2012 , 1.4 Rövid történelem, p. 11-13.
  28. ↑ Cardelli, 1991 , 6. Erőfajták, p. 32.
  29. ↑ 1 2 3 4 Abadi, Cardelli, 1994 .
  30. ↑ 1 2 3 Cardelli, 1985 , 6. Bounded Quantification, p. 28.
  31. ↑ Minsky fordítása: DMK, 2014 , Altípus, p. 259.
  32. ↑ Cardelli, 1985 , p. 9.
  33. ↑ Harper, 2012 , 16. fejezet. Rekurzív típusok, p. 132.
  34. ↑ 1 2 Cardelli, 1991 , p. 35-37.
  35. ↑ Cardelli, 1985 , 2.3. Alaptípusok, strukturált típusok és rekurzió, p. 12-14.
  36. ↑ Harper, 2012 , 25. fejezet. Dinamikus elküldés, p. 229.
  37. ↑ 1 2 Joyner, 1996 , 3.38 Signature Variance, p. 35.
  38. ↑ Objektum-orientált programozás szabványos ML-ben . Letöltve: 2016. március 11. Az eredetiből archiválva : 2016. január 14..
  39. ↑ Minsky fordítása: DMK, 2014 , 11. fejezet. Tárgyak, o. 253.
  40. ↑ Az ML2000 munkacsoport. Az ML2000 alapelvei és előzetes terve . – 1999.
  41. ↑ Castagna, Ghelli, Longo. Számológép túlterhelt függvényekhez altípussal  // Információ és számítás. - Akadémiai sajtó, 1995. - T. 117 , sz. 1 . - S. 115-135 . - doi : 10.1006/inco.1995.1033 .
  42. ↑ Joyner, 1996 , 2.8 Encapsulation, p. nyolc.
  43. ↑ Mitchell, 2002 , 6.2.1 Típusbiztonság, p. 132-133.
  44. ↑ Harper, 2012 , 4. fejezet Statika, p. 35.
  45. ↑ Pierce, 2012 , 31. Magasabb rendű altípusok, p. 495.
  46. ↑ 12 Wadler , 1988 , p. 3.
  47. ↑ Johan Jeuring. Politipikus mintaillesztés  // FPCA. - 1995. - doi : 10.1.1.36.5645 .
  48. ↑ Ralf Lammel és Joost Visser, "Typed Combinators for Generic Traversal", in Practical Aspects of Declarative Languages: 4th International Symposium (2002), p. 153.
  49. ↑ Patrik Jansson, Johan Jeuring. PolyP – Politipikus programozási nyelv kiterjesztése . – Sigplan SPPL, 1997.
  50. ↑ Girard - Extension of Type Theory, 1971 .
  51. ↑ Girard - Magasabb rendű kalkulus, 1972 .
  52. ↑ Reynolds, 1974 .
  53. ↑ Pálca, 1987 .

Irodalom

  • Christopher Strachey. A programozási nyelvek alapfogalmai  . - 1967. Archiválva : 2017. augusztus 12.
    • Újra kiadva: Christopher Strachey. A programozási nyelvek alapfogalmai  // Magasabb rendű és szimbolikus számítás  . - 2000. - Vol. 13 . - 11-49 . o . - 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  (francia)  // Proceedings of the Second Scandinavian Logic Symposium. - Amszterdam, 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  (francia) . – Université Paris 7, 1972.
  • John C. Reynolds. A típusszerkezet elmélete felé // Számítástechnikai előadásjegyzetek . - Párizs: Colloque sur la programation, 1974. - 19. évf . - S. 408-425 . - doi : 10.1007/3-540-06859-7_148 .
  • Luca Cardelli , Peter Wegner. A típusok, az adatabsztrakció és a polimorfizmus megértése //ACM számítástechnikai felmérések. - New York, USA:ACM, 1985. -17,no. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.
  • Robert Harper . Bevezetés a Standard ML-be. - Carnegie Mellon Egyetem, 1986. - ISBN PA 15213-3891.
  • Orosz nyelvű fordítás: Robert Harper . Bevezetés a Standard ML-be. - Carnegie Mellon Egyetem, 1986. - 97 p. — ISBN PA 15213-3891.
  • Luca Cardelli . Típusrendszerek (angol) // Handbook of Computer Science and Engineering. – CRC Press, 1996.
  • John C. Reynolds. Programozási nyelvek elméletei . - Cambridge University Press, 1998. - ISBN 978-0-521-59414-1 (keménykötés), 978-0-521-10697-9 (puhakötés).
  • Benjamin Pierce. Típusok és programozási nyelvek  . - MIT Press , 2002. - ISBN 0-262-16209-1 .
    • Orosz nyelvű fordítás: Benjamin Pierce. Típusok a programozási nyelvekben . - Dobrosvet , 2012. - 680 p. — ISBN 978-5-7913-0082-9 .
  • John C. Mitchell Fogalmak a programozási nyelvekben  . - Cambridge University Press, 2002. - 540 p. - ISBN 978-0-521-78098-8 .
  • Minsky, Madhavapeddy, Hickey. Valós világ OCaml: Funkcionális programozás  tömegek számára . - O'Reilly Media, 2013. - 510 p. — ISBN 9781449324766 .
    • Orosz nyelvű fordítás: Minsky, Madhavapeddy, Hickey. Programozás OCaml nyelven . - DMK, 2014. - 536 p. — (Funkcionális programozás). - ISBN 978-5-97060-102-0 .