Polimorfismo parametrico - Parametric polymorphism

Polimorfismo
Polimorfismo ad hoc
Sovraccarico delle funzioni Sovraccarico dell'operatore
Polimorfismo parametrico
Funzione generica Programmazione generica
sottotipizzazione
Funzione virtuale Spedizione unica e dinamica Doppia spedizione Spedizione multipla Spedizione predicato
v T e

Nei linguaggi di programmazione e nella teoria dei tipi , il polimorfismo parametrico è un modo per rendere un linguaggio più espressivo, pur mantenendo la piena sicurezza del tipo statico . Usando il polimorfismo parametrico , una funzione o un tipo di dati può essere scritto genericamente in modo che possa gestire i valori in modo identico senza dipendere dal loro tipo. Tali funzioni e tipi di dati sono chiamati rispettivamente funzioni generiche e tipi di dati generici e costituiscono la base della programmazione generica .

Ad esempio, una funzione appendche unisce due elenchi può essere costruita in modo che non si preoccupi del tipo di elementi: può aggiungere elenchi di interi , elenchi di numeri reali , elenchi di stringhe e così via. Lascia che la variabile type a denoti il ​​tipo di elementi nelle liste. Quindi appendpuò essere digitato

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

dove [a]denota il tipo di elenchi con elementi di tipo a . Diciamo che il tipo di appendè parametrizzato da a per tutti i valori di a . (Si noti che poiché esiste una sola variabile di tipo, la funzione non può essere applicata a una qualsiasi coppia di liste: la coppia, così come la lista dei risultati, deve essere costituita dallo stesso tipo di elementi) Per ogni luogo in cui appendviene applicata, un il valore è deciso per a .

Seguendo Christopher Strachey , il polimorfismo parametrico può essere contrapposto al polimorfismo ad hoc , in cui una singola funzione polimorfica può avere un numero di implementazioni distinte e potenzialmente eterogenee a seconda del tipo di argomento a cui è applicata. Pertanto, il polimorfismo ad hoc può generalmente supportare solo un numero limitato di tali tipi distinti, poiché deve essere fornita un'implementazione separata per ciascun tipo.

Storia

Il polimorfismo parametrico è stato introdotto per la prima volta nei linguaggi di programmazione in ML nel 1975. Oggi esiste in Standard ML , OCaml , F# , Ada , Haskell , Mercury , Visual Prolog , Scala , Julia , Python , TypeScript , C++ e altri. Java , C# , Visual Basic .NET e Delphi hanno introdotto dei "generici" per il polimorfismo parametrico. Alcune implementazioni del polimorfismo di tipo sono superficialmente simili al polimorfismo parametrico introducendo anche aspetti ad hoc. Un esempio è la specializzazione dei modelli C++ .

La forma più generale di polimorfismo è " polimorfismo impredicativo di rango superiore ". Due restrizioni popolari di questa forma sono il polimorfismo di rango ristretto (ad esempio, il polimorfismo di rango 1 o prenex ) e il polimorfismo predicativo. Insieme, queste restrizioni danno "polimorfismo predicativo prenex", che è essenzialmente la forma di polimorfismo trovato in ML e nelle prime versioni di Haskell.

Polimorfismo di grado superiore

Polimorfismo di grado 1 (prenex)

In un sistema polimorfico prenex , le variabili di tipo potrebbero non essere istanziate con i tipi polimorfici. Questo è molto simile a quello che viene chiamato "stile ML" o "polimorfismo Let" (tecnicamente il polimorfismo Let di ML ha alcune altre restrizioni sintattiche). Questa restrizione rende molto importante la distinzione tra tipi polimorfi e non polimorfici; così nei sistemi predicativi i tipi polimorfici sono a volte indicati come schemi di tipo per distinguerli dai tipi ordinari (monomorfi), che sono talvolta chiamati monotipi . Una conseguenza è che tutti i tipi possono essere scritti in una forma che pone tutti i quantificatori nella posizione più esterna (prenex). Ad esempio, considera la appendfunzione sopra descritta, che ha tipo

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

Per applicare questa funzione a una coppia di elenchi, è necessario sostituire un tipo alla variabile a nel tipo della funzione in modo che il tipo degli argomenti corrisponda al tipo di funzione risultante. In un sistema impredicativo , il tipo che viene sostituito può essere qualsiasi tipo, incluso un tipo che è esso stesso polimorfo; quindi appendpuò essere applicato a coppie di elenchi con elementi di qualsiasi tipo, anche a elenchi di funzioni polimorfiche come se appendstesso. Il polimorfismo nel linguaggio ML è predicativo. Questo perché la predicatività, insieme ad altre restrizioni, rende il sistema dei tipi abbastanza semplice da rendere sempre possibile l' inferenza completa del tipo .

Come esempio pratico, OCaml (un discendente o dialetto di ML ) esegue l'inferenza del tipo e supporta il polimorfismo impredicativo, ma in alcuni casi quando viene utilizzato il polimorfismo impredicativo, l'inferenza del tipo del sistema è incompleta a meno che il programmatore non fornisca alcune annotazioni di tipo esplicite.

