Generalized Multisets for Chemical Programming
Résumé
Gamma is a programming model where computation can be seen as chemical reactions between data represented as molecules floating in a chemical solution. This model can be formalized as associative, commutative, conditional rewritings of multisets where rewrite rules and multisets represent chemical reactions and solutions, respectively. In this article, we generalize the notion of multiset used by Gamma and present applications through various programming examples. First, multisets are generalized to include rewrite rules which become first-class citizen. This extension is formalized by the $\gamma$-calculus, a chemical model that summarizes in a few rules the essence of higher-order chemical programming. By extending the $\gamma$-calculus with constants, operators, types and expressive patterns, we build a higher-order chemical programming language called HOCL. Finally, multisets are further generalized by allowing elements to have infinite and negative multiplicities. Semantics, implementation and applications of this extension are considered. \\ Gamma est un modèle de programmation où les calculs peuvent être vus comme des réactions chimiques entre des données représentées comme des molécules flottant dans une solution chimique. Ce modèle peut être formalisé par la réécriture associative, commutative et conditionnelle de multi-ensembles où les règles de réécriture et les multi-ensembles représentent respectivement les réactions et les solutions chimiques. Dans cet article, nous généralisons la notion de multi-ensemble utilisé dans Gamma et nous présentons des applications à travers divers exemples de programmes. Dans un premier temps, les multi-ensembles sont étendus pour inclure les règles de réécriture qui deviennent donc des molécules comme les autres (ordre supérieur). Cette extension est formalisée par le $\gamma$-calcul, un modèle de calcul chimique qui contient en quelques règles l'essence même des programmes chimiques d'ordre supérieur. Ensuite, en étendant le $\gamma$-calcul avec des constantes, des opérateurs, des types et des motifs plus expressifs, nous construisons un langage de programmation qu'on appelle HOCL. Enfin, les multi-ensembles sont de nouveau étendus en permettant d'exprimer des multiplicités infinies et négatives. Sémantique, implémentation et applications de cette extension sont abordées.
Loading...