化学反应隐喻中的高阶条件多集重写和形式微积分

。这个反应需要γn和γc的表现力：这两个分叉必须是相邻的（γ c的反应条件），并且应该是同时（γn的原子性）以防止死锁。T思维反应把一个吃东西的哲学家变成了两个可用的大多数现有的化学模型都有反应条件和原子化处理多个分子的能力。它们与γcn密切相关，即使它们是第一阶语言。我们这里有两个第一订单模型（Gamma和CHAM）和高阶扩展（多集重写和嗯-微积分。4.2.1伽马射线据我们所知，Gamma [2，3]是第一个化学模型。它由包含碱性非活性分子和外部、条件和n元反应的单个多组反应组成。反应是n次的：应用它们直到没有反应发生。它们是第一阶的：它们不是多集的一部分，不能作为参数接受或作为结果返回。此外，没有嵌套的解决方案。即使子解可以被编码，在伽马中也没有惯性的概念（只有全局终止）。一个标准的伽马程序很容易表达为一个由表示多重集的溶液（惰性是因为没有任何抽象）和一个表示反应的递归γ抽象集合组成的γcn-分子伽马激发了许多扩展（例如，组成算子[12]）和其他化学模型。这些扩展和模型中的大多数仍然与γcn有关。144J. - P. Banâtre等人理论计算机科学电子笔记124（2005）1334.2.2化学抽象机化学抽象机（英语：Chemical Abstract Machine）是一种在没有显式控制的情况下描述并发计算的化学方法。它从伽马射线开始，增加了许多功能，如膜、（子）溶液、惯性和气锁。像Gamma一样，反应是n次和n次重写规则，它们不是多重集的一部分。重写规则左手边的选择模式可以包括常量，这是一种反应条件。例如，在[4]中，对TCCS和CCS计算的操作语义的描述包含一个清除规则（0~），该规则清除等于0. 如果CHAM是高阶的，它将等价于γcn。4.2.3高阶扩展[13]中提出了伽马的第一个高阶扩展。Gamma的定义包括两种不同的术语：程序（重写规则集）和多集。高阶Gamma的主要扩展在于将这两个表达式类别统一为一个配置概念。配置包含一个程序和一个命名倍数列表-ets.它由[Prog，V ar1=多集1，...其中V arn=多集n]。程序Prog是配置的多集（命名为V ari）的重写规则-尿。此模型是高阶模型，因为任何配置都可以通过其程序处理其他配置。这包括反应条件和n次重写规则。然而，反应不是第一类公民，因为他们与多个数据集保持分离。高阶多集机器的微积分被描述为伽马的扩展，其中反应是一次性的和第一类 公 民 。 Ana bSTR a ctiondenotebyλx 。 M1M0 的 cribesareaction 规 则 ：itakesseveraltermsdenotedby atuplex，thetermM1i s action andthetermM0是反应条件。就像γbb一样，嗯-微积分使用名称调用。战略。它需要一个孵化规则来从溶液中提取惰性分子。任何反应都可以在解决方案和抽象中进行。hmm-微积分可以被看作是γcn-微积分的懒惰版本，或者是γbb-微积分的扩展，具有条件和n元反应。4.2.4P系统P-systems [14]是受生物学启发的计算设备。它由分子反应的嵌套膜组成。分子可以在膜之间交叉和移动。一组偏序重写规则与每个膜相关联。这些规则描述了分子膜之间这些特征可以用γcn表示为J. - P. Banâtre等人理论计算机科学电子笔记124（2005）133145⟨ ⟨ ⟩⟩介绍两个新概念。他们没有增加额外的表达能力，但他们对自己很方便和感兴趣。• 第一个需要的概念是普遍量化的条件。直观地，如果存在满足C的解，则可以读取反应条件C... ".另一种条件也可以被考虑：".这个普遍量子化的条件可以用γ c来表示。它相当于测试是否存在满足C的分子。 使用该机制，可以将反应之间的部分顺序指定为优先级。高优先级反应应在低优先级反应之前反应优先级。 为了编码优先级，抽象应该检查没有具有更高优先级的抽象可以响应，即，解决方案中没有满足更高优先级抽象条件的元素。• 第二个概念是多孔溶液。有可能找到可以被γ-抽象操纵的多孔解，即使它们是活动的。由活性分子X1制成的多孔溶液，... X可以由γ x编码。X1，...和XN。γ-抽象的主体是活跃的，但可以通过从其惰性封闭溶液中提取它并将其应用于一场争论。该特征可用于表示P-系统的多孔例如，当对与其环境连续交互的非终止反应性系统进行建模时，此功能也很有用。因此，反应性系统由始终活跃的多孔溶液表示，环境由添加（发送）和去除（接收）溶液中元素的反应表示。4.2.5其他型号我们的比较列表并不详尽，可能已经考虑了其他模型。例如，琳达和她的变体（特别是包豪斯琳达）是接近伽马。根据化学隐喻[11]或[9]中的模型，关于λ-微积分的其他工作已经进行5结论在本文中，我们研究了化学编程范式的基本特征。γ0-微积分在四个句法规则中体现了基本特征（AC多集重写）。术语是可以嵌套（内部解决方案）的多个集合（使用AC应用程序操作符"、"构建）。这个最小的微积分已经被证明是富有表现力的，足以表达λ-微积分和一类非确定性程序。 但它确实如此。146J. - P. Banâtre等人理论计算机科学电子笔记124（2005）133它不能密切反映像Gamma这样的现有化学语言为了实现类似的表达能力，必须考虑两个扩展：反应条件和原子捕获。使用适当的语法糖（递归、con-constants、运算符、模式匹配、多孔解等），γcn-微积分模型接近于大多数现有的化学编程模型。本文提出了几个研究方向。首先，我们应该形式化地证明我们的扩展确实提高了我们的最小化学演算的表达能力。语言表达能力的比较是由Felleisen在[10]中正式研究的。他将"句法糖"和"表达力"的直观概念形式化。如果一个新结构使用另一个结构的表达需要"整个程序的全局重组"，则该新结构被认为是增强的表达性。[5]中对不同协调语言的表达能力进行了正式比较 这项工作比较了琳达的不同变体[6]与不同的伽马模型，以及它们如何在宇宙中发挥作用。可以采用一种非线性方法来正式建立图7中的预排序。我们的工作还可以通过将现有的化学模型正式转化为相应的γ-演算来完成。另一个方向是提出一种基于γcn演算的现实高阶化学编程语言。它将有助于完成前面提到的语法sugar，一个类型系统，以及表达式模式和模块语言。参考文献[1] 我 是 J. P. 和P。 FR AD ETND. Metayer ， Gammaandthechemic lreactionmdel ：Fiteenyearsafter，载于：多集处理，LNSCS2235（2001），第100页。17-44.[2] 我是J. P. A和D。L'eM'etayer，编程的一年，技术报告RR0566，INRIA（1986）。[3] 我是J. P. A和D。M'etayer，Programmingbymultittransformation，Commnicationsof the ACM（CACM）36（1993），pp.98-111.[4] 贝里，G.和G.Boudol，化学抽象机，理论计算机科学96（1992年），p。217-248。[5] 布罗吉，A.和J. - M. Jacquet，《论协调模型的表现性》，载于：P. Ciancarini和A.沃尔夫，编辑，proc. 第三国际Conf. 关于协调模型和语言，LNSCS 1594，1999年，第134-149.[6] Carriero，N.和D. Gelernter，Linda in上下文，ACM通信32（1989），第444-458。[7] Carriero，N.，D. Gelernter和L.Zuck，Bauhaus Linda，in：并发系统的基于对象的模型和，LNSCS924（1994），第66-76。[8] 科 恩 ， D. 和 J.Muylaert-Filho ， 介 绍 高 阶 多 集 编 程 的 微 积 分 ， 载 于 ： 协 调 语 言 和 模 型 ，LNSCS1061，1996年，第124-141.J. - P. Banâtre等人理论计算机科学电子笔记124（2005）133147[9] 迪特里希，P.J. 齐格勒和W.Banzhaf，人工化学（2001年），第225-275。[10] Felleisen先生， 关于编程语言的表达能力，载于：第三届欧洲编程研讨会，ESOP'90 ， LNSCS432，Springer-Verlag，纽约，纽约，1990年，第134-151。[11] 丰塔纳，W.和L.巴斯，《拟合测试的到来：走向生物组织理论》，《数学生物学公报》，第56期（1994）。[12] Hankin，C. D. L. M和AERA N D. Sands，Acalculu usofGamaprograms，in：并行计算的语言和编译器，第五届国际研讨会，LNSCS757（1992），第342- 355。[13] LM和AR，D。我的意思是，我的意思是。 M. S. （A MS），e d itor，Proc. DIMACS并行算法规范研讨会，DIMACS离散数学系列18，1994年[14] P是一个，G。（2000年），第6页。（2000年）。108-143.