Recursos de programación tipo Scala

Sinopsis

La programación a nivel de tipo tiene muchas similitudes con la programación tradicional a nivel de valor. Sin embargo, a diferencia de la programación a nivel de valor, donde el cálculo ocurre en tiempo de ejecución, en la programación a nivel de tipo, el cálculo ocurre en tiempo de compilación. Trataré de establecer paralelismos entre la programación a nivel de valor y la programación a nivel de tipo.

Paradigmas

Hay dos paradigmas principales en la programación a nivel de tipo: "orientado a objetos" y "funcional". La mayoría de los ejemplos vinculados a from here siguen el paradigma orientado a objetos.

Un ejemplo bueno y bastante simple de programación a nivel de tipo en el paradigma orientado a objetos se puede encontrar en la implementación del cálculo lambda de apocalisp, replicada aquí:

// 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
}

Como se puede ver en el ejemplo, el paradigma orientado a objetos para la programación a nivel de tipo procede de la siguiente manera:

• Primero: definir un rasgo abstracto con varios campos de tipo abstracto(vea a continuación lo que es un campo abstracto). Esta es una plantilla para garantizar que existen ciertos campos de tipos en todas las implementaciones sin forzar una implementación. En el ejemplo de cálculo lambda, esto corresponde a trait Lambda que garantiza que existen los siguientes tipos: subst, apply, y eval.
• Siguiente: defina sustratos que amplíen el rasgo abstracto e implemente los diversos campos de tipo abstracto
  • A menudo, estos sustratos serán parametrizado con argumentos. En el ejemplo de cálculo lambda, los subtipos son trait App extends Lambda que se parametriza con dos tipos (S y T, ambos deben ser subtipos de Lambda), trait Lam extends Lambda parametrizado con un tipo (T), y trait X extends Lambda (que no está parametrizado).
  • los campos de tipo a menudo se implementan haciendo referencia a los parámetros de tipo del sustrait y, a veces, haciendo referencia a sus campos de tipo a través del operador hash: # (que es muy similar al operador de punto: . para valor). En trait App del ejemplo de cálculo lambda, el tipo eval se implementa de la siguiente manera: type eval = S#eval#apply[T]. Esto es esencialmente llamar al tipo eval del parámetro del rasgo S, y llamar a apply con el parámetro T en el resultado. Tenga en cuenta que S tiene garantizado un tipo eval porque el parámetro especifica que es un subtipo de Lambda. Del mismo modo, el resultado de eval debe tener un tipo apply, ya que se especifica que es un subtipo de Lambda, como se especifica en el rasgo abstracto Lambda.

El paradigma Funcional consiste en definir muchos constructores de tipos parametrizados que no están agrupados en rasgos.

Comparación entre la programación a nivel de valor y la programación a nivel de tipo

• clase abstracta
  • nivel de valor: abstract class C { val x }
  • nivel de tipo: trait C { type X }
• tipos dependientes de la ruta
  • C.x (campo de referencia valor / función x en el objeto C)
  • C#x (haciendo referencia al campo tipo x en el rasgo C)
• firma de función (sin implementación)
  • nivel de valor: def f(x:X) : Y
  • nivel de tipo: type f[x <: X] <: Y (esto se llama un "constructor de tipo" y generalmente ocurre en el rasgo abstracto)
• implementación de funciones
  • nivel de valor: def f(x:X) : Y = x
  • nivel de tipo: type f[x <: X] = x
• condicionales
  • ver aquí
• comprobación de la igualdad
  • nivel de valor: a:A == b:B
  • nivel de tipo: implicitly[A =:= B]
  • nivel de valor: Ocurre en la JVM a través de una prueba unitaria en tiempo de ejecución (es decir, sin errores de tiempo de ejecución):
    • en essense es una afirmación: {[44]]}
  • nivel de tipo: Ocurre en el compilador a través de una comprobación de tipo (es decir, no hay errores en el compilador):
    • , en esencia, es una comparación de tipos: por ejemplo, implicitly[A =:= B]
    • A <:< B, compila solo si A es un subtipo de B
    • A =:= B, compila sólo si A es un subtipo de B y B es un subtipo de A
    • A <%< B, ("ver como") compila sólo si A es visible como B (es decir, hay una conversión implícita de A a un subtipo de B)
    • un ejemplo
    • más comparación operadores

Conversión entre tipos y valores

• En muchos de los ejemplos, los tipos definidos a través de traits a menudo son abstractos y sellados, y por lo tanto no pueden ser instanciados directamente ni a través de subclases anónimas. Por lo tanto, es común usar null como un valor de marcador de posición cuando se hace un cálculo a nivel de valor utilizando algún tipo de interés:

  • por ejemplo, val x:A = null, donde A es el tipo te importa

• Debido al borrado de tipos, todos los tipos parametrizados tienen el mismo aspecto. Además, (como se mencionó anteriormente) los valores con los que está trabajando tienden a ser null, por lo que condicionar el tipo de objeto (por ejemplo, a través de una sentencia match) es ineficaz.

El truco es usar funciones y valores implícitos. El caso base suele ser un valor implícito y el caso recursivo suele ser una función implícita. De hecho, la programación a nivel de tipo hace un uso intensivo de implicitos.

Considere este ejemplo (tomado de metascala y apocalisp):

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Aquí tienes una codificación peano de los números naturales. Es decir, tiene un tipo para cada entero no negativo: un tipo especial para 0, a saber _0; y cada entero mayor que cero tiene un tipo de la forma Succ[A], donde A es el tipo que representa un entero más pequeño. Por ejemplo, el tipo que representa 2 sería: Succ[Succ[_0]] (sucesor aplicado dos veces al tipo que representa cero).

