jMiniLang的设计思路

前言

项目地址:https://github.com/bajdcc/jMiniLang

演示视频:https://www.bilibili.com/video/av13294962

jMiniLang是一个Java实现的基于栈的解释器,包含了语法分析和虚拟机等两大内容。

基于这个虚拟机呢,用脚本搭建了一个简单的“操作系统”。本来只是用来测试下解释器的语法特性的,后来把一些想法加了进去。

截图在https://github.com/bajdcc/jMiniLang/releases里面,操作视频在。
系统的架构倒是比较“另类”的,它完全就是由管道和互斥来构造的。对于进程而言,无非就是阻塞来实现进程同步,管道一方面可以形成阻塞,另一方面可以实现进程间通信,可以说,管道机制非常有效。

下面就简单讲讲jMiniOS系统的设计思路。几个部分:语法特性、同步机制、系统架构。(一共就3张图)

语法特性

语法分析用LALR的,只要设计好BNF就能解析,parser涉及的内容太多,这里就略了。这里说下某些特性的实现:闭包和协程。

闭包

说到闭包,就会提到lambda。实现闭包,首先,系统需要能够动态地返回函数,其次,返回的函数中会引用到函数体外部的变量

closure.png

上图中的fact会返回一个lambda(fk其实是多余的,只是语法实现功能有限)叫fk,fk中的一句"call f(n-1)"引用到了外层fact函数的参数f。

那这个特性如何去实现呢?

想像一下我现在执行fact函数时,发生的情况:

  1. f压栈,调用fact
  2. 栈上取参f,放入数据栈
  3. 返回一个lambda(图中是fk)

这时执行这个返回的lambda(注意它有一个参数n):

  1. 参数n压栈,调用lambda
  2. 栈上取参n
  3. 如果n大于0,跳到4,否则跳到5
  4. 执行f(n-1),乘上n,再返回
  5. 返回1

这里的问题是:在lambda中,如何执行f(n-1)呢?进一步要思考的问题:返回的lambda知晓不知晓f的存在?什么时候知晓的?解决了问题,就能实现闭包。

便于描述,将图中的f称作一个闭包(变量)。

思路:动态解决+静态解决。

从语法分析开始说起,解析fact函数之前,fk函数已经解析完毕了,这是由LR分析的特点决定的。在解析fk函数之前,fact的参数f已经被我放入一层层的符号表中,不管找到的这个f是在哪一层函数中的,只要找到了,确认不是引用错误就行。

步骤一:静态解决

在符号表中找到f后,接下来,我要让fk函数进行自检。由于这时fk函数已经是AST中的一个结点了,只要递归调用自检函数就可以了。自检很简单,凡是引用某个变量的,就将引用对象放入引用表中。然后,看一下fk函数的参数表。最终,引用表-参数表=闭包

这样,通过自检,我在解析fact的过程中知道了fk的闭包。

解析好语法树后,就可以生成指令了。对于fk这个lambda,生成指令包含两大部分——实现部分和赋值部分。

实现部分就是将fk函数里面代码翻成指令(然后知道了fk第一行指令的位置fk_line),好理解。

赋值部分就是生成lambda并赋值给fk,指令类似于"load_lambda fk_line",这是因为对lambda而言,需要做一些额外的工作,因为这是动态语言,所以必须生成一个为function的动态类型。那闭包又该如何处理呢?对于函数中的闭包需要“额外优待”,即生成指令时将这些变量载入进去,每个变量有个自己的编号,载入这些编号就可以了。所以对于图中的fk,在"load_lambda fk_line"前肯定要有个声明闭包的指令"load_lambda_reference f",这样在生成动态类型时,会将外部变量f的值绑定到fk函数中

步骤二:动态解决

动态运行的指令类似于(这里简化了,跟项目生成的有差别):

【fk函数的实现指令】
[1000] 载入参数n到数据栈
....
[1010] 返回

【fact函数的实现指令】
[2000] 载入参数f到数据栈
[2001] 将f放到额外的一个栈中(用于存放闭包)
[2002] 加载函数fk,地址1000,这时检测额外栈中有闭包,故生成动态类型RuntimeFunction时加上一个闭包f

