文档章节

编译原理之学习 lua 3.1 (七) Closure 闭包支持

刘军兴
 刘军兴
发布于 2013/12/28 18:54
字数 2559
阅读 840
收藏 7
点赞 0
评论 0

lua 3.1 与其前一个版本 3.0 比, 有了很大的变化, 可参见历史文件 HISTORY.
 
我们关心的有:
1. 解析由 LR 的变成手写的 LL 递归下降解析器了, 文法变化,代码生成变化了;
2. 新概念: 闭包 (closure)
   NEW CONCEPT: anonymous functions with closures (via "upvalues").

首先研究解析器问题:
解析入口: TProtoFunc *luaY_parser(ZIO *z)
函数: next(LexState *): 读入下一个符号.
chunk(LexState *): 文法正式的入口.

下面用定界符 <% %> 表示代码块. 因 {} 被 LL 文法使用.
文法符号含义:
  -> 推导出
  { } 可重复 1-M 次, 相当于正则 ()+ 中多次的意思.
  [ ] 可选, 即可 0-1 次
  -- 后面加一些注释

program -> chunk <%代码: close_func() 完成一个整的 code chunk. %> ;
chunk -> statlist ret
statlist -> { stat [;] }  -- 语句列表是一个或多个语句, 中间可选分号分隔
  对应函数 statlist() 实现即写成:
    while (true) {
   stat() and if (END) break;  -- 读入语句结束则 退出循环.
   optional(';');
 }
stat -> IF ifpart END  -- if 语句
      | WHILE cond DO block END -- while 语句
   | DO block END -- do 语句块
   | REPEAT block UNTIL exp1
   | FUNCTION funcname body
   | LOCAL localnamelist decinit
   | stat -> func | ['%'] NAME assignment  -- 函数调用或赋值
      | error -- 不是上述情况则是错误.

回顾原 LL 文法中 func 调用和赋值的部分:
stat -> functioncall
stat -> varlist1 '=' exprlist1
functioncall -> funcvalue funcParams
funcvalue -> varexp | varexp ':' NAME
varlist1 -> var | varlist1 ',' var
var -> singlevar | varexp '[' expr1 ']' | varexp '.' NAME
singlevar -> NAME
varexp -> var

合并 var (LR格式):
  var -> NAME | var '[' expr1 ']' | var '.' NAME
转换为 LL 形式的:
  var -> NAME { '[' expr1 ']' | '.' NAME }
则 FOLLOWS() 集合中就是 NAME

varlist1 写成 LL 形式的:
  varlist1 -> var { ',' var }*
则 varlist1 的 FOLLOWS() 集合是 NAME.
(对产生式的各种变换, LL,LR 等还是让计算机科学家做好, 我们开心使用和学习就挺好了)

funcvalue -> var {':' NAME}
则 funvalue 的 FOLLOWS() 集合是 NAME, 和 varlist1 相同了, 故而
  在 var 读入后根据后一个终结符才能判定是 func, 还是 assign.
例子:  f(1,2,3)  -- 读入 NAME=f, 在之后遇到 '(' 才能判定是函数调用.
例子: x=4 或 x,y=5,6 -- 读入 NAME=x, 在之后遇到 '=', ',' 才能判定是
  赋值.
为此需要将非终结符 var 的综合属性传递给后面分析步骤用, 此一属性以结构
  vardesc 描述.

结构 vardesc:
  varkind k; -- var 类型描述.
  int info; -- 该 var 的索引, 根据 varkind 类型有不同含义.
 
关于 varkind 的原注释:
  must include a "exp" option because LL(1) cannot distinguish
  between variables, upvalues and function calls on first sight.
也即上面通过产生式说明的问题.


实现上函数 var_or_func(vardesc *v) 读取第一个 var, 此时尚分辨不出
后面将是 '(' 等导去函数调用, 还是 '=' 等导去赋值.
  var_or_func -> ['%'] NAME var_or_func_tail
