Skip to content

Commit 8ba1308

Browse files
BowenFuBowenFu
authored
Add compiler. (#32)
* Add compiler. * Fix build. * Fix build. Co-authored-by: Bowen Fu <missing>
1 parent 5ab700b commit 8ba1308

File tree

12 files changed

+246
-35
lines changed

12 files changed

+246
-35
lines changed

‎include/lisp/compiler.h

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
#ifndef LISP_COMPILER_H
2+
#define LISP_COMPILER_H
3+
4+
#include "vm.h"
5+
#include "evaluator.h"
6+
7+
class Compiler
8+
{
9+
Env mEnv{};
10+
ByteCode mCode{};
11+
public:
12+
Compiler() = default;
13+
void compile(ExprPtr const& expr);
14+
ByteCode code() const
15+
{
16+
return mCode;
17+
}
18+
};
19+
20+
#endif // LISP_COMPILER_H

‎include/lisp/evaluator.h

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@
1111
#include <functional>
1212
#include <variant>
1313

14+
class Compiler;
15+
1416
class Expr;
1517
using ExprPtr = std::shared_ptr<Expr>;
1618
class Env;
@@ -135,7 +137,7 @@ class Expr
135137
virtual std::string toString() const = 0;
136138
virtual bool equalTo(ExprPtr const&) const
137139
{
138-
FAIL("Not implemented");
140+
FAIL_("Not implemented");
139141
}
140142
virtual ~Expr() = default;
141143
};
@@ -197,7 +199,7 @@ class RawWord : public Expr
197199
}
198200
ExprPtr eval(std::shared_ptr<Env> const& /* env */) override
199201
{
200-
FAIL("RawWord should never be evaluated!");
202+
FAIL_("RawWord should never be evaluated!");
201203
}
202204
std::string toString() const override
203205
{
@@ -635,6 +637,7 @@ class MacroProcedure final : public CompoundProcedureBase
635637

636638
class Application final : public Expr
637639
{
640+
friend Compiler;
638641
ExprPtr mOperator;
639642
std::vector<ExprPtr> mOperands;
640643
public:

‎include/lisp/meta.h

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,15 @@
11
#ifndef LISP_META_H
22
#define LISP_META_H
33

4+
#include <sstream>
5+
46
#define ASSERT(_) if (!(_)) { std::stringstream s; s << __FILE__ << ":" << __LINE__ << " (" << #_ <<") "; throw std::runtime_error{s.str()}; }
5-
#define FAIL(_) { throw std::runtime_error{#_}; }
7+
#define FAIL_(_) { std::stringstream s; s << __FILE__ << ":" << __LINE__ << " (" << #_ <<") "; throw std::runtime_error{s.str()}; }
8+
9+
template <typename... Ts>
10+
void unused(Ts const&...)
11+
{
12+
return;
13+
}
614

715
#endif // LISP_META_H

‎include/lisp/metaParser.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,7 @@ class MetaParser
7272
return false_();
7373

7474
default:
75-
FAIL("Not implemented yet!");
75+
FAIL_("Not implemented yet!");
7676
break;
7777
}
7878
return true_();

‎include/lisp/parser.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -358,11 +358,11 @@ inline auto atomicToQuoted(ExprPtr const& expr)
358358
}
359359
if (dynamic_cast<Variable const*>(expr.get()))
360360
{
361-
FAIL("Variable should not appear as atomic!");
361+
FAIL_("Variable should not appear as atomic!");
362362
}
363363
if (dynamic_cast<Symbol const*>(expr.get()))
364364
{
365-
FAIL("Symbol should not appear as atomic!");
365+
FAIL_("Symbol should not appear as atomic!");
366366
}
367367
return expr;
368368
}

‎include/lisp/vm.h

Lines changed: 24 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,6 @@
1+
#ifndef LISP_VM_H
2+
#define LISP_VM_H
3+
14
#include <cstdint>
25
#include <vector>
36
#include <stack>
@@ -6,11 +9,15 @@
69

710
using Byte = uint8_t;
811

