C++模板元编程：函数式编程在C++中的应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记279（3）（2011）27-40www.elsevier.com/locate/entcsC++模板元程序A'belSinkovics埃奥特维奥斯·洛兰德大学编程语言与语言学系布达佩斯，匈牙利电子邮件：abel@elte.hu摘要越来越多的C++应用程序通过使用基于模板元程序的库来直接或间接地使用模板元程序由于C++模板元程序遵循函数式范式，因此函数式编程的知名和广泛使用的工具也应该可用于C++模板元程序的开发人员许多函数式语言都支持let表达式来将表达式绑定到本地名称它简化了源代码，减少了重复，避免了命名空间的污染。在本文中，我们提出了如何让表达式可以在C++模板元程序。我们还展示了如何使用let表达式来实现lambda表达式。Boost元编程库为模板元程序提供了lambda表达式，我们展示了嵌套lambda表达式的局限性，以及我们的实现如何处理这些情况。保留字：C++，boost：：mpl，模板元编程，函数式编程1引言Let表达式是函数式编程语言中的常用工具。它们的目的是在另一个表达式的作用域中给表达式命名。例如，在Haskell [19]中，让表达式看起来像这样：让{ d1;... ;dn } in e其中d1，...，dn是e表达式范围内的声明模板被设计为在运行时捕获抽象的共性而不会导致性能损失，然而在1994年，Erwin Unruh展示了它们如何强制任何标准C++编译器执行特定算法作为副作用的汇编过程。这种模板的应用被称为C++模板元编程，它形成了C++的图灵完备子语言。[3]第一章模板元编程如今有许多应用领域，如实现表达式模板[15]、静态接口检查[6，9]、活动库[16]或1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.03628×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）domain specific language embedding[4，17，8，18].C++模板元程序是函数式程序[7，11]。不幸的是，它们有一个复杂的语法，导致程序难以编写和理解。模板元程序由模板元函数组成[1]。在元函数的主体中可能有多次使用的子表达式，这些子表达式必须被复制，从而导致维护问题，或者被移动到新的元函数，从而导致名称空间污染。将表达式绑定到元函数中的本地名称的能力可以简化C++模板元程序的开发和维护。许多编程语言都提供了在表达式中创建无名称函数对象的工具。这些工具被称为lambda表达式，通过使用它们，程序员在需要简单实现的函数对象时不必创建小的实用函数。在当前的C++标准中没有lambda表达式支持，但是有一些作为库实现的解决方法。Boost的Phoenix和Lambda库提供了构建lambda表达式的工具[17]。即将到来的标准C++0x [13]支持lambda表达式。没有lambda表达式，业务逻辑分散在许多小的实用程序函数中，使代码难以理解和更改。Boost元编程库[17]提供了为编译时执行的算法构建lambda表达式的工具。lambda表达式的参数称为1、2等，这会导致程序员必须在其他lambda表达式中创建嵌套的lambda表达式时出现问题。我们提出的let表达式的解决方案基于这里提出的思想实现的库可以在[18]中找到论文的其余部分组织如下。 在第2节中，我们详细介绍了let表达式的概念。在第3节中，我们介绍了将let表达式添加到函数式语言的方法，函数式语言没有内置的支持。4我们介绍了如何使用我们的方法来实现嵌套的lambda表达式。在第5节中，我们扩展了我们的方法来支持递归let表达式。我们在第6节中介绍了未来的工作，我们在第7节中总结了我们的结果。2Let表达式让Haskell中的表达式将声明绑定到名称。声明可以使用模式匹配将值绑定到名称，例如：让a =f 11（b，c）=return元组13ina + b + c上面的示例将表达式f11绑定到a。它计算返回元组13并尝试将其结果与模式（b，c）匹配。 如果×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）29它产生一个错误。声明可以是递归的，因此我们可以在让块。举例来说：让fact=\n ->ifn == 0 then1 else（n*（fact（n - 1）in事实3上面的例子在表达式fact的作用域中定义了一个阶乘函数3 .第三章。事实的定义指的是事实本身。有些语言不允许let表达式中的递归这些语言为递归提供了一个letrec结构Common Lisp [12]也支持let表达式。 它们看起来如下：(let（（ ）.（ ）））它创建名为，.，，值为，...，in.我们的实现遵循以下构造的语义设 = e1>in我们将绑定<到e2>作用域中的。 我们<<我们提供了另一种递归构造let表达式：letrec = e1> inletrec支持递归名称绑定，因此也在自身的作用域中绑定到我们计算e1，我们懒惰地绑定到名称的表达式。它在第一次使用时进行评估。当它不被使用时，它3let的实现大多数支持let表达式的函数式语言都在语言中内置了对它们的支持这些构造是语言的一部分，编译器必须处理它们。模板元编程不是C++的设计目标，并且没有编译器支持let表达式等构造。在本节中，我们将介绍如何仅使用标准C++特性添加let表达式我们定义的let表达式可以实现为lambda表达式[5]。设a = e1在e2中等价于（\a -> e2）e1。 Boost元程序库提供了构建lambda表达式的工具，但是参数的名称是固定的，它们必须是1，2等，因此通过使用lambda表达式我们只能绑定到这些名称。让表达式必须能够绑定到任意名称，因此我们不能使用Boost库提供的lambda表达式。30×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）空值元函数[1]是一个可以在没有额外参数的情况下计算的元函数。我们可以将元函数看作是一段可执行代码。一个空值元函数可以从任何元函数中创建，方法是向它传递所需数量的参数，但不计算它。例如：//带有两个参数的元函数模板classa，class b>struct f： boost：：mpl：：plus_a，b>{};//空元函数typedef f boost：：mpl：：int_0>，boost：：mpl：：int_1> >空值元函数;//计算空值元函数typedefnullary_metafunction：：类型evaluated_nullary_metafunction;上面的代码演示了向元函数传递参数和对其求值是两个独立的步骤。在模板元程序中使用let表达式，我们应该能够表达如下内容：template class n> structmy_metafunction：让x = boost：：mpl：：plus n，boost：：mpl：：int_13>>在boost：：mpl：：times x，x>{};在上面的例子中，我们将boost：：mpl：：plus n，boost：：mpl：：int 13>>绑定到boost：：mpl：：times x，x>域中的名称x。我们绑定的表达式和我们在其作用域中进行绑定的表达式都是C++类，因此它们可以是模板元函数的参数。我们可以声明一个空类x来表示名称x，所以它也可以是元函数的参数：struct x;现在我们例子中的所有元素都是C++类，我们可以创建一个实现let表达式语义的这个元函数可以通过以下方式使用：template class n>structmy_metafunction：让 >，boost：：mpl：：times x，x>>：：type {};×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）31信函签名如下：模板class a，class e1，classe2>structlet;这个元功能需要• a，要绑定到• e1，绑定表达式• e2，表达式绑定的范围作为论据。它将e1绑定到e2作用域中的a。由于我们这样做的结果是一个新的空元函数，它的行为就像它是具有新绑定规则的原始代码一样let是一个模板元函数，它的结果是替换表达式。例如设x，boost：：mpl：：int_13>，boost：：mpl：：plus x，联系我们是一个空元函数，然而设x，boost：：mpl：：int_13>，boost：：mpl：：plus x，x>>：：type是boost：：mpl：：plus boost：：mpl：：int<13>，boost：：mpl：：int<13>>.为了实现let，我们需要一个helper元函数，让impl具有相同的签名：模板class a，class e1，class e2> structlet_impl;此元函数的前提是e2永远不会与a相同，因此让impl永远不会用要替换的名称作为其参数实例化LETIMPL可以使用模式匹配来实现。它的一般版本涵盖了在e2中没有替代品的情况：template class a，class e1，classe2>struct let_impl：id e2> {};注意，我们在这里使用了一个辅助元函数id它实现了身份Meta函数：模板类x>struct id {typedef x type;};由于使用了id，替换的表达式是let<。>：：type. 这种类型一个typedef，因此只有一个新的名称的替代表达式。通过不使用id，let的用户不必访问嵌套类型type。letimpl的一般情况的实现将是template class a，class e1，classe2>struct let_impl：e2 {};问题是，让<。.............................>wouldn'tbeatypedefofthe substantiated32×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）表情当一个模板被特殊化为一个类型时，它就不是特殊化为该类型的子类。[14]例如：structB {};structD：B {};template classT> structTemplateClass {};template>struct TemplateClass B>{};模板类B> usesSpecialisation;模板类D>usesGeneralCase;当我们将B的类模板专门化为它的参数类型时，专门化在模板类以B作为其参数实例化时使用。但是当它用B的子类D实例化时由于模板元程序中的模式匹配是使用专门化实现的[7]，元函数不应该返回结果的子类，而应该返回结果本身。这就是为什么在let的实现中使用id很重要的原因。我们已经介绍了let impl的一般情况，它几乎涵盖了所有的情况。它唯一没有覆盖的结构是模板类的实例。它们实现元函数调用。 实例化模板时使用的参数是传递给元函数的参数。它们可以通过使用模板参数来覆盖[14]。例如，接受一个参数的模板类的实例可以由let impl的以下专门化所涵盖：template classa， class e1，template class> classt， class a1>struct let_impl a，e1，t a1>>：id t types let a，e1，a1>：：type>>{};我们递归地在模板参数上应用let。递归处理确保了也为元函数参数模拟名称绑定可以用类似的专门化来覆盖接受两个、三个等参数的模板类。这些情况可以使用Boost预处理器库自动生成[17]，由于空间问题，我们它在我们的实现中可用[18]。我们将使用可变模板而不是预处理器库来实现它作为未来的工作。我们用let来处理模板元程序，因此我们可以假设模板类的参数总是类。带有整数参数的模板类只需要实现装箱，let只需要处理装箱的值，这在let impl的一般情况下都有涉及。现在我们已经完成了letimpl，我们也可以实现let。我们可以使用模式匹配。一般情况如下：模板类a，类e1，类e2>×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）33结构let：let_impl a，e1，e2>{};请注意，我们将调用转发到我们刚刚实现的helper元函数它涵盖了所有情况，除了e2与a相同的情况。我们可以用let的专门化来覆盖它：template class a，classe1>struct let a，e1，a>：id e1>{};这种情况下，let表达式绑定到的名称将替换为绑定到该名称的表达式。Haskell支持隐藏在let表达式中定义的名称。下面的表达式的值是35。让X = 11在x +（设 x = 13， x +11）外部let表达式将11绑定到x，但内部let表达式隐藏x，在内部let表达式的主体中，x被绑定到13。我们也应该在C++模板元程序中处理这些情况。上面的例子在C++模板元程序中看起来如下：让，boost：：mpl：：plus，boost：：mpl：：plus x，boost：：mpl：：int_11>>>>>到目前为止，我们定义的let函数将在整个表达式中用11代替x，包括内部let。它将评价以下方面：boost：：mpl：：plusboost：：mpl：：int_11>，让，boost：：mpl：：int_13>，boost：：mpl：：plus，boost：：mpl：：int_11>>>>然后，内部let将用13代替11，这不是我们所期望的34×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）从最初的表达。let的实现在到达另一个绑定相同名称的let时必须停止替换绑定的名称。它可以通过添加以下let impl的专门化来实现：模板class a，class e1，class e1a，class e2>结构let_impl a，e1，let a，e1a，e2>>：id let a，e1a，e2> >{};由于模板类的实例化规则[2]，当一个嵌套的let绑定到相同的名称时，编译器实例化这个专门化，并停止用外部let定义的值替换绑定的名称。它让内部let保持不求值，以支持惰性求值。使用letimpl而不是将每个专业化都添加到let中是很重要的。通过不使用letimpl和覆盖所有情况作为专业化，让一些情况变得模棱两可。对绑定到的名称没有限制，它可以是任何类。因此，它也可以是模板类的实例。使用模板类的实例作为名称会导致模棱两可的情况：编译器通过在两个单独的元函数中处理它们，这两个模式我们所介绍的专业涵盖了所有情况，let的实施现已完成。它通过用要绑定到的值替换要绑定4嵌套Lambda表达式不管我们使用哪种编程语言，我们在开发中使用的泛型函数越多，我们就越需要小的实用函子来实现泛型算法的自定义逻辑。考虑std：：transform或其等效元编程boost：：mpl：：transform。这两个函数都会改变序列中的每个元素。 它们将改变一个元素的函子作为参数，并将其应用于序列的所有元素。 我们可以在许多地方使用这个函数和许多其他类似的函数，但是我们需要提供实现自定义位的小实用函数，例如序列中一个元素的转换。这些小函数包含应用程序的业务逻辑。通过将它们实现为实用函数，我们将业务逻辑的位移动到源代码的不同位置。Lambda函数为这个问题提供了一个解决方案。它是一种在代码段中间就地实现小型实用函子的技术。这些函数没有名字，除非我们将它们存储在变量中。这个解决方案使得实现泛型算法的函子成为可能。当开发人员在复杂的情况下使用泛型函数时，他们需要将复杂的函子构造为lambda表达式。复杂的lambda表达式可以包含嵌套的lambda表达式。假设我们有以下数据结构：typedef boost：：mpl：：list<×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）35boost：：mpl：：list_c int，1，2>，boost：：mpl：：list_c int，三、>list_in_list;我们我们可以用boost：：mpl：：lambda实现它，如下所示：boost：：mpl：：transformlist_in_list， boost：：mpl：：lambda>>>：：type>>：：type>：：type我们需要在外部和内部lambda表达式中使用boost：：mpl：：1也实现它是可能的，但它使理解代码更加困难，因为boost：：mpl：：1的出现涉及不同的事情。考虑另一个例子：使用transform将长度添加到每个元素它所处的名单。预期结果是：typedef boost：：mpl：：list，//长度为2boost：：mpl：：list_c int，4>//长度为1>result_of_second_example;在这种情况下，我们需要在内部lambda表达式中使用外部lambda表达式的参数如果我们使用Boost元编程库提供的lambda表达式，我们可以只使用变通方法。内部lambda表达式必须接受两个参数：外部表达式的参数值我们需要使用 一 些 currying 解 决 方 案 [10] 来 隐 藏 第 一 个 参 数 ， 并 使 其 与 通 用 算 法transform一起工作。考虑到这种解决方案的复杂性，开发人员很可能会创建一些小的帮助函数，这就避免了将业务逻辑放在源代码的不同位置的问题我们在本文中介绍的let绑定方法可以用于在C++模板元编程中实现lambda表达式。下面的元函数类使用let实现了一个参数的lambda表达式：template class arg，class f>structlambda{36×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）template class t>struct apply： let arg，t，f>：：type {};};它是一个元函数类[1]，以参数的名称和lambda表达式的主体作为参数。当一个参数应用于元函数类时，它使用let将参数绑定到主体中的名称。我们离开它的扩展，以支持一个以上的论点作为未来的工作。使用lambda，上面的例子可以通过以下方式实现：boost：：mpl：：transformlist_in_list，lambda nested_list，boost：：mpl：：transformnested_list，lambda i，boost：：mpl：：plus i，boost：：mpl：：sizenested_list>>>>>>>>>>：：type此解决方案利用了名称绑定在整个主体中生效的事实Lambda表达式，包括内部Lambda表达式。我们可以在内部lambda表达式中使用外部lambda表达式的参数，因此使用我们的lambda实用程序解决第二个示例是一个微不足道的任务我们可以给lambda参数起有意义的名字，也可以在不同的嵌套层次上使用不同的名字我们介绍的绑定机制也将值绑定到嵌套lambda表达式中的名称，因此在内部lambda表达式中使用外部lambda表达式的参数很简单。5递归let表达式到目前为止，我们已经介绍了如何在C++模板元编程中实现非递归let表达式和高级lambda在本节中，我们将介绍如何支持递归let表达式考虑以下示例，该示例将实现阶乘的高阶函数绑定到表达式中的名称factboost：：mpl：：apply fact，boost：：mpl：：int<3>>：让事实，λ n，boost：：mpl：：eval_if >，boost：：mpl：：int_1>，boost：：mpl：：times boost：：mpl：：apply fact，boost：：mpl：：minus n，boost：：mpl：：int_1>，n>，boost：：mpl：：apply fact，boost：：mpl：：int_3>>> >×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）37上面的代码let让Haskell中的表达式支持递归。let表达式不支持递归的语言通常提供let表达式的递归版本，通常称为letrec。我们遵循这种方法，并单独实现递归版本，在其实现中使用非递归版本。我们称之为let letrec的递归版本。letrec的声明如下：模板class a，class e1，classe2> structletrec;我们需要将e1绑定到e1作用域中的a，并将我们得到的表达式绑定到e2作用域中的a。下面的代码可以做到这一点：模板类a，类e1，类e2>struct letrec： let a，let a，e1，e1>，e2>{};这个实现的问题是，我们在e1的作用域中绑定到a的表达式e1因此，我们也需要在e1的作用域中递归地将e1绑定到a模板类a，类e1，类e2>结构letrec： let a，letrec a，e1，e1>，e2>{};上面的代码递归地使用letrec来实现表达式e1到表达式e1本身中的名称a的递归绑定。由于绑定是延迟进行的，因此只有当e1使用名称a时才会发生递归。当e1不使用名称a时，letrec不会再次求值，递归停止。我们得到一个表达式作为这个递归绑定的结果。 这是我们在e2作用域中绑定到名称a的表达式。由于我们没有将e2绑定到任何名称，因此在这一步我们不需要递归绑定，因此我们可以使用let。使用letrec我们可以实现阶乘示例：letrec fact，lambda n，boost：：mpl：：eval_if >，boost：：mpl：：int_1>，boost：：mpl：：timesboost：：mpl：：apply<事实上，boost：：mpl：：minus n，boost：：mpl：：int_1>>>，n>，boost：：mpl：：apply fact，boost：：mpl：：int_3>>> >letrec将factorial函数的递归实现绑定到名称在函数的作用域中，它也是有效的。然而，我们严重依赖于38×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）惰性求值，因此我们需要确保我们在factorial函数体中使用的所有函数都惰性地计算其参数boost库提供的函数期望急切地评估参数[10]，因此我们需要用延迟评估参数的代码包装它们，然后调用来自Boost库的函数。template classf， classx>struct lazy_apply：boost：：mpl：：apply typeValue，x>{};模板class a，classb> structlazy_equal_to：boost：：mpl：：equal_to typa：：type，typb：：type>{};模板class a，classb> structlazy_times：boost：：mpl：：times类型a：：type，类型b：：type>{};让<事实，lambda >，boost：：mpl：：int_1>，lazy_timeslazy_apply<事实上，boost：：mpl：：minus n，boost：：mpl：：int_1>>>，n>>>，lazy_apply事实，boost：：mpl：：int_3>>>这最终是我们阶乘示例的一个工作版本，它只使用惰性Meta函数。我们将创建一个通用的包装器，使Boost库的所有函数都是惰性的，作为未来的工作。6未来的作品我们已经看到，这个解决方案支持将值绑定到模板元程序中的名称。到目前为止，这个名称一直是一个名称文字，我们通过创建一个具有该名称的空类在系统中引入了它。由于这种解决方案发生在元编程执行时并使用模式匹配，×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）39要实现绑定，我们不仅限于绑定到名称。我们可以绑定到任何类或模板类的实例，包括空模板元函数。因此，我们可以将新代码绑定到其他代码片段，并替换或修改现有元函数的位。该技术使得在C++模板元编程中不使用外部织入工具就能支持面向方面编程成为可能。我们把它作为未来的工作。7总结Let表达式是许多函数式编程语言的基本构建块之一，如Haskell，Lisp等。我们已经展示了对表达式的支持可以添加到C++模板元编程中，这是一种没有内置支持的函数式语言。我们还展示了如何使用let表达式来添加对lambda表达式的支持。我们已经构建了一个支持lambda表达式和let表达式的库，用于C++模板元编程[18]。使用我们的let解决方案，可以实现Boost元编程库的根本改进我们已经证明，按照本文中提出的方法构建的lambda表达式也可以处理嵌套的lambda表达式引用[1] D. Abrahams，A. C++ template metaprogramming，Concepts ，Tools，and Techniques from Boostand Beyond，Addison-Wesley，Boston，2004.[2] ANSI/ISO C++委员会，编程语言[3] K. 恰 尔 内 茨 基 湾 W. Eisenecker ， Generative Programming ： Methods ， Tools and Applications ，Addison-Wesley，2000.[4] Y. Gil，K. Lenz，Simple and Safe SQL Queries withC++ templates，Charles Consela和JuliaL. Lawall（eds），Generative Programming and Component Engineering，第六届国际会议，GPCE2007，奥地利萨尔茨堡，2007年10月1-3日，第1 - 3 -24页。[5] S. L. Peyton Jones，函数式语言的实现，Prentice Hall，1987，[445]，ISBN：0-13-453333-9 Pbk[6] B. McNamara，Y. Smaragdakis，C++中的静态接口，第一次C++模板元编程研讨会，2000年[7] Bartosz Milewski，Haskell和C++模板元编程http://bartoszmilewski.wordpress.com/2009/10/26/haskellc-video-and-slides[8] Zolt'anPorkol'ab ， A'belSinkovics ， Domain-specLlanguageIntegrationwithSpread-timeParserGeneratorLibrary ， In Proceedings of the Generative Programming and Component Engineering ， 9thInternational Conference，GPCE 2010，Eindhoven，The Netherlands，October 10-13，2010.[9] J. Siek，A.Lumsdaine，概念检查：C++中的绑定参数多态性，第一次C++模板元编程研讨会，2000年[10] A'belSinkovics，FunctionalextensionstotheBostMetaproprogramLibrary，InPorkolab，Pataki（Eds）Proceedings of the 2nd Workshop of Generative Technologies，WGT第56-[11] A' 。 我是受害者Z. Porkol'ab，ExpressingC++TemplateMetaprogramsasLambdaexpressions，在第十届函数式编程趋势研讨会上（TFPPieter Koopman，eds.），2009年6月2日至4日，斯洛伐克科马尔诺pp. 97-111[12] 盖湖Steele，Common Lisp the Language，2nd edition Digital Press，1990。ISBN：1-55558-041-6 Pbk40×。Sinkovics/Electronic Notes in Theoretical Computer Science 279（3）（2011）[13] B. Stroustrup，Evolving a Language in and for the Real World：C++，1991-2006。ACM HOPL-III.六月2007[14] D. Vandevoorde，N. M. Josuttis，C++模板：完整指南，Addison-Wesley，2003年。[15] T. Veldhuizen，表达式模板，C++报告vol.号75，1995，pp.26比31[16] T. Veldhuizen ， D. Gannon ， Active libraries ： Rethinking the roles of compilers and libraries ， InProceedings of the SIAM Workshop on Object Oriented Methods for Inter-operable Scientic andEngineering Computing（OO'98）. SIAM Press，1998 pp. 二十一至二十三岁[17] Boost编程库www.boost.org[18] mpllibs的源代码http://github.com/sabel83/mpllibs[19] Haskell 98语言和库修订的报告。http://www.haskell.org/onlinereport