Podemos alias varios números naturales para una referencia más conveniente. Ejemplo:

type _3 = Succ[Succ[Succ[_0]]]

(Esto es muy parecido a definir a val como el resultado de una función.)

Ahora, supongamos que queremos definir una función de nivel de valor def toInt[T <: Nat](v : T) que toma un valor de argumento, v, que se ajusta a Nat y devuelve un entero que representa el número natural codificado en el tipo de v. Por ejemplo, si tenemos el valor val x:_3 = null (null de tipo Succ[Succ[Succ[_0]]]), desearíamos toInt(x) devolver 3.

Para implementar toInt, vamos a hacer uso de la siguiente clase:

class TypeToValue[T, VT](value : VT) { def getValue() = value }

Como veremos a continuación, habrá un objeto construido a partir de la clase TypeToValue para cada Nat desde _0 hasta (por ejemplo) _3, y cada uno almacenará la representación del valor del tipo correspondiente (es decir, TypeToValue[_0, Int] almacenará el valor 0, TypeToValue[Succ[_0], Int] almacenará el valor 1, etc.). Nota, TypeToValue está parametrizado por dos tipos: T y VT. T corresponde al tipo al que estamos tratando de asignar valores (en nuestro ejemplo, Nat) y VT corresponde al tipo de valor que le estamos asignando (en nuestro ejemplo, Int).

Ahora hacemos las siguientes dos definiciones implícitas:

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 implementamos toInt de la siguiente manera:

def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()

Para entender cómo funciona toInt, consideremos lo que hace en un par de entradas:

val z:_0 = null
val y:Succ[_0] = null

Cuando llamamos a toInt(z), el compilador busca argumento implícito ttv de tipo TypeToValue[_0, Int] (ya que z es de tipo _0). Encuentra el objeto _0ToInt, llama al método getValue de este objeto y vuelve 0. El punto importante a tener en cuenta es que no especificamos al programa qué objeto usar, el compilador lo encontró implícitamente.

Ahora consideremos toInt(y). Esta vez, el compilador busca un argumento implícito ttv de tipo TypeToValue[Succ[_0], Int] (ya que y es de tipo Succ[_0]). Encuentra la función succToInt, que puede devolver un objeto del tipo apropiado (TypeToValue[Succ[_0], Int]) y lo evalúa. Esta función en sí toma un argumento implícito (v) de tipo TypeToValue[_0, Int] (es decir, un TypeToValue donde el primer parámetro de tipo tiene uno menos Succ[_]). El compilador suministra _0ToInt (como se hizo en la evaluación de toInt(z) anterior), y succToInt construye un nuevo objeto TypeToValue con el valor 1. Una vez más, es importante tener en cuenta que el compilador está proporcionando todos estos valores implícitamente, ya que no tenemos acceso a ellos explícitamente.

Comprobando tu trabajo

Hay varias maneras de verificar que sus cálculos a nivel de tipo están haciendo lo que espera. Aquí hay algunos enfoques. Haga dos tipos A y B, que desea verificar son iguales. A continuación, compruebe que la siguiente compile:

• Equal[A, B]
  • con: rasgo Equal[T1 >: T2 <: T2, T2] (tomado de apocalisp )
• implicitly[A =:= B]

Alternativamente, puede convertir el tipo a un valor (como se muestra arriba) y hacer una comprobación en tiempo de ejecución de los valores. Por ejemplo, assert(toInt(a) == toInt(b)), donde a es de tipo A y b es de tipo B.

Recursos Adicionales

El conjunto completo de construcciones disponibles se puede encontrar en la sección tipos de el manual de referencia de scala (pdf).

Adriaan Moors tiene varios artículos académicos sobre constructores de tipos y temas relacionados con ejemplos de scala:

• Genéricos de tipo superior (pdf)
• Type Constructor Polymorphism for Scala: Theory and Practice (pdf) (Tesis doctoral, que incluye el artículo anterior de Moors)
• Inferencia de Polimorfismo del Constructor de Tipo

Apocalisp es un blog con muchos ejemplos de programación a nivel de tipo en scala.

• La programación a nivel de tipo en Scala es una visita guiada de alguna programación a nivel de tipo que incluye booleanos, números naturales (como arriba), números binarios, listas heterogéneas y más.
• More Scala Typehackery es la implementación de cálculo lambda anterior.

ScalaZ es un proyecto muy activo que está proporcionando funcionalidad que extiende la API de Scala utilizando varias características de programación a nivel de tipo. Es un proyecto muy interesante que tiene una gran siguiente.

MetaScala es una biblioteca a nivel de tipo para Scala, incluyendo meta tipos para números naturales, booleanos, unidades, HList, etc. Es un proyecto de Jesper Nordenberg (su blog).

El Michid (blog) tiene algunos ejemplos impresionantes de programación a nivel de tipo en Scala (de otra respuesta):

• Meta-Programación con Scala Parte I: Adición
• Meta-Programación con Scala Parte II: Multiplicación
• Metaprogramación con Scala Parte III: Aplicación de funciones parciales
• Metaprogramación con Scala: Compilación condicional y Desenrollamiento de bucle
• Codificación de nivel de tipo Scala del cálculo de ESQUÍ

Debasish Ghosh (blog) también tiene algunos posts relevantes:

• Abstracciones de orden superior en scala
• La escritura estática te da una ventaja
• Scala implicita clases de tipo, aquí vengo
• Refactorización en clases de tipo scala
• Usando restricciones de tipo generalizadas
• Cómo escribe scalas palabras del sistema para usted
• Elegir entre miembros de tipo abstracto

(He estado haciendo algunas investigaciones sobre este tema y esto es lo que he aprendido. Todavía soy nuevo en él, así que por favor señale cualquier inexactitudes en esta respuesta.)