Машин доторх машин

Өөрийн программчлалын хэл бүтээх нь — 1-р улирал: Cecile · 2-р хэсэг: Байткод виртуал машин

Өмнөх нийтлэлд би Cecile-ийн нэг мөр кодыг ийм болгон хөрвүүлсэн:

PUSH 3
PUSH 4
MUL          ; 3 * 4  -> 12
PUSH 2
ADD          ; 2 + 12 -> 14
STORE x      ; x = 14

Тэгээд бүх төслийн хамгийн чухал асуултыг чимээгүйхэн алгасчихсан: үүнийг хэн ажиллуулдаг вэ?

Учир нь тэр зааврын жагсаалт өөрөө юу ч хийдэггүй. Энэ бол зүгээр л өгөгдөл — санах ойд хэвтэж буй хэдэн байт. Хэн нэгэн тэднийг нэг нэгээр нь аваад гүйцэтгэх ёстой. Тэр «хэн нэгэн» бол виртуал машин, мөн гайхмаар жижигхэн юм: нэг давталт, нэг стек, нэг заагч. Хамтдаа нэгийг бүтээе. Төгсгөлд нь 2 + 3 * 4 яг яаж 14 болдгийг — өөрөө ч бас программ болох машин дотор — харах болно.

Яагаад модоо шууд алхаж болохгүй гэж?

Өмнөх удаа үүнийг өнгөц өнгөрсөн тул шулуухан хэлье.

Cecile-ийн анхны хувилбарт виртуал машин огт байгаагүй. AST — тэр сайхан мод — байсан бөгөөд би түүнийг зүгээр л алхдаг байлаа: +-ийг ажиллуулахын тулд зүүн дэд зангилаа руу орж, баруун дэд зангилаа руу орж, хоёрыг нэмнэ. Энгийн. Ажилладаг ч байсан. Тэгвэл би яагаад үүнийг хаяад бүхэл бүтэн байткод машин бүтээсэн юм бэ?

Хурдны төлөө — бас яагаад гэдгийг нь бодитоор харах нь зүйтэй. Мод алхана гэдэг нь үйлдэл бүрт программ санах ойгоор нааш цааш заагч хөөнө гэсэн үг: дэд зангилаа руу доошоо, буцаад дээшээ, өөр нэг рүү доошоо, буцаад дээшээ. Санах ой тархай байдаг тул CPU дараагийн зангилааг хүлээсээр л цагаа өнгөрөөнө. Байткодын хавтгай жагсаалт бол эсрэгээрээ: зааврууд санах ойд зэрэгцэн байрлаж, машин тэднийг нэг шулуун, урьдчилан таамаглахуйц дарааллаар уншина. Үр дүн нь адилхан, гэхдээ нэг загвар нь техник хангамжтай тэмцдэг бол нөгөө нь түүнтэй зохицдог.

Жинхэнэ хэлүүд — V8, Python, JVM — модоо алхахын оронд байткод руу хөрвүүлдэг шалтгаан ердөө л энэ. Тиймээс би ч гэсэн тэгсэн.

Хамгийн жижиг машин: нэг давталт, нэг стек

Санаа бүхэлдээ ердөө ийм жижиг.

Байткод виртуал машин хоёр хэсэгтэй:

1. Зааврын заагч (instruction pointer) — одоогийн заавар руу чиглэсэн хуруу. Дээрээс эхлээд доош алхана.
2. Стек (stack) — зөвхөн дээд талаас нь хүрч болох утгуудын овоо. PUSH дээр нь нэг утга тавина; MUL дээд хоёрыг авч, үржүүлээд, үр дүнг нь буцааж тавина.

Тэгээд л болоо. Виртуал машин бол нэг давталт: хурууны заасан зааврыг унш, гүйцэтгэ, хуруугаа доош нэг шилжүүл, дахин эхэл. Үүнийг авах–тайлах–гүйцэтгэх (fetch–decode–execute) давталт гэдэг. Энэ нэр танил сонсогдож байвал гайхах хэрэггүй — жинхэнэ CPU яг ингэж ажилладаг. Байткод виртуал машин бол программаар хийсэн жижигхэн CPU.

