2007-11-09

lambda之路...

DMD最近的版本号加入了闭包，感觉非常有用，虽然有些背后动作，不过我是实用派不介意这个。玩的时候忽然想到为什么没有lambda呢？AST还没影，不过可以利用D强大的模板可以使用字符串来先模拟一下。

我假想的语法是这样的： 
int[] arr = [1,2,3];
int[] arr1 = arr.map(lambda!("int x -> x * x"));


上面执行的arr1结果将会是[1,4,9]。

在编写过程中发现匿名委托不能够使用模板来这样生成： 
template labmda(string expr)
{
    auto lambda = mixin("(int x){return (x);}");
}

所以必须在使用的地方去mixin（如果你可以避免这个请告诉我），像这样的： 

int[] arr1 = arr.map(mixin("(int x){return (x);}"));

测试很长时间没有找到突破方法去掉这个mixin，所以就在这个起点上向目标前进了。

测试过程中也发现现在的模板对于字符串参数似乎不像以前那么友好了，编译期执行函数则得到了加强，所以使用它来实现： 
int indexof(string s, char ch)
{
	foreach(i, c; s)
		if(c == ch)
			return i;
	return -1;
}

int indexof(string s, string sub)
{
	for(int i=0; i<s.length-sub.length; i++)
	{
		if (s[i..i+sub.length] == sub)
			return i;
	}
	return -1;
}

string _RetType(string expr)
{
	int end = indexof(expr, '|');
	if (end == -1)
		return "";
	else
	{
		int end1 = indexof(expr, "->");
		assert(end1 > 0, "'->' not found in lambda expression: " ~ expr);

		if (end > end1) return "";

		return expr[0..end];
	}
}

string _ArgTypes(string expr)
{
	int start = indexof(expr, '|');

	int end = indexof(expr, "->");
	assert(end > 0, "'->' not found in lambda expression: " ~ expr);

	if (start > end) start = -1;

	return expr[start+1 .. end];
}

string _Body(string expr)
{
	int start = indexof(expr, "->");
	assert(start > 0 && start<expr.length-1, "'->' not found in lambda expression: " ~ expr);

	return expr[start+2 .. $];
}

string lambda(string expr)
{
	return
		"delegate " ~ _RetType(expr) ~ 
		"(" ~ _ArgTypes(expr) ~ "){return (" ~
		_Body(expr) ~ ");}";
}

它支持的lambda语法是这样的： 
//参数列表 -> 表达式：
int x -> x
int x, int y -> x * y

//返回值 | 参数列表 -> 表达式:
string | int x -> toString(x)

测试： 
T[] map(T,T1)(T1[] arr, T delegate(T1) dg)
{
	T[] result;
	result.length = arr.length;
	foreach(i, v; arr)
		result[i] = dg(v);
	return result;
}

void main()
{
	int[] arr = [1,2,3];
	// int[] arr1 = arr.map(int x -> x * x);
	int[] arr1 = arr.map(mixin(lambda("int x -> x * x")));
	writefln(arr1);

	string sep = ";\n";
	string[] arr2 = arr.map(mixin(lambda("string | int x -> toString(x) ~ sep")));
	writefln(arr2);
}

运行结果：
引用

[3 6 9]
[1;
2;
3;
]

语法罗嗦了一些，要是有AST宏不知道是否能简化一些。。

加一个例子： 
T1 inject(T,T1)(T[] arr, T1 init, T1 delegate(T1, T) dg)
{
	T1 value = init;
	foreach(e; arr)
		value = dg(value, e);
	return value;
}

void main()
{
	int[] arr = [1,2,3];

	// int total = arr.inject(0, (int sum, int elem) -> sum + elem);
	int total = arr.inject(0, mixin(lambda("int sum, int elem -> sum + elem")));
	writefln(total);
}


运行得到的结果是6.

对应的ruby代码： 
total = [1,2,3].inject(0){|sum, elem| sum + elem}


从这个例子的注释中可以看到，lambda的参数应该用括号包起来，和参数加以区别；而单参数的lambda则应该省掉括号让它更美观，我上面的解析部分还不包括括号的解析。
评论
qiezi 2007-11-10   回复
oldrev 写道
引用

这个好像是类型反推了，估计有点困难。

