Skip to content

Commit 5ac89a1

Browse files
BowenFuBowenFu
authored
Support closures. (#40)
* Add test. * closure. * closure. * SymbolTable. * comment out test. * assert. * Fix mem issue. Co-authored-by: Bowen Fu <missing>
1 parent e420db0 commit 5ac89a1

File tree

7 files changed

+298
-92
lines changed

7 files changed

+298
-92
lines changed

‎core.lisp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -237,3 +237,5 @@
237237
)
238238

239239
(define (even num) (= (% num 2) 0))
240+
241+
(define (my-cons car cdr) (lambda (dispatch) (if (= dispatch 'my-car) car cdr)))

‎include/lisp/compiler.h

Lines changed: 100 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -9,59 +9,130 @@ enum class Scope
99
{
1010
kLOCAL,
1111
kGLOBAL,
12-
kFUNCTION_SELF_REF
12+
kFUNCTION_SELF_REF,
13+
kFREE
1314
};
1415

1516
class CurrentFunctionIndex
1617
{};
1718

1819
inline constexpr CurrentFunctionIndex currentFunctionIndex{};
1920

21+
using VarInfo = std::pair<size_t, Scope>;
22+
class SymbolTable
23+
{
24+
std::map<std::string, VarInfo> mNameToVarInfo{};
25+
std::vector<VarInfo> mOrigFreeVars{};
26+
size_t mNbDefinitions{};
27+
SymbolTable* mEnclosing{};
28+
public:
29+
SymbolTable() = default;
30+
SymbolTable(SymbolTable* const enclosing)
31+
: mEnclosing{enclosing}
32+
{}
33+
auto extend()
34+
{
35+
return SymbolTable(this);
36+
}
37+
auto defineFreeVar(std::string const& name, VarInfo const& orig)
38+
{
39+
auto freeIndex = mOrigFreeVars.size();
40+
mOrigFreeVars.push_back(orig);
41+
auto const freeVar = VarInfo{freeIndex, Scope::kFREE};
42+
mNameToVarInfo[name] = freeVar;
43+
return freeVar;
44+
}
45+
std::optional<VarInfo> resolve(std::string const& name)
46+
{
47+
// found
48+
auto const& map = mNameToVarInfo;
49+
auto const iter = map.find(name);
50+
if (iter != map.end())
51+
{
52+
return iter->second;
53+
}
54+
55+
// enclosing
56+
if (mEnclosing)
57+
{
58+
auto const opVarInfo = mEnclosing->resolve(name);
59+
if (opVarInfo.has_value())
60+
{
61+
auto const varInfo = opVarInfo.value();
62+
if (varInfo.second == Scope::kGLOBAL)
63+
{
64+
return varInfo;
65+
}
66+
return defineFreeVar(name, varInfo);
67+
}
68+
}
69+
70+
return {};
71+
}
72+
73+
VarInfo define(std::string const& name, Scope scope)
74+
{
75+
auto const index = mNbDefinitions;
76+
auto const varInfo = VarInfo{index, scope};
77+
mNameToVarInfo[name] = varInfo;
78+
++mNbDefinitions;
79+
return varInfo;
80+
}
81+
auto freeVariables() const
82+
{
83+
return mOrigFreeVars;
84+
}
85+
};
86+
2087
class Compiler
2188
{
22-
using Index = size_t;
23-
using SymbolTable = std::map<std::string, Index>;
2489
SymbolTable mSymbolTable{};
2590
ByteCode mCode{};
2691
using FuncInfo = std::tuple<Instructions, SymbolTable, std::string>;
27-
std::optional<FuncInfo> mFunc{};
92+
std::stack<FuncInfo> mFuncStack{};
2893
auto& instructions()
2994
{
30-
return mFunc ? std::get<0>(mFunc.value()) : mCode.instructions;
95+
return mFuncStack.empty() ? mCode.instructions : std::get<0>(mFuncStack.top());
96+
}
97+
auto& symbolTable()
98+
{
99+
return mFuncStack.empty() ? mSymbolTable : std::get<1>(mFuncStack.top());
31100
}
32-
std::pair<Index, Scope> getIndex(std::string const& name) const
101+
void emitVar(VarInfo const& varInfo);
102+
void emitIndex(size_t index);
103+
VarInfo resolve(std::string const& name)
33104
{
34-
if (mFunc)
105+
if (mFuncStack.empty())
35106
{
36-
auto const& funcInfo = mFunc.value();
37-
if (name == std::get<2>(funcInfo))
38-
{
39-
return {0, Scope::kFUNCTION_SELF_REF};
40-
}
41-
auto const map = std::get<1>(funcInfo);
42-
auto iter = map.find(name);
43-
if (iter != map.end())
44-
{
45-
return {iter->second, Scope::kLOCAL};
46-
}
107+
auto varInfo = mSymbolTable.resolve(name);
108+
ASSERT_MSG(varInfo, name);
109+
return varInfo.value();
110+
}
111+
112+
auto& funcInfo = mFuncStack.top();
113+
auto& symTable = std::get<1>(funcInfo);
114+
if (auto varInfo = symTable.resolve(name))
115+
{
116+
return varInfo.value();
117+
}
118+
// first local args, then self
119+
if (name == std::get<2>(funcInfo))
120+
{
121+
return {0, Scope::kFUNCTION_SELF_REF};
47122
}
48-
auto const idx = mSymbolTable.at(name);
49-
return {idx, Scope::kGLOBAL};
123+
FAIL_("Resolve failed!");
50124
}
51-
std::pair<Index, Scope> defineCurrentFunction(std::string const& name)
125+
VarInfo defineCurrentFunction(std::string const& name)
52126
{
53-
ASSERT(mFunc);
54-
std::get<2>(mFunc.value()) = name;
127+
ASSERT(!mFuncStack.empty());
128+
std::get<2>(mFuncStack.top()) = name;
55129
auto const scope = Scope::kFUNCTION_SELF_REF;
56130
return {0, scope};
57131
}
58-
std::pair<Index, Scope> define(std::string const& name)
132+
VarInfo define(std::string const& name)
59133
{
60-
auto& map = mFunc ? std::get<1>(mFunc.value()) : mSymbolTable;
61-
auto const idx = map.size();
62-
map[name] = idx;
63-
auto const scope = mFunc ? Scope::kLOCAL : Scope::kGLOBAL;
64-
return {idx, scope};
134+
auto const scope = mFuncStack.empty() ? Scope::kGLOBAL : Scope::kLOCAL;
135+
return symbolTable().define(name, scope);
65136
}
66137
public:
67138
Compiler() = default;

‎include/lisp/meta.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
#include <sstream>
55

66
#define ASSERT(_) if (!(_)) { std::stringstream s; s << __FILE__ << ":" << __LINE__ << " (" << #_ <<") "; throw std::runtime_error{s.str()}; }
7+
#define ASSERT_MSG(_, msg) if (!(_)) { std::stringstream s; s << __FILE__ << ":" << __LINE__ << " (" << #_ << ", " << (msg) << ") "; throw std::runtime_error{s.str()}; }
78
#define FAIL_(_) { std::stringstream s; s << __FILE__ << ":" << __LINE__ << " (" << #_ <<") "; throw std::runtime_error{s.str()}; }
89

910
template <typename... Ts>

‎include/lisp/vm.h

Lines changed: 37 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
#include <string>
88
#include <variant>
99
#include <memory>
10+
#include "meta.h"
1011

1112
using Byte = uint8_t;
1213

@@ -25,6 +26,9 @@ enum OpCode : Byte
2526
kRET,
2627
kGET_LOCAL,
2728
kSET_LOCAL,
29+
kSET_GLOBAL,
30+
kGET_GLOBAL,
31+
kGET_FREE,
2832
kTRUE,
2933
kFALSE,
3034
kEQUAL,
@@ -34,13 +38,12 @@ enum OpCode : Byte
3438
kMINUS,
3539
kJUMP,
3640
kJUMP_IF_NOT_TRUE,
37-
kSET_GLOBAL,
38-
kGET_GLOBAL,
3941
kPOP,
4042
kCONS,
4143
kCAR,
4244
kCDR,
43-
kCURRENT_FUNCTION
45+
kCURRENT_FUNCTION,
46+
kCLOSURE
4447
};
4548

4649
using Instructions = std::vector<Byte>;
@@ -82,6 +85,9 @@ class FunctionSymbol
8285
}
8386
};
8487

88+
class Closure;
89+
using ClosurePtr = std::shared_ptr<Closure>;
90+
8591
class VMCons;
8692
using ConsPtr = std::shared_ptr<VMCons>;
8793

@@ -91,7 +97,27 @@ class VMNil
9197

9298
inline constexpr VMNil vmNil{};
9399

94-
using Object = std::variant<int32_t, double, std::string, FunctionSymbol, ConsPtr, VMNil>;
100+
using Object = std::variant<int32_t, double, std::string, FunctionSymbol, ClosurePtr, ConsPtr, VMNil>;
101+
102+
class Closure
103+
{
104+
FunctionSymbol mFuncSym;
105+
std::vector<Object> mFreeVars;
106+
public:
107+
Closure(FunctionSymbol const& funcSym, std::vector<Object> const& freeVars)
108+
: mFuncSym{funcSym}
109+
, mFreeVars{freeVars}
110+
{
111+
}
112+
auto const& funcSym() const
113+
{
114+
return mFuncSym;
115+
}
116+
auto const& freeVars() const
117+
{
118+
return mFreeVars;
119+
}
120+
};
95121

96122
class VMCons
97123
{
@@ -131,19 +157,20 @@ class VM;
131157

132158
class StackFrame
133159
{
134-
FunctionSymbol const mFunc;
160+
ClosurePtr const mClosure;
135161
std::vector<Object> mLocals;
136162
size_t mReturnAddress;
137163
public:
138-
StackFrame(FunctionSymbol const& func, std::vector<Object>&& locals, size_t returnAddress)
139-
: mFunc{func}
164+
StackFrame(ClosurePtr const& func, std::vector<Object>&& locals, size_t returnAddress)
165+
: mClosure{func}
140166
, mLocals{std::move(locals)}
141167
, mReturnAddress{returnAddress}
142168
{
143169
}
144-
auto const& func() const
170+
auto const& closure() const
145171
{
146-
return mFunc;
172+
ASSERT(mClosure);
173+
return mClosure;
147174
}
148175
auto returnAddress() const
149176
{
@@ -179,7 +206,7 @@ class VM
179206
}
180207
auto const& instructions() const
181208
{
182-
return mCallStack.empty() ? mCode.instructions : mCallStack.top().func().instructions();
209+
return mCallStack.empty() ? mCode.instructions : mCallStack.top().closure()->funcSym().instructions();
183210
}
184211
private:
185212
ByteCode mCode{};

0 commit comments

Comments
 (0)