Datortentamen i TDP007 fredag 17 mars 2017 08:00-12:00 ------------------------------------------------------- Tentan startar kl. 08:00 och pågår till 12:00. Ni kommer att få köra på begränsade datortentakonton, precis som under duggan. Instruktioner för att logga in på dessa lämnas i salen. Alla filer som ni behöver för att lösa uppgifterna finns i hemkatalogen när ni har loggat in. Där finns också en PDF-version av en tidig utgåva av kursboken som ni gärna får använda er av. Öppna den med t.ex. kommandot xpdf. Under tentan kommer ni också att kunna komma åt ruby-doc.org och rubular.com för att kunna kolla upp och testa saker. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså sex filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Tentan består av sex uppgifter, några indelade i deluppgifter, som totalt kan ge 32 poäng. För godkänt krävs 50%, dvs minst 16 poäng. För betyg 4 krävs minst 21 poäng och för 5 minst 26 poäng. Inga poäng från duggor kan räknas tillgodo, utan tentan bedöms helt på egen hand. Om man redan har fått ett betyg genom duggan eller tidigare tentor kan det aldrig sänkas, bara höjas. Uppgift 1: Teorifrågor (5p) --------------------------- a) Om man kör följande Ruby-program, varför skriver det ut att a är 45 och inte 73? (1p) def sub a = 73 yield end def main a = 45 sub { puts "a = #{a}" } end main b) I Ruby kan man utöka ett enskilt objekt med nya metoder (som alltså inte är tillgängliga för andra objekt av samma klass). Vilka för- och nackdelar kan finnas med den möjligheten? (2p) c) När ska man använda strömparsning och när ska man använda trädparsning? Ge ett exempel på användningsområde och förklara kort varför den ena metoden skulle kunna vara bättre. (2p) d) Vad är ett domänspecifikt språk? Vad kan man hoppas uppnå genom att skapa ett sådant? (2p) Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- Norrboda universitet har en lärplattform som heter Nosam. Den kan generera olika typer av loggar som talar om vad lärare och studenter gör i systemet. Ett exempel på en sådan loggfil finns i auditlog_TJMP75.csv som är en semikolonseparerad textfil. Första raden i filen anger namnet på varje kolumn. Varje rad i resten av loggfilen representerar att en person har hämtat en viss resurs från en kurswebb. Vi vill ha hjälp att analysera den här loggfilen. Mer specifikt vill vi ha en generell metod som kan kolla hur många gånger olika värden finns i en angiven kolumn. Om man anger fältet "Dokumentplats" från exempelfilen ska metoden alltså kolla vilka olika värden som finns i den kolumnen och för varje värde räkna hur många gånger det förekommer. Sedan vill vi att metoden ska skriva ut de N högsta värdena, där N är ett tal som vi skickar in. Det är nog enklare att förklara med ett exempel. Så här skulle det kunna funka: >> la = LogAnalyzer.new("auditlog_TJMP75.csv") ... >> la.top("Dokumentplats",10) 8 sites/TJMP75/TJMP75-2017VT/Sidor/Material/Contoso Quality Review 2.pdf 8 sites/TJMP75/TJMP75-2017VT/Sidor/Material/Contoso Quality Review 1.pdf 9 sites/TJMP75/TJMP75-2017VT/Sidor/Material/Contoso_Dev_Str.pdf 14 sites/TJMP75/TJMP75-2017VT/Sidor/Material/Contoso Agile Manifesto.pdf 54 sites/TJMP75/TJMP75-2017VT/Sidor/Föreläsningar/Workshop 1 - How to form teams.pdf 80 sites/TJMP75/TJMP75-2017VT/CourseDocuments/KursinformationTJMP75 2017 final.pdf 89 sites/TJMP75/TJMP75-2017VT/CoursePlan/KursinformationTJMP75 2017 final.pdf 171 sites/TJMP75/TJMP75-2017VT/Sidor/Föreläsningar/FÖ1 Kursintroduktion TJMP75 2017N.pdf 195 sites/TJMP75/TJMP75-2017VT/Sidor/Material/INLÄMNINGSUPPGIFTER TJMP75 vt 2017.pdf 197 sites/TJMP75/TJMP75-2017VT/Sidor/Material/Gantt_Schema_beskrivning.pdf >> la.top("Användar-ID",5) 30 Per Arja 34 Marcus Wallin 45 Lisa Ahl 74 Iman Sandberg 90 Systemkonto Körexemplet svarar alltså först på frågan "Vilka dokument har laddats ner flest gånger?" och därefter på frågan "Vilka personer har gjort flest antal nedladdningar?". (All information i filen är givetvis fejkad och alla eventuella likheter med verkligheten är helt slumpmässiga.) Lösningen behöver inte nödvändigtvis bestå av en klass, som i exemplet, så länge man kan fråga efter en sammanställning på vilken kolumn som helst (och då alltså inte bara på kolumnerna just i den här filen, utan i vilken fil som helst som är semikolonseparerad). Uppgift 3: XML (6p) ------------------- Lille Timmy är tolv år och går i Big Rock Elementary School som ligger någonstans i Texas. Varje dag äter Timmy lunch i skolans cafeteria, där det finns 3-5 olika hälsosamma rätter att välja mellan. Timmy tycker att det är svårt att välja, så därför vill hans mamma Christy gärna hjälpa honom. Christy jobbar för ett multinationellt programvaruföretag och tänker att det bästa sättet att hjälpa sin son är att skriva ett program som väljer åt honom. Tyvärr har hon händerna fulla av företagets nästa stora och viktiga release, så hon vill istället att du ska skriva programmet. Just nu är hon väldigt mycket inne på Ruby, och behändigt nog publicerar skolan lunchmenyn i XML-format. I filen menu.xml återfinns lunchmenyn för några dagar i oktober. Varje dag finns det 3-5 rätter att välja mellan, och förutom namnet på rätten finns även kaloriinnehållet angivet. Christy vill nu att du ska skriva två alternativa program för att hitta på vad lille Timmy ska välja. a) (4p) Skriv en funktion choose1 som givet en XML-fil som är strukturerad på samma sätt som menu.xml skriver ut en lista med förslag på vad man borde äta varje dag. Funktionen choose1 ska ha strategin att hela tiden ta nästa nummer på listan. Man börjar med val 1 första dagen, går vidare till val 2 nästa dag, osv. Kommer man till ett nummer som inte finns på den aktuella dagen så börjar man om från början på 1. Utskriften från funktionen ska se ut så här: >> choose1("menu.xml") Monday 1. Soft Pretzels and Cheese Tuesday 2. Cheeseburger on a Bun Wednesday 3. Chicken Caesar Salad Thursday 4. Corn Dog on a Stick Friday 1. Stuffed Crust Pizza Monday 2. Cheeseburger on a Bun ... b) (2p) Skriv en funktion choose2 med samma förutsättningar som ovan, men med strategin att alltid välja den rätt som har högst kaloriangivelse. Utskriften från denna funktion ska även inkludera kalorivärdet och se ut så här: >> choose2("menu.xml") Monday 2. Chicken Patty on a Bun (550) Tuesday 1. Little Caesar's Pizza (540) Wednesday 4. BBQ Pork on a Bun (535) Thursday 2. Lasagna with Garlic Toast (505) ... Uppgift 4: DSL (5p) ------------------- Många system lagrar information i relationsdatabaser som man typiskt ställer frågor till med språket SQL. Ett alternativt sätt att lagra enklare typer av information är så kallade 'triple stores' eller 'RDF stores' (efter standarden Resource Description Framework). Grundtanken med 'triple stores' är ganska enkel. Man lagrar information i form av egenskaper som knyter samman två olika objekt. Om jag vill uttrycka att Stockholm är en stad i Sverige och att Stockholm dessutom är huvudstad kan jag uttrycka det så här: city 'Stockholm', 'Sweden' capital 'Stockholm', 'Sweden' På den första raden finns egenskapen 'city' som knyter samman en stad och ett land. På den andra raden finns egenskapen 'capital' som knyter samman en huvudstad med ett land. Det är bara information som kan tredelas på detta sätt som kan lagras i ett triple store, men begränsningen gör att man kan optimera dem ganska kraftigt. I denna uppgift ska du skapa ett mycket enkelt 'triple store' som kan läsa in information på formatet ovan från en textfil. I filen triples.rb finns ovanstående exempel med några ytterligare egenskaper. Du ska betrakta innehållet i textfilen som ett litet domänspecifikt språk och behandla det därefter. Tanken är att din inläsningsrutin ska köra filen, och att den ska kunna hantera vilka egenskapsnamn som helst, inte bara de som finns i just denna fil. Ditt 'triple store' ska även kunna svara på frågor från användaren. Det ska fungera så här: >> ts = TripleStore.load('triples.rb') # >> ts.find('capital','Stockholm','Sweden') [["Stockholm", "Sweden"]] >> ts.find('population','*','Sweden') [[9600000, "Sweden"]] >> ts.find('city','*','France') [["Nice", "France"], ["Paris", "France"], ["Lyon", "France"]] Första anropet till find kollar om Stockholm verkligen är huvudstad i Sverige. Eftersom det är sant får vi tillbaka en array med ett par i. (Om svaret hade varit falskt hade vi fått en tom array.) Nästa anrop har '*' som argument. Det innebär att find ska matcha alla möjliga värden som andra argument, även om det i just detta fall bara fanns ett svar. Tredje anropet visar dock ett exempel där det finns fler svar. Specialargumentet '*' ska kunna skickas in som andra eller tredje argument till find. Uppgift 5: Deklarativ programmering (5p) ---------------------------------------- I filen constraint_networks.rb finns de restriktionsnät som vi arbetat med under föreläsningar och seminarier. Din uppgift är att konstruera en ny constraint som kan slå ihop två strängar till en. Vi tänker oss att denna nya constraint tar två indata-strängar, a och b, och som resultat ger en utdata-sträng c som är en sammanslagning av dessa två strängar. Om vi har skapat tre "connectors" och satt ihop dessa med hjälp av vår nya constraint borde vi kunna skriva så här: >> a.user_assign("foo") => "ok" >> b.user_assign("bar") => "ok" >> c.value == "foobar" => true Vår nya constraint ska fungera åt båda hållen. Om vi t.ex. känner till värdet på a och c bör vi kunna räkna ut värdet på b. Förutom att konstruera en constraint ska du också skapa ett antal lämpliga och heltäckande testfall. Uppgift 6: Parsning (6p) ------------------------ En grundskola vill ha ett enkelt system för att träna elever att räkna på engelska. Vi ska bara använda talen 0 till 20 och bara operationerna plus och minus. Tanken är att eleverna ska skriva in meningar på engelska och få svar uträknade. I princip kan man göra två saker: räkna ut vad någonting blir eller göra en jämförelse. Följande körexempel illustrerar allt man kan göra: >> np=NumberParser.new => # >> np.log(false) => 2 >> np.repl [NumberParser] one plus two => 3 [NumberParser] two plus three is five => yes [NumberParser] four minus three is greater than four => no [NumberParser] one plus one plus one => 3 [NumberParser] one minus two is negative one => yes [NumberParser] negative three plus three is zero => yes Resultaten av en beräkning ska vara ett tal (med siffror) och resultatet av en jämförelse ska vara antingen 'yes' eller 'no'. Man kan använda negativa tal genom att skriva 'negative' framför. Vad som händer om man råkar gå utanför intervallet -20 till +20 är odefinierat, d.v.s. det spelar ingen roll. Grammatiken för det här lilla språket ser ut så här: VALID ::= EXPR | COMP EXPR ::= NUMBER | EXPR plus EXPR | EXPR minus EXPR COMP ::= EXPR is EXPR | EXPR is less than EXPR | EXPR is greater than EXPR NUMBER ::= NUM | negative NUM NUM ::= one | two | three | ... | twenty Din uppgift är att, med utgångspunkt från exempelparsern i filen rdparse.rb, konstruera en parser för den här begränsade delen av engelska språket. Observera att reglernas ordning - både i lexern och parsern - kan spela roll! Om du vill får du utöka språket, men inte på ett sätt som gör uppgiften lättare. Omvandligen mellan tal som strängar ('one', 'two', etc) och siffror (1, 2, etc) gör du lämpligen inte i parserreglerna. Det är dock helt okej att ha en hårdkodad tabell.