20220112lispy

Jan 12, 2022

编译原理

之前学过输入语法转AST，AST转换另一种语法格式。这其实是自然语言组织能力，比如中文转成英文来说。

语言是表达能力，计算机操作需要在表达能力上，实现语法格式并能操作运行。

当前篇幅用于描述学习文章: BuildYourOwnLisp 过程中遇到的点，过程。这个系列会出多个文章描述，会对应到学习文章对应的章节。

开篇

BuildYourOwnLisp 这篇文章在目前我学习入门c 里面是相当之精妙的，各种用法都是灵活运用，前提还是需要c 语言基础的，基础部分看learnc。

基础入门之后，就可以在这篇文章带领下学学c 的深入使用，并且可以感受到编译原理的基础。

里面用到mpc的库，这个库是剥离AST表达式的点，然后直接学习真实的制作一门小型语言。mpc后期我会再出一篇文章，并且以此修改自己的程序以支持。

之前在豆瓣上看到有人评论说到该篇文章精髓都在mpc 里面，其实是不对的，这是两个阶段，两个层面。

好了，不多说了，直接进入正式环节。

步骤

分析 buildyourownlisp 这本书，我们从大致的大纲开始。

  1. mpc 库解析用户输入，词法分析后得到mpc 自带的ast 树形结构。
  2. 使用mpc_ast_t 得到带有tag、content 的属性进入到 lval*(*lval_read)(mpc_ast_t*) 方法进行转换成lval对应结构
  3. 使用已转换过结构的lval 传递给下一个方法: lval*(*lval_eval)(lenv*, lval*)
  4. lval* (*lval_expr_eval)(lenv*, lval*) 内部执行波兰式语句.

上面即为前11章内容，第10章Q-Expression - Quote 表达式将Symbol 某个统一入口方法识别。

第11章开始，带入lenv 环境变量的逻辑。前11章之前，都是很好理解，我们直接从方法实现往下。

我们先讲完前10章，感受下简单。第11章将会第10章之后衔接。

lval_read