仔细想了一下，确实是不行，不过返回值类型确实是可以省略的。

返回值是可以省略，现在也支持，不过在D这种强类型系统里面，有时候需要明确指定返回类型来进行精确匹配，减少程序员犯错误的机会，比如： 
	char c = 'a';
	auto i = c & 0xff;
	writefln(typeid(typeof(i)));

新手很容易认为i是个char类型，实际上却是个int，所以可选的返回值类型我感觉是必要的。
oldrev 2007-11-10   回复
引用

这个好像是类型反推了，估计有点困难。

仔细想了一下，确实是不行，不过返回值类型确实是可以省略的。
引用

从函数里面返回delegate在D1。0上应该也是不安全的吧。

因为这个 delegate 无法触及任何作用域以外的东西，就跟递归调用一样。
qiezi 2007-11-10   回复
oldrev 写道
引用

qiezi

对了，你上面这种消除mixin的手法也只有在最新的DMD上才能进行吧，这是一个闭包而不是内嵌函数或委托量。

另外改用你这个版本以后，前两个用法都能通过，第三个有点问题：
代码

   1. string sep = ";\n"; 
   2. string[] arr2 = arr.map(lambda!("string | int x -> toString(x) ~ sep")); 
   3. writefln(arr2); 


编译无法通过，因为返回的闭包被包裹了一层，上下文已经不对了。


我的办法在 D 1.0 上也是可行的（GDC 0.24测试），附带的好处是可以防止1.0 的闭包问题，当然，定义处上下文是不能处理了。

D的delegate字面值允许省略返回值类型，所以 _RetType 也可以省掉了。

从函数里面返回delegate在D1。0上应该也是不安全的吧。
qiezi 2007-11-10   回复
oldrev 写道
可不可以再改进一下，允许省略参数类型和返回值类型，做到：
"x -> x*x"

这个好像是类型反推了，估计有点困难。如何从这个委托所处的上下文获得它应该成为的类型？
oldrev 2007-11-10   回复
引用

qiezi

对了，你上面这种消除mixin的手法也只有在最新的DMD上才能进行吧，这是一个闭包而不是内嵌函数或委托量。

另外改用你这个版本以后，前两个用法都能通过，第三个有点问题：
代码

   1. string sep = ";\n"; 
   2. string[] arr2 = arr.map(lambda!("string | int x -> toString(x) ~ sep")); 
   3. writefln(arr2); 


编译无法通过，因为返回的闭包被包裹了一层，上下文已经不对了。


我的办法在 D 1.0 上也是可行的（GDC 0.24测试），附带的好处是可以防止1.0 的闭包问题，当然，定义处上下文是不能处理了。

D的delegate字面值允许省略返回值类型，所以 _RetType 也可以省掉了。
oldrev 2007-11-10   回复
可不可以再改进一下，允许省略参数类型和返回值类型，做到：
"x -> x*x"
qiezi 2007-11-10   回复
修改了一下，现在支持这种用法：
	int[] arr = [1,2,3];
	int result = arr.inject(0, mixin(lambda("int r, int c -> r | c")));
	writefln(result);


"|" 在 "->" 后面。
oldrev 2007-11-10   回复
引用
# // 匹配 int | int x, int y -> x * y 
# macro(TYPE, "|", PARAM_LIST, "->", EXPR) 


这估计是不行的，语法分析阶段无法识别类型
qiezi 2007-11-10   回复
对了，你上面这种消除mixin的手法也只有在最新的DMD上才能进行吧，这是一个闭包而不是内嵌函数或委托量。

另外改用你这个版本以后，前两个用法都能通过，第三个有点问题： 
	string sep = ";\n";
	string[] arr2 = arr.map(lambda!("string | int x -> toString(x) ~ sep"));
	writefln(arr2);

编译无法通过，因为返回的闭包被包裹了一层，上下文已经不对了。
qiezi 2007-11-10   回复
对了，这个实验的初衷是看到邮件列表中有人对比D的闭包和其它语言的闭包语法，D虽然语法也够简炼了，不过比起来还是显得罗嗦，比如：
// ruby:
arr = [1,2,3]
total = arr.inject(0){|sum, elem| sum + elem}

// D:
int[] arr = [1,2,3]
int total = arr.inject(0, (int sum, int elem){return sum + elem;});

