编程语言里函数的简要描述：
函数是变量，定义在作用域里，可以被调用。调用的过程是：创建新的作用域，并在这个作用域里声明函数的形参，最后执行函数体，求得返回值
再看一遍数组表达式：
00// 计算 a + a 01['+', 'a', 'a'] 02 03// 再看看这个 js 函数 04a => a + a 05 06// 不难发现，如下函数跟上面数组表达式的联系： 07// 1. 形参 + 数组表达式 构成函数 08a => ['+', 'a', 'a'] 09 10// 2. 形参 + 词法作用域 + 数组表达式 构成闭包 11(a, scope) => ['+', 'a', 'a'] 12 13// 3. 函数的调用即是把实际参数传入，然后在 scope 里声明形参 14// 然后执行函数体，即求值数组表达式 15let fn = (a, scope) => ['+', 'a', 'a'];
上面做了一个函数的声明，调用过程。
接下来，我将结合上篇 《数组和计算式》 和对 JavaScript, lisp 的借鉴和类比，基于数组计算式来实现一个简单的、带闭包的、函数式的 lisp 方言，能解释求值以下代码：
00;; 声明递归求和函数 01(define sum 02 (lambda (n) 03 (? (> n 0) 04 (+ n (sum (+ n -1))) 05 0))) 06 07;; 执行调用 08(sum 5) 09;; => 10;; 5 + 4 + 3 + 2 + 1 + 0 = 15
等价于：
00// 声明递归求和函数 01let sum = n => ( 02 n > 0 ? 03 (n + sum(n - 1)) : 04 0 05); 06 07// 执行调用 08sum(5); 09// => 10// 5 + 4 + 3 + 2 + 1 + 0 = 15
# 词法解析 ↵
要做解释器，首先得先将我们的代码变成数组表达式，这样才可以。
00const parse = require('./parse') 01 02let exps = parse(` 03 (+ 1 1) 04 (+ 2 2) 05 (+ 3 3) 06 (+ 4 (+ 2 2)) 07`); 08 09console.log(exps); 10 11// calc 是上一篇的 calc 函数，用于求值 12let res = exps.map(calc); 13 14console.log(res);
parse 结结果
词法解析一般来说主要是算法和与语义方面的内容，不是本文的核心，本文的核心是探讨编程语言的执行过程以及利用数组计算式去设计实现一个简单的编程语言。
在此，贴出我的词法解析代码，直接拿来使用即可 （已折叠）
折叠的源码
# 词法解析代码之一 getExp.js ↵
单行的核心解析。
00module.exports = getExp; 01 02function getExp(chars){ 03 let bracket = 0, args = []; 04 05 for (let i = 0; i < chars.length; i++){ 06 let char = chars[i]; 07 08 if (char === '('){ 09 bracket = bracket + 1; 10 if (bracket === 1){ 11 // push next 12 let nextChar = chars[i + 1]; 13 14 if (nextChar !== '('){ 15 args.push(chars[i + 1]); 16 i = i + 1; 17 } 18 19 } else if (bracket === 2) { 20 let innerExp = chars.slice(i); 21 let { exp, len } = getExp(innerExp); 22 23 args.push(exp); 24 25 i = i + len - 1; 26 } 27 } else if (char === ')'){ 28 bracket = bracket - 1; 29 if (bracket === 0){ 30 // 回归 31 return { 32 exp: $(args), 33 len: i 34 } 35 } 36 } else { 37 if (bracket === 1){ 38 args.push(char); 39 } 40 } 41 } 42 43 return { 44 exp: $(args), 45 len: chars.length 46 } 47} 48 49function $(args){ 50 return args.map(val => { 51 let num = parseInt(val); 52 53 if (Number.isNaN(num)){ 54 return val 55 } else { 56 return num 57 } 58 }); 59}
# 词法解析代码之二 parse.js ↵
多行的预处理，以及删除注释等处理。
00const getExp = require('./getExp') 01 02module.exports = parse; 03 04/** 05 * @description parse 06 * @param { String } text 07 */ 08function parse(text){ 09 text = text.split('\n') 10 .map(line => { 11 let pos = line.indexOf(';'); 12 13 if (pos !== -1){ 14 return line.substring(0, pos) 15 } else { 16 return line; 17 } 18 }) 19 .join('\n') 20 .replace(/\(/g, ' ( ') 21 .replace(/\)/g, ' ) ') 22 .replace(/\n/g, '') 23 .replace(/\r/g, '') 24 .replace(/\t/g, '') 25 26 27 let chars = text.split(' ') 28 .filter(e => e); 29 30 let ast_blocks = parseBlock(chars); 31 32 return ast_blocks; 33} 34 35/** 36 * @description 处理行 37 * @param { Array<String> } chars 38 * @param { Array } blocks 39 */ 40function parseBlock(chars, blocks = []){ 41 let { exp, len } = getExp(chars); 42 43 let nextChars = chars.slice(len + 1); 44 45 blocks.push(exp); 46 47 if (nextChars.length === 0){ 48 return blocks; 49 } else { 50 return parseBlock(nextChars, blocks); 51 } 52}
# 函数 ↵
一个函数的组成由形式参数、函数体构成，运行的时候需要作用域环境和实际参数，比如：
00function add(a, b){ 01 return a + b; 02} 03 04// 在全局下调用，传入实际参数 1, 2 05add(1, 2);
在 js 里的函数所在的环境指的是函数声明的位置，确定了函数是否能访问到某个变量。
单纯的数组计算式，其实就是一条语句，只需要在上面添加作用域环境和形参表即可构成函数，比如上面的函数 add 可以写成这样：
00let fn_array = { 01 // 形参列表 02 args: ['a', 'b'], 03 // 函数体 04 body: ['+', 'a', 'b'], 05 // 全局作用域下 06 // 函数执行的时候要在上面创建一个作用域来临时存放 a 和 b 07 scope: global 08 // 下文实现作用域, 这里不深入追究作用域 09}
对闭包理解比较深刻的人应该已经发现了，fn_array 就是闭包，它包括了函数的声明、函数体以及函数所在的环境。
闭包离不开作用域，作用域的意义得靠函数来体现，接下来，我将先阐述闭包和作用域的概念，并分别给出一个可行的实现。
# 闭包 ↵
闭包，是函数的声明、函数体、函数所能访问的各种变量的集合所构成的三元组。
由此可以得出，从定义上来看，函数是闭包的真子集，函数的调用离不开闭包。 （针对 JavaScript）
可以说，
从技术的角度上来说，每一个函数就是一个闭包 (出自权威指南)，这句话是没有问题的。观察如下代码：
00let outer = 'outer'; 01 02function a(){ 03 let inner = 'inner'; 04 05 return function b(){ 06 let inner_inner = 'inner_inner'; 07 console.log(outer, inner, inner_inner); 08 } 09} 10 11let b = a(); 12 13b(); 14// => 15// outer inner inner_inner
执行 a 返回了一个闭包，包括函数 b 以及函数 b 声明的
环境, 换言之：能访问到的各种变量的集合。那要怎么实现闭包？首先得解决作用域的问题。
# 作用域 ↵
词法作用域的关键是：函数能不能访问到某个变量取决于它声明的位置，从括号从里到外，比如：
00let outer = 'outer'; 01 02function a(){ 03 let inner = 'inner'; 04 05 return function b(){ 06 let inner_inner = 'inner_inner'; 07 console.log(outer, inner, inner_inner); 08 } 09} 10 11function c(){ 12 let hello = 'hello'; 13 14 return function d(){ 15 let star = 'star'; 16 } 17}
示意图如下
作用域示意图
可以看到，上述的写法会产生两条单向链表： b–>a–>全局 和 d–>c–>全局 ，起点是 b 和 d。
b 执行的时候，需要搜索变量，其过程是：在当前作用域找，找不到就往上一级找，直到全局作用域也找不到就报错。
因为有两条链，很自然的，d 里面是不可能直接访问到 a 作用域内的 inner 的。
除非让 b 调用 d，让 b 吧 inner 给 d，换言之，通过传递闭包的方式来达到不同链之间的变量传递 ：
00let outer = 'outer'; 01 02function a(){ 03 let inner = 'inner'; 04 05 return function b(fn){ 06 let inner_inner = 'inner_inner'; 07 console.log(outer, inner, inner_inner); 08 09 fn(inner); 10 } 11} 12 13function c(){ 14 let hello = 'hello'; 15 16 return function d(a_inner){ 17 let star = 'star'; 18 19 console.log(a_inner); 20 } 21} 22 23let d = c(); 24let b = a(); 25// 让 b 调用 d，让 b 吧 inner 给 d 26b(d);
要实现词法作用域，其实是实现单向链表。，以及一些拓展操作如声明变量，在作用域链上搜索变量，创建作用域等等，大概的实现，如下：
00// Scope.js 01module.exports = class Scope { 02 /** 03 * @param { Object } vars 04 * @param { outer } Scope 05 */ 06 constructor(vars = {}, outer = null){ 07 // 变量池 08 this.vars = vars; 09 10 // 指向外层作用域 11 this.outer = outer; 12 } 13 14 /** 15 * @description 创建作用域 16 */ 17 extend(){ 18 let new_scope = new Scope(); 19 20 // 新作用域应该指向现在的 21 new_scope.outer = this; 22 23 return new_scope; 24 } 25 26 /** 27 * @description 定义变量 28 * @param { String } var_name 29 * @param { * } val 30 */ 31 define(var_name, val){ 32 this.vars[var_name] = val; 33 } 34 35 /** 36 * @description 递归地搜索作用域链，如果找不到就报错 37 * @param { String } name 38 */ 39 find(name){ 40 let { vars, outer } = this; 41 42 if (typeof vars[name] !== 'undefined'){ 43 return vars[name]; 44 } else { 45 if (outer){ 46 return outer.find(name); 47 } else { 48 let msg = `Error Var '${name}' Not Found`; 49 console.error(msg); 50 return msg; 51 } 52 } 53 } 54}
对于 Scope.js 的一个示例：
00const Scope = require('./Scope'); 01 02let global_scope = new Scope(); 03let a = global_scope.extend(); 04let b = a.extend(); 05// b -> a -> global_scope 06 07// 在全局定义一个变量 hello, 值是 world 08global_scope.deinde('hello', 'world'); 09 10// 在 b 作用域种搜索， 11// 它会一层一层的找，最终在全局找到 12b.find('hello'); 13// => 'world'
实现了作用域，下一步就是实现闭包了。
# 闭包的实现 ↵
闭包，是函数的声明、函数体、函数所能访问的各种变量的集合所构成的三元组。
函数的声明即是形参列表、函数体即是数组计算式、所谓的各种变量的集合其实是作用域。
实现闭包，就是实现函数的过程, 从语法和 parse 来考虑：
00;; 等价于 x => x + x 01(lambda (x) (+ x x)) 02 03;; parse 后的结果是： 04// ['lambda', ['x'], ['+', 'x', 'x']]
据此：
00// Closure.js 01// 这个模块在最后一小节来写， 02// 仅需知道，它的功能是求值数组计算式，跟上篇一样 03const calc = require('./calc') 04 05class Closure { 06 /** 07 * @description 构造函数 08 * @param { Array<*> } args 形式参数 09 * @param { Array<*> } fn_body 数组计算式 10 * @param { Scope } scope 作用域 11 */ 12 constructor(args, fn_body, scope){ 13 this.args = args; 14 this.fn_body = fn_body; 15 this.scope = scope; 16 } 17 18 /** 19 * @description 函数调用 20 * @param { * } ctx 函数运行的上下文this指向 21 * @param { Array<*> } active_args 实际参数 22 */ 23 apply(ctx, active_args){ 24 let { args, fn_body, scope } = this; 25 26 // 函数运行前，新建作用域 27 let new_scope = scope.extend(); 28 29 // 在新作用域上声明形参 30 active_args.forEach((var_val, idx) => { 31 let var_name = args[idx]; 32 33 // 声明 34 new_scope.define(var_name, var_val); 35 }); 36 37 // 定义 this 指向 38 new_scope.define('this', ctx); 39 40 // 新作用域上执行函数体 并返回结果 41 // calc 函数在下面实现 42 return calc(fn_body, new_scope); 43 } 44} 45 46/** 47 * @description 从表达式中构造闭包 48 * @param { Array } exp 形如 ['lambda', ['x'], ['+', 'x', 'x']] 49 * @param { Scope } scope 50 */ 51function from(exp, scope){ 52 let [keyword, args, fn_body] = exp; 53 54 if (keyword === 'lambda'){ 55 return new Closure(args, fn_body, scope); 56 } else { 57 console.error('不是函数'); 58 59 return null; 60 } 61} 62 63Closure.from = from; 64exports.from = from; 65 66module.exports = Closure;
一个可能的用例：
00const Closure = require('./Closure') 01 , Scope = require('./Scope') 02 03let my_scope = require('./Scope'); 04 05let my_lambda = Closure.of( 06 ['x'], 07 ['+', 'x', 'x'], 08 my_scope 09); 10 11 12// apply 里面会调用 calc 进行求值 13let a = my_lambda.apply(2); 14let b = my_lambda.apply(4); 15 16console.log(a, b); 17// => 18// 4 8
# 闭包 + 作用域 + 数组计算式 = ? ↵
接下来完成执行函数体 calc 的实现，它基本上跟上篇的《数组计算式》里的 calc 类似，不过这里要考虑到变量的声明，闭包函数和基础运算符，因此要做很大的修改：
00// calc.js 01const Scope = require('./Scope') 02 , Closure = require('./Closure') 03 04// 更多的基础运算符 05let table = { 06 '+': (...args) => args.reduce((acc, cur) => acc + cur), 07 '-': (...args) => args.reduce((acc, cur) => acc - cur), 08 '*': (...args) => args.reduce((acc, cur) => acc * cur), 09 '>': (l, r) => l > r, 10 '<': (l, r) => l < r, 11 '>=': (l, r) => l >= r, 12 '<=': (l, r) => l <= r 13} 14 15// 解释器运行的的全局作用域 16let GLOBAL_SCOPE = new Scope(); 17 18// calc 是递归的，递归过程解释在文末 19module.exports = function calc(exp, scope = GLOBAL_SCOPE) { 20 if (!Array.isArray(exp)) { 21 let exp_type = typeof exp; 22 23 if (exp_type === 'number') { 24 return exp; 25 } else if (exp_type === 'string') { 26 // 说明是变量 27 // 应该在作用域里寻找这个变量 28 return scope.find(exp); 29 } 30 } else { 31 // 是数组, 按照数组计算式的结构来计算 32 let [first, ...args] = exp; 33 34 // 说明是函数 35 if (first === 'lambda'){ 36 // 从表达式里构造闭包 37 return Closure.from(exp, scope); 38 } else if (first === 'define') { 39 // 说明是声明 40 let [var_name, var_exp] = args; 41 42 let var_val = calc(var_exp, scope); 43 44 scope.define(var_name, var_val); 45 46 } else if (first === '?') { 47 // 说明是 if 运算 48 let [condition, true_todo, false_todo] = args 49 50 let true_or_flase = calc(condition, scope); 51 52 return calc( 53 (true_or_flase ? true_todo : false_todo), 54 scope 55 ); 56 } else { 57 // 如果有，则说明应该是基础计算式, 否则是闭包 58 let fn = table[first] || scope.find(first); 59 60 // 计算函数的实参 61 // add((1 + 1), 2) => add(2, 2) => 4 62 // (+ (+ 1 1) 2) => (+ 2 2) => 4 63 args = args.map(e => calc(e, scope)); 64 65 return fn.apply(scope, args); 66 } 67 } 68}
calc 的
递归过程 如下：# 如果 exp 不是数组, 则进一步判断 exp 的类型：
- 如果 exp 是数字，直接返回数字
即 calc(123, scope) 会返回 123 - 如果 exp 是字符串，那么需要在作用域里寻找这个变量
即 calc(‘a’, scope) 等价于 scope.find(‘a’)
# 如果 exp 是数组，即 exp 是一个数组计算式，则判断数组计算式的第一个元素：
- 如果第一个元素是
lambda，则应该将这个数组计算式转化成闭包
即调用calc(exp, scope)会返回：Closure.from(exp, scope) - 如果第一个元素是
define，则说明是声明变量
接下来exp的第二个元素是变量名，第三个元素是值
调用 scope.define 声明变量 - 如果第一个元素是
?, 说明应该是if运算
这时候先计算数组计算式的第二个参数的结果
如果是true, 计算数组计算式的第三个元素的值，并返回
如果是false, 计算数组计算式的第四个元素的值，并返回 - 以上两点不满足，说明第一个元素是一个基础运算符或者自定义的闭包
因为基础运算符对于的函数和闭包都实现了 apply 因此可以统一使用 fn.apply 进行调用
在调用前，应该对参数进行处理，即把参数计算出结果出来, 即递归的调用 calc
比如 js 调用add( (1 + 1), 2 )首先得求1 + 1然后才add(2, 2)
这里做的处理也是一样的，先对参数进行最简化，然后传入调用。
# 解释器 ↵
00;; test.se 01;; 声明递归求和函数 02(define sum 03 (lambda (n) 04 (? (> n 0) 05 (+ n (sum (+ n -1))) 06 0))) 07 08;; 执行调用 09(sum 5) 10;; => 11;; 5 + 4 + 3 + 2 + 1 + 0 = 15
编写 boot.js
00const Closure = require('./Closure') 01 , Scope = require('./Scope') 02 , calc = require('./calc') 03 , parse = require('./parse') 04 , fs = require('fs') 05 06let code = fs.readFileSync('./test.se').toString(); 07 08let exps = parse(code); 09 10let scope = new Scope(); 11 12console.log('parse 结果，Array<数组计算式>') 13exps.forEach(exp => console.log(exp)); 14 15let res = exps.map(exp => { 16 let temp = calc(exp, scope); 17 return temp; 18}); 19 20// 打印每行的执行结果 21console.log('\n\n求值结果：'); 22res.forEach((temp, idx) => { 23 let exp = exps[idx]; 24 console.log(`第 ${idx + 1} 块`, `[ ${exp[0]} ]:`, temp); 25})
运行求值
00parse 结果，Array<数组计算式> 01[ 'define', 02 'sum', 03 [ 'lambda', [ 'n' ], [ '?', [Object], [Object], 0 ] ] ] 04[ 'sum', 5 ] 05 06 07求值结果： 08第 1 块 [ define ] undefined 09第 2 块 [ sum ] 15
结果为 15 ，正常运行。
以下经典的递归程序，也都是可以正常运行的：
00;; 递归求斐波那契第 n 项 (从 0 开始数) 01(define fib 02 (lambda (n) 03 (? (> n 1) 04 (+ (fib (+ n -1)) 05 (fib (+ n -2))) 06 1))) 07 08;; 等价于 ( JavaScript ) 09;; fib = n => ( 10;; n > 1 ? 11;; (fib(n-1) + fib(n-2)) : 12;; 1 13;; ); 14 15(fib 0) 16(fib 1) 17(fib 2) 18(fib 3) 19(fib 4) 20(fib 5) 21;; 1 1 2 3 5 8
# 变量、函数、调用 ↵
闭包，是函数的声明、函数体、函数所能访问的各种变量的集合所构成的三元组。
声明里包括了函数的形式参数，函数被调用的时候会在其闭包上的作用域上创建一个新作用域，在里面将形参声明并绑定到实际参数上，最后执行函数体。
函数体可以简化为数组计算式，形参的处理即创建新作用域并在上面绑定实参，最后执行函数体即可。
接下来还有柯里化，数组类型等特性可以完成，有兴趣可以试试 （挖坑）