Testes ou tipos? - Versão ferrugem

Alguns dias atrás, 0xd34df00d publicou uma tradução de um artigo aqui que descreve o que você pode aprender sobre uma função em diferentes idiomas, se você a considera uma "caixa preta" sem usar informações sobre sua implementação (mas, é claro, sem impedi-la de usar o compilador). Obviamente, as informações recebidas dependem muito do idioma - quatro exemplos foram considerados no artigo original:

• Python - informações mínimas dinamicamente digitadas, apenas testes fornecem algumas dicas;
• C - tipicamente estaticamente fraco, sem muito mais informações;
• Haskell - fortemente tipado estaticamente, com funções puras, muito mais informações;
• Idris é uma linguagem com tipos dependentes, há informações suficientes para provar a correção da função durante a compilação.

"Há C, há Haskell, mas onde está Rust ?!" - imediatamente a questão foi levantada. A resposta está sob o corte.

Lembre-se da condição do problema:

Deixe uma lista e algum significado ser dado. É necessário retornar o índice desse valor na lista ou indicar que esse valor não está na lista.

Para os impacientes - todas as opções discutidas abaixo podem ser vistas no playground Rust .
Vamos lá!

Pesquisa simples

Começaremos com uma assinatura quase ingênua, que, de fato, difere do código C apenas em alguns elementos idiomáticos:

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

O que sabemos sobre esse recurso? Bem ... não tanto, na verdade. Obviamente, ter Option<usize> nos valores retornados é muito melhor do que C nos forneceu, mas ainda não temos informações sobre a semântica da função. Em particular, não há garantia de que não haverá efeitos colaterais, nem pode haver nenhuma maneira de verificar o comportamento esperado.

Um teste escrito corretamente pode corrigir a situação? Nós olhamos:

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

Em geral, não recebemos nada de novo - todas as mesmas verificações que poderíamos fazer facilmente com o Python (e, olhando para o futuro, os testes não darão praticamente nada no futuro).

Use os genéricos, Luke!

Mas é realmente bom que somos forçados a usar apenas números assinados de 32 bits? A bagunça. Nós corrigimos:

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

Sim! Isso já é alguma coisa. Agora podemos pegar fatias, consistindo em quaisquer elementos que possamos comparar para igualdade. Polimorfismo explícito é quase sempre melhor que implícito e quase sempre melhor que nenhum, é?

No entanto, essa função pode passar inesperadamente no seguinte teste para nós:

 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 imediatamente alguma falha de nossa parte, porque, de acordo com a especificação original, essa chamada teria que retornar Some(0) . Obviamente, o problema aqui é devido à especificidade dos tipos com uma comparação parcialmente definida em geral e flutuadores em particular.
Suponha que agora desejamos nos livrar de um problema desse tipo - por isso, apenas reforçamos os requisitos para o tipo El:

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

Agora, exigimos não apenas a possibilidade de comparação para igualdade - exigimos que essa comparação seja uma relação de equivalência . Isso restringe um pouco o intervalo de parâmetros possíveis, mas agora os tipos e testes sugerem (embora não indique explicitamente) que o comportamento esperado deve realmente se encaixar na especificação.

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

Como antes, apenas mais rigoroso

No entanto, por exemplo, as garantias oferecidas pelo compilador em estágios já conhecidos não são suficientes para nós. Ou, digamos, não queremos (por um motivo ou outro) entrar em uma pilha, mas queremos trabalhar na pilha, o que significa que precisamos de uma matriz em vez de um vetor, mas ao mesmo tempo queremos que nosso código seja generalizado para diferentes tamanhos da matriz . Ou queremos que a função seja otimizada o máximo possível para cada tamanho específico da lista de entrada.

Em resumo, precisamos de uma matriz genérica - e o Rust já possui um pacote que a fornece literalmente .

Agora temos à nossa disposição o seguinte 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>, { // 10000    } 

O que sabemos desse código? Que a função use uma matriz de algum tamanho fixo, refletida em seu tipo (e compilada independentemente para cada tamanho). Até agora, isso não muda muito - no final, exatamente as mesmas garantias, não apenas no estágio de monomorfização, mas em tempo de execução, fornecendo um corte à versão anterior.

Mas podemos ir ainda mais longe.

Aritmética de nível de tipo

O artigo original mencionava várias garantias que recebemos de Idris e que não conseguimos obter de mais ninguém. Um deles - e talvez o mais simples, porque, para isso, você nem precisa escrever uma prova completa ou um teste completo, mas apenas especificar um pouco o tipo, diz que o valor de retorno, se existir (ou seja, se não for Nothing ), é garantido que não exceda o comprimento da lista de entrada.

Parece que a condição necessária para essa garantia é a presença de tipos dependentes, bem, ou pelo menos algum tipo de similaridade, e seria estranho esperar algo assim da Rust, certo?

Conheça - typenum . Com isso, nossa função pode ser representada assim:

 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>, { // 10000    } 

"Que diabos é essa magia negra ?!" - você pergunta. E você certamente estará certo: o typenum é essa magia negra, e as tentativas de usá-la pelo menos de alguma maneira são duplamente.

No entanto, a assinatura dessa função é bastante inequívoca.

• A função aceita uma matriz de elementos El de comprimento Size e um elemento do tipo El.
• A função retorna um valor Option, que, se for Some,
  
  • É um objeto de característica baseado no tipo UnsignedLessThan<T> , que aceita o tipo Tamanho como parâmetro;
  • por sua vez, a característica UnsignedLessThan<T> IsLess<T> implementada para todos os tipos que implementam Unsigned e IsLess<T> para os quais IsLess<T> retorna B1, ou seja, verdade

Em outras palavras, dessa maneira, escrevemos uma função que é garantida para retornar um número não negativo (não assinado) menor que o tamanho original da matriz (ou melhor, é claro, ela retorna esse mesmo objeto de característica, do qual devemos chamar posteriormente o método as_usize , garantido para retornar esse número) .

Existem exatamente dois truques nessa abordagem:

1. Podemos perder visivelmente o desempenho. Se de repente, por algum motivo, tal função estiver na parte "quente" do programa, a necessidade constante de chamadas dinâmicas poderá ser uma das operações mais lentas. No entanto, essa desvantagem pode não ser tão significativa quanto parece, mas há um segundo:
2. Para que essa função seja compilada corretamente, precisaremos realmente escrever dentro dela a prova da correção de seu trabalho, ou "enganar" o sistema de tipos de maneira unsafe . O primeiro é muito complicado para o artigo de sexta-feira, mas o segundo é simplesmente uma farsa.

Conclusão

Obviamente, na prática, nesses casos, será usada a segunda implementação (recebendo uma fatia de um tipo arbitrário) ou a implementação sob um spoiler (recebendo um objeto iterável). Todos os argumentos subsequentes quase certamente não têm interesse prático e servem apenas como um exercício de trabalho com um sistema de tipos.

No entanto, o fato de que no sistema do tipo Rust possa ser capaz de emular uma das características do sistema obviamente mais forte do tipo Idris é, na minha opinião, bastante indicativo.