Parametrik polimorfizm - Parametric polymorphism

İçinde Programlama dilleri ve tip teorisi, parametrik polimorfizm bir dili tam statik olarak korurken, bir dili daha anlamlı kılmanın bir yoludur tip güvenliği. Parametrik kullanma çok biçimlilik, bir işlev veya bir veri türü, değerleri işleyebilmesi için genel olarak yazılabilir aynı şekilde türlerine bağlı olmaksızın.^[1] Bu tür işlevler ve veri türleri denir genel işlevler ve genel veri türleri sırasıyla ve temelini oluşturur genel programlama.

Örneğin, bir işlev eklemek iki listeyi birleştiren öğe türlerini önemsemeyecek şekilde oluşturulabilir: tamsayı listelerini, gerçek sayı listelerini, dizelerin listelerini vb. ekleyebilir. Bırak tip değişken a listelerdeki öğelerin türünü belirtir. Sonra eklemek yazılabilir

forall a. [a] × [a] -> [a]

nerede [a] tür öğelere sahip listelerin türünü belirtir a. Biz türünü söylüyoruz eklemek dır-dir tarafından parametrelendirilmiş tüm değerleri için a. (Yalnızca bir tür değişkeni olduğundan, işlevin yalnızca herhangi bir liste çiftine uygulanamayacağına dikkat edin: çift ve sonuç listesi aynı tür öğelerden oluşmalıdır.) Her yer için eklemek uygulanır, bir değer belirlenir a.

Takip etme Christopher Strachey,^[2] parametrik polimorfizm ile karşılaştırılabilir ad hoc polimorfizm, burada tek bir polimorfik fonksiyon, uygulandığı argüman (lar) ın türüne bağlı olarak bir dizi farklı ve potansiyel olarak heterojen uygulamaya sahip olabilir. Bu nedenle, ad hoc polimorfizm genellikle sadece sınırlı sayıda bu tür farklı türleri destekleyebilir, çünkü her tür için ayrı bir uygulamanın sağlanması gerekir.

Tarih

Parametrik polimorfizm ilk olarak programlama dillerine tanıtıldı ML 1975'te.^[3] Bugün var Standart ML, OCaml, F #, Ada, Haskell, Merkür, Görsel Prolog, Scala, Julia, Python, TypeScript, C ++ ve diğerleri. Java, C #, Visual Basic .NET ve Delphi her biri parametrik polimorfizm için "jenerik" tanıttı. Tip polimorfizmin bazı uygulamaları, yüzeysel olarak parametrik polimorfizme benzerdir ve aynı zamanda ad hoc yönler sunar. Bir örnek C ++ şablon uzmanlığı.

Polimorfizmin en genel biçimi "üst düzey cezalandırıcı polimorfizm ". Bu formun iki popüler kısıtlaması, sınırlı sıra polimorfizmidir (örneğin, rank-1 veya prenex polimorfizm) ve öngörücü polimorfizm. Birlikte, bu kısıtlamalar, esasen ML'de ve Haskell'in erken sürümlerinde bulunan polimorfizm formu olan "preneks öncesi polimorfizmi" verir.

Daha yüksek dereceli polimorfizm

Derece-1 (prenex) polimorfizmi

Bu bölüm için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. (Şubat 2019) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

İçinde prenex polimorfik sistem, tür değişkenleri polimorfik türlerle somutlaştırılamaz.^[4] Bu, "ML-tarzı" veya "Let-polimorfizmi" olarak adlandırılan şeye çok benzer (teknik olarak ML'nin Let-polimorfizminin birkaç başka sözdizimsel kısıtlaması vardır). Bu kısıtlama, polimorfik ve polimorfik olmayan tipler arasındaki ayrımı çok önemli hale getirir; bu nedenle tahmin sistemlerinde polimorfik tipler bazen şu şekilde anılır: tip şemaları onları bazen adı verilen sıradan (monomorfik) türlerden ayırmak için monotipler. Bunun bir sonucu, tüm türlerin tüm niceleyicileri en dıştaki (prenex) konuma yerleştiren bir biçimde yazılabilmesidir. eklemek türü olan yukarıda açıklanan işlev

forall a. [a] × [a] -> [a]

Bu işlevi bir çift listeye uygulamak için, değişken yerine bir tür değiştirilmelidir. a işlevin türünde, argümanların türü sonuçta ortaya çıkan işlev türü ile eşleşecek şekilde. Bir cezalandırıcı sistemde, ikame edilen tip, kendisi polimorfik olan bir tip dahil olmak üzere herhangi bir tip olabilir; Böylece eklemek her türden öğeye sahip liste çiftlerine uygulanabilir - hatta polimorfik işlevlerin listelerine de uygulanabilir: eklemek ML dilinde polimorfizm öngörücüdür.^{[kaynak belirtilmeli ]} Bunun nedeni, diğer kısıtlamalarla birlikte öngörülebilirliğin, tip sistemi yeterince basit bu kadar dolu tür çıkarımı her zaman mümkündür.

Pratik bir örnek olarak, OCaml (soyundan veya lehçesinden ML ) tür çıkarımı gerçekleştirir ve impredicative polimorphism'i destekler, ancak bazı durumlarda impredicative polymorphism kullanıldığında, programcı tarafından bazı açık tür ek açıklamaları sağlanmadıkça sistemin tür çıkarımı eksik kalır.

Sırak çok biçimlilik

Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Kasım 2013)

Sabit bir değer için k, sıra-k polimorfizm, bir niceleyicinin solunda görünmeyebileceği bir sistemdir. k veya daha fazla ok (yazı bir ağaç olarak çizildiğinde).^[1]

Çıkarım türü rank-2 polimorfizmi için karar verilebilir, ancak rank-3 ve üstü için yeniden yapılanma karar verilmez.^[5]