(跳过 mpc库使用，这个库在一开始使用后，都不再在本篇幅出现。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main(int argc, char** argv) {
  mpc_parser_t* Number = mpc_new("number");
  mpc_parser_t* Symbol = mpc_new("symbol");
  mpc_parser_t* Sexpr = mpc_new("sexpr");
  mpc_parser_t* Expr = mpc_new("expr");
  mpc_parser_t* Lispy = mpc_new("lispy);
  mpca_lang(MPCA_LANG_DEFAULT,
    "                                            \
    number : /-?[0-9]+/ ; \
    symbol : '+' | '-' | '*' | '/' ; \
    sexpr : '(' <expr>* ')' ; \
    expr : <number> | <symbol> | <sexpr> ; \
    lispy : /^/ <expr>* /$/ ;
    ",
    Number, Symbol, Sexpr, Expr, Lispy);
  puts("Lispy Version 0.0.0.0.5");
  while (1) {
    char* input = readline("lispy> ");
    add_history(input);

    mpc_result_t r;
    if (mpc_parse("<stdin>", input, Lispy, &r)) {
      lval* val = lval_read(r.output);
      lval* x = lval_eval(val);
      lval_println(x);
      lval_del(x);
      mpc_ast_delete(r.output);
    } else {
      mpc_err_print(r.error);
      mpc_err_delete(r.error);
    }
    free(input);
  }
  mpc_cleanup(5, Number, Symbol, Sexpr, Expr, Lispy);
}

以上还会增加Q表达式、识别String、Comment 输入等。

我们直接从S表达式开始。

lval_read 我愿意拆开来, S表达式、Q表达式放到一起: lval_expr_read，其他走 lval_read.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#define FORLESS(lessCount) for (int i = 0; i < lessCount; i++)
int strlength(char* s) {
  return strlen(s)+1;
}

enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR, LVAL_QEXPR };

struct lval;
typedef struct lval lval;
struct lval {
  int type;

  long num;
  char* err;
  char* sym;

  int count;
  lval** cell;
};
#define NEWLVAL lval* v = malloc(sizeof(lval));

lval* lval_err(char* err) {
  NEWLVAL;
  v->type = LVAL_ERR;
  v->err = malloc(strlength(err));
  strcpy(v->err, err);
  return v;
}
lval* lval_num(long num) {
  NEWLVAL;
  v->type = LVAL_NUM;
  v->num = num;
  return v;
}
lval* lval_check_num(char* numstr) {
  errno = 0;
  // 10进制转换，如果错误、out of range 则errno会报错
  long num = strtol(numstr, NULL, 10);
  return errno != 0 ? lval_err("Invalid number!") : lval_num(num);
}
lval* lval_sexpr(void) {
  NEWLVAL;
  v->type = LVAL_SEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}
lval* lval_qexpr(void) {
  NEWLVAL;
  v->type = LVAL_QEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}
// lval删除内存空间:
void lval_del(lval* v);
void lval_expr_del(lval* v) {
  FORLESS(v->count) {
    lval_del(v->cell[i]);
  }
  free(v->cell);
}
void lval_del(lval* v) {
  switch (v->type) {
    case LVAL_NUM: break;
    case LVAL_ERR: free(v->err); break;
    case LVAL_SYM: free(v->sym); break;
    case LVAL_SEXPR: lval_expr_del(v); break;
  }
  free(v);
}

lval* lval_read(mpc_ast_t* t);
// 识别 >(program)、sexpr、qexpr
lval* lval_expr_read(mpc_ast_t* t) {
  lval* x;
  if (strcmp(t.tag, ">") == 0) { x = lval_sexpr(); }
  else if (strstr(t.tag, "sexpr")) { x = lval_sexpr(); }
  // 将子借点数据添加进x，如果子节点也是其他表达式，则也会被纳入x
  FORLESS(t->children_num) {
    // 过滤无用字符
    if (strcmp(t->children[i]->content, "(") == 0) continue;
    if (strcmp(t->children[i]->content, ")") == 0) continue;
    if (strcmp(t->children[i]->content, "{") == 0) continue;
    if (strcmp(t->children[i]->content, "}") == 0) continue;
    // 过滤mpc 带有的regex字符
    if (strcmp(t->children[i]->tag, "regex") == 0) continue;
    x = lval_add(x, lval_read(t->children[i]));
  }
  return x;
}
// 单独处理number / symbol 的转换
lval* lval_read(mpc_ast_t* t) {
  if (strstr(t->tag, "number")) {
    return lval_check_num(t->content);
  } else if (strstr(t->tag, "symbol") == 0) {
    return lval_symbol(t->content);
  }
  // 其他交给lval_expr_read
  return lval_expr_read(t);
}
void lval_print(lval* v);
void lval_expr_print(lval* v, char open, char close) {
  putchar(open);
  FORLESS(v->count) {
    lval_print(v->cell[i]);
    if (i != (v->count-1)) {
      putchar(' ');
    }
  }
  putchar(close);
}
void lval_print(lval* v) {
  switch (v->type) {
    case LVAL_NUM: printf("%i", v->num); break;
    case LVAL_ERR: printf("%s", v->err); break;
    case LVAL_SYM: printf("%s", v->sym); break;
    case LVAL_FUN: printf("<Function>"); break;
    case LVAL_SEXPR: lval_expr_print(v, '(', ')'); break;
    case LVAL_QEXPR: lval_expr_print(v, '{', '}'); break;
  }
}
void lval_println(lval* v) { lval_print(v); putchar('\n'); }

以上还有 lval*(*lval_add)(lval* x, lval* a)，其将a加入到x的cell中:

1
2
3
4
5
6
lval* lval_add(lval* x, lval* a) {
  x->count++;
  x->cell = realloc(x->cell, sizeof(lval*)*x->count);
  x->cell[x->count-1] = a;
  return x;
}

现在开始使用lval_eval, lval_eval 遇到S表达式，去lval_expr_eval 执行，其他原样返回:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// 从v(S表达式/Q表达式)中取出其cell中的第i个元素
lval* lval_pop(lval* v, int i) {
  // 拿到指针
  lval* x = v->cell[i];
  // 通过内存折叠，去掉这个空位
  // 也可以写作: lval** a = &v->cell[i]; lval** b = &v->cell[i+1]; memmove(a, b, ...);
  memmove(&v->cell[i], &v->cell[i+1], sizeof(lval*)*(v->count-i-1));
  // 由于折叠了一个元素，realloc v->cell
  v->count--;
  v->cell = realloc(v->cell, sizeof(lval*)*v->count);
  return x;
}
// take动作是pop之后，删除v，不需要v了
lval* lval_take(lval* v, int i) {
  lval* x = lval_pop(v, i);
  lval_del(x);
  return x;
}
// 这个LASSERT也是精髓
#define LASSERT(arg, cond, err) if (!(cond)) { lval_del(arg); return lval_err(err); }
lval* buildin_op(lval* v, char* op) {
  FORLESS(v->count) {
    LASSERT(v, v->cell[i]->type == LVAL_NUM, "Function op passed invalid format type");
  }
  // 拿出第一个参数来做运算。之后会销毁其他所有内存对象
  lval* x = lval_pop(v, 0);
  // 如果没有其他参数，而且op为-, 则表示该对象为取反
  if (v->count == 0 && strcmp(op, "-") == 0) {
    x->num = -x->num;
  }
  // 轮训v
  while (v->count) {
    lval* y = lval_pop(v, 0);
    if (strcmp(op, "+") == 0) { x->num += y->num; }
    else if (strcmp(op, "-") == 0) { x->num -= y->num; }
    else if (strcmp(op, "*") == 0) { x->num *= y->num; }
    else if (strcmp(op, "/") == 0) {
      // 除数不能为0
      if (y->num == 0) {
        // 这里复用x的指针
        lval_del(x); lval_del(y);
        x = lval_err("Division By Zero!");
        break;
      }
      x->num /= y->num;
    }
    lval_del(y);
  }
  // 删除v
  lval_del(v);
  return x;
}
lval* lval_eval(lval* v);
lval* lval_expr_eval(lval* v) {
  // 进入到执行阶段，首先将子集全部执行。
  // 这样如果他是S表达式，其会先处理内部的数据，得到答案后返回给外层，再统一结算，得到最终结果
  FORLESS(v->count) {
    v->cell[i] = lval_eval(v->cell[i]);
  }
  // 测试如果出现LVAL_ERR，则直接返回该err
  FORLESS(v->count) {
    if (v->cell[i]->type == LVAL_ERR) {
      return lval_take(v, i);
    }
  }
  // 判断是否S表达式为空，或者只有一个，都直接返回
  if (v->count == 0) return v;
  if (v->count == 1) return lval_take(v, 0);
  // 拿出第一个元素，第一个元素必定是 LVAL_SYM
  lval* f = lval_pop(v, 0);
  if (f->type != LVAL_SYM) {
    lval_del(f); lval_del(v); return lval_err("S-Expression must start with Symbol!");
  }
  // 这里就是结果了
  lval* res = buildin_op(v, f->sym);
  // 此处仅释放f；v的释放由buildin_op处理。
  // 原因是接下来还有好多buildin_x 内部要处理v，都有内部去控制删除了。
  lval_del(f);
  return res;
}
lval* lval_eval(lval* v) {
  if (v->type == LVAL_SEXPR) return lval_expr_eval(v);
  return v;
}

S-Expression

S表达式指的是 (...) 这种格式的内容，S表达式内涵其他表达式，他在eval 中一遇到就会被执行，而且是一直往内层执行，返回结果给外层计算。

上面的使用方式就包括了S表达式，这里不重述。

对应buildyourownlisp 中的第9章。这个做完你能得到基本多层运算规则。+-*/ 计算器。

学完这章，你可以做到:

+ 1 (* 7 5) 3
(- 100)
/

Q-Expression

Q表达式指的是 {...}这种格式的内容，他如果需要被执行，则需要其他的buildin方法辅助主动执行，否则其只是对元素等进行挂载保存，直到收到buildin方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
enum { LVAL_ERR, ... LVAL_QEXPR }
lval* lval_qexpr(void) {
  NEWLVAL;
  v->type = LVAL_QEXPR;
  v->count = 0;
  v->cell = NULL;
  return v;
}
void lval_del(lval* v) {
  switch (v->type) {
    ...
    case LVAL_SEXPR:
    case LVAL_QEXPR:
      lval_expr_del(v);
      break;
  }
  ...
}
lval* lval_expr_read(mpc_ast_t* t) {
  lval* x;
  if (strcmp(t->tag, ">") == 0) { x = lval_sexpr(); }
  else if (strstr(t->tag, "sexpr")) { x = lval_sexpr(); }
  // 增加识别Q表达式
  else if (strstr(t.tag, "qexpr")) { x = lval_qexpr(); }
  ...
}
// 同时lval_print 增加识别Q表达式打印

以上是Q表达式的录入方案，他就是为了能将自己保存到Q表达式里面，等待被执行。从这里也可以很明显区分出S表达式-Q表达式的区别: S表达式在lval_eval中直接执行；Q表达式相当于元素，直接放回。

以下开始实现Q表达式执行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 首先改造lval_err
lval* lval_err(char* fmt, ...) {
    NEWLVAL;
    v->type = LVAL_ERR;
    va_list va;
    va_start(va, fmt);
    static int ERR_LENGTH = 512;
    v->err = malloc(sizeof(char)*ERR_LENGTH);
    vsnprintf(v->err, ERR_LENGTH-1, fmt, va);
    v->err = realloc(v->err, sizeof(char)*strlength(v->err));
    va_end(va);
    return v;
}
char* ltype_name(int type) {
  switch (type) {
    case LVAL_ERR: return "<Error>";
    case LVAL_NUM: return "<Number>";
    case LVAL_SYM: return "<Symbol>";
    case LVAL_SEXPR: return "<S-Expression>";
    case LVAL_QEXPR: return "<Q-Expression>";
    default: return "<Unknown Function>";
  }
}
// 改造LASSERT ##__VA_ARGS__ 粘性宏
#define LASSERT(arg, cond, fmt, ...) if (!(cond)) { lval* err = lval_err(fmt, ##__VA_ARGS__); lval_del(arg); return err; }
// 增加几个帮助宏
#define LASSERT_NUM(func, arg, expect) LASSERT(arg, arg->count == expect, "Function '%s' passed invalid number of argument. " \
  "Got %i, Expected %i", func, arg->count, expect)