主要是丑在大括号这部分，小括号里面包着大括号感觉很怪。
qiezi 2007-11-10   回复
oldrev 写道
貌似 AST 宏也不是很难实现，我的设想是编译器遇到 AST 宏就把它记录到一张表里，并为宏里的代码生存一棵单独的 AST。当整个程序的代码都生成 AST 以后，再对代码 AST 进行模式匹配，然后把宏体内的 AST 嫁接上去就行了。

除了 The Future of D 里的演示外，应该再往前走一步，允许无名宏： 
macro("for_each", "(", value, "in", container, ")", body)
{
	auto iter = container.begin();
	for(; iter != container.end(); ++iter)
	{
		auto value = iter.value();
		body; 
	}
}

int[] array = [1,2,3,4,5,6];

for_each(i in array)
	writefln(i);


这个是很有必要，不知道Walter打算如何实现。另外对于一些常用的匹配应该提供一些内置的名称，类似下面的TYPE/PARAM_LIST/EXPR： 
// 匹配 int | int x, int y -> x * y
macro(TYPE, "|", PARAM_LIST, "->", EXPR)

// 匹配 (int x, int y) -> x * y
macro("(", PARAM_LIST, ")", "->", EXPR)

// 匹配 int x -> x * x
macro(PARAM_LIST, "->", EXPR)

还有变长部分的匹配，最好与可变参数一致。
qiezi 2007-11-10   回复
哈哈，不错！这么曲溜拐弯的。。往前走了一步。

在没有AST macro的情况下，估计也只能写成这样了。
oldrev 2007-11-10   回复
程序里有个错误，请把第11行的 size_t 改成 int
oldrev 2007-11-10   回复
当当当，经过一个半小时的努力，终于去除了 mixin!
import std.stdio;

int indexof(string s, char ch)  
{  
    foreach(int i, c; s)  
        if(c == ch)  
            return i;  
    return -1;  
}  

size_t indexof(string s, string sub)  
{  
    for(int i = 0; i < s.length - sub.length; i++)  
    {  
        if (s[i .. i + sub.length] == sub)  
            return i;  
    }  
    return -1;  
}  

template _RetType(string expr)
{
    static if (indexof(expr, '|') == -1) 
        const string _RetType =  "";  
    else
        const string _RetType = expr[0..indexof(expr, '|')];  
}

template _ArgTypes(string expr)
{
	const string _ArgTypes = expr[indexof(expr, '|') + 1 .. indexof(expr, "->")];
}

template _Body(string expr)
{
	const string _Body = expr[indexof(expr, "->") + 2 .. $];
}


template _LambdaLiteral(string expr)
{
	const string _LambdaLiteral = "delegate " ~ _RetType!(expr) ~ 
		"(" ~ _ArgTypes!(expr) ~ "){return (" ~  _Body!(expr) ~ ");}";
}

template lambda(string expr)
{
	typeof(mixin(_LambdaLiteral!(expr))) lambda()
	{
		return mixin(_LambdaLiteral!(expr));
	}
}


T1 inject(T,T1)(T[] arr, T1 init, T1 delegate(T1, T) dg)  
{  
    T1 value = init;  
    foreach(e; arr)  
        value = dg(value, e);  
    return value;  
}  

void main()  
{  
    int[] arr = [1,2,3];  
    int total = arr.inject(0, lambda!("int sum, int elem -> sum + elem"));
    writefln(total);  
}


输出：
6


缺点是错误检测还没做，不过这是小问题。
oldrev 2007-11-10   回复
貌似 AST 宏也不是很难实现，我的设想是编译器遇到 AST 宏就把它记录到一张表里，并为宏里的代码生存一棵单独的 AST。当整个程序的代码都生成 AST 以后，再对代码 AST 进行模式匹配，然后把宏体内的 AST 嫁接上去就行了。

除了 The Future of D 里的演示外，应该再往前走一步，允许无名宏：
macro("for_each", "(", value, "in", container, ")", body)
{
	auto iter = container.begin();
	for(; iter != container.end(); ++iter)
	{
		auto value = iter.value();
		body; 
	}
}

int[] array = [1,2,3,4,5,6];

for_each(i in array)
	writefln(i);
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论

qiezi
搜索本博客
存档
最新评论