你好 我向您介绍了实现JavaScript编程语言的指南翻译的第二部分-PL教程 。

来自翻译

我们将创建自己的编程语言-λ语言 （原始语言 -λanguage）。 在创建过程中，我们将使用许多有趣的技术，例如递归下降，控件传递样式和基本的优化技术。 将创建两个版本的解释器-常规和CPS解释器，即JavaScript中的反编译器。

原著的作者是Mihai Bazon ，著名的UglifyJS库（一种用于最小化和格式化JS代码的工具）的作者。

PS解释器和编译器中有一个错误：在a() && b()或a() || b()类a() && b()表达式中 a() || b()这两个部分始终执行。 当然，这是错误的，因为a()对于&&运算符a() false，或者对于||为false。 ，则b()的值不起作用。 这并不难解决。

简单的口译员

在上一部分中，我们编写了3个函数： InputStream ， TokenStream和parse 。 为了从代码中获取AST，我们使用以下代码：

 var ast = parse(TokenStream(InputStream(code))); 

编写解释器比解析器容易：我们只是递归地遍历树并以其正常顺序执行表达式。

上下文（ Environment ）

为了正确执行代码，我们需要一个上下文-一个在给定位置包含所有变量的对象。 它将作为参数传递给evaluate函数。

每次我们进入lambda节点时，都必须向上下文中添加新变量-函数参数。 如果参数与外部块中的变量重叠，则必须在退出函数后恢复变量的旧值。

最简单的方法是使用原型JavaScript继承。 输入新函数时，我们将创建一个新上下文，将外部上下文设置为其原型，然后在新上下文中调用该函数。 因此，我们一无所有-在外部环境中，其所有变量都将保留。

这是Environment对象的实现：

 function Environment(parent) { this.vars = Object.create(parent ? parent.vars : null); this.parent = parent; } Environment.prototype = { extend: function() { return new Environment(this); }, lookup: function(name) { var scope = this; while (scope) { if (Object.prototype.hasOwnProperty.call(scope.vars, name)) return scope; scope = scope.parent; } }, get: function(name) { if (name in this.vars) return this.vars[name]; throw new Error("Undefined variable " + name); }, set: function(name, value) { var scope = this.lookup(name); //          if (!scope && this.parent) throw new Error("Undefined variable " + name); return (scope || this).vars[name] = value; }, def: function(name, value) { return this.vars[name] = value; } }; 

Environment对象有一个指向外部上下文的parent字段。 对于全局上下文，它将为null 。 它有一个vars字段，其中所有变量都属于此上下文。 对于全局上下文，它立即等于一个空对象（ Object.create(null) ）和一个非全局对象的父上下文变量的副本（ Object.create(parent.vars) ）。

它有几种方法：

• extend() -复制当前上下文。
• lookup(name) -查找定义name变量的上下文。
• get(name) -获取名为name的变量的值。 如果尚未定义变量，则引发异常。
• set(name, value) -设置变量的值。 此方法在定义变量的上下文中查找。 如果未定义，并且我们不在全局环境中，则将引发异常。
• def(name, value) -在当前上下文中创建（或重叠或覆盖）变量。

evaluate功能

现在我们有了Environment对象，我们可以继续解决主要问题了。 此功能将是一个很大的switch块，它将根据传输的节点的类型执行某些操作：

 function evaluate(exp, env) { switch (exp.type) { 

对于文字，我们只返回其值：

  case "num": case "str": case "bool": return exp.value; 

变量是从上下文中获取的（变量的名称包含在value字段中）：

  case "var": return env.get(exp.value); 

要进行分配，我们必须确保在左侧具有变量的名称（node var ）。 如果不是，那么我们只抛出一个异常（除了变量之外，我们不支持赋值）。 接下来，我们使用env.set设置变量的值。 请注意，表达式的右侧必须使用递归调用来evaluate ：

  case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); return env.set(exp.left.value, evaluate(exp.right, env)); 

对于binary类型的节点binary必须对两个操作数都应用运算符。 稍后我们将编写apply_op函数。 另外，我们调用表达式的两个部分的evaluate ：

  case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env)); 

lambda类型的节点将返回普通的JavaScript闭包，因此即使从JavaScript中也可以像常规函数一样调用它。 我添加了make_lambda函数，稍后将显示它：

  case "lambda": return make_lambda(env, exp); 

if节点的执行非常简单：首先我们找到条件的值。 如果不是false，则返回then分支的值。 否则，如果存在else分支，则其值为false ：

  case "if": var cond = evaluate(exp.cond, env); if (cond !== false) return evaluate(exp.then, env); return exp.else ? evaluate(exp.else, env) : false; 

prog节点是一个表达式序列。 我们只需按顺序执行所有表达式并获取后者的值（空序列的值为false ）：

  case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val; 

对于call类型的节点call我们需要调用一个函数。 在此之前，我们将找到函数本身的值，找到所有参数的值，然后使用apply调用函数：

  case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); })); 

