Dugga 2 i TDP007 torsdag 13 mars 2014 kl 15.15-17.00 ------------------------------------------------------- Duggan startar kl. 15:15 och pågår till 17:00. Ni kommer att få köra på begränsade datortentakonton. 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 kommandot acroread. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså fyra filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Duggan består av fyra uppgifter (några indelade i deluppgifter) som totalt kan ge 25 poäng. Dessa poäng summeras ihop med poängen från den första duggan. Uppgift 1: Teorifrågor (7p) --------------------------- a) Vad är en lexer (del av en parser) och hur fungerar den i grova drag? (1p) b) Nämn två egenskaper hos Ruby som kan göra det lättare att implementera interna domänspecifika språk och förklara varför. (2p) c) Ge två exempel på områden eller tillfällen där man skulle kunna vilja använda ett domänspecifikt språk och förklara vilken nytta man skulle ha av det. (2p) d) Under en av föreläsningarna tittade vi på en generell problemlösare som med hjälp av coninuations implementerade backtracking. Vad är poängen med att använda den istället för att bara ställa upp ett antal for-loopar för att hitta rätt svar? (2p) Uppgift 2: Constraint-nätverk (6p) ---------------------------------- 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 3: DSL (6p) ------------------- 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 4: Parsning (6p) ------------------------ I den här uppgiften ska vi använda parsern från filen rdparse.rb för att läsa in en kalender. Informationen i kalendern ligger lagrad i vanlig text och ett exempel finns i filen calendar.txt som innehåller följande: - 6 mars 2014 - 08.15-10.00 'Labb, SU02' 10.15-12.00 'Föreläsning, A2' 13.15-15.00 'Seminarium, D31' - 7 mars 2014 - 10.00-11.00 'Möte med Anders' 12.00-13.30 'Lunch med Lisa' Uppgiften är att, med utgångspunkt från exemplet DiceRoller, skriva en enkel parser för kalenderdata. (Just detta exempel skulle antagligen ha varit enklare att läsa in med t.ex. reguljära uttryck, men den här gången ska vi använda vår parser.) Vi vill att det i slutändan ska fungera så här: >> c = Calendar.new => # >> c.read_meetings("calendar.txt") => [["Labb, SU02", 2014-03-06 08:15:00 +0100, 2014-03-06 10:00:00 +0100], ["Föreläsning, A2", 2014-03-06 10:15:00 +0100, 2014-03-06 12:00:00 +0100], ["Seminarium, D31", 2014-03-06 13:15:00 +0100, 2014-03-06 15:00:00 +0100], ["Möte med Anders", 2014-03-07 10:00:00 +0100, 2014-03-07 11:00:00 +0100], ["Lunch med Lisa", 2014-03-07 12:00:00 +0100, 2014-03-07 13:30:00 +0100]] Metoden read_meetings() som anropas ovan använder sig av parsern för att tolka innehållet i filen och returnera en datastruktur som innehåller kalenderinformationen. I lösningen ovan har vi lagrat start- och sluttid för respektive händelse i Time-objekt, men det är inte nödvändigt. Man kan även tänka sig egengjorda klasser, men de ska i så fall innehålla motsvarande information.