È utile il polimorfismo parametrico di rango più alto?

In generale, usi il polimorfismo di rango più alto quando vuoi che callee sia in grado di selezionare il valore di un parametro di tipo, piuttosto che il chiamante . Ad esempio:

f :: (forall a. Show a => a -> Int) -> (Int, Int)
f g = (g "one", g 2)

Qualsiasi funzione g che passo a questo f deve essere in grado di darmi un Int da un valore di qualche tipo, dove la cosa solo g sa di questo type è che ha un'istanza di Show . Quindi questi sono kosher:

f (length . show)
f (const 42)

Ma questi non sono:

f length
f succ

Un'applicazione particolarmente utile è l'uso dell'ambito dei tipi per forzare l'ambito dei valori . Supponiamo di avere un oggetto di tipo Action<T> , che rappresenta un'azione che possiamo eseguire per produrre un risultato di tipo T , come un futuro o callback.

T runAction<T>(Action<T>)

runAction :: forall a. Action a -> a

Ora, supponiamo di avere anche un Action che può allocare% oggetti di% co_de:

Action<Resource<T>> newResource<T>(T)

newResource :: forall a. a -> Action (Resource a)

Vogliamo far sì che tali risorse siano solo utilizzate all'interno di Resource<T> in cui sono state create e non condivise tra diverse azioni o diverse esecuzioni della stessa azione, in modo che le azioni siano deterministiche e ripetibile.

Possiamo utilizzare tipi con classificazione più alta per ottenere ciò aggiungendo un parametro Action ai tipi S e Resource , che è totalmente astratto: rappresenta lo "scope" di Action . Ora le nostre firme sono:

T run<T>(<S> Action<S, T>)
Action<S, Resource<S, T>> newResource<T>(T)

runAction :: forall a. (forall s. Action s a) -> a
newResource :: forall s a. a -> Action s (Resource s a)

Ora, quando forniamo Action e runAction , siamo certi che poiché il parametro "scope" Action<S, T> è completamente polimorfico, non può sfuggire al corpo di S , quindi qualsiasi valore di un tipo che utilizza runAction come S allo stesso modo non può uscire!

(In Haskell, questo è noto come Resource<S, int> monad, dove ST è chiamato runAction , runST è chiamato Resource e STRef è chiamato newResource .)

Il polimorfismo di rango più elevato è estremamente utile. In System F (il linguaggio principale dei linguaggi FP tipizzati con cui si ha familiarità), questo è essenziale per l'ammissione di "encodings Church typed", che è in realtà il modo in cui System F esegue la programmazione. Senza questi, il sistema F è completamente inutile.

Nel sistema F definiamo i numeri come

Nat = forall c. (c -> c) -> c -> c

L'addizione ha il tipo

plus : Nat -> Nat -> Nat
plus l r = Λ t. λ (s : t -> t). λ (z : t). l s (r s z)

che è un tipo di rango più alto (il forall c. appare all'interno di quelle frecce).

Questo succede anche in altri posti. Ad esempio, se vuoi indicare che un calcolo è uno stile di passaggio di continuazione appropriato (google "hashell di codifica"), allora avresti ragione come

type CPSed A = forall c. (A -> c) -> c

Anche parlare di un tipo disabitato in System F richiede un polimorfismo di rango più alto

type Void = forall a. a 

Il lungo e breve di questo, scrivere una funzione in un sistema di tipo puro (System F, CoC) richiede un polimorfismo di rango più elevato se vogliamo trattare con qualsiasi dato interessante.

In particolare in System F, queste codifiche devono essere "impredicative". Ciò significa che un forall a. quantifica su assolutamente tutti i tipi . Questo include in modo critico il tipo stesso che stiamo definendo. In forall a. a che a potrebbe effettivamente rappresentare ancora forall a. a ! In linguaggi come ML questo non è il caso, si dice che siano "predicativi" poiché una variabile di tipo quantifica solo sull'insieme di tipi senza quantificatori (chiamati monotipi). Anche la nostra definizione di plus ha richiesto l'impredicatività perché abbiamo istanziato c in l : Nat in Nat !

Infine, vorrei menzionare un ultimo motivo per cui ti piacerebbe sia l'impredicatività che il polimorfismo di rango più elevato anche in un linguaggio con tipi arbitrariamente ricorsivi (a differenza del sistema F). In Haskell, c'è una monade per effetti chiamata "monade thread di stato". L'idea è che la monade del thread di stato ti consenta di mutare le cose ma richiede di evitarlo perché il tuo risultato non dipende da nulla di mutevole. Ciò significa che i calcoli ST sono perfettamente osservabili. Per far rispettare questo requisito usiamo il polimorfismo di rango più alto

runST :: forall a. (forall s. ST s a) -> a

Qui assicurando che a sia legato al di fuori dell'ambito in cui introduciamo s , sappiamo che a rappresenta un tipo wellformed che non si basa su s . Usiamo s per parametrizzare tutte le cose mutabili in quel particolare stato, quindi sappiamo che a è indipendente dalle cose mutabili e quindi che nulla sfugge allo scope di quel calcolo di ST ! Un meraviglioso esempio di utilizzo dei tipi per escludere programmi mal formati.

A proposito, se sei interessato a conoscere la teoria dei tipi ti suggerisco di investire in un buon libro o due. È difficile imparare queste cose a pezzi. Suggerirei uno dei libri di Pierce o Harper sulla teoria PL in generale (e alcuni elementi di teoria dei tipi). Il libro "Argomenti avanzati in tipi e linguaggi di programmazione" copre anche una buona quantità di teoria dei tipi. Infine, "La programmazione nella teoria dei tipi di Martin Lof" è un'ottima esposizione alla teoria del tipo intensionale descritta da Martin Lof.