【调用fact函数返回的lambda--fk】
[3000] 将n取出并保存到数据栈中
....
[3005] "call f(n-1)"对应的指令,这时要加载f,到符号表中找肯定找不到(因为当前执行的环境中没有f),因而尝试到当前环境fk的闭包里去找,找到后执行它并返回

闭包部分总结

  1. 语法分析部分:AST中查找闭包(变量),将闭包的信息存入AST结点ExpFunc中

  2. 指令生成部分:在AST中的调用结点ExpInvoke中,如果发现了闭包信息,就添加额外的指令load_lambda_reference(本项目中是压栈指令,将闭包的编号压栈,再将闭包数量压栈)

  3. 运行时部分:执行到load_lambda指令时,确认是否有闭包在栈中,如果有,将其添加到运行时函数类型RuntimeFunction中

  4. 查找变量:先在当前(函数)域中查找正常声明的变量(用var声明的),找不到,再从域中查找闭包(变量),再找不到,从上一层域中找,以此类推

协程

coroutine.png

认识协程,先想一个问题:实现对[a,b]中每个整数的依次处理(比方,实现[1,100]这一百个数的依次打印)

【简单方法】for循环100个数,分别调用之
【一般方法】先生成一个数组,for循环放入1~100这100个数,然后对数组遍历
【另类方法】协程,如图所示

上面除另类方法外,应该都好理解。另类方法其实是一种新的语法特性,协程。

在上面的问题上增加难度,现在对[a,b]进行扩展,变成[a,正无穷),如何?

【简单方法】依然可以
【一般方法】数组占用了大量内存空间,程序gg
【另类方法】依然可以

再降低难度,将范围[a,b]变成列表{101,203,407,666,888},列表里数是我胡乱写的,如何?

【简单方法】gg
【一般方法】将列表中的数依然放入数组并遍历
【另类方法】依然可以(yield 101,yield 203...)

需要3的倍数,...,再分别调用,如何?

【简单方法】可以
【一般方法】gg
【另类方法】魔性,"foreach (var i : call g_range(1, INT_MAX) * 3) {}",改个数字即可

综上,协程确实在某些方法与传统方法有着差别。

项目中用yield声明协程函数,返回用"yield n"。

foreach搭配yield的使用,使得foreach每次迭代时,会调用一次协程函数,协程返回一个当前索引i,然后再执行foreach循环体。第二次循环调用的协程不会重新开始,而是在第一次循环的基础上继续执行,这,就是协程的精华。常规语法时,每次调用同一个函数,如果函数不依靠任何外部信息,那么每次返回的值都是相同的,而协程不一样,它每次被调用后,就“自动暂停”了。

协程要怎样实现呢?

协程的实现基于for循环。for的语法是"for (声明指令; 判断指令; 迭代指令) {主体}";foreach的语法是"foreach(var 变量名 : yield函数表达式){主体}"。

for循环生成指令的主要步骤:

  1. 生成声明指令
  2. 生成break和continue的label
  3. 生成判断指令
  4. 生成循环主体指令
  5. 生成迭代指令(如i++)

而foreach生成指令的步骤:

  1. 生成声明指令
  2. 生成break和continue的label
  3. 调用协程函数(函数如果返回空则break)
  4. 生成循环主体指令
  5. 生成迭代指令(如i++)

在foreach中协程一直存在,既然它的状态是持续的,因而必然要保存其状态。

先设计好一些指令:

  1. iyldl 协程返回
  2. iyldr 协程进入
  3. iyldx 协程销毁
  4. iyldy 协程创建
  5. iyldi 协程栈数据入栈
  6. iyldo 协程栈数据出栈

上述指令负责程序在foreach间与协程函数间进行切换,以及数据交换等操作。

【协程函数翻译指令】

无非是原有的return指令变成了yield return指令。原先:ipushXXX/iret;现在:ipushXXX/iyldi/iyldl,即数据压栈、数据进协程栈、协程切回。

【调用者foreach指令】

调用协程的具体过程

