Dagon est une bibliothèque Scala conçue pour la réécriture et l'optimisation de graphes orientés acycliques (DAG). Elle offre une compatibilité avec les versions 2.11, 2.12 et 2.13 de Scala, fonctionnant à la fois sur la JVM et Scala.js. L'objectif principal de Dagon est de fournir un mécanisme simple basé sur des règles pour identifier et transformer des motifs spécifiques au sein d'abrres de syntaxe abstraite (AST), permettant ainsi de simplifier et d'optimiser les structures DAG.

Configuration du projet

Pour intégrer Dagon, ajoutez les dépendances nécessaires dans votre fichier build.sbt :

// Pour un environnement JVM
libraryDependencies ++= Seq(
  "com.stripe" %% "dagon-core" % "0.3.3",
  compilerPlugin("org.spire-math" %% "kind-projector" % "0.9.4")
)

// Pour Scala.js ou une approche multiplateformes
libraryDependencies ++= Seq(
  "com.stripe" %%% "dagon-core" % "0.3.3",
  compilerPlugin("org.spire-math" %% "kind-projector" % "0.9.4")
)

Modélisation de l'arbre de syntaxe abstraite

Créons d'abord une structure d'AST pour représenter des expressions mathématiques :

sealed trait MathExpr[T] {
  def unary_-(): MathExpr[T] = Inv(this)
  def +(other: MathExpr[T]): MathExpr[T] = Plus(this, other)
  def -(other: MathExpr[T]): MathExpr[T] = Plus(this, Inv(other))
}

case class Num[T](intValue: Int) extends MathExpr[T]
case class SymbolVar[T](id: String) extends MathExpr[T]
case class Inv[T](expr: MathExpr[T]) extends MathExpr[T]
case class Plus[T](left: MathExpr[T], right: MathExpr[T]) extends MathExpr[T]

object MathExpr {
  def inv[T](e: MathExpr[T]): MathExpr[T] = Inv(e)
  def plus[T](x: MathExpr[T], y: MathExpr[T]): MathExpr[T] = Plus(x, y)
}

Conversion vers le format Dagon

Convertissons notre AST en un type Literal compréhensible par Dagon à l'aide d'une fonction de transformation mémorisée :

import com.stripe.dagon._

val exprToLiteral: FunctionK[MathExpr, Literal[MathExpr, *]] = Memoize.functionK[MathExpr, Literal[MathExpr, *]](
  new Memoize.RecursiveK[MathExpr, Literal[MathExpr, *]] {
    def toFunction[T] = {
      case (n @ Num(_), _)      => Literal.Const(n)
      case (v @ SymbolVar(_), _) => Literal.Const(v)
      case (Inv(inner), rec)    => Literal.Unary(rec(inner), MathExpr.inv[T])
      case (Plus(l, r), rec)    => Literal.Binary(rec(l), rec(r), MathExpr.plus[T])
    }
  }
)

Déclaration des règles de simplification

Définissons des règles de réécriture pour optimiser et réduire nos expressions :

object ReduceNegation extends PartialRule[MathExpr] {
  def applyWhere[T](on: Dag[MathExpr]) = {
    case Inv(Inv(e)) => e
    case Inv(Num(x)) => Num(-x)
  }
}

object ReduceAddition extends PartialRule[MathExpr] {
  def applyWhere[T](on: Dag[MathExpr]) = {
    case Plus(Num(x), Num(y))           => Num(x + y)
    case Plus(Plus(e, Num(x)), Num(y))  => Plus(e, Num(x + y))
    case Plus(Plus(Num(x), e), Num(y))  => Plus(e, Num(x + y))
    case Plus(Num(x), Plus(Num(y), e))  => Plus(Num(x + y), e)
    case Plus(Num(x), Plus(e, Num(y)))  => Plus(Num(x + y), e)
  }
}

val simplificationRules = ReduceNegation.orElse(ReduceAddition)

Exécution de l'optimisation

Appliquons l'ensemble de ces règles sur une expression composée pour obtenir sa forme la plus simple :

val exprA: MathExpr[Unit] = SymbolVar("x") + Num(1)
val exprB: MathExpr[Unit] = exprA + Num(2)
val exprC: MathExpr[Unit] = exprA + Num(5) + SymbolVar("y")
val exprD: MathExpr[Unit] = exprB - exprC

val optimized: MathExpr[Unit] = Dag.applyRule(exprD, exprToLiteral, simplificationRules)

Cas d'usage et intégrations

Dagon excelle dans la simplification d'expressions complexes, comme la transformation de (x + 1) + 2 en x + 3. Dans le domaine du traitement de données et de l'optimisation de compilateurs, il permet de réduire la complexité computationnelle des DAG. Il s'avère également utile pour la génération de tests automatisés via la manipulation et la validation d'AST.

Au sein de l'écosystème Scala, Dagon s'intègre à des frameworks de traitement de données massives. On peut citer Summingbird pour l'optimisation des flux de traitement, Scalding pour la restructuration interne des DAG, ou encore Apache Spark pour affiner la planification et l'ordonnancement des tâches distribuées.