C++实现编译器(11): 闭包¶

参照《Writing An Interpreter/Compiler In Go》，改用C++实现。

项目源码: https://github.com/LeslieZhu/monkey-cpp

引言¶

本篇对应的源码位于目录: src/10/

闭包是迄今为止字节码编译器和虚拟机领域中最重要的功能之一。

比如:

let newAdder = fn(a){
    let adder = fn(b) { a + b; }
    return adder;
}

let addTwo = newAdder(2);

addTwo(3); // => 5

newAdder函数返回的adder就是闭包，因为它不仅有自己的参数b，还可以继续访问自己被定义时候的newAdder的参数a。

之前解释器中函数支持闭包是通过为函数添加一个env变量实现的:

struct Function : Object
{
    std::vector<std::shared_ptr<ast::Identifier>> Parameters;
    std::shared_ptr<ast::BlockStatement> Body;
    std::shared_ptr<Environment> Env;
    //...
};

这个env变量会指向函数定义时候的环境，从而在执行的时候，需要使用这个定义时的环境来执行。

但现在是通过编译器和虚拟机来实现闭包，它们是编译时与运行时的概念，迎来一系列的挑战。

自由变量与闭包函数对象¶

关于闭包实现的资料可供参考:

GNU Guile
Lua实现
Wren代码库
Matt Might关于编译闭包主题文章

自由变量既不是当前局部作用域中定义的变量，也不是当前函数的参数；不受当前作用域的约束。

自由变量是那些在局部使用但在封闭作用域内定义的变量。

不管函数是否是闭包，先把所有函数都变成闭包; 在编译函数时检查它是否有对自由变量的引用，如果有则将引用的值放到栈内，将值和编译后的函数放到一个闭包结构中，作为一个整体入栈。

struct Closure: Object
{
    std::shared_ptr<CompiledFunction> Fn;
    std::vector<std::shared_ptr<Object>> Free;

    Closure(std::shared_ptr<CompiledFunction> fn): Fn(fn){}
    virtual ~Closure(){}

    virtual ObjectType Type() { return ObjectType::CLOSURE; }
    virtual std::string Inspect()
    {
        std::stringstream oss;
        oss << "Closure[" << this << "]";
        return oss.str();
    }
};

struct Frame{
    // std::shared_ptr<objects::CompiledFunction> fn;
    std::shared_ptr<objects::Closure> cl;

    int ip;
    int basePointer;

    //...

    bytecode::Instructions Instruction()
    {
        // return fn->Instructions;
        return cl->Fn->Instructions;
    }
};

这里的Free相当于一个env角色；为了将函数编译成闭包，需要新增操作码:

{OpcodeType::OpClosure, std::make_shared<Definition>("OpClosure", std::vector<int>{2, 1})},

OpClosure有两个操作数，第1个操作数用于找到函数本体，第2个操作数用于标记有多少个自由变量。

函数变闭包¶

假设所有函数都有0个自由变量，即OpClosure第二个操作数是0；同时，之前编译函数后使用的OpConstant指令需要都换成OpClosure指令:

//emit(bytecode::OpcodeType::OpConstant, {pos});
emit(bytecode::OpcodeType::OpClosure, {pos, 0});

case bytecode::OpcodeType::OpClosure:
    {
        uint16_t constIndex;
        bytecode::ReadUint16(instructions, ip+1, constIndex);
        frame->ip += 2;

        uint8_t numFree;
        bytecode::ReadUint8(instructions, ip+3, numFree);
        frame->ip += 1;

        auto result = PushClosure((int)constIndex);
        if(objects::isError(result))
        {
           return result;
        }
    }
    break;


std::shared_ptr<objects::Object> PushClosure(int constIndex)
{
    auto constant = constants[constIndex];
    auto compiledFn = std::dynamic_pointer_cast<objects::CompiledFunction>(constant);
    if(compiledFn == nullptr)
    {
        return objects::newError("not a function: " + constant->Inspect());
    }

    auto closure = std::make_shared<objects::Closure>(compiledFn);

    return Push(closure);
}

