Add virtual (#31)

BowenFu · web-flow · commit 5ab700b4ebb0 · 2021-12-26T22:57:05.000+08:00
* Add virtual machine - part 1

* Fix build.

* Fix build.

Co-authored-by: Bowen Fu &lt;missing&gt;
diff --git a/.github/FUNDING.yml b/.github/FUNDING.yml
@@ -9,4 +9,4 @@ community_bridge: # Replace with a single Community Bridge project-name e.g., cl
 liberapay: bfu # Replace with a single Liberapay username
 issuehunt: # Replace with a single IssueHunt username
 otechie: # Replace with a single Otechie username
-custom: http://paypal.me/bowfu # Replace with up to 4 custom sponsorship URLs e.g., ['link1', 'link2']
+custom: # Replace with up to 4 custom sponsorship URLs e.g., ['link1', 'link2']
diff --git a/README.md b/README.md
@@ -1,6 +1,6 @@
 # lisp.cpp
 
-lisp : a simple computer algebra system in C++
+lisp : a simple lisp interpreter in C++ with scheme style syntax + quote / unquote style macros.
 
 <!-- ![lisp](./lisp.svg) -->
 
diff --git a/core.lisp b/core.lisp
@@ -122,6 +122,14 @@
         (expand-clauses clauses)
     ))
 
+(define delay (macro (action)
+   `(lambda () ,action))
+)
+
+(define force (macro (delayed)
+    `(,delayed))
+)
+
 (define atom?
     (lambda (x)
     (and (not (pair? x)) (not (null? x)))))
