Энэ бяцхан программыг ойлгох гэж би гурван жил зарцуулсан

Өөрийн программчлалын хэл бүтээх нь — 1-р хэсэг: Интерпретатор

Ойлгох гэж гурван жил зарцуулсан анхны программ минь энэ:

функц үндсэн() -> тоо {
    мөр_хэвлэх("Өдрийн мэнд");
    // буц 0;   // байхгүй байсан ч болно — үндсэн() өөрөө 0-г буцаана
}

Өдрийн мэнд

Зургаан мөр. Нэг мэндчилгээ. Гурван жил.

Би энэ файлыг гурван жил ширтэж суусан гэсэн үг биш. Энэ хэдэн мөрөнд нэг асуулт нуугдаж байсан бөгөөд түүнд жинхэнэ ёсоор хариулах гэж би гурван жил зарцуулсан: машинд хэдэн үсэг өгөхөд тэр үүнийг яг яаж ажиллуулдаг вэ? Ерөнхийд нь биш — хамгийн гүн давхарга хүртэл нь бүрэн ойлгохыг хүссэн юм.

Энэ бол тэр асуултыг хөөж эхэлсэн эхний жилийн минь түүх. Би яаж өөрийн программчлалын хэл бүтээхээр зориглосон, «hello world»-ийг задлаад дотроос нь юу олж харсан, хамгийн уйтгартай гэгддэг тэр программ хэрхэн компьютерийн талаарх хамгийн сонирхолтой бүх зүйлийг чимээгүйхэн нуугаад байдгийг өгүүлье.

Тэгэхээр — яагаад ийм зүйл хийх болов?

Би юу хийхээ ч мэдэхгүй байсан хоёрдугаар курсын оюутан байлаа.

Заримдаа шөнө орой болтол унтаж чадалгүй, нэг л асуултыг бодож хэвтэнэ: ажилд яаж орох вэ? Надад бусад оюутнаас ялгарах юу байна? Ажлын туршлага гэж огт байхгүй. Тэгээд оюутнууд ихэвчлэн шийддэг шигээ — бага зэрэг сандран — нэг шийдвэр гаргалаа: хуруугаараа заагаад «Үүнийг би хийсэн» гэж хэлж болох нэг жинхэнэ зүйл надад хэрэгтэй.

Ингээд төсөл хайж эхлэв.

Үнэнийг хэлэхэд анхны зорилго маань тийм ч гүн гүнзгий зүйл биш байсан: ажилд ороход минь тус болох, бусдад гайхуулж болохуйц нэг төсөл олох л байлаа. build-your-own-x репог (өөрийн git / өгөгдлийн сан / regex хөдөлгүүр гэх мэтийг өөрөө бүтээх зааврын жагсаалт) гүйлгэж байтал нэг мөр анхаарлыг минь татлаа: өөрийн компайлер / интерпретатор бүтээх.

Эдгээр үг юу гэсэн үг болохыг би бүрэн мэдэхгүй байлаа. Гол нь ч тэр байсан. Зүгээр л сонирхолтой харагдсан.

«Зүгээр л сонирхолтой харагдсан болохоор уу?»

Тиймээ. Бас нэг зүйлийг хийх гэж байгаад замдаа өөр арван зүйлийг санамсаргүй сурчихдаг тийм төсөл шиг санагдсан.

Намайг татсан итгэл үнэмшил ийм байсан, одоо ч хэвээрээ: кодыг ажиллуулдаг тэр механизм бол программ хангамжийн хамгийн нууцлаг, хамгийн суурь хэсэг юм. Тэр нь компьютертэй яг зэрэгцэн төрж, хамт өссөн. Түүнийг авчихвал «программ хангамж» гэдэг үг утгаа алдана — программ бичих хэрэгсэл ч үлдэхгүй. Чиний хэрэглэж байсан апп, вэбсайт, тоглоом бүхэн хүний бичсэн текстийг чипийн гүйцэтгэх үйлдэл болгон хувиргадаг ямар нэг программ дээр суурилдаг. Би тэр механизмыг олон жил өдөр бүр ашиглаж байсан атлаа яаж ажилладгийг нь огт мэддэггүй байлаа.

Хэзээ нэгэн цагт дотор нь харах л ёстой гэж бодсон.

