Geekly articles weekly

我们编写编程语言，第1部分：我们编写语言VM

引言


祝所有habrachitateli美好的一天！

因此，也许值得一说的是，我的工作目标是写出许多雕像，并以此为基础，一路创建自己的功能齐全的PL（零个人），然后与感兴趣的人分享我的知识，最佳实践和经验。

我将在此之前描述语言的创建。

他对许多人感兴趣，并在评论中引发了激烈的讨论。 因此，该主题对许多人来说都很有趣。

我认为值得立即发布有关该项目的信息：

网站 （稍后将填充文档）。
资料库

要亲自触摸项目并查看运行中的所有内容，最好下载存储库并从bin文件夹中运行所有内容。 在此版本中，我不急于上传语言和运行时的最新版本，因为 有时候我太懒了。

我可以用C / C ++和对象Pascal进行编码。 自从我在FPC上写了这个项目 我认为这种语言更简单，更适合于这样的写作。 第二个决定性因素是FPC支持大量目标平台，并且可以用最少的改动为所需平台重建项目。 如果由于某种原因我不喜欢Object Pascal，那么就不要急于关闭该帖子，不要在评论中扔石头。 这种语言非常漂亮和直观，但是我不会提供太多代码。 正是您所需要的。

因此，也许我将开始我的故事。

我们设定目标


首先，任何项目都需要其目标和传统知识，而这些目标和传统知识必须在将来实施。 有必要预先决定要创建哪种类型的语言，以便为其编写主VM。

决定我的虚拟机进一步发展的关键点如下：

  • 动态打字和打字。 我决定在VM的开发阶段组织她的支持。
  • 多线程支持。 我事先将此项目包括在此列表中，以便正确设计VM的体系结构并在VM的核心级别组织对多线程的支持，而以后不会再使用cru拐杖了。
  • 导出外部方法。 没有这个，语言将毫无用处。 除非将其嵌入任何项目中。
  • 语言的编译（成一个抽象的可执行文件）。 部分编译或解释？ 在很大程度上取决于此。
  • 通用VM体系结构。 堆栈或注册将成为我们的VM吗？ 我试图实现这一点。 我选择了堆叠式VM作为支持。
  • 您如何看待使用变量，数组，结构？ 就个人而言，那时我想实现一种语言，其中几乎所有内容都与隐式指针相关联，因为这种方法将大大节省内存并简化开发人员的工作。 如果我们允许将大的东西传递给方法，则只会自动转移指向该大东西的指针。

因此，我选择了以上优先级，然后开始实现语言虚拟机。 当然这很奇怪，通常通常先编写任何解析器/翻译器，然后再编写VM。 好吧，我开始按此顺序开发该项目，我将按照开发它的顺序对其进行进一步描述。

我必须马上说，我尽可能雄辩地称呼VM-SVM（基于堆栈的虚拟机）。

让我们从变量类的实现开始


最初，我只是使用了一个变体类型，因为它更加简单快捷。 这是一个拐杖，但它支撑了该项目，并允许我快速实现VM和语言的第一个版本。 后来我坐在代码旁，编写了“变体”的实现。 本质上，您需要编写一个在内存中存储指向值的指针的类，在我的实现中，该类为null/cardinal/int64/double/string/array 。 可以使用案例类型输入，但是我认为实现我的实现方式会更好。

在开始编写类代码之前，我决定立即将{$ H +}指令放在模块头中，以更灵活地支持将来的语言中的字符串。
附言 对于可能不了解H-和H + FPC模式之间差异的用户。

在H模式下汇编代码时，字符串将显示为字符数组。 当H +-作为指向一块内存的指针时。 在第一种情况下，这些行最初将固定长度，默认情况下限制为256个字符。 在第二种情况下，这些行将可以动态扩展，并且可以在其中塞满更多字符。 它们的工作速度会稍慢一些，但功能会更多。 使用H +，您还可以将字符串声明为字符数组，例如以这种方式：

 var s:string[256];
因此，对于初学者来说，我们将为Enum声明一个类型，我们将其用作某个标志来通过指针确定数据类型：

 type TSVMType = (svmtNull, svmtWord, svmtInt, svmtReal, svmtStr, svmtArr);

