Kirjutasin programmeerimiskeele. Siit saate teada, kuidas saate ka.

Viimase kuue kuu jooksul olen töötanud programmeerimiskeele nimega Pinecone. Ma ei nimetaks seda veel küpseks, kuid sellel on juba piisavalt funktsioone, et see oleks kasutatav, näiteks:

  • muutujad
  • funktsioone
  • kasutaja määratletud struktuurid

Kui see teile huvi pakub, vaadake Pinecone'i sihtlehte või selle GitHubi repot.

Ma ei ole ekspert. Kui ma seda projekti alustasin, polnud mul aimugi, mida ma tegin ja ei tee seda siiani. Olen keeleloome õppinud nullklassi, lugenud selle kohta ainult natuke veebis ja pole järginud paljusid mulle antud nõuandeid.

Ja ometi tegin ma ikkagi täiesti uue keele. Ja see töötab. Nii et ma pean midagi õigesti tegema.

Selles postituses sukeldun kapoti alla ja näitan torujuhtme Pinecone (ja teisi programmeerimiskeeli), mida lähtekoodi võluks muuta.

Puudutan ka mõnda minu tehtud kompromissi ja seda, miks ma oma otsused tegin.

See pole kaugeltki täielik õpetus programmeerimiskeele kirjutamiseks, kuid see on hea lähtepunkt, kui olete huvitatud keele arendamisest.

Alustamine

"Mul pole absoluutselt aimugi, kust ma üldse alustaksin" on asi, mida kuulen palju, kui ütlen teistele arendajatele, et kirjutan keelt. Juhul, kui see on teie reaktsioon, vaatan nüüd läbi mõned esialgsed otsused, mis tehakse ja mis astutakse uue keele alustamisel.

Koostatud vs tõlgendatud

Keeli on kahte peamist tüüpi: kompileeritud ja tõlgendatud:

  • Koostaja mõtleb välja kõik, mida programm teeb, muudab selle masinkoodiks (vormingus, mida arvuti suudab väga kiiresti käitada), seejärel salvestab selle hiljem täidetavaks.
  • Tõlk astub lähtekoodist läbi rea, selgitades välja, mida ta teeb.

Tehniliselt võiks koostada või tõlgendada ükskõik millist keelt, kuid üks või teine ​​on konkreetse keele jaoks tavaliselt mõttekam. Üldiselt kipub suuline tõlge olema paindlikum, kompileerimisel aga suurem jõudlus. Kuid see kraabib ainult väga keeruka teema pinda.

Ma hindan kõrgelt jõudlust ja nägin, et puuduvad programmeerimiskeeled, mis oleksid ühtaegu nii suure jõudluse kui ka lihtsusele orienteeritud, nii et läksin koos Pinecone'i jaoks kompileeritud.

See oli oluline otsus varakult langetada, sest see mõjutab paljusid keelekujunduse otsuseid (näiteks staatiline kirjutamine on kompileeritud keeltele suureks eeliseks, kuid tõlgendatud keelte jaoks mitte nii palju).

Hoolimata asjaolust, et Pinecone oli loodud just kompileerimist silmas pidades, on sellel siiski täiesti toimiv tõlk, mis oli ainus viis seda mõnda aega käitada. Sellel on mitu põhjust, mida ma hiljem selgitan.

Keele valimine

Ma tean, et see on natuke meta, kuid programmeerimiskeel on ise programm ja seega peate selle kirjutama keeles. Valisin C ++ selle jõudluse ja suure funktsioonikomplekti tõttu. Samuti meeldib mulle tegelikult töötada C ++ -s.

Kui kirjutate tõlgendatud keelt, on mõttekas kirjutada see kompileeritud keelde (näiteks C, C ++ või Swift), kuna teie tõlgi ja teie tõlki tõlgendavas tõlkes kaotatud jõudlus liitub.

Kui kavatsete kompileerida, on aeglasem keel (nt Python või JavaScript) vastuvõetavam. Kompileerimisaeg võib olla halb, kuid minu arvates pole see kaugeltki nii suur probleem kui halb jooksuaeg.

Kõrgetasemeline disain

