Surcharge des opérateurs : Elixir versus Ruby

Cet article a été écrit avant l'introduction de l'opérateur ** en Elixir qui aurait grandement simplifié la secode partie !

Le puzzle d'aujourd'hui sur Advent Of Code demande d'implémenter un simple calculateur qui lit des expressions mathématiques telles et en donne le résultat. Par exemple:

# Exemple 1
1 + 2 * 3 + 4 * 5 + 6

# Exemple 2
1 + (2 * 3) + (4 * (5 + 6))

Mais, afin que cela ait un quelconque intérêt, les règles suivantes s'appliquent :

Pour la première partie de l'exercice, les opérateurs n'ont plus de précédence, on exécute simplement les opérations dans l'ordre. Les « vraies » règles mathématiques veulent que 1 + 2 * 3 soit exécuté comme 1 + (2 * 3), ce qui donne 7. Dans cet exercice, cela sera plutôt interprété comme (1 + 2) * 3, donc 9.
Les parenthèses sont cependant toujours prises en compte, donc si l'on écrit explicitement 1 + (2 * 3) alors on doit bien obtenir 7.
Pour la seconde partie, les parenthèses comptent toujours, mais l'opérateur + devient prioritaire par rapport à *.
4 * 5 + 6 est donc interprété comme 4 * (5 + 6).

Sans ces règles, il suffirait d'utilser la fonction eval() en JavaScript, PHP, Ruby ou un équivalent dans d'autres langages. Avec ces règles, il est nécessaire de parser l'expression méthématique puis d'implémenter un interpréteur.

Advent Of Code nous donne un fichier contenant plusieurs calculs comme ceux présentés ci-dessus. L'exercice consiste à tous les exécuter puis à faire la somme de tous les résultats. D'abord avec les règles de la partie 1, puis avec les règles de la seconde partie.

Le fichier contient environ 380 lignes afin que tout être humain normalement constitué n'envisage jamais de le faire à la main par pure flemme, et également afin de s'assurer que la solution soit suffisament rapide.

Dans le cadre d'Advent Of Code, la « solution » désigne non pas le nombre final à trouver mais le code qui permet de le trouver. Chaque joueur reçoit un fichier "input" différent, l'important est de trouver le code qui permet de trouver la bonne réponse pour un input donné.

# Extrait de mon fichier d'input

6 + 9 * (6 + 7 + (3 + 9))
(6 * 7) + 2
9 + (4 * (4 * 2 + 6 + 9) + 2 + 4 * 5 + 9)
2 * (8 + 6 * 2 * 6 + 2 * (6 + 5 + 9 + 6)) * 2 * 6
(5 * 7 * 4) * 3 * (3 * 6)

Voici une bonne solution qui implémente un parser et un interpréteur dont on peut configurer la précédence des opérateurs.

Surcharge des opérateurs en Ruby

Voici maintenant une solution en Ruby que j'ai trouvée sur reddit :

# Part 1 in ruby
class Integer
  def -(other)
   self * other
  end
end
total = 0
File.open('day18_input.txt', 'r').each do |line|
  total += eval(line.tr('*', '-'))
end
puts total

# Part 2 in ruby
class Integer
  def **(other)
    self + other
  end
end
total = 0
File.open('day18_input.txt', 'r').each do |line|
  total += eval(line.gsub(/+/, '**'))
end
puts total

L'idée du hack que l'on voit ici est d'utiliser le parseur natif du langage pour faire tout le travail. On ne peut pas contrôler la précédence des opérateurs au niveau du langage, car celle-ci est considérée au moment ou le code source est transformé en abstract syntax tree. L'astuce consiste donc à réimplémenter un opérateur qui a la précédence souhaitée, directement sur la classe Integer, en lui faisant faire l'opération que l'on veut, puis faire la même transformation sur le texte en input.

Evil, non ? C'est absolument dégueulasse en termes de bonnes pratiques, nous sommes bien d'accord. Mais le problème posé par Advent Of Code demande simplement d'implémenter l'addition et la multiplication avec une précédence spécifique, et ce code répond parfaitement au problème.

Pour la première partie de l'exercice, on souhaite que l'addition et la multiplication soient traitées avec la même précédence. Il faut donc remplacer l'opérateur *, prioritaire par rapport à +, par un opérateur de même précédence que +.

L'auteur·e de ce code à donc choisi la soustraction, -. Il/elle remplace donc le caractère * par - dans l'input :

line.tr('*', '-')

Pour que cela fonctionne, il faut quand même qu'une multiplication soit faite, et non une soustraction, donc on surcharge l'opérateur - pour la classe Integer, en effectuant la multiplication à la place :

class Integer
  def -(other)
   self * other
  end
end

Enfin il ne reste qu'à lire chaque ligne du fichier, appeler eval() et faire la somme des résultats.

Pour la seconde partie, on ne veut pas une précédence neutre entre + et *. On souhaite l'inverser. On remplace donc l'opérateur + par un opérateur encore plus prioritaire que *, l'opérateur ** (exponent).

