Comment coder des types de données algébriques dans un langage semblable à C # ou à Java?

58

Certains types de données algébriques permettent de résoudre facilement certains problèmes. Par exemple, un type de liste peut être exprimé de manière très succincte par:

data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l

Cet exemple particulier est en Haskell, mais il serait similaire dans d'autres langues avec une prise en charge native des types de données algébriques.

Il se trouve qu'il existe une correspondance évidente avec les sous-types de style OO: le type de données devient une classe de base abstraite et chaque constructeur de données devient une sous-classe concrète. Voici un exemple en Scala:

sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)

La seule chose nécessaire au-delà des sous-classes naïves est un moyen de sceller les classes, c'est-à-dire de rendre impossible l'ajout de sous-classes à une hiérarchie.

Comment aborderiez-vous ce problème dans un langage comme C # ou Java? Les deux obstacles que j'ai trouvés en essayant d'utiliser des types de données algébriques en C # étaient les suivants:

  • Je ne pouvais pas comprendre comment s'appelait le type du bas en C # (c'est-à-dire que je ne savais pas quoi mettre dans class Empty : ConsList< ??? >)
  • Je ne pouvais pas trouver un moyen de sceller ConsList afin qu'aucune sous-classe ne puisse être ajoutée à la hiérarchie

Quel serait le moyen le plus idiomatique d'implémenter les types de données algébriques en C # et / ou Java? Ou, si ce n'est pas possible, quel serait le remplacement idiomatique?

Jörg W Mittag
la source
3
C # est le langage POO. Résoudre des problèmes en utilisant la POO. N'essayez pas d'utiliser un autre paradigme.
Euphoric
7
@Euphoric C # est devenu un langage fonctionnel tout à fait utilisable avec C # 3.0. Fonctions de première classe, opérations fonctionnelles communes intégrées, monades.
Mauricio Scheffer
2
@Euphoric: certains domaines sont faciles à modéliser avec des objets et difficiles à modéliser avec des types de données algébriques, d'autres au contraire. Savoir faire les deux vous donne plus de flexibilité dans la modélisation de votre domaine. Et comme je l'ai dit, la mise en correspondance de types de données algébriques avec des concepts OO typiques n'est pas si complexe: le type de données devient une classe de base abstraite (ou une interface ou un trait abstrait), les constructeurs de données deviennent des sous-classes d'implémentation concrètes. Cela vous donne un type de données algébrique ouvert. Les restrictions sur l'héritage vous donnent un type de données algébrique fermé. Le polymorphisme vous donne une distinction de cas.
Jörg W Mittag
3
@Euphorique, paradigme, schmaradigme, qui s'en soucie? Les ADT sont orthogonaux à la programmation fonctionnelle (ou POO ou autre). Encoder une AST de n'importe quelle langue est une douleur sans support ADT décent, et la compilation de cette langue est une douleur sans autre caractéristique agnostique de paradigme, la correspondance de modèle.
SK-logic le

Réponses:

42

Il existe un moyen simple mais difficile de sceller les classes en Java. Vous mettez un constructeur privé dans la classe de base, puis créez des sous-classes de ses classes internes.

public abstract class List<A> {

   // private constructor is uncallable by any sublclasses except inner classes
   private List() {
   }

   public static final class Nil<A> extends List<A> {
   }

   public static final class Cons<A> extends List<A> {
      public final A head;
      public final List<A> tail;

      public Cons(A head, List<A> tail) {
         this.head = head;
         this.tail = tail;
      }
   }
}

Pointage sur un modèle de visiteur pour l'envoi.

Mon projet jADT: Java Algebraic DataTypes génère pour vous tout ce que vous voulez. Https://github.com/JamesIry/jADT

James Iry
la source
2
En quelque sorte, je ne suis pas surpris de voir votre nom apparaître ici! Merci, je ne connaissais pas cet idiome.
Jörg W Mittag
4
Quand vous avez dit «chaud», j'étais préparé à quelque chose de bien pire ;-) Java peut parfois être très pénalisant avec warmplate.
Joachim Sauer le
mais cela ne compose pas: vous n'avez aucun moyen de spécialiser le type A sans avoir à l'affirmer à travers un casting (je pense)
nicolas
Cela semble malheureusement incapable de représenter certains types de somme plus complexes, par exemple Either. Voir ma question
Zoey Hewll
20

Vous pouvez y parvenir en utilisant le modèle de visiteur , qui complétera la correspondance de modèle. Par exemple

data List a = Nil | Cons { value :: a, sublist :: List a }

peut être écrit en Java comme

interface List<T> {
    public <R> R accept(Visitor<T,R> visitor);

    public static interface Visitor<T,R> {
        public R visitNil();
        public R visitCons(T value, List<T> sublist);
    }
}