Programmeerimiskeel on tavaliselt üles ehitatud kui torujuhe. See tähendab, et sellel on mitu etappi. Igal etapil on andmed vormindatud kindlal, täpselt määratletud viisil. Sellel on ka funktsioonid andmete teisendamiseks igast etapist järgmisse.

Esimene etapp on string, mis sisaldab kogu sisendallika faili. Viimane etapp on midagi, mida saab joosta. See kõik saab selgeks, kui käime Pinecone torujuhtme samm-sammult läbi.

Lexing

Esimene samm enamikus programmeerimiskeeltes on leksimine ehk tokeniseerimine. "Lex" on lühike leksikaalseks analüüsiks, väga uhke sõna hunniku teksti jagamiseks märkideks. Sõna „tokenizer” on palju mõttekam, kuid „lexer” on nii lõbus öelda, et ma kasutan seda ikkagi.

Märgid

Luba on väike keeleühik. Luba võib olla muutuja või funktsiooni nimi (AKA identifikaator), operaator või number.

Lexeri ülesanne

Lekser peaks võtma sisse stringi, mis sisaldab kogu failide väärtuses lähtekoodi, ja sülitama välja loendi, mis sisaldab kõiki märke.

Torujuhtme tulevased etapid ei viita algsele lähtekoodile, seega peab lekser tootma kogu neile vajaliku teabe. Selle suhteliselt range torujuhtme vormingu põhjus on see, et lekser võib teha selliseid ülesandeid nagu kommentaaride eemaldamine või tuvastamine, kas midagi on number või identifikaator. Soovite hoida seda loogikat lukustuses lukustatuna, nii et te ei peaks ülejäänud keele kirjutamisel nendele reeglitele mõtlema ja nii saate seda tüüpi süntaksi kõik ühes kohas muuta.

Flex

Päeval, mil ma keelt alustasin, kirjutasin esimese asjana lihtsa lexeri. Varsti pärast seda hakkasin õppima tööriistade kohta, mis väidetavalt muudaksid leksimise lihtsamaks ja vähem lollakaks.

Valdav selline tööriist on leksereid genereeriv programm Flex. Annate talle faili, millel on keele grammatika kirjeldamiseks spetsiaalne süntaks. Sellest genereerib see C-programmi, mis leksitseerib stringi ja toodab soovitud väljundi.

Minu otsus

Valisin esialgu enda kirjutatud lekseri alles. Lõpuks ei näinud ma Flexi kasutamisest märkimisväärseid eeliseid, vähemalt mitte piisavalt, et õigustada sõltuvuse lisamist ja koostamisprotsessi keerukust.

Minu lekser on ainult mõnisada rida ja see tekitab mulle harva probleeme. Enda lexeri veeretamine annab mulle ka suurema paindlikkuse, näiteks võime lisada keelele operaatori ilma mitut faili redigeerimata.

Parsimine

Torujuhtme teine ​​etapp on parser. Parser muudab märkide loendi sõlmpuuks. Seda tüüpi andmete salvestamiseks kasutatav puu on tuntud kui abstraktne süntaksipuu ehk AST. Vähemalt Pinecone'is pole AST-l mingit teavet tüüpide ja milliste identifikaatorite kohta. See on lihtsalt struktureeritud märgid.

Parseri kohustused

Parser lisab struktuuri lekseri toodetud märkide järjestatud loendisse. Ebamäärasuste peatamiseks peab parser arvestama sulgude ja toimingute järjekorraga. Lihtsalt operaatorite parsimine pole eriti keeruline, kuid kui lisandub rohkem keelekonstruktsioone, võib sõelumine muutuda väga keerukaks.

Piisonid

Jällegi otsustati kaasata kolmanda osapoole raamatukogu. Valdav parsimisraamatukogu on Bison. Bison töötab palju nagu Flex. Kirjutate faili kohandatud vormingus, mis salvestab grammatikateabe, seejärel loob Bison selle abil C-programmi, mis teeb teie sõelumise. Ma ei valinud Bisoni kasutamist.

Miks kohandatud on parem

Lekseri puhul oli otsus kasutada minu enda koodi üsna ilmne. Lekser on nii tühine programm, et enda kirjutamata jätmine tundus peaaegu sama tobe kui omaenda vasakpoolse kirja kirjutamine.