我们永远不会到达这里，但是如果我们将新的节点类型添加到解析器中，而忘记将其添加到解释器中：

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

这是口译员的主要部分。 上面，我们使用了尚未实现的两个功能，因此让我们开始吧：

apply_op ：

 function apply_op(op, a, b) { function num(x) { if (typeof x != "number") throw new Error("Expected number but got " + x); return x; } function div(x) { if (num(x) == 0) throw new Error("Divide by zero"); return x; } switch (op) { case "+" : return num(a) + num(b); case "-" : return num(a) - num(b); case "*" : return num(a) * num(b); case "/" : return num(a) / div(b); case "%" : return num(a) % div(b); case "&&" : return a !== false && b; case "||" : return a !== false ? a : b; case "<" : return num(a) < num(b); case ">" : return num(a) > num(b); case "<=" : return num(a) <= num(b); case ">=" : return num(a) >= num(b); case "==" : return a === b; case "!=" : return a !== b; } throw new Error("Can't apply operator " + op); } 

它接收运算符类型和参数。 简单直观的switch 。 与JavaScript不同，JavaScript可以采用任何值，例如变量，甚至是没有意义的变量。 我们要求算术运算符的操作数为数字，并且不允许除以零。 对于字符串，我们稍后会提出一些建议。

make_lambda ：

 function make_lambda(env, exp) { function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; } 

如您在上面看到的，它返回一个常规的JavaScript函数，该函数使用传递的上下文和AST函数。 仅当调用函数本身时，才执行所有工作：创建上下文，设置参数（如果不够，则变为false ）。 然后，仅在新的上下文中执行函数主体。

本机功能

如您所见，我们无法通过我们的语言与JavaScript进行交互。 我曾经使用过print和println函数，但是没有在任何地方定义它们。 我们需要用JavaScript编写它们，然后将它们添加到全局上下文中。

这是这样的代码的示例：

 //  -   var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; // ,  parse  TokenStream,      InputStream var ast = parse(TokenStream(InputStream(code))); //    var globalEnv = new Environment(); //  ""  "print" globalEnv.def("print", function(txt){ console.log(txt); }); //  evaluate(ast, globalEnv); //  5 

整个代码

您可以下载我们这段时间编写的所有代码 。 可以使用NodeJS启动它。 只需将代码传递到标准流即可：

 echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js 

代码示例

我们的编程语言虽然简单，但是（理论上）可以解决计算机可以完全解决的任何问题。 这是因为Alonzo Church和Alan Turing比我以前更聪明，他们曾经证明λ微积分（lambda calculus）等效于Turing机器，并且我们的λ语言实现了λ微积分。

这意味着即使我们的语言没有任何机会，我们也可以利用我们已经拥有的机会同样地实现它们。 或者，如果很难做到这一点，我们可以为此编写另一种语言的解释器。

周期数

如果我们有递归，循环就不是问题。 我已经展示了在递归顶部实现循环的示例。 让我们再试一次。

 print_range = λ(a, b) if a <= b { print(a); if a + 1 <= b { print(", "); print_range(a + 1, b); } else println(""); }; print_range(1, 10); 

但是，这里存在一个问题：如果将迭代次数增加到1000，例如，在600之后，出现错误“超出最大调用堆栈大小”。这是因为解释器是递归的，并且递归达到了最大深度。

这是一个严重的问题，但是有解决方案。 我想为迭代添加新的构造（ for或while ），但让我们尝试不使用它们。 递归看起来很漂亮，所以让我们离开它。 稍后我们将看到如何解决此限制。

数据结构（缺少）

在我们的λ语言中，数据有三种类型：数字，字符串和布尔类型。 似乎您无法创建复杂的类型，例如数组或对象。 但这不是一个问题，我们还有一个类型：函数。 事实证明，如果遵循λ演算，那么即使具有继承性，我们也可以创建任何数据结构，包括对象。

我将在列表示例中显示它。 假设我们有一个cons函数，该函数创建一个包含两个值的对象。 我们将此对象称为“单元”或“对”。 我们将名称之一命名为“ car”，另一个命名为“ cdr”。 仅因为它们在Lisp中被称为。 现在，如果我们有一个对象“ cell”，则可以使用car和cdr函数获取其值：

 x = cons(10, 20); print(car(x)); #  10 print(cdr(x)); #  20 

现在我们可以轻松定义一个列表：