CPU-ийн дүрд тоглож буй программ

Сүүлийн өгүүлбэр дээр түр саатъя, учир нь бүх нууц нь тэнд байгаа.

Жинхэнэ CPU бол чип. Түүний дотор нэг регистр дараагийн заавар руу заадаг. Чип тэр зааврыг авч, утгыг нь тайлж, гүйцэтгээд, заагчаа цааш шилжүүлнэ — секундэд хэдэн тэрбум удаа. Мөн тэр зөвхөн өөрийн заавруудыг л ойлгодог: цахиурт шингэсэн машины код.

Миний виртуал машин яг ижил ажлыг хийдэг — гэхдээ чип биш. Энэ бол Rust дээр бичсэн программ. Түүний зааврын заагч бол зүгээр л нэг хувьсагч. Заавар нь байткод — PUSH, MUL, ADD — миний өөрөө зохиосон жижигхэн зааврын багц. Дэлхий дээрх ямар ч чип PUSH 3-ыг ойлгохгүй. Харин миний виртуал машин ойлгодог, учир нь түүнийг ойлгодог мэт ажилладаг давталтыг би өөрөө бичсэн.

Виртуал гэдэг нь энд үүнийг л хэлж байгаа юм. Виртуал машин бол биетээр оршдоггүй машин: CPU-ийн дүрд тоглож буй программ. Харин түүний доор жинхэнэ CPU тэр программыг өөрийн жинхэнэ заавруудаар нэг нэгээр нь ажиллуулж байдаг.

Тэгэхээр бие биенийхээ дээр давхарласан хоёр машин байна — миний бүтээсэн, CPU-ийн дүрд тоглодог машин, мөн түүнийг ажиллуулдаг жинхэнэ машин. Энэ зургийг санаж яваарай. Энэ цувралын үлдсэн хэсэг бүхэлдээ тэр жинхэнэ машин яг юу хийж байгаа тухай.

Нэг нэмэх үйлдэл, хоёр машин

Илүү тодорхой болгохын тулд ганцхан нэмэх үйлдлийг — 2 + 3-ыг — хоёр машин дээр дагаж үзье.

Миний виртуал машинд байткод 2, 3-ыг аль хэдийн стек дээр тавьчихсан, дараагийн заавар нь ADD. Үүнийг ажиллуулдаг Cecile-ийн виртуал машины хэсэг энэ (бага зэрэг товчилсон):

loop {
    match self.read_u8() {        // авах: дараагийн байтыг уншаад, ip-г урагшлуулна
        op::ADD => self.op_binary_add(),
        op::MUL => self.mul(),
        // ...заавар бүрд нэг салбар
    }
}

fn op_binary_add(&mut self) {
    let b = self.pop();           // 3
    let a = self.pop();           // 2
    self.push((a.as_number() + b.as_number()).into());   // 5
}

Авах нь read_u8. Тайлах нь match. Гүйцэтгэх нь op_binary_add: хоёр утга авч, нэмээд, үр дүнг буцааж тавина. Энэ бол ганц байткод заавар — гэхдээ мөр бүр нь энгийн Rust код тул бүгд жинхэнэ CPU-ийн гүйцэтгэдэг жинхэнэ машины заавар болж хөрвөнө. Байт унших, зөв салбар руу үсрэх, хоёр удаа авах, нэг удаа тавих: миний виртуал машины ганц ADD жинхэнэ CPU дээр нэлээд хэдэн заавар болдог. Тэдний дунд a + b өөрөө CPU-ийн жинхэнэ нэмэх заавар болж хөрвөнө (Cecile-ийн тоонууд 64 битийн бутархай тоо тул бутархай тооны нэмэх заавар).