接下来，我们描述变量类型的基本结构和一些方法：

  TSVMMem = class m_val: pointer; m_type: TSVMType; constructor Create; destructor Destroy; procedure Clear; end; ... constructor TSVMMem.Create; begin m_val := nil; m_type := svmtNull; end; destructor TSVMMem.Destroy; begin Clear; end; procedure TSVMMem.Clear; inline; begin case m_type of svmtNull: { nop }; svmtWord: Dispose(PCardinal(m_val)); svmtInt: Dispose(PInt64(m_val)); svmtReal: Dispose(PDouble(m_val)); svmtStr: Dispose(PString(m_val)); svmtArr: begin SetLength(PMemArray(m_val)^, 0); Dispose(PMemArray(m_val)); end; else Error(reVarInvalidOp); end; end;

该类不继承任何东西，因此可以省略构造函数和析构函数中的继承调用。 我将注意内联指令。 当然，最好在文件标题中添加{$ inline on}。 它在VM中的积极使用大大提高了生产率（某处的Mb高达15-20％！）。 她告诉编译器，方法的主体最好嵌入在调用的位置。 最后，输出代码会稍大一些，但是会更快地工作。 在这种情况下，建议使用内联。

好的，在这一阶段，我们已经冲洗了班级的基础。 现在，我们需要在我们的课程中描述一些setter和getter（setter和getter）。

我们的任务是编写一些方法，这些方法将使您可以塞入并稍后从类中获取值。

首先，让我们找出类的值分配。 首先，您可以编写一个通用的setter，然后针对单个数据类型：

 procedure TSVMMem.SetV(const value; t:TSVMType); inline; begin if (m_val <> nil) and (m_type = t) then begin case t of svmtWord: PCardinal(m_val)^ := Cardinal(value); svmtInt: PInt64(m_val)^ := Int64(value); svmtReal: PDouble(m_val)^ := Double(value); svmtStr: PString(m_val)^ := String(value); end; end else begin if m_val <> nil then FreeMem(m_val); m_type := t; case t of svmtWord: begin New(PCardinal(m_val)); PCardinal(m_val)^ := Cardinal(value); end; svmtInt: begin New(PInt64(m_val)); PInt64(m_val)^ := Int64(value); end; svmtReal: begin New(PDouble(m_val)); PDouble(m_val)^ := Double(value); end; svmtStr: begin New(PString(m_val)); PString(m_val)^ := String(value); end; else Error(reVarTypeCast); end; end; end; ... procedure TSVMMem.SetW(value:cardinal); inline; begin if (m_val <> nil) and (m_type = svmtWord) then PCardinal(m_val)^ := value else begin if m_val <> nil then FreeMem(m_val); m_type := svmtWord; New(PCardinal(m_val)); PCardinal(m_val)^ := value; end; end;

现在，您可以为几个吸气剂编写代码：

 function TSVMMem.GetW:cardinal; inline; begin Result := 0; case m_type of svmtWord: Result := PCardinal(m_val)^; svmtInt: Result := PInt64(m_val)^; svmtReal: Result := Trunc(PDouble(m_val)^); svmtStr: Result := StrToQWord(PString(m_val)^); else Error(reVarTypeCast); end; end;