判断协程是否初始化(首次创建),如果没有创建,就初始化。

初始化操作:

  1. 调用类型:ipush 调用类型/iyldi
  2. 协程传参:ipush 每个参数/后面带iyldi
  3. ipush 地址:传协程入口地址
  4. iyldy:创建协程,此时协程栈的大小=1(调用类型)+参数数量+1(地址)

如果已经初始化完成,进行:

  1. iyldr:切换到协程
  2. iyldo:将数据出协程栈,入数据栈
  3. ijnan:判断数据合法性,如果是null,就退出foreach循环

协程的创建

  1. 读取协程栈中的数据:调用类型+协程参数+协程地址。
  2. 切换到协程并执行

由于有协程栈和调用栈,所以栈与栈间存在父子关系。协程是当前调用栈创建出的,因为要设置父子关系parent。这样,当协程返回时,只要找到其parent就可以了(子找父)。反过来时,父根据hash表找到子,这是因为同一时刻同一层次也只有唯一一个协程存在。

循环出口的清理工作

执行iyldx,销毁创建的协程。

协程部分总结

  1. 调用栈部分:协程就是一种调用栈,而调用栈可以创建协程(调用)栈,反之亦可,可见调用栈存在层级关系,栈间的切换可以用类似树中父子关系实现
  2. 协程传参:通过协程栈数据通道进行传参,这个通道维系当前调用栈和产生的协程调用栈,且协程调用栈和普通调用栈一样,也有自己的数据栈和函数栈
  3. 指令部分:由上述设计的6种指令组成,不过还可进一步简化,值得注意的是,协程的创建只能创建一次,后一次必须检测协程是否已存在,避免重复创建

同步机制

jMiniLang采用的单线程模拟多进程的方式,这种比较容易实现。

多进程的世界,有两个典型问题——互斥量、信号量。进程的状态我设置得很简单——阻塞和非阻塞。把互斥量、信号量这两个问题解决了,就ok。

从时间来看,互斥量的使用场景应是激烈竞争、占用时间少的情况;信号量的情况是竞争不激烈、占用时间长。基于此情况,我将多数操作采用自旋锁实现,如锁定单变量的操作等。将少数耗时操作用信号量去做,即让进程休眠,节省开销。

互斥量

自旋锁实现是很简单的,就是轮循。由于解释器是单线程的,因此非常easy。

我添加了全局共享变量,让互斥量有用武之地。比如进程间的等待操作,将pid挂到等待列表上,而读写等待列表的操作是互斥的,且读写操作很快。

代码写来就是"lock(var);操作...;unlock(var);",而lock的操作就是"while(检测var有锁不,有就锁定);操作...",unlock的操作"直接解锁var变量"。其中这个while就是轮询。事实上,这些轮询操作都可以转化为用信号量去做,只是要设计一些等待列表。上面说到使用场景不怎么花时间(就改个变量),而用信号量会让进程休眠,强行进程切换,因此用信号量反而不适宜。

PS:jMiniLang中的互斥量是用自旋锁实现的,这不意味着所有互斥量都是用自旋锁做的。

信号量

这里,信号量我主要用block()和wakeup(),就是阻塞和唤醒。这两个方法的使用不是在用户代码层面,是在虚拟机层面。

管道与信号量

本系统中我设计了管道,相信管道这一概念已非常普及了。我没有直接提供操作信号量的API,而是提供了管道的API。

管道的操作:

  1. 创建/销毁
  2. 读/写

其中,管道读是一个阻塞操作,利用这一阻塞,可以用管道去实现信号量的功能。

原理也很简单,设计的命名管道,每一管道有缓冲区。读:如果缓冲区无数据,就阻塞,否则取数据;写:向缓冲区写数据,并唤醒阻塞的进程。

另外,进程等待(join)操作也是阻塞的。类似的耗时操作都可以改成阻塞的。

系统架构

用jMiniLang解释器做个仿OS的程序,姑且称作jMiniOS吧。

它的设计理念:

  1. 基于互斥量和信号量
  2. 仅有共享变量服务(全局set/get)和管道服务
  3. 微服务架构service
  4. 多进程间的输入/输出流
  5. 中断例程task(流实现)

