MyLisp项目日志：函数

函数

我们想让用户可以定义自己的函数，而不仅仅是使用我们提供的内建函数

那我们要提供这样的功能就要首先就得提供一个内置函数，可以使用户通过这个函数创建自定义的函数

他使用起来有两个参数，第一个是形参列表，也就是要使用的参数，第二个参数是另一个列表，也就是函数的具体内容，运行函数时，我们调用对应函数进行处理即可

我们使用\来表示定义函数

例如

\ {x y} {+ x y}

然后可以将其作为普通的S表达式使用，也就是计算的符号

(\ {x y} {+ x y}) 10 20

如果我们想命名这个函数，只需要使用def给他起个名字，这样就能使用名字直接调用了

def {add-together} (\ {x y} {+ x y})

add-together 10 20

函数类型

我们要将函数存储为一种MLval的值，就需要考虑他的组成部分

根据刚刚功能的描述，可以基本确定如下内容：

1. 函数有三个部分构成
2. 第一个是形参列表，并且需要绑定参数和值才能计算出值
3. 第二个是Q表达式，用来表示函数的主体部分
4. 第三个是，用来存储分配给形式参数的空间，这里我们直接可以使用环境存储即可

我们把内置函数和用户定义的函数都放在MLVAL_FUN中，就需要使用一个方法判断是否为内置函数，如果builtin是NULL，就说明不是内置函数

struct MLval {
	int type;

	// 基础内容
	double num;
	char* err;
	char* sym;

	// 函数内容
	MLbuiltin builtin;
	MLenv* env;
	MLval* formals; // 形式参数
	MLval* body;

	// 表达式内容
	int count;
	MLval** cell;
};

我们还需要为用户定义的MLval的函数创建构造函数同时构造一个新的环境，把形参和函数主体都传入

// 外部函数初始化
MLval* MLval_lambda(MLval* formals, MLval* body) {
	MLval* v = malloc(sizeof(MLval));
	v->type = MLVAL_FUN;
	// 设置内建指向空
	v->builtin = NULL;
	// 新建函数
	v->env = MLenv_new();
	// 设置形式参数和函数主体
	v->formals = formals;
	v->body = body;
	return v;
}

因为我们对MLval的内部结构进行更改了，所以与之对应的删除，复制，打印都需要更改，具体更改内容见最后的汇总

Lambda函数

这里的Lambda函数简单理解就可以认为是用户编写的函数，他的本意是一系列符号的联系

我们需要根据用户的要求构建函数，第一步应该是检查用户输入的格式是否正确，然后取出对应的内容，传递给之前的构造函数即可

MLval* builtin_lambda(MLenv* e, MLval* a) {
	// 检查两个参数，每个都是Q表达式
	MLASSERT_NUM("\\", a, 2);
	MLASSERT_TYPE("\\", a, 0, MLVAL_QEXPR);
	MLASSERT_TYPE("\\", a, 1, MLVAL_QEXPR);
	// 检查第一个Q表达式只包含符号
	for (int i = 0; i < a->cell[0]->count; i++) {
		MLASSERT(a, (a->cell[0]->cell[i]->type == MLVAL_SYM),
				 "Cannot define non-symbol. Got %s, Expected %s.",
				 ltype_name(a->cell[0]->cell[i]->type), ltype_name(MLVAL_SYM));
	}
	// pop前两个参数的首位(formals body)，传递给lambda（构建外部函数）
	MLval* formals = MLval_pop(a, 0);
	MLval* body = MLval_pop(a, 0);
	MLval_del(a);
	return MLval_lambda(formals, body);
}

然后我们这里需要把这个函数放到集中调用的函数中去，这里也不过多赘述

运行环境

我们为函数提供了他们自身的环境，并在这个环境中为形参设置相对应的值，当我们计算函数时，就可以直接在这个环境中运行，并且可以保证这些变量的值一定是正确的

在这里不要忽视，函数是可以访问全局环境中的变量的，例如其他的内置函数，因此我们可以通过更改环境的定义来包含对一些父环境的引用来解决这个问题，这样就能访问全局环境中的变量了

我们在环境的定义中增加一项MLenv* par来指向父环境，当我们从环境中取变量时，如果找不到，就迭代指向父环境，查看父环境中是否存在目标变量，一直到是根的父环境

如下