Sıran ("daha yüksek sıralı") polimorfizm

Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Kasım 2013)

Sıran polimorfizm, niceleyicilerin rastgele birçok okun solunda görünebildiği bir polimorfizmdir.

Öngörülebilirlik ve impredicativite

Tahmine dayalı polimorfizm

Öngörücü parametrik polimorfik bir sistemde, bir tür ${ displaystyle tau}$ bir tür değişkeni içeren ${ displaystyle alpha}$ böyle bir şekilde kullanılamaz ${ displaystyle alpha}$ polimorfik tipte somutlaştırılmıştır. Tahmini tip teorileri şunları içerir: Martin-Löf Tip Teorisi ve NuPRL.

İmpredikatif polimorfizm

İmpredikatif polimorfizm (olarak da adlandırılır birinci sınıf polimorfizm) parametrik polimorfizmin en güçlü şeklidir.^[6] Bir tanım olduğu söyleniyor cezalandırıcı kendine atıfta bulunuyorsa; tür teorisinde bu, bir türdeki bir değişkenin somutlaştırılmasına izin verir ${ displaystyle tau}$ polimorfik türler dahil olmak üzere herhangi bir türle, örneğin ${ displaystyle tau}$ kendisi. Buna bir örnek, Sistem F tip değişkeni ile X tipte ${ displaystyle T = forall X.X to X}$, nerede X hatta başvurabilir T kendisi.

İçinde tip teorisi, en sık incelenen empredikatif yazılan λ-calculi şunlara dayanıyor lambda küpü, özellikle Sistem F.^[1]

Sınırlı parametrik polimorfizm

1985 yılında Luca Cardelli ve Peter Wegner izin vermenin avantajlarını fark etti sınırlar tip parametrelerinde.^[7] Çoğu işlem, veri türleri hakkında biraz bilgi gerektirir, ancak aksi takdirde parametrik olarak çalışabilir. Örneğin, bir maddenin bir listeye dahil olup olmadığını kontrol etmek için, maddeleri eşitlik açısından karşılaştırmamız gerekir. İçinde Standart ML, formun parametrelerini yazın ’’ A eşitlik işleminin kullanılabilir olması için sınırlandırılmıştır, dolayısıyla işlevin türü olacaktır ’’ A × ’’ A liste → bool ve ’’ A sadece tanımlanmış eşitliğe sahip bir tür olabilir. İçinde Haskell sınırlama, türlerin bir tip sınıfı; bu nedenle aynı işlevin türü vardır ${ displaystyle { scriptstyle Eq , alpha , Rightarrow alpha , rightarrow sol [ alpha sağ] rightarrow Bool}}$ Haskell'de. Parametrik polimorfizmi destekleyen nesneye yönelik programlama dillerinin çoğunda, parametreler şu şekilde sınırlandırılabilir: alt türler belirli bir türden (bkz. Alt tip polimorfizmi ve hakkındaki makale Genel programlama ).

Ayrıca bakınız

• Parametriklik
• Polimorfik özyineleme
• Sınıf # Yüksek tür polimorfizm yazın

Notlar

Referanslar

• Strachey, Christopher (1967), Programlama Dillerinde Temel Kavramlar (Ders notları), Kopenhag: Bilgisayar Programcılığında Uluslararası Yaz OkuluCS1 bakimi: ref = harv (bağlantı). Yeniden yayınlandı: Strachey Christopher (2000). Yüksek Dereceli ve Sembolik Hesaplama. 13: 11–49. doi:10.1023 / A: 1010000313106. Eksik veya boş | title = (Yardım)
• Hindley, J. Roger (1969), "Kombinasyon mantığında bir nesnenin ana tip şeması", Amerikan Matematik Derneği İşlemleri, 146: 29–60, doi:10.2307/1995158, JSTOR  1995158, BAY  0253905CS1 bakimi: ref = harv (bağlantı).
• Girard, Jean-Yves (1971). "Une Extension de l'Interpretation de Gödel à l'Analyse, and son Application à l'Élimination des Coupures dans l'Analyse and la Théorie des Types". İkinci İskandinav Mantığı Sempozyumu Bildirileri (Fransızcada). Amsterdam. sayfa 63–92. doi:10.1016 / S0049-237X (08) 70843-7.CS1 bakimi: ref = harv (bağlantı)
• Girard, Jean-Yves (1972), Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (Doktora tezi) (Fransızca), Université Paris 7CS1 bakimi: ref = harv (bağlantı).
• Reynolds, John C. (1974), "Tip Yapısı Teorisine Doğru", Colloque Sur la Programlama, Bilgisayar Bilimlerinde Ders Notları, Paris, 19: 408–425, doi:10.1007/3-540-06859-7_148, ISBN  978-3-540-06859-4CS1 bakimi: ref = harv (bağlantı).
• Milner, Robin (1978). "Programlamada Tip Polimorfizm Teorisi" (PDF). Bilgisayar ve Sistem Bilimleri Dergisi. 17 (3): 348–375. doi:10.1016/0022-0000(78)90014-4.CS1 bakimi: ref = harv (bağlantı)
• Cardelli, Luca; Wegner, Peter (Aralık 1985). "Türleri, Veri Soyutlamasını ve Polimorfizmi Anlamak Üzerine" (PDF). ACM Hesaplama Anketleri. 17 (4): 471–523. CiteSeerX  10.1.1.117.695. doi:10.1145/6041.6042. ISSN  0360-0300.CS1 bakimi: ref = harv (bağlantı)
• Pierce, Benjamin C. (2002). Türler ve Programlama Dilleri. MIT Basın. ISBN  978-0-262-16209-8.CS1 bakimi: ref = harv (bağlantı)