想象一下，代码被编译器编译的时候，已经有了函数字节码对象作为常量存储着，然后知道它的索引是N，那么主程序字节码只需要一个OpClosure指令即可，带上两个操作数，第1个是函数本体的索引；等到虚拟机去执行的时候，解压遇到OpClosure指令，根据操作数获取一个函数本体，打包为一个闭包，入栈即可。

相应的OpCall调用的对象就是闭包或内置函数了，不会直接调用函数本体:

std::shared_ptr<objects::Object>  executeCall(int numArgs)
{
    auto fnObj = stack[sp - 1 - numArgs];

    if(fnObj->Type() == objects::ObjectType::CLOSURE)
    {
        //auto compiledFnObj = std::dynamic_pointer_cast<objects::CompiledFunction>(fnObj);
        //return callFunction(compiledFnObj, numArgs);

        auto closureFn = std::dynamic_pointer_cast<objects::Closure>(fnObj);        
        return callClosure(closureFn, numArgs);
    }
    else if(fnObj->Type() == objects::ObjectType::BUILTIN)
    {
        auto builtinFnObj = std::dynamic_pointer_cast<objects::Builtin>(fnObj);
        return callBuiltin(builtinFnObj, numArgs);
    }
    else
    {
        return objects::newError("calling non-function and non-built-in");
    }
}

对于没有自由变量的普通函数，它目前工作良好。

编译与解析自由变量¶

新增一种编译作用域，叫自由变量作用域:

namespace SymbolScopeType
{
    const SymbolScope GlobalScope = "GLOBAL";
    const SymbolScope LocalScope = "LOCAL";
    const SymbolScope BuiltinScope = "BUILTIN";
    const SymbolScope FreeScope = "FREE";
}

符号表中需携带一个自由变量清单:

struct SymbolTable{
    std::shared_ptr<SymbolTable> Outer;
    std::map<std::string, std::shared_ptr<Symbol>> store;
    int numDefinitions;

    std::vector<std::shared_ptr<Symbol>> FreeSymbols;
    //...
};

编译器在编译函数的时候，本身已经有一个符号表了，这个符号表记录了它的局部变量，现在在这个符号表内部添加了一个存储空间来存储自由变量:

std::shared_ptr<Symbol> DefineFree(std::shared_ptr<Symbol> original)
{
    // 记录最原始信息
    FreeSymbols.push_back(original);

    // 第三个参数index使得可以通过2次跳转找到最原始的符号信息
    auto symbol = std::make_shared<Symbol>(original->Name, SymbolScopeType::FreeScope ,FreeSymbols.size() - 1);
    store[original->Name] = symbol;
    return symbol;
}

std::shared_ptr<Symbol> Resolve(std::string name)
{
    auto fit = store.find(name);
    if(fit != store.end())
    {
        return fit->second;
    }
    else if(Outer != nullptr)
    {
        auto obj = Outer->Resolve(name);
        if(obj == nullptr)
        {
            return obj;
        }

        if(obj->Scope == SymbolScopeType::GlobalScope || obj->Scope == SymbolScopeType::BuiltinScope)
        {
            return obj;
        }

        // 注册自由变量
        auto free = DefineFree(obj);
        return free;
    }
    else
    {
        return nullptr;
    }
}

判断函数里面的自由变量就是看它是否是局部变量，如果不是，那么从外部查找，找到后发现它不是全局变量或内置变量，那么就是外部局部变量，即自由变量。

编译函数的时候，需要在函数本体前面把自由变量提前编码:

//...
if(!lastInstructionIs(bytecode::OpcodeType::OpReturnValue))
{
    emit(bytecode::OpcodeType::OpReturn);
}

// 获取编译好的函数自由变量
auto freeSymbols = symbolTable->FreeSymbols;

auto numLocals = symbolTable->numDefinitions;
auto numParameters = funcObj->v_pParameters.size();
auto ins = leaveScope();

// 首先编码自由变量
for(auto &sym: freeSymbols)
{
    loadSymbol(sym);
}

auto compiledFn = std::make_shared<objects::CompiledFunction>(ins, numLocals, numParameters);
auto pos = addConstant(compiledFn);