程序逻辑如下:
  if (有 '%' 符号) -- 引用上一层函数的局部变量, 即闭包变量.
    push_upvalue() -- 产生代码, 压栈 upvalue. 研究闭包时详述
    vardesc.kind = VEXP, .info = 0  -- 表示已经获取了
  else -- 否则是一个变量的名字
    singlevar(vardesc, NAME, ...)
  var_or_func_tail() -- 产生式 var_or_func -> ... var_or_func_tail

函数 singlevar(vardesc, NAME, ...) 中:
  if (NAME 是一个局部变量)
    vardesc.kind = VLOCAL, .info = 局部变量索引 -- 是一个局部变量时
  else
    if (NAME 是上一级函数中的变量) 警告: 不能访问上级变量
 否之: vardesc.kind = VGLOBAL, .info = 全局变量索引.

函数 var_or_func_tail() 相当于下面产生式(可多次重复):
  var_or_func_tail ->* '.' NAME  -- 如 a.b, vardesc.kind = VDOT
    | '[' expr1 ']' -- 如 a['b'], 对应 vardesc.kind = VINDEXED
 | ':' NAME funcparams -- 如 obj:f(1,2), 对应 vardesc.kind = VEXP
 | (以 '(' or '{' 开头的) funcparams -- 如 f(1,2), f{a=1,b=2},
    对应 vardesc.kind = VEXP

故而函数 var_or_func_tail() 返回时, 会填写好 vardesc 的信息.
(这里 vardesc 结构兼具综合属性和继承属性的特点, 即即向下传递信息,
 又向上传递信息)

后续需要 var 的地方, 主要一是作为表达式左值, 如 varlist1 中, 一是作为
表达式右值, 如 expr, expr1 中. 当用作左值时, kind=VGLOBAL,VLOCAL,
VDOT,VINDEXED 可用作左值, 其表示不同的寻址方式, 见于函数 storevar();
当作用右值时, VEXP可以直接用, 其它几种需要加载该地址的值, 见于函数
lua_pushvar(). (这两个函数一个读一个写, 本来有相对应性, 可名字由于
历史原因吧, 不是很配对)

函数 lua_pushvar():
  if (var 是 VGLOBAL 类型的)  -- 即全局变量
    产生 PUSHGLOBAL i 指令, 其中 i 是此全局变量的索引, 即 vardesc.info 值
  else if (var 是 VLOCAL 类型的) -- 局部变量, 函数参数
    产生 PUSHLOCAL i 指令
  else if (var 是 VDOT 类型的) -- a.b 形式访问的
    产生 GETDOTTED 指令
  else if (var 是 VINDEXED 类型的) -- a['b'] 形式访问的
    产生 GETTABLE 指令
  else if (var 是 VEXP 类型的) -- 已经是值了
    close_exp() -- 和函数多返回值情况有关, 此处略.
  之后, 设置 vardesc.kind = VEXP, 因为已经将值加载到栈中了.

  当 var 是 upvalues 时候, 已经在函数 var_or_func() 中使用 push_upvalue()
  产生了 PUSHUPVALUE 指令.

这里与原有的 3.0, 2.1, 1.1 等早期版本对比, 区分了 a.b, a['b'] 的访问为
两种寻址方式(旧版本中都是用 PUSHINDEXED 来寻址), 新增了 PUSHUPVALUE 寻址
方式, 也即现在有 5 种寻址方式了.

同样 storevar():
  if (var 是 VGLOBAL 类型的)
    产生 STOREGLOBAL 指令
  else if (var 是 VLOCAL 类型的)
    产生 STORELOCAL 指令
  else if (var 是 VINDEXED 类型的)
    产生 SETTABLE 指令
  else
    报告错误.