Энэ амаргүй байх нь тодорхой гэдгийг учрыг нь тайлбарлаж чадахгүй ч би мэдэрч байлаа. Компайлер компьютерийн ухааны талыг нэг дор хамардаг — грамматик, парсинг, өгөгдлийн бүтэц, санах ой, мөн CPU өөрөө яаж «боддог» талаар багахан. Яг тэр нь л намайг татсан. Хүнд сэдэв, өргөн цар хүрээ, сурах юм асар их. Ийм хэцүү зүйлийг санамсаргүй тэмтэрч сурахыг хүсээгүй — надад тодорхой бүтэц хэрэгтэй байв. Тэгээд хамгийн энгийн алхмыг хийлээ: ном худалдаж авлаа.

Ном: Crafting Interpreters

Robert Nystrom 2020 онд бичиж дуусгасан Crafting Interpreters номыг хүмүүс их магтдаг — магтуулах ч ёстой ном. Эхлэгчдэд ойлгомжтой ч өнгөц биш, гараар зурсан зураг ихтэй. Бас техникийн номын хувьд ховор зүйл: уншихад үнэхээр сонирхолтой. Энэ сэдвийг сурмаар байгаа бол энэ номоос эхэл. Үнэхээр.

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

1-р хэсэг — Tree-Walk интерпретатор (10 бүлэг). Java дээр Lox нэртэй жижиг хэл бүтээнэ. Lox нь JavaScript-тэй, үнэндээ ихэнх script хэлтэй адилхан санагдах ба төгсгөлд нь бүрэн ажилладаг болно. Үүнийг tree-walk интерпретатор гэдэг нь программаас чинь шууд мод (tree) босгоод, тэр модоо зангилаа зангилаагаар нь алхаж, зангилаа болгоны хэлснийг гүйцэтгэдэгт оршино. Хэлийг ажиллуулах хамгийн шулуун арга. Ихэнх эхлэгч энд ирж тогтдог — тэр бол огт буруу зүйл биш. Би ч бас тэгсэн.

2-р хэсэг — Байткод виртуал машин (17 бүлэг). Энэ бол номын цөм, энгийн гарын авлага байхаа больж жинхэнэ боловсрол болж хувирдаг газар. Java хувилбараа хаяад, Lox-оо энэ удаад C дээр эхнээс нь дахин бүтээнэ. Энэ удаад жинхэнэ хэлүүдийн цаана ажилладаг санаануудтай танилцана:

• Байткод (bytecode) — мод алхахын оронд программаа жижигхэн зааврын нягт жагсаалт болгон хавтгайруулна.
• Виртуал машин — тэр зааврыг давталт дотор ажиллуулдаг, программаар хийсэн жижигхэн CPU.
• Санах ойн удирдлага — одоо C дээр байгаа болохоор чиний араас цэвэрлэх хүн байхгүй.
• Garbage collector — хэл нь өөрийн хэрэглэгчдийн араас автоматаар цэвэрлэж чадахын тулд.

Tree-walk хувилбар аль хэдийн ажиллаж байхад яагаад ийм зовлон үүрэх вэ? Хурдны төлөө, бас бодит байдалд ойртохын төлөө. Мод алхана гэдэг үйлдэл бүрт санах ойн өнцөг булан бүрээр заагч хөөнө гэсэн үг; энгийн ч удаан. Байткод болгон хавтгайруулж, нэг энгийн давталтаар ажиллуулах нь орчин үеийн хэлүүд бодитоор яаж ажилладагт хамаагүй ойр. JavaScript-ын V8, Python, Java — бүгд энэ байткод-виртуал машины санааны нэг хувилбар дээр ажилладаг. Хурдан хэлүүдийн нэмж хэрэглэдэг заль бол JIT (Just-In-Time) компиляци: программ ажиллаж байх зуур хамгийн олон давтагддаг хэсгүүдийг нь анзаараад, яг тэднийг нь жинхэнэ машины код руу шууд хөрвүүлдэг. Миний сурч байсан яг тэр цөм архитектур; дээр нь нэг ухаалаг давхарга нэмсэн хэрэг.

2-р хэсгийн төгсгөлд надад ажиллагаатай хэл байхаас гадна өөрийн гэсэн бодол төрсөн байлаа.