Жинхэнэ CPU-д яг энэ нэмэх үйлдэл ганцхан заавар. 2 аль хэдийн eax гэдэг регистрт байгаа, дараагийн заавар нь add eax, 3 гэж бодъё. Санах ойд энэ ердөө гурван байт: 83 C0 03. CPU-ийн зааврын заагч — x86-64 дээр rip гэдэг регистр — тэдгээр рүү заана. Чип байтуудыг авч, тайлагч нь «eax-д 3-ыг нэм» гэдгийг таньж, ALU гэдэг хэлхээ нэмэх үйлдлийг хийнэ. eax одоо 5-ыг агуулж, rip дараагийн заавар руу шилжинэ. Давталт ч, match ч, үүнийг ажиллуулдаг программ ч байхгүй. Авах–тайлах–гүйцэтгэх давталт нь цахиурын хэлхээнд шууд шингэсэн.

Нэг нэмэх үйлдэл, нэг хариу. Гэхдээ миний виртуал машинд ганц ADD бол жинхэнэ CPU дээр ажилладаг жижиг программ. Харин жинхэнэ CPU-д add бол хамгийн доод түвшин: түүний доор хэлхээнээс өөр юу ч байхгүй.

Одоо бүх зүйл ажилладгийг заавруудаа гараар нэг бүрчлэн мөшгиж баталъя.

Стек 2 + 3 * 4-ийг хэрхэн бодохыг хараарай

Байткодыг дээрээс доош ажиллуулна. Алхам бүрийн дараах стекийг зурна, дээд тал нь баруун гар талд.

эхлэл          стек: [ ]

PUSH 3         стек: [ 3 ]
PUSH 4         стек: [ 3, 4 ]
MUL            → 4-ийг, 3-ыг авч, 3*4-ийг хийнэ    стек: [ 12 ]
PUSH 2         стек: [ 12, 2 ]
ADD            → 2-ыг, 12-ыг авч, 12+2-ыг хийнэ    стек: [ 14 ]
STORE x        → 14-ийг авч x хувьсагчид хийнэ     стек: [ ]   (x = 14)

Юу болсныг хараач. Машин үйлдлийн эрэмбэ, мод, үржих нь түрүүлдэг гэдгийг хаана ч «мэдээгүй». Дараалал аль хэдийн зааврын жагсаалтад шингэчихсэн байсан — компайлер модыг алхахдаа MUL-ыг ADD-ийн өмнө тавьсан. Виртуал машин юу ч ойлгодоггүй. Хэлсэн дарааллаар нь л утга тавьж, авсаар байгаад зөв хариуг гаргаад ирдэг.

Өөрийн стекээ ингэж ажиллаж байгааг — заавар бүрийн дараа өөрийгөө хэвлэж байгааг — анх харсан тэр мөчөөс эхлэн энэ бүхэн ид шид мэт санагдахаа больсон. Энэ бол зүгээр л тоонуудын овоо ба нэг давталт.

Функцүүд: стек дээшээ өсдөг

Тоо таах тоглоомд функц хэрэгтэй, харин стек өөрийн ач холбогдлоо функц дээр л харуулдаг.

Cecile guessGame()-ийг дуудахад виртуал машин зүгээр л түүн рүү үсрээд хаанаас ирснээ мартаж болохгүй — дараа нь буцаж ирэх ёстой. Тиймээс эхлээд стек дээр жижиг бүртгэлийн багц тавина: хаашаа буцах, мөн функцийн локал хувьсагчдад зориулсан зай. Тэр багцыг дуудлагын фрейм (call frame) гэдэг. Функц дуудвал фрейм нэмнэ. Буцвал фреймээ авна — хуруу ч яг орхисон газраа буцаж үсэрнэ.

Дуудлагуудыг давхарлахад фреймүүд бие биенийхээ дээр овоорно. Тэгэхэд программчлалын хамгийн аймшигтай хэллэг аймшигтай байхаа болино: stack overflow гэдэг нь шууд утгаараа энэ стек түүнд өгсөн зайнаасаа өндөр болох явдал — ихэвчлэн нэг функц өөрийгөө дахин дахин дуудаад хэзээ ч буцахгүй, фреймүүдийг эцэс төгсгөлгүй овоолсны улмаас. Энэ нууцлаг алдаа биш. Нүдээрээ харж болно. Яг энэ овоо тааз мөргөж байгаа нь.

Хэн ч анхааруулдаггүй хэсэг: цэвэрлэгээ

Гарын авлага тав тухтай байхаа больсон газар энд.

