用 Lua 实现一个微型虚拟机-基本篇
用 Lua 实现一个微型虚拟机-基本篇目录
介绍在网上看到一篇文章 使用 C 语言实现一个虚拟机,这里是他的代码 Github示例代码,觉得挺有意思,作者用很少的一些代码实现了一个可运行的虚拟机,所以打算尝试用 准备工作:
为什么要写这个虚拟机?原因是: 很有趣,想象一下,做一个非常小,但是却具备基本功能的虚拟机是多么有趣啊! 指令集谈到虚拟机就不可避免要提到指令集,为简单起见,我们这里使用跟上述那篇文章一样的指令集,硬件假设也一样:
这样基于堆栈的虚拟机的实现要比基于寄存器的虚拟机的实现简单得多. 示例指令集如下: PSH 5 ; pushes 5 to the stack PSH 10 ; pushes 10 to the stack ADD ; pops two values on top of the stack,adds them pushes to stack POP ; pops the value on the stack,will also print it for debugging SET A 0 ; sets register A to 0 HLT ; stop the program 注意, 说明: 原文的 虚拟机工作原理这里也是本文的核心内容,实际上虚拟机很简单,遵循这样的模式:
为聚焦于真正的核心,我们现在简化一下这个处理步骤,暂时忽略虚拟机的编码部分,因为比较典型的虚拟机会把一条指令(包括操作码和操作数)打包成一个数字,然后再解码这个数字,因此,典型的虚拟机是可以读入真实的机器码并执行的. 项目文件结构正式开始编程之前,我们需要先设置好我们的项目. 我是在 首先,我们需要一个 Air:GitHub admin$ cd ~/GitHub/miniVM/ Air:miniVM admin$ 如上,我们先 运行也很简单,我们的虚拟机程序是 lua miniVM.lua 机器指令集现在开始为虚拟机准备要执行的代码了. 首先,我们需要定义虚拟机使用的机器指令集. 指令集数据结构设计我们需要用一种数据结构来模拟虚拟机中的指令集. C语言版在 假设助记符 typedef enum { PSH,ADD,POP,SET,HLT } InstructionSet; Lua版的其他方案看看我们的
第一篇是直接用 第二篇是用 function CreateEnumTable(tbl,index) local enumtbl = {} local enumindex = index or 0 for i,v in ipairs(tbl) do enumtbl[v] = enumindex + i end return enumtbl end local BonusStatusType = CreateEnumTable({"NOT_COMPLETE","COMPLETE","HAS_TAKE"},-1) 不过这种实现对我们来说也不太适合,一方面写起来比较繁琐,另一方面代码也不太易读,所以需要设计自己的枚举类型. 最终使用的Lua版现在的方案是直接选择用一个 InstructionSet = {"PSH","ADD","POP","SET","HLT"} 这样的实现目前看来最简单,可读性也很不错,不过缺乏扩展性,我们暂时就用这种方案. 测试程序数据结构设计现在需要一段用来测试的程序代码了,假设是这样一段程序: 把 在 const int program[] = { PSH,5,PSH,6,HLT };
我们的 program = { "PSH","5","PSH","6","HLT" } 这段代码具体来说,就是把 很好,我们有了一个完整的测试程序. 现在,我们描述了虚拟机的 从测试程序中取得当前指令因为我们的 虚拟机有一个用来定位当前指令的地址计数器,一般被称为 -- 指令指针初值设为第一条 IP = 1 那么结合我们的 IP = 1 instr = program[IP]; 如果我们打印 function fetch() return program[IP] end 该函数会返回当前被调用的指令,那么我们想要取得下一条指令该如何呢? 很简单,只要把指令指针 x = fetch() -- 取得指令 PSH IP = IP + 1 -- 指令指针加 1 y = fetch() -- 取得操作数 5 我们知道,虚拟机是会自动执行的,比如指令指针会在每执行一条指令时自动加 running = true -- 设置指令指针指向第一条指令 IP = 1 while running do local x = fetch() if x == "HLT" then running = false end IP = IP + 1 end
一个虚拟机最基本的核心就是上面这段代码了,它揭示了最本质的东西,我们可以把上面这段代码看做一个虚拟机的原型代码,更复杂的虚拟机都可以在这个原型上扩展. 不过上面这段代码什么具体工作也没做,它只是顺序取得程序中的每条指令,检查它们是不是停机指令 执行每一条指令但是我们希望虚拟机还能够执行其他指令,那么就需要我们对每一条指令分别进行处理了,这里最适合的语法结构就是 void eval(int instr) { switch (instr) { case HLT: running = false; break; } } 不过 function eval(instr) if instr == "HLT" then running = false end end 我们可以这样调用 running = true IP = 1 while running do eval(fetch()) IP = IP + 1 end 增加对其他指令处理的 function eval(instr) if instr == "HLT" then running = false elseif instr == "PSH" then -- 这里处理 PSH 指令,具体处理后面添加 elseif instr == "POP" then -- 这里处理 POP 指令,具体处理后面添加 elseif instr == "ADD" then -- 这里处理 ADD 指令,具体处理后面添加 end end 栈的数据结构设计因为我们的这款虚拟机是基于栈的,一切的数据都要从存储器搬运到栈中来操作,所以我们在为其他指令增加具体的处理代码之前,需要先准备一个栈.
在 int sp = -1; int stack[256]; 我们的 SP = 0 stack = {}
各种指令执行时栈状态变化的分析下面是一个形象化的栈,最左边是栈底,最右边是栈顶: [] // empty PSH 5 // put 5 on **top** of the stack [5] PSH 6 [5,6] POP [5] POP [] // empty PSH 6 [6] PSH 5 [6,5] 先手动分析一下我们的测试程序代码执行时栈的变化情况,先列出测试程序: PSH,HLT 先执行 [5] 再执行 [5,6] 再执行 上面这段描述很重要,理解了这个你才清楚如何用代码来模拟栈的操作. 上述没有提到栈指针 空的栈指针在 如果我们在栈中压入 SP指向这里(SP = 3) | V [1,9] 1 2 3 <- 数组下标 现在我们先从栈上弹出 SP指向这里(SP = 2) | V [1,9] 1 2 <- 数组下标
因为我们是最简版的山寨栈,所以执行弹出指令时只修改栈指针的话,栈中的那个应该被弹出的 各指令的处理逻辑经过上面的详细分析,我们应该对执行 SP = -1; stack = {}; SP = SP + 1 stack[SP] = 5 在 void eval(int instr) { switch (instr) { case HLT: { running = false; break; } case PSH: { sp++; stack[sp] = program[++ip]; break; } } }
所以在我们 function eval(instr) if instr == "HLT" then running = false elseif instr == "PSH" then -- 这里处理 PSH 指令,具体处理如下 SP = SP + 1 -- 指令指针跳到下一个,取得 PSH 的操作数 IP = IP + 1 stack[SP] = program[IP] elseif instr == "POP" then -- 这里处理 POP 指令,具体处理后面添加 elseif instr == "ADD" then -- 这里处理 ADD 指令,具体处理后面添加 end end 分析一下我们的代码,其实很简单,就是发现当指令是 接着是 elseif instr == "POP" then -- 这里处理 POP 指令,具体处理如下 local val_popped = stack[SP] SP = SP - 1 elseif ... ADD指令的处理逻辑最后是稍微复杂一些的 elseif instr == "ADD" then -- 这里处理 ADD 指令,具体处理如下 -- 先从栈中弹出一个值 local a = stack[SP] stack[SP] = 0 SP = SP - 1 -- 再从栈中弹出一个值 local b = stack[SP] stack[SP] = 0 SP = SP - 1 -- 把两个值相加 local result = a + b -- 把相加结果压入栈中 SP = SP + 1 stack[SP] = result end 最终代码很好,现在我们 -- 项目名称: miniVM -- 项目描述: 用 Lua 实现的一个基于栈的微型虚拟机 -- 项目地址: https://github.com/FreeBlues/miniVM -- 项目作者: FreeBlues -- 指令集 InstructionSet = {"PSH","HLT"} Register = {A,F,NUM_OF_REGISTERS} -- 测试程序代码 program = {"PSH","HLT"} -- 指令指针,栈顶指针,栈数组 IP = 1 SP = 0 stack = {} -- 取指令函数 function fetch() return program[IP] end -- 求值函数 function eval(instr) if instr == "HLT" then running = false elseif instr == "PSH" then -- 这里处理 PSH 指令,具体处理如下 local val_popped = stack[SP] SP = SP - 1 elseif instr == "ADD" then -- 这里处理 ADD 指令,具体处理如下 -- 先从栈中弹出一个值 local a = stack[SP] stack[SP] = 0 SP = SP - 1 -- 再从栈中弹出一个值 local b = stack[SP] stack[SP] = 0 SP = SP - 1 -- 把两个值相加 local result = a + b -- 把相加结果压入栈中 SP = SP + 1 stack[SP] = result -- 为方便查看测试程序运行结果,这里增加一条打印语句 print(stack[SP]) end end -- 虚拟机主函数 function main() running = true while running do eval(fetch()) IP = IP + 1 end end -- 启动虚拟机 main() 执行结果如下: Air:miniVM admin$ lua miniVM.lua 11.0 Air:miniVM admin$ 本项目代码可以到 Github-miniVM 下载. 虚拟机内部状态可视化应该说目前为止我们的虚拟机已经完美地实现了,不过美中不足的是它的一切动作都被隐藏起来,我们只能看到最终运行结果,当然了我们也可以增加打印命令来显示各条指令执行时的情况,但是这里我们打算把虚拟机运行时内部状态的变化用图形的方式绘制出来,而不仅仅是简单的 框架选择:Love2D这里我们选择使用
Love2D的简单介绍用 function love.draw() love.graphics.print("Hello World",400,300) end 执行命令是用 love ./love 它会新建一个窗口,然后打印 更详细的可以参考我写的这篇文档Mac 下安装使用 Love2D 把项目修改为 Love2D 的形式其实很简单,就是在项目文件目录下新建个目录 Air:miniVM admin$ cp ./miniVM.lua ./miniVM/main.lua Air:miniVM admin$ tree . ├── README.md ├── miniVM │?? └── main.lua └── miniVM.lua 1 directory,3 files Air:miniVM admin$ 按照 function love.load() -- 指令集 InstructionSet = {"PSH","HLT"} Register = {A,NUM_OF_REGISTERS} -- 测试程序代码 program = {"PSH","HLT"} -- 指令指针,栈数组 IP = 1 SP = 0 stack = {} running = true end function love.update(dt) -- 虚拟机主体 if running then eval(fetch()) IP = IP + 1 end end function love.draw() love.graphics.print("Welcome to our miniVM!",300) end -- 取指令函数 function fetch() return program[IP] end -- 求值函数 function eval(instr) if instr == "HLT" then running = false elseif instr == "PSH" then -- 这里处理 PSH 指令,这里增加一条打印语句 print(stack[SP]) end end 代码整合完毕,检查无误后用 Air:miniVM admin$ pwd /Users/admin/GitHub/miniVM Air:miniVM admin$ love ./miniVM 11 Air:miniVM admin$ 我们会看到弹出一个窗口用于绘制图形,同时命令行也会返回执行结果. 编写绘制函数目前我们的虚拟机有一个用来模拟存储器保存测试程序指令的 绘制 program 表和指令指针 IP首先绘制作为存储器使用的
我们一步步来,先绘制右侧矩形和指令,代码如下: -- 绘制存储器中指令代码的变化 function drawMemory() local x,y = 500,300 local w,h = 60,20 for k,v in ipairs(program) do -- 绘制矩形 love.graphics.setColor(0,255,50) love.graphics.rectangle("fill",y-(k-1)*h,h) -- 绘制要执行的指令代码 love.graphics.setColor(200,100) love.graphics.print(v,x+15,y-(k-1)*h+5) end end function love.draw() -- love.graphics.print("Welcome to our miniVM!",300) -- 绘制存储器中指令代码的变化 drawMemory() end 显示效果如下: 接着我们把左侧的地址矩形和地址值,还有指令指针也绘制出来,v in ipairs(program) do -- 绘制存储器右侧矩形 love.graphics.setColor(0,50) love.graphics.rectangle("line",y+(k-1)*h,h) -- 绘制存储器中要执行的指令代码 love.graphics.setColor(200,y+(k-1)*h+5) -- 绘制存储器左侧矩形 love.graphics.setColor(0,x-w/3-10,w/3+10,h) -- 绘制表示存储器地址的数字序号 love.graphics.setColor(200,100) love.graphics.print(k,x-w/2-10+10,y+(k-1)*h+5) -- 绘制指令指针 IP love.graphics.setColor(255,10,10) love.graphics.print("IP".."["..IP.."] ->",x-w-10+10-120,y+(IP-1)*h) end end 显示效果如下: 绘制 stack 表和栈顶指针 SP接下来就是绘制用来模拟栈的 -- 绘制栈的变化 function drawStack() local x,y = 200,v in ipairs(stack) do -- 显示栈右侧矩形 love.graphics.setColor(0,h) -- 绘制被压入栈内的值 love.graphics.setColor(200,x+10,y+(k-1)*h) -- 绘制栈左侧矩形 love.graphics.setColor(0,x-w-20,w+20,h) -- 绘制表示栈地址的数字序号 love.graphics.setColor(200,x-w-20+10,y+(k-1)*h) -- 绘制栈顶指针 SP love.graphics.setColor(255,10) love.graphics.print("SP".."["..SP.."] ->",x-w-10+10-100,y+(SP-1)*h) end end function love.draw() -- love.graphics.print("Welcome to our miniVM!",300) -- 绘制存储器中指令代码的变化 drawMemory() drawStack() end 显示效果如下: 很不错的结果,终于能看到虚拟机这个黑盒子里面的内容了,不过一下子就执行过去了,还是有些遗憾,那么就给它增加一项单步调试的功能好了!
增加单步调试功能其实很简单,我们只需要在虚拟机的主体执行流程中增加一个判断逻辑,每执行一条指令后都等待用户的输入,这里我们设计简单一些,就是每执行完一条指令,虚拟机就自动暂停,如果用户用键盘输入 需要用到这个键盘函数:
代码如下: function love.load() ... step = false end function love.keyreleased(key) if key == "s" then step = true end end function love.update(dt) -- 虚拟机主体 if running then if step then step = false eval(fetch()) IP = IP + 1 end end end 运行中可以通过按下 到现在为止,我们的可视化部分完成了,而且也可以通过用户的键盘输入来单步执行指令,可以说用 完整项目代码完整项目代码保存在 Github-miniVM 里,欢迎自由下载. 项目文件清单如下: Air:miniVM admin$ tree . ├── README.md ├── miniVM │?? └── main.lua ├── miniVM.lua └── pic ├── p01.png ├── p02.png ├── p03.png ├── p04.png ├── p05.png ├── p06.png ├── p07.png ├── p08.png └── p09.png 2 directories,12 files Air:miniVM admin$ 后续计划因为这种方式很好玩,所以我们打算后续在这个基础上实现一个 参考
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |