学习 FC++:C++ 函数编程库

使用 FC++ 实现基本的函数编程

C++ 常常被视为面向对象编程 (OOP) 的同义词,流行的技术文献在很大程度上加强了这种认识。本文尝试讨论 C++ 的不同方面 — 通过 Yannis Smaragdakis 和 Brian McNamara 提供的开放源码 FC++ 库用 C++ 实现函数编程。学习如何使用 FC++ 实现基本的函数编程。

Arpan Sen, 独立作家

Arpan Sen 是致力于电子设计自动化行业的软件开发首席工程师。他使用各种 UNIX 版本(包括 Solaris、SunOS、HP-UX、IRIX,以及 Linux 和 Microsoft Windows)已经多年。他热衷于各种软件性能优化技术、图论和并行计算。Arpan 获得了软件系统硕士学位。



2010 年 10 月 25 日

为什么要实现函数编程,尤其是使用 FC++ 实现?

与 OOP 等其他编程模型相比,函数编程具有一些优点:

  • 代码简洁
  • 编程没有副作用(没有通过 set/get 例程操纵的全局/静态变量)
  • 可以进行快速的原型设计
  • FC++ 提供大量语法和库函数,帮助 Haskell 程序员顺利完成转换

通过使用库您并不能回避 C++ 本身没有任何函数编程构造这一事实。FC++ 是最好的基于 C++ 的函数编程库开放源码实现,可以把它插入遗留的 C++ 代码中。BSFC++ 等项目中已经使用了 FC++,BSFC++ 是一个用 C++ 进行函数大规模同步并行编程的库。


下载和安装

可以从 SourceForge 下载 FC++(见 参考资料)。解压压缩的安装文件 (.zip) 会产生一组头文件。只需在用户应用程序源代码中包含 prelude.h 头文件,就可以开始使用 FC++。清单 1 说明如何编译使用 FC++ 代码的源代码。注意,这是依赖于头文件的安装,不涉及其他库。

清单 1. 编译使用 FC++ 代码的源代码
g++ user_source1.cpp –I<path to FC++ installation>

注意:本文中的所有代码已经用 FC++ 1.5 和 g++ 3.4.4 测试过。


理解 CFunType

函数编程模型允许函数接受其他函数作为参数。显然,基本的 C/C++ 不允许这种语法。为了解决这个问题,FC++ 函数表示为符合特定编码约定的类的实例,这就是 CFunType 发挥作用的地方。C++ 函数对象的特征是在类定义中有 operator ( )清单 2 给出一个示例。

清单 2. C++ 函数对象的典型用法
struct square { 
   int operator( ) (int x) { return x * x; } 
};

square sqr1;
int result = sqr1(5);

清单 2 中的实现的问题在于,准确地说,sqr1 的函数类型是 int —> int,但是 sqr1 的 C++ 类型是 struct square。FC++ 引入了模板 CFunType,使用它对类型签名信息进行编码。CFunType 的最后一个参数是函数的返回类型,其他参数是输入类型信息,其次序与函数原型中的次序相同。清单 3 说明如何使用 CFunType 对 square 函数进行编码。

清单 3. 使用 CFunType 对求平方操作的函数签名进行编码
#include "prelude.h"

struct square : public CFunType<int, int> { 
   int operator( ) (int x) { return x * x; } 
};

square sqr1;
int result = sqr1(5);

清单 4 是另一个示例,它在列表中插入一个整数并返回更新后的列表。

清单 4. 使用 CFunType 对列表操作的函数签名进行编码
#include "prelude.h"

