👩🏽‍💼 👩🏿‍🤝‍👩🏼 💼 Implémentation de l'extension Active Patterns pour OCaml 🙀 🥀 🚨

à propos du projet

Au printemps 2020, dans le cadre de la pratique printanière au Computer Science Center, je développais un nouveau design pour le langage de programmation OCaml sous la stricte direction de Dmitry Kosarev .

Pourquoi OCaml

OCaml est l'une des implémentations les plus réussies et les plus développées du syncrétisme de programmation industrielle (d'où multi-paradigme, multi-plateforme, compilateur très rapide, productivité élevée du code généré) et des mathématiques (d'où le système de type de pointe avec une implémentation puissante de l'inférence de type, de l'expressivité et de l'extensibilité langage, proximité de la notation mathématique et de la sémantique).

En même temps, la communauté linguistique est très sélective et n'ajoute lentement à la langue que des constructions très demandées, à condition qu'elles n'introduisent pas de restrictions dans la langue existante. Par conséquent, le noyau du langage est très petit et intuitif, et OCaml est utilisé avec plaisir par les développeurs industriels et, par exemple, par les mathématiciens du département d'algèbre supérieure et de théorie des nombres de l'Université d'État de Saint-Pétersbourg .

Pour approfondir le sujet, je vous suggère de jeter un œil aux articles OCaml pour les masses et Why OCaml .

Actuellement, des travaux sont en cours pour implémenter un système multicœur pour OCaml, couplé à des effets algébriques, qui augmentera simultanément les performances globales du langage et éliminera les limitations existantes du système de types associées au fait que le langage autorise des calculs impurs.

Correspondance de motifs et motifs actifs

Mon travail s'est principalement concentré sur la construction de correspondance de modèles, largement utilisée dans les langages de programmation fonctionnelle.

Pour illustrer, considérons un exemple simple de rotation d'un nœud dans un arbre binaire. Dans le style impératif le plus courant, le code ressemblerait probablement à ceci:

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

Et voici exactement le même code écrit en utilisant la construction de correspondance de modèle:

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

Lors de l'utilisation de cette conception, nous avons les avantages suivants:

haute expressivité;
le contrôle d'exhaustivité , qui est une propriété critique pour le contrôle d'exactitude et la refactorisation du programme
des schémas de compilation efficaces.

Le contrôle de complétude signifie que le compilateur, connaissant la définition de type, peut vérifier pour chaque correspondance s'il est vrai que toutes les alternatives possibles ont été analysées et qu'il n'y a pas de branches inaccessibles, quelle que soit la complexité des échantillons et quelle que soit la façon dont ils se croisent. Ainsi, si vous modifiez la définition de type (ajout de nouvelles alternatives, suppression ou modification de celles existantes), le compilateur vous donnera gentiment tous les endroits du code qui ont été directement affectés.

Par exemple, si j'ai ajouté de nouvelles constructions à l'arborescence de syntaxe, le compilateur me montrera le code de frappe AST jusqu'au corps de la fonction, où je dois écrire le code de frappe pour les nouvelles constructions:

Cette propriété rend OCaml très résistant à la refactorisation et à d'autres changements de code.

Malgré tous les avantages décrits, il existe également une limitation très sérieuse de l'applicabilité. L'avez-vous remarqué? La définition de type doit être publique (pour que le compilateur puisse afficher les alternatives qui la composent). Et cela, bien sûr, décompose immédiatement les abstractions les plus simples. Par exemple, si nous voulons définir l'interface de liste la plus simple, il n'y a aucun moyen de dire à l'avance quelle définition de type exporter:

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

Cependant, ce problème n'est pas fondamental et, comme noté en 1987, il est possible de réaliser une correspondance de motifs sur des types abstraits.

Formulation du problème

Depuis 1987, de nombreux designs différents ont été présentés dans la littérature pour résoudre le problème, en voici quelques-uns:

Au début du projet, un travail avait déjà été fait sur un choix raisonnable et objectif d'une solution spécifique pour l'implémentation , le plus avantageux était l'extension Active patterns implémentée en langage F #.

Le but du projet était de commencer à implémenter Active Patterns pour le compilateur OCaml et de progresser dans la mesure du possible.

Modèles actifs

L'idée même des modèles actifs (ainsi que des extensions similaires) est très simple: puisque l'abstraction est obtenue en cachant l'implémentation à l'intérieur de la fonction, il est nécessaire d'autoriser un appel de fonction à l'intérieur de la correspondance de modèle qui convertirait la valeur inconnue du type de données abstrait en une liste connue d'alternatives. Les modèles actifs codent cette liste d'alternatives directement dans le nom de la fonction. Ainsi, dans l'interface de la liste ci-dessus, vous devez ajouter la fonction suivante (|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

