Panoramica
programmazione Type-livello ha molte analogie con tradizionali, la programmazione del valore di livello. Tuttavia, a differenza della programmazione a livello di valore, in cui il calcolo avviene a runtime, nella programmazione a livello di codice, il calcolo avviene al momento della compilazione. Cercherò di tracciare paralleli tra la programmazione a livello di valore e la programmazione a livello di tipo.
paradigmi
Esistono due principali paradigmi di programmazione del tipo Sali: "object-oriented" e "funzionale". La maggior parte degli esempi collegati da qui seguono il paradigma orientato agli oggetti.
Una buona, abbastanza semplice esempio di programmazione tipo di livello nel paradigma orientato agli oggetti possono essere trovati in apocalisp di implementation of the lambda calculus, replicato qui:
// Abstract trait
trait Lambda {
type subst[U <: Lambda] <: Lambda
type apply[U <: Lambda] <: Lambda
type eval <: Lambda
}
// Implementations
trait App[S <: Lambda, T <: Lambda] extends Lambda {
type subst[U <: Lambda] = App[S#subst[U], T#subst[U]]
type apply[U] = Nothing
type eval = S#eval#apply[T]
}
trait Lam[T <: Lambda] extends Lambda {
type subst[U <: Lambda] = Lam[T]
type apply[U <: Lambda] = T#subst[U]#eval
type eval = Lam[T]
}
trait X extends Lambda {
type subst[U <: Lambda] = U
type apply[U] = Lambda
type eval = X
}
Come si vede nell'esempio, l'oggetto orientato il paradigma per la programmazione a livello di codice procede come segue:
- Primo: definire un tratto astratto con vari campi di tipo astratto (vedere sotto per cosa è un campo astratto). Questo è un modello per garantire che alcuni tipi di campi esistano in tutte le implementazioni senza forzare un'implementazione.Nell'esempio del calcolo lambda, questo corrisponde a
trait Lambda che garantisce che esistano i seguenti tipi: subst, apply e eval.
- successivo: definire subtraits che estendono il tratto astratto e implementare i vari campi di tipo astratte
- Spesso, questi subtraits saranno parametrizzati con argomenti. Nell'esempio lambda calcolo, i sottotipi sono
trait App extends Lambda parametrizzato con due tipi (S e T, entrambi devono essere sottotipi di Lambda), trait Lam extends Lambda parametrizzati con un tipo (T), e trait X extends Lambda (che non è parametrizzato).
- i campi tipo vengono spesso implementati facendo riferimento ai parametri di tipo del sottotitolo ea volte facendo riferimento ai campi del tipo tramite l'operatore hash:
# (che è molto simile all'operatore punto: . per i valori). Nel tratto App dell'esempio di calcolo lambda, il tipo eval è implementato come segue: type eval = S#eval#apply[T]. Questo è essenzialmente chiamando il tipo del parametro del tratto S e chiamando apply con il parametro T sul risultato. Nota: S ha un tipo eval poiché il parametro lo specifica come sottotipo di Lambda. Analogamente, il risultato di eval deve avere un tipo apply, poiché è specificato che è un sottotipo di Lambda, come specificato nel tratto astratto Lambda.
Il paradigma funzionale consiste nel definire un sacco di costruttori di tipo parametrico che non sono raggruppati insieme in tratti.
Confronto tra programmazione a livello di valore e programmazione tipo livello
- abstract class
- valore di livello:
abstract class C { val x }
- tipo di livello:
trait C { type X }
- path dependent tipi
C.x (riferimento valore di campo/funzione x in oggetto C)C#x (referenziare tipo di campo x nel tratto C)
- firma funzione (senza attuazione)
- valore di livello :
def f(x:X) : Y
- livello-tipo:
type f[x <: X] <: Y (questo è chiamato "tipo costruttore" e di solito si verifica nel tratto astratto)
- attuazione funzione
- valore di livello:
def f(x:X) : Y = x
- tipo di livello:
type f[x <: X] = x
- condizionali
- controllo parità
- valore di livello:
a:A == b:B
- tipo di livello:
implicitly[A =:= B]
- valore di livello: succede nel JVM tramite un test di unità durante il funzionamento (ossia nessun errore runtime):
- in essenza è un'asserzione:
assert(a == b)
- tipo di livello: accade nel compilatore tramite un TYPECHECK (cioè senza errori di compilatore):
- in sostanza è un confronto dei tipi: es
implicitly[A =:= B]
A <:< B, compila solo se A è un sottotipo di BA =:= B, compila solo se A è un sottotipo di B e B è un sottotipo di AA <%< B, ("visualizzabile come") viene compilato solo se A è visualizzabile come B (cioèv'è una conversione implicita da A a un sottotipo di B)- an example
- more comparison operators
Conversione tra tipi e valori
In molti l'ex amples, tipi definiti tramite tratti sono spesso astratti e sigillati, e quindi non possono essere istanziati direttamente né tramite sottoclassi anonime. Quindi è comune l'uso di null come valore segnaposto quando si fa un calcolo a livello di valore con un certo tipo di interesse:
- esempio
val x:A = null, dove A è il tipo che si preoccupano
a causa del tipo-cancellazione, tipi parametrizzati tutti lo stesso aspetto. Inoltre, (come menzionato sopra) i valori con cui lavori tendono a essere tutti null, e quindi il condizionamento sul tipo di oggetto (ad esempio tramite un'istruzione di corrispondenza) è inefficace.
Il trucco è utilizzare funzioni e valori impliciti. Il caso base è di solito un valore implicito e il caso ricorsivo è di solito una funzione implicita. In effetti, la programmazione a livello di codice fa un pesante uso di impliciti.
consideri questo esempio (taken from metascala e apocalisp):
sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat
Qui avete una codifica Peano dei numeri naturali. Cioè, hai un tipo per ogni intero non negativo: un tipo speciale per 0, ovvero _0; e ogni numero intero maggiore di zero ha un tipo di modulo Succ[A], dove A è il tipo che rappresenta un numero intero più piccolo. Ad esempio, il tipo che rappresenta 2 sarebbe: Succ[Succ[_0]] (successore applicato due volte al tipo che rappresenta zero).
Possiamo alias vari numeri naturali per un riferimento più comodo. Esempio:
type _3 = Succ[Succ[Succ[_0]]]
(. Questo è un po 'come la definizione di un val di essere il risultato di una funzione)
Ora, supponiamo di voler definire una funzione a livello di valore def toInt[T <: Nat](v : T) che prende in un valore di argomento , v, conforme a Nat e restituisce un numero intero che rappresenta il numero naturale codificato nel tipo v. Ad esempio, se abbiamo il valore val x:_3 = null (null di tipo Succ[Succ[Succ[_0]]]), vorremmo toInt(x) restituire 3.
Per implementare toInt, stiamo andando a fare uso della seguente classe:
class TypeToValue[T, VT](value : VT) { def getValue() = value }
Come vedremo di seguito, ci sarà un oggetto costruito dalla classe TypeToValue per ogni Nat da _0 fino a (ad esempio) _3 e ognuno memorizzerà la rappresentazione del valore del tipo corrispondente (ad esempio, TypeToValue[_0, Int] memorizzerà il valore 0, TypeToValue[Succ[_0], Int] memorizzerà il valore 1, ecc.). Nota: TypeToValue è parametrizzato da due tipi: T e VT. T corrisponde al tipo che stiamo cercando di assegnare valori a (nel nostro esempio, Nat) e VT corrisponde al tipo di valore che gli stiamo assegnando (nel nostro esempio, Int).
Ora facciamo le seguenti due definizioni implicite:
implicit val _0ToInt = new TypeToValue[_0, Int](0)
implicit def succToInt[P <: Nat](implicit v : TypeToValue[P, Int]) =
new TypeToValue[Succ[P], Int](1 + v.getValue())
E implementiamo toInt come segue:
def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()
Per capire come toInt opere, consideriamo ciò che fa su un paio di ingressi :
val z:_0 = null
val y:Succ[_0] = null
Quando chiamiamo toInt(z), il compilatore cerca un argomento implicito ttv di tipo TypeToValue[_0, Int] (dal z è di tipo _0). Trova l'oggetto _0ToInt, chiama il metodo getValue di questo oggetto e torna 0. Il punto importante da notare è che non abbiamo specificato al programma quale oggetto usare, il compilatore lo ha trovato implicitamente.
Ora consideriamo toInt(y). Questa volta, il compilatore cerca un argomento implicito ttv di tipo TypeToValue[Succ[_0], Int] (dal y è di tipo Succ[_0]). Trova la funzione succToInt, che può restituire un oggetto del tipo appropriato (TypeToValue[Succ[_0], Int]) e lo valuta. Questa funzione accetta un argomento implicito (v) di tipo TypeToValue[_0, Int] (ovvero, TypeToValue in cui il primo parametro di tipo ha un numero inferiore di Succ[_]). Il compilatore fornisce _0ToInt (come è stato fatto nella valutazione di toInt(z) sopra) e succToInt crea un nuovo oggetto TypeToValue con il valore 1. Di nuovo, è importante notare che il compilatore fornisce tutti questi valori implicitamente, poiché non abbiamo accesso ad essi esplicitamente.
Verifica il tuo lavoro
Ci sono diversi modi per verificare che i vostri calcoli di tipo a livello stanno facendo quello che ci si aspetta. Ecco alcuni approcci. Creare due tipi A e B, che si desidera verificare sono uguali.Quindi controllare che la seguente compilazione:
Equal[A, B]
implicitly[A =:= B]
In alternativa, è possibile convertire il tipo per un valore (come mostrato sopra) e fare un controllo runtime dei valori. Per esempio. assert(toInt(a) == toInt(b)), dove a è di tipo A e b è di tipo B.
Risorse aggiuntive
Il set completo di costrutti disponibili si possono trovare nella sezione tipi di the scala reference manual (pdf).
Adriaan Moors ha diverse pubblicazioni accademiche sui costruttori di tipo e argomenti correlati con esempi tratti dalla Scala:
Apocalisp è un blog con molti esempi di livello di tipo pro gramming in scala.
ScalaZ è un progetto molto attivo che fornisce funzionalità che estendono l'API Scala utilizzando varie funzionalità di programmazione a livello di codice. È un progetto molto interessante che ha un grande seguito.
MetaScala è una libreria di tipi di livello per la Scala, tra cui i meta tipi per i numeri naturali, booleani, unità, HList, ecc Si tratta di un progetto di Jesper Nordenberg (his blog).
Il Michid (blog) ha alcuni esempi impressionanti di programmazione tipo di livello a Scala (da altra risposta):
Debasish Ghosh (blog) ha alcuni messaggi importanti così:
(Ho fatto qualche ricerca su questo argomento ed ecco cosa ho imparato. Sono ancora nuovo ad esso, quindi per favore segnala eventuali inesattezze in questa risposta.)
wiki della comunità? –
Personalmente, trovo l'ipotesi che qualcuno che voglia fare una programmazione a livello di codice in Scala sappia già come programmare la programmazione in Scala in modo abbastanza ragionevole. Anche se questo significa che non capisco una parola di quegli articoli che hai collegato a :-) –