#define LASSERT_TYPE(func, arg, i, expect) LASSERT(arg, arg->cell[i]->type == expect, "Function '%s' passed invalid type at index: %i. " \
  "Got %s, Expected %s", func, i, ltype_name(arg->cell[i]->type), ltype_name(expect))
#define LASSERT_NOT_EMPTY(func, arg, i) LASSERT(arg, arg->cell[i]->count != 0, "Function '%s' at index:%i passed '{}' empty arguments!", func, i)
lval* buildin_head(lval* v) {
  LASSERT_NUM("head", v, 1);
  LASSERT_TYPE("head", v, 0, LVAL_QEXPR);
  LASSERT_NOT_EMPTY("head", v, 0);
  // take拿出该Qexpr, 形如将v删除
  lval* x = lval_take(v, 0);
  // 将除0 以外的元素清空
  while (x->count > 1) { lval_del(lval_pop(x, 1)); }
  return x;
}
lval* buildin_tail(lval* v) {
  LASSERT_NUM("tail", v, 1);
  LASSERT_TYPE("tail", v, 0, LVAL_QEXPR);
  LASSERT_NOT_EMPTY("tail", v, 0);
  lval* x = lval_take(v, 0);
  // 删除第0个，其他保留
  lval_del(lval_pop(x, 0));
  return x;
}
// 直接将元素改为Q表达式
lval* buildin_list(lval* v) {
  v->type = LVAL_QEXPR;
  return v;
}
lval* buildin_eval(lval* v) {
  LASSERT_NUM("eval", v, 1);
  LASSERT_TYPE("eval", v, 0, LVAL_QEXPR);
  lval* x = lval_take(v, 0);
  // 先改为S表达式
  x->type = LVAL_SEXPR;
  // 运行该表达式
  return lval_eval(x);
}
// 作用是把多个元素合并为一个，全部拼接
lval* buildin_join(lval* v) {
  FORLESS(v->count) {
    LASSERT_TYPE("join", v, i, LVAL_QEXPR);
  }
  lval* x = lval_pop(v, 0);
  while (v->count) {
    lval* y = lval_pop(v, 0);
    while (y->count) {
      // 将内部元素依次加到x中
      x = lval_add(lval_pop(y, 0));
    }
    lval_del(y);
  }
  lval_del(v);
  return x;
}
lval* buildin(lval* v, char* op) {
  if (strcmp(op, "head") == 0) { return buildin_head(v); }
  else if (strcmp(op, "tail") == 0) { return buildin_tail(v); }
  else if (strcmp(op, "list") == 0) { return buildin_list(v); }
  else if (strcmp(op, "eval") == 0) { return buildin_eval(v); }
  else if (strcmp(op, "join") == 0) { return buildin_join(v); }
  else if (strstr("+-*/", op)) { return buildin_op(v); }
  lval_del(v);
  return lval_err("UnKnown Function: %s", op);
}
lval* lval_expr_eval(lval* v) {
  ...
  lval* res = buildin(v, f->sym);
  // lval* res = buildin_op(v, f->sym);
  lval_del(f);
  return res;
}