Le résultat est un type de somme anonyme choice2qui a la définition suivante (il existe des types générés similaires jusqu'à choice32):

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

Ainsi, la fonction (|Cons|Nil|)convertira la liste en l'une des deux alternatives: soit une paire tête et queue, soit une alternative vide signifiant que la liste était vide.

Définir une telle fonction pour une liste standard est trivial et ressemblerait à ceci:

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

Comme exemple d'utilisation, considérons une fonction qui supprime les doublons consécutifs dans une liste:

(* 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))

Notez que tous les avantages de la correspondance de modèle sont conservés: la syntaxe de correspondance est la même et les contrôles d'exhaustivité peuvent fonctionner pleinement. Compiler efficacement une telle solution dépasse le cadre de cet aperçu, mais c'est également possible.

Le progrès

Dans le cadre de ce travail, il a été possible d'implémenter l'analyse et le typage de l'extension pour le compilateur OCaml version 4.09, les résultats sont présentés ici .

L'analyseur du compilateur est implémenté à l'aide du générateur d'analyseur avancé Menhir . Menhir a un manuel assez complet et détaillé , mais même avec lui, on ne savait pas toujours comment définir la règle d'inférence, ni comment et pourquoi. Le correctif d'analyseur résultant est assez petit et simple, mais le chemin pour y parvenir passe par 10 à 15 conflits de réduction et de réduction de décalage, dont l'analyse et la résolution ont pris un certain temps:

Je voudrais rendre hommage aux développeurs de Menhir et les remercier pour leur travail de détail et de clarification des erreurs. Une fois que l'analyseur-générateur n'a pas réussi à illustrer le conflit et a dû le démonter en utilisant l'automate construit pour 1500 états. Cela exigeait, bien sûr, un ordre de grandeur de plus de temps.

Le typage des extensions était particulièrement difficile. Le code de saisie prend environ 37 000 lignes et est presque non documenté, ce qui n'est pas facile à comprendre pour un débutant. J'ai été sauvé par un article d'Oleg Kiselev , qui explique les aspects clés de la mise en œuvre.

Une autre conclusion que je me suis faite est de ne pas oublier d'utiliser les anciennes versions du projet. Par exemple, voici une comparaison quantitative du même morceau de frappe dans les versions 2019 et 2005:

La version 2019 contient une analyse et des avertissements du compilateur, ainsi que des détails techniques supplémentaires qui ne m'intéressaient pas. Pour comprendre, il me suffisait de regarder la version 2005, qui ne contient que des actions clés.

Enfin, la principale conclusion que j'ai tirée au cours de mon travail est la confirmation que la documentation des projets open source est d'une importance cruciale. Aussi expressif que soit le langage, le code source peut seulement dire comment une fonction se comporte, pas ce qu'elle fait ou pourquoi elle le fait comme elle le fait. Il est très difficile de lire les chaînes d'appels type_self_pattern-> type_cases-> t ype_pat-> type_pat'-> type_pat_auxet de déterminer la fonction dont vous avez besoin; ou juste un nom de paramètreconstrdevinez quels constructeurs et pourquoi devraient être écrits ici.

Le besoin de regarder les cas d'utilisation à chaque fois ralentit le programmeur et se fatigue très vite: permettez-moi de vous rappeler la règle «sept, plus ou moins deux» - autant d'objets qu'une personne peut, en moyenne, garder simultanément à l'esprit. Et lorsque vous comprenez enfin la signification du paramètre à l'intérieur de la sixième fonction imbriquée et que vous réalisez soudainement que vous ne vous souvenez pas pourquoi vous en aviez besoin, ou qu'il s'avère que vous n'en aviez pas besoin, cela devient très triste à cause du temps passé.

Conclusion

Dans le cadre d'un projet, j'ai pu implémenter l'analyse et la saisie des modèles Active. Le compilateur que j'ai corrigé peut analyser et taper le fichier avec des exemples d'utilisation de modèles actifs.

Ensuite, vous devez modifier le schéma de compilation (OCaml utilise une compilation d'optimisation non triviale de la correspondance de modèles) et les vérifications d'exhaustivité du schéma, qui ont été presque complètement réécrits par l'équipe de développement du compilateur OCaml pendant le projet.

J'espère que cette implémentation sera encore terminée, avec ou sans moi. Malgré toutes les difficultés, c'était génial d'essayer par vous-même de développer un compilateur industriel pour votre langage préféré.

Auteur:

Alexander Bashkirov est un étudiant du Centre d'informatique et un programme de licence de 4e année en génie logiciel à l'Université d'État de Saint-Pétersbourg, un employé de JetBrains.

Implémentation de l'extension Active Patterns pour OCaml