Testes vs. Tipos - Versão ferrugem

Alguns dias atrás, 0xd34df00d publicou a tradução do artigo , descrevendo as informações possíveis sobre alguma função se a usarmos como uma "caixa preta", sem tentar ler sua implementação. Obviamente, essa informação é bem diferente de idioma para idioma; no artigo original, quatro casos foram considerados:

• Python - digitação dinâmica, quase nenhuma informação da assinatura, algumas dicas são obtidas pelos testes;
• C - digitação estática fraca, um pouco mais de informação;
• Haskell - digitação estática forte, com funções puras por padrão, muito mais informações;
• Idris-dependente digitando, compilador pode provar a correção da função.

"Aqui está C e há Haskell, e quanto a Rust?" - essa foi a primeira pergunta na discussão a seguir. A resposta está aqui.

Vamos primeiro relembrar a tarefa:

Dada uma lista de valores e um valor, retorne o índice do valor na lista ou signifique que ele não está presente na lista.

Se alguém não quiser não quiser ler tudo isso, os exemplos de código são fornecidos no playground Rust .
Caso contrário, vamos começar!

Pesquisa simples

A primeira abordagem será a assinatura quase ingênua, diferindo do código C apenas em alguns elementos idiomáticos:

fn foo(x: &[i32], y: i32) -> Option<usize> { // Implementation elided } 

O que sabemos sobre essa função? Bem, de fato - não muito. Obviamente, a Option<usize> como valor de retorno é uma grande melhoria em relação ao que for fornecido por C, mas não há informações sobre a semântica da função. Em particular, não temos garantia de que os efeitos colaterais estejam ausentes e não há como verificar o comportamento desejado.

Um teste pode melhorar isso? Veja aqui:

 #[test] fn test() { assert_eq!(foo(&[1, 2, 3], 2), Some(1)); assert_eq!(foo(&[1, 2, 3], 4), None); } 

Parece que nada mais - todas essas verificações podem ser iguais no Python (e, antecipadamente, os testes serão de pouca ajuda para todo o artigo).

Use os genéricos, Luke!

Mas é bom que tenhamos que usar apenas números assinados de 32 bits? Corrigindo:

 fn foo<El>(x: &[El], y: El) -> Option<usize> where El: PartialEq, { // Implementation elided } 

Bem, isso é alguma coisa! Agora podemos pegar qualquer fatia, consistindo em elementos de qualquer tipo comparável. Polimorfismo explícito é quase sempre melhor que implícito (olá, Python) e quase sempre melhor que nenhum polimorfismo (olá, C), certo?

Embora essa função possa passar inesperadamente neste teste:

 fn refl<El: PartialEq + Copy>(el: El) -> Option<usize> { foo(&[el], el) // should always return Some(0), right? } #[test] fn dont_find_nan() { assert_eq!(refl(std::f64::NAN), None); } 

Isso indica um ponto que falta, pois a especificação deseja que a função refl retorne sempre Some(0) . Obviamente, tudo isso se deve ao comportamento específico dos tipos parcialmente equivalentes em geral e flutua em particular.
Talvez nós queremos nos livrar desse problema? Então, simplesmente apertaremos o limite no tipo El:

 fn foo<El>(x: &[El], y: El) -> Option<usize> where El: Eq, { // Implementation elided } 

Agora, exigimos não apenas que o tipo seja comparável - exigimos que essas comparações sejam equivalências . Obviamente, isso limita os tipos possíveis de uso com essa função, mas agora a assinatura e os testes sugerem que o comportamento deve se encaixar na especificação.

 fn foo<'a, El: 'a>(x: impl IntoIterator<Item = &'a El>, y: El) -> Option<usize> where El: Eq, { // Implementation elided } 

Como antes, mas um pouco mais rigoroso

Mas agora, talvez precisemos de mais algumas garantias. Ou queremos trabalhar na pilha (e, portanto, não podemos usar o Vec ), mas precisamos generalizar nosso código para todos os tamanhos de matriz possíveis. Ou queremos compilar a função otimizada para cada tamanho de matriz de concreto.

De qualquer forma, precisamos de uma matriz genérica - e há uma caixa no Rust, fornecendo exatamente isso .

Agora, aqui está o nosso código:

 use generic_array::{GenericArray, ArrayLength}; fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<usize> where El: Eq, Size: ArrayLength<El>, { // Implementation elided } 

O que sabemos disso? Sabemos que a função terá a matriz de algum tamanho específico, refletida em seu tipo (e será compilada independentemente para cada tamanho). Por enquanto, isso não é quase nada - as mesmas garantias foram fornecidas em tempo de execução pela implementação anterior.

Mas podemos ir mais longe.

Aritmética em nível de tipo

O artigo inicial mencionava várias garantias fornecidas por Idris que eram impossíveis de obter de outros idiomas. Um deles - e provavelmente o mais simples, já que não envolve provas ou testes, apenas uma pequena alteração nos tipos - afirma que o valor de retorno, se não for o Nothing , sempre será menor que o comprimento da lista.

Parece que os tipos dependentes - ou algo parecido - são necessários para essa garantia, e não podemos obter o mesmo da Rust, certo?

Conheça o typenum . Usando-o, podemos escrever nossa função da seguinte maneira:

 use generic_array::{ArrayLength, GenericArray}; use typenum::{IsLess, Unsigned, B1}; trait UnsignedLessThan<T> { fn as_usize(&self) -> usize; } impl<Less, More> UnsignedLessThan<More> for Less where Less: IsLess<More, Output = B1>, Less: Unsigned, { fn as_usize(&self) -> usize { <Self as Unsigned>::USIZE } } fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<Box<dyn UnsignedLessThan<Size>>> where El: Eq, Size: ArrayLength<El>, { // Implementation elided } 

"O que é essa magia negra ?!" - você poderia perguntar. E você está certo: o typenum é uma magia negra, e qualquer tentativa de usá-lo é ainda mais mágica.

Mas essa assinatura de função é bastante concreta.

• É preciso uma matriz de El's com o tamanho Size e mais um El.
• Retorna uma opção que, se for alguma,
  
  • mantém um objeto de característica , com base na característica UnsignedLessThan<Size> ;
  • e o UnsignedLessThan<T> é implementado sempre que Unsigned e IsLess<T> são implementados e IsLess<T> retorna B1, ou seja, true.

Em outras palavras, é garantido que essa função retorne um número inteiro não assinado menor que o tamanho da matriz (a rigor, ele retorna o objeto de característica, mas podemos chamar o método as_usize e obter o número inteiro).

Agora posso falar de duas grandes advertências:

1. Podemos obter uma perda de desempenho. Se, de alguma forma, essa função estiver no caminho "quente" do programa, os despachos dinâmicos constantes poderão desacelerar todo o processo. Isso pode não ser uma grande preocupação, de fato, mas há outra:
2. Para que essa função seja compilada, é preciso escrever a prova de sua exatidão dentro dela ou enganar o sistema de tipos com alguma unsafe . O primeiro é bastante complexo, e o último é apenas trapaça.

Conclusão

Obviamente, na prática, geralmente usaremos a segunda abordagem (com fatia genérica) ou a abordagem no spoiler (com iterador). Toda discussão subsequente provavelmente não tem nenhum interesse prático e é aqui apenas como um exercício com tipos.

De qualquer forma, o fato de o sistema do tipo Rust poder emular o recurso do sistema do tipo Idris mais forte, quanto a mim, é bastante impressionante por si só.