文件标题：值递归在程序设计中的挑战

理论计算机科学电子笔记148（2006）3-25www.elsevier.com/locate/entcs初始化相互引用的抽象对象：值递归的挑战Don Syme1英国剑桥微软研究院摘要对象之间的相互依赖性在程序中频繁出现，并且程序员必须通过手动填充“初始化漏洞”来帮助构造相应的对象图（即空值和/或显式可变位置），从而典型地解决这种值递归。 本文的目的是增加正在进行的理论工作值递归与描述的半安全机制的广义形式的值递归ML类语言，初始化对应于一个图的懒惰计算的节点顺序强制，需要运行时检查的合理性在初始化期间的风格Russo。我们的主要贡献是使用mechanism开发引人注目的例子，说明在抽象边界存在的情况下，值递归的缺乏如何导致真正的问题，并给出微观例子，说明初始化图如何允许更多的程序在ML的无突变片段中表达。最后，我们认为，在异构编程环境中的值递归的半安全的变化可能是适当的ML类语言，因为从外部库的初始化效果是难以表征，文档和控制。保留字：ML，值递归，图，GUI编程1介绍编程语言的主要目标之一是允许以与非正式规范密切对应的形式编写程序。例如，以下是GUI表单（即窗口）的非正式规范，其中每个菜单项都切换另一个菜单项的激活状态。标题为“Form”的表单f1Email：ds y me@micr o soft. Com1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.11.0384D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3我们希望用一种没有突变或空指针的安全语言来编程在本文中，我们首先描述了ML风格语言中的值递归的这种机制有它的问题，但可以让我们编写上面的程序如下（我们使用类似OCaml的语法）：letrecf= req Form（“Form”，[m]）m= Menu（“File”，[mi1; mi2]）和mi1 = MenuItem（“Item1”，λ（）. t o g g l e （mi2））（A）并且mi2 = miMenuItem（“Item2”，λ（）. toggle（mi1））这里我们假设API：2type菜单项目类型菜单类型表单值Form：string* 菜单列表->表单val =“”>菜单：string* 菜单项列表->菜单val MenuItem：string *（unit→ unit）-> MenuItem valtoggle：MenuItem -> unit客户端程序在ML家族语言中是不允许的，因为ML静态地强制执行了一个强有力的初始化可靠性概念，特别是递归绑定不会失败或根本不会有副作用。为了解决这个问题，程序员编写了一个显式的初始化漏洞：让=函数|一些v→v|None→failwith“bug”let mi2 =refNoneletmi1 = MenuItem（“Item1”，λ（）. toggle（the（！mi2）let_= mi2：=Some（“Ite m2“，λ（）. toggle（mi1）let m= Menu（“File”，[mi1; the！mi2]）let f= n Form（“Form”，[m]）值递归的缺乏迫使程序员依赖于突变和失败来编写简单的程序，即使是在“安全”的函数式语言中31.1本文的贡献本文的主要贡献如下：• 我们描述了依赖于外部库（例如F#，MLj和SML.NET [22，2]）的新兴“面向平台”版本的ML如何• 我们通过形式演算（§2）描述了一种使用运行时检查和惰性的值递归形式，并证明了该系统的一些简单性质。虽然使用惰性来调解递归的原则是2我们使用λ（）。对于3另一种选择是使用一个引用单元格，该单元格保存一个初始化为多态失败虚拟值letdummy=raise“bug”的函数值。D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）35众所周知，我们还没有看到这个特定的系统作为严格语言的核心中的递归绑定的解释而被提出• 我们给出了一个程序的例子，它不能在ML的无突变片段中定义，但可以使用这种形式的值递归来定义• 我们给出了令人信服的和以前未注意到的例子，说明缺乏值递归如何迫使程序员打破抽象边界（§3-§5），包括对文献中的pickler示例的分析，肯尼迪[13]。我们还首次记录了GUI编程和值递归之间的关系（§6）。最后，我们总结了相关的工作和未来的方向（§8-§9）。请注意，本文并不是关于对值递归施加静态控制的（在整个过程中假设了一个标准的Core ML类型系统）。价值的静态控制递归是一个至关重要的目标，例如，参见[3，4，5，20，11]中关于在模块和混入的上下文中控制值递归的尝试的讨论相反，本文认为，安全和半安全机制的混合似乎仍然是必要的，特别是对于部署在异构多语言环境中的语言。2联系我们2.1通过显式使用懒惰来考虑下面对§1：4中的程序（A）的变换letrecf和m并且mi1' = lazy_menuItem（“Item1”，λ（）. toggle（force mi2 '））和mi2' = lazy_menuItem（“Item2”，λ（）。toggle（force设f=力 f令mi1 =力mi1绑定已经变成了惰性计算，但只是为了初始化的目的。我们称这样解释的let rec为初始化图。我们首先注意到，这种方法有明显的问题：• 图的节点是按需探索的，因此评估顺序可能是违反直觉的。然而，求值顺序仍然被精确定义，并且所有节点最终都被求值，前提是没有错误发生。• 导致循环初始化时间依赖关系[4]这里，lazy和force生成并消耗了延迟的αlazy类型的计算，使用适当的区分并集和引用单元来定义。6D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3导致运行时错误。这种情况下需要重新检查图是Dreyer在标准ML的递归模块的上下文中提出的无限制递归的一种形式[5]。图是一种直接而简单的值递归方法，并且懒惰可以用于编码值递归的一般观察是众所周知的（例如，参见[11]中的讨论）。然而，似乎没有人记录过使用惰性（与空指针相反）作为值递归基础的正式演算。此外，文献中缺少值递归重要性的令人信服的例子：例如，mixin模块和值递归之间的相互作用已经研究过[11，3，4]，但给出的例子只是简单的递归函数。此外，语义学家认为无限制的递归是一种必须不惜一切代价避免的邪恶，但它实际上是作为C#和Java初始化的动态链接语义的一部分出现的（参见第12节），因此探索无限制递归的选项似乎是严格静态技术的一个附属物。2.2术语：立即和延迟的支付我们做了以下区分，类似于德雷尔[5]所做的区分• 当执行let rec的绑定时，我们说一个直接依赖已经出现，即如果我们评估一个对v的引用，它在语法上出现在u的绑定中，那么从u到v的直接依赖已经出现。• 绑定完成后，闭包仍然可以引用这些变量。我们说这些的后续评估产生了延迟的依赖性，即。在用于u的绑定中句法上出现的对v的引用的评估生成从u到v的延迟依赖性。即时依赖和延迟依赖是动态概念：一般来说，不可能静态地确定递归绑定变量的给定语法出现是否导致即时依赖或延迟依赖，或者甚至两者兼而有之（在一般情况下，无法确定初始化绑定的哪些部分将执行）。延迟依赖与初始化的合理性无关：它们纯粹是被定义的对象值的涌现行为的一部分。2.3λI：初始化图本节介绍一个扩展了初始化图的类型化lambda演算。该语言由图1中的语法定义，除了允许递归绑定右侧的任意表达式外，它是标准的D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）37v=id变量e=v值/节点参考=e e函数应用= letrecb1和. b nine 递归绑定=funv−> eLambda Abstraction=print（）一个简单有效的构造b=v=e约束力Fig. 1. λI的λ我们结合了有效的动作打印（）。这种语言的类型规则也是标准的，这里不介绍图2中的评估环境和规则是非标准的。5.评估环境是指向位置的地图，而不是指向价值的地图我们省略了print（）和传播错误（参见§2.7）。给定的演算可以扩展为包括条件，非递归结构化数据，模式匹配，可变状态和I/O-本文中的大多数示例都假设已经进行了这些扩展。如果包含递归数据，则必须考虑直接递归绑定的数据和值递归之间的交互[12]，这超出了本文的范围6.我们将在稍后审议例外情况问题递归绑定的评估首先为每个变量分配一个新的延迟计算，然后评估每个形实转换程序。因此，递归绑定的执行不会留下未解决的延迟计算，因此延迟计算不会逃脱其词法作用域，如以下定理所示：定理2.1（成功的初始化消除了初始化thunk）设T（σ）={1|阿夫特角 σ（l）=（r，λ0e）}。则Γ，σ∈e~v，σJ蕴含T（σJ）<$T（σ）。证明是通过推导归纳的，在let rec绑定处进行适当的一个推论是，对来自没有初始化thunks的状态的项的求值产生没有初始化thunks的状态。我们非正式地提出，当λI被扩展到包含典型ML家族语言的完整构造时，相应的结果成立请注意：5我们采用了一个隐式规则，即程序的总体输出记录在状态中，尽管一般来说，输出在语义中除了支持最小有效操作之外不起任何作用。6我们的原型实现支持两者，但要求每个let rec要么使用数据递归，要么是一个初始化图，但不能两者兼而有之。7注意，这个定理是根据形实转换程序堆中初始化形实转换程序的数量和状态：通常无法观察到的东西。8D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3r =id→l环境σ=l→V图态V=v评估的深度Thunk| (Γ, λ0e)Delayed Initialization Thunk| errorInitialization Errorv =（Γ，λx.e） 闭合值f<$（x<$→y）函数扩张Γ（x）=l σ（l）=v Γ，σ∈x~v，σΓ（x）=lσ（l）=（Γ′，λ0e）Γ′， σ<$（l<$→error）<$e~v，σ′σ′′=σ′<$（l<$→v）Γ， σ∈x~v，σ′′Γ，σ0<$e1~（Γ′，λx.e），σ1Γ，σ1∈e2~v1，σ2新鲜报Γ，σ< $（funx->e）~（Γ，λx.e），σΓε（x<$→l），σ2ε（l<$→v1）εe~v2，σ3Γ，σ0< $（e1e2）~v2，σ3li′freshΓ =Γ（xi<$→li）（1≤i≤n）σ0=σ<$（ li<$→ （Γ′ ， λ0ei ））（ 1≤i≤n ） Γ′ ， σi−1<$xi~vi ， σi（1≤i≤n）Γ′，σn<$e~v，σ′r， σn（letrecx1=e1. . xn=enine）~v，σ′图二. 从λI的• 表达式从不计算延迟初始化thunks。• 初始化图中的位置永远不会有别名，因为它们不直接被表达式引用。• 递归绑定let rec x = e1in e2（其中x未在e1中使用）等效于传统的 call-by-valuei解释lettx= e1ine2。 ）的方式• 如果let rec右边的所有表达式都是直接函数，那么我们就有了letrec的传统语义。 （初始化thunks减少到闭包值）。2.4表现力图是对核心ML的扩展：所有现有的核心ML程序都可以在没有警告的情况下被接受，并以不变的行为运行如果不使用该机制，则不会发生初始化失败然而，初始化图确实扩展了ML变体的表达能力，这些变体包括数据抽象但不包括突变。考虑以下D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）39模块，定义流生成器具有标识的流8模块类型MSig =sig模块M：MSig =结构typettypet= T of string*（unit ->t）valint：（unit ->t）->t letintf= T（gen（），f）val next：t->tletnext（T（n，f））=f（）val id：t->string let id（T（n，f））= nend end考虑到上述情况，不可能生成类型为t的值，其中：id x1 = id（next（x1））= id（next（next（x1）=.不使用突变，即，显式初始化漏洞，例如，letx1hole = refNone让rec x1= rec（fun（）-> the！x1hole）let_=x1hole：= Some（x1）然而，初始化图允许我们定义这样的值：letrec x1= x2（fun（）-> x1）我们在不使用值递归或突变的情况下所能做的最好的事情是：letrec xf（）=xfletx2 =xf（）但现在每次调用next都会导致调用next，因此会导致多个对象标识，所以id（x1）id（next（x1））id（next（next（x1）。 注意，我们只实现了这一点通过对初始化健全性使用运行时检查来增加表现力。关于这个例子的进一步讨论见§ 9。2.5静态误差和误差λI允许无意义的定义，例如let recx = x + 1，其中x在绑定右侧的求值将导致立即异常。技术报告提供了一个简单的静态分析的细节，该分析报告了许多此类情况下的错误[23]。另请参阅Boudol [3，4]，深入讨论与值递归的特定静态类型系统相关的推理问题。此外，初始化图显然应该小心使用，因此在我们的原型实现中，每当使用该机制时都会给出警告。这些警告类似于典型的ML编译器给出的“不完全模式匹配”警告：存在不合理的可能性，并且程序员被告知这一8我们假设一个函数gen（）生成新的名字（也可以使用print（），输出的数量表示生成的名字的数量）。10D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）311nn我J2.6实现技术let rec的初始化图解释可以很容易地完全避免正常递归函数，即绑定x=e，其中e是λ或其他一些延迟计算，因此正常ML代码的性能不会受损。这些方法几乎涵盖了真实程序中所有的let rec绑定，我们还没有遇到过初始化图主导计算的非人为程序，因为这样的图通常用于指定GUI和其他反应式机器。然而，它们在实践中很容易实现：一个简单的转换可以将递归绑定转换为支持惰性计算的目标语言，例如OCaml中提供的。形式的每一个表达令recx1=e1. xn=enine转化为设x1，.， xn= letrecx′= lazye′. x′=lazye′在（力x′，...，力x′）1N在大肠其中每个eJ通过取ei并替换对每个xj的所有引用来形成力xJ。也就是说，值递归的使用被实现为惰性计算的初始化thunks所取代，对递归绑定变量的引用被强制操作所取代letrec中的所有表达式现在都是延迟计算，这是OCaml、F#和可选的SML/NJ支持的一种递归数据形式2.7尴尬的小队：值携带异常、并发和持续随附的技术报告[23]解决了三个额外的主题：可以抛出异常（特别是可以携带复杂数据值的异常）的初始化操作的语义由于我们的目标是有一个半安全的机制，可以补充静态技术，我们遵循典型的ML对这些问题的响应：ML不试图控制效果，语言的规范只是定义了单个线程上的计算结果。在实践中，不鼓励在初始化过程中使用对象，除非程序员认为对象是构造和连接构成递归绑定的对象的重要部分。例如，在.NET或Java编程的上下文中，可以创建线程对象并指定其属性，但不应启动线程本身如果将控制效果的一元系统添加到ML，则需要限制与D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）311初始化计算（参见§8和[10]）。我们顺便提到，ML这只是限制了可以被赋予广义多态类型的let绑定类，但这意味着抽象API有时必须将构造声明为计算而不是值。这与本文讨论的问题是正交的，其他静态类型编程语言（如Java）有更繁重的限制。3值递归示例：缓存本文的主要贡献之一是使用初始化图来呈现一系列引人注目的值递归示例，其中• 需要抽象API来创建相关对象的图形;以及• 对象图结合了即时和/或延迟依赖性，但是在即时依赖性中没有循环。我们的第一个例子展示了缺乏值递归如何导致程序员打破抽象边界。在实际的ML编程中，一个常见的例子与缓存有关例如，考虑具有以下抽象API的函数缓存，其中第一个参数是比较函数：val cache：实现方式可以变化，例如，下面的简单尝试，假设函数为使用具有给定比较函数的查询关联列表的函数ASPACK和ASPACKletcache cf f= letcref=ref []in funx->if if_asblockcfx（！cref）然后aspletcfx！cref else let y =fxin cref：=（x，y）：：（！cref）;y下面的简单程序尝试缓存even的调用：令rec odd n = even（n-1）even = cache compare（fun n -> n = 0 or odd（n-1））但是由于LET_REC限制而被拒绝。一个常见的结果是，程序员揭示和/或复制他们的缓存实现，或者简单地避免向递归绑定添加缓存，即使从性能的角度来看，它是适当的。12D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）34值递归的例子：自动机在下一个例子中，我们使用初始化图来描述自动机的相互引用状态。我们特别感兴趣的情况下，自动机状态的实现是隐藏的。假设我们希望以编程方式指定一个自动机，该自动机响应于信号在控制状态暂停、运行和结束之间转换，例如Unix文件句柄或实例.NET我们可以编写这样的代码使用对平台原语的显式调用的规范，例如Unix.NET的WaitHandle.WaitAny，后者的类型为WaitHandle数组→ int。然而，使用组合子和抽象值来表示控制状态也有其优点：状态的实现可以统一地扩充具有额外的跟踪、缓存、概要和/或模型检查功能，而不需要改变规范。因此，假设我们有以下API：类型状态类型Signal = WaitHandletype Transition = Signal* NextStatetype NextState = unit→ Stateval waitAll：Signallist * NextState→ Stateval waitAny：Transitionlist→ Stateval peekOne：Transitionlist * NextState→ Stateval doThen：（unit→unit）* NextState→ Statevalfinish： Stateval run：State→ unit这里，自动机是具有相关行为的状态对象，即程序指定的状态图中的节点waitAll自动机阻塞，直到所有给定的信号都被设置; waitAny自动机在信号之间进行选择并提交到一个选定的转换; peekOne是waitAny，具有零超时和默认转换; finish终止。使用run执行自动机会导致线程在信号的控制下从一个状态转换到另一个状态。处于doThen状态的自动机对该值执行给定的计算，然后进入下一个状态（在执行计算时不响应API使用NextState值的计算API的一部分的简单实现是：type State={ runAction：unit-> unit; count：int ref}let run st= incr st.count; st.runAction（）let finish={runAction=（λ（）. （））;count=ref0}letwaitAny transitions=let waithandles= Array.of_list（map fst transitions）in let actions= Array.of_list（map snd transitions）inletrunAction（）=leti = WaitHandle.WaitAny（waithandles）in run（actions. (i)（））在D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）313{runAction = runAction; count = ref 0}在这里，状态通过私有跟踪来增加，以计算进入每个状态此外，waitAny函数预先计算了两个数组，这两个数组在图形的实际执行过程中被重用工人自动机的转换现在可以使用初始化图来指定下面是一个这样的图（我们假设支持函数reset和step的类型为unit→unit，它们执行底层计算）：letrec initial= resetThen并且paused = waitAny [stepSignal，（λ（）. stepThen）;resetSignal，（λ（）.resetTheNode）; exitSignal，（λ（）.完成）]且stepThen = doThen（step，（λ（）.paused））和resetThen = doThen（reset，（λ（）. paused））let_ = runinitial这是一组相互依赖的抽象对象及其行为的紧凑声明4.1无初始化图状态机传统上使用递归函数来编程，例如，let waithandles=[|stepSignal; resetSignal; exitSignal|]let rec initial（）=resetThenRun（）并暂停（）=match（WaitHandle.WaitAny（waithandles））with| 0 ->step（）; paused（）| 1 ->reset（）; paused（）| 2 ->（）| _-> failwith“unexpected”这通过将状态定义为函数来避免let rec限制。然而，这个熟悉的习惯用法有一个明显的缺点，即状态不是抽象的：它们被认为是unit → unit类型的函数。 上面的程序对waitAny调用使用了显式的预计算数组，因为抽象API会遇到let rec限制，从而阻止这些数组从更抽象的规范中进行预计算。此外，状态计数插装只能通过修改客户端程序来添加，而不是扩充库，这违反了抽象。理想情况下，甚至不应该透露与指令和性能相关的缓存的5价值递归的例子：Picklers下一个例子来自Kennedy [13]，他引入了一个用于指定picklers的组合子库，这是一种指定管理数据结构的编组和解组的对象的组合方式亲-14D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3语法控制编组的内容、编组顺序、编组图中的共享以及底层数据格式的形状自动构建相应的解组器，以确保一致性。封送器可以被认为是具有一对封送/解封送方法的对象，尽管实现可以用附加功能来增强它们。其目的是通过组合子构建编组器，例如以下面向通道版本的API中的组合子type Channel（*e.g. afile stream *）typeα Mrshlval marshal：αMrshl→α * Channel→（）val unmarshal：αMrshl→Channel →αval pairMrshl：αMrshl *βMrshl→（α*β）Mrshlval listMrshl：αMrshl→（αlist）Mrshlval innerMrshl：（α→β）*（β→α）→αMrshl→β Mrshlval intMrshl：intMrshlval stringMrshl：string Mrshl元帅是αMrshl的实例。这里显示的组合器是用于对（pairMrshl）、列表（listMrshl）和内部数据（innerMrshl）的组合器。编组对象的类型是抽象的，但可以通过对象或记录类型实现，typeα Mrshl ={ marshal：α* Channel→（）;解组：通道→α}例如，如果文件由一些结构化数据表示，那么可以很容易地构造封送器：类型文件=int*stringletfileMrshl=pairMrshl（intMrshl，stringMrshl）let fileMrshl=listMrshl（fileMrshl）Kennedy观察到为递归数据结构指定编组器如何在标准ML中遇到let rec限制的麻烦例如，考虑以下递归数据类型（我们添加一些帮助函数以使后续代码更简洁）：typefolder ={files：filelist;subfldrs：folders}和文件夹=文件夹列表letmkFldr（x，y）={files=x;subfldrs=y} let destFldr f=（f.files，f.subfldrs）设fldrInnerMrshl（f，g）=innerMrshl（mkFldr，destFldr）（pairMrshl（f，g））我们现在希望为单个文件夹和文件夹列表创建封送处理器一种尝试如下：令recfldrMrshl=fldrInnerMrshl（filesMrshl，fldrsMrshl）且fldrsMrshl=listMrshl（fldrMrshl）但是，由于ML对值递归的限制，此声明被拒绝。它也将是一个无效的初始化图，因为它具有D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）315即时循环9即使你揭示了编组器的实现（就像我们在第4节中对抽象类型的状态所做的那样），你仍然功能协调发展的引用肯尼迪的话这个问题在解析器组合子[18]通过暴露解析器的具体函数类型我们在初始化图的上下文中，一个简单的解决方案是可能的。首先，我们在API中添加以下函数val delayMrshl：（（）→αMrshl）→αMrshl令 delayMrshl p ={marshal =（fun x→（p（））.marshal x）;unmarshal =（fun y →（p（））.unmarshaly）}这个函数需要一个延迟的计算，只有当一个marshal/unmarshal操作被调用时才被评估-它这正是让我们使用初始化图来构建编组器对象的递归图的原因。这可以用来打破直接依赖关系之间的循环令rec fldrMrshl = fldrInnerMrshl（pairMrshl（filesMrshl，fldrsMrshl））且fldrsMrshl = listMrshl（delayMrshl（λ（）.fldrMrshl））请注意，我们已经能够以简洁的风格定义交互编组对象的相互递归图6 值递归示例：GUIGUI提供了一个很好的对象相互引用图的示例源，其中即时依赖和延迟依赖都很突出。通常，相关GUI对象集合的小部件包含层次结构必须在创建时通过使用直接依赖关系来指定。此外，配置GUI组件的命令功能通常在初始化期间执行。我们已经展示了简单GUI组件中自引用的简单示例。这个故事在典型的手工编程或工具生成的GUI代码中以更大的规模重演，以至于GUI组件的初始化代码可以运行到许多页面，充满了组件网络例如，名为ConcurrentLife的程序的GUI组件（请参见这是显而易见的，因为存在依赖循环，但在右侧没有延迟计算，因此所有依赖都是立即的。16D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3[22]中的示例）涉及一个表单、一个菜单、7个菜单项、一个后台工作线程和一个记录显示状态的位图。 所有GUI对象 的Windows窗体库创建和操作的. NET。出现的问题如下：• 直接依赖性来自小部件包含层次结构;• GUI组件之间存在许多延迟依赖循环。• 所有主要的GUI API都是单线程的：工作线程可能不直接操作GUI组件，但必须通过GUI线程的事件循环序列化它们的GUI更新这会导致非本地延迟依赖循环：表单引用一个菜单项，该菜单项的操作会导致线程通过表单将计算结果序列化依赖项不是立即的，因为线程对象是在初始化期间创建的，但不是启动的。作者开发了这个程序的三个变体版本，使用以下技术来调解递归：• 显式初始化漏洞（选项ref）;• 明确使用懒惰;• 初始化图形。递归引用基本上出现在递归绑定的每一行。用初始化图编码的版本看起来更简单，更容易维护和修改。实际上，所有版本的程序都是可靠的。初始化，但在任何情况下都不能被静态类型系统检查。然而，使用显式技术的版本被发现包含几个竞争条件w.r.t.多线程。与显式中介值递归相关的重复混乱实现得很少，并且模糊了程序的真实逻辑。6.1“Create and Configure”大多数GUI编程API需要直接指定和额外的初始化风格的组合，我们称之为配置和配置。例如，导言中的API实际上可以如下结构：val Form：string ->Form valMenu：string ->Menuval MenuItem：string -> MenuItem10在.NET Windows窗体库的上下文中，这是通过使用每个窗体对象上提供的Form.Beginerlke方法来完成的，该窗体对象充当相关GUI组件组的容器。D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）317val toggle：MenuItem-> unitval setMenus：Form*Menulist-> unitval setMenuItems：Menu* MenuItemlist->unit valsetAction：MenuItem *（unit->unit）->unit在这里，API使用显式突变来检查组件的事后配置使用配置和配置APIs的缺点是缺乏局部性：指定对象的配置信息分布在代码的创建和配置部分。可能的调用图也变得更难理解。11通过将配置操作添加到图中，可以将配置和配置API与初始化图结合使用例如实施例(A) 第1节可以写成：letrecf= f Form（“Form”）（a）and _ = setMenus（f，[m]）（b）和m=setMenu（“File”）（c ） 和 _ = setMenuItem （ m ， [mi 1; mi2] ）（d ） 和 mi 1 = setMenuItem （ “Item 1” ）（e ） 和 _ = setAction （ mi 1 ， λ （ ） 。toggle（ mi2 ） ）（ f ） 和 mi2 = setMenuItem（“Item2”）（g ） 和 _ = setAction （ mi2 ， λ （ ） 。toggle（mi1））（h）在这种情况下，绑定将按顺序a、c、b、e、g、d、f、h完成。显然，程序员只将这种绑定用于本质上是可交换的初始化操作是至关重要的，也就是说，程序员应该确保在所有绑定都建立之后执行配置操作会获得相同的结果7面向对象语言中的图和自为了完整起见，我们记录了在OO语言的设计和使用中值递归和递归问题之间的联系面向对象语言使用标识符self（或this）进行自引用访问，并且通常具有在初始化期间使用对象引起的不合理性例如，在构造函数的中间调用虚方法可能会导致许多问题，不同的语言甚至为相关的分派实现限制self的使用直到所有字段都被初始化的语言似乎太不灵活了，尽管更自由的系统甚至在虚拟机验证器中引起了一些安全漏洞[9]。11OO API还允许通过方法重写来配置组件就本文而言，这只是一种在初始化过程中直接指定函数参数值的方便方法。18D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）3我们注意到，初始化图允许你在方法中编码自引用，而根本不需要在语言中使用self例如，考虑以下将对象编码为ML记录的编码。12type object ={ getName：unit ->string;lengthOfName：unit -> int}letmkObject name =letrec obj ={getName =λ（）. 姓名;lengthOfName= λ（）.getName（）;}在目标内部递归绑定是一个初始化图，自引用obj.getName永远不会导致运行时错误，因为依赖项被延迟，即只有在稍后调用lengthOfName时才会显示 技术报告[23]给出了更多的例子，其中self在定义相互引用的对象时遇 到 了 限制 。这意味着，初始化图承认一个有纪律的方法，介绍有限的静态检查的初始化合理性在面向对象编程的上下文中。例如，考虑以下错误程序：letrec mkObject name =letrec obj =let len= length（obj.getName（））in{getName =λ（）. name;lengthOfName= λ（）. int;}obj在OO的说法中，方法getName在obj的构造逻辑期间被调用。上面的错误将被§2.5中描述的静态检查捕获，所以初始化图至少提供了一些针对这种错误的保护（典型的OO语言不会抱怨调用初始化期间的虚拟方法此外，初始化图是例外而不是规范这与大多数OO语言形成鲜明对比，在大多数OO语言中，通过self广泛使用递归初始化引用使设计，推理和分析的许多方面变得复杂。动态加载时的顶级初始化图实际上出现在OO语言动态加载组件的顶级静态初始化语义中。C#和Java通过类初始化器支持顶级初始化。一个C#ex-task引擎（例如，编译器[14]）通常会执行类初始化器，12将对象系统编码为ML会遇到限制然而，这与本文讨论的问题是正交的。D. Syme/Electronic Notes in Theoretical Computer Science 148（2006）319第一次访问一个类的静态字段。所有静态字段最初都设置为空值。如果两个类的静态变量之间存在相互引用，那么一个类初始化器将首先完成，并且可以观察到空值，即使所有静态字段似乎都由每个静态初始化器初始化在并发设置中，互斥只应用于单个类初始化器的粒度，因此执行相互引用的类初始化器的线程可能会死锁。这个函数可以任意打破这些死锁，并且可以观察到空值在实践中，程序员避免了类初始化器之间的相互引用8相关工作递归是计算机科学理论和实践中的一个主题，初始化图的概念与其他环境中提出的思想有很强的相似性我们相信，本文中研究的机制和示例将对那些追求动态链接，递归，固定点和效果的纪律方法的更多理论方面的人有用我们也相信，它将为这一领域的类型系统的开发提供额外的动力Scheme随附的报告[23]描述了许多其他语言中的值递归方法在Scheme中，引言中的示例变为：（letrec（（mi1（MenuItem（“I te m1“，λ（）. toggle（mi2）（mi2（MenuItem（“I te m2“，λ（）.toggle（mi1）（m（Menu（“File”，（mi1，mi2）（f（表格（“Fo rm“，（m）.）Scheme执行时初始值设置为undef，这是一种初始化漏洞。这里的问题是，程序员必须根据直接依赖关系图手动对声明进行排序，如果这种顺序指定不正确，则不会提供保护。 我们已经展示了直接依赖性是如何非常自然地产生的，特别是当在对象被定义，或者在组合器生成的对象的情况下，如§5中的编组器，延迟依赖是例外而不是规则。API、数据还是语言？值递归的一种方法