diff --git a/include/lisp/vm.h b/include/lisp/vm.h
@@ -0,0 +1,112 @@
+#include <cstdint>
+#include <vector>
+#include <stack>
+#include <string>
+#include <variant>
+
+using Byte = uint8_t;
+
+enum Instruction
+{
+    kICONST,
+    kIADD,
+    kSCONST,
+    kHALT,
+    kPRINT,
+    kCALL,
+    kRET,
+    kLOAD,
+    kSTORE,
+};
+
+
+class FunctionSymbol
+{
+    std::string mName{};
+    size_t mNbArgs{};
+    size_t mNbLocals{};
+    size_t mAddress{};
+public:
+    FunctionSymbol(std::string name, size_t nbArgs, size_t nbLocals, size_t address)
+    : mName{name}
+    , mNbArgs{nbArgs}
+    , mNbLocals{nbLocals}
+    , mAddress{address}
+    {}
+    std::string name() const
+    {
+        return mName;
+    }
+    size_t nbArgs() const
+    {
+        return mNbArgs;
+    }
+    size_t nbLocals() const
+    {
+        return mNbLocals;
+    }
+    size_t address() const
+    {
+        return mAddress;
+    }
+};
+
+using Object = std::variant<int32_t, float, std::string, FunctionSymbol>;
+
+class VM;
+
+class StackFrame
+{
+    FunctionSymbol const& mFunc;
+    std::vector<Object> mLocals;
+    size_t mReturnAddress;
+public:
+    StackFrame(FunctionSymbol const& func, std::vector<Object>&& locals, size_t returnAddress)
+    : mFunc{func}
+    , mLocals{std::move(locals)}
+    , mReturnAddress{returnAddress}
+    {
+    }
+    auto func() const
+    {
+        return mFunc;
+    }
+    auto returnAddress() const
+    {
+        return mReturnAddress;
+    }
+    auto& locals(size_t i)
+    {
+        return mLocals.at(i);
+    }
+};
+
+class VM
+{
+public:
+    VM(std::vector<Byte> const& code, std::vector<Object> const& constantPool = {})
+    : mCode{code}
+    , mConstantPool{constantPool}
+    {}
+    void run();
+    auto peekOperandStack() const
+    {
+        return mOperands.top();
+    }
+    auto& operandStack()
+    {
+        return mOperands;
+    }
+private:
+    std::vector<Byte> mCode{};
+    std::vector<Object> mConstantPool{};
+    size_t mIp{};
+    std::stack<Object> mOperands{};
+    std::stack<StackFrame> mCallStack{};
+};
+
+template <typename T>
+auto fourBytesToInteger(Byte const* buffer) -> T
+{
+    return static_cast<T>(buffer[0] << 24 | buffer[1] << 16 | buffer[2] << 8 | buffer[3]);
+}
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -3,6 +3,7 @@ target_include_directories(lisp PUBLIC
 
 target_sources(lisp PRIVATE
 evaluator.cpp
+vm.cpp
 )
 
 target_compile_options(lisp PRIVATE ${BASE_COMPILE_FLAGS})
diff --git a/src/vm.cpp b/src/vm.cpp
@@ -0,0 +1,99 @@
+#include "lisp/vm.h"
+#include <iostream>
+
+std::ostream& operator << (std::ostream& o, StackFrame const& f)
+{
+    return o << "StackFrame " << f.func().name();
+}
+
+std::ostream& operator << (std::ostream& o, FunctionSymbol const& f)
+{
+    return o << "Function " << f.name();
+}
+
+void VM::run()
+{
+    while (mIp < mCode.size())
+    {
+        Byte bytecode = mCode[mIp];
+        ++mIp;
+        switch (bytecode)
+        {
+        case kICONST:
+        {
+            int32_t word = fourBytesToInteger<int32_t>(&mCode[mIp]);
+            mIp += 4;
+            operandStack().push(word);
+            break;
+        }
+        case kIADD:
+        {
+            int32_t rhs = std::get<int32_t>(operandStack().top());
+            operandStack().pop();
+            int32_t lhs = std::get<int32_t>(operandStack().top());
+            operandStack().pop();
+            int32_t result = lhs + rhs;
+            operandStack().push(result);
+            break;
+        }
+        case kSCONST:
+        {
+            uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
+            mIp += 4;
+            operandStack().push(mConstantPool.at(index));
+            break;
+        }
+        case kPRINT:
+        {
+            auto op = operandStack().top();
+            operandStack().pop();
+            std::visit([](auto op)
+            {
+                std::cout << op << std::endl;
+            }, op);
+            break;
+        }
+        case kHALT:
+            return;
+        case kCALL:
+        {
+            uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
+            mIp += 4;
+
+            auto const& functionSymbol = std::get<FunctionSymbol>(mConstantPool.at(index));
+            std::vector<Object> params(functionSymbol.nbArgs() + functionSymbol.nbLocals());
+            for (size_t i = functionSymbol.nbArgs(); i > 0; --i)
+            {
+                params.at(i - 1) = operandStack().top();
+                operandStack().pop();
+            }
+            mCallStack.push(StackFrame{functionSymbol, std::move(params), mIp});
+            mIp = functionSymbol.address();
+            break;
+        }
+        case kRET:
+        {
+            mIp = mCallStack.top().returnAddress();
+            mCallStack.pop();
+            break;
+        }
+        case kLOAD:
+        {
+            uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
+            mIp += 4;
+
+            operandStack().push(mCallStack.top().locals(index));
+            break;
+        }
+        case kSTORE:
+        {
+            uint32_t index = fourBytesToInteger<uint32_t>(&mCode[mIp]);
+            mIp += 4;
+
+            mCallStack.top().locals(index) = operandStack().top();
+            operandStack().pop();
+            break;
+        }
+        }
+    }
+}
diff --git a/test/lisp/CMakeLists.txt b/test/lisp/CMakeLists.txt
@@ -1,5 +1,6 @@
 add_executable(unittests
 test.cpp
+testVm.cpp
 )
 target_include_directories(unittests PRIVATE
   ${PROJECT_SOURCE_DIR}/src)
diff --git a/test/lisp/testVm.cpp b/test/lisp/testVm.cpp
@@ -0,0 +1,54 @@
+#include "gtest/gtest.h"
+#include "lisp/vm.h"
+#include <numeric>
+
+TEST(VM, add)
+{
+    std::vector<Byte> const code = {kICONST, 0, 0, 0, 1, kICONST, 0, 0, 0, 2, kIADD};
+    VM vm{code, {}};
+    vm.run();
+    auto result = vm.peekOperandStack();
+    EXPECT_EQ(std::get<int32_t>(result), 3);
+}
+
+TEST(VM, print)
+{
+    std::vector<Byte> const code = {kICONST, 0, 0, 0, 1, kICONST, 0, 0, 0, 2, kIADD, kPRINT};
+    VM vm{code, {}};
+    testing::internal::CaptureStdout();
+    vm.run();
+    std::string output = testing::internal::GetCapturedStdout();
+    EXPECT_EQ(output, "3\n");
+}
+
+TEST(VM, str)
+{
+    std::vector<Byte> const code = {kSCONST, 0, 0, 0, 0, kPRINT};
+    VM vm{code, {"some str: 123"}};
+    testing::internal::CaptureStdout();
+    vm.run();
+    std::string output = testing::internal::GetCapturedStdout();
+    EXPECT_EQ(output, "some str: 123\n");
+}
+
+TEST(VM, func)
+{
+    std::vector<Byte> const code = {kICONST, 0, 0, 0, 11, kCALL, 0, 0, 0, 0, kHALT, kLOAD, 0, 0, 0, 0, kPRINT};
+    std::vector<Object> const constPool = {FunctionSymbol{"main", 1, 1, 11}};
+    VM vm{code, constPool};
+    testing::internal::CaptureStdout();
+    vm.run();
+    std::string output = testing::internal::GetCapturedStdout();
+    EXPECT_EQ(output, "11\n");
+}
+
+TEST(VM, func2)
+{
+    std::vector<Byte> const code = {kICONST, 0, 0, 0, 11, kCALL, 0, 0, 0, 0, kPRINT, kHALT, kLOAD, 0, 0, 0, 0, kICONST, 0, 0, 0, 2, kIADD, kSTORE, 0, 0, 0, 1, kLOAD, 0, 0, 0, 1, kRET};
+    std::vector<Object> const constPool = {FunctionSymbol{"id", 1, 1, 12}};
+    VM vm{code, constPool};
+    testing::internal::CaptureStdout();
+    vm.run();
+    std::string output = testing::internal::GetCapturedStdout();
+    EXPECT_EQ(output, "13\n");
+}

Original file line number	Diff line number	Diff line change
`@@ -3,6 +3,7 @@ target_include_directories(lisp PUBLIC`
`3`	`3`
`4`	`4`	`target_sources(lisp PRIVATE`
`5`	`5`	`evaluator.cpp`
	`6`	`+vm.cpp`
`6`	`7`	`)`
`7`	`8`
`8`	`9`	`target_compile_options(lisp PRIVATE ${BASE_COMPILE_FLAGS})`
Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,6 @@`
`1`	`1`	`add_executable(unittests`
`2`	`2`	`test.cpp`
	`3`	`+testVm.cpp`
`3`	`4`	`)`
`4`	`5`	`target_include_directories(unittests PRIVATE`
`5`	`6`	`${PROJECT_SOURCE_DIR}/src)`