Cecile дээр let name: string = "Bataa" гэж бичээд тэр үсгүүд хаана хадгалагдахыг огт бодолгүй явж болно. Гэхдээ хаа нэгтээ виртуал машин санах ойн сул хэсэг олж, тэмдэгт мөрийг тэнд тавиад, санаж байх ёстой байсан. Харин тэр мөрийг хэн ч ашиглахаа больсон үед — функц буцсан, хувьсагч алга болсон — тэр санах ойг буцааж өгөх ёстой. Эс бөгөөс программ машины бүх санах ойг аажмаар идсээр байгаад унана.

Миний урьдчилан хараагүй урхи энд байлаа. Би Cecile-ийн виртуал машиныг Rust дээр бичиж байсан бөгөөд Rust-ын алдартай санах ойн аюулгүй байдал үүнийг өөрөө шийднэ гэж бодсон. Үгүй — энэ асуудлыг шийддэггүй. Rust өөрийн утгуудыг автоматаар цэвэрлэдэг. Харин Cecile программ ажиллах явцдаа үүсгэдэг объектууд — тэмдэгт мөр, массив, бие бие рүүгээ заагаад тойрог үүсгэж чадах объектууд — виртуал машины гараар удирддаг heap-д амьдардаг. Rust-ын хувьд энэ бол миний хариуцах нэг том санах ойн хэсэг л юм. Cecile-ийн аль объект амьд хэвээр байгааг зөвхөн Cecile л хэлж чадна. Тиймээс надад хоёр сонголт байлаа:

• Cecile программистаар хийлгэх (C шиг: өөрөө санах ой авна, өөрөө чөлөөлнө, алдана, бүх зүйл унана).
• Автоматаар хийх — өөрөөр хэлбэл, зочин хэлний объектуудад зориулж хог цуглуулагч (garbage collector) бичих.

Би Cecile-ийг энэ талаар огт бодох шаардлагагүй JavaScript шиг байлгахыг хүссэн. Тиймээс хог цуглуулагч сонгосон.

Хог цуглуулагч яг яаж боддог вэ

Санаа нь сонсогддогоосоо хамаагүй энгийн. Хог цуглуулагч нэг л асуултад дахин дахин хариулдаг: «Энэ санах ойд хүрэх зам байгаа юу?»

Энэ аргыг mark-and-sweep (тэмдэглэх ба цэвэрлэх) гэдэг бөгөөд яг нэрээрээ ажилладаг:

1. Тэмдэглэх (mark). Яг одоо амьд гэдгийг нь мэдэж байгаа зүйлсээс — стек дээрх хувьсагчид, одоогийн дуудлагын фреймүүд — эхлээд, бүх холбоосыг нь дагаж гадагш яв. Тэр тэмдэгт мөр, түүнийг агуулсан массив, тэр массив харьяалагдах объект. Хүрч болох бүхнийг будна.
2. Цэвэрлэх (sweep). Өгч байсан бүх санах ойгоо нэг бүрчлэн шалга. Будаагүй үлдсэн бүхэнд хүрэх зам байхгүй — ямар ч амьд хувьсагч дахиж түүнд хүрч чадахгүй — тиймээс энэ хог. Чөлөөл.

Бүх алгоритм ердөө л энэ. Хүрч болох нь амьд, хүрч болохгүй нь үхсэн. Аль нь аль болохыг зүгээр л... стекээс эхлэн сумнуудыг дагаж баталж болно.

Үнэнийг хэлэхэд үүнийг зөв болгох нь бүх төслийн хамгийн хэцүү, хамгийн алдаатай долоо хоног байсан. Ямар нэг зүйлийг хэтэрхий эрт чөлөөлбөл программ чинь хог уншаад огт ойлгомжгүй байдлаар унана. Хэтэрхий оройтож чөлөөлбөл санах ой алдагдана. Гэхдээ эцэст нь ажилласан тэр үед — Cecile давталт дотор мянга мянган тэмдэгт мөрийг боловсруулахдаа санах ойгоо хөөргөлгүй тогтвортой барьж чадсан тэр үед — энэ нь хэлийг анх ажиллуулснаас ч илүү том амжилт мэт санагдсан.