struct MLenv {
	MLenv* par; // 父环境
	int count;
	char** syms; // 符号列表
	MLval** vals; // 参数列表
};

// 环境初始化
MLenv* MLenv_new() {
	MLenv* e = malloc(sizeof(MLenv));
	e->par = NULL;
	e->count = 0;
	e->syms = NULL;
	e->vals = NULL;
	return e;
}

// 从环境中取值
MLval* MLenv_get(MLenv* e, MLval* k) {
	// 遍历所有项
	for (int i = 0; i < e->count; i++) {
		// 检查存储的字符串中是否有与符号字符串匹配
		// 如果匹配则返回值的副本
		if (strcmp(e->syms[i], k->sym) == 0) {
			return MLval_copy(e->vals[i]);
		}
	}
	// 如果没有找到则检查父环境中是否匹配，否则返回报错
	if (e->par) {
		return MLenv_get(e->par, k);
	} else {
		return MLval_err("Unbound Symbol '%s'", k->sym);
	}
}

// 复制环境
MLenv* MLenv_copy(MLenv* e) {
	MLenv* n = malloc(sizeof(MLenv));
	n->par = e->par;
	n->count = e->count;
	n->syms = malloc(sizeof(char*) * n->count);
	n->vals = malloc(sizeof(MLval*) * n->count);
	for (int i = 0; i < e->count; i++) {
		n->syms[i] = malloc(strlen(e->syms[i]) + 1);
		strcpy(n->syms[i], e->syms[i]);
		n->vals[i] = MLval_copy(e->vals[i]);
	}
	return n;
}

因为有了父环境和子环境的概念，那么定义变量时就要区分是在父环境中定义还是在子环境中定义，我们提供两个方法，def表示在全局环境中定义，put表示在当前环境中定义

// 把值存到当前变量
void MLenv_put(MLenv* e, MLval* k, MLval* v) {
	// 遍历环境中的项
	for (int i = 0; i < e->count; i++) {
		// 找到
		// 首先删除原位置的项
		// 其次使用用户提供的项替换
		if (strcmp(e->syms[i], k->sym) == 0) {
			MLval_del(e->vals[i]);
			e->vals[i] = MLval_copy(v);
			return;
		}
	}
	// 若不存在则构造
	e->count++;
	e->vals = realloc(e->vals, sizeof(MLval*) * e->count);
	e->syms = realloc(e->syms, sizeof(char*) * e->count);
	e->vals[e->count - 1] = MLval_copy(v);
	e->syms[e->count - 1] = malloc(strlen(k->sym) + 1);
	strcpy(e->syms[e->count - 1], k->sym);
}

// 在全局中存储变量
void MLenv_def(MLenv* e, MLval* k, MLval* v) {
	// 迭代到最大的父环境（根节点）
	while (e->par) {
		e = e->par;
	}
	// 添加到环境中
	MLenv_put(e, k, v);
}

函数调用

我们需要在创建完函数后，能够使之正确调用

这时就分两种情况，第一种是内置函数，我们仍然使用之前的函数指针直接调用

另一种就是用户函数了，我们需要把每个参数都绑定到形参中，然后计算函数主体，将父环境设置为调用环境

但是当提供的参数数量和形参的数量不对应时，就不能正常工作了，当提供的参数小于形参个数时，我们可以优先绑定先前的几个形式参数，然后返回，其余参数不绑定，当形参数量大于提供参数的个数时，报出错误

还需要更新计算表达式的函数，让他支持调用函数的计算

可变参数

我们有一些内建函数是支持可变参数的，例如add，join，我们需要让用户也支持这种操作

但是我们没办法让C语言原生支持这种操作，只能添加一些特定的语法，将其硬编码到我们的语言中

我们规定&符号，让其使用类似{x & xs}的形式参数，意思是表示这个函数的参数列表首先会接收一个参数x，然后是零个或多个其他参数，我们会将这些参数连在一起形成一个xs列表

在我们的函数处理中，分配形参时，会特别寻找和处理&符号，如果存在，则采用下一个形参并且分配给他我们剩余的参数

除此之外，我们需要检查&之后的形参是否有效，无效就应该报错，还需要将参数列表转换为Q表达式

如果用户在调用函数时不提供任何额外参数，只提供第一个有名的参数，那么后面那个参数列表就应该是空列表