以上就是Q表达式。

这章结束，你可以实现如:

list 1 2 3 4
{head (list 1 2 3 4)}
eval { head (list 1 2 3 4) }
tail { tail tail tail }
eval (tail { tail tail { 5 6 7 } } )
eval (head {(+ 1 2) (+ 10 20)})

lenv

这章开始，更牛逼的来了: 环境变量的引入！

首先enum 增加 LVAL_FUN，其作用是在 lval_expr_eval中原先是Symbol的类型，改为获取为了LVAL_FUN:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// 增加LVAL_FUN 类型
enum { ... LVAL_FUN }
struct lenv;
typedef lenv lenv;
typedef lval*(*lbuildin)(lenv* e, lval* v);
struct lval {
  ...
  lbuildin fun;
  ...
}
void lval_del(lval* v) {
  switch (v->type) {
    ...
    case LVAL_FUN: break;
    ...
  }
  ...
}
lval* lval_fun(lbuilin fun) {
  NEWLVAL;
  v->type = LVAL_FUN;
  v->fun = fun;
  return v;
}
// 增加lval_copy 为lval 做copy使用
lval* lval_copy(lval* a) {
  NEWLVAL;
  v->type = a->type;
  switch (v->type) {
    case LVAL_NUM: v->num = a->num; break;
    case LVAL_FUN: v->fun = a->fun; break;
    case LVAL_ERR: v->err = malloc(strlength(a->err)); strcpy(v->err, a->err); break;
    case LVAL_SYM: v->sym = malloc(strlength(a->sym)); strcpy(v->sym, a->sym); break;
    case LVAL_SEXPR:
    case LVAL_QEXPR:
      v->count = a->count;
      v->cell = malloc(sizeof(lval*)*v->count);
      FORLESS(v->count) {
        // 将a所有子集复制到v中
        v->cell[i] = lval_copy(a->cell[i]);
      }
      break;
  }
  return v;
}
// 增加lenv 结构
struct lenv {
  // 环境变量中保存所有syms 和所有vals 数据
  int count;
  char** syms;
  lval** vals;
};
void lenv_del(lenv* e) {
  FORLESS(e->count) {
    free(e->syms[i]);
    lval_del(e->vals[i]);
  }
  free(e);
}
// lenv_get 作用是lval_eval 在类型为symbol时查找对应的实际数据的拷贝。
// 避免直接使用symbol在执行时需要硬编码。可以分开实现。
// 这里采用轮训方式，简单实现为主，没有使用hash table
lval* lenv_get(lenv* e, lval* k) {
  FORLESS(e->count) {
    // 遇到相同的，则返回e->vals 对应数据的拷贝对象
    if (strcmp(e->syms[i], k->sym) == 0) {
      return lval_copy(e->vals[i]);
    }
  }
  return lval_err("Unbound Function: %s", k->sym);
}
void lenv_put(lenv* e, lval* k, lval* v) {
  FORLESS(e->count) {
    // 找到了就更换
    if (strcmp(e->syms[i], k->sym) == 0) {
      e->vals[i] = lval_copy(v);
      return;
    }
  }
  // 找不到添加该元素
  e->count++;
  e->syms = rellaoc(e->syms, sizeof(char*)*e->count);
  e->vals = realloc(e->vals, sizeof(lval*)*e->count);
  e->syms[e->count-1] = malloc(sizeof(char)*strlength(k->sym));
  strcpy(e->syms[e->count-1], k->sym);
  e->vals[e->count-1] = lval_copy(v);
}
// 首个参数改为lenv
lval* buildin_op(lenv* e, lval* v, char* op) {
  ...
}
lval* buildin_head(lenv* e, lval* v) {
  ...
}
lval* buildin_tail(lenv* e, lval* v) {
  ...
}
lval* buildin_list(lenv* e, lval* v) {
  ...
}
lval* buildin_eval(lenv* e, lval* v) {
  ...
  return lval_eval(e, x);
}
lval* buildin_join(lenv* e, lval* v) {
  ...
}
lval* buildin_add(lenv* e, lval* v) {
  return buildin_op(e, v, "+");
}
lval* buildin_sub(lenv* e, lval* v) {
  return buildin_op(e, v, "-");
}
lval* buildin_mul(lenv* e, lval* v) {
  return buildin_op(e, v, "*");
}
lval* buildin_div(lenv* e, lval* v) {
  return buildin_op(e, v, "/");
}