列表是一对，包含“ car”中的第一个元素和“ cdr”中的其余元素。 但是`cdr`只能包含一个值！ 该值将是一个列表。 列表是一对，包含“ car”中的第一个元素和“ cdr”中的其余元素。 但是`cdr`只能包含一个值！ 该值将是一个列表。 [...]

这是一种递归数据类型。 但是仍然存在一个问题：何时需要停止？ 逻辑上，当cdr为空列表时，我们应该停止。 但是什么是空清单？ 为此，我们添加一个名为“ NIL”的新对象。 它可以作为一对使用（我们可以在上面使用car和cdr ，但它们的结果将是NIL本身）。 现在让我们创建项目1、2、3、4、5的列表：

 x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x)); # 1 print(car(cdr(x))); # 2  Lisp  . cadr print(car(cdr(cdr(x)))); # 3 caddr print(car(cdr(cdr(cdr(x))))); # 4 cadddr print(car(cdr(cdr(cdr(cdr(x)))))); # 5     . 

当没有特殊语法时，它看起来很糟糕。 但是我只是想表明可以使用现有的λ语言功能来完成此操作。 这是实现：

 cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); 

当我第一次看到cons / car / cdr以这种方式制作时，我很惊讶他们不需要一个if （但是，由于它不在原始的λ微积分中，所以这很奇怪）。 当然，没有编程语言会这样做，因为它效率极低，但不会使λ计算的美观度降低。 用一种清晰的语言，此代码执行以下操作：

• cons函数采用两个值（ a和b ）并返回保存它们的函数。 该功能正是该功能对的目标。 她接受一个参数，并为该对的两个值调用该参数。
• car函数调用传递的参数，并传递返回第一个参数的函数。
• cdr函数与car函数的功能相同，但唯一的区别是传递的函数返回第二个参数。
• NIL函数的工作原理与cons相同，但返回的一对值等于NIL的两个值。

 cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); println(car(x)); # 1 println(car(cdr(x))); # 2 println(car(cdr(cdr(x)))); # 3 println(car(cdr(cdr(cdr(x))))); # 4 println(car(cdr(cdr(cdr(cdr(x)))))); # 5 

列表上有很多算法可以递归实现，看起来很合逻辑。 例如，以下函数为每个列表项调用传递的函数：

 foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println); 

这是另一个为一系列数字创建列表的列表：

 range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL; #     1  8 foreach(range(1, 8), λ(x) println(x * x)); 

上面实现的列表是不可变的（创建列表后，我们无法更改car或cdr ）。 大多数Lisp具有更改对的功能。 在Scheme中，它们称为set-car! / set-cdr! 。 在Common Lisp中， rplaca / rplacd 。 这次我们使用Scheme中的名称：

 cons = λ(x, y) λ(a, i, v) if a == "get" then if i == 0 then x else y else if i == 0 then x = v else y = v; car = λ(cell) cell("get", 0); cdr = λ(cell) cell("get", 1); set-car! = λ(cell, val) cell("set", 0, val); set-cdr! = λ(cell, val) cell("set", 1, val); #  NIL     NIL = cons(0, 0); set-car!(NIL, NIL); set-cdr!(NIL, NIL); ## : x = cons(1, 2); println(car(x)); # 1 println(cdr(x)); # 2 set-car!(x, 10); set-cdr!(x, 20); println(car(x)); # 10 println(cdr(x)); # 20 

这表明我们可以实现可变数据结构。 从代码可以明显看出，我不会深入研究它是如何工作的。

我们可以进一步实现对象，但是如果不更改语法，将很难做到。 另一种方法是在令牌生成器/解析器中实现新语法，并将其处理添加到解释器中。 所有主要的编程语言都这样做，因此有必要实现正常的性能。 我们将在本文的下一部分中添加新的语法。

[摘自译者：如果您对lambda演算感兴趣，那么有一篇关于Habré的很酷的文章专门针对这个主题： JavaScript中的Lambda演算 。

新的语法构造

我们的λ语言具有很多语法结构。 例如，没有直接添加新变量的方法。 如前所述，我们必须使用IIFE，所以它看起来像这样：

 (λ(x, y){ (λ(z){ ## it gets worse when one of the vars depends on another print(x + y + z); })(x + y); })(2, 3); 

我们将添加let关键字。 这将允许我们编写如下内容：

 let (x = 2, y = 3, z = x + y) print(x + y + z); 

对于let块中的每个变量，即使在同一块中，先前的变量也应该可用。 因此，上面的代码将等效于以下代码：

 (λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2); 

这些更改可以直接在解析器中进行，然后不需要解释器中的更改。 无需添加新的let节点，我们可以将其变成call和lambda节点。 这意味着我们没有对语言进行任何语义更改-这被称为“语法糖”，而将其转换为之前存在的AST节点的操作被称为“无糖”（原始：“ desugaring”）。

但是，无论如何我们都必须更改解析器。 让我们添加一个新的“ let”节点，因为它可以更有效地进行解释（无需创建闭包并立即调用它们，我们只需要复制和更改上下文）。

另外，我们还将添加对Scheme中“ let named”的支持。 它使创建循环更加容易：

 print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0); 

这是一个“递归”循环，它计算10 + 9 + ... + 0的总和。以前，我们必须这样做：

 print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })()); 

另外，为简化此操作，我们将添加“带有名称的功能”的语法。 它看起来像这样：

 print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10)); 

