Kodprov 2018-12-11 (förmiddag)

Inlämning går till så här: ställ dig i katalogen kodprov181211. Om du har tappat bort dig i filsystemet kan du skriva cd; cd kodprov181211. 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.

Ponera två länkade listor (OBS! Utan dummies, vilket de kan ha i implementationen.) Figuren nedan visa före och efter anrop till list_merge(list1, list2).

Observera att “C” ligger kvar i samma länk, liksom “B” etc.

make compile kompilerar driver.c och yourcode.c till a.out.

make test kompilerar enligt make compile och kör sedan testerna.

make memtest kör testerna enligt make test under valgrind.

Testerna slår ihop två listor tre gånger, i tre olika test. Du måste själv läsa outputen och tolka den för att se om allt gick bra!

Här är ett exempel på ett test som passerar:

=========================== TEST START =================================
First random list 'a'
'[k, r, v]'
Second random list 'b'
'[g, q, x]'
Merging lists
Expecting size of 'a' to be zero
0 == 0 ... PASSED
Expecting size of 'b' to be sum of 'a' and 'b' before merge
6 == 6 ... PASSED
Expecting the output of 'a' to be []
'[]'
Expecting the output of 'b' to be all elements of 'a' and 'b' before merge in ascending order (e.g. a < b, b < c, etc.)
'[g, k, q, r, v, x]'
Checking that the links, not just elements were moved
... PASSED
=========================== TEST STOP ==================================

Som synes skapas två listor (samma skapas varje gång du kör testet!), i detta fall båda av längden 3, med unika data. Först skrivs listorna ut så vi ser vad som händer, sedan slås de ihop. Efter detta förväntar vi oss att \(a\) är tom, och att \(b\) har fått samtliga element. Sista testet kollar att det faktiskt är länkarna som flyttas över och inte enbart elementen.

1. Missa att det var länkarna som skulle flyttas över och bara flytta elementen
2. Förutsätta något om sorteringsordningen istället för att använda funktionspekarna
3. Ignorera sorteringen och bara konkatenera listorna
4. Blanda ihop listorna efter merge (båda listorna hade gemensamma länkar)
5. Missa att uppdatera last

Visar endast i linjär tid:

int list_size(list_t *list)
{
  int sum = 0;
  for (link_t *cursor = list->first; cursor->next; cursor = cursor->next)
    {
      ++sum;
    }
  return sum;
}

Lösningsförslaget loopar över listan l1 i den yttre loopen (for). Varje varv flyttas en länk från l1 över till l2. Pekaren prev_l2 används för att hitta föregående länk i l2 där länken från l1 skall in. Den inre loopen (while) används för att positionera prev_l2 korrekt.

Efter den inre loopen pekar prev_l1->next på den länk som skall flyttas över, och prev_l2->next är den plats dit länken skall flyttas.

void list_merge(list_t *l1, list_t *l2)
{
  /// Varje varv i loopen flyttas prev_l1->next över
  for (link_t *prev_l1 = l1->first; prev_l1->next;)
    {
      /// Bekvämt för jämförelsen i while-loopen
      void *element = prev_l1->next->element;

      link_t *prev_l2 = l2->first;

      /// Flytta prev_l2 till platsen innan där prev_l1->next skall stoppas in 
      while (prev_l2->next && l2->compare(prev_l2->next->element, element) < 0)
        {
          prev_l2 = prev_l2->next;
        }

      /// Låt link_l1 vara länken som skall flyttas
      link_t *link_l1 = prev_l1->next;

      /// Länka link_l1 ur l1
      prev_l1->next = link_l1->next;

      /// Länka in link_l1 i l2
      link_l1->next = prev_l2->next;
      prev_l2->next = link_l1;

      /// Uppdatera last-pekaren 
      if (prev_l2 == l2->last)
        {
          l2->last = link_l1;
        }
    }

    /// Uppdatera l1's last-pekare 
    l1->last = l1->first;
}  

Om vi hade haft amorterad list_size() hade vi också behövt följande kod:

l2->elements += l1->elements; /// Eftersom vi kunde utgå från inga dubletter 
l1->elements = 0; 

Denna uppgift bygger på AST-delen av den symboliska kalkylatorn (dvs. ingen parsning). Koden för ett abstrakt syntaxträd med följande konstruktioner är utdelad. Du kommer inte att behöva läsa och förstå den mesta av denna kod!

• Satser (Statement)
  • Tilldelning (Assigment), t.ex. x = 42 som tilldelar resultatet av ett uttryck till en variabel
  • Utskrift (Print), t.ex. print(3 + 5) som skriver ut resultatet av ett uttryck på terminalen
  • Variabeldeklaration (VariableDeclaration), t.ex. var x som anger att en variabel finns och kan tilldelas
  • Sekvenser (Sequence), t.ex. { var x; x = 42; print(x); } som grupperar satser separerade med ;, som kan evalueras i ett gemensamt environment
  • Uttryck enligt nedan
