用变量作用域模拟面向对象

用变量作用域模拟面向对象

> LeekScript 教程

本页只适用于 LS1.0。从 LS1.1 起可以直接使用类：面向对象编程

由于 LeekScript 不是面向对象的语言，这篇文章将带你实现一种“伪 OOP”（面向对象编程）。我会先介绍 OOP 的概念，再讲解变量作用域的工作原理。为了不至于太理论化，我们会动手编写一种叫“二叉搜索树”的结构，它是专为有序插入和查找而优化的结构。

OOP 的概念

如果你开始对 C（++/#）、PHP、Java 等其他语言感兴趣，这个概念就非常重要。它是一种组织程序的新方式，引入了“对象”。你大概知道日常生活中的对象是什么：可以改变、可以操作的东西。而在编程中，我们把由变量和函数组成的结构叫作“对象”，这些变量和函数分别称为属性和方法。以一辆汽车为例：它有速度、加速度（细节就不展开了）等特征，还有转向、加速、刹车……等动作。我们可以这样表示这辆车：

这样写出的代码结构清晰、整洁。它还能简化一些由复杂指令组成的动作的使用，这些指令对使用者是隐藏的。OOP 中另一个非常重要的东西是封装原则……并不是所有属性和方法都应该交给使用者操作：如果使用者没有检查好这个那个，就可能把对象“弄坏”。假设使用者在游戏进行中修改了汽车的速度，却没有考虑惯性之类的因素，汽车就会出现怪异的行为，而这还只是一个很小的改动。 所以，封装就是让对象的某些部分对使用者不可见，这样的属性/方法称为私有的；反之，使用者可以使用的属性/方法则是公有的。

这些对象的定义称为“类”。使用类的方法是创建它的一个新实例，就像使用普通类型（数字、数组、字符串……）一样。只不过在大多数编译器中（说“所有”也不为过），这种实例化是隐式的：var a = 5; 创建了一个数字对象类型的变量，值为 '5'。这里说“数字对象”是一种不严谨的说法。 OOP 的一个不同之处在于作用于变量的函数：

var a = 1;

// 不用 OOP

add(a, 1); // 定义为 function (@obj, nbr) { obj += nbr; }

// OOP

a.add(1); // 定义为 method add (nbr) { this += nbr; }

函数 'add' 的参数是要加上的数字。两种写法的区别在于上下文：第一种情况下，'add' 不知道要对哪个对象执行这些指令，需要一个指向这个数字的引用（参数 'obj'）；而第二种情况下它是一个方法，所以它知道要修改哪个对象，因为 'add' 属于 'a'。 注意： 这里的语法完全是随意设定的，理解原理就行。

顺便说一句，如果你一路看下来了就会明白，'add' 是公有的，因为使用者可以调用它。

变量作用域

你一定用过全局变量，它们可以在回合之间保存信息，并且在代码的任何地方都能访问。它们和“局部”变量的区别就在于“作用域”。来看下面的代码：

global _global;

function testPortee () { var localFunction; }

var localMain;

上面每个变量的作用域都不一样：_global 在所有回合、任何地方都能访问；localMain 只能在主代码块中访问（函数里不行）；localFunction 只能在函数“testPortee”中访问。作用域同样适用于函数：testPortee 在所有回合、任何地方都能访问，而匿名函数只能在它诞生的地方访问（和变量一样）。

变量的作用域适用于所有代码块（代码块的符号：'{' 和 '}'）。因此，在 if、while、do/while、for 中创建的变量，在它外面是访问不到的：