这里解释下为什么 storevar() 没出现的其它 var 类型:
  1. VEXP: 是右值, 不能当做左值用, 所以不出现.
  2. VDOT: 在 storevar() 调用前(如在 assignment() 函数中), 转为
    VINDEXED 类型的, 所以没有 SETDOTTED 指令与 GETDOTTED 对应,
    是有点奇怪. 也许这种不匹配现象在后续版本有变化?
  3. upvalue 类型的: 在前面解析中已经转换为 VEXP 类型了.
    这里意味着 upvalue 类型的只是做右值, 不能当左值, 即不能被修改.


解析器改为使用 LL 文法的手写的递归下降解析器, 在文法上要改变, 在
代码生成上也要改变以适应, 尤其是表达式和 if 语句块. 有时间我们再
详细学习吧.

 

下面再看看新引入的闭包问题. 上面研究的时候已经遇到 upvalue 类型的
变量了, 我们可以合理推测 lua 3.1 中闭包"只是"将上一级函数的局部变量
"复制" 到被返回的子函数中, 来实现闭包的. 下面的例子验证这一点:
  function f(n)
    local upv = n
    print ('before create rf(), upv = ' .. upv)
    local rf = function()  -- 准备用来返回的闭包函数
      print ('inner %upv = ' .. %upv)
    end
    upv = upv + 100
    print ('after create rf(), upv = ' .. upv)
    return rf
  end

  rf = f(123) -- get the closure
  rf()        -- call the closure

这个例子执行的结果为:
  before create rf(), upv = 123
  after create rf(), upv = 223
  inner %upv = 123

结果是返回的闭包函数 c 在调用时 %upv 已经被复制到 c 的 upvalue[]
数组中了, 所以后面再改变也不会反应到闭包函数中了.

另外在内部函数 rf() 中, 只能用 %upv 语法使用外层变量, 否则会报告
语法错误. 再就是只能将 %upv 做右值用, 不能写 %upv = 789 当左值用.
这些都可以容易的验证出来.

下面研究如何实现闭包的, 为此函数 pushupvalue() 被下面仔细查看:
  pushupvalue(l, NAME) -- NAME 为此 upvalue 的名字, 如上例中的 "upv"
    判断略
    i = indexupvalue(NAME)
    产生代码 PUSHUPVALUE i

其中函数 indexupvalue(NAME):
  在当前正在编译的函数 FuncState *f 中查找 upvalues[] 数组, 找到
    则返回索引 i
  未找到, 则添加一个新的 upvalue 项到 f->upvalues[] 中.

在虚拟机 lvm.c 的函数 lua_execute() 中, 指令 PUSHUPVALUE 为:
  case PUSHUPVALUE:
    *top++ = closure->consts[upvalue 的索引];

即从 closure (表示当前正在执行的闭包函数), 的表格 consts[] 指定索引
位置中加载该 upvalue 的值. 现在剩下的最后一个问题, 该 upvalue 是什么
时候被复制到 consts[] 中的? 最合理的猜测是, 当该 closure 被创建的
时候被填入的, 否则我们上面那个例子, 在后面的改变也应该会影响该值,
事实是没有影响. 故而下面继续研究:

在产生式:
  stat -> FUNCTION funcname body  --- 用于定义函数的产生式
  body -> '(' parlist ')' chunk END <%代码块1%>
后一个 body 的产生式, 代码块1 处会调用 func_onstack() 函数, 有关
upvalue 值复制的秘密操作应该就藏在这里:

func_onstack(FuncState *func):
  for (i = 0; i < func->nupvalues; i++)
    lua_pushvar(ls, &func->upvalues[i]);
  产生代码 CLOSURE func->nupvalues

其中的 lua_pushvar() 部分产生将 upvalue 压栈的指令, 应该一定是上一级
函数的 VLOCAL 类型的变量(因此 lua 这里似乎不支持多层上级).

下面看虚拟机中 CLOSURE 指令:
  case CLOSURE:
    *top++ = consts[aux] -- 推测是得到闭包的函数原型地址
 luaV_closure(*pc++) -- 应是产生闭包函数, 根据要绑定的闭包值

