Pruebas o tipos? - Versión oxidada

Hace un par de días, 0xd34df00d publicó una traducción de un artículo aquí que describe lo que puede aprender sobre una función en diferentes idiomas, si la considera como un "recuadro negro" sin usar información sobre su implementación (pero, por supuesto, sin impedir que use el compilador). Por supuesto, la información recibida depende mucho del idioma: se consideraron cuatro ejemplos en el artículo original:

• Python: información mínima de tipo dinámico, solo las pruebas dan algunas pistas;
• C - débilmente estáticamente tipado, no mucha más información;
• Haskell: fuertemente tipado estáticamente, con funciones puras, mucha más información;
• Idris es un lenguaje con tipos dependientes, hay suficiente información para demostrar la corrección de la función durante la compilación.

"Hay C, hay Haskell, pero ¿dónde está Rust?" - Inmediatamente se planteó la pregunta. La respuesta está debajo del corte.

Recordemos la condición del problema:

Deja que se dé una lista y algún significado. Es necesario devolver el índice de este valor en la lista o indicar que este valor no está en la lista.

Para los impacientes: todas las opciones que se analizan a continuación se pueden ver en el área de juegos de Rust .
Vamos!

Búsqueda simple

Comenzaremos con una firma casi ingenua, que, de hecho, difiere del código C solo en algunos elementos idiomáticos:

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

¿Qué sabemos sobre esta característica? Bueno ... no tanto, en realidad. Por supuesto, tener Option<usize> en los valores de retorno es mucho mejor que lo que C nos proporcionó, pero aún no tenemos información sobre la semántica de la función. En particular, no hay garantía de que no habrá efectos secundarios, ni puede haber ninguna forma de verificar el comportamiento esperado.

¿Puede una prueba escrita correctamente arreglar la situación? Buscamos:

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

En general, no obtuvimos nada nuevo: todas las mismas comprobaciones que podríamos hacer fácilmente con Python (y, mirando hacia el futuro, las pruebas no darán prácticamente nada en el futuro).

¡Usa los genéricos, Luke!

Pero, ¿es realmente bueno que nos veamos obligados a usar solo números con signo de 32 bits? El desastre Arreglamos:

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

Si! Esto ya es algo. Ahora podemos tomar rebanadas, que consisten en cualquier elemento que podamos comparar para la igualdad. El polimorfismo explícito es casi siempre mejor que implícito y casi siempre mejor que ninguno, ¿verdad?

Sin embargo, dicha función puede pasar inesperadamente la siguiente prueba para nosotros:

 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); } 

Esto indica inmediatamente alguna falla de nuestra parte, porque de acuerdo con la especificación original, dicha llamada tendría que devolver Some(0) . Por supuesto, el problema aquí se debe a la especificidad de los tipos con una comparación parcialmente definida en general y flotantes en particular.
Supongamos ahora que queremos deshacernos de ese problema; para esto solo ajustamos los requisitos para el tipo El:

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

Ahora exigimos no solo la posibilidad de comparación para la igualdad, sino que exigimos que esta comparación sea una relación de equivalencia . Esto reduce un poco el rango de posibles parámetros, pero ahora tanto los tipos como las pruebas sugieren (aunque no indiquen explícitamente) que el comportamiento esperado realmente debería caer dentro de la especificación.

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

Como antes, solo más estricto

Sin embargo, por ejemplo, las garantías ofrecidas por el compilador en etapas ya conocidas no son suficientes para nosotros. O, digamos, no queremos (por una razón u otra) entrar en un montón, pero queremos trabajar en la pila, lo que significa que necesitamos una matriz en lugar de un vector, pero al mismo tiempo queremos que nuestro código se generalice a diferentes tamaños de la matriz. . O queremos que la función se optimice tanto como sea posible para cada tamaño específico de la lista de entrada.

En resumen, necesitamos una matriz genérica, y Rust ya tiene un paquete que lo proporciona textualmente .

Ahora tenemos a nuestra disposición el siguiente 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    } 

¿Qué sabemos de este código? Que la función toma una matriz de algún tamaño fijo, reflejada en su tipo (y compilada independientemente para cada tamaño). Hasta ahora, esto no cambia mucho: al final, exactamente las mismas garantías, no solo en la etapa de monomorfización, sino en tiempo de ejecución, proporcionaron un corte a la versión anterior.

Pero podemos ir aún más lejos.

Nivel aritmético tipo

El artículo original mencionaba varias garantías que recibimos de Idris y que nadie más podía obtener. Uno de ellos, y quizás el más simple, porque para ello ni siquiera necesita escribir una prueba completa o una prueba completa, sino solo para especificar un poco el tipo: dice que el valor de retorno, si existe (es decir, si no es Nothing ), se garantiza que no excederá la longitud de la lista de entrada.

Parece que la condición necesaria para tal garantía es la presencia de tipos dependientes, bueno, o al menos algún tipo de similitud, y sería extraño esperar algo así de Rust, ¿verdad?

Conoce - typenum . Con ella, nuestra función se puede representar así:

 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    } 

"¡¿Qué demonios es esta magia negra ?!" - usted pregunta Y ciertamente tendrá razón: typenum es esa magia negra, y los intentos de usarla al menos de alguna manera sensata son doblemente.

Sin embargo, la firma de esta función es bastante inequívoca.

• La función acepta una matriz de elementos El de longitud Tamaño y un elemento de tipo El.
• La función devuelve un valor de Opción que, si es Some,
  
  • Es un objeto de rasgo basado en el tipo UnsignedLessThan<T> , que acepta el tipo Size como parámetro;
  • a su vez, el IsLess<T> UnsignedLessThan<T> IsLess<T> implementa para todos los tipos que implementan Unsigned e IsLess<T> para los cuales IsLess<T> devuelve B1, es decir cierto

En otras palabras, de esta manera escribimos una función que garantiza que devolverá un número no negativo (sin signo) más pequeño que el tamaño original de la matriz (o más bien, por supuesto, devuelve este mismo objeto de rasgo, del que luego debemos llamar al método as_usize , garantizado para devolver dicho número) .

Hay exactamente dos trucos en este enfoque:

1. Podemos perder notablemente el rendimiento. Si de repente, por alguna razón, nuestra función se encuentra en la parte "activa" del programa, la necesidad constante de llamadas dinámicas puede ser una de las operaciones más lentas. Sin embargo, este inconveniente puede no ser tan significativo como parece, pero hay un segundo:
2. Para que esta función se compile correctamente, necesitaremos escribir en su interior la prueba de la corrección de su trabajo o "engañar" al sistema de tipos de manera unsafe . El primero es demasiado complicado para el artículo del viernes, pero el segundo es simplemente una estafa.

Conclusión

Por supuesto, en la práctica, en tales casos, se utilizará la segunda implementación (que recibe una porción de un tipo arbitrario) o la implementación bajo un spoiler (que recibe un objeto iterable). Es casi seguro que todos los argumentos posteriores no tienen ningún interés práctico y sirven únicamente como ejercicio para trabajar con un sistema de tipos.

Sin embargo, el hecho de que en el sistema de tipo Rust pueda emular una de las características del sistema de tipo Idris obviamente más fuerte es, en mi opinión, bastante indicativo.