Өөрийн хэлээ загварчлах

Тэгээд би Lox хүсэхгүй байгаагаа ойлгов. Өөрийнхийгөө хиймээр байлаа.

Тэр үед би Rust сурч байсан бөгөөд үнэхээр дурлачихсан байв — гайхалтай хэл (borrow checker бид хоёр санал зөрөлддөг ч энэ тусдаа яриа). Ингээд өөрөөсөө нэг энгийн мэт харагдах асуулт асуулаа:

Rust шиг уншигддаг, JavaScript шиг ажилладаг, TypeScript шиг төрөлтэй хэл бол ямар вэ?

Тэр минь зорилго болов. Rust-ын цэвэрхэн, тодорхой синтакс. JavaScript-ын хялбар, чөлөөтэй ажиллагааны мэдрэмж. TypeScript-ын «хэрэгтэй үед нь төрөл байдаг» гэдэг. Мөн хамгийн их дуртай шийдэл маань:

Түлхүүр үгс нь монголоор.

функц бол function. мөр_хэвлэх бол нэг мөр хэвлэх. буц бол return. хэрэв … бол нь if … then. Миний hello world «hello world» гэдэггүй — Өдрийн мэнд гэдэг. Эхэндээ зүгээр л гоёлын юм шиг сонсогдоно, гэтэл анхны давталтаа өөрийн үсгээр бичихэд юу юунаас илүү жам ёсны зүйл мэт санагддаг.

Гэхдээ компьютер амтаар ажилладаггүй. Хэлийг жинхэнэ утгаар бүтээхийн тулд эхлээд түүний дүрмийг (grammar) бичнэ — юуг зөв программ гэж тооцохыг зааж өгдөг яг тодорхой журам. Дүрэм бол гэрээ. Түүнийг гаргамагц дараагийн бүх зүйл дараалсан хөрвүүлэлт болно: хөрвүүлэлт бүр программыг чинь машин гүйцэтгэж чадах хэлбэрт нэг алхам ойртуулна. Нэг мөр кодыг эдгээр алхам бүрээр дамжуулж үзүүлье.

Нэг мөр код яаж машин ажиллуулж чадах зүйл болж хувирдгийг харцгаая

Программ дотор ийм мөр байлаа гэж бодъё:

зарла x: тоо = 2 + 3 * 4;   // let x: int = 2 + 3 * 4

Энэ мөр ийм аялал хийнэ.

1-р шат — Лексер: текст → токенууд

Компьютер үг хардаггүй. Тэр зөвхөн тэмдэгтийн урсгал хардаг: з, а, р, л, а, зай, x, : гэх мэт. Лексер (эсвэл scanner) бол анхны хөрвүүлэгч. Ганц ажил нь тэр урсгалыг утга бүхий хэсгүүд буюу токен (token) болгон хуваагаад, тус бүрд нь шошго наах.

Ингээд зарла x: тоо = 2 + 3 * 4; лексерээс ийм болж гарна:

[зарла → keyword:let]  [x → identifier]  [: → colon]
[тоо → type:int]       [= → equals]
[2 → number]  [+ → plus]  [3 → number]  [* → star]  [4 → number]  [; → semicolon]

Тэгээд л болоо. Текст орж, шошготой токенууд гарна. Лексер математик ч, утга ч хараахан ойлгодоггүй — * нь +-ээс түрүүлж бодогддогийг мэдэхгүй. Зүгээр л «энэ бол тоо, тэр бол түлхүүр үг, энэ тэмдэг бол од» гэдгийг мэднэ. Энгийн, хурдан, гэхдээ зайлшгүй хэрэгтэй.

2-р шат — Парсер: токенууд → мод

Энэ бол хүнд хэсэг. Үнэнийг хэлэхэд, бүх төслийн хамгийн хэцүү алхмуудын нэг.

Парсер тэр хавтгай токенуудыг аваад доторх нь нуугдаж буй бүтцийг — миний дүрмийн шаардсан хэлбэрийг — олж илрүүлнэ. Сонгож болох парсингийн алгоритм олон байдаг ба би Pratt parsing-ийг recursive descent дээр ажиллуулах аргыг сонгосон. Pratt-ыг сонгосон шалтгаан маань лексерийн дийлээгүй яг тэр зүйл: үйлдлийн эрэмбэ (precedence). 2 + 3 * 4 бол (2 + 3) * 4 = 20 биш. Энэ бол 2 + (3 * 4) = 14, учир нь үржих нь нэмэхээс түрүүлж бодогддог — тэр дүрэм эцэст нь парсер дээр хэрэгжинэ.