函数 luaV_closure(nelems):
  Closure *c = new Closure() -- 新建一个闭包对象
  c->consts[0] = Func -- 函数原型
  c->consts[...] = 从栈上复制
  返回此创建的闭包.

总结: lua 3.1 实现了闭包, 但比较简单有限:
1. 闭包变量在创建闭包函数之后, 发生的改变不再影响到闭包函数了.
2. 闭包变量只能是上一级父函数的, 不能是更多层级的父函数(代码上看是这样,
   未实测验证)
3. 语法上要用 %upv 形式, 也许有清晰的优点, 也许有麻烦的缺点?
4. 从语义上说, 单词 upvalue 表示 "上一级的值", 似乎比较贴切.

实现的具体方法:
1. 分解函数对象为函数原型(FuncState) 和闭包函数(Closure) 两个对象,
  后续 lua 版本这个区分更明显, 引用也更清晰. lua 3.1 用 consts[0] 引用,
  即麻烦, 也不清晰.
2. 闭包函数 Closure 在创建的时候, 复制上一级父函数的被引用的局部变量到
  Closure 的 consts[] 表中, 这些变量被 "闭包" 到该 Closure 中, 后续仍
  可使用. 但这样的 "复制" 实现, 语义上应不完备. const 语义上表示这些值
  是常量了.
3. 新增了几条指令用于支持闭包: CLOSURE 指令用于创建闭包; PUSHUPVALUE
  用于读访问闭包变量, 没有写闭包变量的指令(其被当 const 对待).

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 54
博文 150
码字总数 226172
作品 0
昌平
在C++项目中引入Lua(AlphaGo使用的方案)

最近大火的AlphaGo,其中的deepmind已经开源,可以到github中下载https://github.com/deepmind/lab·,网上还有一个基于Python开源AlphaGo,那个不是google的。通过看deepmind源码,我们可以...

夏曹俊 ⋅ 2017/02/09 ⋅ 0

LuaJIT 2.0.3 稳定版发布,Lua 编译器

LuaJIT 2.0.3 发布,此版本是目前最新的稳定版本。更新内容如下: 添加了 PS4 移植 Add support for multilib distro builds. Fix OSX build. Fix MinGW build. Fix Xbox 360 build. Improv...

oschina ⋅ 2014/03/13 ⋅ 6

编写C函数的技术-《lua程序设计》 27章 学习

1.数组操作 void luarawgeti(luaState * L ,int index,int key) void luarewseti(luaState * L,int index,int key) index表示table在栈的位置,key表示元素在table中的位置 test.lua内容 tab ......

技术小阿哥 ⋅ 2017/11/26 ⋅ 0

Python二次元世界-Lisp的帝国斜阳 lambda与closure

