zqdabian.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于Python字节码的虚拟机的设计与实现 \n",
    "========\n",
    "\n",
    "中期答辩 --- 陶青云\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python的执行过程\n",
    "![执行过程](/notebooks/1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# Python的字节码\n",
    "代码块（包括 Module，Class， Function）会被编译成code object，而字节码就存在于code object中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# .pyc是一个被序列化的code object\n",
    "f = open('vm.pyc', 'rb')\n",
    "magic = f.read(4)\n",
    "date = f.read(4)\n",
    "\n",
    "# marshal是python的序列化工具\n",
    "import marshal\n",
    "code_object = marshal.load(f)\n",
    "\n",
    "# dir(code_object)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# code_object.co_code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 一个简单函数的例子\n",
    "def foo(x):\n",
    "    if x > 666:\n",
    "        return 'yes'\n",
    "    else:\n",
    "        return 'no'\n",
    "\n",
    "# 函数体的code object被保存在函数对象中\n",
    "foo.__code__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 字节码有两种类型，不带操作数的一个字节，带操作数的三个字节\n",
    "# [ord(o) for o in foo.__code__.co_code]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 反汇编字节码\n",
    "# dis — Disassembler 是pyhton标准库中的反汇编器\n",
    "import dis\n",
    "\n",
    "# 反汇编foo函数, 基于栈的虚拟机\n",
    "# dis.dis(foo.__code__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 用python实现的python虚拟机 ---- vm.py\n",
    "（注：pypy是用python写的， gcc是用C实现的， gc(go的编译器)是go写的）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import vm\n",
    "\n",
    "# 实例化一个VirtualMachine对象\n",
    "vm_obj = vm.VirtualMachine()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# 一个例子(斐波那契数列)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s = '''\\\n",
    "def fib(n):\n",
    "    if n in (0,1):\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)\n",
    "        \n",
    "for i in range(20):\n",
    "    print fib(i),\n",
    "'''\n",
    "\n",
    "# compile是python内置的编译器\n",
    "co = compile(s, \"\", \"exec\")\n",
    "#dis.dis(co)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# vm.run_code 是虚拟机的入口点，输入code object， 返回执行结果\n",
    "vm_obj.run_code(co)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "exec co"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# class VirtualMachine\n",
    "完成虚拟机的主要功能。具体包括：\n",
    "- 140多条字节码的具体实现\n",
    "- 对函数调用栈的相关操作\n",
    "- 维护一个指令指针IP\n",
    "- 一个虚拟的CPU，包括3个功能\n",
    "  * 取下一条指令\n",
    "  * 解码操作数\n",
    "  * 执行指令\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import re\n",
    "# VirtualMachine类中所有以大写字母开头方法的都是相关字节码的实现\n",
    "byte_codes = [ k for k in vm.VirtualMachine.__dict__.keys() if re.match('[A-Z]', k)]\n",
    "#print \"\\n\".join(byte_codes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 用一个列表结构来维护函数调用栈帧\n",
    "#print vm_obj.frames\n",
    "\n",
    "# 相关操作有\n",
    "#print vm_obj.make_frame, vm_obj.pop_frame, vm_obj.push_frame, vm_obj.run_frame\n",
    "\n",
    "# 指令指针在每个frame中维护"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "vm_obj.run_code\n",
    "vm_obj.run_frame\n",
    "vm_obj.parse_byte\n",
    "vm_obj.dispatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# class Frame\n",
    "Frame对象对应函数调用时所动态生成的栈帧（与C语言栈帧类似）。frame是一个属性的集合，它没有任何方法。\n",
    "- 它要维护3重要的命名空间，全局，局部和内建命名空间。\n",
    "- 它还要包含要执行的指令，和指令指针。\n",
    "- 数据栈\n",
    "- 块栈（ 与循环结构，异常处理相关）\n",
    "- 上一个frame的引用  \n",
    "\n",
    "与C语言不同，函数执行返回后，Frame可能不会被销毁。这点是实现Generator的基础\n",
    "\n",
    "```python\n",
    "class Frame(object):\n",
    "    def __init__(self, f_code, f_globals, f_locals, f_back):\n",
    "        self.f_code = f_code        # 指令集\n",
    "        self.f_globals = f_globals    # 全局命名空间\n",
    "        self.f_locals = f_locals     # 局部命名空间\n",
    "        self.f_back = f_back        # 上一个frame的引用\n",
    "        if hasattr(__builtins__, '__dict__'):   #内建命令空间\n",
    "            self.f_builtins = __builtins__.__dict__ \n",
    "        else:\n",
    "            self.f_builtins = __builtins__\n",
    "        self.stack = []            # 数据栈       \n",
    "        self.f_lasti = 0           # 指令指针\n",
    "        self.block_stack = []        # 块栈\n",
    "        \n",
    "        ##---------------------------- generator，closure相关\n",
    "        self.generator = None\n",
    "        if f_code.co_cellvars:\n",
    "            self.cells = {}\n",
    "            for var in f_code.co_cellvars:\n",
    "                cell = self.f_locals.get(var)\n",
    "                self.cells[var] = cell\n",
    "        else:\n",
    "            self.cells = None\n",
    "            \n",
    "        if f_code.co_freevars:\n",
    "            if not self.cells:\n",
    "                self.cells = {}\n",
    "            for var in f_code.co_freevars:\n",
    "                self.cells[var] = self.f_locals.get(var)\n",
    "\n",
    " ``` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print vm_obj.frame == None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# class Function\n",
    " Fuction对象代表Python中的一个函数。他的重点在于可调用性。\n",
    " 当它被调用时，自动创建一个Frame对象执行函数中的字节码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "vm.Function??"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# 参数传递"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def test(x, y=5, *args, **kwargs):\n",
    "    print x, y, args, kwargs\n",
    "\n",
    "test(1)\n",
    "test(1,2) \n",
    "test(1,2,3) \n",
    "test(1,2,3,4)\n",
    "test(x=1) \n",
    "test(x=1,y=1) \n",
    "test(x=1,y=1,a=1)\n",
    "test(x=1,y=1,a=1,b=1) \n",
    "test(1,y=1)\n",
    "test(1,2,3,4,a=1) \n",
    "test(1,2,3,4,k=1,t=2,o=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "与之相关的字节码\n",
    "- CALL_FUNCTION(argc)\n",
    "- CALL_FUNCTION_VAR(argc)\n",
    "- CALL_FUNCTION_KW(argc)\n",
    "- CALL_FUNCTION_VAR_KW(argc)\n",
    "\n",
    "官方文档对[CALL_FUNCTION](https://docs.python.org/2/library/dis.html#opcode-CALL_FUNCTION)的解释\n",
    ">    Calls a function. The low byte of argc indicates the number of positional parameters, the high byte the number of keyword parameters. On the stack, the opcode finds the keyword parameters first. For each keyword argument, the value is on top of the key. Below the keyword parameters, the positional parameters are on the stack, with the right-most parameter on top. Below the parameters, the function object to call is on the stack. Pops all function arguments, and the function itself off the stack, and pushes the return value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "vm_obj.CALL_FUNCTION??\n",
    "vm_obj.call_function??"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# 闭包机制的实现\n",
    ">    Closures are functions that refer to independent (free) variables. In other words, the function defined in the closure 'remembers' the environment in which it was created. \n",
    "[MDN中的解释](https://developer.mozilla.org/en/docs/Web/JavaScript/Closures)\n",
    "\n",
    "相关代码或字节码：\n",
    "- Function.\\_\\_call\\_\\_\n",
    "- LOAD_CLOSURE\n",
    "- MAKE_CLOSURE\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 一个简单闭包的例子\n",
    "def makeAdd(x):\n",
    "    def f(y):\n",
    "        return x + y\n",
    "    return f\n",
    "\n",
    "add1 = makeAdd(1)\n",
    "add3 = makeAdd(3)\n",
    "print add1(0)\n",
    "print add3(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Function在创建时会保存它的自由变量，在func_closure属性中\n",
    "print add1.func_closure[0].cell_contents\n",
    "print add3.func_closure[0].cell_contents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 字节码层的解释\n",
    "# 编译器在编译时已确定自由变量\n",
    "print add1.__code__.co_freevars\n",
    "\n",
    "# 同时外层函数也会确定哪些变量会被内函数引用\n",
    "print makeAdd.__code__.co_cellvars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有了这些信息，就可以完成闭包机制。闭包函数在被调用时，在创建Frame之前，把自由变量和对应的值存入局部命名空间中。（CPython不是这样实现的，看不懂）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# 生成器\n",
    ">    In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. In fact, all generators are iterators.    \n",
    "Generators can be implemented in terms of more expressive control flow constructs, such as coroutines or first-class continuations. 摘自[wikipedia](https://en.wikipedia.org/wiki/Generator_(computer_programming)\n",
    "\n",
    "相关代码或字节码：\n",
    "- Function.\\_\\_call\\_\\_\n",
    "- class Generator\n",
    "- YIELD_VALUE\n",
    "- RUTURN_VALUE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 再一次斐波那契数列\n",
    "s = \"\"\"\\\n",
    "def gen_fib(n):\n",
    "    a, b, i = 0, 1, 0\n",
    "    while i < n:\n",
    "        yield a\n",
    "        a, b = b, a+b\n",
    "        i += 1\n",
    "gen = gen_fib(20)\n",
    "\n",
    "for i in gen:\n",
    "    print i,\n",
    "\"\"\"\n",
    "\n",
    "o = compile(s, \"\", \"exec\")\n",
    "vm_obj.run_code(o)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "exec s\n",
    "# 无穷序列\n",
    "gen = gen_fib(10)\n",
    "print gen.next()\n",
    "# C语言中，一个函数返回之后对应栈帧就会被清除\n",
    "# 而在python中frame可能被保存\n",
    "print gen.next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 普通函数与含yield函数的区别\n",
    "# code object有个flags属性, 编译时含yield函数的flags的第六位被置为1\n",
    "print bin(gen_fib.__code__.co_flags & 0b100000)\n",
    "# 普通函数flags第六位置为0\n",
    "print fib.__code__.co_flags & 32"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "在函数被调用时,虚拟机会判断该位是否置1,如果是,则返回一个生成器对象,否则走正常流程,执行字节码   \n",
    "\n",
    "```python\n",
    "class Generator(object):\n",
    "    def __init__(self, g_frame, vm):\n",
    "        self.gi_frame = g_frame    # 保存所在的栈帧,即Frame对象\n",
    "        self.vm = vm\n",
    "        self.started = False\n",
    "        self.finished = False\n",
    "\n",
    "    # --------------------------------  实现迭代器协议\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def next(self):\n",
    "        return self.send(None)\n",
    "\n",
    "    def send(self, value=None):\n",
    "        if not self.started and value is not None:\n",
    "            raise TypeError(\"Can't send non-None value to a just-started generator\")\n",
    "        self.gi_frame.stack.append(value)       # 数据栈中压入值,会在下次运行frame时弹出,实现yield赋值功能\n",
    "        self.started = True\n",
    "        val = self.vm.resume_frame(self.gi_frame)  # 重新运行所在的frame\n",
    "        if self.finished:\n",
    "            raise StopIteration(val)\n",
    "        return val\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "# 异常处理机制"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}