實戰(zhàn)：clox 的標記聯(lián)合（Tagged Union）值表示與動態(tài)類型運行時)
編程語言解釋器編譯器語言運行時教程【免費下載鏈接】craftinginterpretersRepository for the book Crafting Interpreters項目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters點擊查看免費下載導(dǎo)讀本篇圍繞《Crafting Interpreters》第三部分 clox 字節(jié)碼虛擬機的重要一章講解 clox 從unityped單類型的純數(shù)字計算器進化為支持nil、Boolean、Number 三類動態(tài)類型值的完整過程。核心內(nèi)容是 C 語言中標記聯(lián)合tagged union值表示的設(shè)計與實現(xiàn)以及運行時類型檢查、錯誤處理、falsiness 規(guī)則和相等/比較運算的落地。讀完本篇你將掌握 clox 如何在 C 的靜態(tài)類型世界里構(gòu)建一套可動態(tài)承載多種類型的 Value 表示并理解 bytecode VM 中指令集與源碼不必一一對應(yīng)的核心設(shè)計思想。背景從 unityped 到 dynamically typedclox 是《Crafting Interpreters》中用 C 實現(xiàn)的 Lox 語言字節(jié)碼虛擬機。在前幾章clox 內(nèi)部所有值都是double類型——即原文中unityped單類型范式所有變量都只有一種類型通常是機器寄存器整數(shù)。Forth 和 BCPL 就屬于這一范式的語言。此刻的 clox 正是 unityped 的。但 Lox 語言是動態(tài)類型的同一個變量在不同時刻可以持有 Boolean、數(shù)字或字符串。要讓 clox 真正支持這一語義需要回答兩個關(guān)鍵問題如何表示一個值的類型例如用戶嘗試用數(shù)字乘以true時需要在運行時檢測錯誤并報告因此運行時必須能判斷值的類型。如何存儲值本身不僅要能判斷3 是數(shù)字還要能區(qū)分它和數(shù)字 4。同時作為自建語言的實現(xiàn)者還必須考慮效率——如何在盡量少的比特位中打包以上兩類信息。語言黑客們想出了各種巧妙方案本章采用最經(jīng)典、最簡單的解決方案標記聯(lián)合tagged union。標記聯(lián)合Value 的數(shù)據(jù)結(jié)構(gòu)設(shè)計類型標簽枚舉VM 視角的類型值由兩部分組成一個類型標簽tag和一個保存實際數(shù)據(jù)的負載payload。首先為 VM 支持的每種值定義一個枚舉// c/value.h typedef enum { VAL_BOOL, VAL_NIL, VAL_NUMBER, VAL_OBJ } ValueType;需要特別強調(diào)的是見 c/value.h這個枚舉的每個 case 對應(yīng)的是VM 內(nèi)置支持的值的種類而不是用戶定義的類型。當后續(xù)為語言加入 class 時每個用戶自定義的類并不需要自己的枚舉項——對 VM 而言類的每個實例都是同一種類型instance實例。這是 VM 視角的類型不是用戶的類型。為什么是 union 而不是 struct僅存類型標簽還不夠還要存數(shù)據(jù)本身數(shù)字的double、Boolean 的true/false。一種樸素想法是定義一個包含每種類型字段的 struct但這會浪費內(nèi)存——一個值不可能同時既是數(shù)字又是 Boolean任何時刻只有一個字段被用到。C 的union讓所有字段在內(nèi)存中重疊其大小為最大字段的大小因此更緊湊。這種設(shè)計還對應(yīng)一個概念熟悉 ML 家族語言的讀者會發(fā)現(xiàn)C 的 struct/union 大致對應(yīng)積類型與和類型的區(qū)別元組 vs 代數(shù)數(shù)據(jù)類型。同時用 union 將底層比特重新解釋為不同類型是 C 的精髓——它打開了大量巧妙優(yōu)化的空間但也極度不安全必須小心使用。完整的 Value 結(jié)構(gòu)體將類型標簽與 union 組合成單個結(jié)構(gòu)體// c/value.h typedef struct { ValueType type; union { bool boolean; double number; Obj* obj; // 后續(xù)字符串、函數(shù)、類等對象類型使用 } as; // as 命名讀取時讀起來像一次 cast } Value;在 64 位機器、典型 C 編譯器下布局大致為4 字節(jié)的type標簽在前隨后是 union由于 union 內(nèi)含 8 字節(jié)的double編譯器會在type后插入 4 字節(jié)**填充padding**以保持 double 對齊。也就是說實際花了 8 字節(jié)來存放只需表示 0~3 的標簽。把枚舉塞進更小的類型只會徒增填充并不能省內(nèi)存。因此每個 Value 是 16 字節(jié)略大。不過它們?nèi)宰銐蛐】梢源娣旁?C 棧上并按值傳遞。這之所以安全是因為目前支持的這些類型都是**不可變immutable**的把包含數(shù)字 3 的 Value 副本傳給某個函數(shù)無需擔心調(diào)用方看到被修改的值——你無法修改3。原文預(yù)告內(nèi)存布局的優(yōu)化留待后面的 optimization 章節(jié)nan-boxing見 c/value.h 中#ifdef NAN_BOXING分支。關(guān)于 ValueArray每個 Chunk 的常量表由ValueArray動態(tài)數(shù)組承載initValueArray/writeValueArray/freeValueArray見 c/value.c通過GROW_CAPACITY與GROW_ARRAY宏擴容。由于數(shù)組元素按 8 字節(jié)對齊存儲 double編譯器會在每個 Value 之間插入同樣的填充。橋接兩個世界Lox Value 與 C Value 的轉(zhuǎn)換宏新的 Value 可以包含一個 double但不再等價于double。clox 中所有直接 C 強轉(zhuǎn)的舊代碼都失效了必須通過宏完成強制轉(zhuǎn)換。核心宏定義在 c/value.h提升C 值 → Lox Value*_VAL宏#define BOOL_VAL(value) ((Value){VAL_BOOL, {.boolean value}}) #define NIL_VAL ((Value){VAL_NIL, {.number 0}}) #define NUMBER_VAL(value) ((Value){VAL_NUMBER, {.number value}}) #define OBJ_VAL(object) ((Value){VAL_OBJ, {.obj (Obj*)object}})每個宏接收適當類型的 C 值產(chǎn)生一個帶正確類型標簽并包含底層數(shù)據(jù)的 Value將靜態(tài)類型的 C 值提升到 Lox 的動態(tài)類型宇宙中。解包Lox Value → C 值A(chǔ)S_*宏#define AS_BOOL(value) ((value).as.boolean) #define AS_NUMBER(value) ((value).as.number) #define AS_OBJ(value) ((value).as.obj)注意沒有AS_NIL宏——因為nil只有一個值VAL_NIL類型的 Value 不攜帶任何額外數(shù)據(jù)。這些宏直接訪問 union 字段因此**類型正確是硬前提**。若寫出下面的代碼就是直接打開了通往暗影位面的傳送門Value value BOOL_VAL(true); double number AS_NUMBER(value); // 危險類型不符類型檢查IS_*宏#define IS_BOOL(value) ((value).type VAL_BOOL) #define IS_NIL(value) ((value).type VAL_NIL) #define IS_NUMBER(value) ((value).type VAL_NUMBER) #define IS_OBJ(value) ((value).type VAL_OBJ)任何一次AS_*調(diào)用之前都必須先用對應(yīng)的IS_*宏守衛(wèi)。依靠這 8 個宏4 組_VAL 4 組AS_ 4 個IS_數(shù)據(jù)可以在 Lox 的動態(tài)世界與 C 的靜態(tài)世界之間安全往返。讓舊代碼重新工作動態(tài)類型數(shù)字與運行時錯誤編譯期數(shù)字常量包裝編譯數(shù)字字面量時先把詞素lexeme轉(zhuǎn)換為 C double再用NUMBER_VAL()包裝成 Value 后存入常量表c/compiler.c 中的number()解析函數(shù)。運行時打印值時則在printf()之前先用AS_NUMBER()解包出 double見 c/value.c 的printValue的VAL_NUMBER分支。一元取負與運行時錯誤一元取負會彈出一個操作數(shù)、取負、壓回結(jié)果。有了多種類型后不能再假設(shè)操作數(shù)一定是數(shù)字——用戶完全可能寫出print -false;。clox 的答案是引入runtime errors運行時錯誤在執(zhí)行要求特定類型的操作前先確認 Value 確實是該類型。VM 中的OP_NEGATE分支c/vm.c如下case OP_NEGATE: if (!IS_NUMBER(peek(0))) { runtimeError(Operand must be a number.); return INTERPRET_RUNTIME_ERROR; } push(NUMBER_VAL(-AS_NUMBER(pop()))); break;這里用到兩個新機制peek(int distance)從棧中返回一個值但不彈出它distance表示距離棧頂?shù)纳疃? 是棧頂1 是下一格。原文解釋不先 pop 再校驗是因為后續(xù)章節(jié)中若操作中途觸發(fā)垃圾回收需要讓操作數(shù)留在棧上以便 GC 能找到它們——這里主要出于習(xí)慣保持一致。runtimeError()C 可變參數(shù)函數(shù)va_listvfprintf定義見 c/vm.c需要包含stdarg.h頭。調(diào)用者可像printf()一樣傳入格式字符串和若干參數(shù)后續(xù)章節(jié)會用它產(chǎn)生含更多數(shù)據(jù)的格式化錯誤信息。打印錯誤信息后還要告訴用戶出錯時正在執(zhí)行源碼的哪一行。由于編譯期已經(jīng)丟棄了 token運行時通過 chunk 中編譯進去的調(diào)試行信息lines數(shù)組查出行號。關(guān)鍵細節(jié)取的是當前字節(jié)碼指令索引減一——因為解釋器在每條指令執(zhí)行前會先推進指令指針所以調(diào)用runtimeError()時出錯的正是上一條指令。Lox 的錯誤處理相當吝嗇所有錯誤都是致命的立即中止解釋器用戶代碼沒有任何恢復(fù)手段。原文直言若 Lox 是真實語言這會是首先要改進的地方之一。二元算術(shù)運算符、-、*、/四個運算符的公共邏輯被封裝進一個預(yù)處理器宏BINARY_OP在早幾章看似過度設(shè)計本章得到了回報只需把運算符 token 作為參數(shù)傳入類型檢查和轉(zhuǎn)換集中在一處#define BINARY_OP(valueType, op) \ do { \ if (!IS_NUMBER(peek(0)) || !IS_NUMBER(peek(1))) { \ runtimeError(Operands must be numbers.); \ return INTERPRET_RUNTIME_ERROR; \ } \ double b AS_NUMBER(pop()); \ double a AS_NUMBER(pop()); \ push(valueType(a op b)); \ } while (false)流程與一元取負一致先確認兩個操作數(shù)都是數(shù)字任一不是則報錯并返回操作數(shù)合法后彈出并解包應(yīng)用給定運算符再包裝結(jié)果壓回棧。結(jié)果包裝宏valueType作為宏參數(shù)傳入——C 中宏可以作為參數(shù)傳給宏。算術(shù)運算傳NUMBER_VAL而下一節(jié)會看到比較運算傳BOOL_VAL這正是把包裝宏做成參數(shù)的原因。VM 中的四個算術(shù)分支c/vm.ccase OP_SUBTRACT: BINARY_OP(NUMBER_VAL, -); break; case OP_MULTIPLY: BINARY_OP(NUMBER_VAL, *); break; case OP_DIVIDE: BINARY_OP(NUMBER_VAL, /); break;新增三種字面量true、false、nil現(xiàn)在 clox 可以在內(nèi)部表示新類型但用戶程序還無法創(chuàng)建這些類型的值。接下來為編譯器增加三個新字面量true、false、nil的支持。對于數(shù)字字面量由于存在海量可能的數(shù)值需要存入常量表并用OP_CONSTANT加載但true/false/nil總共只有 3 個可能值再浪費一個兩字節(jié)指令和常量表項就太奢侈——而且更慢。因此定義 3 條專用指令直接把字面量壓棧c/vm.ccase OP_NIL: push(NIL_VAL); break; case OP_TRUE: push(BOOL_VAL(true)); break; case OP_FALSE: push(BOOL_VAL(false)); break;原文附注為常見常量值提供專用指令確實更快——字節(jié)碼 VM 大部分執(zhí)行時間花在讀取和解碼指令上行為一定時指令越少越簡單就越快。例如 Java 字節(jié)碼指令集就有專門加載 0.0、1.0、2.0 以及 -1 到 5 的整數(shù)的指令多數(shù)成熟 JVM 已用 JIT 編譯這成了遺留優(yōu)化。掃描器scanner已經(jīng)將true、false、nil視為關(guān)鍵字所以直接進入解析器。基于表的 Pratt 解析器中只需把同一個解析函數(shù)literal()掛到三個關(guān)鍵字 token 對應(yīng)的行上c/compiler.c 的rules[]表[TOKEN_FALSE] {literal, NULL, PREC_NONE}, [TOKEN_NIL] {literal, NULL, PREC_NONE}, [TOKEN_TRUE] {literal, NULL, PREC_NONE},由于parsePrecedence()已消費掉關(guān)鍵字 tokenliteral()只需依據(jù) token 類型輸出相應(yīng)指令static void literal(bool canAssign) { switch (parser.previous.type) { case TOKEN_FALSE: emitByte(OP_FALSE); break; case TOKEN_NIL: emitByte(OP_NIL); break; case TOKEN_TRUE: emitByte(OP_TRUE); break; default: return; // Unreachable. } }原文提及也可為每個字面量寫?yīng)毩⒔馕龊瘮?shù)以省去 switch但作者認為那是個人品味問題。前端完成后別忘了反匯編器disassembler也要認識新指令OP_NIL、OP_TRUE、OP_FALSE在 c/debug.c 中通過simpleInstruction()輸出名稱。此時運行程序true解釋器在打印結(jié)果時會崩潰——printValue()必須擴展以處理新類型c/value.cswitch (value.type) { case VAL_BOOL: printf(AS_BOOL(value) ? true : false); break; case VAL_NIL: printf(nil); break; case VAL_NUMBER: printf(%g, AS_NUMBER(value)); break; case VAL_OBJ: printObject(value); break; }邏輯非與 falsiness新類型最有用的第一批操作是邏輯運算符。一元!獲得新指令OP_NOTc/vm.ccase OP_NOT: push(BOOL_VAL(isFalsey(pop()))); break;編譯端復(fù)用一元運算符解析函數(shù)unary()——之前為取負寫的 switch 已按 token 類型分發(fā)指令只需加一個 casec/compiler.ccase TOKEN_BANG: emitByte(OP_NOT); break; case TOKEN_MINUS: emitByte(OP_NEGATE); break;并把!掛進解析表。與一元取負不同Lox 對!及其它期望 Boolean 的上下文非常寬容其規(guī)則稱為falsiness假值性。實現(xiàn)于 c/vm.cstatic bool isFalsey(Value value) { return IS_NIL(value) || (IS_BOOL(value) !AS_BOOL(value)); }Lox 遵循 Ruby 的規(guī)則nil和false是 falsey其余一切值都表現(xiàn)得像true。所以!nil合法并得到true而-nil則是運行時錯誤。測試用例 test/operator/not.lox 完整驗證了這條規(guī)則!true→false、!false→true、!nil→true、!0→false、!→false、!foo函數(shù)→false。isFalsey函數(shù)后續(xù)還被OP_JUMP_IF_FALSE用于控制流and/or短路是跳轉(zhuǎn)章節(jié)的基礎(chǔ)。反匯編器同樣需新增OP_NOT的顯示。相等與比較運算符最后一組是返回 Boolean 結(jié)果的運算符、!、、、、and/or因需要短路控制流留到跳轉(zhuǎn)章節(jié)。只定義三條指令的脫糖desugaring新指令只有三條c/vm.cOP_EQUAL、OP_GREATER、OP_LESS。為什么沒有!、、的指令從性能角度定義它們 VM 會執(zhí)行得更快但本書的首要教學(xué)目標是讓你內(nèi)化字節(jié)碼指令無需與用戶源碼一一對應(yīng)——VM 可以自由選擇任何指令集和代碼序列只要用戶可見行為正確a ! b語義等同!(a b)編譯器可將前者編譯為OP_EQUAL后接OP_NOTa b等同!(a b)a b等同!(a b)。嚴格來說IEEE 754 規(guī)定操作數(shù)為 NaN 時所有比較都返回 false因此NaN 1與NaN 1都為 false脫糖并非恒等——書中不做深究但真實語言實現(xiàn)必須注意這類細節(jié)。對應(yīng)地解析表中六個運算符全部復(fù)用binary()解析函數(shù)binary()內(nèi)的 switch 擴展出六個 casec/compiler.ccase TOKEN_BANG_EQUAL: emitBytes(OP_EQUAL, OP_NOT); break; case TOKEN_EQUAL_EQUAL: emitByte(OP_EQUAL); break; case TOKEN_GREATER: emitByte(OP_GREATER); break; case TOKEN_GREATER_EQUAL: emitBytes(OP_LESS, OP_NOT); break; case TOKEN_LESS: emitByte(OP_LESS); break; case TOKEN_LESS_EQUAL: emitBytes(OP_GREATER, OP_NOT); break;六個運算符只花三條指令的代價。valuesEqual跨類型相等OP_EQUAL可以作用于任意一對值包括不同類型的值。邏輯被拆到獨立的valuesEqual()函數(shù)聲明于 c/value.h實現(xiàn)在 c/value.c它總是返回 C 的bool所以可安全包進BOOL_VALbool valuesEqual(Value a, Value b) { if (a.type ! b.type) return false; switch (a.type) { case VAL_BOOL: return AS_BOOL(a) AS_BOOL(b); case VAL_NIL: return true; case VAL_NUMBER: return AS_NUMBER(a) AS_NUMBER(b); case VAL_OBJ: return AS_OBJ(a) AS_OBJ(b); default: return false; // Unreachable. } }首先比較類型標簽類型不同則必然不相等原文對比了 JS 的隱式轉(zhuǎn)換導(dǎo)致的 0 0 之類的寬松相等問題、PHP 認為 1 與 01 等價等反例。類型相同則解包后直接比較。每個類型一個 case之后每加新類型這里就新增 case。一個關(guān)鍵問題為什么不能直接memcmp()兩個 Value 結(jié)構(gòu)體因為填充字節(jié)和不同大小的 union 字段導(dǎo)致 Value 含有未使用的比特位C 不保證這些位的內(nèi)容——兩個相等的 Value 可能在未使用字節(jié)上不同memcmp會錯誤地判定不相等。這就是valuesEqual必須逐字段比較的原因。VM 側(cè)OP_EQUAL分支c/vm.ccase OP_EQUAL: { Value b pop(); Value a pop(); push(BOOL_VAL(valuesEqual(a, b))); break; }比較運算符復(fù)用 BINARY_OP、只作用于數(shù)字比相等更簡單。直接復(fù)用上文的BINARY_OP宏把結(jié)果包裝宏換成BOOL_VALcase OP_GREATER: BINARY_OP(BOOL_VAL, ); break; case OP_LESS: BINARY_OP(BOOL_VAL, ); break;這正是當初把包裝宏做成BINARY_OP參數(shù)的原因——算術(shù)傳NUMBER_VAL比較傳BOOL_VAL。反匯編器同樣為三條新指令加上simpleInstruction名稱輸出。至此clox 從一個數(shù)字計算器成長為接近通用的表達式求值器。運行!(5 - 4 3 * 2 !nil)可以正常得到結(jié)果。相等/NaN 語義由測試用例 test/operator/equals.lox如nil false為 false、0 0為 false與 test/number/nan_equality.lox0/0產(chǎn)生的 NaN 不與自身相等驗證。實踐構(gòu)建并運行 clox倉庫根目錄 Makefile 提供了構(gòu)建入口make clox # 編譯 release 版解釋器并復(fù)制到倉庫頂層 ./clox make debug # 編譯帶調(diào)試符號的 cloxd可開 DEBUG_TRACE_EXECUTION 跟蹤執(zhí)行 make test_clox # 運行 clox 的全部回歸測試make clox通過util/c.make以NAMEclox MODErelease SOURCE_DIRc編譯 c/ 目錄下的源碼main.c、vm.c、compiler.c、scanner.c、chunk.c、value.c、debug.c等。構(gòu)建完成后即可在交互式 REPL 或腳本模式下體驗本章新增的類型與運算符行為。當前 c/ 目錄中的 c/value.h 是全書最終版本——包含VAL_OBJ字符串、函數(shù)、閉包、類等對象類型與#ifdef NAN_BOXING下的優(yōu)化分支其中IS_NUMBER改為按 QNaN 模式判斷、AS_NUMBER用memcpy實現(xiàn)類型雙關(guān)valueToNum/numToValue并定義了TAG_NIL/TAG_FALSE/TAG_TRUE三個標簽位。這正是本章標記聯(lián)合方案在后文 optimization 中演進為 NaN 盒nan-boxing的伏筆。延伸閱讀與本章挑戰(zhàn)后續(xù)章節(jié) strings 將引入最復(fù)雜的內(nèi)置類型——字符串。字符串長度可變這一微小差異帶來了巨大的實現(xiàn)影響因此專章論述。本章的標記聯(lián)合設(shè)計在后文被 NaN 盒nan-boxing優(yōu)化取代詳見 optimization作為對比jloxJava 版解釋器中同一問題通過Object與 instanceof 解決見 java/com/craftinginterpreters/lox。原文給出的兩道挑戰(zhàn)題值得動手思考進一步縮減二元運算符除!、、外還能消除哪些指令編譯器在缺少它們時如何應(yīng)對提示OP_NOT與OP_EQUAL的組合還能覆蓋哪些情形反向優(yōu)化為提升字節(jié)碼 VM 速度可以增加更多對應(yīng)高層操作的專用指令。針對本章新增支持的用戶代碼字面量、邏輯非、相等/比較你會定義哪些指令來加速贊分享編程語言解釋器編譯器語言運行時教程【免費下載鏈接】craftinginterpretersRepository for the book Crafting Interpreters項目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters點擊查看免費下載相關(guān)推薦Graphene 聯(lián)合類型Union完整指南定義、Schema 表示與運行時解析Graphene 聯(lián)合類型Union完整指南定義、Schema 表示與運行時解析 聯(lián)合類型Union是 GraphQL 中用于表達一個字段可能返回多后端API設(shè)計Darklang運行時類型動態(tài)類型系統(tǒng)實現(xiàn)Darklang運行時類型動態(tài)類型系統(tǒng)實現(xiàn) 還在為靜態(tài)類型系統(tǒng)的編譯時約束感到束手束腳Darklang的動態(tài)類型系統(tǒng)為你提供了運行時靈活性同時保持了類型安深入理解Crafting Interpreters類型系統(tǒng)實現(xiàn)的藝術(shù)與科學(xué)深入理解Crafting Interpreters類型系統(tǒng)實現(xiàn)的藝術(shù)與科學(xué) 在編程語言設(shè)計的核心領(lǐng)域類型系統(tǒng)的實現(xiàn)是一項既富有挑戰(zhàn)性又充滿藝術(shù)性的工作。今天編程語言解釋器編譯器語言運行時教程上一篇Playwright GenericAssertions 全解析expect 通用值斷言的完整用法與底層實現(xiàn)下一篇ESPnet2 × PortMedia 法語語料XLS-R 預(yù)訓(xùn)練語音編碼器 mBART-50 預(yù)訓(xùn)練文本編碼器-解碼器的 ASR/SLU 訓(xùn)練實戰(zhàn)創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 Crafting Interpreters 類型系統(tǒng)實戰(zhàn)：clox 的標記聯(lián)合（Tagged Union）值表示與動態(tài)類型運行時
編程語言解釋器編譯器語言運行時教程【免費下載鏈接】craftinginterpretersRepository for the book Crafting Interpreters項目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters點擊查看免費下載導(dǎo)讀本篇圍繞《Crafting Interpreters》第三部分 clox 字節(jié)碼虛擬機的重要一章講解 clox 從unityped單類型的純數(shù)字計算器進化為支持nil、Boolean、Number 三類動態(tài)類型值的完整過程。核心內(nèi)容是 C 語言中標記聯(lián)合tagged union值表示的設(shè)計與實現(xiàn)以及運行時類型檢查、錯誤處理、falsiness 規(guī)則和相等/比較運算的落地。讀完本篇你將掌握 clox 如何在 C 的靜態(tài)類型世界里構(gòu)建一套可動態(tài)承載多種類型的 Value 表示并理解 bytecode VM 中指令集與源碼不必一一對應(yīng)的核心設(shè)計思想。背景從 unityped 到 dynamically typedclox 是《Crafting Interpreters》中用 C 實現(xiàn)的 Lox 語言字節(jié)碼虛擬機。在前幾章clox 內(nèi)部所有值都是double類型——即原文中unityped單類型范式所有變量都只有一種類型通常是機器寄存器整數(shù)。Forth 和 BCPL 就屬于這一范式的語言。此刻的 clox 正是 unityped 的。但 Lox 語言是動態(tài)類型的同一個變量在不同時刻可以持有 Boolean、數(shù)字或字符串。要讓 clox 真正支持這一語義需要回答兩個關(guān)鍵問題如何表示一個值的類型例如用戶嘗試用數(shù)字乘以true時需要在運行時檢測錯誤并報告因此運行時必須能判斷值的類型。如何存儲值本身不僅要能判斷3 是數(shù)字還要能區(qū)分它和數(shù)字 4。同時作為自建語言的實現(xiàn)者還必須考慮效率——如何在盡量少的比特位中打包以上兩類信息。語言黑客們想出了各種巧妙方案本章采用最經(jīng)典、最簡單的解決方案標記聯(lián)合tagged union。標記聯(lián)合Value 的數(shù)據(jù)結(jié)構(gòu)設(shè)計類型標簽枚舉VM 視角的類型值由兩部分組成一個類型標簽tag和一個保存實際數(shù)據(jù)的負載payload。首先為 VM 支持的每種值定義一個枚舉// c/value.h typedef enum { VAL_BOOL, VAL_NIL, VAL_NUMBER, VAL_OBJ } ValueType;需要特別強調(diào)的是見 c/value.h這個枚舉的每個 case 對應(yīng)的是VM 內(nèi)置支持的值的種類而不是用戶定義的類型。當后續(xù)為語言加入 class 時每個用戶自定義的類并不需要自己的枚舉項——對 VM 而言類的每個實例都是同一種類型instance實例。這是 VM 視角的類型不是用戶的類型。為什么是 union 而不是 struct僅存類型標簽還不夠還要存數(shù)據(jù)本身數(shù)字的double、Boolean 的true/false。一種樸素想法是定義一個包含每種類型字段的 struct但這會浪費內(nèi)存——一個值不可能同時既是數(shù)字又是 Boolean任何時刻只有一個字段被用到。C 的union讓所有字段在內(nèi)存中重疊其大小為最大字段的大小因此更緊湊。這種設(shè)計還對應(yīng)一個概念熟悉 ML 家族語言的讀者會發(fā)現(xiàn)C 的 struct/union 大致對應(yīng)積類型與和類型的區(qū)別元組 vs 代數(shù)數(shù)據(jù)類型。同時用 union 將底層比特重新解釋為不同類型是 C 的精髓——它打開了大量巧妙優(yōu)化的空間但也極度不安全必須小心使用。完整的 Value 結(jié)構(gòu)體將類型標簽與 union 組合成單個結(jié)構(gòu)體// c/value.h typedef struct { ValueType type; union { bool boolean; double number; Obj* obj; // 后續(xù)字符串、函數(shù)、類等對象類型使用 } as; // as 命名讀取時讀起來像一次 cast } Value;在 64 位機器、典型 C 編譯器下布局大致為4 字節(jié)的type標簽在前隨后是 union由于 union 內(nèi)含 8 字節(jié)的double編譯器會在type后插入 4 字節(jié)**填充padding**以保持 double 對齊。也就是說實際花了 8 字節(jié)來存放只需表示 0~3 的標簽。把枚舉塞進更小的類型只會徒增填充并不能省內(nèi)存。因此每個 Value 是 16 字節(jié)略大。不過它們?nèi)宰銐蛐】梢源娣旁?C 棧上并按值傳遞。這之所以安全是因為目前支持的這些類型都是**不可變immutable**的把包含數(shù)字 3 的 Value 副本傳給某個函數(shù)無需擔心調(diào)用方看到被修改的值——你無法修改3。原文預(yù)告內(nèi)存布局的優(yōu)化留待后面的 optimization 章節(jié)nan-boxing見 c/value.h 中#ifdef NAN_BOXING分支。關(guān)于 ValueArray每個 Chunk 的常量表由ValueArray動態(tài)數(shù)組承載initValueArray/writeValueArray/freeValueArray見 c/value.c通過GROW_CAPACITY與GROW_ARRAY宏擴容。由于數(shù)組元素按 8 字節(jié)對齊存儲 double編譯器會在每個 Value 之間插入同樣的填充。橋接兩個世界Lox Value 與 C Value 的轉(zhuǎn)換宏新的 Value 可以包含一個 double但不再等價于double。clox 中所有直接 C 強轉(zhuǎn)的舊代碼都失效了必須通過宏完成強制轉(zhuǎn)換。核心宏定義在 c/value.h提升C 值 → Lox Value*_VAL宏#define BOOL_VAL(value) ((Value){VAL_BOOL, {.boolean value}}) #define NIL_VAL ((Value){VAL_NIL, {.number 0}}) #define NUMBER_VAL(value) ((Value){VAL_NUMBER, {.number value}}) #define OBJ_VAL(object) ((Value){VAL_OBJ, {.obj (Obj*)object}})每個宏接收適當類型的 C 值產(chǎn)生一個帶正確類型標簽并包含底層數(shù)據(jù)的 Value將靜態(tài)類型的 C 值提升到 Lox 的動態(tài)類型宇宙中。解包Lox Value → C 值A(chǔ)S_*宏#define AS_BOOL(value) ((value).as.boolean) #define AS_NUMBER(value) ((value).as.number) #define AS_OBJ(value) ((value).as.obj)注意沒有AS_NIL宏——因為nil只有一個值VAL_NIL類型的 Value 不攜帶任何額外數(shù)據(jù)。這些宏直接訪問 union 字段因此**類型正確是硬前提**。若寫出下面的代碼就是直接打開了通往暗影位面的傳送門Value value BOOL_VAL(true); double number AS_NUMBER(value); // 危險類型不符類型檢查IS_*宏#define IS_BOOL(value) ((value).type VAL_BOOL) #define IS_NIL(value) ((value).type VAL_NIL) #define IS_NUMBER(value) ((value).type VAL_NUMBER) #define IS_OBJ(value) ((value).type VAL_OBJ)任何一次AS_*調(diào)用之前都必須先用對應(yīng)的IS_*宏守衛(wèi)。依靠這 8 個宏4 組_VAL 4 組AS_ 4 個IS_數(shù)據(jù)可以在 Lox 的動態(tài)世界與 C 的靜態(tài)世界之間安全往返。讓舊代碼重新工作動態(tài)類型數(shù)字與運行時錯誤編譯期數(shù)字常量包裝編譯數(shù)字字面量時先把詞素lexeme轉(zhuǎn)換為 C double再用NUMBER_VAL()包裝成 Value 后存入常量表c/compiler.c 中的number()解析函數(shù)。運行時打印值時則在printf()之前先用AS_NUMBER()解包出 double見 c/value.c 的printValue的VAL_NUMBER分支。一元取負與運行時錯誤一元取負會彈出一個操作數(shù)、取負、壓回結(jié)果。有了多種類型后不能再假設(shè)操作數(shù)一定是數(shù)字——用戶完全可能寫出print -false;。clox 的答案是引入runtime errors運行時錯誤在執(zhí)行要求特定類型的操作前先確認 Value 確實是該類型。VM 中的OP_NEGATE分支c/vm.c如下case OP_NEGATE: if (!IS_NUMBER(peek(0))) { runtimeError(Operand must be a number.); return INTERPRET_RUNTIME_ERROR; } push(NUMBER_VAL(-AS_NUMBER(pop()))); break;這里用到兩個新機制peek(int distance)從棧中返回一個值但不彈出它distance表示距離棧頂?shù)纳疃? 是棧頂1 是下一格。原文解釋不先 pop 再校驗是因為后續(xù)章節(jié)中若操作中途觸發(fā)垃圾回收需要讓操作數(shù)留在棧上以便 GC 能找到它們——這里主要出于習(xí)慣保持一致。runtimeError()C 可變參數(shù)函數(shù)va_listvfprintf定義見 c/vm.c需要包含stdarg.h頭。調(diào)用者可像printf()一樣傳入格式字符串和若干參數(shù)后續(xù)章節(jié)會用它產(chǎn)生含更多數(shù)據(jù)的格式化錯誤信息。打印錯誤信息后還要告訴用戶出錯時正在執(zhí)行源碼的哪一行。由于編譯期已經(jīng)丟棄了 token運行時通過 chunk 中編譯進去的調(diào)試行信息lines數(shù)組查出行號。關(guān)鍵細節(jié)取的是當前字節(jié)碼指令索引減一——因為解釋器在每條指令執(zhí)行前會先推進指令指針所以調(diào)用runtimeError()時出錯的正是上一條指令。Lox 的錯誤處理相當吝嗇所有錯誤都是致命的立即中止解釋器用戶代碼沒有任何恢復(fù)手段。原文直言若 Lox 是真實語言這會是首先要改進的地方之一。二元算術(shù)運算符、-、*、/四個運算符的公共邏輯被封裝進一個預(yù)處理器宏BINARY_OP在早幾章看似過度設(shè)計本章得到了回報只需把運算符 token 作為參數(shù)傳入類型檢查和轉(zhuǎn)換集中在一處#define BINARY_OP(valueType, op) \ do { \ if (!IS_NUMBER(peek(0)) || !IS_NUMBER(peek(1))) { \ runtimeError(Operands must be numbers.); \ return INTERPRET_RUNTIME_ERROR; \ } \ double b AS_NUMBER(pop()); \ double a AS_NUMBER(pop()); \ push(valueType(a op b)); \ } while (false)流程與一元取負一致先確認兩個操作數(shù)都是數(shù)字任一不是則報錯并返回操作數(shù)合法后彈出并解包應(yīng)用給定運算符再包裝結(jié)果壓回棧。結(jié)果包裝宏valueType作為宏參數(shù)傳入——C 中宏可以作為參數(shù)傳給宏。算術(shù)運算傳NUMBER_VAL而下一節(jié)會看到比較運算傳BOOL_VAL這正是把包裝宏做成參數(shù)的原因。VM 中的四個算術(shù)分支c/vm.ccase OP_SUBTRACT: BINARY_OP(NUMBER_VAL, -); break; case OP_MULTIPLY: BINARY_OP(NUMBER_VAL, *); break; case OP_DIVIDE: BINARY_OP(NUMBER_VAL, /); break;新增三種字面量true、false、nil現(xiàn)在 clox 可以在內(nèi)部表示新類型但用戶程序還無法創(chuàng)建這些類型的值。接下來為編譯器增加三個新字面量true、false、nil的支持。對于數(shù)字字面量由于存在海量可能的數(shù)值需要存入常量表并用OP_CONSTANT加載但true/false/nil總共只有 3 個可能值再浪費一個兩字節(jié)指令和常量表項就太奢侈——而且更慢。因此定義 3 條專用指令直接把字面量壓棧c/vm.ccase OP_NIL: push(NIL_VAL); break; case OP_TRUE: push(BOOL_VAL(true)); break; case OP_FALSE: push(BOOL_VAL(false)); break;原文附注為常見常量值提供專用指令確實更快——字節(jié)碼 VM 大部分執(zhí)行時間花在讀取和解碼指令上行為一定時指令越少越簡單就越快。例如 Java 字節(jié)碼指令集就有專門加載 0.0、1.0、2.0 以及 -1 到 5 的整數(shù)的指令多數(shù)成熟 JVM 已用 JIT 編譯這成了遺留優(yōu)化。掃描器scanner已經(jīng)將true、false、nil視為關(guān)鍵字所以直接進入解析器。基于表的 Pratt 解析器中只需把同一個解析函數(shù)literal()掛到三個關(guān)鍵字 token 對應(yīng)的行上c/compiler.c 的rules[]表[TOKEN_FALSE] {literal, NULL, PREC_NONE}, [TOKEN_NIL] {literal, NULL, PREC_NONE}, [TOKEN_TRUE] {literal, NULL, PREC_NONE},由于parsePrecedence()已消費掉關(guān)鍵字 tokenliteral()只需依據(jù) token 類型輸出相應(yīng)指令static void literal(bool canAssign) { switch (parser.previous.type) { case TOKEN_FALSE: emitByte(OP_FALSE); break; case TOKEN_NIL: emitByte(OP_NIL); break; case TOKEN_TRUE: emitByte(OP_TRUE); break; default: return; // Unreachable. } }原文提及也可為每個字面量寫?yīng)毩⒔馕龊瘮?shù)以省去 switch但作者認為那是個人品味問題。前端完成后別忘了反匯編器disassembler也要認識新指令OP_NIL、OP_TRUE、OP_FALSE在 c/debug.c 中通過simpleInstruction()輸出名稱。此時運行程序true解釋器在打印結(jié)果時會崩潰——printValue()必須擴展以處理新類型c/value.cswitch (value.type) { case VAL_BOOL: printf(AS_BOOL(value) ? true : false); break; case VAL_NIL: printf(nil); break; case VAL_NUMBER: printf(%g, AS_NUMBER(value)); break; case VAL_OBJ: printObject(value); break; }邏輯非與 falsiness新類型最有用的第一批操作是邏輯運算符。一元!獲得新指令OP_NOTc/vm.ccase OP_NOT: push(BOOL_VAL(isFalsey(pop()))); break;編譯端復(fù)用一元運算符解析函數(shù)unary()——之前為取負寫的 switch 已按 token 類型分發(fā)指令只需加一個 casec/compiler.ccase TOKEN_BANG: emitByte(OP_NOT); break; case TOKEN_MINUS: emitByte(OP_NEGATE); break;并把!掛進解析表。與一元取負不同Lox 對!及其它期望 Boolean 的上下文非常寬容其規(guī)則稱為falsiness假值性。實現(xiàn)于 c/vm.cstatic bool isFalsey(Value value) { return IS_NIL(value) || (IS_BOOL(value) !AS_BOOL(value)); }Lox 遵循 Ruby 的規(guī)則nil和false是 falsey其余一切值都表現(xiàn)得像true。所以!nil合法并得到true而-nil則是運行時錯誤。測試用例 test/operator/not.lox 完整驗證了這條規(guī)則!true→false、!false→true、!nil→true、!0→false、!→false、!foo函數(shù)→false。isFalsey函數(shù)后續(xù)還被OP_JUMP_IF_FALSE用于控制流and/or短路是跳轉(zhuǎn)章節(jié)的基礎(chǔ)。反匯編器同樣需新增OP_NOT的顯示。相等與比較運算符最后一組是返回 Boolean 結(jié)果的運算符、!、、、、and/or因需要短路控制流留到跳轉(zhuǎn)章節(jié)。只定義三條指令的脫糖desugaring新指令只有三條c/vm.cOP_EQUAL、OP_GREATER、OP_LESS。為什么沒有!、、的指令從性能角度定義它們 VM 會執(zhí)行得更快但本書的首要教學(xué)目標是讓你內(nèi)化字節(jié)碼指令無需與用戶源碼一一對應(yīng)——VM 可以自由選擇任何指令集和代碼序列只要用戶可見行為正確a ! b語義等同!(a b)編譯器可將前者編譯為OP_EQUAL后接OP_NOTa b等同!(a b)a b等同!(a b)。嚴格來說IEEE 754 規(guī)定操作數(shù)為 NaN 時所有比較都返回 false因此NaN 1與NaN 1都為 false脫糖并非恒等——書中不做深究但真實語言實現(xiàn)必須注意這類細節(jié)。對應(yīng)地解析表中六個運算符全部復(fù)用binary()解析函數(shù)binary()內(nèi)的 switch 擴展出六個 casec/compiler.ccase TOKEN_BANG_EQUAL: emitBytes(OP_EQUAL, OP_NOT); break; case TOKEN_EQUAL_EQUAL: emitByte(OP_EQUAL); break; case TOKEN_GREATER: emitByte(OP_GREATER); break; case TOKEN_GREATER_EQUAL: emitBytes(OP_LESS, OP_NOT); break; case TOKEN_LESS: emitByte(OP_LESS); break; case TOKEN_LESS_EQUAL: emitBytes(OP_GREATER, OP_NOT); break;六個運算符只花三條指令的代價。valuesEqual跨類型相等OP_EQUAL可以作用于任意一對值包括不同類型的值。邏輯被拆到獨立的valuesEqual()函數(shù)聲明于 c/value.h實現(xiàn)在 c/value.c它總是返回 C 的bool所以可安全包進BOOL_VALbool valuesEqual(Value a, Value b) { if (a.type ! b.type) return false; switch (a.type) { case VAL_BOOL: return AS_BOOL(a) AS_BOOL(b); case VAL_NIL: return true; case VAL_NUMBER: return AS_NUMBER(a) AS_NUMBER(b); case VAL_OBJ: return AS_OBJ(a) AS_OBJ(b); default: return false; // Unreachable. } }首先比較類型標簽類型不同則必然不相等原文對比了 JS 的隱式轉(zhuǎn)換導(dǎo)致的 0 0 之類的寬松相等問題、PHP 認為 1 與 01 等價等反例。類型相同則解包后直接比較。每個類型一個 case之后每加新類型這里就新增 case。一個關(guān)鍵問題為什么不能直接memcmp()兩個 Value 結(jié)構(gòu)體因為填充字節(jié)和不同大小的 union 字段導(dǎo)致 Value 含有未使用的比特位C 不保證這些位的內(nèi)容——兩個相等的 Value 可能在未使用字節(jié)上不同memcmp會錯誤地判定不相等。這就是valuesEqual必須逐字段比較的原因。VM 側(cè)OP_EQUAL分支c/vm.ccase OP_EQUAL: { Value b pop(); Value a pop(); push(BOOL_VAL(valuesEqual(a, b))); break; }比較運算符復(fù)用 BINARY_OP、只作用于數(shù)字比相等更簡單。直接復(fù)用上文的BINARY_OP宏把結(jié)果包裝宏換成BOOL_VALcase OP_GREATER: BINARY_OP(BOOL_VAL, ); break; case OP_LESS: BINARY_OP(BOOL_VAL, ); break;這正是當初把包裝宏做成BINARY_OP參數(shù)的原因——算術(shù)傳NUMBER_VAL比較傳BOOL_VAL。反匯編器同樣為三條新指令加上simpleInstruction名稱輸出。至此clox 從一個數(shù)字計算器成長為接近通用的表達式求值器。運行!(5 - 4 3 * 2 !nil)可以正常得到結(jié)果。相等/NaN 語義由測試用例 test/operator/equals.lox如nil false為 false、0 0為 false與 test/number/nan_equality.lox0/0產(chǎn)生的 NaN 不與自身相等驗證。實踐構(gòu)建并運行 clox倉庫根目錄 Makefile 提供了構(gòu)建入口make clox # 編譯 release 版解釋器并復(fù)制到倉庫頂層 ./clox make debug # 編譯帶調(diào)試符號的 cloxd可開 DEBUG_TRACE_EXECUTION 跟蹤執(zhí)行 make test_clox # 運行 clox 的全部回歸測試make clox通過util/c.make以NAMEclox MODErelease SOURCE_DIRc編譯 c/ 目錄下的源碼main.c、vm.c、compiler.c、scanner.c、chunk.c、value.c、debug.c等。構(gòu)建完成后即可在交互式 REPL 或腳本模式下體驗本章新增的類型與運算符行為。當前 c/ 目錄中的 c/value.h 是全書最終版本——包含VAL_OBJ字符串、函數(shù)、閉包、類等對象類型與#ifdef NAN_BOXING下的優(yōu)化分支其中IS_NUMBER改為按 QNaN 模式判斷、AS_NUMBER用memcpy實現(xiàn)類型雙關(guān)valueToNum/numToValue并定義了TAG_NIL/TAG_FALSE/TAG_TRUE三個標簽位。這正是本章標記聯(lián)合方案在后文 optimization 中演進為 NaN 盒nan-boxing的伏筆。延伸閱讀與本章挑戰(zhàn)后續(xù)章節(jié) strings 將引入最復(fù)雜的內(nèi)置類型——字符串。字符串長度可變這一微小差異帶來了巨大的實現(xiàn)影響因此專章論述。本章的標記聯(lián)合設(shè)計在后文被 NaN 盒nan-boxing優(yōu)化取代詳見 optimization作為對比jloxJava 版解釋器中同一問題通過Object與 instanceof 解決見 java/com/craftinginterpreters/lox。原文給出的兩道挑戰(zhàn)題值得動手思考進一步縮減二元運算符除!、、外還能消除哪些指令編譯器在缺少它們時如何應(yīng)對提示OP_NOT與OP_EQUAL的組合還能覆蓋哪些情形反向優(yōu)化為提升字節(jié)碼 VM 速度可以增加更多對應(yīng)高層操作的專用指令。針對本章新增支持的用戶代碼字面量、邏輯非、相等/比較你會定義哪些指令來加速贊分享編程語言解釋器編譯器語言運行時教程【免費下載鏈接】craftinginterpretersRepository for the book Crafting Interpreters項目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters點擊查看免費下載相關(guān)推薦Graphene 聯(lián)合類型Union完整指南定義、Schema 表示與運行時解析Graphene 聯(lián)合類型Union完整指南定義、Schema 表示與運行時解析 聯(lián)合類型Union是 GraphQL 中用于表達一個字段可能返回多后端API設(shè)計Darklang運行時類型動態(tài)類型系統(tǒng)實現(xiàn)Darklang運行時類型動態(tài)類型系統(tǒng)實現(xiàn) 還在為靜態(tài)類型系統(tǒng)的編譯時約束感到束手束腳Darklang的動態(tài)類型系統(tǒng)為你提供了運行時靈活性同時保持了類型安深入理解Crafting Interpreters類型系統(tǒng)實現(xiàn)的藝術(shù)與科學(xué)深入理解Crafting Interpreters類型系統(tǒng)實現(xiàn)的藝術(shù)與科學(xué) 在編程語言設(shè)計的核心領(lǐng)域類型系統(tǒng)的實現(xiàn)是一項既富有挑戰(zhàn)性又充滿藝術(shù)性的工作。今天編程語言解釋器編譯器語言運行時教程上一篇Playwright GenericAssertions 全解析expect 通用值斷言的完整用法與底層實現(xiàn)下一篇ESPnet2 × PortMedia 法語語料XLS-R 預(yù)訓(xùn)練語音編碼器 mBART-50 預(yù)訓(xùn)練文本編碼器-解碼器的 ASR/SLU 訓(xùn)練實戰(zhàn)創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考