Recursos de programação do tipo Scala

De acordo com esta pergunta , o sistema de tipos de Scala é Turing completo . Quais recursos estão disponíveis para permitir que um recém-chegado aproveite o poder da programação em nível de tipo?

Aqui estão os recursos que encontrei até agora:

• A Alta Magia de Daniel Spiewak na Terra de Scala
• Programação de nível de tipo do Apocalisp em Scala
• Jesper's HList

Esses recursos são ótimos, mas sinto que não tenho o básico e, portanto, não tenho uma base sólida sobre a qual construir. Por exemplo, onde há uma introdução às definições de tipo? Que operações posso realizar nos tipos?

Existem bons recursos introdutórios?

Visão geral

A programação em nível de tipo tem muitas semelhanças com a programação tradicional em nível de valor. No entanto, ao contrário da programação de nível de valor, onde o cálculo ocorre em tempo de execução, na programação de nível de tipo, o cálculo ocorre em tempo de compilação. Tentarei traçar paralelos entre a programação no nível do valor e a programação no nível do tipo.

Paradigmas

Existem dois paradigmas principais na programação de nível de tipo: "orientada a objetos" e "funcional". A maioria dos exemplos vinculados a partir daqui seguem o paradigma orientado a objetos.

Um bom e bastante simples exemplo de programação em nível de tipo no paradigma orientado a objetos pode ser encontrado na implementação do cálculo lambda do Apocalisp , replicado aqui:

// 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 pode ser visto no exemplo, o paradigma orientado a objetos para programação em nível de tipo procede da seguinte forma:

• Primeiro: defina um traço abstrato com vários campos de tipo abstrato (veja abaixo o que é um campo abstrato). Este é um modelo para garantir que certos campos de tipos existam em todas as implementações sem forçar uma implementação. No exemplo lambda cálculo, isto corresponde a trait Lambdaque existem os seguintes tipos que garantias: subst, apply, e eval.
• A seguir: defina subtraits que estendem o traço abstrato e implemente os vários campos de tipo abstrato
  • Freqüentemente, esses subtraits serão parametrizados com argumentos. No exemplo do cálculo lambda, os subtipos são trait App extends Lambdaparametrizados com dois tipos ( Se T, ambos devem ser subtipos de Lambda), trait Lam extends Lambdaparametrizados com um tipo ( T) e trait X extends Lambda(que não é parametrizado).
  • os campos de tipo são frequentemente implementados referindo-se aos parâmetros de tipo do subtítulo e às vezes referenciando seus campos de tipo por meio do operador hash: #(que é muito semelhante ao operador ponto: .para valores). No traço Appdo exemplo lambda cálculo, o tipo evalé implementada da seguinte forma: type eval = S#eval#apply[T]. Isso é essencialmente chamar o evaltipo de parâmetro do trait Se chamarapply com parâmetro Tno resultado. Observe que Sé garantido ter um evaltipo porque o parâmetro especifica que é um subtipo de Lambda. Da mesma forma, o resultado de evaldeve ter um applytipo, uma vez que é especificado como um subtipo de Lambda, conforme especificado no traço abstrato Lambda.

O paradigma Funcional consiste em definir muitos construtores de tipo parametrizados que não são agrupados em características.

Comparação entre programação em nível de valor e programação em nível de tipo

• classe abstrata
  • nível de valor: abstract class C { val x }
  • nível de tipo: trait C { type X }
• tipos dependentes de caminho
  • C.x (referenciando o valor do campo / função x no objeto C)
  • C#x (referenciando o tipo de campo x no traço C)
• assinatura de função (sem implementação)
  • nível de valor: def f(x:X) : Y
  • nível de tipo: type f[x <: X] <: Y(isso é chamado de "construtor de tipo" e geralmente ocorre no traço abstrato)
• implementação de função
  • nível de valor: def f(x:X) : Y = x
  • nível de tipo: type f[x <: X] = x
• condicionais
  • Veja aqui