Ces exercices « pour le fun » sont vraiment les seuls cas au monde où il est acceptable de surcharger un opérateur de base sur les nombres entiers – à mon sens. À moins que la fin du monde approche et que vous n'ayez que quelques minutes pour implémenter une solution d'urgence qui va éviter une guerre nucléaire… D'autant plus qu'en Ruby, la rédéfinition de l'opérateur vaut pour le runtime entier, pas simplement pour le scope courant (mais je peux me tromper, je connais très mal ce langage). C'est donc une pratique innomable à laquelle ce code à recours ici. Mais pour Advent Of Code, tout est permis.

Surcharge des opérateurs en Elixir

Voyons maintenant comment on peut faire la même chose avec Elixir.

Première partie

Pour la première partie il est possible de faire quelque chose d'équivalent. Il nous faut un contexte d'exécution pour surcharger l'opérateur - et le transformer en multiplication, donc nous définissons un module.

Dans ce module nous importons explicitement Kernel (qui est normalement importé d'office) pour omettre d'importer la fonction Kernel.-/2, ce qui nous permet de définir cet opérateur sans qu'il y ait clash.

defmodule NoPrecedence do
  import Kernel, except: [-: 2]

  def a - b, do: a * b

  # ...

Ensuite nous définissons l'interprétation de la commande.

Nous prenons comme base l'environnement courant __ENV__ pour y ajouter NoPrecedence.-/2 en tête de la liste des fonctions disponibles dans le scope. Cela nous donne notre environnement d'exécution – et nous sommes bien d'accord, un tel truc ne dois jamais partir en production !
Nous remplaçons "*" par "-" dans la chaîne de caractères afin d'utiliser notre opérateur - surchargé à la place de la multiplication.
Nous pouvons maintenant évaluer l'expression en appelant Code.eval_string/3 avec cette nouvelle chaîne, une liste vide comme bindings et notre environnement ~~corrompu~~ modifié. Cela nous retourne un tuple dont le premier élément (d'index 0) est le résultat de l'évaluation.

  # ...

  def eval(expression) do
    env = Map.update!(__ENV__, :functions, fn funs ->
      [{NoPrecedence, -: 2} | funs]
    end)

    expression
    |> String.replace("*", "-")
    |> Code.eval_string([], env)
    |> elem(0)
  end
end

Il est enfin temps d'exécuter tout l'input avec cette nouvelle solution !

for line <- File.stream!("day-18.inp") do
  NoPrecedence.eval(line)
end
|> Enum.sum()
|> IO.inspect(label: "part 1")

Et ça fonctionne ! J'ai testé avec mon input d'Advent Of Code et j'obtiens bien les résultats attendus.

Ça reste plus complexe et beaucoup plus long que son pendant Ruby, mais sans aucun impact sur le reste du runtime. Si par malheur il s'avère qu'un jour il ne reste que cette ultime solution pour résoudre un problème, on pourrait envisager un instant de la mettre en place. Reste à trouver quel genre de projet nous pousserait à faire une telle chose… je préfère ne pas y penser.

Seconde partie

Les choses se corsent ! Il n'y a pas d'opérateur ** en Elixir, et aucun autre opérateur left-to-right n'a de précédence supérieure à * et /.

Pour rappel, nous devons ici exécuter les + avant les *, c'est à dire l'inverse de la règle mathématique standard.

La solution reste simple :

Transformer les + en / ;
Transformer les * en - ;
Surcharger / et -.

Ainsi 2 * 4 + 8 s'écrira 2 - 4 / 8, la précédence aura comme effet d'interpréter ça comme 2 - (4 / 8), et notre surcharge effectuera finalement 2 * (4 + 8).

Hyper « simple » !

Voici le code intégral pour la partie 2. J'ai utilisé un for/reduce au lieu d'un for classique histoire de réduire le nombre d'itérations du code (et aussi réduire le nombre de lignes ! – espoir futile).

defmodule AdditionPrecedence do
  import Kernel, except: [-: 2, /: 2]

  def a / b, do: a + b
  def a - b, do: a * b

  def eval(expression) do
    env = Map.update!(__ENV__, :functions, fn funs ->
      [{AdditionPrecedence, -: 2}, {AdditionPrecedence, /: 2} | funs]
    end)

    expression
    |> String.replace("+", "/")
    |> String.replace("*", "-")
    |> Code.eval_string([], env)
    |> elem(0)
  end
end


for line <- File.stream!("day-18.inp"), reduce: 0 do
  sum -> sum + AdditionPrecedence.eval(line)
end
|> IO.inspect(label: "part 2")

Conclusion

Grâce à ce petit exercice j'ai pu comprendre un peu mieux le fonctionnement de l'environnement lors de la compilation. L'implémentation n'a pas été immédiate ; j'ai notamment du chercher pourquoi mes opérateurs surchargés n'étaient pas trouvés (fonction :erl_eval.-/2 manquante).