//emit(bytecode::OpcodeType::OpConstant, {pos});
emit(bytecode::OpcodeType::OpClosure, {pos, static_cast<int>(freeSymbols.size())});

在loadSymbol中新增了OpGetFree获取自由变量。

虚拟机运行时重建闭包对象¶

现在函数编译后的字节码存储顺序如下:

OpGetFree 0,OpGetFree 1,...,OpGetFree N,OpClosure,FnIndex,N-Free

虚拟机解码字节码的时候构建调用栈情况如下:

LocalN
...
Local2
Local1 --->函数本体中有局部变量N，根据基指针借用
ArgN
...
Arg2
Arg1 --> 函数本体中有参数个数N，基指针往后N个借用空间用于函数执行时使用
CompiledFunction ---> 根据常量索引找到函数本体，其位置是基指针
FreeN ---> 通过OpClosure知道有N个自由变量，那么基指针往前N个直接拿
....
Free2
Free1
函数之前的其它对象, 函数执行后栈指针回到这里

解码OpGetFree指令读取自由变量:

case bytecode::OpcodeType::OpGetFree:
      {
          uint8_t freeIndex;
          bytecode::ReadUint8(instructions, ip+1, freeIndex);
          frame->ip += 1;

          auto currentClosure = frame->cl;

          // 读取闭包自由变量值
          auto result = Push(currentClosure->Free[freeIndex]);
          if(objects::isError(result))
          {
             return result;
          }
      }
      break;

打包函数为闭包部分需要包含自由变量:

case bytecode::OpcodeType::OpClosure:
    {
        uint16_t constIndex;
        bytecode::ReadUint16(instructions, ip+1, constIndex);
        frame->ip += 2;

        uint8_t numFree;
        bytecode::ReadUint8(instructions, ip+3, numFree);
        frame->ip += 1;

        auto result = PushClosure((int)constIndex, (int)numFree);
        if(objects::isError(result))
        {
           return result;
        }
    }

std::shared_ptr<objects::Object> PushClosure(int constIndex, int numFree)
{
    auto constant = constants[constIndex];
    auto compiledFn = std::dynamic_pointer_cast<objects::CompiledFunction>(constant);
    if(compiledFn == nullptr)
    {
        return objects::newError("not a function: " + constant->Inspect());
    }

    // 从调用栈读取所有自由变量
    std::vector<std::shared_ptr<objects::Object>> free(numFree);
    for(int i = 0; i < numFree; i++)
    {
        free[i] = stack[sp - numFree + i];
    }

    // 调用栈指针归位
    sp -= numFree;

    auto closure = std::make_shared<objects::Closure>(compiledFn, free);

    return Push(closure);
}

递归闭包¶

函数递归调用:

let countDown = fn(x){
    if(x == 0){
       return 0;
    } else {
       countDown(x - 1);
    }
}

let wrapper = fn(){
    countDown(1);
}

wrapper();

因为这个countDown函数调用了自己，那么在这个函数必须进行编译的时候必须先把它加入到符号表，否则编译时会找不到自己:

    else if(node->GetNodeType() == ast::NodeType::LetStatement)
    {
         std::shared_ptr<ast::LetStatement> letObj = std::dynamic_pointer_cast<ast::LetStatement>(node);
+
+        // 对函数内部来说，函数名是外部变量了，自然可以访问到
+        auto symbol = symbolTable->Define(letObj->pName->Value);
+
         auto resultObj = Compile(letObj->pValue);
         if (objects::isError(resultObj))
         {
              return resultObj;
         }

-        auto symbol = symbolTable->Define(letObj->pName->Value);
+        // auto symbol = symbolTable->Define(letObj->pName->Value);

         //....
     }

只是调整了函数名进入符号表的时机就可以解决上面这种简单函数递归调用，但面对递归闭包的时候，比如:

let wrapper = fn(){
    let countDown = fn(x){
         if(x == 0){
             return 0;
         } else {
             countDown(x - 1);
         }
    };

    countDown(1);
};

wrapper();

在这个例子里面虽然还是调用countDown函数，但区别是这个函数是定义在wrapper自己内部的，即这个闭包是递归的。