final class Nil<T> implements List<T> {
    public Nil() { }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitNil();
    }
}
final class Cons<T> implements List<T> {
    public final T value;
    public final List<T> sublist;

    public Cons(T value, List<T> sublist) {
        this.value = value;
        this.sublist = sublist;
    }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitCons(value, sublist);
    }
}

Le scellement est réalisé par la Visitorclasse. Chacune de ses méthodes explique comment déconstruire l'une des sous-classes. Vous pouvez ajouter plusieurs sous - classes, mais il faudrait mettre en œuvre acceptet en appelant une des visit...méthodes, il devrait soit se comporter comme Consou comme Nil.

Petr Pudlák
la source
13

Si vous abusez des paramètres nommés C # (introduits dans C # 4.0), vous pouvez créer des types de données algébriques faciles à faire correspondre:

Either<string, string> e = MonthName(2);

// Match with no return value.
e.Match
(
    Left: err => { Console.WriteLine("Could not convert month: {0}", err); },
    Right: name => { Console.WriteLine("The month is {0}", name); }
);

// Match with a return value.
string monthName =
    e.Match
    (
        Left: err => null,
        Right: name => name
    );
Console.WriteLine("monthName: {0}", monthName);

Voici l'implémentation de la Eitherclasse:

public abstract class Either<L, R>
{
    // Subclass implementation calls the appropriate continuation.
    public abstract T Match<T>(Func<L, T> Left, Func<R, T> Right);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public void Match(Action<L> Left, Action<R> Right)
    {
        this.Match<int>(
            Left: x => { Left(x); return 0; },
            Right: x => { Right(x); return 0; }
        );
    }
}

public class Left<L, R> : Either<L, R>
{
    L Value {get; set;}

    public Left(L Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Left(Value);
    }
}

public class Right<L, R> : Either<L, R>
{
    R Value { get; set; }

    public Right(R Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Right(Value);
    }
}
Joey Adams
la source
J'ai déjà vu une version Java de cette technique, mais les paramètres lambdas et nommés la rendent tellement lisible. +1!
Doval
1
Je pense que le problème ici est que Right n’est pas générique pour ce type d’erreur. Quelque chose comme class Right<R> : Either<Bot,R>:, où Soit est remplacé par une interface avec des paramètres de type covariant (sortant), et Bot est le type inférieur (sous-type de tous les autres types, à l'opposé de Object). Je ne pense pas que C # a un type de fond.
croyd
5

En C #, vous ne pouvez pas avoir ce Emptytype car, en raison de la réification, les types de base sont différents pour les différents types de membres. Vous pouvez seulement avoir Empty<T>; pas utile.

En Java, vous pouvez avoir à Empty : ConsListcause de l'effacement de type, mais je ne suis pas sûr que le vérificateur de type ne crie pas quelque part.

Cependant, étant donné que les deux langues ont null, vous pouvez penser à tous leurs types de référence comme étant "Quoi | Null". Donc, vous utiliseriez simplement le nullcomme "Vide" pour éviter d'avoir à spécifier ce qu'il dérive.

Jan Hudec
la source
Le problème, nullc’est qu’il est trop général: il représente l’absence de tout , c’est-à-dire le vide en général, mais je veux représenter l’absence d’éléments de liste, c’est-à-dire une liste vide en particulier. Une liste vide et un arbre vide doivent avoir des types distincts. De plus, la liste vide doit être une valeur réelle, car elle a toujours son propre comportement et doit donc avoir ses propres méthodes. Pour construire la liste [1, 2, 3], je veux dire Empty.prepend(3).prepend(2).prepend(1)(ou dans un langage avec des opérateurs à droite associative 1 :: 2 :: 3 :: Empty), mais je ne peux pas dire null.prepend ….
Jörg W Mittag
@ JörgWMittag: Les valeurs nulles ont des types distincts. Vous pouvez également créer facilement une constante typée avec la valeur null à cette fin. Mais il est vrai que vous ne pouvez pas appeler de méthodes dessus. Votre approche avec les méthodes ne fonctionne pas sans Empty de toute façon spécifique au type d'élément.
Jan Hudec
certaines méthodes d'extension astucieuses peuvent simuler des appels de "méthode" sur des valeurs NULL (bien sûr, elles sont vraiment statiques)
jk.
Vous pouvez avoir un Emptyet un Empty<>et l' abus des opérateurs de conversion implicites pour permettre une simulation assez pratique, si vous voulez. Vous utilisez essentiellement Emptydu code, mais toutes les signatures de type, etc., n'utilisent que les variantes génériques.
Eamon Nerbonne
3

La seule chose nécessaire au-delà des sous-classes naïves est un moyen de sceller les classes, c'est-à-dire de rendre impossible l'ajout de sous-classes à une hiérarchie.

En Java, vous ne pouvez pas. Mais vous pouvez déclarer la classe de base comme étant un paquet privé, ce qui signifie que toutes les sous-classes directes doivent appartenir au même paquet que la classe de base. Si vous déclarez ensuite les sous-classes en tant que final, vous ne pourrez plus les sous-classer.

Je ne sais pas si cela réglerait votre problème réel cependant ...

Stephen C
la source
Je n'ai pas vraiment de problème, ou j'aurais posté ceci sur StackOverflow, pas ici :-) Une propriété importante des types de données algébriques est qu'ils peuvent être fermés , ce qui signifie que le nombre de cas est corrigé: dans cet exemple , une liste est vide ou non. Si je peux assurer de manière statique que c'est bien le cas, je peux alors effectuer des conversions dynamiques ou des intanceofvérifications dynamiques "pseudo-type-safe" (c'est-à-dire: je sais que c'est sûr, même si le compilateur ne le fait pas), simplement en m'assurant que vérifiez ces deux cas. Si, toutefois, quelqu'un d'autre ajoute une nouvelle sous-classe, je peux obtenir des erreurs d'exécution auxquelles je ne m'attendais pas.
Jörg W Mittag Le
@ JörgWMittag - Eh bien, Java ne le supporte manifestement pas ... dans le sens où vous semblez manquer. Bien sûr, vous pouvez faire diverses choses pour bloquer les sous-types non désirés au moment de l'exécution, mais vous obtenez alors des "erreurs d'exécution inattendues".
Stephen C
3