// 首个入参是环境变量
lval* lval_expr_eval(lenv* e, lval* v) {
  ...
  lval* f = lval_pop(v, 0);
  if (f->type != LVAL_FUN) {
    lval* err = lval_err("S-Expression not start with Function! receive type: %s", ltype_name(f->type));
    lval_del(f); lval_del(v);
    return err;
  }
  lval* res = f->fun(e, v);
  // lval* res = buildin(v, f->sym);
  // lval* res = buildin_op(v, f->sym);
  ...
}
lval* lval_eval(lenv* e, lval* v) {
  if (v->type == LVAL_SYM) {
    lval* f = lenv_get(e, v);
    lval_del(v);
    return f;
  }
  if (v->type == LVAL_SEXPR) return lval_expr_eval(e, v);
  return v;
}
// 定义lenv_add_buildins 将lenv 环境变量添加到全文lenv中
void lenv_add_buildin(lenv* e, char* op, lbuildin fun) {
  lval* sym = lval_sym(op);
  lval* funValue = lval_fun(fun);
  lenv_put(e, sym, funValue);
  lval_del(sym); lval_del(funValue);
}
void lenv_add_buildins(lenv* e) {
  lenv_add_buildin(e, "head", buildin_head);
  lenv_add_buildin(e, "tail", buildin_tail);
  lenv_add_buildin(e, "list", buildin_list);
  lenv_add_buildin(e, "eval", buildin_eval);
  lenv_add_buildin(e, "join", buildin_join);

  lenv_add_buildin(e, "+", buildin_add);
  lenv_add_buildin(e, "-", buildin_sub);
  lenv_add_buildin(e, "*", buildin_mul);
  lenv_add_buildin(e, "/", buildin_div);
}
int main(int argc, char** argv) {
  ...
  puts("Lispy Version 0.0.0.0.11");
  // 创建lenv 环境变量，让其在整个生命周期中体现出环境值
  lenv* e = lenv_new();
  lenv_add_buildins(e);
  while (1) {
    ...
    lval* x = lval_eval(e, res);
    ...
  }
  ...
}