Parseri puhul on asi teine. Minu Pinecone parser on praegu 750 rida ja ma olen neist kirjutanud kolm, sest kaks esimest olid prügikast.

Algselt tegin otsuse mitmel põhjusel ja kuigi see pole päris libedalt kulgenud, peab enamik neist paika. Peamised neist on järgmised:

  • Minimeerige kontekstivahetus töövoos: konteksti vahetamine C ++ ja Pinecone vahel on piisavalt halb, ilma et oleksite sisse visanud Bisoni grammatika grammatikat
  • Hoidke ehitamine lihtsana: iga kord, kui grammatika muutub, tuleb enne ehitamist Bison käivitada. Seda saab automatiseerida, kuid see muutub ehituskomplekside vahetamisel valuks.
  • Mulle meeldib ehitada jama: ma ei teinud Pinecone'i, sest arvasin, et see on lihtne, miks ma siis delegeeriksin keskse rolli, kui saaksin seda ise teha? Kohandatud parser ei pruugi olla tühine, kuid see on täiesti teostatav.

Alguses ei olnud ma täiesti kindel, kas lähen elujõulist rada pidi, kuid enesekindluse andis mulle see, mida Walter Bright (C ++ varajase versiooni arendaja ja D-keele looja) ütles teema:

"Mõnevõrra vaieldavam, ma ei viitsi raisata aega lexeri või parseri generaatorite ja teiste nn kompilaatorite kompilaatoritega. Need on aja raiskamine. Lekseri ja parseri kirjutamine on väike protsent kompilaatori kirjutamise tööst. Generaatori kasutamine võtab umbes sama palju aega kui ühe käsitsi kirjutamine ja see abiellub teid generaatoriga (mis on oluline kompilaatori uuel platvormil teisaldamisel). Ja ka generaatoritel on kahetsusväärne maine, et nad edastavad ebameeldivaid veateateid. "

Tegevuspuu

Oleme nüüdseks lahkunud üldlevinud, universaalsete terminite piirkonnast või vähemalt ei tea ma enam, mis need terminid on. Minu arusaamade järgi sarnaneb see, mida ma nimetan „tegevuspuudeks“, kõige rohkem LLVM-i IR-ga (vahepealne esitus).

Tegevuspuu ja abstraktse süntaksipuu vahel on peen, kuid väga oluline erinevus. Mul läks üsna kaua aega, et aru saada, et nende vahel peaks isegi erinevus olema (mis aitas kaasa parseri ümberkirjutamise vajadusele).

Tegevuspuu vs AST

Lihtsustatult öeldes on tegevuspuu kontekstiga AST. See kontekst on teave, näiteks mis tüüpi funktsioon tagastab, või see, et kaks muutuja kasutuskohta kasutavad tegelikult sama muutujat. Kuna see peab kogu selle konteksti välja mõtlema ja meelde jätma, vajab tegevuspuu genereeriv kood palju nimeruumi otsingu tabeleid ja muid asju.

Tegevuspuu käivitamine

Kui tegevuspuu on käes, on koodi käivitamine lihtne. Igal toimingusõlmel on funktsioon 'execute', mis võtab teatud sisendi, teeb kõik, mida tegevus peaks tegema (sealhulgas võimaliku alamtoimingu kutsumise) ja tagastab tegevuse väljundi. See on tõlk tegevuses.

Valikute koostamine

"Aga oota!" Kuulen, et ütlete: "Kas Pinecone ei peaks olema koostatud?" Jah see on. Kuid koostamine on raskem kui tõlgendamine. On paar võimalikku lähenemist.

Ehitage oma koostaja

See tundus mulle alguses hea mõte. Mulle meeldib ise asju valmistada ja mul on olnud kihvt ettekäände pärast, et montaaž oleks hea.

Kahjuks pole kaasaskantava kompilaatori kirjutamine nii lihtne kui iga keeleelemendi jaoks mõne masinakoodi kirjutamine. Arhitektuuride ja operatsioonisüsteemide arvu tõttu ei ole iga inimese jaoks praktiline kirjutada ristplatvormi kompilaatori taustaprogrammi.