Python二次元世界-函数式编程 Function , lambda与closure 本章讲述Python语言自Lisp语言演变而来的一些高级函数编程技巧 如闭包(closure) 匿名函数(lambda) 生成器(yield) 嵌套作用域(ne...

圣何塞白话人 ⋅ 2012/05/13 ⋅ 0

[转] Javascript闭包

资料: http://kb.cnblogs.com/page/110782/ 当function里嵌套function时,内部的function可以访问外部function里的变量。 function foo(x) {var tmp = 3;function bar(y) { }bar(10);} foo(......

庸夫俗子 ⋅ 2011/11/18 ⋅ 0

lua语言的闭包问题

lua语言的闭包问题 function newCounter() local i = 0 return function() i = i + 1 return i end end c1=newCounter() print(c1()) --1 print(c1()) --2 请问是为什么,最好具体点,我看了......

lodirk ⋅ 2014/01/08 ⋅ 1

kahlua java上的lua脚本介绍及性能测试

kahlua是一款基于CLDC1.1且非常小巧的Lua解释器,它很容易扩展。只需要配合一个Lua编译器,就可以执行编译后的Lua源代码。 也可以用在j2se上,而且速度还非常快!!支持把lua文件的编译执行,...

JavaGG ⋅ 2010/05/24 ⋅ 2

说说 Python 中的闭包

(点击上方公众号,可快速关注) 来自: cicaday https://segmentfault.com/a/1190000007321972 Python中的闭包不是一个一说就能明白的概念,但是随着你往学习的深入,无论如何你都需要去了解...

Python开发者 ⋅ 01/09 ⋅ 0

Lua编译器--LuaJIT

LuaJIT:采用C语言写的Lua的解释器的代码 LuaJIT is a Just-In-Time Compiler for the Lua* programming language. LuaJIT试图保留Lua的精髓--轻量级,高效和可扩展. 功能 所有的函数缺省会被...

匿名 ⋅ 2010/03/05 ⋅ 0

lua函数深入了解

函数是一种“第一类值”,它们具有特定的词法域。 “第一类值”表示在lua中函数域其他传统类型的值句用相同的权利。函数可以存储到变量中(无论是全局变量还是局部变量)或table中,可以作为...

安卓农民种苹果 ⋅ 2015/07/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring Cloud构建微服务架构—创建“服务注册中心”

创建一个基础的Spring Boot工程,命名为eureka-server,并在pom.xml中引入需要的依赖内容: <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-par......

itcloud ⋅ 15分钟前 ⋅ 0

拖动

<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>event</title> <style> #box { width: 100px; height: 100px; background-color: aquamarine; position: absolute; } </style......

fyliujj ⋅ 17分钟前 ⋅ 0

es6 polyfill array

polyfill之javascript函数的兼容写法——Array篇 1. Array.isArray(obj) if (!Array.isArray) { Array.isArray = function(arg) { return Object.prototype.toString.call(arg) === '[objec......

球球 ⋅ 19分钟前 ⋅ 0

kibana启动异常

检查一下:kibana.yml 每一对key:value中,冒号之后应有空格。

增删改查1 ⋅ 21分钟前 ⋅ 0

js修改img的src属性刷新图片时的图片缓存问题

问题:上传一张图片,通过js更新src属性刷新图片使其即时显示时, 当img的src当前的url与上次地址无变化时(只更改图片,名称不变,不同图片名称相同)图片不变化(仍显示原来的图片) 但通过...

HaierBrother ⋅ 21分钟前 ⋅ 0

Mysql

1.Jdbc Url 设置allowMultiQueries为true和false mysql的批量更新是要我们主动去设置的, 就是在数据库的连接url上设置一下,加上* &allowMultiQueries=true *即可。 参数名称 参数说明 缺省...

瑟青豆 ⋅ 25分钟前 ⋅ 0

mysql导出导入表结构与数据

当我们需要进行数据迁移时,mysql自带的mysqldump会是最好的方式。 1.导出某张表的结构和数据 首先,我们应当使用服务器,打开终端,连接到所需要导出的表所在的服务器上。执行命令: mysqld...

hengbao5 ⋅ 25分钟前 ⋅ 0

世界杯也走向“比拼”大数据的时代

《日本经济新闻》6月19日报道称,俄罗斯足球世界杯已于6月14日揭开战幕。作为第21次举办的足球世界杯,如何活用大数据有可能成为决定各支球队胜负的重要因素。从对阵球队的分析到战术建议,还...

加米谷大数据 ⋅ 25分钟前 ⋅ 0

金额转为千分制,金额转中文大写

金额转关为大写 /** 数字金额大写转换(可以处理整数,小数,负数) */ function digitUppercase(n){ if(!n) reutrn "" let fraction = ['角', '分']; let digit = [...

YXMBetter ⋅ 28分钟前 ⋅ 0

开发利器JRebel部署SpringBoot项目

不要以为年纪轻轻就跌倒了人生谷底,未来还有更大的下降空间等着你。 idea下载和安装JRebel 激活JRebel 访问https://my.jrebel.com/ 使用facebook或twitter登录 勾选 Build project automati...

郑龙飞 ⋅ 34分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部