if (true) { var localIf = 0;// 创建 localIf } // localIf 的生命结束

debug(localIf); // 错误：(localIf) 未知的变量或函数

for (var i = 0; i

术语

节点： 树由节点组成，每个节点包含一个值，以及分别指向右边节点和左边节点的引用（可以为空） 根： 就是没有父节点的那个节点 父节点： 每个节点只有一个父节点，也就是指向它的那个节点 子节点： 当前节点所指向的节点 叶子： 没有子节点的节点 内部节点： 不是叶子的节点 后继： 节点左子树中的最小值 前驱： 节点右子树中的最大值 在上图中：

8 是这棵树的根 3、6、10 和 14 是内部节点 1、4、7 和 13 是叶子 3 是 1 和 6 的父节点 14 是 10 的子节点 8 的后继是 13 8 的前驱是 7

伪代码使用的语法（名称保留法语原文；关键字对照：METHODE … FIN METHODE = 方法定义，SI / SINON / SINON SI / FIN SI = 如果 / 否则 / 否则如果 / 结束如果，RETOURNER = 返回，Vrai / Faux / Nul = 真 / 假 / 空，ET / OU / NOT = 且 / 或 / 非，nombre = 数字）：

输入参数

当前对象的属性

静态方法（可以在任何类之外使用）

节点的属性和方法

插入

现在来看看二叉搜索树的几个主要算法。插入节点就是其中之一。

如果树为空：直接把这个值设为根即可。 如果树中已有一个或多个节点： 从根开始遍历这棵树， 如果值更大，就向左移动 否则向右移动 重复这个操作，直到无法继续：目标子节点为空。 有两种方法：递归（递归）或迭代。第二种情况下，主树（持有根的引用的那棵树）有一个方法，负责遍历整棵树直到找到正确的位置。我们要用的是递归，也就是说，每个节点都有一个方法，把插入操作交给它的某个子节点去做，除非这个子节点为空，这时就由它自己插入新节点。 下面是递归（递归）插入的伪代码：

// 主树的方法：由使用者调用 METHODE Insertion (valeur : nombre) SI EstVide (racine) racine 能够实例化一个类 拥有公有和私有属性 拥有公有和私有方法

在什么情况下，不借助数组也能创建新变量？（因为数组开销太大） 答案是函数：要用函数来创建新变量：

function new_Object () { var attribut; }

有了这样一个函数，每次调用都会创建一个新变量，但在函数外面无法直接访问它。要解决这个问题，可以返回指向这个变量的引用（但如果对象包含多个变量就行不通了），或者返回一个函数或一个数组。

function new_Object () { var privateAttribut; var publicAttribut; var privateMethod; var publicMethod;

return @( function (/* 这里放什么？/) {/ 这里放什么？/} ); // 或者 return @ [/ 这里放什么？ */]; }

var obj = new_Object();

因为我不喜欢数组的开销，除非另有说明，我都会使用匿名函数。 'obj' 现在是 'Object' 的一个实例，但目前它还无法修改自己，因为那个函数什么也不做…… 如果我们返回一个会修改属性的匿名函数：

function new_Object () { // ……（我不会每次都把代码全部重写一遍）

return @( function () { publicAttribut = 1; } ); }

var obj = new_Object(); // 所以 obj 是一个匿名函数

// obj := // privateAttribut = null // publicAttribut = null; // privateMethod = null; // publicMethod = null;

obj(); // 调用在 new_Object 中创建的函数

// obj := // privateAttribut = null // publicAttribut = 1; // privateMethod = null; // publicMethod = null;

注意： ':=' 的意思是“按定义等于”，我会用它来展示对象各个属性的值

如果你一路看下来了，就会发现属性是可以修改的，因为函数“记得”它的上下文，也就是说，通过 'obj()' 调用函数时，函数的执行方式就好像它仍然位于那个可以访问这些属性的函数内部一样。

不过，目前我们还没法选择要修改什么、怎么修改。办法很简单：给匿名函数传一个命令作为参数就行：

function new_Object () { // …… return @( function (@cmd) { if (cmd === "Modifie !") publicAttribut = 1; }); }

var obj = new_Object();

obj("Modifie !");

// obj := // publicAttribut = 1; // ...

搞定！只要命令确实是 "Modifie !"（“修改！”），'publicAttribut' 的值就会被设为 1。 第二个问题是：怎样选择要赋给 'publicAttribut' 的值？ 我们不能简单地给返回的函数加上多个参数，因为这样不够灵活：假设程序里已经用上了某个对象，再给这个函数加一个参数，就会让整个代码出错…… 不过，我们可以再返回一个函数，它接收要赋给 'publicAttribut' 的值作为参数：

function new_Object () { // …… return @( function (@cmd) { if (cmd === "Modifie !") return function (@value) { publicAttribut = value; }; }); }

调用方式如下：

var obj = new_Object();

var mod_obj = obj("Modifie !"); // 返回一个接收一个参数的函数 mod_obj(5); // 修改 obj 的属性

// 可以简写为： obj("Modifie !")(5);

这样就能实现封装了：默认一切都是私有的，再借助命令让某些方法变成公有。顺便说明，属性是无法变成公有的，必须通过 getter/setter 来访问，也就是说：

function new_Object () { var attribut; return @( function (@cmd) { if (cmd === "SetAttribut") return function (@value) { attribut= value; }; if (cmd === "getAttribut") return @attribut; }); }

注意： 当且仅当属性包含的是数组或字符串时，才能通过 return 获得指向该属性的引用（参见 @的行为）。

优化思路

以参数传入的命令

---

当你向对象发送命令时： obj("commande"); ，这个命令是以原始数据的形式传过去的。函数签名 return function (@cmd) { /* ... */ } 中的 '@' 能省下 1 个操作数，但传递本身仍然要花 1 个操作数。要降低这个开销，就得传一个变量（@的行为）。这里我们要用常量，而在 LS 中常量用全局变量来实现。

global setAttribut = 0; // 每个常量都要修改其中的值

var obj = new_Object();

obj(setAttribut); // 调用函数只花 1 个操作数，而不是 2 个

此外，这样还能用上自动补全

注意： 使用多个类时，小心不要创建两个同名的全局变量：要么给常量加上和对象相关的首字母前缀，要么把所有常量集中起来重复使用。

二分法

--- 第二点比较复杂。它能降低调用方法的平均开销。目前，我们是用一连串 'if' 来根据命令选出正确的方法。为此，我们要引入二分法的概念。 没接触过这个原理的话，想象一下你在玩猜数字游戏：你要用尽可能少的次数，猜出在某个区间内随机选定的数字。最好的办法是把区间一分为二，报出中间的那个数，然后在新的区间里重复这个过程。

要使用这个技巧，你必须已经用上了上面讲的“用常量表示命令”。每个常量都应该是连续的自然数，除非你喜欢给自己找麻烦。

这样就可以借助三元运算符来使用二分法了：

function new_Object () { return @( function (@cmd) { return @( cmd < 4 ? cmd < 2 ? // 4/2 cmd < 1 ? // 2/2 CMD_0 : CMD_1 : cmd < 3 ? // 2 + 1 CMD_2 : CMD_3 : cmd < 6 ? // 4 + 4/2 cmd < 5 ? // 4 + 2/2 CMD_4 : CMD_5 : cmd < 7 ? // 4 + 2 + 1 CMD_6 : CMD_7 ); }); }

这是一个例子，有点难解释，跟着条件走一遍就明白了。每个 CMD_X 都可以替换成要返回的函数或属性。这样查找命令总是只需要 3 个操作数，而用 'if' 则需要 1 到 8 个操作数，平均 4.5 个。要算出二分法需要几层，可以计算 ceil(log2(n))，例如 n = 11 时：log2(11) = 3.46（四舍五入），即 ceil(3.46) = 4 层，你的第一个条件就是：cmd < 2^(4-1) 。

这个技巧的局限：你可能还不知道，访问数组要花 5 个操作数，而每个条件要花 1 个操作数，因此可以确定方法的数量上限，即 2^5 = 32。也就是说，如果你的方法不超过 16 个，就用二分法；否则就像这样使用数组：

function new_Object () { var this =@ [ 0 : CMD_0, 1 : CMD_1, 2 : CMD_2, 3 : CMD_3, 4 : CMD_4, 5 : CMD_5, 6 : CMD_6, 7 : CMD_7, // 等等…… ]; return @( this ); }

我承认这简单多了，但优化优先。

用 LeekScript 实现二叉搜索树

打开你的编辑器吧！

结构设计

首先，我们要定一份需求清单，搞清楚如何组织各个结构。我们需要： 给使用者的：

对使用者不可见的：

ABR（树）类的结构：

节点类的结构：

我没有加上后继函数，因为它只在删除时有用，而且它并不能满足需求（还需要父节点）。

创建 BST 类

我们沿用伪 OOP 一节中的结构。

// 添加常量，二分法稍后再加 // 我给它们加了前缀，以免冲突 global ABR_Search = 0; global ABR_Insert = 1; global ABR_Remove = 2;

function new_BST () { // 树的根（' = null' 其实没有用） // 另一种做法是给 new_BST 传一个值作为根，并用这个值创建节点 var _racine = null;

return @( function (@cmd) { // 每个函数都需要一个值，所以要返回一个需要参数的匿名函数 if (cmd === ABR_Search) return @(function (@v) {

}); if (cmd === ABR_Insert) return @(function (@v) {

}); if (cmd === ABR_Remove) return @(function (@v) {

}); }); }

创建 Node 类

这个类不能让使用者访问到。为此，它必须是属于 BST 类的一个函数：

function new_BST () { var new_Node = function (@_value) { // 需要一个参数，因为节点必须有值 // 不需要写 var v = value;，因为这个变量已经作为参数创建好了，写了也没区别 // 添加子节点 var _leftChild; var _rightChild;

return @( function (@cmd) { // 同样，要返回一个需要参数的匿名函数 if (cmd === ABR_Search) return @(function (@v) {

}); if (cmd === ABR_Insert) return @(function (@v) {

}); if (cmd === ABR_Remove) return @(function (@v) {

}); }); };

// BST 函数的其余部分写在下面 }

所有结构都搭好了，只差算法了

查找

这个方法我会用前面讲过的算法。

// BST 类： // …… if (cmd === ABR_Search) return @(function (@v) { // 也可以写成三元运算符，但在这里不会改变性能 if (_racine === null) return @false; else return @_racine(ABR_Search)(v); }); // ……

// Node 类： // …… if (cmd === ABR_Search) return @(function (@v) { if (_value < v) { if (_leftChild === null) return @false; else return @_leftChild(ABR_Search)(v); } else if (_value === v) return @true; else { if (_rightChild === null) return @false; else return @_rightChild(ABR_Search)(v); } }); // ……

插入

这个方法我会用前面讲过的算法。

// BST 类： // …… if (cmd === ABR_Insert) return @(function (@v) { if (_racine === null) _racine = new_Node(v); else _racine(ABR_Insert)(v); }); // ……

// Node 类： // …… if (cmd === ABR_Insert) return @(function (@v) { if (_value < v) { if (_leftChild === null) _leftChild = new_Node(v); else _leftChild(s)(v); } else { if (_rightChild === null) _rightChild = new_Node(v); else _rightChild(s)(v); } }); // ……

翻译成 LS 真的很简单。 但到了删除这一步，事情就复杂起来了…… [ Le Gentleman 正在撰写中…… ]