Isegi Swifti, Rusti ja Clangi taga olevad meeskonnad ei taha selle kõigega ise vaeva näha, nii et selle asemel kasutavad nad kõik…

LLVM

LLVM on kompilaatori tööriistade kogu. Põhimõtteliselt on see teek, mis muudab teie keele kompileeritud käivitatavaks binaarseks. See tundus ideaalne valik, nii et hüppasin otse sisse. Kahjuks ei kontrollinud ma vee sügavust ja uppusin kohe.

Ehkki LLVM pole koostekeel kõva, on see hiiglaslik kompleksne teek. Seda pole võimatu kasutada ja neil on head õpetused, kuid mõistsin, et pean natuke harjutama, enne kui olen valmis sellega Pinecone kompilaatori täielikult juurutama.

Ümberlaadimine

Tahtsin mingit kompileeritud Pinecone'i ja tahtsin seda kiiresti, seega pöördusin ühe meetodi poole, mida teadsin, et suudan tööd teha: tõlkimist.

Kirjutasin C ++ transpilerisse Pinecone ja lisasin võimaluse väljundiallikat automaatselt kompileerida GCC-ga. Praegu töötab see peaaegu kõigi Pinecone'i programmide puhul (kuigi on mõned servajuhtumid, mis seda lõhuvad). See pole eriti kaasaskantav ega skaleeritav lahendus, kuid esialgu töötab.

Tulevik

Eeldades, et jätkan Pinecone'i arendamist, saab see varem või hiljem LLVM-i kompileerimise tuge. Ma kahtlustan, et pole materi, kui palju ma selle kallal töötan, transpiler ei ole kunagi täiesti stabiilne ja LLVM-i eelised on arvukad. Küsimus on lihtsalt selles, millal mul on aega LLVM-is mõned näidisprojektid teha ja sellest aru saada.

Seni on tõlk suurepärane triviaalsete programmide jaoks ja C ++ tõlkimine töötab enamiku suurema jõudlust vajavate asjade puhul.

Järeldus

Loodan, et olen muutnud teie jaoks programmeerimiskeeled natuke vähem salapäraseks. Kui soovite seda ise teha, soovitan seda tungivalt. Välja selgitamiseks on palju rakenduse üksikasju, kuid siinsest kontuurist peaks teie jätkamiseks piisama.

Siin on minu kõrgel tasemel nõuanded alustamiseks (pidage meeles, et ma ei tea tegelikult, mida ma teen, nii et võtke see koos soola teraga):

  • Kui teil on kahtlusi, minge tõlgendatuks. Tõlgendatud keeli on üldiselt lihtsam kujundada, ehitada ja õppida. Ma ei heiduta teid koostatud koopia kirjutamist, kui teate, et seda soovite teha, aga kui olete aia peal, siis tõlgendaksin.
  • Lekserite ja parserite osas tehke kõike, mida soovite. Enda kirjutamise poolt ja vastu on kehtivaid argumente. Lõpuks, kui mõtlete oma disaini läbi ja rakendate kõike mõistlikult, pole see tegelikult oluline.
  • Õpi torujuhtmest, milleni ma jõudsin. Praegu kasutatava torujuhtme projekteerimisel läks palju katseid ja vigu. Olen püüdnud kõrvaldada AST-d, AST-d, mis muutuvad paigaks tegevuspuudeks, ja muid kohutavaid ideid. See torujuhe töötab, nii et ärge muutke seda, kui teil pole tõesti head ideed.
  • Kui teil pole aega ega motivatsiooni keeruka üldotstarbelise keele rakendamiseks, proovige rakendada sellist esoteerilist keelt nagu Brainfuck. Need tõlgid võivad olla nii lühikesed kui mõnisada rida.

Mul on Pinecone'i arendamisel väga vähe kahetsust. Tegin sel teel mitmeid halbu valikuid, kuid olen suurema osa sellistest vigadest mõjutatud koodi ümber kirjutanud.

Praegu on Pinecone piisavalt heas seisukorras, et toimib hästi ja seda saab hõlpsasti parandada. Käbikirja kirjutamine on olnud minu jaoks tohutult hariv ja nauditav kogemus ning see on alles algus.