Uppgifter för dugga 2 i TDP007 2011-03-11
-----------------------------------------
Uppgift 1: Teorifrågor (5p)
---------------------------
a) Vad menas med begreppet token (i parser-sammanhang)? (1p)
b) Vad är ett domänspecifikt språk? Vad kan man hoppas uppnå genom att
skapa ett sådant? (2p)
c) I uppgift 3 längre ner i duggan ska man hitta alla möjliga kombinationer
med hjälp av problemlösaren i filen amb.rb. Vad är poängen med att använda
den istället för att bara sätta upp en massa for-loopar eller liknande? (2p)
Uppgift 2: Domänspecifika språk (5p)
------------------------------------
Elinor arbetar på ett företag som utvecklar affärssystem, alltså programvara
som företag använder för att hålla ordning på allt, t.ex. lager, fakturor,
beställningar, kassakvitton. Deras programvara är utvecklad i Ruby. Varje
företag som installerar deras system måste konstruera en fil med inställningar
som innehåller olika basuppgifter om företaget. I version 2.3 ser den här
filen ut så här:
company: Lennarts ostlager AB
store: Ost-Lennart
manager: Lennart Abrahamsson
greeting: Välkommen åter önskar Lennart med medarbetare!
Elinor har nu läst en del om domänspecifika språk och kommit fram till att
det vore jättebra att ändra på de här inställningsfilerna inför version 3.0.
Hon vill att man ska betrakta inställningsfilen som ett domänspecifikt språk.
Hennes tanke är att man med rätt små modifikationer kan skriva så här istället:
company "Lennarts ostlager AB"
store "Ost-Lennart"
managerfn "Lennart"
managersn "Abrahamsson"
greeting "Välkommen till #{store} önskar #{managerfn} med medarbetare!"
manager "#{managerfn} #{managersn}"
Som man ser i exemplet kan man återanvända inställningar längre ner,
eftersom det här i praktiken är någon slags anpassad Ruby-kod.
Elinor vill i slutändan att det ska funka ungefär så här:
>> c=Configuration.load("config.rb")
=> ...
>> c.manager
=> "Lennart Abrahamsson"
Konstruera klassen Configuration som kan läsa in den här typen av (nya)
konfigurationsfiler och lagra informationen i attribut. För full poäng ska
du konstruera en lösning som klarar av vilka inställningar som helst.
För halva poängen kan du istället välja att göra en lösning som enbart funkar
med de inställningar som finns i exemplet ovan.
Uppgift 3: Icke-deterministisk programmering (5p)
-------------------------------------------------
Georg Stenåker arbetar med att sätta ihop musiklistor till radiokanalen
Max Megatönt som spelar den sämsta blandningen av gamla och ännu äldre
låtar. I filen playlist.txt finns en lista med ett antal låtar som han
har valt ut som möjlig utfyllnad i ännu ett helt meningslöst radioprogram.
Han vill välja ut fyra olika låtar av dessa. För att få en blandning vill
han dessutom att varje låt ska komma från ett annat årtionde än låten som
kommer omedelbart innan. På hur många sätt kan man välja ut fyra låtar
från denna lista enligt dessa förutsättningar?
Lös problemet genom att först skriva en funktion som läser in låtlistan
på valfritt sätt. Använd därefter problemlösaren i filen amb.rb för att
hitta alla möjliga kombinationer.
Uppgift 4: Constraint-nätverk (5p)
----------------------------------
a) Monica, som driver företaget Monicas Handelsträdgård, ska sätta en
massa lökar för att driva upp amaryllis (en stor klockliknande blomma
som folk gärna köper till jul). Leverantören av lökarna hävdar att
höjden på växterna beror på hur tätt man sätter dem. Han har till
och med en matematisk formel som säger hur höga de blir:
h(x) = 5 + 3x - x^2
I den här formeln är x hur tätt lökarna sitter, och om man räknar ut
formeln får man ut hur hög varje växt kommer bli. Monica vill ju gärna
räkna ut det här, men matte är inte riktigt hennes favoritgrej.
Hon vill istället att du ska bygga ett constraint-nätverk för den
här formeln, så att hon kan testa den lite lättare.
Alltså, med utgångspunkt från koden i constraint_networks.rb, bygg
upp ett constraint-nätverk som motsvarar den här formeln. (Koden är
behäftad med samma fel som koden inför seminarie 4, men det behöver
inte påverka lösningen, och du behöver inte korrigera koden.) (3p)
b) Monica är väldigt intresserad av hur höga blommorna kan bli som mest,
och vad det optimala avståndet mellan plantorna är. Hon vill att du
ska skriva en funktion som testar det här constraint-nätverket och
provar lite olika värden tills den hittar det största. (2p)
Den metod som hon föreslår är följande:
Börja räkna ut vad h(x) blir för något bra startvärde på x. Pröva sedan
att öka x lite grann och se om h(x) blir större. Om det blir större är vi
på rätt väg och kan fortsätta att öka x lite grann. I annat fall backar
vi tillbaka och försöker öka x lite mindre istället. Så där fortsätter
man tills det steg som man ökar x med i varje omgång har blivit så litet
att man är nöjd.
Omvandlat till någon slags pseudokod kan det se ut så här:
1) Börja testa med x=1 och steg=1. Spara värdet av h(x).
2) Om steg är tillräckligt litet är vi klara.
3) Annars ökar vi x med steg och kollar vad h får för värde för x+steg.
Är det större än det förra, sparade värdet på h?
3a) Ja. Spara det här nya h-värdet och gå tillbaka till punkt 2.
3b) Nej. Backa tillbaka genom att minska x med steg. Halvera sedan
steg och försök igen på punkt 2.
Uppgift 5: Parsning (5p)
------------------------
Det rykande färska språket STRIMLA (String Manipluation Language) är ett
enkelt interpreterat språk för att manipulera textsträngar på olika sätt.
Ett uttryck i STRIMLA kan se ut på fem olika sätt, vilket illustreras med
följande exempel:
[Hejsan] En enkel sträng anges med hakparenteser och den kan
innehålla i princip vad som helst, förutom hakparenteser.
3x[banan] Detta skapar en sträng som innehåller banan tre gånger,
d.v.s. "bananbananbanan".
2#[abc] Flyttar respektive tecken två steg framåt, d.v.s.
resultatet är "cde". (Lös detta på enklast möjliga
valfria sätt. Det behöver inte nödvändigtvis wrappas på
något snyggt sätt heller.)
[foo]&[fie] Slår ihop två strängar, d.v.s. "foofie".
(2x[oh])&[hai] Parenteser kan användas för att bestämma prioriteten.
I det här fallet blir resultatet "ohohhai".
Alternativt skulle man kunna uttrycka syntaxen med en BNF-regel så här:
EXPRESSION ::= STRING
| INTEGER 'x' EXPRESSION
| INTEGER '#' EXPRESSION
| EXPRESSION '&' EXPRESSION
| '(' EXPRESSION ')'
Alla strängar måste omges med hakparenteser. Talet som står framför 'x'
måste vara positivt, medan talet som står framför '#' även kan vara negativt.
Din uppgift är att, med utgångspunkt från parsern i rdparse.rb, konstruera
en parser för STRIMLA som kan hantera det språk som beskrivs ovan. Språket
får inte utökas på något sätt som gör parsern enklare. Följande exempel
visar hur det kan se ut:
irb(main):189:0> StrimlaParser.new.repl
[STRIMLA] 4x[boom]
=> boomboomboomboom
[STRIMLA] [I haz a ]&[pony!]
=> I haz a pony!
[STRIMLA] (2x[HEJ ])&[MON]&-1#[JDB]
=> HEJ HEJ MONICA