ADUBA BLOG
Vi vill skapa ett retroprogrammeringsspel.
Ett programmeringsspel är när man låter två eller flera (i vårt fall mindre) datorprogram spela mot varandra. Konceptet är inte nytt och har funnits sedan 60-talet.
While och bytecode
Hej Alla!
Någon kanske har funderat över kopplingen mellan Adubakod och bytecode-instruktionerna som användes i det förra inläggets uppladdade källkod. Vi tänker använda WhileLoopTest()-metoden som finns där, för att visa de bakomliggande tankarna. I WhileLoopTest()-metoden kör vi följande Adubakod:
MODULE test; VAR i:INTEGER; BEGIN i := 0; WHILE i < 3 DO BEGIN i := i + 1; END END
Innan tittar på motsvarande bytecode-instruktioner måste vi reda ut några saker:
Var/hur lagrar man variabler?
Hur går det till när man beräknar uttryck?
Vi har löst baserat vårt exekveringssystem på ECMA-335 när vi har lekt med programkod (speciellt kapitel I.12 samt III.3). ECMA använder något som de kallar för Local Variable Array (LVA) för att lagra variabler. För vår del är det inget annan än ett fält (eng. array) som består av ValueType’s vilket är bastypen för en variabel. LVA är vår bas för lagring och det är där variabeln i kommer att finnas som ett element.
Ett enkelt sätt att utföra uttryck är att använda en stack och det är bra för vår motor är stackbaserad. ECMA kallar denna “beräkningsstack” för Evaluation Stack (ES). Vi använder ordet ‘stack’ i texten om inget annat anges. Det är via denna stack som vi t ex utför i < 3 och i + 1. Så, för att utföra i + 1 kommer innehållet av variablen i samt 1 att läggas på stacken varefter operatorn + hämtar dessa två stackelement och adderar dessa. Resultatet av additionen läggs sedan tillbaka på stacken.
Vi behöver en sak till och det är ett sammanhang för vår LVA och ES. Anledningen till detta är vi inte vill blanda samman egenskaper som är specifika för procedureanrop (även om det skulle gå, så gör detta hanteringen enklare). Detta sammanhang kallas för ‘Method State’ av ECMA och är alltså en samling av egenskaper som är till för hålla ordning på saker och ting när man exekverar ett anrop. Ytterligare egenskaper, annat än LVA och ES, som placeras där är t ex den aktuella instruktionspekaren.
Nu är vi framme vid instruktionerna och om ni tittar i ECMA’s kapitel III.3 så ser ni var inspirationen kommer ifrån. I varje instruktionsbeskrivning nedan finns följande delar:
En kort sammanfattning över vad instruktionen gör.
Eventuella parametrar.
Stackens utseende före och efter att instruktionen utförts. Den notationen finns beskriven i ECMA dokumentet kapitel III.1.3.
Listan av instruktioner som används för att köra Adubakoden ovan:
LdLoc (Load Location)
Ladda variabel till stacken (push).
Parameter: index i LVA där variabeln är lagrad.
Stack: … —> …, värde
StLoc (Store Location)
Hämta värde från stacken (pop) och lagra i variabel.
Parameter: index i LVA där variabeln är lagrad.
Stack: …, värde —> …
LdcInt (Load Constant Int)
Ladda heltalsvärde till/på stacken.
Parameter: Heltalsvärde.
Stack: … —> …, värde
Clt (Compare Less Than)
Utför värde1 < värde2. Om sant är resultat satt till 1, annars 0.
Stack: …, värde1, värde2 —> …, resultat
BrFalse (Break if false)
Hoppa till <instruktionsadress> om värdet på stacktoppen är 0.
Parameter: Instruktionsadress.
Stack: …, värde —> …
Br (Break)
Hoppa till <instruktionsadress>.
Parameter: Instruktionsadress.
Stack: … —> …
Add
resultat = värde1 + värde2.
Stack: …, värde1, värde2 —> …, resultat
Exit
Avsluta exekvering.
Äntligen, översättningen från Aduba till bytecode instruktioner. Nedanstående rader är uppdelade i fyra kolumner: den första är radnummer för att göra det lättare att hänvisa till i själva förklaringen, den andra är minnespositionens start för instruktionen, den tredje är själva instruktionen och slutligen den fjärde som är en kommentar. Variabeln i kommer att ligga på plats 0 i LVA och ES är tom när exekveringen startar.
Rad Pos Instruktion Kommentar =================================================================================== 1 00 LdcInt, 0 Lägg 0 på stacken. 2 02 StLoc, 0 Spara värdet på stacken i variabeln i. 3 04 LdLoc, 0 Lägg i’s värde på stacken. 4 06 LdcInt, 3 Lägg 3 på stacken. 5 08 Clt Utför i < 3 och lägg 1 på stacken om det är sant, annars 0. 6 09 BrFalse, 20 Om 0 ligger på stacken hoppa till instruktionen som har minnespos 20 7 11 LdLoc, 0 Här hamnar vi om i < 3 är sant. Lägg i’s värde på stacken. 8 13 LdcInt, 1 Lägg 1 på stacken. 9 15 Add Addera. 10 16 StLoc, 0 Spara värdet på stacken i variabeln i. 11 18 Br, 4 Hoppa till instruktionen på minnespos 4 (rad 3). 12 20 Exit Här hamnar man om i < 3 inte är sant.
Man kan också sammanfatta kopplingen mellan Adubakoden och instruktionerna så här:
BEGIN Rad 1-2 i:=0 Rad 3-6 WHILE i < 3 DO BEGIN Rad 7-10 i:=i+1; Rad 11 END Rad 12 END
En något kort förklaring, men det var det hela.
Är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå! Det viktiga är att vi har kul tillsammans!
Lek med rekursion och annat
Hej Alla!
Vi har lekt vidare och det finns några nya saker som är testade (i liten utsträckning):
while
rekursiva procedure-anrop
string som typ
Även en enklare disassembler finns med.
Sedan har vi ändrat i hur vi lägger till nya instruktioner i det fält som utgör den virtuella maskinens programminne. Tidigare så bestod detta fält av Instruction-instanser. Vi tog bort dessa instanser och istället finns det instruktionsidentifierare samt eventuella parametrar som element direkt i fältet. Det känns enklare.
Fält? Array på svenska.
Zip-fil med källkod finns att ladda ned härifrån.
Är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå! Det viktiga är att vi har kul tillsammans!
Crafting Interpreters
Hej Alla!
Det finns en bra webbplats som handlar om hur man förstår och skapar interpreterare samt virtuella maskiner här.
Eftersom planen är att använda ANTLR som parser och generator så kommer inte del II kanske till så stor nytta i sin helhet (men den är väl värd att läsa ändå). Del III är däremot intressantare, då den avhandlar virtuella maskiner på ett bra sätt.
Man kan köpa bokvarianten av webbplatsen, vilket jag gjort. Mest för att det passar mig bäst när jag läser. En sak som skiljer sig mellan boken och webbplatsen är att när programkod visas, så är bokens syntaxfärgning gråskalad medans webbplatsens är ‘färgad’.
Leker
Hej Alla!
Vi har lekt lite och det känns helt ok.
Vår tanke var att se hur det skulle kunna bli om man gjorde om följande Adubakod till VM instruktioner som vi sedan kör:
MODULE test; VAR r:REAL; PROCEDURE AddPi(someVal:REAL):REAL VAR retVal:REAL; BEGIN retVal := someVal + 3.14; RETURN retVal; END BEGIN r := System.Pow(System.Sqrt((5.0 + 3.0) / 2.0), 5.0); (* System library calls *) r := AddPi(r); WriteLn(r); END
Applikationens struktur är löst baserat på ECMA (se tidigare inlägg) kapitel I.12 samt III.3. Vi har också försökt använda begreppen från det dokumentet i källkoden där det lämpar sig, så förhoppningsvis går det att se kopplingarna mellan dem.
Läs också III.1.3, där förklaras hur man med enbart text beskriver hur stackens förändras när en instruktion utförs.
Applikationen är skapad med C# (.Net 7) och finns att ladda hem här som .zip-fil.
Vi är inte riktigt klara över vad som är nästa steg. Kanske fundera mer över hur olika Adubakonstruktioner översätts till motsvarande sekvens av VM instruktioner?
Som alltid, är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå. Det viktiga är att vi har kul tillsammans!
Virtuell maskin
Hej Alla!
Tanken med att göra sin egen virtuella maskin är, bland annat, att försöka få så hög kontroll över exekveringen av program som det är möjligt. Och för att det är intressant. Och för att se om vi kan 🙂
Vi har spanat lite på hur olika virtuella maskiner fungerar genom att studera andra maskiners dokumentation t ex:
Common Lanugage Infrastructure, ECMA 335 (.Net) --> Inledningsvis kapitel I6 och I12.
The Java Virtual Machine Specification --> Inledningsvis kapitel 1-2 samt 5.
Vi kan nog ta en del idéer från dessa två. Vi kanske kan känna oss för och leka lite med med motsvarande CLI’s evaluation stack och några instruktioner?
Som alltid, är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå. Det viktiga är att vi har kul tillsammans!
Oberon-07
Hej Alla!
Som vi nämnt tidigare så vill vi få med så många som möjligt som användare av Aduba.
Med det som bakgrund och det faktum att många jobbar aktivt i programmeringsfasen, så ligger det nära till hands att välja ett känt språk som vi utgår ifrån (läs: minimerar). Problemet med att minimera ett känt programspråk är att det nog skapar förväntningar på vad som ska vara med (vi har alla olika preferenser). Då är det kanske bättre att basera Aduba på något som de flesta inte känner till men känner igen sig i. En möjlighet är Oberon-07.
Upphovsperson i stort till Oberon-07 är en av de gamla hjältarna Niklaus Wirth. Att han funnits med sedan länge förstår man när man inser att han var deltagare i den kommité som tog fram Algol i början på 60-talet. Algol är urmodern till många av dagens språk, bland annat C, Java och Pascal. Den sistnämnda är via Modula en gammelmormor till Oberon. I rapporten “Modula-2 and Oberon” skriver Wirth “The principal guideline was to concentrate on features that are basic and essential and to omit ephemeral issues. ” och det märks då dess syntax får plats på en A4-sida. Med andra ord, den har allt som behövs men inget mer vilket förhoppningsvis gör det enklare för oss att implementera.
Några länkar:
- Allmänt om språket: http://oberon07.com/
- “The programming language Oberon”: https://people.inf.ethz.ch/wirth/Oberon/Oberon07.Report.pdf (Rapport över hur man tänker sig att språket fungerar.)
- “Modula 2 and Oberon”: https://people.inf.ethz.ch/wirth/Articles/Modula-Oberon-June.pdf
Som alltid, är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå. Det viktiga är att vi har kul tillsammans!
ANTLR
Hej Alla!
ANTLR (ANother Tool for Language Recognition) är ett verktyg för att skapa parsergeneratorer.
Den befinner sig på version 4 vilket känns bra, att landa i version 1 kan emellanåt ha sina baksidor. Verktyget har också bra hjälpmedel och dokumentation.
Själva grammatik-filen har liknande syntax som Lex och YACC, men då dessa verktyg genererar C/C++ har ANTLR ett större utbud av parserspråk. Bland annat Java, C# och Python.
Intressant är att det finns ett repository på github med grammatikfiler för en mängd olika programspråk, däribland Oberon-07. Då vi redan sneglat lite på det innan som en möjligt språk att utgå ifrån, laddade vi hem dess grammatikfil och körde den igenom ANTLR.
Vi testade med följande Oberon-07 nonsensprogram:
MODULE MyModule;
IMPORT
Out;
VAR
added:INTEGER;
i,j:INTEGER;
PROCEDURE add(i1:INTEGER; i2:INTEGER):INTEGER;
BEGIN
RETURN i1 + i2
END add;
BEGIN
Out.String("Hello!");
i := 32;
j := add(i, 4);
Out.Int(j);
END MyModule.Emellertid så blev det problem med skanningen av tal. Talet 32 ovan tolkades som först 3 och sedan 2, vilket resulterade i syntaxfel då i := 3 2; inte är korrekt. Efter att ha ändrat en aning i grammatikfilen (igenkänning av tal flyttades från produktion till lexikal) så fungerade det som vi ville.
Vi valde att generera en C# parser (.net 7) och nedanstående program är det som kördes för att testa nonsensprogrammet ovan:
using Antlr4.Runtime;
using Antlr4.Runtime.Tree;
string input = System.IO.File.ReadAllText(@".\oberonTest1.mod");
ICharStream stream = CharStreams.fromString(input);
ITokenSource lexer = new oberonLexer(stream);
ITokenStream tokens = new CommonTokenStream(lexer);
oberonParser parser = new oberonParser(tokens);
parser.BuildParseTree = true;
IParseTree tree = parser.module();
System.Console.WriteLine( tree.ToStringTree(parser));Utskriften från sista raden blir:
(module MODULE (ident MyModule) ; (importList IMPORT (import_ (ident Out)) ;) (declarationSequence VAR (variableDeclaration (identList (identdef (ident added))) : (type_ (qualident (ident INTEGER)))) ; (variableDeclaration (identList (identdef (ident i)) , (identdef (ident j))) : (type_ (qualident (ident INTEGER)))) ; (procedureDeclaration (procedureHeading PROCEDURE (identdef (ident add)) (formalParameters ( (fPSection (ident i1) : (formalType (qualident (ident INTEGER)))) ; (fPSection (ident i2) : (formalType (qualident (ident INTEGER)))) ) : (qualident (ident INTEGER)))) ; (procedureBody declarationSequence BEGIN (statementSequence statement) RETURN (expression (simpleExpression (term (factor (designator (qualident (ident i1))))) (addOperator +) (term (factor (designator (qualident (ident i2))))))) END) (ident add)) ;) BEGIN (statementSequence (statement (procedureCall (designator (qualident (ident Out) . (ident String))) (actualParameters ( (expList (expression (simpleExpression (term (factor "Hello!"))))) )))) ; (statement (assignment (designator (qualident (ident i))) := (expression (simpleExpression (term (factor (number (integer 32)))))))) ; (statement (assignment (designator (qualident (ident j))) := (expression (simpleExpression (term (factor (designator (qualident (ident add))) (actualParameters ( (expList (expression (simpleExpression (term (factor (designator (qualident (ident i))))))) , (expression (simpleExpression (term (factor (number (integer 4))))))) )))))))) ; (statement (procedureCall (designator (qualident (ident Out) . (ident Int)) (selector ( (qualident (ident j)) ))))) ; statement) END (ident MyModule) .)
Ljuv musik :)
Till nästa gång funderar vi troligen på det tänkta programspråket.
Som alltid, är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå. Det viktiga är att vi har kul tillsammans!
Aduba
Aduba intro
Hej Alla!
Efter vårt Aduba-webinar den 14 september har några kanske ställt sig frågan: varför finns Aduba?Jo, det här är ett feelgoodprojekt där vi försöker skapa ett minimalt programmeringsspel. Vi gör det också för att vi är nyfikna på konceptet och för att vi vill.
Sen finns det fler värden, när programmeringsspelet är (tillräckligt) klart så kan vi spela mot varandra. Vare sig du varit med att skapa spelet eller inte!
Vi vill också att de som är med och spelar inte behöver ha programmering som sin huvudsyssla. Det här sätter möjligtvis också vilkor på utformingen av programspråket som man konstruerar sina alster med. Ett programspråk som är tydlig i sin utforming och som är enkelt för oss att implementera. Vi tror inte att den behöver vara optimalt implementerad, då vi tror att spelprogrammen som skapas kommer att vara “mindre”.
Ett sådant programspråk som vi kan utgå och ta delar i från är t ex Oberon-07.
Det finns en del verktyg för att skapa kompilatorer för ett språk. Några av er kanske känner till gamla hederliga LEX/YACC eller motsvarande GNU-varianten Flex/Bison. Det finns några andra generatorer bland annat ANTLR som är modernare i sitt snitt. Vi kommer att kika lite på den till nästa gång.
Som ni märker är vi i en “känner oss för” fas där vi letar efter och testar saker. Det finns inget som är ristat i sten.
Är det någon som vill vara med och skapa Aduba så är ni ypperligt välkomna oavsett kunskapsnivå! Det viktiga är att vi har kul tillsammans!