好的，很好，既然您已经花了一段时间盯着IDE并热情地输入了setter和getter的代码，我们面临着实现对我们的数学和逻辑运算类型的支持的任务。 作为示例，我将给出加法操作的实现：

 procedure TSVMMem.OpAdd(m:TSVMMem); inline; begin case m_type of svmtWord: case m.m_type of svmtWord: SetW(GetW + m.GetW); svmtInt: SetI(GetW + m.GetI); svmtReal: SetD(GetW + m.GetD); svmtStr: SetD(GetW + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtInt: case m.m_type of svmtWord: SetI(GetI + m.GetW); svmtInt: SetI(GetI + m.GetI); svmtReal: SetD(GetI + m.GetD); svmtStr: SetD(GetI + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtReal: case m.m_type of svmtWord: SetD(GetD + m.GetW); svmtInt: SetD(GetD + m.GetI); svmtReal: SetD(GetD + m.GetD); svmtStr: SetD(GetD + StrToFloat(m.GetS)); else Error(reVarInvalidOp); end; svmtStr: case m.m_type of svmtWord: SetS(GetS + IntToStr(m.GetW)); svmtInt: SetS(GetS + IntToStr(m.GetI)); svmtReal: SetS(GetS + FloatToStr(m.GetD)); svmtStr: SetS(GetS + m.GetS); else Error(reVarInvalidOp); end; else Error(reVarInvalidOp); end; end;

一切都很简单。 可以用类似的方式描述进一步的操作，现在我们的课程已经准备就绪。
当然，对于数组，您仍然需要几个方法，一个通过索引获取元素的示例：

 function TSVMMem.ArrGet(index: cardinal; grabber:PGrabber): pointer; inline; begin Result := nil; case m_type of svmtArr: Result := PMemArray(m_val)^[index]; svmtStr: begin Result := TSVMMem.CreateFW(Ord(PString(m_val)^[index])); grabber^.AddTask(Result); end; else Error(reInvalidOp); end; end;

太好了 现在我们可以继续。

我们实现了一个堆栈


一段时间后，我想到了这样的想法。 堆栈必须同时为静态（为了提高速度）和动态（为了提高灵活性）。

因此，堆栈以块的形式实现。 即 它应该如何工作-最初，堆栈的数组具有一定的大小（我决定将块大小设置为256个元素，以使其美观而不小）。 因此，该阵列包含一个计数器，指示堆栈的当前顶部。 内存重新分配是一项超长的操作，可以减少执行频率。 如果将更多的值压入堆栈，则可以始终将其大小扩展为另一个块的大小。

我带来了整个堆栈的实现：

 type TStack = object public items: array of pointer; size, i_pos: cardinal; parent_vm: pointer; procedure init(vm: pointer); procedure push(p: pointer); function peek: pointer; procedure pop; function popv: pointer; procedure swp; procedure drop; end; PStack = ^TStack; procedure TStack.init(vm: pointer); begin SetLength(items, StackBlockSize); i_pos := 0; size := StackBlockSize; parent_vm := vm; end; procedure TStack.push(p: pointer); inline; begin items[i_pos] := p; inc(i_pos); if i_pos >= size then begin size := size + StackBlockSize; SetLength(items, size) end; end; function TStack.peek: pointer; inline; begin Result := items[i_pos - 1]; end; procedure TStack.pop; inline; begin dec(i_pos); if size - i_pos > StackBlockSize then begin size := size - StackBlockSize; SetLength(items, size); end; end; function TStack.popv: pointer; inline; begin dec(i_pos); Result := items[i_pos]; if size - i_pos > StackBlockSize then begin size := size - StackBlockSize; SetLength(items, size); end; end; procedure TStack.swp; inline; var p: pointer; begin p := items[i_pos - 2]; items[i_pos - 2] := items[i_pos - 1]; items[i_pos - 1] := p; end; procedure TStack.drop; inline; begin SetLength(items, StackBlockSize); size := StackBlockSize; i_pos := 0; end;

在外部方法中，VM将指针传递给堆栈，以便它们可以从那里获取必要的参数。 稍后添加了指向VM流的指针，以便可以实现来自外部方法的回调调用，并且通常可以通过VM方法传递更多的权限。

因此，您如何熟悉堆栈的排列方式。 回调堆栈以相同的方式安排，以简化和方便调用和返回操作以及垃圾回收器堆栈。 唯一的是块的其他大小。

谈论垃圾


通常很多很多。 而且您需要做一些事情。

首先，我想谈谈如何以其他语言（例如Lua，Ruby，Java，Perl，PHP等）布置垃圾收集器。 它们的工作原理是对内存中对象的指针计数。

即 因此，我们为某些事情分配了内存，这是合乎逻辑的-指针立即放置在变量/数组/其他地方。 运行时垃圾收集器会立即将此指针与可能的垃圾对象列表一起添加到自身。 在后台，垃圾收集器不断监视所有变量，数组等。 如果可能垃圾列表中没有指向某物的指针，则意味着必须删除垃圾和其下的内存。

我决定卖掉我的自行车。 我更习惯于按照塔拉斯·布尔巴（Taras Bulba）的原则处理记忆。 我生了你-我的意思是，当我在下一堂课中打电话给下一个Free时，我会杀了你。 因此，我的VM的垃圾回收器是半自动的。 即 需要在手动模式下调用它并相应地使用它。 反过来，添加了指向已声明的临时对象的指针（此角色主要由翻译负责，而对开发人员则负责）。 要从其他对象下释放内存，可以使用单独的操作码。

即 调用时，垃圾收集器有一个现成的指针列表，您需要检查这些指针以释放内存。

因此，现在我们将处理编译为抽象的可执行文件


最初的想法是，用我的语言编写的应用程序可以在没有源代码的情况下运行，就像许多类似语言一样。 即 它可以用于商业目的。

为此，请确定可执行文件的格式。 我得到以下内容：

  1. 标头，例如“ SVMEXE_CNS”。
  2. 包含从中导入方法的库列表的部分。
  3. 所需方法的导入部分，从上面部分中的编号表示从中导入方法的库。
  4. 常量部分。
  5. 代码部分

我认为没有必要为这些部分提供实现解析器的详细步骤，因为您可以在自己的存储库中看到所有内容。

代码执行


解析了以上部分并初始化了VM之后，我们将其中一部分包含代码。 在我的VM中，执行未对齐的字节码，即 指令可以是任意长度。

一组操作码-虚拟机的说明，带有一些小注释，我在下面预先显示：

 type TComand = ( {** for stack **} bcPH, // [top] = [var] bcPK, // [var] = [top] bcPP, // pop bcSDP, // stkdrop bcSWP, // [top] <-> [top-1] {** jump's **} bcJP, // jump [top] bcJZ, // [top] == 0 ? jp [top-1] bcJN, // [top] <> 0 ? jp [top-1] bcJC, // jp [top] & push callback point as ip+1 bcJR, // jp to last callback point & rem last callback point {** for untyped's **} bcEQ, // [top] == [top-1] ? [top] = 1 : [top] = 0 bcBG, // [top] > [top-1] ? [top] = 1 : [top] = 0 bcBE, // [top] >= [top-1] ? [top] = 1 : [top] = 0 bcNOT, // [top] = ![top] bcAND, // [top] = [top] and [top-1] bcOR, // [top] = [top] or [top-1] bcXOR, // [top] = [top] xor [top-1] bcSHR, // [top] = [top] shr [top-1] bcSHL, // [top] = [top] shl [top-1] bcNEG, // [top] = -[top] bcINC, // [top]++ bcDEC, // [top]-- bcADD, // [top] = [top] + [top-1] bcSUB, // [top] = [top] - [top-1] bcMUL, // [top] = [top] * [top-1] bcDIV, // [top] = [top] / [top-1] bcMOD, // [top] = [top] % [top-1] bcIDIV, // [top] = [top] \ [top-1] bcMV, // [top]^ = [top-1]^ bcMVBP, // [top]^^ = [top-1]^ bcGVBP, // [top]^ = [top-1]^^ bcMVP, // [top]^ = [top-1] {** memory operation's **} bcMS, // memory map size = [top] bcNW, // [top] = @new bcMC, // copy [top] bcMD, // double [top] bcRM, // rem @[top] bcNA, // [top] = @new array[ [top] ] of pointer bcTF, // [top] = typeof( [top] ) bcSF, // [top] = sizeof( [top] ) {** array's **} bcAL, // length( [top] as array ) bcSL, // setlength( [top] as array, {stack} ) bcPA, // push ([top] as array)[top-1] bcSA, // peek [top-2] -> ([top] as array)[top-1] {** memory grabber **} bcGPM, // add pointer to TMem to grabber task-list bcGC, // run grabber {** constant's **} bcPHC, // push copy of const bcPHCP, // push pointer to original const {** external call's **} bcPHEXMP, // push pointer to external method bcINV, // call external method bcINVBP, // call external method by pointer [top] {** for thread's **} bcPHN, // push null bcCTHR, // [top] = thread(method = [top], arg = [top+1]):id bcSTHR, // suspendthread(id = [top]) bcRTHR, // resumethread(id = [top]) bcTTHR, // terminatethread(id = [top]) {** for try..catch..finally block's **} bcTR, // try @block_catch = [top], @block_end = [top+1] bcTRS, // success exit from try/catch block bcTRR, // raise exception, message = [top] {** for string's **} bcSTRD, // strdel bcCHORD, bcORDCH, {** [!] directly memory operations **} bcALLC, //alloc memory bcRALLC, //realloc memory bcDISP, //dispose memory bcGTB, //get byte bcSTB, //set byte bcCBP, //mem copy bcRWBP, //read word bcWWBP, //write word bcRIBP, //read int bcWIBP, //write int bcRFBP, //read float bcWFBP, //write float bcRSBP, //read string bcWSBP, //write string bcTHREXT,//stop code execution bcDBP //debug method call );

因此，您熟练地熟悉了我编写的VM可以执行的操作。 现在，我想谈谈这一切如何运作。

VM被实现为对象，因此您可以轻松实现多线程支持。

它有一个指向带有操作码，IP（指令指针）的数组的指针-执行指令的偏移量和指向其他VM结构的指针。

代码执行是一个很大的转换案例。

只需给出虚拟机的描述：

 type TSVM = object public ip, end_ip: TInstructionPointer; mainclasspath: string; mem: PMemory; stack: TStack; cbstack: TCallBackStack; bytes: PByteArr; grabber: TGrabber; consts: PConstSection; extern_methods: PImportSection; try_blocks: TTRBlocks; procedure Run; procedure RunThread; procedure LoadByteCodeFromFile(fn: string); procedure LoadByteCodeFromArray(b: TByteArr); end;

关于异常处理的一些知识


为此，VM具有一堆异常处理程序和一个较大的try / catch块，在其中封装了代码执行。 从堆栈中，您可以将具有入口点偏移量的结构放在catch和finally / end异常处理块上。 我还提供了trs操作码，该操作码位于catch之前，如果成功，则将代码扔到finally / end，同时从相应堆栈的顶部删除包含有关异常处理程序信息的块。 简单吗？ 很简单 方便吗 方便。

让我们谈谈外部方法和库


我已经提到过它们。 导入，库...没有它们，该语言将不会具有所需的灵活性和功能性。

首先，在VM的实现中，我们声明外部方法的类型和调用它的协议。

 type TExternalFunction = procedure(PStack: pointer); cdecl; PExternalFunction = ^TExternalFunction;

导入VM时，导入节解析器将填充指向外部方法的指针数组。 因此，每个方法都有一个静态地址，该地址是在VM下应用程序的组装阶段计算出来的，可以通过该地址调用所需的方法。

稍后，在代码执行期间将以这种方式进行调用：

 TExternalFunction(self.extern_methods^.GetFunc(TSVMMem(self.stack.popv).GetW))(@self.stack);

让我们为我们的虚拟机编写一个简单的库


让她首先实现Sleep方法：

 library bf; {$mode objfpc}{$H+} uses SysUtils, svm_api in '..\svm_api.pas'; procedure DSleep(Stack:PStack); cdecl; begin sleep(TSVMMem(Stack^.popv).GetW); end; exports DSleep name 'SLEEP'; end.

总结


关于这一点，我可能会从一个设想的周期结束我的第一篇文章。

今天，我详细介绍了语言运行时的创建。 我相信这篇文章对于决定尝试编写自己的语言或了解类似编程语言的工作原理的人将非常有用。

完整的VM代码可在资源库的/ runtime / svm分支中找到。

如果您喜欢这篇文章，那么不要懒惰地在业力方面加一个优势，并在顶部提高它，我已经尝试过并将为您尝试。

如果您不清楚，请欢迎进入评论或论坛 。

也许您的问题和答案不仅对您很有趣。

Source: https://habr.com/ru/post/zh-CN435202/

More articles:


All Articles