Kodprov 2019-01-14

Inlämning går till så här: ställ dig i katalogen kodprov190114. Om du har tappat bort dig i filsystemet kan du skriva cd; cd kodprov190114. Nu kan du skriva make handin för att lämna in kodprovet. När du kör detta kommando skapas en zip-fil med de filer som du har uppmanats att ändra i (inga andra), och denna fil sparas sedan på en plats där vi kan rätta provet. Vid behov kan du köra make handin flera gånger – endast den sista inlämningen räknas.

Den automatiska rättningen kommer att gå till så att vi kör dina inlämningar mot omfattande testfall. Du har fått ut mindre omfattande testfall eller motsvarande i detta prov som du kan använda som ett stöd för att göra en korrekt lösning. Experiment med att lämna ut mer omfattande tester har visat sig skapa mer stress än hjälp (tänk fler testfall som fallerar)¹.

Om du har löst uppgifterna på rätt sätt och testfallen som du får ut passerar är du förhoppningsvis godkänd.

• Samma regler som för en salstenta gäller: inga mobiltelefoner, inga SMS, inga samtal med någon förutom vakterna oavsett medium.
• Du måste kunna legitimera dig.
• Du får inte på något sätt titta på eller använda gammal kod som du har skrivit.
• Du får inte gå ut på nätet.
• Du får inte använda någon annan dokumentation än man-sidor och böcker.
• Det är tillåtet att ha en bok på en läsplatta, eller skärmen på en bärbar dator. Inga andra program får köra på dessa maskiner, och du får inte använda dem till något annat än att läsa kurslitteratur.
• Du måste skriva all kod själv, förutom den kod som är given.
• Du får använda vilken editor som helst som finns installerad på institutionens datorer, men om 50 personer använder Eclipse samtidigt så riskerar vi att sänka servrarna.

Vi kommer att använda en blandning av automatiska tester och granskning vid rättning. Du kan inte förutsätta att den kod du skriver enbart kommer att användas för det driver-program som används för testning här. Om du t.ex. implementerar en länkad lista av strängar kan testningen ske med hjälp av ett helt annat driver-program än det som delades ut på kodprovet.

I mån av tid har vi ofta tillämpat ett system där vi ger rest för mindre fel. Det är oklart om detta system tillämpas för detta kodprov men det betyder att det är värt att lämna in partiella lösningar, t.ex. en lösning som har något mindre fel.

Uppgiften går ut på att skriva klart implementationen av en treemap som finns i filen yourcode.c.

Du skall skriva all kod i filen yourcode.c. Filen treemap.h innehåller signaturerna för alla publika funktioner som skall finnas i yourcode.c samt dokumentation för hur de olika funktionerna skall fungera. Det finns markeringar av typen /// TODO i filen som beskriver vad du skall göra.

Du kan förutsätta att NULL inte används som ett värde.

• Du måste implementera hela programmet från grunden.
• Du får inte läcka minne eller läsa utanför initierat minne.
• Du skall skriva all din kod i yourcode.c som är den enda fil som lämnas in!

• make compile kompilerar yourcode.c mot testerna.
• make test kör testerna.
• make memtest kör testerna i valgrind för att hitta eventuella minnesfel.

Din uppgift är att utöka AST-trädet med en ny sats: IfThenElse, motsvarande en if-sats i C eller Java. En IfThenElse-nod har tre attribut, ett expression, guard, samt två statements, thenBody och elseBody. En IfThenElse-nod evalueras enligt följande:

1. Först evalueras guard i det aktuella scopet
2. Om guard evalueras till ett värde som inte är noll evalueras thenBody i ett nytt scope
3. Annars evalueras elseBody i ett nytt scope
4. Sist returneras Bottom

Att evaluera något i det aktuella scopet betyder att det evalueras med det environment som skickades in till dess eval()-metod. Nu följer en förklaring av vad som avses med att evalueras i ett nytt scope. Vi börjar med ett exempel i C:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  int x = 42; /// yttre x deklareras
  printf("before: %d\n", x);
  if (rand() % 2 == 1) { /// thenbody
    x++;
    int x = 0; /// inre x deklareras 
    x++;
    printf("thenBody: %d\n", x);
  } else { /// elsebody
    x++;
    printf("elseBody: %d\n", x);
  }
  printf("after: %d\n", x);

  return 0;
}

Om rand() % 2 == 1 ovan är true kommer vi att köra “thenbodyn”, dvs. det första blocket. Följande resultat syns då vid körning:

before: 42
thenBody: 1
after: 43

Vi kan se att x från början avser “yttre” x, men efter att vi introducerat det “inre” x med int x = 0 ändras det så att x sedan avser det “inre” x. När vi når slutet av “thenbodyn” försvinner alla variabler deklarerade där, dvs. “inre” x försvinner. När vi når den sista utskriften avser x den “yttre” x igen.

Om rand() % 2 == 1 ovan är false kommer vi att köra “elsebodyn”, dvs. det andra blocket. Då finns bara den “yttre” x-variabeln. Resultat av körningen:

before: 42
elseBody: 43
after: 43

Observera att detta scope-beteende skiljer sig något från Inlupp 4 år 2018.

Att evaluera något i ett nytt scope betyder helt enkelt att vi skall använda ett nytt environment! Dock kan vi inte helt kasta bort det gamla environmentet, eftersom koden kanske vill läsa eller skriva till variabler i det gamla environmentet. Om env är det aktuella environmentet betyder det att vi kan evaluera thenBody enligt följande: this.thenBody.eval(new Environment(env)).

För att implementera stöd för scopes kan vi följa denna enkla design: Utöka Environment med en next-pekare så att varje environment effektivt blir en länkad lista av minst ett Environment. Sedan ändrar vi hasVariable(), updateVariable() och readVariable() så att de först kollar igenom det första environmentet i listan, och om variabeln inte finns går de vidare och kollar på nästa environment. När vi skall evaluera thenBody, t.ex. skapar vi först sålunda ett nytt tomt environment med det existerande environmentet som next och använder detta nya environment för anropet till eval() på thenBody.

För att underlätta felsökning finns ytterligare en ny sats: dump(). Denna sats skriver ut innehållet i ett environment så att nästlade scope blir synliga. Inre scopes skrivs ut nästlade i yttre, t.ex. Scope{ Scope{ x => 2 } , x => 1 }.

Kompilera med make compile som kompilerar alla källkodsfiler och lägger resultatet i underkatalogen classes. För enkelhets skull finns inga paket.

Kör ditt program med make run.

Testa att ditt program ger rätt output med make test. Testerna är implementerade genom att programmets utdata stämmer överens med förväntat utdata som ligger i filen expected_output.txt. Om du vill stoppa in spårutskrifter i ditt program för så kallad “println debugging”, gör då det med System.err.println(...) så att testerna inte tolkar spårutskrifterna som en del av testresultaten.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, ran by Tobias Wrigstad.