在这里可以做到和之前一致的输入与输出，不过其执行是以上下文环境的方案查找对应的方法。重点是 lval_eval 中使用 == LVAL_SYM 找出在环境变量找出的对应的buildins 或者表达式。

下面添加一个def 来将输入的形参和实参绑定，并且也是通过lval_eval 转变出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// def {a b c d} 1 2 3 4
lval* buildin_def(lenv* e, lval* v) {
  LASSERT_TYPE("def", v, 0, LVAL_QEXPR);
  lval* syms = v->cell[0];
  FORLESS(syms->count) {
    LASSERT(v, syms->cell[i]->type == LVAL_SYM, "Function '%s' passed invalid format argument."
    "Got %s, Expect %s", "def", ltype_name(syms->cell[i]->type), ltype_name(LVAL_SYM));
  }
  LASSERT(v, syms->count == v->count-1, "Function '%s' passed invalid number of arguments."
  "Symbols %i, Values %i", "def", syms->count, v->count-1);
  FORLESS(syms->count) {
    lenv_put(e, syms[i], v->cell[i+1]);
  }
  return lval_sexpr();
}
void lenv_add_buildins(lenv* e) {
  ...
  lenv_add_buildin(e, "def", buildin_def);
}

这一步之后，你可以做到:

def {x} 100
def {y} 200
x
y
+ x y
def { a b } 5 6
+ a b
def { arglist } { a b x y }
arglist
def arglist 1 2 3 4
list a b x y

第十二章:函数

这章超级重要，超级super 给力，内容不是很多，适应下。
这章过后，之后基本关于c的简单多了，喘口气? 别急，让我们赶紧开始吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
// 函数，延续使用LVAL_FUN, 不过 lval 增加formals, 保存环境变量中的参数，body保存环境变量中的执行语句，以及增加一个lenv 作为局部变量
// 且LVAL_FUN中的 buildin 和函数要区分开，有lbuildin 则为内建方法，另外的则为lambda表达式:
struct lval {
  int type;

