语句求值2

25 min read
编译原理解释器面向对象原型链

1 面向对象概述

面向对象是一个复杂的概念,我们的语言中想要实现两个重要的面向对象特性:继承和多态。在语法分析章节中,我们支持了class的声明和创建new语法如下:

// class中由多个赋值表达式组成,如果赋值的是函数类型,则该函数的this指向实例对象,super指向父类
// constructor是一个预留的函数名,为构造方法,该方法必须以`super()`开头,调用父类的构造方法
class Person {
    age = 10;
    constructor = function(name, age) {
        super();
        this.name = name;
        this.age = age;
    }
    say = function() {
        print(this.name+ " is "+ this.age + " years old.");
    }
}

new Person("John", 20).say();

面向对象有两种主要的实现方式:classprototype,前者最为常见,大多数面向对象语言都采用了class形式实现。

1.1 class形式

以java为例,先来思考这段代码的打印结果

class A {
    int age = 1;
    public void printAge() {
        System.out.println(this.age);
    }
}

class B extends A {
    int age = 2;
    public void printAge() {
        super.printAge();
        System.out.println(this.age);
    }
}

new B().printAge();

打印结果为1 2也就是B这个对象中存储了两个age字段,使用lucene-core打印System.out.println(RamUsageEstimator.shallowSizeOf(new B()));结果为24(对象头8+4 两个age 4+4,取整得到24),如果只有一个age的话是16.

<dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-core</artifactId>
    <version>6.6.1</version>
</dependency>

上面例子说明两个事情:

  • 1 java同名方法会动态调用,也就是多态特性,b对象先到自己的类元信息中找printAge方法找到了就用自己这个方法的。
  • 2 与方法不同字段是静态绑定的,super.printAge找到了A的printAge方法,这里打印的是A类中的age=1,也就是当前对象有A#ageB#age,在A类中的方法的this.age指向的其实是this.A#age

他的实现原理大概是,b对象的对象头有Klass point指向B这个类的元数据信息,这些信息包括了B这个类的父类、接口、字段、方法等信息,而在new B()的时候,会根据这个元数据信息来创建一个B类的对象,然后把B类的对象赋值给b变量,创建对象要知道对象到底占用内存有多大,需要遍历B类的所有父类,按顺序排列所有的字段,对象类型是4字节引用,其他基础类型按照各自大小计算,这样就把每个字节紧凑排列起来了。换句话说b对象里存的俩age是12这个挨着的8个字节存放的,而具体前四个字节是A#age后四个是B#age,则是按照元数据信息顺序算出来的。

class形式非常简单、清晰。

1.2 prototype形式

prototype是另一种实现面向对象的方式,比较少见,我知道的只有js采用了这种设计,这个很不一样的设计,也是前端面试中一个重要的考点,就是原型链。那我们就先来看一下js的原型链是如何设计的,这次我们站在语言实现者的角度来思考这个问题,不再纠结如何背原型链的面试题,而是彻底搞懂为什么要这么设计,他与class的实现有什么区别。

js中几乎一切数据都是对象Object,而对象中有默认的内置属性[[Prototype]],在大多数浏览器中可以通过.__proto__查看这个内置属性,例如一个普通对象{},他的__proto__信息如下,可以看到原型本身就是一个普通对象,当前这个对象原型中封装了包括toString在内的多个方法,并且在constructor属性我们看到了f Object(),这是因为这个原型其实就是基础的Object的原型,当我们调用x.toString()返回的字符串是[object Object],这就是基础的Object默认的toString方法的返回结果。

img

image

当我们调用x.toString()的时候,会先从x这个对象自身的字段中寻找有没有toString属性,这列是空{}对象所以没有,接下来就会从x.[[Prototype]]找有没有这个属性,发现是有这个方法,就会调用这个方法,并将方法中的this指向当前对象x,所以x.toString()返回的字符串是[object Object],如果我们将x.__proto__.toString重写如下,会发现修改的是Object的原型,进而导致其他的对象的toString也会被修改,这侧面也印证了所以的基础对象的[[Prototype]]指向的都是一个单例的对象。

image

img

上面例子我们知道了所有的对象创建都是有[[Prototype]]原型属性的,默认都是指向一个单例的普通对象,该对象中有toString等方法。接下来我们来看数字类型的原型,如下,数字类型的原型与普通对象原型不同,是一个新的原型,这个原型的原型是指向对象原型的,这就是所谓的原型链。

