Implementación de la extensión Active Patterns para OCaml

sobre el proyecto

En la primavera de 2020, como parte de la práctica de primavera en el Computer Science Center, estaba desarrollando un nuevo diseño para el lenguaje de programación OCaml bajo la estricta guía de Dmitry Kosarev .

Por qué OCaml

OCaml es una de las implementaciones más exitosas y desarrolladas de sincretismo de programación industrial (por lo tanto, multi-paradigma, multiplataforma, compilador muy rápido, alta productividad del código generado) y matemáticas (de ahí el sistema de tipo de vanguardia con una implementación poderosa de inferencia de tipo, expresividad y extensibilidad lenguaje, cercanía a la notación matemática y semántica).



Al mismo tiempo, la comunidad lingüística es muy selectiva y poco a poco añade al lenguaje solo construcciones muy demandadas, siempre que no introduzcan restricciones en el lenguaje existente. Por lo tanto, el núcleo del lenguaje es muy pequeño e intuitivo, y OCaml es utilizado con agrado tanto por desarrolladores industriales como, por ejemplo, matemáticos del Departamento de Álgebra Superior y Teoría de Números de la Universidad Estatal de San Petersburgo .



Para profundizar en el tema, sugiero echar un vistazo a los artículos OCaml para las masas y Por qué OCaml .



Actualmente, se está trabajando para implementar un sistema multinúcleo para OCaml, junto con efectos algebraicos, que simultáneamente aumentarán el rendimiento general del lenguaje y eliminarán las limitaciones existentes del sistema de tipos asociadas con el hecho de que el lenguaje permite cálculos impuros.

Patrones coincidentes y patrones activos

Mi trabajo se ha centrado principalmente en la construcción de coincidencia de patrones, que se usa ampliamente en lenguajes de programación funcional.

Para ilustrar, considere un ejemplo simple de rotar un nodo en un árbol binario. En el estilo imperativo más común, el código probablemente se vería así:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t

Y aquí está el mismo código escrito usando la construcción de coincidencia de patrones:

let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x

Al utilizar este diseño, tenemos las siguientes ventajas:

• alta expresividad;
• comprobación de la integridad , que es una propiedad fundamental para la comprobación de la corrección y la refactorización del programa;
• esquemas de compilación eficientes.

La verificación de integridad significa que el compilador, conociendo la definición de tipo, puede verificar para cada coincidencia si es cierto que se han analizado todas las alternativas posibles y que no hay ramas inalcanzables, sin importar cuán complejas sean las muestras y sin importar cómo se crucen entre sí. Por lo tanto, si cambia la definición de tipo (agregando nuevas alternativas, eliminando o cambiando las existentes), el compilador amablemente le dará todos los lugares en el código que fueron directamente afectados.



Por ejemplo, si agregué nuevas construcciones al árbol de sintaxis, el compilador me mostrará el código de escritura AST hasta el cuerpo de la función, donde necesito escribir el código de escritura para nuevas construcciones:







esta propiedad hace que OCaml sea muy resistente a la refactorización y otros cambios de código.



A pesar de todas las ventajas descritas, también existe una limitación muy seria de aplicabilidad. ¿Lo has notado? La definición del tipo debe ser pública (para que el compilador pueda mostrar las alternativas que lo componen). Y esto, por supuesto, rompe de inmediato incluso las abstracciones más simples. Por ejemplo, si queremos definir la interfaz de lista más simple, no hay forma de saber de antemano qué definición de tipo exportar:

module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

Sin embargo, este problema no es fundamental y, como se señaló en 1987, es posible lograr la coincidencia de patrones en tipos abstractos.

Formulación del problema

Desde 1987, se han presentado muchos diseños diferentes en la literatura para resolver este problema, aquí hay solo algunos de ellos:







Al comienzo del proyecto, ya se había trabajado en una elección razonable y objetiva de una solución específica para la implementación , el más ventajoso fue la extensión de patrones activos implementada en el lenguaje F #.



El objetivo del proyecto era comenzar a implementar Active Patterns para el compilador OCaml y avanzar en la medida de lo posible.

Patrones activos

La idea misma de los patrones activos (así como las extensiones similares) es muy simple: dado que la abstracción se logra al ocultar la implementación dentro de la función, es necesario permitir una llamada a una función dentro de la coincidencia de patrones que convertiría el valor desconocido del tipo de datos abstracto en una lista conocida de alternativas. Los patrones activos codifican esta lista de alternativas justo dentro del nombre de la función. Entonces, en la interfaz de la lista anterior, debe agregar la siguiente función (|Cons|Nil|):