• verificando a igualdade
  • nível de valor: a:A == b:B
  • nível de tipo: implicitly[A =:= B]
  • nível de valor: acontece na JVM por meio de um teste de unidade no tempo de execução (ou seja, sem erros de tempo de execução):
    • em essência é uma afirmação: assert(a == b)
  • nível de tipo: acontece no compilador por meio de uma verificação de tipo (ou seja, sem erros do compilador):
    • em essência é uma comparação de tipo: por exemplo implicitly[A =:= B]
    • A <:< B, compila apenas se Afor um subtipo deB
    • A =:= B, compila apenas se Afor um subtipo de Be Bfor um subtipo deA
    • A <%< B, ("visível como") compila apenas se Afor visível como B(ou seja, há uma conversão implícita de Apara um subtipo de B)
    • um exemplo
    • mais operadores de comparação

Conversão entre tipos e valores

• Em muitos dos exemplos, os tipos definidos por meio de características são frequentemente abstratos e selados e, portanto, não podem ser instanciados diretamente nem por meio de uma subclasse anônima. Portanto, é comum usar nullcomo um valor de espaço reservado ao fazer um cálculo de nível de valor usando algum tipo de interesse:

  • por exemplo val x:A = null, ondeA está o tipo que você gosta

• Devido ao apagamento de tipo, os tipos parametrizados parecem todos iguais. Além disso, (como mencionado acima) os valores com os quais você está trabalhando tendem a ser todosnull , portanto, o condicionamento no tipo de objeto (por exemplo, por meio de uma instrução de correspondência) é ineficaz.

O truque é usar funções e valores implícitos. O caso base geralmente é um valor implícito e o caso recursivo é geralmente uma função implícita. Na verdade, a programação em nível de tipo faz uso intenso de implícitos.

Considere este exemplo ( tirado de metascala e apocalisp ):

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

Aqui você tem uma codificação peano dos números naturais. Ou seja, você tem um tipo para cada inteiro não negativo: um tipo especial para 0, a saber _0; e cada inteiro maior que zero tem um tipo da forma Succ[A], onde Aé o tipo que representa um inteiro menor. Por exemplo, o tipo que representa 2 seria:Succ[Succ[_0]] (sucessor aplicado duas vezes ao tipo que representa zero).

Podemos criar um alias para vários números naturais para uma referência mais conveniente. Exemplo:

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

(Isso é muito parecido com definir um valcomo o resultado de uma função.)

Agora, suponha que queremos definir uma função de nível de valor def toInt[T <: Nat](v : T)que recebe um valor de argumento v,, que está em conformidade com Nate retorna um inteiro que representa o número natural codificado no vtipo de. Por exemplo, se temos o valor val x:_3 = null( nulldo tipo Succ[Succ[Succ[_0]]]), gostaríamos toInt(x)de retornar 3.

Para implementar toInt, vamos fazer uso da seguinte classe:

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

Como veremos a seguir, haverá um objeto construído a partir da classe TypeToValuepara cada um Natde _0até (por exemplo) _3, e cada um armazenará a representação do valor do tipo correspondente (ou seja TypeToValue[_0, Int], armazenará o valor 0, TypeToValue[Succ[_0], Int]armazenará o valor 1etc.). Nota, TypeToValueé parametrizado por dois tipos: Te VT. Tcorresponde ao tipo ao qual estamos tentando atribuir valores (em nosso exemplo, Nat) e VTcorresponde ao tipo de valor que estamos atribuindo a ele (em nosso exemplo,Int ).

Agora fazemos as seguintes duas definições 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 da toIntseguinte forma:

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

Para entender como toIntfunciona, vamos considerar o que ele faz em algumas entradas:

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

Quando chamamos toInt(z), o compilador procura um argumento implícito ttvdo tipo TypeToValue[_0, Int](já que zé do tipo _0). Ele encontra o objeto _0ToInt, ele chama o getValuemétodo deste objeto e retorna0 . O ponto importante a notar é que não especificamos para o programa qual objeto usar, o compilador o encontrou implicitamente.