服务组成

ps.png

模拟IRQ的系统服务task:

  1. remote 用户界面输入输出
  2. task 微服务代理
  3. print 控制台debug输出
  4. signal 信号(如poweroff)

用户服务service(目前实现的):system util ui net

微服务架构

三种对象:客户端(调用者)、代理端(系统服务)、服务端(被调用者)

下面区别三种对象:客户端、代理端、服务端

  1. 客户端(调用者)
    调用方法:客户端进程调用g_task_get/g_task_get_fast/g_task_get_fast_arg方法,获取数据

  2. 代理端(充当中介)
    已实现的task_handler,它的目的是连接客户端和服务端

  3. 服务端(服务者)
    这方面要自己实现

调用顺序:

  1. 客户端调用task_get_fast等方法
  2. task_get_fast安排好请求数据,触发int#1服务中断
  3. 中断会调用task_handler代理方法

客户端向代理端发送消息

  1. 准备请求数据
  2. 锁定等待队列
  3. 将当前进程添加至代理端的等待队列中
  4. 解锁队列
  5. 报告服务中断例程
  6. 发送消息事件给中断例程,使之调用task_handler
  7. 此时代理端会向服务端发送请求
  8. 等待代理端处理完毕

代理端处理客户端的消息

  1. 锁定等待队列
  2. 取最早等待的进程,移除它
  3. 解锁队列
  4. 读取客户端的数据
  5. 唤醒服务端,这时服务端在处理请求
  6. 连接服务端
  7. 防止多个代理端同时请求服务端,用管道做阻塞
  8. 处理完毕,唤醒客户端

此架构的好处

如果没有代理端,那么客户端和服务端直接相连,由于服务端只有一条输入管道,那么多个客户端发送的数据会发生冲突,因此多个客户端的请求只能一个个来,代理端就是这个作用,维护一个等待队列。

另外,服务端的接口不会暴露给客户端,保证了安全。

进程传输流

jMiniOS提供了一个简单的shell,用来执行一些程序,依照linux,采用管道去处理父/子进程间的输入输出流。

以最简单的pipe函数为例:

  1. 获取本pid的输入流句柄
  2. 获取本pid的输出流句柄
  3. 读取输入流,在读取操作中将数据传给输出流

当最内层的进程销毁输出流后,流将被链式销毁,直到最外层进程。实现ctrl+c的思路:销毁各子进程的输入流、创建SIGKILL类似的共享变量。

由于我未实现kill_process函数,所以每个进程只能自己退出,不会强行被kill,这样只要所有进程都退出,就说明堵塞的调用没有问题。

总结

从15年开始第一行代码,到现在约莫2W行(除去废话),每次加个新功能要想半天+查错N天,但是还是坚持下来了。写上面的闭包和协程时因为当时懒没多少注释,还打log半天才搞懂当时的设计思路,所以写写总结也是必要的,毕竟是坚持得最久的一个repo了。

把parser+vm+ui结合起来,除了fastjson和log4j也没用其他库,白手起家,自娱自乐~

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,884评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,347评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,435评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,509评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,611评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,837评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,987评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,730评论 0 267
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,194评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,525评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,664评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,334评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,944评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,764评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,997评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,389评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,554评论 2 349

推荐阅读更多精彩内容

  • 前言 人生苦多,快来 Kotlin ,快速学习Kotlin! 什么是Kotlin? Kotlin 是种静态类型编程...
    任半生嚣狂阅读 26,168评论 9 118
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 171,790评论 25 707
  • 一、温故而知新 1. 内存不够怎么办 内存简单分配策略的问题地址空间不隔离内存使用效率低程序运行的地址不确定 关于...
    SeanCST阅读 7,784评论 0 27
  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,213评论 11 349
  • 妈妈呛流了眼泪 捂着鼻子责问: 你又在屋子里偷偷抽烟了? 孩子低头抠着手指 ——我只是想闻闻爸爸的味道...
    LittleHurricame阅读 270评论 3 1