  long num;
  char* err;
  char* sym;

  lbuildin buildin; // 内建方法

  lenv* env; // 对象所属局部变量
  lval* formals; // 参数列表
  lval* body; // body执行参数列表

  int count;
  lval** cell;
}
lval* lval_fun(lbuildin fun) {
  NEWLVAL;
  v->type = LVAL_FUN;
  v->buildin = fun;
  return v;
}
lval* lval_lambda(lval* formals, lval* body) {
  NEWLVAL;
  v->type = LVAL_FUN;
  v->buildin = NULL; // 记得一定置空，否则会出现野指针
  v->lenv = new_lenv();
  v->formals = formals;
  v->body = body;
  return v;
}
lval* lval_del(lval* v) {
  switch (v->type) {
    case LVAL_FUN:
      // 只需要处理def 出来的变量
      if (!v->buildin) {
        lenv_del(v->env);
        lval_del(v->formals);
        lval_del(v->body);
      }
      break;
  }
}
lval* lval_copy(lval* x) {
  ...
  switch (v->type) {
    case LVAL_FUN:
      // x 有buildin则代表
      if (a->buildin) {
        v->buildin = x->buildin;
      } else {
        // 保证buildin是NULL, 否则变出来野指针了
        v->buildin = NULL;
        v->env = lenv_copy(x->env);
        v->formals = lval_copy(x->formals);
        v->body = lval_copy(x->body);
      }
      break;
    ...
  }
}
struct lenv {
  lenv* pair; // 增加父环境变量
  ...
}
lval* lenv_get(lenv* e, lval* k) {
  FORLESS(e->count) {
    ...
  }
  if (e->pair) {
    return lenv_get(e->pair, k);
  }
  return lval_err("Unbound Symbol: %s", k->sym);
}
// 增加一个lenv copy
lenv* lenv_copy(lenv* e) {
  lenv* n = malloc(sizeof(lenv));
  n->count = e->count;
  n->pair = e->pair;
  n->syms = malloc(sizeof(char*)*n->count);
  n->vals = malloc(sizeof(lval*)*n->count);
  FORLESS(n->count) {
      n->vals[i] = lval_copy(e->vals[i]);
      n->syms[i] = malloc(sizeof(char)*strlength(e->syms[i]));
      strcpy(n->syms[i], e->syms[i]);
  }
  return n;
}
void lenv_put(lenv* e, lval* k, lval* v) {
  ...
}
// def 用在将环境变量保存在顶层。只要保证while 循环到顶层即可。
void lenv_def(lenv* e, lval* k, lval* v) {
  while (e->pair) { e = e->pair; }
  lenv_put(e, k, v);
}
lval* buildin_var(lenv* e, lval* v, char* op) {
  LASSERT_TYPE("def", v, 0, LVAL_QEXPR);
  lval* syms = v->cell[0];
  FORLESS(syms->count) {
    LASSERT(v, syms->cell[i]->type == LVAL_SYM, "Function '%s' passed invalid format argument."
    "Got %s, Expect %s", "def", ltype_name(syms->cell[i]->type), ltype_name(LVAL_SYM));
  }
  LASSERT(v, syms->count == v->count-1, "Function '%s' passed invalid number of arguments."
  "Symbols %i, Values %i", "def", syms->count, v->count-1);
  FORLESS(syms->count) {
    if (strcmp(op, "def") == 0) {
      lenv_def(e, syms[i], v->cell[i+1]);
    } else {
      lenv_put(e, syms[i], v->cell[i+1]);
    }
  }
  return lval_sexpr();
}
lval* buildin_def(lenv* e, lval* v) {
  return buildin_var(e, v, "def");
}
lval* buildin_put(lenv* e, lval* v) {
  return buildin_var(e, v, "put");
}
lval* buildin_lambda(lenv* e, lval* v) {
  LASSERT_NUM("\\", v, 2);
  LASSERT_TYPE("\\", v, 0, LVAL_QEXPR);
  LASSERT_TYPE("\\", v, 1, LVAL_QEXPR);

  //    形参↓    运行↓
  // \ { x y } { + x y }
  lval* formals = lval_pop(v, 0);
  lval* body = lval_pop(v, 0);
  lval_del(v);
  // 生成lambda表达式
  return lval_lambda(formals, body);
}
// lval_expr_eval 执行换成 lval_call
lval* lval_call(lenv* e, lval* v, lval* f) {
  if (f->buildin) return f->buildin(e, v);

  int count = v->count;
  int total = f->formals->count;
  while (v->count) {
    if (f->formals->count == 0) {
      lval_del(v);
      return lval_err("Function '%s' passedd too many argument!"
                      "Got %i, Expect %i",
                      "call", count, total);
    }
    // 此处将fun中的形参拿出，同时将参数对应上
    // 然后保存到f->env 环境变量中
    lval *sym = lval_pop(f->formals, 0);
    // def { addCurry } (\ { x y & last } { eval (join (list + x y) (head last) ) })
    // addCurry 10 20 40 30 -> 10 + 20 + 40 = 70
    if (strcmp(sym->sym, "&") == 0) {
      if (f->formals->count != 1) {
        lval_del(sym);
        lval_del(v);
        return lval_err("Function '%s' pass invalid format argument!"
                        "Symbol '&' must followed by only one symbol!"
                        "Got %i, Expect %i",
                        "call", f->formals->count, 1);
      }
      lval *syms = lval_pop(f->formals, 0);
      lval *vals = buildin_list(f->env, v);
      lenv_put(f->env, syms, vals);
      lval_del(sym);
      lval_del(syms);
      break;
    }
    lval *val = lval_pop(v, 0);
    lenv_put(f->env, sym, val);
    lval_del(sym);
    lval_del(val);
  }
  lval_del(v);
  // 这里的作用，是在上面执行后，仍然还有 `& x`
  // 其实参数已经写完，只剩复数参数，那么直接给其复制空参数即可执行了
  if (f->formals->count != 0 && strcmp(f->formals->cell[0]->sym, "&") == 0) {
    if (f->formals->count != 2) {
      return lval_err("Function '%s' pass invalid format argument!"
                      "Symbol '&' must followed by only one symbol!"
                      "Got %i, Expect %i",
                      "call", f->formals->count, 1);
    }
    lval_del(lval_pop(f->formals, 0));
    lval *syms = lval_pop(f->formals, 0);
    lval *vals = lval_qexpr(); // 空参数
    lenv_put(f->env, syms, vals);
    lval_del(syms);
    lval_del(vals);
  }
  // 说明参数全，开始运行
  if (f->formals->count == 0) {
    // 为当前fun的局部环境变量增加父级环境变量
    f->env->pair = e;
    // 执行时，将环境变量传入，相当于提前有了相关的环境变量
    // 执行语句是body，拷贝一份给 buildin_eval 去执行
    return buildin_eval(f->env, lval_add(lval_qexpr(), lval_copy(f->body)));
  } else {
    return lval_copy(f);
  }
}
lval* lval_expr_eval(lenv* e, lval* v, char* op) {
  ...
  lval* res = lval_call(e, v, f);
  // lval* res = f->fun(e, v);
  // lval* res = buildin(v, f->sym);
  // lval* res = buildin_op(v, f->sym);
}
void lenv_add_buildins(lenv* e) {
  lenv_add_buildin(e, "\\", buildin_lambda);
  lenv_add_buildin(e, "def", buildin_def);
  lenv_add_buildin(e, "=", buildin_put);
  ...
}

以上就是在环境变量lenv这章之后，增加的lambda 表达式以及执行方案。

这章之后你可以做到:

def {add-mul} (\ {x y} {+ x (* x y)}) // ()
add-mul 10 20 // 210
add-mul 10 // (\ {y} {+ x (* x y)})
def {add-mul-ten} (add-mul 10)
add-mul-ten 50 // 510

\ {args body} {def (head args) (\ (tail args) body)}
def {fun} (\ {args body} {def (head args) (\ (tail args) body)})
fun {add-together x y} {+ x y}
fun {unpack f xs} {eval (join (list f) xs)}
fun {pack f & xs} {f xs}
def {uncurry} pack // ()
def {curry} unpack // ()
curry + {5 6 7} // 18
uncurry head 5 6 7 // {5}
def {add-uncurried} + // ()
def {add-curried} (curry +) // ()
add-curried {5 6 7} // 18
add-uncurried 5 6 7 // 18