• Uttryck (Expression)
  • Variabler (Variable), t.ex. x
  • Addition (Addition) och subtraktion (Subtraction) t.ex. x + 4 och y + (2 - z)
  • Konstanter av heltalstyp (Integer)
  • Konstanten “bottom” (Bottom) som avser avsaknaden av ett värde (jmf. null)

Utöver dessa klasser finns ytterligare abstrakta klasser som ingår i en arvshierarki under Statement, samt klassen Environment som håller reda på variablers värden.

För enkelhets skull är dessa klasser deklarerade i två olika filer:

• ASTFixed.java – här ligger klasser som du INTE FÅR ändra i
• YourCode.java – här ligger klasser som du FÅR ändra i (detta är den enda fil som lämnas in!)

Testkod finns i Driver.java. OBS!!! Du behöver ändra på rad 12 i Driver.java för att köra testerna.

Nedan följer några exempel på valida “program” i form av sekvenser av statements, för tydlighets skull skrivna på olika rader. Följande program skriver ut “49” som sitt resultat.

var x;        // anger att variabeln x finns och har värdet "bottom"
var y;        // anger att variabeln y finns och har värdet "bottom"
var z;        // anger att variabeln z finns och har värdet "bottom"
x = 7;        
y = 42;
z = x + y;
print(z);

Följande program skriver ut “<bottom>” som sitt resultat. Analogt att printa null.

var z;        // anger att variabeln z finns och har värdet "bottom"
print(z);

Följande program skriver ut “A/An java.lang.RuntimeException was thrown (Bottom used as a value!)”. Analogt med att avreferera null.

var x;       // anger att variabeln x finns och har värdet "bottom"
var y;       // anger att variabeln y finns och har värdet "bottom"
print(x + y);

Följande program skriver ut “A/An java.lang.RuntimeException was thrown (Access to undeclared variable!)” eftersom z inte har deklarerats innan den användes.

print(z);

Uppgiften går ut på att utöka systemet med flyttalskonstanter i klassen Float som du måste skriva själv från grunden och i filen YourCode.java (varför klassen inte får vara publik!). Uppgiftens karaktär är “läsa mycket, skriva lite”. Du har ledning av existerande kod i alla delar av uppgiften.

1. Förutom numeriken (flyttal istf. heltal) skall flyttalskonstanter fungera som heltalskonstanter, dvs. de skall gå att skriva ut, de skall stöda addition och subtraktion, det skall gå att spara flyttal i variabler, etc.
2. Addition eller subtraktion mellan två flyttal eller ett heltal och ett flyttal skall returnera ett flyttal.

För att avgöra när du är klar finns några enkla tester som beskrivs nedan.

OBS! Du får inte använda instanceof i din lösning. Inte heller får du “lösa” problemet genom att generera och matcha strängar.

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. OBS!!! Du behöver ändra på rad 12 i Driver.java för att skapa flyttalskonstanter.

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.

Klassen java.lang.Number är superklass till klassen java.lang.Integer (bland annat). Du kan se hur den används i klassen Integer i ASTFixed.java och aritmetik-metoderna sub() och add() i Calculation i YourCode.java. Här är några metoder i klassen Number som kan vara av intresse.

• abstract double doubleValue() Returns the value of the specified number as a double.
• abstract float floatValue() Returns the value of the specified number as a float.
• abstract int intValue() Returns the value of the specified number as an int.
• abstract long longValue() Returns the value of the specified number as a long.
• short shortValue() Returns the value of the specified number as a short.

Utöver Calculation-klassen som var delvis delad med förmiddagns kodprov gick eftermiddagens kodprov ut på att lägga till en ny klass NumberConstant för numeriska konstanter. Eftersom den ärver av en klass för godtyckliga konstanten (t.ex. även strängliteraler) bestod en av svårigheterna i att inse att en numerisk konstant alltid har ett value som är ett Number. Så här kunde denna klass exempelvis implementeras:

abstract class NumberConstant extends Constant {
    /// TODO
    public NumberConstant(Number value) {
        super(value);
    }

    public Number value() {
        return (Number) super.value();
    }

    public int intValue() {
        return this.value().intValue(); 
    }

    public double floatValue() {
        return this.value().doubleValue(); 
    }
}

Observera att i och med att konstruktorn alltid tar in ett Number som argument vet vi att value() som finns i Constant-klassen kommer att returnera ett Number. Det möjliggör typomvandligen i value() vilket i sin tur möjliggör de smidigar implementationerna av intValue() och floatValue().

Mindre eleganta (i mitt tycke) lösningar som räknades som helt godkända var struntade t.ex. i att override:a value() och istället implementera ex. intValue() så här:

public int intValue() {
    return ((Number) this.value()).intValue(); 
}