目前它不能运行，因为对于递归闭包还支持不好，虚拟机执行的时候会报错，但查看编译器的编码:

0000 OpGetLocal 0    ===> 这里造成错误
0002 OpClosure 3 0
0006 OpSetLocal 0
0008 OpGetLocal 0
0010 OpConstant 4
0013 OpCall 1
0015 OpReturnValue

因为countDown编译的时候发现调用了自己，而函数自己本身还没有编译好，因此它被当做了自由变量。在闭包函数之前会把自由变量入栈，但这个入栈的东西其实还没有定义好。

记录函数名字¶

std::shared_ptr<ast::LetStatement> parseLetStatement()
{
    std::shared_ptr<ast::LetStatement> pStmt = std::make_shared<ast::LetStatement>();
    pStmt->Token = curToken;

    if (!expectPeek(token::types::IDENT))
    {
        return nullptr;
    }

    pStmt->pName = std::make_shared<ast::Identifier>(curToken, curToken.Literal);

    if (!expectPeek(token::types::ASSIGN))
    {
        return nullptr;
    }
    nextToken();

    pStmt->pValue = parseExpression(Priority::LOWEST);

    // 如果是用let定义函数，则记下函数名字，方便后续检查是否自引用
    if(pStmt->pValue->GetNodeType() == ast::NodeType::FunctionLiteral)
    {
        auto fl = std::dynamic_pointer_cast<ast::FunctionLiteral>(pStmt->pValue);
        fl->Name = pStmt->pName->Value;
    }

    if (peekTokenIs(token::types::SEMICOLON))
    {
        nextToken();
    }

    return pStmt;
}

编译自引用¶

编译函数的时候，进入函数内部作用域后，第一步是让函数名本身占据符号表最开始的位置:

std::shared_ptr<Symbol> DefineFunctionName(std::string name)
{
    auto symbol = std::make_shared<Symbol>(name, SymbolScopeType::FunctionScope ,0);
    store[name] = symbol;
    return symbol;
}

//...
else if(node->GetNodeType() == ast::NodeType::FunctionLiteral)
{
    std::shared_ptr<ast::FunctionLiteral> funcObj = std::dynamic_pointer_cast<ast::FunctionLiteral>(node);

    enterScope();

    // 实际上等于函数名本身不会是自由变量了
    // 而是局部变量，但属于FunctionScope
    if(funcObj->Name != "")
    {
        symbolTable->DefineFunctionName(funcObj->Name);
    }

    for(auto &args: funcObj->v_pParameters)
    {
        symbolTable->Define(args->Value);
    }
    //...
}

//...
else if(node->GetNodeType() == ast::NodeType::Identifier)
{
    std::shared_ptr<ast::Identifier> identObj = std::dynamic_pointer_cast<ast::Identifier>(node);
    auto symbol = symbolTable->Resolve(identObj->Value);
    if(symbol == nullptr)
    {
        return objects::newError("undefined variable " + identObj->Value);
    }

    loadSymbol(symbol);
}

这样在函数体内部编译的时候，遇到自引用情况时，它会找到函数名在符号表中的索引位置，并发出获取它的指令，但因为它已经被定义为FunctionScope了，会使用OpCurrentClosure指令，而不是之前的OpGetFree指令。

虚拟机对OpCurrentClosure的处理:

case bytecode::OpcodeType::OpCurrentClosure:
      {
          auto currentClosure = frame->cl;
          auto result = Push(currentClosure);
          if(objects::isError(result))
          {
             return result;
          }
      }
      break;

总结¶

闭包是比较难理解和难实现的功能，尤其是需要在编译时和运行时两个不同阶段处理却又要能够正常运行时，再加上嵌套递归闭包，那不同的实现方式对于执行速度影响会非常大。

本文作者：「吴羽舒(LeslieZhu) 」创作于Saturday, December 17, 2022，共2647字，需要14分钟阅读时间
微信搜索： 「 MinYiLife 」, 关注公众号!
本文链接： https://www.lesliezhu.com/blog/2022/12/17/writing_an_interpreter_in_cpp_11/
版权声明： 原创文章，如需转载请注明文章作者和出处。谢谢！