module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

El resultado es un tipo de suma anónimo choice2que tiene la siguiente definición (hay tipos generados similares hasta choice32):

type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b

Por lo tanto, la función (|Cons|Nil|)convertirá la lista en una de dos alternativas: ya sea en un par de cabeza y cola de la lista, o en una alternativa vacía, lo que significa que la lista estaba vacía.



Definir tal función para una lista estándar es trivial y se vería así:

let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)

Como ejemplo de uso, considere una función que elimina duplicados consecutivos en una lista:

(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))

Tenga en cuenta que se conservan todos los beneficios de la coincidencia de patrones: la sintaxis de coincidencia es la misma y las comprobaciones de integridad pueden funcionar en su totalidad. Compilar de manera eficiente una solución de este tipo está fuera del alcance de esta descripción general, pero también es posible.

Progreso

Como parte de este trabajo, fue posible implementar el análisis y la escritura de la extensión para el compilador OCaml versión 4.09, los resultados se presentan aquí .



El analizador del compilador se implementa mediante el generador de analizador avanzado Menhir . Menhir tiene un manual bastante completo y detallado , pero incluso con él no siempre estaba claro cómo se puede establecer la regla de inferencia, y cómo no y por qué. El parche del analizador resultante es bastante pequeño y simple, pero el camino hacia él pasa por 10-15 conflictos de reducción-reducción y reducción-reducción, cuyo análisis y corrección llevó algún tiempo:







Me gustaría rendir homenaje a los desarrolladores de Menhir y agradecerles su trabajo para detallar y aclarar los errores. Una vez que el analizador-generador falló en ilustrar el conflicto y tuvo que analizarlo de acuerdo con el autómata construido para 1500 estados. Esto requirió, por supuesto, un orden de magnitud más de tiempo.



La escritura de extensiones fue especialmente difícil. El código de mecanografía tiene unas 37.000 líneas de largo y está casi indocumentado, lo que dificulta que un principiante lo adivine. Me salvó un artículo de Oleg Kiselev , que explica los aspectos clave de la implementación.



Otra conclusión que hice por mí mismo es no olvidar usar las versiones antiguas del proyecto. Por ejemplo, aquí hay una comparación cuantitativa del mismo tipo de escritura en las versiones 2019 y 2005:







La versión 2019 contiene análisis y advertencias del compilador, así como detalles técnicos adicionales que no me interesaron. Para entender, solo tuve que mirar la versión 2005, que contiene solo acciones clave.



Finalmente, la principal conclusión a la que llegué durante mi trabajo es la confirmación de que la documentación para proyectos de código abierto es de vital importancia. Por muy expresivo que sea el lenguaje, el código fuente solo puede decir cómo se comporta una función, no qué hace o por qué lo hace de la forma en que lo hace. Es muy difícil leer las cadenas de llamadas type_self_pattern-> type_cases-> t ype_pat-> type_pat'-> type_pat_auxy averiguar qué función necesita; o solo un nombre de parámetroconstradivina qué constructores y por qué deberían escribirse aquí.



La necesidad de mirar los casos de uso cada vez ralentiza al programador y se cansa muy rápidamente: permítame recordarle la regla "siete, más o menos dos": la misma cantidad de objetos que una persona puede, en promedio, tener en cuenta simultáneamente. Y cuando finalmente comprende el significado del parámetro dentro de la sexta función anidada y de repente se da cuenta de que no recuerda por qué lo necesitaba, o resulta que no lo necesitaba, se pone muy triste por la cantidad de tiempo invertido.

Conclusión

Como parte de un proyecto, pude implementar el análisis y la escritura de patrones activos. El compilador que parcheé puede analizar y escribir el archivo con cualquier ejemplo de uso de patrones activos.



A continuación, debe modificar el esquema de compilación (OCaml utiliza una compilación optimizadora no trivial de coincidencia de patrones) y comprobaciones de integridad del esquema, que el equipo de desarrollo del compilador de OCaml reescribió casi por completo durante el trabajo en el proyecto.



Espero que esta implementación aún se complete, conmigo o sin mí. A pesar de todas las dificultades, fue genial probarse a sí mismo desarrollando un compilador industrial para su lenguaje favorito.

Autor:

Alexander Bashkirov es un estudiante del Centro de Ciencias de la Computación y un programa de licenciatura de cuarto año en Ingeniería de Software en la Universidad Estatal de San Petersburgo, un empleado de JetBrains.