经济模拟器函数式编程的静态方法

经济模拟器函数式编程的静态方法安托万·卡兹契奇引用此版本：安托万·卡兹契奇。经济模拟器函数式编程的静态方法。建模和仿真。巴黎-北巴黎第十三大学，2019年。法语。NNT：2019PA131045。电话：03156294HAL ID：电话：03156294https://theses.hal.science/tel-03156294提交日期：2021年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire我是一个很好的朋友。我的意思是，我的意思是。圣ATI CME THOD S为T他 fU nctIO nALP罗杰阿米NG的Econo和他的IMULAtorsANTOI NE KA SZCZY CCH RI toPHE foU qUE rÉ，DRECTEU RPIE RREBOUDE S，ENCAD RA NT我的rcoPEDI cI nI，rAPPOrtEU rDA nIELE vA rA ccA，rAPPO rtEU r sYL vIEBOLDO，考试nA tri cE2019年12月 18日实验室RA到IRE我的意思是，我的意思是。i材料表论文1摘要摘要三论文五导论我使用Monades9进行模拟1Monades函数式编程入门111.a函数式编程导论111.b模拟可变效应：单子2具有谓词的单子状态2.a程序对谓词的尊重2.b通过抽象类型322.c使用抽象类型342.d关于函数的353单子的优化393.a内存大小错误简介393.b单子和递归463.c单子状态和写入器的483.d现有解决方案523.eMonad58的特殊递归函数3.f非受控递归的一元混凝土603.g使用REPL 67的一元混凝土3.h有关使用环境3.i结论694实现：一个经济模拟器4.a经济模拟器Jamel 71的研究4.b功能模拟器中使用的单子734.c单子库734.d提升难度744.e可变数据结构算法764.f单子混凝土的存在77ii4.g功能和单子与全局易变性77材料表二演员模拟795演员、Akka和消息815.a一个竞争的模式：Akka82演员5.b简化演员语言的语法5.c通过小步价值进行885.d正常形式和值905.e分型、进展、保存915.f消息类型976实现：仿真103论文105的结论参考书目107附件111普通单子的基本OCaml定义111A.1单子状态111A.2单子阅读器111A.3单子写入器111A.4单子选项112A.5单子列表112A.6单子继续112B 证据113B.1单子规则的两种书写方式的等价性证明B.2证明WriterM是每个单子的C 性能测试119C.1测试程序119C.2119试验机的特点C.3测试脚本120C.4不带终结递归的125C.5终结递归列表大小126C.6具有左递归的单子状态126C.7具有右递归的单子状态128C.8具有m_while129的单子状态C.9具有具体单子的单子状态129C.10 带左递归的MonadeWriter130C.11 带右递归的MonadeWriter130C.12 带m_while131的单子写入器C.13 使用具体单子的单子写入器132C.14 带左递归的状态写入器单子132C.15 具有右递归的状态写入器单子133C.16 带m_while135的单元状态写入器C.17 具有具体单子的单子状态写入器136D章单子的137D.1一元值的递归...........................................................................................................................................137iii图表、表格、代码和资源表1391→论文摘要论文的第一部分是关于函数式程序中的副作用及其在单子上的模拟。这些建议具有广泛的范围：无论方案的主题如何，它们都可以适用。然而，他们的灵感来自于一个储蓄模拟器编程环境这种类型的程序大量使用副作用和功能重复。论文中的建议与具有这些特征的程序更相关像许多它们不适合于执行"快速完成"的程序，而是执行一个关键部分已得到保护且不再需要关注的程序第1章介绍了函数式编程，以及反映运行时内存消耗的执行方案它引入了单子和单子变换器，作为在不可变上下文中自动模拟可变方面的机制第2章讨论了副作用的管理：用状态单子模拟可变本章首先定义了谓词合规性的确切含义，特别是通过众所周知的抽象类型的解决接下来，我们观察到谓词在涉及函数类型（A）时更有表现力。（A）加上-而不仅仅是A。状态单子为在程序中实现谓词提供了足够的支持，因为它通过函数的组合来表达可变变量。在IF-仿真中，带谓词的抽象状态单子允许表达辅助但无处不在的机制，如伪随机数的生成或银行账户的管理。这是两个概念，副作用模拟第3章讨论了程序安全的另一个方面：内存消耗。它受到运行程序的计算机的物理组件的限制如果本章介绍了函数式编程中遇到的两种类型L’erreur 补救办法是然而，它在单子的存在下更难应用，单子用程序员控制较少的绑定应用程序替换标准应用程序此外，函数组合必须存储，这可能会导致Out_Of_Memory错误。然后，本章介绍了现有的解决方案，其中最好的解决方案为每个单子定义了一个专门的递归函数。现有的解决方案不能解决递归不受"控制"的情况，即在此上下文中，解决方案可能会导致我们提出了"一元具体"原理作为解决方案这是然后，可以在不暂停操作的情况下执行不受控制的递归。上下文负责本章最后介绍了读取评估打印循环（REPL）的背景它包括提取（读取）每个绑定之间的一元值。这是现有解决方案的一个问题，因为它需要2材料表每次都要重新计算暂停。因此，一元混凝土是足够的，因为第4章收集了编写一个小型功能模拟器所产生的一组观察结果。观察涉及从前面的章节中创建的单子库，提升机制的困难，在孤立和关键位置使用可变性。本章最后试图比较可变变量编程和不可变变量编程。论文的第二部分和第五章的主题是参与者系统及其类型，这是一个旨在表达并发程序的系统。由于代理和参与者之间的相似性，它们被认为是基于代理的模拟器。我们介绍了Akka，一个实现这个模型的库，我们看到在它的基本版本中，它没有对传输的消息类型应用检查，这可能会导致程序进入一个意想不到的状态。然后，我们用一种简化的语言来表达参与者，我们向他们展示了如何添加简单的类型（就像简单类型化的lambda计算一样）。在本章的最后，我们提供了一些例子来说明为什么这种类型需要扩展以恢复第二部分以第6章结束，该章报告了在实现基于参与者模型的模拟发射平台方面所做的工作。该平台允许您同时运行多个模拟，可能在不同的机器上运行，并具有一个客户端界面，可在运行时显示结果。关键词— 功能性— 单子— 模拟器— 记忆3→摘要博士论文的第一部分涉及函数式程序中的副作用及其在单子上的模拟所提出的解决方案有一个总体目标：无论方案的主题如何，它们都是有用的。然而，他们受到了经济模拟器编程环境的启发。尽管如此，program还是大量使用了副作用和函数调用的重复。所提出的解决方案对于具有这些特征的程序更有用。像许多其他人一样，他们被要求严格组织该计划。他们不打算建立一个"快速和良好的"程序，而是一个关键部分已经安全，不需要进一步关注的程序。第1章介绍了函数式编程，以及表示内存消耗的执行方案它引入了单子和单子变换器，作为在不变的上下文中自动模拟可变方面的机制。第二章副作用的地址处理：状态单子对可变变量的模拟，谓词对其值的框架化。本章首先定义了遵守谓词的确切含义，特别是通过抽象类型的众所周知的解决方案。然后，我们观察到，当谓词涉及函数类型（A）而不是简单的A时，它更有表现力。单子状态提供了一个足够的结构来在程序中实现谓词，因为它模拟了一个可变变量。在经济模拟器中，带有谓词的抽象单子状态可以表达类似但相同的机制，如伪随机生成或银行账户处理。这是两个概念，副作用的模拟和对谓词的尊重，这是由抽象的单子状态解决的。第3章讨论了程序安全性的另一个方面：内存消耗。它与计算机的物理组件有关。如果程序的执行需要太多的内存空间，则程序将被停止。本章介绍了函数式编程中两种类型的内存错误：Stack_Overflow和Out_Of_Memory。Stack_Overflow错误由递归函数引起解决方案是尾部调用优化。然而，在存在单子的情况下，它更难应用，单子将标准的应用替换为应用绑定，而操作程序对单子的控制更弱。最具代表性的例子是单子状态，它创建了未通过尾调用优化的函数的组合。此外，必须存储函数的组合，这可能会导致Out_Of_Memory错误。然后，这一章介绍了现有的解决方案，最好的一个定义了一个递归函数专门为每个单子。然而，没有一个解解决了递归"不受控制"的情况，即当程序员只是给出一个要重复的函数时在这种情况下，现有的解决方案存在内存不足的风险，因为它们将函数存储在挂起状态。我们提出了我们的解决方案："一元混凝土"。其思想是创建一个所有信息都已知的内部上下文，例如状态的辅助变量。然后可以在没有挂起操作的情况下执行递归不受控制的递归上下文负责等待信息。本章最后介绍了Read Eval Print Loop（REPL）的上下文。它包括提取（读取）每个绑定之间的一元值。这给现有的解决方案带来了一个问题，因为每一个解决方案都必须重新考虑暂停。一元混凝土本身就足够了，因为它们不使用悬浮液。第四章收集了一组观察结果，这些观察结果来自于编写一个小型函数经济模拟器。它们涉及前一章中实现的单子库、提升的问题、muta-的使用4材料表在孤立和时间关键的地方。本章最后试图将编程与可变性和不变性进行比较。博士学位的第二部分及其第5章涉及演员系统及其类型。这些是表示快速并发程序的系统时间。通过代理和参与者之间的相似性，他们被设想为实现基于代理的模拟我们介绍了Akka，一个现有的演员模型库，我们观察到，在其基本版本中，它不对演员之间的通信消息进行键入。这可能会导致系统进入计划外状态。然后，我们用一种简单的语言表达了行动者系统，并演示了如何将简单类型添加到简单类型的lambda演算中。本章最后介绍了一些示例，说明为什么必须增强此类型以恢复原始表现力。第二部分以第6章结束，第6章介绍了基于演员模型的模拟发射porgram的实现工作该程序允许在不同的计算机上运行几个并行模拟，并提供一个实时显示结果的GUI。关键词— 功能性— 单子— 模拟器— 内存5论文引言这项工作的出发点是通过函数式编程编写代理经济模拟器。应用环境更广泛，涵盖了使用mo- nades的函数式代理模拟器是使一组代理玩游戏并与之交互的程序他们的目标是例如，在经济学中，它们被用来表示货币在每个时期之间不会消失的系统。让我们引用Pascal Seppecher的话，他是Jamel储蓄模拟器的创建者生产的货币理论，因为它致力于探索货币在经济体系中的涨落机制，是基于主体之间相互作用的宏观经济学方法的一个重要支点。然而，这一理论它导致的模型不能令人满意地反映利润和利息等基本类别多智能体建模技术克服了我们描述了一个真正动态的货币经济模型的构建通过模拟，我们观察到我们从编程的角度来讨论代理经济模拟器。Pascal Seppecher使用Java语言编写Jamel，其范例是面向对象编程。它类别是用来建立属于它的物件。例如，对于储蓄模拟器请注意，引文强调了对"存量和流量的一致性"的尊重这对象编程允许通过对象对其属性的控制来强制执行我们还可以使用"断言"方法，该方法包括定期调用一个过程，该过程检查是否符合属性，并在出现故障时停止程序。我们采取了另一个立场：在编写经济体代理模拟器时遵循功能范式。这种范式有其自身的特点：— 数据结构是不可变的，因此任何过程都不能改变另一个过程使用这增强了对正确性的信心：我们知道我们的当前数据不会被调用任何函数所破坏— 基本结构是函数，它是"第一类元素"。操作函数允许您操作源代码片段材料表6通过遵循函数式范式，我们希望编写节省模拟器没有太大的困难，并更容易地控制库存和流量的一致性 在这个意义上，我们在人工经济学会议上发表了《货币经济学模拟：存量-流量一致不变性，单子式》（BKP15）。编写模拟器的功能范式的主要特点C’est par exemple utile pour implémenter un在函数中，函数的唯一效果是它的返回值，因此必须使用该值其结果是函数的输入和输出值的混乱。在这种情况下，我们使用一个单子来清理输入/输出，使其中一些是隐式的，并自动化它们的传输。这种机制被称为单子状态。我们利用单子状态的集中化特征，将库存和流量的一致性验证与之联系起来（第2章）。储蓄模拟器一个时期本身由阶段组成。例如，在工资阶段，每个家庭都是其银行账户转账的接收者。因此，模拟器的程序包含大量的小动作，这些小动作很容易超过一百万个。请注意，我们还可以"校准"模拟器，计算机是为重复而生的，尽管我们总是对它们提出更多的要求，但模拟器程序在最坏的情况下，它需要很长的时间来运行，这取决于代理的数量然而，尽管单子被定义为"用户"结构，但它们是特殊的，因为它们存在于程序的每个阶段，它们对程序的执行有很大的影响在语言中使用单子意味着通过添加新的控制结构来修改原始语言Oleg Kiselyov和Hiromi Ishii [KI15]的Freer Monads，More Extensible Effects中的运行机制证明了这一点，该机制包括在程序本身单子不仅对执行和所表示的值有很大的影响原因是所有单子共享一个公共接口，因此很容易使代码多态，即适用于不同的这两个特征都具有隐藏在时间和空间上的性能的效果，这可能被证明是有问题的，特别是在储蓄模拟器的情况下，其中存在大量的小动作。这就是为什么我们在第三章中专门讨论时间和空间问题，因为它们对于模拟器程序的实际使用是必不可少的。主要问题是Stack Overflow，其中执行了太多的嵌套函数调用。第二个问题出现在第一个问题的现有解决方案中，其中堆栈空间已经被工作内存空间交换，也不是无限的（Out_Of_Memory错误）。已经对几个单子进行了运行时测试，参见附录C。 我们推荐一个现有的解决方案，但在OCaml单子库中并不广泛使用，它包括定义优化的重复函数，重复类型为'a->（'a monad）的函数。我们观察到，这些函数需要递归控制，但情况并非总是如此。此外，根据所使用的单子，它们不允许因此，我们提出了一种新的结构：单子具体后者旨在通过将暂停应用于整个块来避免累积功能暂停，在该块内操作是有效的。一元混凝土是本文的主要贡献。最后，在第4章中，我们收集了关于用OCaml函数式语言实现一个玩具经济模拟器的信息在本文档的第一部分中，我们将重点介绍如何在第二部分中，我们将讨论程序的范式。材料表7竞争对手。这包括将程序转换为一组程序，每个程序在自己的机器上运行，并通过网络与其他程序通信当可以并行执行某些操作时，这可以提高执行速度这也可能是不必要的，因为模拟的大小太大，无法容纳在单个机器的工作存储器中在这种范例中编程的困难是众所周知的。在某种意义上，我们通过使用行动者模型来保持我们的功能观点。我们在这里发现了减少执行可能性和程序表达性的原则执行元是具有定义操作的线程：它有一个用于存储传入消息的缓冲区和一个专用内存区域它一次只处理一个传入的消息，从不允许其他参与者直接访问其内存区域通信完全通过消息的非同步传输来完成我们的工作是通过完成类型检查系统来加强演员的安全，该系统对演员之间的消息非常灵活。第5章介绍了一种标准的lambda计算语言，它添加了参与者模型的基元，并演示了如何定义一个也检查消息发送的类型系统。我们还致力于开发一个参数化的模拟发射平台，见第6章。9第一部分使用单子进行11第一章用单子进行在单子部分的介绍性章节中，我们介绍了编程语言及其特征，观察到的问题及其解决方案是基于这些特征的。我们介绍了使这些观察成为可能的背景：经济模拟器编程本节中使用的编程范例是函数式编程，特别是在值调用中，但也会有一些关于必要性调用的注释我们将以一种简化的方式展示在程序执行的每个阶段显示内存状态的执行模式我们将介绍调用堆栈机制，该机制用于在函数调用开始计算时保留上下文信息。这将允许我们引入然后，我们将解释接下来，我们将介绍目前最流行的在函数程序中模拟突变的技术：单子。我们将从程序员的角度来研究它们我们将比较同一个程序的不同版本我们将通过介绍单子变换器来研究单子的模块性最后，我们将讨论用函数式语言编写经济模拟器这里应该注意的是，通常1.a函数式编程简介"函数式"编程指的是"函数"："趋向于特定目标的活动"1。它是关于把下面是一个程序（或函数）（funx->x+1）的示意图，其中自然数作为域和共域：1. 维基百科目前https://fr.wiktionary.org/wiki/fonction第一章Monades的函数式编程简介1210让v=10让f=（乐趣x-> x+1）让a=4a=5;012...012...域：N共域：N一个函数有一个"输入"：它需要一个域类型中的参数（x）它有一个"输出"：它在共域的类型中给出一个返回值（x+1）总函数必须覆盖函数式编程是基于除了将一个函数，相对独立于它的上下文，并有一个非常简单的接口（一个输入，一个输出），很好地适合重用。现在，我们将用一种类似于OCaml函数式语言的语言来开发函数的特性在我们的语言中，我们可以声明一个表达式并将其与一个名称相关联，例如，我们将整数与名称v相：程序从上到下运行，每个名称都根据前面的名称进行计算。在下面的示例中，1 让a=42 让b= a+33 让c= d+24 让d=5我们有时会用"变量"这个词来表示一个名称。这并在函数式语言中，突变是被禁止或限制的。"标准"名称是不可变的，它们的表达式不能更改。但是，也可以"重载"一个名称，这包括声明一个已经声明的名称在下面的示例中，让a=2让x= a*10让a=3让y= a*10一旦给出了变量的这些细节，我们就可以接近这意味着提供输入并启动第一章Monades的函数式编程简介13151 让v=102 让f=（乐趣x->x+v）3 让v=204 设r=（f5）让v=10让f =（乐趣x-> x+v）v=20;设r=（ f5）设f=（fun x-> x+1）设 r=（ f5）L’exécutionf，因此，函数是一种延迟代码的求值的方法L’exécution LA的代码然后加载函数f，将名称x与5相关联。一旦此代码的计算结果为6，执行将从调用时的位置因此，名称r被赋予我们有时会使用"函数调用函数可以使用参数名称让v=10让f=（乐趣 x-> x+ v）让 r=（ f5）变量v在函数f中被称为"自由"，因为它不像变量x那样"绑定"到参数。函数f的自由变量集称为f的闭包。在前面的示例中， 如果是10，则r为10。但是在下面的例子中会发生什么呢是R 是15还是25？如果r是15，我们就有了"静态链接"：函数f中v的定义永远是定义f时有效的定义，第2行。如果r为25，则存在"动态链接"：v的值是调用函数f时的有效值，第4行。我们将为我们的语言选择静态绑定，因为它是当今请注意，静态绑定和名称不变性这两个属性的存在因此，使用相同参数对同一函数的两次调用无法区分。换句话说，一个函数不能"改变它的环境"，例如通过改变它的闭包中的变量值我们甚至可以在代码中将函数对其参数的应用替换为该应用的输出此属性称为"引用透明性"。更具体地说，如果对于任何程序p，p中e的任何出现都可以被e的求值结果替换，而不影响程序p的意义，则表达式e因此，可以通过用具有相同值的透明表达式替换透明表达式来对程序进行推理。如果对于任何透明表达式e，表达式（f e）是透明的，则函数f2. 前提是函数的自由变量在替换时是可计算的。否则，如果第一章函数式编程简介，使用单子14让f=（乐趣x-> x+1）让g=（乐趣 x-> x* x）让r=（ f（g10））1 让c=82 让fx=3让c=（x+c）in4字母r=（c+c）in5R6 设a=（f3）7 让c=128 让b=（f4）单词"value"表示计算表达式。例如，在这种语言中，我们使用"头的正常形式"，这意味着任何不是应用程序的表达式请注意，有几种评估可能性 例如，在下面的示例中，函数f的输入给出了哪个精确表达式？如果相反，如果在函数输入中按原样给出在这两种技术中，r的最终值将始终相同：101。在按名称计算时，执行仅计算所需的内容。 定义一个名称并不保证对其表达式的求值，也不保证将该名称作为函数调用的输入。在以下表达式（print（x +y））中print命令在屏幕上显示值L’évaluation de son argument est donc nécessaire, ce qui implique que lesévaluations de我们将应用基于下面是一个示例程序及其执行的示意图，说明了前面介绍的原则为了处理重载，我们将应用以下两种技术，而不是用数字来区分两个同名的变量（这会使阅读变得困难）：1. 闭包包含变量的名称以及函数定义中有效的值2. 对于每个函数调用，我们创建一个在调用结束时被删除的环境这会移除函式程式码所执行的变数覆写。代码1.a.13. Chris Okasaki在他的书"Purely functional data stringuctures"[Oka99]中写道，