Qu'est-ce qu'une" algèbre multisortée", et comment l'utiliser pour résoudre de"vrais problèmes"?

apparemment, Alexander Stepanov a déclaré ce qui suit dans un interview :

"je trouve de la programmation orientée objet [de la programmation orientée objet] défauts techniques. Il tente de décomposer le monde en termes d'interfaces qui varient d'un seul type. pour faire face aux problèmes réels, vous avez besoin d'algèbres multi - portées-des familles d'interfaces qui couvrent plusieurs types. " [C'est nous qui soulignons.]

ignorant un instant sa déclaration concernant L'OOP, que sont les "algèbres multisortées", au-delà de sa définition laconique, et pouvez-vous donner un exemple pratique de la façon dont elles sont utilisées (dans la langue de votre choix)?

30
demandé sur Peter O. 2010-09-20 20:28:56

3 réponses

je crois qu'il parlait de programmation générique (il a inventé le terme ), que ce soit dans le contexte de cette discussion sur la STL, ou "dans l'ensemble", au sens de:

  1. programmation par rapport à une sorte d'interface qui décrit quelque chose qui pourrait s'adapter tout (et, espérons-le, plusieurs) types (donc multi-triés),...
  2. ... fourni ils ont certaines propriétés , souvent quelque chose sur la nature de certaines opérations sur des éléments de ce type (d'où algèbres).

(1), vous devez disposer d'un moyen de spécifier un programme qui prend un type comme un paramètre , c'est à dire polymorphisme , et (2), vous avez besoin d'une façon de dire que vous aussi voulez ce type à transporter opérations (et, à condition que vous puissiez les exprimer propriétés ). En effet, vous paramétrez votre programme par la structure 1519180920" des données qu'il manipule. Le paradigme est appelé dans certains endroits délimitée polymorphisme, type de données-programmation générique, ... qui reflète que les langues ont des notions différentes de la façon de mettre en œuvre cette idée - d'où la "sorte de" en italique ci-dessus.

  • pour C++, il semble que-pour Stepanov au moins - cela correspond à templates (bien que les idées sur la façon de faire ce mieux sont encore en évolution ).
  • pour les langues OO (Java Générique, C#), les contraintes sur les paramètres de type sont généralement exprimées en utilisant des limites de sous-type ('bounded wildcards')...).
  • pour Haskell ou Scala, vous avez (respectivement, et de manière similaire) les classes de type ou implicites .
  • la famille des langues ML préfère utiliser modules .
  • notez qu'un certain nombre de proof assistants (qui peut exprimer 'honest-to-god' propriétés comme types) ont développé une saveur de classes de type: Isabelle, Coq, Matita sont de tels exemples

notez que Stepanov vient de co-écrire un livre entier donnant un développement exhaustif d'une bibliothèque qui incarne exactement ce qu'il veut dire (je pense). Donc si vous voulez des exemples en C++ , c'est certainement là que vous devriez chercher. Il convient également de noter qu'il s'agit d'un conseil beaucoup plus évolué que celui, désormais courant, du codage par rapport à une interface, plutôt que d'un objet .

par 'exemple pratique", je ne sais pas si vous entendez par "comment" ou " pourquoi fait-on l'utilise. Pour donner une réponse caricaturalement rapide au "pourquoi", la généricité est agréable parce que, un peu comme le polymorphisme courant-de-l'usine, il vous permet code de réutilisation . Mais, plus important encore:

  1. code polymorphe qui doit fonctionner avec chaque un seul type souvent ne peut rien faire d'intéressant, alors que d'avoir une interface contrainte à jouer Avec permet d'écrire des programmes plus riches

  2. en spécifiant comment cette interface s'adapte à certaines de vos données, vous avez un moyen de type sûr pour sélectionner seulement les éléments qui conviennent à vos besoins. Par exemple, vous savez probablement que l'opérateur reduction (l'opérateur reduce de Python& Hadoop, fold d'un groupe de langages fonctionnels) est parallélisable seulement si l'ordre dans lequel vous appliquez votre fonction de réduction n'a pas d'importance. ( + , x , min , and le travail, mais la différence établie ne le fait pas). Si vous avez une notion de " type équipé d'un associatif opération", vous savez que vous serez en mesure d'appeler une diminution parallèle.

  3. tous les frais généraux engagés par genericity se produisent au moment de la compilation. Par exemple, les modèles sont légendaire rapide

si vous avez vu Java Générique, regardez say, l'interface générique Comparable . Il définit juste une opération, mais le contrat qu'il fait, bien que de base, est beaucoup de saveur algébrique. Je cite:

pour les personnes mathématiquement inclinées, la relation qui définit l'ordre naturel sur une Classe C donnée est: 

  {(x, y) such that x.compareTo((Object)y) <= 0}.

le quotient pour cet ordre total est: 

  {(x, y) such that x.compareTo((Object)y) == 0}.

il suit immédiatement après le contrat de compareTo que le quotient est une relation d'équivalence sur C, > et que l'ordre naturel est une commande totale sur C.

maintenant, je peux écrire une méthode qui sélectionne le minimum, une fois, et l'utiliser pour tout type qui correspond à cette interface : 

 public static <T extends Comparable<T>> T min (T x, T y) {
   if (x.compare(y) < 0) x; else y;
 }

naturellement, puisque la façon dont les constructions programmatives mettent en œuvre cette notion varie énormément, ce que vous obtiendrez en termes de la convivialité et l'expressivité varieront également. Peut-être ne devriez - vous pas juger la programmation de type data-generic uniquement par des langages OO comme C++ ou Java-mais j'ai déjà trop écrit pour commencer avec le module ascription ou la génération automatique d'instance des classes de type.

23
répondu huitseeker 2017-05-23 12:25:49

je suis en retard, mais peut-être que ça vous sera utile. L'utilisateur huitseeker a écrit une excellente réponse du point de vue de la conception du logiciel. Je veux répondre à votre question du point de vue des mathématiques. Avant de plonger dans le monde du logiciel Alex Stepanov a été un mathématicien et a étudié abstract et universel algèbre. Et il a souvent essayé d'apporter des bases mathématiques rigoureuses dans le monde du logiciel et la conception d'algorithme. Dans ses livres des mathématiques à la programmation générique et éléments de programmation il prône cette pratique de conception. Ses idées sur le mélange des concepts de structures algébriques et la conception de logiciels ont été réalisés dans la notion de generic programming . Et maintenant, parlons de sa citation:

pour faire face aux problèmes réels, vous avez besoin de plusieurs algèbres-familles d'interfaces qui s'étendent plusieurs types de

à mon avis, il y a deux concepts principaux qu'il a voulu mentionner ici: l'idée de type de données abstraites ( ADT ) et structure algébrique . Première concept: ADT . ADT - est un modèle mathématique pour un type de données où un type de données est défini uniquement par sa sémantique. Stepanov a opposé l'idée de ADT à l'idée de object dans le sens de la programmation orientée objet. Objects contains data and state while ADTs - not . ADT - est un behavioural abstraction , un operation cluster qui décrit l'interaction avec les données. L'abstraction comportementale est entièrement décrite au moyen de la spécification algébrique du type de données abstraites. Vous pouvez lire plus à ce sujet dans l'original Liskov et Zilles papier, aussi je vous recommande un papier Programmation Orientée Objet Versus types de données abstraites par William R. Cook .

( Discalimer : vous pouvez passer ce paragraphe, parce qu'il est plus "mathématique et pas si important" ) d'abord, je veux clarifier une certaine terminologie. Quand je parle du algebraic structure c'est la même chose que l'algèbre. Le mot algebra est souvent également utilisé pour une structure algébrique. Pour être plus précis quand nous parlons de structures algébriques (algèbres) nous voulons généralement dire algèbre sur une théorie algébrique . Il existe un concept de la variété d'algèbres , parce qu'il ya plusieurs notions d'une structure algébrique sur un objet d'une certaine catégorie. Par définition, une algebraic theory (algèbre sur elle) consiste en une spécification des opérations et des lois que ces opérations doivent satisfaire: il s'agit d'une définition de travail de la structure algébrique que nous allons utiliser, et cette définition ,je pense, Stepanov implicitement mentionné dans la citation.

second concept que Stepanov a voulu mentionner est le plus intéressant propriété des ADTs: ils peuvent être formellement modélisés directement comme many-sorted algebraic structures . Parlons-en de façon plus formelle. Une structure algébrique-est un carrier set avec une ou plusieurs opérations de la nageoire définie sur elle. Ces opérations sont généralement définis non plus un jeu, mais sur plusieurs. E. g. définissons et algèbre quels modèles de concaténation de chaîne. Cette algèbre sera définie non pas sur un ensemble de cordes mais sur deux ensembles: cordes S et nombres naturels N , parce que nous pouvons définir une opération qui peut concaténer une corde avec lui-même un nombre fini de fois. Ainsi, cette opération prendra deux opérandes, qui appartient à différents ensembles sous-jacents (carrier): S et N . Ensemble qui définit ces différents opérandes (leurs types) en algèbre appelé un ensemble de sorts . Sort est un analogue algébrique du type. Algèbre avec plusieurs sortes appelée une algèbre multi-triée. En algèbre universelle, un signature énumère les opérations qui caractérisent une structure algébrique. Une structure algébrique triée peut avoir un nombre arbitraire de domaines. Les tris sont partie de la signature, et ils jouent le rôle de noms pour les différents domaines. Plusieurs signatures triées prescrivent également sur qui trie les fonctions et les relations d'une structure algébrique triée sont définies. Pour une variété d'algèbres triées une signature est un ensemble, dont les éléments sont appelés opérations, à chacune desquelles est attribué un nombre cardinal (0,1,2,...) appelé son arité. Une signature d'algèbre multi-triée peut être définie comme Σ = (S,OP,A) , où S - ensemble de noms de tri (types), OP - ensemble de noms d'opération et A - Aries comme avant, sauf que maintenant une arité est une liste ( séquence ou plus généralement monoïde libre ) d'entrées différentes d'un simple nombre naturel (la longueur de la liste) et d'une sortie. Maintenant, nous pouvons créer une spécification algébrique d'un type de données abstraites ADT comme un triple: 

ADT = (N, Σ, E)

, où N - nom du type de données abstraites, Σ = (S,OP,A) - signature de la structure algébrique multi-triée, E = {e1, e2, …,en} - est une collection finie d'égalités dans le signature. Comme vous pouvez le voir maintenant, nous avons une description mathématique rigoureuse de L'ADT. En mathématiques, de nombreuses structures algébriques triées sont souvent utilisées comme un outil pratique, même lorsqu'elles pourraient être évitées avec un peu d'effort. Les structures algébriques triées sont rarement définies d'une manière rigoureuse, car il est facile d'effectuer la généralisation explicitement. C'est pourquoi la théorie des algèbres triées peut être appliquée avec succès à la conception de logiciels.

Donc, Alex Stepanov a voulu dire qu'il préfère ADTs et la programmation générique à OOP, parce que nous pouvons ainsi créer des programmes avec des bases mathématiques/algébriques rigoureuses. J'apprécie ses efforts beaucoup. Nous savons tous que la conception algébrique est toujours correcte, rigoureuse, belle, simple et nous donne de meilleures abstractions.

9
répondu Oleksandr Karaberov 2015-09-26 21:48:28

non pas que je sois un expert avec la théorie de l'un de ceux-ci, mais nous allons jeter un coup d'oeil à la citation afin que je puisse essayer de donner ma compréhension pratique pour ajouter à la discussion.

pour faire face aux problèmes réels, vous avez besoin de plusieurs algèbres - familles d'interfaces qui couvrent plusieurs types.

D'après mes lectures, je pense que familles d'interfaces qui couvrent plusieurs types sonne beaucoup comme classes de type de Haskell, qui est similaire aux concepts de C++. Prenez une classe de type comme Foldable il est en fait un type d'interface paramétrée, c'est à dire. une famille d'interfaces qui couvrent plusieurs types. Donc, à propos de votre question sur la façon de résoudre les problèmes avec les algèbres multisorties, la programmation générique est tout au sujet de cela si vous le prenez à des classes de type ou des concepts.

0
répondu meguli 2018-05-01 08:45:56