Ухарч харъя: бид юу бүтээв?

Бүхэл бүтэн хэлний ажиллах орчин (runtime) — гэхдээ толгойд чинь багтана:

• Кодыг чинь байткодын хавтгай жагсаалт болгодог компайлер (өмнөх нийтлэл).
• Тооцоолох явцад утгуудыг хадгалдаг стек.
• Заавар бүрийг аваад гүйцэтгэдэг давталт — программаар хийсэн жижигхэн CPU.
• Функцүүдэд бие биенээ дуудаж, буцаж ирэх боломж олгодог дуудлагын фреймүүд.
• Чиний ашиглахаа больсон зүйлсийг чимээгүйхэн эргүүлэн авдаг хог цуглуулагч.

Энэ бол JavaScript, Python хэрхэн ажилладгийн тоглоом хувилбар биш. Бүтцийн хувьд тэд яг ийм. Жинхэнэ хэлүүд дээр нь мянган оптимизаци нэмдэг — хамгийн том нь JIT компиляци: программ ажиллаж байх зуур хамгийн олон давтагддаг хэсгүүдийг нь виртуал машин анзаараад, яг тэднийг жинхэнэ машины код руу шууд хөрвүүлдэг. Гэхдээ зүрх нь чиний сая харсан тэр давталт ба стек хэвээрээ.

Гэсэн ч — би техник хангамжид хүрээгүй хэвээр байлаа

Cecile одоо бүх зүйлтэй болсон: кодыг токенд хувааж, модонд задалж, байткод руу хөрвүүлж, ажиллуулж, ард нь өөрөө цэвэрлэдэг. Ямар ч ухаалаг хэмжүүрээр бол дууссан. Жинхэнэ хэл.

Гэхдээ сүүлийн хэсгийг дахин уншаад үз. «Программаар хийсэн жижигхэн CPU.» «Жинхэнэ машины код руу хөрвүүлдэг.» Би ийм өгүүлбэрүүдийг бичсээр, тэдний хажуугаар гулсаж өнгөрсөөр байлаа. Миний виртуал машин бол программаар хийсэн CPU — жинхэнэ CPU дээр ажилладаг. Миний JIT машины код руу хөрвүүлэх байсан — гэхдээ машины код гэж чухам юу юм бэ? Өөртөө өгсөн тайлбар бүр маань нэг л газар тасардаг байлаа — миний харж чадахаас нэг давхар доор.

Би өөрийн машин дотор машин бүтээчихсэн. Гэтэл хамгийн доод талын машин хэдэн үсгийг яг юу хийдгийг одоо ч хэлж чадахгүй байлаа.

Тиймээс би Cecile-д юм нэмэхээ зогсоосон. Cecile бол ажилладаг хэл — гэхдээ үргэлж программ дотор, үргэлж миний удирддаг виртуал машин дотор, цахиурт хэзээ ч хүрдэггүй. Жинхэнэ хариуг хүсвэл надад өөр төрлийн хэл хэрэгтэй байв. Тав тухтай виртуал машин дээр огт ажилладаггүй, харин чипийн шууд гүйцэтгэдэг заавар хүртэл бүрэн хөрвүүлэгддэг хэл.

Надад компайл хийгддэг хэл бүтээх хэрэгтэй байлаа. Мөн түүний түлхүүр үгс миний эх хэлээр байгаасай гэж хүссэн.

Дараа нь: 2-р улирал

Эндээс эхлэн яриа Cecile-ийн тухай байхаа больж, техник хангамжийн тухай болно.

Шинэ хэл, шинэ ном, энэ удаад код чип хүртэл шууд хөрвүүлэгдэнэ. Бид доошоо явна — жинхэнэ компайлерыг дамжиж, LLVM-ийн хажуугаар (яагаад алгассанаа ч хэлнэ), ассемблер болон CPU өөрөө рүү, программ эцэст нь үйлдлийн системтэй уулздаг системийн дуудлага, линкер хүртэл.

2-р улирал компайлераар эхэлнэ. Нуугдах виртуал машин байхгүй. 👋