9-
enum Instruction
12+
enum OpCode : Byte
1013
{
1114
kICONST,
1215
kIADD,
13-
kSCONST,
16+
kADD,
17+
kSUB,
18+
kMUL,
19+
kDIV,
20+
kCONST,
1421
kHALT,
1522
kPRINT,
1623
kCALL,
@@ -51,7 +58,7 @@ class FunctionSymbol
5158
}
5259
};
5360

54-
using Object = std::variant<int32_t, float, std::string, FunctionSymbol>;
61+
using Object = std::variant<int32_t, double, std::string, FunctionSymbol>;
5562

5663
class VM;
5764

@@ -81,12 +88,20 @@ class StackFrame
8188
}
8289
};
8390

91+
using Instructions = std::vector<Byte>;
92+
93+
class ByteCode
94+
{
95+
public:
96+
Instructions instructions{};
97+
std::vector<Object> constantPool{};
98+
};
99+
84100
class VM
85101
{
86102
public:
87-
VM(std::vector<Byte> const& code, std::vector<Object> const& constantPool = {})
103+
VM(ByteCode const& code)
88104
: mCode{code}
89-
, mConstantPool{constantPool}
90105
{}
91106
void run();
92107
auto peekOperandStack() const
@@ -98,8 +113,7 @@ class VM
98113
return mOperands;
99114
}
100115
private:
101-
std::vector<Byte> mCode{};
102-
std::vector<Object> mConstantPool{};
116+
ByteCode mCode{};
103117
size_t mIp{};
104118
std::stack<Object> mOperands{};
105119
std::stack<StackFrame> mCallStack{};
@@ -109,4 +123,6 @@ template <typename T>
109123
auto fourBytesToInteger(Byte const* buffer) -> T
110124
{
111125
return static_cast<T>(buffer[0] << 24 | buffer[1] << 16 | buffer[2] << 8 | buffer[3]);
112-
}
126+
}
127+
128+
#endif // LISP_VM_H