为此需要进行的修改：

• 支持lambda关键字后的可选名称。 如果存在，那么我们必须在当前上下文中添加一个变量，该变量将指向函数本身。 这与JavaScript中带有名称的函数完全相同。
• 支持新的let关键字。 接下来是一个可选名称和以下形式的变量定义列表（可能为空）： foo = EXPRESSION ，用逗号分隔。 let表达式的主体是单个表达式（当然，它可以是一系列表达式）。

解析器更改

首先，对标记生成器进行一些小的更改，将let关键字添加到关键字列表中：

 var keywords = " let if then else lambda λ true false "; 

更改parse_lambda函数，使其读取可选名称：

 function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null, //   vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } 

现在添加一个解析let表达式的函数：

 function parse_let() { skip_kw("let"); if (input.peek().type == "var") { var name = input.next().value; var defs = delimited("(", ")", ",", parse_vardef); return { type: "call", func: { type: "lambda", name: name, vars: defs.map(function(def){ return def.name }), body: parse_expression(), }, args: defs.map(function(def){ return def.def || FALSE }) }; } return { type: "let", vars: delimited("(", ")", ",", parse_vardef), body: parse_expression(), }; } 

这处理两种情况。 如果在let之后有一个类型为var的令牌，则以名称命名。 此外，我们使用定delimited函数读取定义列表，因为它们位于方括号中并以逗号分隔，并且我们使用parse_vardef函数，如下所示。 接下来，我们返回类型为call的节点，该节点立即调用名为（IIFE）的函数。 该函数的参数是let定义的变量，并且call节点会将值作为参数传递。 而且，当然，可以使用parse_expression()读取函数的主体。

如果它是简单的let ，那么我们将返回一个类型为let的节点，其中包含vars和body字段。 vars字段包含以下格式的变量数组： { name: VARIABLE, def: AST } ，这些{ name: VARIABLE, def: AST }由以下函数解析：

 function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; } 

另外，您需要在parse_atom函数中添加对新型表达式的parse_atom ：

 //      parse_if if (is_kw("let")) return parse_let(); 

口译员变更

由于我们决定更改AST的结构，而不是将其“破解”到旧的节点类型中，因此我们必须将新逻辑的处理添加到解释器中。

为了增加对可选函数名称的支持，我们修改了make_lambda函数：

 function make_lambda(env, exp) { if (exp.name) { //  env = env.extend(); //  env.def(exp.name, lambda); //  } //  function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; } 

如果函数具有名称，那么在创建闭包时，我们将复制上下文，并将函数添加到上下文中。 其余的保持不变。

最后，要处理let类型的节点，我们将以下情况添加到解释器中：

 case "let": exp.vars.forEach(function(v){ var scope = env.extend(); scope.def(v.name, v.def ? evaluate(v.def, env) : false); env = scope; }); return evaluate(exp.body, env); 

注意，对于每个变量，都会创建一个新上下文，并在其中添加新变量。 之后，我们仅在最后一个上下文中执行主体。

例子

 println(let loop (n = 100) if n > 0 then n + loop(n - 1) else 0); let (x = 2, y = x + 1, z = x + y) println(x + y + z); #   ..     let # print(x + y + z); let (x = 10) { let (x = x * 2, y = x * x) { println(x); ## 20 println(y); ## 400 }; println(x); ## 10 }; 

— .

. , , , . JavaScript λ.

:

 globalEnv.def("fibJS", function fibJS(n){ if (n < 2) return n; return fibJS(n - 1) + fibJS(n - 2); }); globalEnv.def("time", function(fn){ var t1 = Date.now(); var ret = fn(); var t2 = Date.now(); println("Time: " + (t2 - t1) + "ms"); return ret; }); 

time , , , .

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); print("fib(10): "); time( λ() println(fib(10)) ); print("fibJS(10): "); time( λ() println(fibJS(10)) ); println("---"); 

, Google Chrome, n (27), λ , , JS 4 . , , .

λ JavaScript. , for / while ; JS. ? JS , .

, , JavaScript, , JavaScript.

, , . , .

结论

, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).

, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.

: JavaScript. 第3部分：CPS解释器