struct Insert : public CFunType<int,List<int>,List<int> > {
   List<int> operator()( int x, const List<int>& l ) const {
    // code for determining where to insert the data goes here
}

注意:清单 4 中的 List 数据类型是预定义的 FC++ 类型。


把函数转换为对象

为了让函数接受函数作为输入参数,必须把函数转换为对象。FC++ 在 CFunTypeptr_to_fun 例程的基础上定义 FunN 类别的类,由 ptr_to_fun 例程实际执行转换。请看一下 清单 5

清单 5. 使用 ptr_to_fun 把函数转换为 FC++ 函数对象
int multiply(int m, int n) { return m*n; }

Fun2<int, int, int> mult1 = ptr_to_fun (&multiply);
int result = mult1(8, 9); 

// result equals 72

CFunType 一样,Fun2 的签名暗示这个对象代表一个函数,此函数接受两个整数输入并返回一个整数。同样,Fun3<int, double, double, string> 代表的函数接受一个整数和两个双精度数,返回一个字符串。


列表和惰性

列表操作是函数编程的核心。FC++ 定义了自己的列表数据类型,它不同于 Standard Template Library (STL) 列表。FC++ 列表是惰性的。可以在 FC++ 中创建包含无限多元素的列表,但是只在需要时计算这些元素。清单 6 说明其意义。

清单 6. 定义和使用惰性列表
List<int> numbers = enumFrom (33);
List<int> even_and_greater_than_33 = filter (even, numbers);
assert (take(4, even_and_greater_than_33)) = list_with (34, 36, 38, 40);

enumFromfiltereventakelist_with 是 FC++ 中预定义的函数。在清单 6 中,enumFrom 返回一个从 33 开始的无限数字列表。filter 例程返回另一个无限列表,其中的数字是大于 33 的偶数。最后,take 例程实际上从这个列表中提取出前 4 个元素。显然,列表实际上不会存储无限多的数字 — 只在需要时计算元素。

表 1 说明 FC++ 列表常用的一些函数。

表 1. 与 FC++ 列表结合使用的函数
函数说明
head(<list>)返回列表的第一个元素
tail(<list>)返回一个列表,其中的元素与 <list> 相同,但是不包含第一个元素
cons(<element >, <list>)返回一个列表,其中的元素与 <list> 相同,但是在最前面添加了 <element>
NIL表示空列表
list_with(<element1, element2>, , <elementN>)创建一个包含 N 个元素的列表
enumFrom(<element1>)创建一个从 element1 开始的无限列表
compose(<func1>, <func2>)compose (f, g) 相当于 f(g(x)),其中的 f(x) 和 g(x) 是两个函数
filter(<func1>, <list>)返回使用 <func1> 函数筛选 <list> 所获得的元素列表
take(<N>, <list>)返回包含 <list> 中前 N 个元素的列表
map(<function>, <list>)把第一个 <function> 函数应用于第一个 <list> 的每个元素

清单 7 中的示例说明如何创建和显示列表的内容。

清单 7. 创建列表、检查列表内容并显示数据
#include <iostream>
#include "prelude.h"

int main( ) 
{
int x=1, y=2, z=3;
List<int> li = cons(x,cons(y,cons(z,NIL)));

// head also removes the 1st element from the list
assert( head(li) == 1 );

// tail returns whatever is left of in the list, and list_with is
// used to define small sized list
assert( tail(li) == list_with(2,3) );

 while( li ) {
      std::cout << li.head() << " ";
      li = li.tail();
 }
return 0;
}

注意:在创建 li 列表时,cons 在一个列表的前面添加元素;通过依次添加 z、y 和 x 创建最终的列表。


更快的列表实现

FC++ 1.5 提供 List 数据结构的另一种变体,它称为 OddList,在 list.h 中定义。OddList 的接口与 List 完全相同,但是它更快。所有对 List 进行操作的 FC++ 例程也适用于 OddListOddList 的效率高是由于它缓存列表中的下一个节点。清单 8 演示 OddList 的一些比较微妙的用法。

清单 8. 比较微妙的 OddList 用法
OddList<int> odd1 = enumFrom (1);
List<int> list1 = odd1.tail ( ); // always returns List<int>!!

OddList<int> odd2 = enumFrom (1);
List<int> list2 = odd2.delay ( ); // create a List<int> with same data as odd2

List<int> list3 = enumFrom (1);
OddList<int> odd3 = list3.force ( ); // creates an OddList<int> with same data as list3

OddList 不支持适用于 List 的 STL 式迭代器。关于 OddList 实现的详细信息见 参考资料


创建自己的筛选器

如果希望在 清单 6 中创建自己的筛选器(例如所有能够被 100 整除的大于 33 的数字),那么只需定义自己的筛选函数,然后调用 ptr_to_fun 把它转换为函数对象。清单 9 说明具体做法。

清单 9. 创建自己的筛选器
bool div_by_100 (int n) { 
  return n % 100 ? false : true;
}

List<int> num = enumFrom(34);
List<int> my_nums = filter( ptr_to_fun(&div_by_100), num);

注意,FC++ Listfilter 在本质上是完全泛化的,可以适用于任何数据类型。

接下来,讨论两种基本的函数技术:currying 和合成。


currying

currying 这种函数编程技术把某一函数的一部分参数绑定到固定的值,由此创建新函数。清单 10 中的示例对 f 函数执行 currying。

清单 10. 使用 currying 创建新函数
int multiply(int m, int n) { return m * n; }
Fun2<int, int, int> f2 = ptr_to_fun (&multiply);
Fun1<int, int> f1 = curry2 (f2, 9);

std::cout << f1(4) << std::endl; // equivalent to multiply(9, 4)

Fun1<int, int> f1_implicit = f2(9); 
std::cout << f1_implicit(4) << std::endl; // same as f1(4)

预定义的 curry2 例程把 f2 的第一个参数绑定到 9。FC++ 1.5 提供 curry1curry2curry3 操作符,它们把前 N 个参数绑定到特定的值。另外,FC++ 还定义绑定例程,它们通过预先固定现有函数的特定参数的值来创建新函数。例如,bind2and3of3 (f, 8, 9) 相当于 f(x, 8, 9),其中的 f(x, y, z) 是有 3 个输入参数的函数。另一种对参数进行特化的方式是使用下划线 (_)。例如,greater (_, 10) 相当于 f(x) = (x > 10)。注意,greater 是 FC++ 中预定义的。清单 11 给出一些 currying 示例。

清单 11. 更多 currying 示例
List<int> integers = enumFrom (1); 
List<int> int_gt_100 = filter(greater(_, 100), integers);

// This list will add 3 to all elements of integers. 
List<int> plus_3 = map (plus(3), integers);

清单 12 中的代码片段显示一个数字的所有因子,包括这个数字本身。

清单 12. 显示一个数字的所有因子
#include "prelude.h"
using namespace fcpp;

#include <iostream>
using namespace std;

bool divisible( int x, int y ) { return x%y==0; }

struct Factors : public CFunType<int,OddList<int> > {
    OddList<int> operator()( int x ) const {
        return filter( curry2(ptr_to_fun(&divisible),x), enumFromTo(1,x) );
    }
} factors;

int main()
{
  OddList<int> odd = factors(20);
  while (odd) { 
      cout << head(odd) << endl;
      odd = tail(odd);
  }
  return 0;
}

理解清单 12 的关键是这一行:return filter( curry2(divisible,x), enumFromTo(1,x) );。这为 enumFrom(1, 20) 返回的列表创建一个筛选器,让 20 能够整除的所有数字成为最终列表的一部分。curry2 例程把 20 绑定到 divisible 函数的第一个参数。注意,ptr_to_fundivisible 转换为函数对象,这样就可以把它作为参数传递给 curry2


合成

函数编程通过组合现有代码创建新功能。compose ( ) 操作符把两个一元函数 f(x)g(x) 组合成新函数 h(x),h(x) 相当于 f(g(x))。例如,compose (head, tail) 返回列表中的第二个元素。这是真正意义上的函数编程;g(x) 作为 f(x) 的参数。取自 "Functional Programming with the FC++ Library" 的 清单 13(见 参考资料)是一个使用合成的示例。

清单 13. 使用 composetail 获取列表的第二个元素
std::string s="foo", t="bar", u="qux";
List<std::string> ls = cons(s, cons(t, cons(u, NIL)));

ls = compose(tail, tail) (ls); // tail(tail(ls));
assert (head(ls) == "qux"); // s, t are removed

清单 14 中的示例让列表的所有元素递增 2。

清单 14. 使用 compose 递增列表元素
List<int> integers = enumFrom (1); 
map (compose(inc, inc), integers);
// this modifies integers to an infinite list [3, 4, 5 ...]

lambda 函数

讨论函数编程就不能不提到 lambda 函数。lambda 抽象用来定义匿名函数。在不希望为小代码段定义单独的函数的情况下,可以使用这种技术。要想在代码中使用 lambda 功能,需要定义 FCPP_ENABLE_LAMBDA 宏。清单 15 从现有代码简便地定义新的数学和逻辑函数。请注意定义 factorial 的方式。

清单 15. 定义 lambda 函数
// a new function where f(x) = 3*x+1
lambda(X)[ plus[multiplies[3,X],1] ]  
   
// a new function where f(x) = x! (factorial x)
lambda(X)[ l_if[equal[X,0],1,multiplies[X,SELF[minus[X,1]]]] ]

清单 15 中的代码的意义很明确。plusmultiplies 等例程是在 FC++ 库中定义的,使用 lambda 操作符从现有代码创建新功能。


结束语

FC++ 提供:

  • CFunType 类型的对象,可以通过扩展它轻松地满足函数编程的需要
  • 惰性列表的实现,其中可以容纳数量无限的元素
  • headtailmapfilterptr_to_fun 等函数编程操作符
  • 使用 currying 操作符、lambdacompose 从现有函数创建新函数的能力

FC++ 惟一的缺点可能是缺少描述头文件中定义的函数的标准化文档。本文介绍了最有用的一些函数:composecurrybindtakemapptr_to_funfilter

参考资料

学习

获得产品和技术

  • 下载 FC++
  • 下载 FC++ client,进一步了解其工作方式。
  • 以最适合您的方式 评估 IBM 产品:下载产品试用版,在线试用产品,在云环境下试用产品,或者在 SOA Sandbox 中花费几个小时来学习如何高效地实现 Service Oriented Architecture。

讨论

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=AIX and UNIX, Linux
ArticleID=555996
ArticleTitle=学习 FC++:C++ 函数编程库
publish-date=10252010