Le type de données ConsList<A>peut être représenté sous forme d'interface. L'interface expose une seule deconstructméthode qui vous permet de "déconstruire" une valeur de ce type, c'est-à-dire de gérer chacun des constructeurs possibles. Les appels à une deconstructméthode sont analogues à une case offorme en Haskell ou ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

La deconstructméthode prend une fonction "callback" pour chaque constructeur de l'ADT. Dans notre cas, il faut une fonction pour le cas de liste vide et une autre pour le cas "cellule".

Chaque fonction de rappel accepte comme arguments les valeurs acceptées par le constructeur. Donc, la casse "liste vide" ne prend pas d'argument, mais la casse "contre" prend deux arguments: la tête et la queue de la liste.

Nous pouvons coder ces "arguments multiples" en utilisant des Tupleclasses ou en utilisant currying. Dans cet exemple, j'ai choisi d'utiliser une Pairclasse simple .

L'interface est implémentée une fois pour chaque constructeur. Premièrement, nous avons l'implémentation pour la "liste vide". L' deconstructimplémentation appelle simplement la emptyCasefonction de rappel.

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Ensuite, nous implémentons le cas "cons cell" de manière similaire. Cette fois, la classe a des propriétés: la tête et la queue de la liste non vide. Dans l' deconstructimplémentation, ces propriétés sont transmises à la consCasefonction de rappel.

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Voici un exemple d'utilisation de ce codage ADTs: on peut écrire une reducefonction qui est le facteur usuel sur les listes.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

Ceci est analogue à cette implémentation dans Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2
jameshfisher
la source
Approche intéressante, très agréable! Je peux voir le lien entre F # Active Patterns et Scala Extractors (et il existe probablement un lien vers Haskell Views également, ce que je ne connais malheureusement pas). Je n'avais pas pensé à transférer la responsabilité de la correspondance de modèle sur les constructeurs de données dans l'instance ADT elle-même.
Jörg W Mittag
2

La seule chose nécessaire au-delà des sous-classes naïves est un moyen de sceller les classes, c'est-à-dire de rendre impossible l'ajout de sous-classes à une hiérarchie.

Comment aborderiez-vous ce problème dans un langage comme C # ou Java?

Il n'y a pas de bonne façon de faire cela, mais si vous voulez vivre avec un bidouillage hideux, vous pouvez ajouter une vérification de type explicite au constructeur de la classe de base abstraite. En Java, ce serait quelque chose comme

protected ConsList() {
    Class<?> clazz = getClass();
    if (clazz != Empty.class && clazz != ConsCell.class) throw new Exception();
}

En C #, c'est plus compliqué à cause des génériques réifiés - l'approche la plus simple pourrait être de convertir le type en chaîne et de le modifier.

Notez qu'en Java, même ce mécanisme peut théoriquement être contourné par quelqu'un qui le souhaite vraiment via le modèle de sérialisation ou sun.misc.Unsafe.

Peter Taylor
la source
1
Ce ne serait pas plus compliqué en C #:Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();
svick
@svick, bien observé. Je ne pensais pas que le type de base serait paramétré.
Peter Taylor
Brillant! Je suppose que cela suffit pour effectuer une "vérification manuelle du type statique". Je cherche plus à éliminer les erreurs de programmation honnêtes que les intentions malveillantes.
Jörg W Mittag