最终如下

// 调用函数
MLval* MLval_call(MLenv* e, MLval* f, MLval* a) {
	// 内建函数直接调用
	if (f->builtin) {
		return f->builtin(e, a);
	}
	// 记录参数数量
	int given = a->count;
	int total = f->formals->count;

	// 当有参数还需要处理时
	while (a->count) {
		// 参数传递过多
		if (f->formals->count == 0) {
			MLval_del(a);
			return MLval_err("Function passed too many arguments. "
							 "Got %i, Expected %i.", given, total);
		}
		// 取出形参的第一个符号
		MLval* sym = MLval_pop(f->formals, 0);
		// '&'特殊处理
		if (strcmp(sym->sym, "&") == 0) {
			// 确保'&'后跟有其他符号
			if (f->formals->count != 1) {
				MLval_del(a);
				return MLval_err("Function format invalid. "
								 "Symbol '&' not followed by single symbol.");
			}
			// 下一个参数绑定到剩余的形参
			MLval* nsym = MLval_pop(f->formals, 0);
			MLenv_put(f->env, nsym, builtin_list(e, a));
			MLval_del(sym); MLval_del(nsym);
			break;
		}
		// 取出列表的下一个参数
		MLval* val = MLval_pop(a, 0);
		// 绑定一份拷贝到函数的环境中
		MLenv_put(f->env, sym, val);
		MLval_del(sym); MLval_del(val);
	}
	// 删除已经被绑定的参数列表
	MLval_del(a);

	// 如果形参列表中含有'&'，将其绑定到空列表
	if (f->formals->count > 0 &&
		strcmp(f->formals->cell[0]->sym, "&") == 0) {
		// 检查并确保'&'没有背无效传递
		if (f->formals->count != 2) {
			return MLval_err("Function format invalid. "
							 "Symbol '&' not followed by single symbol.");
		}
		// 取出并删除'&'符号
		MLval_del(MLval_pop(f->formals, 0));
		// 取出下一个符号并绑定到空列表
		MLval* sym = MLval_pop(f->formals, 0);
		MLval* val = MLval_qexpr();
		// 绑定到环境中
		MLenv_put(f->env, sym, val);
		MLval_del(sym); MLval_del(val);
	}
	// 如果所有的参数都被绑定，则开始计算
	if (f->formals->count == 0) {
		// 将父环境设置为计算环境
		f->env->par = e;
		// 计算并返回
		return builtin_eval(f->env,
							MLval_add(MLval_sexpr(), MLval_copy(f->body)));
	} else {
		// 否则返回函数的拷贝
		return MLval_copy(f);
	}
}

优化函数定义方式

直接使用Lambda定义函数蛮不错的，但是语法略显笨拙，需要涉及很多括号和符号，我们可以舱室用一些更简单的语法来编写一个定义函数的函数

从本质上来讲很简单，我们想要的是一个可以同时执行两个步骤的功能

首先第一步是他应该能创建一个函数，然后将其定义为名称，这一步我们直接用def就可以做到

第二步是我们需要人用户提供一个列表，就是args作为形式参数，body作为函数主体

lambda应该是这样的

\ {args body} {def (head args) (\ (tail args) body)}

然后用def定义一下

def {fun} (\ {args body} {def (head args) (\ (tail args) body)})

简单翻译一下是这样，结合下面的例子更容易理解，定义一个函数fun，他有两个参数，第一个是args，第二个是body，函数功能是这样的，从输入列表args中取出第一个元素，这个元素是新函数的名称，取出这个列表的剩余部分，作为参数和body一同构建一个新的函数，名字就是刚刚取出来的第一个参数

这样我们就可以使用fun直接定义函数了

像这样

fun {add-together x y} {+ x y}

add-together 1 2

柯里化

虽然我们现在可以传递可变参数了，但是如果要传入一个参数列表，或者列表本身，就比较困难了

我们可以定义一个unpack函数来做到这一点。它接受某个函数和某个列表作为输入，并将函数附加到列表前面，然后进行求值

fun {unpack f xs} {eval (join (list f) xs)}

同样的，我们可以有一个相反的过程，有一个接收列表作为为输入的函数，但希望使用可变参数来调用，直接打包即可

fun {pack f & xs} {f xs}

这个两个过程也被称之为柯里化与反柯里化