‎src/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@ target_include_directories(lisp PUBLIC
44
target_sources(lisp PRIVATE
55
evaluator.cpp
66
vm.cpp
7+
compiler.cpp
78
)
89

910
target_compile_options(lisp PRIVATE ${BASE_COMPILE_FLAGS})

‎src/compiler.cpp

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
#include "lisp/compiler.h"
2+
#include <array>
3+
4+
auto integerToFourBytes(size_t num) -> std::array<Byte, 4>
5+
{
6+
std::array<Byte, 4> result;
7+
result[3] = num & 0xFF;
8+
unused(num >>= 8);
9+
result[2] = num & 0xFF;
10+
unused(num >>= 8);
11+
result[1] = num & 0xFF;
12+
unused(num >>= 8);
13+
result[0] = num & 0xFF;
14+
return result;
15+
}
16+
17+
void Compiler::compile(ExprPtr const& expr)
18+
{
19+
auto const exprPtr = expr.get();
20+
if (auto numPtr = dynamic_cast<Number const*>(exprPtr))
21+
{
22+
auto const index = mCode.constantPool.size();
23+
mCode.constantPool.push_back(numPtr->get());
24+
mCode.instructions.push_back(kCONST);
25+
// todo: refactor
26+
auto bytes = integerToFourBytes(index);
27+
for (Byte i : bytes)
28+
{
29+
mCode.instructions.push_back(i);
30+
}
31+
return;
32+
}
33+
if (auto appPtr = dynamic_cast<Application const*>(exprPtr))
34+
{
35+
auto nbOperands = appPtr->mOperands.size();
36+
OpCode opCode = [appPtr, nbOperands]
37+
{
38+
auto opName = appPtr->mOperator->toString();
39+
if (opName == "+")
40+
{
41+
return kADD;
42+
}
43+
else if (opName == "-")
44+
{
45+
ASSERT(nbOperands == 2U);
46+
return kSUB;
47+
}
48+
else if (opName == "*")
49+
{
50+
return kMUL;
51+
}
52+
else if (opName == "/")
53+
{
54+
ASSERT(nbOperands == 2U);
55+
return kDIV;
56+
}
57+
FAIL_("Not supported yet!");
58+
}();
59+
compile(appPtr->mOperands.at(0));
60+
for (auto i = 1U; i < nbOperands; ++i)
61+
{
62+
compile(appPtr->mOperands.at(i));
63+
mCode.instructions.push_back(opCode);
64+
}
65+
return;
66+
}
67+
}

‎src/vm.cpp

Lines changed: 55 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
#include "lisp/vm.h"
2+
#include "lisp/meta.h"
23
#include <iostream>
34

45
std::ostream& operator << (std::ostream& o, StackFrame const& f)
@@ -13,15 +14,15 @@ std::ostream& operator << (std::ostream& o, FunctionSymbol const& f)
1314

1415
void VM::run()
1516
{
16-
while (mIp < mCode.size())
17+
while (mIp < mCode.instructions.size())
1718
{
18-
Byte bytecode = mCode[mIp];
19+
Byte opCode = mCode.instructions[mIp];
1920
++mIp;
20-
switch (bytecode)
21+
switch (opCode)
2122
{
2223
case kICONST:
2324
{
24-
int32_t word = fourBytesToInteger<int32_t>(&mCode[mIp]);
25+
int32_t word = fourBytesToInteger<int32_t>(&mCode.instructions[mIp]);
2526
mIp += 4;
2627
operandStack().push(word);
2728
break;
@@ -36,11 +37,54 @@ void VM::run()
3637
operandStack().push(result);
3738
break;
3839
}
39-
case kSCONST:
40+
case kADD:
41+
case kSUB:
42+
case kMUL:
43+
case kDIV:
4044
{
41-
uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
45+
auto const rhs = operandStack().top();
46+
operandStack().pop();
47+
auto const lhs = operandStack().top();
48+
operandStack().pop();
49+
if (auto lhsDPtr = std::get_if<double>(&lhs))
50+
{
51+
auto lhsD = *lhsDPtr;
52+
auto rhsD = std::get<double>(rhs);
53+
double result{};
54+
switch (opCode)
55+
{
56+
case kADD:
57+
result = lhsD + rhsD;
58+
break;
59+
60+
case kSUB:
61+
result = lhsD - rhsD;
62+
break;
63+
64+
case kMUL:
65+
result = lhsD * rhsD;
66+
break;
67+
68+
case kDIV:
69+
result = lhsD / rhsD;
70+
break;
71+
72+
default:
73+
break;
74+
}
75+
operandStack().push(result);
76+
}
77+
else
78+
{
79+
FAIL_("Not supported yet!");
80+
}
81+
break;
82+
}
83+
case kCONST:
84+
{
85+
uint32_t index = fourBytesToInteger<uint32_t>(&mCode.instructions[mIp]);
4286
mIp += 4;
43-
operandStack().push(mConstantPool.at(index));
87+
operandStack().push(mCode.constantPool.at(index));
4488
break;
4589
}
4690
case kPRINT:
@@ -57,10 +101,10 @@ void VM::run()
57101
return;
58102
case kCALL:
59103
{
60-
uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
104+
uint32_t index = fourBytesToInteger<uint32_t>(&mCode.instructions[mIp]);
61105
mIp += 4;
62106

63-
auto const& functionSymbol = std::get<FunctionSymbol>(mConstantPool.at(index));
107+
auto const& functionSymbol = std::get<FunctionSymbol>(mCode.constantPool.at(index));
64108
std::vector<Object> params(functionSymbol.nbArgs() + functionSymbol.nbLocals());
65109
for (size_t i = functionSymbol.nbArgs(); i > 0; --i)
66110
{
@@ -79,15 +123,15 @@ void VM::run()
79123
}
80124
case kLOAD:
81125
{
82-
uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
126+
uint32_t index = fourBytesToInteger<uint32_t>(&mCode.instructions[mIp]);
83127
mIp += 4;
84128

85129
operandStack().push(mCallStack.top().locals(index));
86130
break;
87131
}
88132
case kSTORE:
89133
{
90-
uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
134+
uint32_t index = fourBytesToInteger<uint32_t>(&mCode.instructions[mIp]);
91135
mIp += 4;
92136

93137
mCallStack.top().locals(index) = operandStack().top();

‎test/lisp/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
add_executable(unittests
22
test.cpp
33
testVm.cpp
4+
testCompiler.cpp
45
)
56
target_include_directories(unittests PRIVATE
67
${PROJECT_SOURCE_DIR}/src)

0 commit comments

Comments
 (0)