Гаралт нь мөр байхаа больж, мод болно:

Уншаад үз — утга нь хэлбэр дотор нь шингэсэн байна: +-ийг тооцоолохын тулд эхлээд *-ийг тооцоолох ёстой, учир нь * нь модонд түүнээс доор сууж байна. Дарааллын асуудал бүтцээрээ шийдэгдэв. Энэ мод жинхэнэ нэртэй — Абстракт синтакс мод буюу AST — бөгөөд бүх дамжлагын хамгийн сэтгэл ханамжтай бүтээгдэхүүн юм, учир нь энэ бол түүхий текст утгаа өөрөө мэддэг зүйл болж хувирдаг мөч. (Хэрэв токенууд дүрэмд таарахгүй бол — жишээ нь зарла x = = 2 гэж бичвэл — парсер яг энд зогсоод чамд синтаксын алдаа өгнө.)

3-р шат — Байткод үүсгэх: мод → зааврууд

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

Ойлголтын хувьд манай бяцхан мод ойролцоогоор ийм болж хөрвөнө:

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

Модны давхарласан бүтэц дараалал болж хувирсныг анзаар: эхлээд үржүүл, дараа нь нэм, эцэст нь хадгал. Тэр бол модны утга, машины дараалан дагаж чадах алхмууд болж дэлгэгдсэн хэлбэр — дахиж модоор заагч хөөх шаардлагагүй. Тэр жагсаалтыг виртуал машинд өгвөл дээрээс доош ажиллаад эцэст нь x-ийн утга 14 болно.

Текст → токен → мод → зааврууд → үр дүн. Дөрвөн хөрвүүлэлт. Энэ бол интерпретатор.

Түр зогсъё — интерпретатор уу, компайлер уу? Ялгаа нь юу вэ?

Зогсоход тохирсон мөч, учир нь эхний сар бүхэлдээ намайг бодогдуулсан асуултыг чи ч бас бодож байж магадгүй: интерпретатор гэж юу юм, компайлераас юугаараа ялгаатай юм бэ?

Эцэст нь надад ойлгуулсан зүйрлэл энэ байна, үүнээс сайныг би олж хараагүй:

Интерпретатор бол хэлмэрч. Компайлер бол орчуулагч.

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

Ингэж хэлэхээр ялгаа нь асар том — ашиг, алдагдал нь ч мөн адил. Орчуулагч (компайлер) илүү сайн, илүү хурдан үр дүн гаргаж чадна, яагаад гэвэл шийдэхээсээ өмнө бүгдийг хардаг тул шалгах, оптимизаци хийх зай нь илүү. Хэлмэрч (интерпретатор) түүнийг орхиж, оронд нь яг одоо, хүлээлгүй, илүү уян хатнаар эхэлдэг. Аль нь ч «зөв» биш; өөр өөр хэлцэл. Мөн хамгийн хурдан орчин үеийн хэлүүд дээр дурдсан JIT-ээр хоёулаа нэгэн зэрэг байж заль хийдэг — эхлээд шуурхай эхлэхийн тулд интерпрет хийж, дараа нь хамгийн олон давтагддаг хэсгүүдээ хурдны төлөө чимээгүйхэн компайл хийдэг.

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

Хажуугийн бодол: тэгвэл яагаад бүх зүйлийг чаддаг ганц хэл байдаггүй юм бэ?

Энэ асуулт намайг хэдэн сар зовоосон тул эцэст нь хариулт өгсөн бодлоо чамтай хуваалцъя.

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

Мөн энэ зөвхөн амт сонирхлын асуудал биш — техник хангамж хүртэл гүн бууна. CPU өөрөө өөр өөр гэр бүлд хуваагддаг бөгөөд дээр нь суусан үйлдлийн систем хэл болгоны юуг чухалчлахыг тодорхойлно. Хоёр том бүлэг:

• CISC — Complex Instruction Set Computer. Intel, AMD чипүүд. x86, x86_64 гэх архитектурууд, тэдэн рүү чиглэсэн олон ассемблер: GAS, NASM, FASM, MASM, TASM гэх мэт.
• RISC — Reduced Instruction Set Computer. ARM гэр бүл (armv1–8), мөн RISC-V, MIPS. Энэ бол чиний Raspberry Pi, STM32, ESP32.

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

Хэрэв цаг хугацааныхаа бараг бүхнийг онол дээр зарцуулж байгаагаа анзаарвал багахан анхаарлаа практик зүйл рүү хандуул; энэ нь чиний онолыг сайжруулна. Хэрэв бараг бүхнийг практик дээр зарцуулж байвал багахан анхаарлаа онол руу хандуул; энэ нь чиний практикийг сайжруулна. — Donald Knuth

Жинхэнэ ажилладаг уу? Энд бүтэн хэл, ажиллаж байна

Онол хангалттай. Дүрэм, лексер, парсер, байткод, виртуал машин — тэр бүхний дараа энд миний хэл дээр бичсэн жинхэнэ, бүрэн программ байна. Тоо таах тоглоом:

функц таахТоглоом() -> хоосон {
    мөр_хэвлэх("Та таамгаа оруулна уу:");

    зарла зорилтотТоо: тоо = санамсаргүйТоо(100);
    зарла оролдлого: тоо = 0;
    зарла хамгийнИхОролдлого: тоо = 10;

    давтах оролдлого < хамгийнИхОролдлого бол {
        зарла таамаглал: тоо = унш32();
        оролдлого = оролдлого + 1;

        хэрэв таамаглал == зорилтотТоо бол {
            мөр_хэвлэх("баяр хүргэе, та зөв таалаа 🎉");
            мөр_хэвлэх("Таны оролдлогын тоо:");
            хэвлэ(оролдлого);
            буц 0;
        }

        хэрэв зорилтотТоо > таамаглал бол {
            мөр_хэвлэх("бага байна");
        }

        хэрэв таамаглал > зорилтотТоо бол {
            мөр_хэвлэх("их байна");
        }
    }

    мөр_хэвлэх("Таны оролдлогын тоо:");
    хэвлэ(оролдлого);
}

функц үндсэн() -> тоо {
    // Программ санамсаргүй тоо гаргаж, хэрэглэгч түүнийг таах зорилготой тоглоом.
    таахТоглоом();
    буц 0;
}

Доторх бүхнийг хараач: төрөлтэй хувьсагч, давтах давталт, хэрэв … бол нөхцөл, функцийн дуудлага, санамсаргүй тооны дуудлага, гараас оролт унших, мөрөн дэх эможи. Тэдгээр боломж болгон токен болж лекслэгдэж, мод болж парслагдаж, байткод болж буурч, миний бичсэн виртуал машинаар гүйцэтгэгдэх ёстой байсан — түлхүүр үг нь монгол хэлтэй хэл дээр. Анх удаа ажиллаад над руу бага байна гэж хэвлэхэд би зүгээр л инээмсэглэн суусан. Одоо ч үүнийг хуулж тавихад бага зэрэг бодит бус мэт санагдана.

Гэхдээ нэг зүйл дутуу хэвээр байлаа

Гэсэн ч.

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

Тэгэхээр дараагийн алхам тодорхой. Интерпретатор намайг нэг давхар доош буулгасан бол жинхэнэ компайлер — C, C++, Rust-аар дамжаад эцэст нь чипийн шууд ойлгодог машины код хүртэл — үлдсэн замыг гүйцээнэ.

Ингээд гүн рүү шумбацгаая.

2-р хэсэгт үргэлжилнэ

Хоёр дахь жил. Одоо илүү хэцүү ном унших цаг иржээ.

Интернэт, Reddit-ийн тал хувийг ухсаны эцэст би Nora Sandler-ийн Writing a C Compiler-ийн хэвлэмэл хувийг гартаа авлаа — дөнгөж саяхан гарсан ном. Энэ удаад цаана нь нуугдах интерпретатор байхгүй. Энэ удаад бид ассемблер хүртэл шууд бууна.

2-р хэсэгт уулзъя. Баяртай. 👋