嵌入式解释器：类型安全、独立编译、可扩展的解释器

理论计算机科学电子笔记148（2006）181-209www.elsevier.com/locate/entcsML Module Mania：一个类型安全、独立编译、可扩展的解释器诺曼·拉姆齐哈佛大学工程与应用科学系摘要为了说明一个强大的模块语言的效用，本文提出了嵌入式解释器Lua-ML。解释器结合了可扩展性和单独编译，而不损害类型安全。它的类型是通过对内置类型和扩展应用求和构造函数来扩展的，然后使用两级类型打一个递归结;求和构造函数使用ML函子编写初始基通过从各个扩展中组合初始化函数来扩展，也使用ML函子。关键词：可扩展解释器，嵌入式解释器，脚本语言，高阶函子，ML模块1引言ML为从可重用模块构建程序提供了非常强大的机制这种能力在其他流行语言中是不存在的，习惯于这些语言的程序员想知道是否真的需要一个强大的模块系统。本文通过一个扩展的编程示例探索了ML模块的强大功能，包括高阶函子。该示例解决了解释器构造中的一个问题：如何在安全的语言中将可扩展性与单独编译相我们重点讨论了一种解释器，其中可扩展性和独立编译是特别重要的：嵌入式解释器。嵌入式解释器实现了一种可重用的脚本语言，可用于控制复杂的应用程序（如Web服务器或优化编译器），该应用程序是用ML等静态类型的编译主机语言编写的。解释器1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.11.045182N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181成为应用程序的一部分，因此应用程序可以调用解释器，解释器可以调用应用程序中的代码。这一想法首先由[21]证明，并被广泛模仿[3，16，12，15，29]。有时候宿主语言也可以用于脚本编写[17]，但通常在运行时使宿主语言编译器可用是不方便的，甚至是不可能的脚本语言及其解释器必须满足以下几个要求：1. 它们必须是可扩展的：关键是将应用程序特定的数据和代码添加到脚本语言中2. 解释器应该与宿主应用程序分开编译。特别是，它应该可以编译一个应用程序特定的扩展，而不使用或更改解释器的源代码。换句话说，解释器应该被隔离在库中。3. 应用程序和脚本语言的组合应该是类型安全的，这种安全性应该由宿主语言编译器检查本文介绍了Lua-ML，据我所知，它是第一个满足所有三个要求的嵌入式解释器。 Lua-ML的API使之成为可能将Lua解释器嵌入到用ObjectiveCaml编写的应用程序中。Lua-ML使用Objective Caml目前，Lua-ML的主要应用是编写和控制可移植汇编语言C的优化编译器。编译器大约有25，000行Objective Caml，使用大约1，000行Lua来配置后端和调用前端、汇编器、链接器等。2背景：可扩展解释器以前关于可扩展解释器的工作有两个方面。使用C语言所做的工作已经产生了可扩展和单独编译但不是类型安全的嵌入式解释器：安全性丧失，因为每个主机值都被赋予了一个使用函数式语言所做的工作已经产生了可扩展和类型安全但不单独编译的解释器因为这项工作已经为Lua-ML的设计提供了信息，所以我们首先回顾一下。Lua-ML的灵感部分来自SteeleSteele遵循[30]设定的议程，即使用Monad来表达可能在解释器中实现的各种语言特征。An “extension” mayinclude not only a newN. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181183新的语法、新的控制流程、新的求值规则或其他新的语言特性。Lua-ML的目标要小得多：与Lua [11]一样，解释器的语法，控制流程和求值规则不能扩展;唯一可能的扩展是添加新的类型和值。我们对用于添加新类型的机制感兴趣Steele的解释器是用一个“塔”的类型构建的。在这样的塔中，一个扩展是使用一个类型为×的类型构造函数来定义的。例如，可以使用类型构造函数arithx定义任意精度有理算术的扩展：type|“值 *”值的比率|下一个类型构造函数arithx表示塔的一层。类型参数“next” 因此，上面的扩展将算术层的值定义为任意精度的整数、两个值的比值或下一层的值。在任何嵌入式解释器中，一个关键问题是如何在原生宿主语言值（如Big int.big int）和类型变量value代表的嵌入式语言值之间从宿主值到嵌入值的转换称为嵌入，从嵌入值到宿主值的转换称为投影。在类型的塔中，嵌入和投影是通过在塔中上下移动的组合函数来实现的。每个这样的函数都很简单;例如，函数fun v -> Other v可以嵌入arithx以下级别的值，函数fun v -> Otherv可以向下投影arithx级别的值。function其他v ->v|->提高投影。构建一个完整的类型之塔需要通过“next”参数连接多个级别 使用类型参数来打一个递归结被称为两级类型[22]。举个例子，这是一个非常简单的塔，有两层：void（空类型）和arithx。打结需要对价值进行递归定义：type void = Void of void（* no values *）typevalue =（value，void）arithx（* illegal *）184N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181不幸的是，在ML和Haskell中，这种值的定义都是非法的：只有当所讨论的类型是代数数据类型时，才允许递归类型定义Steele通过使用程序简化器解决了这个问题，它将类型的塔减少到Haskell编译器可接受的单一递归定义。(The简化器还消除了使用上述Other等值构造函数时固有的间接性。使用简化器消除了任何单独编译的可能性，因为简化器执行相当于整个程序分析的工作。[19]也通过组成部分来构建解释器，但它们使用的是单子变换器，而不是伪单子。我们再次关注类型的定义。Liang、Hudak和Jones没有使用类型参数。• 代替Steele• 为了代替Steele此类型构造函数的作用类似于ML中的cons单元格：它应用于联合中的类型，并且不是任何类型的一部分。相比之下，斯蒂尔在Haskell 98中，求和构造函数被称为Either[23];在早期的工作中，它被称为OR。在Objective Caml中，可以这样写：type（'a，'b）either ='a的左边|b的权利求和构造函数简化了每个级别上类型的定义，因为Other这样的值构造函数不再需要了。上面的例子可以写成type value =（arithx，void）arithx = Big_int的Bignum|价 值* 价值与空隙的比率=空隙的空隙The 由于相互递归的类型必须在单个模块中定义，因此这种设计牺牲了单独编译。Liang、Hudak和Jones使用多参数类型类定义了嵌入和投影函数，重载了函数embed和project（称为inj和prj）。对于使用OR构建的类型，适当的实例声明可以自动组合这些函数。Lua-ML借鉴了所有这些来源的思想。N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181185• 像用C编写的嵌入式解释器一样，Lua-ML是一个单独编译的库。• 像这些解释器之一Lua一样，Lua-ML将其可扩展性限制为新类型和值;语法和求值规则永远不会改变。• 像Steele的解释器一样• 像Liang、Hudak和Jones但是Lua-ML使用ML函子，而不是本文的其余部分描述了Lua-ML扩展是什么样子的，以及如何将扩展与Lua-ML的模块组合在一起，一个雄心勃勃的例子出现在第4节。3使用库Lua-ML基于Lua，一种专门为嵌入而设计的语言[12，14]。Lua-ML实现了Lua语言版本2.5，由[13]描述。2.5版本相对较旧，但它成熟而高效，并且省略了后来版本的一些复杂性。最新的版本是Lua 5.0;我在适当的地方提到了difficult。Lua 是 一 种 动 态 类 型 语 言 ， 有 六 种 类 型 ： nil 、 string 、 number 、function、table和userdata。Nil是一个单例类型，只包含值nil。表是一个可变的哈希表，其中除了nil之外的任何值都可以用作键。Userdata是一种包罗万象的类型，其目的是使应用程序能够向解释器添加新类型。这样的类型必须是指针类型。要添加一个新类型，应用程序为该类型分配一个唯一的标记（或者在Lua 5.0中，一个元表），并用这个标记将该类型的值表示为userdata。这种技术需要少量的不安全代码，但这些代码可以隔离在几个C过程中。Lua-ML使用相同的整体模型，但Lua-ML可以扩展任何类型的用户数据，并且它没有不安全的代码-这是用ML编写的解释器的要求在Lua和Lua-ML中，扩展的惯用单位是库。Lua附带了数学、字符串操作和I/O的库。应用程序员在设计自己的扩展时可以使用这些库作为模型。库最多可以执行三项任务：1. 每个库都定义了额外的值（通常是函数），这些值在启动时安装在解释器中。这些值可以存储在186N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181在全局变量中，在作为全局变量的表中，等等。它们成为Lua初始基础的一部分。例如，Lua I/O库定义了一个函数write，它执行输出。2. 库可以定义用户数据的其他类型。例如，Lua I/O库定义了一个表示“打开文件句柄”的类型3. 库可以为解释器定义额外的可变状态。这种状态可以通过Lua变量暴露，也可以隐藏在Lua函数后面。例如，Lua I/O库定义了一个在C语言中，Lua库隐藏在一个函数后面，该函数在解释器中安装Lua值，获取userdata的标记和可修改的状态。例如，Lua I/O库隐藏在函数lua iolibopen后面。Lua-ML使用Lua的库模型，但用于封装库的程序结构是不同的：每个库都使用ML模块定义。将这些模块的签名与库执行的任务相关联是设计的一个要点3.1图书馆签名每个库都向解释器添加新值（任务1），但添加新类型（任务2）和新状态（任务3）是可选的。根据行使的选项，有四种类型的库。可以给每种库赋予自己的签名，但这样的设计有两个缺陷：• 四个签名太多了，特别是如果我们希望库是可组合的：明显的组合方案使用十六个函子。• 库如何共享类型或状态并不明显在复杂的应用程序中，共享类型是很常见的。例如，我们的优化编译器定义了一个表示控制流图的类型。这种类型在每个后端的库之间共享，用于寄存器分配器和优化。相比之下，国家很少被使用，也很少被分享。这些问题将在第5节中详细讨论。Lua-ML不是将一个库放在一个模块中，并为每种库使用不同的签名，而是将一个库拆分为多个模块。• 新类型的定义（任务2）出现在类型模块中，它与USERTYPE签名匹配。类型模块还包括一些相关的功能，例如，用于打印新类型的值的函数• 新值、函数 或状态的定义（任务1 和3 ）出现在代码模块中，与USERCODE或BARECODE签名匹配（第3.4节）。N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181187这种签名中最有趣的组件是一个init函数，当它应用于解释器• 如果代码模块要求解释器包含特定的新类型，则该模块表示为MLfunctor; functor将所需类型的视图作为参数，并产生匹配USERCODE的结果。视图提供了一个类型以及嵌入和投影该类型的值的能力;它与签名TYPEVIEW（第3.4节）相匹配。如果两个或多个代码模块共享一个类型，则通过将它们应用于同一视图来表示共享。因为状态很少被共享，Lua-ML没有提供一个视图机制来共享状态。相反，如果状态在两个或多个库之间共享，则该状态必须存储在全局Lua变量中，这使得所有库和Lua代码都可以访问它。这种状态可以通过给它一个抽象类型并只允许某些库依赖于该类型来保护它不受不必要的突变的影响如果state是一个库的私有属性（这是常见的情况），它可以隐藏在该库中的一个或多个函数换句话说，它可以作为这些库函数的一个或多个自由变量出现。类型模块和代码模块是[2]所谓的对称组件的例子：类型模块可以组合成一个新的类型模块，代码模块可以组合成一个新的代码模块。这种组合技术在TCP/IP协议栈为FoxNet开发[5]。通过利用组合，如果我们愿意，我们可以将库定义为由一个类型模块和一个代码模块组成的一对3.2连接在被单独编译之后，类型模块和代码模块被链接以形成解释器。1. 使用Lua-ML模块T包括其组成类型模块中的每一个的视图。2. 每个代码模块都是T的专用模块;例如，如果一个代码模块依赖于一个或多个类型模块，它将应用于T中的相关视图。3. 使用Lua-ML4. 模块T和C与一个解析器连接，形成一个解释器：188N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181模块I= MakeInterp（Parser.MakeStandard）（MakeEval（T）（C））Combine函子和相关的签名将在本节的其余部分描述;一个扩展的示例将在第4节中出现。3.3要素的设计值和状态Lua值和Lua解释器的状态都表示为宿主语言Objective Caml中的显式值。Lua解释器包含一个匹配VALUE签名的子模块，其缩写版本为模块类型VALUE = sig类型type srcloc（* a source-code location*）type value = Nil|浮动次数|一串一串| srcloc * func的函数| 用户数据的用户数据|表table和func=值列表->值列表和表=（value，value）Luahash.t和userdata =value userdataand state = { globals：table }（* 其他字段省略 *）valeq：value-> value-> boolval to_string：value -> string...端Value签名表示一个签名族;通过给出“userdata”的定义来标识该族的成员在一个实现中，“用户数据构造函数userdata使用这种机制，值类型可以通过库进行扩展相比之下，状态类型不能扩展。可以用作userdata'的类型构造函数的一个示例Lua-ML I/O库中的Luaiolib.ttype'a t = In of in_c h a n n e l |out_channel外N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181189因为打开文件句柄不包含Lua值，所以不使用类型parame- ter嵌入和投影从Caml值转换为Lua值（Caml类型的值）需要嵌入函数;从Lua转换为Caml需要投影。嵌入函数和投影函数成对出现，为了表示这样的一对，Lua-ML定义了type对于我们嵌入到Lua值中的特殊情况，我们定义类型type与Tcl或Lua等API不同， Lua-ML使用高阶函数来提供无限的嵌入/投影对：嵌入和投影是一个类型索引的函数家族。[4 ]独立发现的这个想法受到[6]的启发，他使用类似的族来实现部分求值。1我们构建类型索引的函数家族如下。• 对于基类型，比如float，我们提供了一个合适的嵌入/投影对。Lua-ML包括float、int、bool、string、unit、userdata、table和value对。• 对于只接受一个参数的类型构造函数，比如list，我们提供了一个高阶函数，它将嵌入/投影对映射到嵌入/投影对。Lua-ML包括列表和选项类型构造函数。• 对于一个有两个或多个参数的类型构造函数，比如函数arrow->，我们继续类似的思路。在Lua-ML中，构建嵌入/投影对的函数是VALUE签名的一部分;细节在其他地方出现[24]。这里重要的是，我们需要为每个类型模块提供一个这些对由用于构建解释器的函子构造。库 可 以 定 义 自 己 的 嵌 入 / 投 影 对 。 例 如 ， I/O 库 需 要 从 类 型Luaiolib.t（打开文件句柄）转换为类型in channel（文件打开输入）。转换是通过嵌入/投影对infile完成的，它的类型为channelmap。它使用了一个对t，它具有类型Luaiolib.t映射。这个对是从Luaiolib.t型的模的观点得到的。let infile=1[7]归功于Andrzej Filinski和Zhe Yang开发了这种技术。190N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181let failv = raise（Projection（v，“input file”））in{embed =（funf-> t.embed（In f））; project=（funv -> matcht.projectv withIn f->f|_->失败v）}每当投影失败时，就会引发异常投影登记初始化解释器的过程包括注册。库通过将值存储在全局Lua变量、表或其他结构中来注册值。在Lua状态下，可以通过直接操作全局变量表来执行注册，但Lua-ML提供了两个方便的函数：函数registerglobals具有类型（string*value）list-> state -> unit;对于列表上的每个（s，v）对，它使v成为状态中全局变量s的值。函数寄存器模块具有类型string ->（string*value）list-> state -> unit;它体现了将一组相关函数放在单个全局表 如果一个正在注册的值已经存在，和register模块引发异常。例如，Lua-ML I/O库在启动时注册了许多函数。注册发生在调用init时，接收具有state类型的interp。let init interp=let io = {currentin=stdin;currentout=stdout} inI/O库函数的定义register_globals[“open_in”，efunc（string**->> infile）open_in;“close_in”，efunc（infile**->>unit）close_in...[英]解释I/O库用新的私有状态扩展解释器：io记录。可变字段currentin和currentout维护当前输入和输出文件，这些文件只能由I/O库中的函数访问。函 数 open in 和 close in 在 Caml 中 是 普 遍 存 在 的 。 值 efunc 、string、**->>和unit都与嵌入有关;代码嵌入open in和close in，openin的 类 型 为 string -> in channel， close in的 类 型 为 in channel ->unit。详细信息可以在配套文件中找到[24]。init函数注册了许多其他函数，这些函数没有显示出来，但是在I/O库函数的定义中有定义，因此它们可以访问currentin和currentout。3.4解释器的组成部分由于构建Lua-ML解释器需要如此多的模块，我将它们的签名和关系总结在一个图中。图1显示了N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181191图形视图，它使用气泡和箭头;以及代数视图，它使用关于模块和签名的非正式匹配和子类型声明。要么查看表面来总结系统，这样你就可以专注于你发现的更合适的。• 类型模在左上方的方框和中间的代数声明组中描述。代码模块在右上方的方框和下面的代数声明组中描述。解释器的其他组件在图形视图的底部和代数权利要求的顶部组中描述。• 手写的模块在图形视图中显示为双边界椭圆中的符号，在代数视图中显示为斜体的短语。Lua-ML提供的模块或通过应用函子构建的模块在图形视图中显示为单边界椭圆形的签名，在代数视图中显示为打字机字体的名称• 一个可能的函子应用程序在图形视图中显示为一个用箭头连接的小圆圈。在大多数情况下，传入箭头来自函子的参数，而标有函子名称的传出箭头指向其结果。然而，在某些情况下，一个传入箭头来自函子，另一个来自其参数;标记为“函子应用”的传出箭头实线箭头表示客户端代码中的函子应用程序;虚线箭头表示由Lua-ML的高阶函子之一“在幕后”完成的函子应用程序一个可能的函子应用程序在代数视图中显示为签名中的箭头。在这两 个 视 图 中 都 出 现 的 一 个 例 子 是 MakeEval ： 它 可 以 应 用 于 匹 配USERTYPE的模块和匹配USERCODE的模块，以生成匹配MANUFACTOR的模块。• 图1显示了两种形式的签名子类型作为is-a子类型的一个例子，任何匹配COMBINED TYPE的模块也匹配USERTYPE。该关系在图形视图中显示为虚线箭头，在代数视图中显示为关系≤。作为has-a子类型的一个示例，任何与COMBINEDTYPE匹配的模块都包含子模块与TYPEVIEW匹配。该关系在图形视图中显示为虚线箭头，在代数视图中显示为关系≤。 .应用所有Lua-ML函子的最终结果既然解释者是我们的最终目标，我们就从那里开始解释192N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181<<>>12我<模块类型：类型定义，等式，embeddin g/p r ojection，. . .函子应用签名子类型（is-a或has-a）组合式Combine.T2TYPEVIEWuserType电梯组合视图值核心MakeEval评估器函子应用Parser.MAKER图书馆(with初始化函数）MakeInterpINTERPUSERCODECombine.C2WithType函子应用BARECODE前用户代码代码模块：库函数8国际米兰P≤米兰TOR≤CORE≤. 值MakeInterp：解析器.MAKER→解析器→ Interp：Parser.MakeStandard：Parser.MAKERMakeEval：USERTYPE→USERCODE→验证器适用于特定应用类型τ的8型模块：USERTYPEτ> 组合T2：用户类型τ1→用户类型τ2→组合类型τ1+τ2组合类型τ≤用户类型τ组合D类型Eτ+τ≤。类型Wτ：组合D视图S≤。TYPEVIEW8电梯：组合式→类型视图→组合视图> 使用应用程序特定类型τ的代码模块：TYPEVIEWτ→USERCODE不使用应用程序特定类型的代码模块：BARECODEUSERCODE= CORE→sig val init：state->unitend>：WithTypee：USERTYPE→BARECODE→USERCODECombine.C2：USERCODE→USERCODE→USERCODEFig. 1. ML模块狂热：Lua-ML解释器CodemoduleTsypemodulesIn preterN. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181193翻译解释器是通过将MakeInterp函子应用于求值器和解析器来构建的通过提供一个非标准的解析器，用户可以扩展解释器所接受的具体语法。这样的延伸必须是跨--后期引入现有的抽象语法，因为Lua-ML的抽象语法是不可扩展的。签名INTERP和仿函数MakeInterp声明如下：模块类型INTERP=sig包括扩展器模块解析器：Luaparser.S，类型为chunk=Ast.chunkval = unit -> stateval dostring： state -> string -> valuelist...端模块MakeInterp（MakeParser： Parser.MAKER）（E：MAKATOR）：INTERP，模块值= E.值在一个匹配INTERP的模块中，函数dostring创建一个全新的、完全初始化的解释器，函数dostring计算一个包含Lua源代码的字符串。我们省略了解析器签名Luaparser.S和Parser.MAKER，它们没什么意义。评估者计算器是使用类型模块和代码模块生成的。评估员的签名是模块类型BASIATOR =sig模块值： VALUEmoduleAst： ASTwith module Value =Valuetype state =Value.statetype value = Value.valuevalpre_order：unit->state类型compiled = unit-> valuelistval compile：块列表->状态->已编译...端求值器使用子模块Value和Ast提供值和项的定义。它提供了pre-configuration，它创建和编译一个解释器，它提供了compile，它将抽象语法转换成一种可以有效计算的形式它还提供了许多方便的功能，这里没有显示为了构建求值器，将函子MakeEval应用于类型模块T和代码模块C，其中的每一个通常是相似模块的组合。type模块提供了类型构造函数T.t，它被用作Value.userdata如3.3节所示，MakeEval通过定义value包含userdata，并将userdata定义为值T.t，来连接递归结。代码模块提供了一个初始化和注册函数，由预处理器调用。模块MakeEval194N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181（T：USERTYPE）（C：USERCODE，类型为：类型为“a Value.userdata”=“a T.t”的查询器这里，对模块C的with类型约束确保了类型模块和代码模块是一致的，这是类型安全所必需的定义和组成类型模块类型模块的基本构造块是用户定义类型，它是一个匹配USERTYPE签名的模块。模块类型USERTYPE =sig类型val eq：valtname： string（*type类型构造函数操作eq和to string是必需的，因为在Lua中，必须能够比较任意两个值是否相等，并将任意值转换为字符串。因为比较价值观类型最后，Lua-ML命名每个类型，所以如果投影失败，它可以发出一个信息错误消息。如何用多态的类型构造函数扩展Lua-ML可能并不明显。例如，如果您不喜欢可变表，而更喜欢类型为（'k，'v）tree的不可变二进制搜索树，该怎么办您可以轻松地将树构造器引入Lua-ML，但有一个关键限制：类型变量因为Lua是动态类型的，正确的做法是用value实例化两者，但是因为在定义树的类型模块时不知道value，所以类型模块必须使用它的类型参数：模块TreeType：USERTYPE，类型为fun eq eq ' t1 t2 =.fun to_string _ _ =“二进制搜索树”valtname =“搜索树”端类似的限制也适用于将多态函数引入Lua-ML [24]。一个类型模块只向Lua添加一个类型，但是一个复杂的应用程序可能需要添加许多类型。为了添加许多类型，程序员将多个类型模块组合成一个类型模块，并将其传递给MakeEval。类型模块使用类似Combine.T2的函子进行组合，如下所示，它接受两个USERTYPE模块作为参数并返回N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181195TV1.mapTV2.maptypetype图二、组合类型中组合类型的视图组合类型模块。签名COMBINED TYPE不仅包括USERTYPE，还包括每个组成类型的嵌入/投影对。嵌入/投影对隐藏在与TYPEVIEW签名匹配的子模块中，其定义大致如下：模块类型TYPEVIEW= sig类型type端类型类型要查看组成单个组合类型的所有单个类型，需要一个这种模块是由两种类型的模块组成的模块类型COMBINED_TYPE =sig包含USERTYPE模块类型VIEW= TYPEVIEW，类型为模块TV2：VIEW结束每个视图通过图形可以更好地理解这种组合;图2显示了单个组合类型及其与组成类型的关系。每个组成类型都可以嵌入到它上面的组合类型中;组合类型可以投影到任何一个组成类型中，但投影可能会引发异常。Combine模块提供了functorCombine.T2，它组合了两个类型模块并返回适当的视图。由于COMBINED TYPE是USERTYPE的子类型，因此应用Combined.T2的结果本身可以传递给Combine.T2：模块合并：sig模块T2（T1： USERTYPE）（T2： USERTYPE）：COMBINED_TYPE，类型为类型为...端196N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181COMBINED TYPE签名中的组成类型的视图对于构建使用这些类型的库是视图提供了投影函数，使库模块能够从组合类型（可能是userdata）的值获取到其选择的组成类型的值。Combine.T2背后的思想与[19]的OR类型构造函数背后的思想非常相似。由于Liang、Hudak和Jones使用的是Haskell，他们通过使用类型类来定义OR类型的嵌入和投影，而不是函子定义和组成代码模块代码模块是一个库模块，它通过注册值和函数来扩展解释器。代码模块必须知道要初始化哪种类型的解释器。图1显示了一个最终解释器（INTERP）是从一个编译器中产生的，它包含一个翻译器（编译器）和库。实际上，在编译器之前还有一个阶段：解释器核心，如图1所示为CORE，编译器的超类型。模块类型CORE=sig模块V： VALUE...val register_globals：（string * V.value）list-> V.state ->unit val register_module： string ->（string * V.value）list-> V.state ->unit端解释器核心包含一个定义值的子模块V。此定义包括使用类型模块构建的用户数据的定义。一个解释器核心还包含一些方便的函数，我们只展示其中最重要的：上面提到的注册函数。代码模块使用这些注册函数以及类型V.value和V.state来帮助初始化解释器。代码模块的思想很简单：它是一个接受解释器核心并产生初始化函数的函子。最简单的代码模块来自一个库，它不添加新类型，因此不依赖于任何特定于应用程序的类型。模块类型BARECODE =functor（C：CORE）-> sig val init： C.V.state-> unitendBARECODE类型的代码模块可以与任何匹配CORE的模块一起使用。但是，如果代码模块依赖于一个或多个特定于应用程序的类型，则有两个额外的要求：• 它必须有合适的嵌入和投影函数，也就是视图，它可以在用户数据和应用程序特定类型的值之间进行映射。• 为了确保类型安全，它只能与解释器核心一起使用，该解释器核心提供了userdata类型构造函数的适当定义A定义N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181197如果它与嵌入和投影函数一致，则是合适的。换句话说，我们真的很想 描 述 一 系 列 签 名 ， 比 如 BARECODE ， 但 是 在 functor 参 数 C 中 的userdata我们首先解决第二个要求。在构造函数上参数化一系列签名的标准方法是将userdata'抽象化，然后使用with类型约束将其特殊化[ 10，§8.7]。 不幸的是，ObjectiveCaml的签名语言没有提供一个with类型约束来命名函子的参数。为了解决这个限制，我们引入了另一层嵌套和一个新的类型构造函数userdata2模块类型USERCODE =sigtype模块M：functor（C： CORE，类型为->sig val init：C.V.state->unit end端给定这个定义，我们可以写一个签名，比如USERCODE，类型为“auserdata”=. 并确保适当地约束函子参数C。这样的约束出现在MakeEval函子的声明中，我们在这里重复：模块MakeEval（T：USERTYPE）（C：USERCODE，类型为：类型为“a Value.userdata”=“a T.t”的查询器手写代码模块不太可能直接实现USERCODE。相反，它可能取决于特定 的 观 点 。 因 为 这 样 的 模 块 接 受 一 个 或 多 个 视 图 并 返 回 一 个 与USERCODE匹配的模块，所以我们称之为应用前USERCODE代码模块建立两个类型标识：• 视图• 视图作为一个例子，这里是Lua-ML I/O库接口的概要。它提供了一个特定于应用程序的类型type'a t = In of in_channel| out_channel模块T：USERTYPE，类型为 “ a t = ” a t模块Make（TV： TYPEVIEW，类型为：USERCODEwith type[2]为了消除这一限制，[25]提出了一些对Camls i g n a t u r e l a n g u e的扩展。198N. Ramsey/Electronic Notes in Theoretical Computer Science 148（2006）181像类型模块一样，代码模块可以组成：模块合并：sig...模块C2（C1：用户代码）（C2：USERCODE，类型为：USERCODEwith type端代码模块只有在它们共享一个用户数据定义时才能组合4、把一切放在一起Lua-ML每个库都在与签名USERTYPE匹配的类型模块中定义其特定于应用程序的类型。每个库都在一个代码模块中定义它的代码，通常是一个匹配BARECODE的结构，或者是一个接受匹配TYPEVIEW的参数并产生匹配USERCODE的结果的函子。类型模块和代码模块都可以单独编译。一旦编写了库，通常最简单的是编写一个单独的“链接模块”来组合库并构建解释器。这样的模块具有程式化的结构：1. 使用Combine.T2组合类型模块，并调用结果T。 对于使用两个以上类型模块的解释器，Lua-ML实际上提供了多达10个的Combine.T函子，这有两个好处：在源代码中，组合多个类型需要更少的符号，并且在运行时，在嵌入和投影的实现中有更少的分配和指针追逐。2. 从匹配COMBINEDTYPE的T中，提取并重命名匹配TYPEVIEW的每个子模块. 这一步并不是绝对必要的，但是子模块有类似T.TV4的名称，重命名它们可以使后续代码使用更可读的名称。3. 安排代码模块在它们之间（以及与T.t）就用户数据的定义达成一致。协议是通过专门化每个代码模块来安排的，以便与T一起工作：• 在USERCODE之前的代码模块应用于步骤2中的相关视图。• 匹配BARECODE的代码模块通过应用WithType（T）函子与T相关联：Module WithType（T：USERTYPE）（C：BARECODE）：USE