Agora vamos considerar toInt(y). Desta vez, o compilador procura um argumento implícito ttvdo tipo TypeToValue[Succ[_0], Int](já que yé do tipo Succ[_0]). Ele encontra a função succToInt, que pode retornar um objeto do tipo apropriado ( TypeToValue[Succ[_0], Int]) e o avalia. Essa função em si leva um argumento implícito ( v) do tipo TypeToValue[_0, Int](ou seja, a TypeToValueonde o primeiro parâmetro de tipo tem um a menos Succ[_]). O compilador fornece _0ToInt(como foi feito na avaliação toInt(z)acima) e succToIntconstrói um novo TypeToValueobjeto com valor 1. Novamente, é importante observar que o compilador está fornecendo todos esses valores implicitamente, já que não temos acesso a eles explicitamente.

Verificando seu trabalho

Existem várias maneiras de verificar se seus cálculos em nível de tipo estão fazendo o que você espera. Aqui estão algumas abordagens. Faça dois tipos Ae B, que você deseja verificar são iguais. Em seguida, verifique se o seguinte compila:

• Equal[A, B]
  • com: traço Equal[T1 >: T2 <: T2, T2]( retirado do apocolisp )
• implicitly[A =:= B]

Como alternativa, você pode converter o tipo em um valor (conforme mostrado acima) e fazer uma verificação de tempo de execução dos valores. Por exemplo assert(toInt(a) == toInt(b)), onde aé do tipo Ae bé do tipo B.

Recursos adicionais

O conjunto completo de construções disponíveis pode ser encontrado na seção de tipos do manual de referência do scala (pdf) .

Adriaan Moors tem vários artigos acadêmicos sobre construtores de tipos e tópicos relacionados com exemplos de scala:

• Genéricos de um tipo superior (pdf)
• Polimorfismo do Construtor de Tipo para Scala: Teoria e Prática (pdf) (tese de doutorado, que inclui o artigo anterior de Moors)
• Inferência de polimorfismo de construtor de tipo

Apocalisp é um blog com muitos exemplos de programação em nível de tipo em scala.

• A Programação em nível de tipo no Scala é um fantástico tour guiado de alguma programação em nível de tipo que inclui booleanos, números naturais (como acima), números binários, listas heterogêneas e muito mais.
• Mais Scala Typehackery é a implementação do cálculo lambda acima.

ScalaZ é um projeto muito ativo que fornece funcionalidade que estende a API Scala usando vários recursos de programação de nível de tipo. É um projeto muito interessante e com muitos seguidores.

MetaScala é uma biblioteca de nível de tipo para Scala, incluindo metatipos para números naturais, booleanos, unidades, HList, etc. É um projeto de Jesper Nordenberg (seu blog) .

O Michid (blog) tem alguns exemplos incríveis de programação em nível de tipo em Scala (de outra resposta):

• Metaprogramação com Scala Parte I: Adição
• Metaprogramação com Scala Parte II: Multiplicação
• Metaprogramação com Scala Parte III: Aplicação de função parcial
• Metaprogramação com Scala: Compilação condicional e desenrolamento de loop
• Codificação de nível de tipo Scala do cálculo SKI

Debasish Ghosh (blog) também tem algumas postagens relevantes:

• Abstrações de ordem superior em scala
• A digitação estática oferece uma vantagem inicial
• Scala implica classes de tipo, aqui vou eu
• Refatoração em classes de tipo scala
• Usando restrições de tipo generalizadas
• Como os scalas digitam palavras do sistema para você
• Escolher entre membros do tipo abstrato

(Tenho feito pesquisas sobre esse assunto e aqui está o que aprendi. Ainda sou novo nisso, então, aponte quaisquer imprecisões nesta resposta.)

Além dos outros links aqui, também há minhas postagens no blog sobre metaprogramação de nível de tipo em Scala:

• Metaprogramação com Scala Parte I: Adição
• Metaprogramação com Scala Parte II: Multiplicação
• Metaprogramação com Scala Parte III: Aplicação de função parcial
• Metaprogramação com Scala: Compilação condicional e desenrolamento de loop
• Codificação de nível de tipo Scala do cálculo SKI

Como sugerido no Twitter: Shapeless: Uma exploração da programação genérica / politípica em Scala por Miles Sabin.

• Sing , uma biblioteca de metaprogramação em nível de tipo no Scala.
• O início da programação em nível de tipo em Scala

Scalaz possui código fonte, wiki e exemplos.