img

另外是this关键字,在obj.method运行时this指向到obj

img

对比class我们会发现这里的[[Prototype]]class非常类似,都存储了一些方法(所以以前java metaspace叫方法区),而当一个对象调用方法的时候,会先从当前class/[[Prototype]]去找,找不到就找ParentClass/原型的原型。而class方法中有一个特殊的字段叫做this指向的就是当前对象,通过this.xxx可以获取当前对象的field或运行当前对象的方法。这是相同点,接下来说一下不同点。

一个非常核心的不同点是class会存储字段信息,而[[Prototype]]如上图只存储了方法,当然我们说原型就是一个普通对象,你可以用它来存储字段,但是他与class存储的字段信息是不一样的,class的字段信息是字段名字段类型等元信息,而[[Prototype]]作为一个普通对象存储的是k=v,所以如果在原型中设置了字段值,那么会对持有该原型的所有对象生效,有点类似java中类的静态字段,当然如果原型中的方法没有使用this的话,这个方法其实也就是一个静态方法了,因为与对象无关,纯粹的函数。话说回来,原型中不记录field元信息会导致什么实质的不同呢?

class中举的B extends A为例,BA都有age字段为例,在js中相同的代码,会发现对象b中只有一份age,使用super.printAge打印的结果也是2。这正是因为原型中没有存储字段元信息,字段的kv都是直接存储在当前对象中的,所以当前对象中k为age的只有一个数,在构造方法中B的构造方法会先调用A的构造方法把age赋值1,然后调用B的构造方法把age赋值2,后续使用打印的this.age是找到当前对象唯一的一个age属性也就是会打印两遍2,这就是js原型与javaclass最核心的不同点。(字段只有一份,因而js中super.field是非法的只有super.method()

img

这种设计带来了灵活性,也就是我们可以用原型来存储方法信息,然后对象本身的kv就是一个动态的map结构,这样我们可以在对象上面无限动态追加属性。(Number/String等内置的基础类型除外,因为这些类型的赋值语句被js sdk修改过,动态的赋值会被忽略,以避免覆盖一些重要的方法或属性)

image

image

1.2.1 prototype与function

jsES6之前是不支持class这个关键字的,起码浏览器中以前是不支持的,也是近些年才支持了class关键字,而这个class的写法是function写法的语法糖,本质上其实是function写法,为什么是function写法呢?因为像前面提到的对象的原型,Number的原型,这些原型本身也是一个对象,这些原型又该如何存储呢?new Object()或者new Number(1)的时候需要把这个对象拿过来,塞到new出来的对象的[[Prototype]]中。而函数就是最佳的载体,new Number(1)中可以看到是有入参的,只有函数能最小改动的来接受入参,并返回一个返回值。所以就设置了这样一个函数function Number(value){},那Number(1)new Number(1)有什么区别呢?下面这个图展示了Number类型的实现方式,可以看到直接运行MyNumber方法就可以得到一个数字了,为什么需要new呢?

image

这是因为js为了更高的灵活性,在Function类型中设置了一个普通属性prototype,这个命名很容易让人误解,虽然他也是原型这个单词,但是他并不是原型,而是函数的一个普通属性,[[Prototype]]才是对象的原型,prototype这个属性的作用是当运行new Func()的时候,会先运行Func()函数,如果Func()有返回值,那么就直接返回了,而如果没有返回值的时候,才是new发挥作用的时候,此时会创建一个空对象,并将对象的[[Prototype]]赋值为Func.prototype,并且将这个空对象作为Func()函数的this,然后运行Func()函数,最后将这个this作为new Func()的返回值。是不是有点绕,看个例子。

var MyNumber = function(value) {
    this.valueOf = function() { return value};
}
MyNumber.prototype = Number.prototype;
const num = new MyNumber(100);

console.log(num instanceof MyNumber);  // true instanceof原理就是判断原型链上有没有MyNumber.prototype
console.log(num instanceof Number);    // true
console.log(num + 100); // 200

image

有些类型检测的代码不用instanceof而是obj.constructor === MyNumber,所以最好把构造方法也指向自己

var MyNumber = function(value) {
    this.valueOf = function() { return value};
}
MyNumber.prototype = Object.create(Number.prototype); // 创建一个新对象,新对象原型指向Number.prototype
MyNumber.prototype.constructor = MyNumber;
const num = new MyNumber(100);

了解了上述原理,可以去验证任意对象的__proto__一定是等于该对象类型的prototype的,因为对象类型在js中其实就是函数,例如Object Number String Function等本身也都是函数,这些函数大都是Native代码实现了,因为得先有底层语言封装基础的数据结构,才能再后续封装js自己的sdk

image

1.2.3 注意

上面我们大量使用了__proto__语法,和直接修改原型,这是比较不建议的,首先是__proto__语法在一些运行时并不支持,可能需要替换为Object.getPrototypeOf()来获取对象的原型,Object.setPrototypeOf(obj, newPro)来设置。设置的时候需要注意安全,就像一开始的例子中我们直接把Object.prototypetoString修改了,这会导致所有对象运行toString都被篡改了。另外一般来说我们不要直接把自己的对象的的原型直接赋值为基础类型的原型,因为我们自己对象如果修改原型会导致把基础类型的原型也给改了,一个建议的做法是使用MyNumber.prototype = Object.create(Number.prototype),这个方法是创建一个新对象,新对象的原型指向Number.prototype,这样套一层就可以有效避免前面的问题。以下两种写法基本等价。

// es5写法
var MyNumber1 = function(value) {
    this.valueOf = function() { return value}; 
}
MyNumber1.prototype = Object.create(Number.prototype); // 创建一个新对象,新对象原型指向Number.prototype
MyNumber1.prototype.constructor = MyNumber;

// es6写法
class MyNumber2 extends Number {
}

好了,到这里我想你应该理解透了js的原型链了,一种方法是动态绑定,字段也是动态绑定的面向对象的实现方式。

2 用原型实现面向对象

在我们的语言中,我打算用原型来实现面向对象,因为他具有更高的灵活性,非常适合动态语言;能帮助我们更好的复习js原型链的知识;另外再实现难度上与class相差无几,但是更有趣。

我们的语言中所有的数据都是Element,并且我们已经对普通字段使用Map结构存储了kv了,就差往Element中添加存储方法的原型了,我们新增一个$$pro$$属性作为对象的原型,存储方法的元数据,并且在运行obj.method()时,先判断obj.method是否存在,不存在,则从obj.$$pro$$中查找method,还不存在则从obj.$$pro$$.get("$$pro$$")中继续查找,接下来是obj.$$pro$$.get("$$pro$$").get("$$pro$$"),依次往上直到为null。代码如下,在Element中添加了$$pro$$,这是一个Map,新增了setPro方法设置原型内容,修改了get方法,

export class Element {
    constructor(type) {
        this.type = type;
        // 普通对象的属性存到map
        this.map = new Map();
        // 类的属性存到pro
        this.$$pro$$ = new Map();
        this.$$pro$$.set("$$pro$$", new Map());
    }
    setPro(key, value) {
        this.$$pro$$.set(key, value);
    }
    set(key, value) {
        this.map.set(key, value);
    }
    get(key) {
        if (key == "type") return new StringElement(this.type);
        // 先从map中找
        if (this.map.get(key) != undefined) {
            return this.map.get(key);
        }
        // 再从原型中找
        if (this.$$pro$$.get(key) != undefined) {
            return this.$$pro$$.get(key);
        }
        // 原型链向上搜索
        var pro = this.$$pro$$.get("$$pro$$")
        while (pro != undefined) {
            if (pro.get(key) != undefined) {
                return pro.get(key);
            }
            pro = pro.get("$$pro$$");
        }
        // 最后还没找到返回nil
        return nil;
    }
    toString() {
        return `{ ${Array.from(this.map.entries()).map(it=>it[0]+":"+it[1].toString()).join(',')} }`;
    }
    toNative() {
        function elementToJsObject(element) {
            if (element instanceof Element) {
                switch(element.type) {
                    case "number":
                    case "boolean":
                    case "null":
                    case "string":
                    case "array":
                        return element.toNative();
                    default:
                        var iter = element.map.keys();
                        var res = {};
                        var item;
                        while (!(item = iter.next()).done) {
                            var key = item.value;
                            res[key] = elementToJsObject(element.map.get(key))
                        }
                        return res;
                }
            }
            return element;
        }
        return elementToJsObject(this);
    }
}

接下来就是实现ClassStatementNewAstNode的解析了,class语句的作用是创建一种类型,而“类型”也要作为一种数据结构,这里我们可以叫ClassElement,但是因为我们整体思路是原型链,所以就叫ProtoElement吧:

export class ProtoElement extends Element {
    // className: string;
    // parent: ProtoElement | null;
    // methods: Map<String, FunctionElement>;
    constructor(className, parent, methods) {
        super();
        this.className = className;
        // 如果有父类,则作为原型链存储
        if (parent != undefined) {
            this.setPro("$$pro$$", parent.$$pro$$);
        }
        if (methods) {
            methods.forEach((v, k) => {
                this.setPro(k, v ? v : nil);
            })
        }
    }
    toString() {
        return "PROTOTYPE"
    }
}

然后ClassStatement中的作用就是在当前上下文中创建一个变量,变量名就是类名,变量值就是一个ProtoElement

function evalStatement(statement, ctx) {
    //..........
    else if (statement instanceof ClassStatement) {
        var parent =  null;
        if (statement.parentIdentifierAstNode) {
            parent = ctx.get(statement.parentIdentifierAstNode.toString());
            if (!(parent instanceof ProtoElement)) {
                throw new RuntimeError("parent class " + 
                    statement.parentIdentifierAstNode.toString() + " must be a class")
            }
        }
        var className = statement.nameIdentifierAstNode.toString();
        // 在语法分析中,我们已经把类中的字段赋值的语法糖写法,转为了在constructor中赋值,所以类中只有方法。
        ctx.set(className, new ProtoElement(className, parent, statement.methods, ctx))
    } 
    //...........
}

然后是NewAstNode的解析,按照js的思路,先创建一个空对象,将该对象的原型指向类型的原型,将this指向该对象,this可以访问字段和方法,将super指向父类原型,super只能调用方法,接下来运行构造方法,将this返回。

function evalExpression(exp, ctx) {
    // .........
    if (exp instanceof NewAstNode) {
        var className = exp.clsIdentifierAstNode.toString();
        var args = exp.args.map((arg) => evalExpression(arg, ctx));
        var clsElement = ctx.get(className);
        if (!(clsElement instanceof ProtoElement)) throw new RuntimeError(`${className} is not a class`);
        // 1 创建空对象
        var _this = new Element(className);
        // 2 当前对象原型 指向 类的原型
        var curClsPro = _this.$$pro$$ = clsElement.$$pro$$;
        var parentClsPro = curClsPro.get("$$pro$$"); 
        // 3 this指向空对象,super指向一个只有父类方法(原型)的对象,这样super.只能调用父类方法
        var _super = new Element();
        _super.$$pro$$ = parentClsPro ? parentClsPro : new Map();


        // 4 运行构造方法,原型链一直往上找constructor构造方法,如果全都没有的话,就不执行任何操作
        if (clsElement.get("constructor") && clsElement.get("constructor") != nil) {
            if (!(clsElement.get("constructor") instanceof FunctionElement)) throw new RuntimeError(`${className}.constructor is not a function`); 
            // 运行构造方法,这里用到了call方法的第三第四个参数分别为this和super的指向
            clsElement.get("constructor").call("constructor", args, _this, _super, exp);
        }
        return _this;
    }
    // .........
}

上面构造方法的调用中使用到了_this_super,之前在函数的call方法中就有声明,这里重新回看一下如下,在函数执行的上下文newCtx中设置了thissuper来指向传入的_this_super,这样我们在构造方法中使用this.a = 1这种语法的时候,就会能把_this这个空Element中设置属性a=1了,整体思路与js一致。

// FunctionElement没有改动,只是回看一下_this和_super的处理。
export class FunctionElement extends Element {
    constructor(params, body, closureCtx) {
        super('function');
        this.params = params;
        this.body = body;
        this.closureCtx = closureCtx;
    }

    toString() {
        return `FUNCTION`
    }

    // name: string, args: Element[], _this: Element, _super: Element, exp: 打印异常堆栈相关
    call(name, args, _this, _super, exp) {
        var newCtx = new Context(this.closureCtx);
        if (_this) {
            newCtx.set("this", _this);
        }
        if (_super) {
            newCtx.set("super", _super);
        }
        newCtx.funCtx.name = name;
        this.params.forEach((param, index) => {
            newCtx.set(param, args[index] ? args[index] : nil);
        });
        try {
            evalBlockStatement(this.body, newCtx);
        } catch (e) {
            if (e instanceof RuntimeError) {
                if (e.element instanceof ErrorElement) {
                    e.element.updateFunctionName(name);
                    e.element.pushStack({position: `${exp.token.line}:${exp.token.pos}`})
                }
            }
            throw e;
        }
        return newCtx.funCtx.returnElement =  newCtx.funCtx.returnElement ?  newCtx.funCtx.returnElement : nil;
    }
}

函数调用FunctionCallAstNode求值的部分也要修改,之前只考虑了普通方法名直接调用的情况。

    // 函数调用
    else if (exp instanceof FunctionCallAstNode) {
        var funcExpression = exp.funcExpression;
        // 去掉冗余的组
        while (funcExpression instanceof GroupAstNode) {
            funcExpression = funcExpression.exp;
        }
        var fname = null, _this = nil, _super = nil, funcElement = nil;
        // 全局方法
        if (funcExpression instanceof IdentifierAstNode) {
            fname = funcExpression.toString();
            // 注入一个print函数,来辅助调试
            if (fname == 'print') {
                console.log(...(exp.args.map((arg) => evalExpression(arg, ctx).toNative())));
                return nil;
            }
            if (fname == 'error') {
                if (exp.args.length == 0) {
                    throw new RuntimeError("error() takes at least 1 argument",`${exp.token.line}:${exp.token.pos}`);
                }
                var msg = evalExpression(exp.args[0], ctx);
                if (!(msg instanceof StringElement)) {
                    throw new RuntimeError("msg should be a String",`${exp.token.line}:${exp.token.pos}`);
                }
                return new ErrorElement(msg.toNative());
            }
            funcElement = evalExpression(funcExpression, ctx);
        } 
        // 对象方法
        else if (funcExpression instanceof InfixOperatorAstNode) {
            // xx.method() => 先对xx求值,结果赋值给_this;然后找到method这个functionElement
            if ((funcExpression.op.type === LEX.POINT && funcExpression.right instanceof IdentifierAstNode) ||
            (funcExpression.op.type === LEX.LBRACKET && funcExpression.right instanceof StringAstNode)) {
                _this = evalExpression(funcExpression.left, ctx)
                funcElement = _this.get(funcExpression.right.toString());
                fname = funcExpression.right.toString();
                var curClsPro = _this.$$pro$$;
                var parentClsPro = curClsPro ? curClsPro.get("$$pro$$") : null;
                _super = new Element(); // 临时的
                _super.$$pro$$ = parentClsPro ? parentClsPro : new Map();
                // super比较特殊,调用super.xx的时候,父类方法中的this指向自身,而是指向当前的对象
                if (funcExpression.left.toString() === 'super') {
                    _this = ctx.get("this");
                }
            } else {
                throw new RuntimeError("Method format invalid");
            }
        }
        // 其他形式,例如 "b()()",函数的返回值也是个函数,直接去调用
        else {
            funcElement = evalExpression(funcExpression, ctx);
        }
        if (funcElement instanceof FunctionElement) {
            return funcElement.call(fname, exp.args.map((arg) => evalExpression(arg, ctx)), _this, _super, exp);
        } else if (funcExpression.right && funcExpression.right.toString() == "constructor") {
            // 默认构造方法,啥也不做
            return nil;
        } else {
            throw new RuntimeError(`${funcExpression.toString()} is not a function`,`${exp.token.line}:${exp.token.pos}`);
        }
    }

这样我们如果运行如下代码,可以看到都正常打印了。

image

继承与多态的体现:

image

好了到此为止我们已经把面向对象的章节写完了,虽然有些地方,例如constructor super的处理,有些hard-code,但是总体还是比较通俗易懂。我们的语言已经越来越强大了,接下来还剩下最后一块拼图了,就是原生SDK的支持,例如我们的基础Element,像StringElementArrayElement需要有一些内置的方法实现,比如对于String来说,因为目前是用js封装的内部对象StringElement,所以没办法在我们的语言中直接调用split join等方法,Array也是同理,push/pop没有办法直接调用,我们将在下一节,来完善基础的String/Array的内置方法,并增加Math/Time的基础库来做基本的数学运算,增加Json库处理json文本与Element的转换,增加Http库进行restful请求,以及File库来处理文件读写。