Di ranghi k polimorfismo

Per qualche valore fisso k , il polimorfismo di rango k è un sistema in cui un quantificatore può non apparire a sinistra di k o più frecce (quando il tipo è disegnato come un albero).

L'inferenza del tipo per il polimorfismo di rango 2 è decidibile, ma la ricostruzione per il rango 3 e superiori non lo è.

Polimorfismo di rango n ("di rango superiore")

Il polimorfismo di rango n è un polimorfismo in cui i quantificatori possono apparire a sinistra di un numero arbitrario di frecce.

Predicatività e impredicatività

Polimorfismo predicativo

In un sistema polimorfico parametrico predicativo, un tipo contenente una variabile di tipo non può essere utilizzato in modo da istanziare un tipo polimorfico. Le teorie dei tipi predicativi includono la teoria dei tipi di Martin-Löf e NuPRL . ${\displaystyle \tau}$${\displaystyle\alpha}$${\displaystyle\alpha}$

Polimorfismo Impredicativo

Il polimorfismo Impredicativo (chiamato anche polimorfismo di prima classe ) è la forma più potente di polimorfismo parametrico. Una definizione si dice impredicativa se è autoreferenziale; nella teoria dei tipi questo consente l'istanziazione di una variabile in un tipo con qualsiasi tipo, inclusi i tipi polimorfici, come se stesso. Un esempio di ciò è il Sistema F con la variabile di tipo X nel tipo , dove X potrebbe anche riferirsi a T stesso. ${\displaystyle \tau}$${\displaystyle \tau}$${\displaystyle T=\forall XX\to X}$

In teoria dei tipi , il più delle volte studiato impredicativa digitato λ-calcoli si basano su quelle del cubo di lambda , in particolare del sistema F .

Polimorfismo parametrico limitato

Nel 1985, Luca Cardelli e Peter Wegner hanno riconosciuto i vantaggi di consentire limiti sui parametri di tipo. Molte operazioni richiedono una certa conoscenza dei tipi di dati, ma possono altrimenti funzionare in modo parametrico. Ad esempio, per verificare se un elemento è incluso in un elenco, è necessario confrontare gli elementi per l'uguaglianza. In Standard ML , i parametri di tipo della forma ''a sono limitati in modo che l'operazione di uguaglianza sia disponibile, quindi la funzione avrebbe il tipo ''a × ''a lista → bool e ''a può essere solo un tipo con definito uguaglianza. In Haskell , il limite si ottiene richiedendo ai tipi di appartenere a una classe di tipi ; quindi la stessa funzione ha il tipo in Haskell. Nella maggior parte dei linguaggi di programmazione orientati agli oggetti che supportano il polimorfismo parametrico, i parametri possono essere vincolati a essere sottotipi di un determinato tipo (vedere Polimorfismo dei sottotipi e l'articolo sulla programmazione generica ). ${\displaystyle {\scriptstyle Eq\,\alpha \,\Rightarrow \alpha \,\rightarrow \left[\alpha \right]\rightarrow Bool}}$

Guarda anche

• Parametricità
• Ricorsione polimorfica
• Classe tipo#polimorfismo di tipo superiore

Appunti

Riferimenti

• Strachey, Christopher (1967), Concetti fondamentali nei linguaggi di programmazione (appunti delle lezioni), Copenhagen: International Summer School in Computer Programming. Ripubblicato in: Strachey, Christopher (2000). Calcolo di ordine superiore e simbolico . 13 : 11-49. doi : 10.1023/A:1010000313106 . Mancante o vuoto |title=( aiuto )
• Hindley, J. Roger (1969), "The main type scheme of an object in combinatory logic", Transactions of the American Mathematical Society , 146 : 29–60, doi : 10.2307/1995158 , JSTOR  1995158 , MR  0253905.
• Girard, Jean-Yves (1971). "Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types". Atti del Secondo Simposio di Logica Scandinava (in francese). Amsterdam. pp. 63-92. doi : 10.1016/S0049-237X(08)70843-7 .
• Girard, Jean-Yves (1972), Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (tesi di dottorato) (in francese), Université Paris 7.
• Reynolds, John C. (1974), "Towards a Theory of Type Structure", Colloque Sur la Programmation , Lecture Notes in Computer Science , Paris, 19 : 408-425, doi : 10.1007/3-540-06859-7_148 , ISBN 978-3-540-06859-4.
• Milner, Robin (1978). "Una teoria del polimorfismo di tipo in programmazione" (PDF) . Giornale di scienze informatiche e di sistema . 17 (3): 348-375. doi : 10.1016/0022-0000(78)90014-4 .
• Cardelli, Luca ; Wegner, Peter (dicembre 1985). "Sulla comprensione dei tipi, dell'astrazione dei dati e del polimorfismo" (PDF) . Sondaggi ACM Computing . 17 (4): 471-523. CiteSeerX  10.1.1.117.695 . doi : 10.1145/6041.6042 . ISSN  0360-0300 .
• Pierce, Benjamin C. (2002). Tipi e linguaggi di programmazione . MIT Press. ISBN 978-0-262-16209-8.