UU/IT/Inl�mningsuppgift 1

PK -08/09: Inl�mningsuppgift 1

Inledning

Uppgiften best�r i att skriva ett program som skall utf�ra symbolisk derivering. Det inneb�r att programmet skall l�sa in en representation av ett matematiskt uttryck (funktion) och konstruera ett nytt matematiskt uttryck som �r derivatan av det givna uttrycket med avseende p� en given variabel. Till exempel skall programmet ber�kna derivatan av x³ med avseende p� x till 3x².

Samtidigt skall programmet f�renkla uttrycket s� att det inte blir on�digt komplicerat. Derivatan av x²+4 skall t.ex. inte bli 2x¹+0 utan 2x.

Uttryck

F�r det f�rsta skall du konstruera en abstrakt datatyp expr f�r att representera enkla matematiska uttryck.

Du kan inte anv�nda ML-funktioner som indata till ditt program eftersom du skall utf�ra symbolisk derivering. D.v.s. ditt program m�ste kunna se hur dina matematiska uttryck �r uppbyggda.

Du skall kunna representera f�ljande slags uttryck: variabler (v), heltal (c), summor av uttryck (e₁+e₂), differenser av uttryck (e₁-e₂), produkter av uttryck (e₁×e₂) och potenser med heltalsexponent (eⁱ).

F�r varje slags uttryck skall du ha:

en konstruktor
ett predikat som "k�nner igen" det slaget av uttryck
en upps�ttning selektorer f�r deluttrycken

Du ska dessutom skriva en funktion exprToString : expr -> string som givet ett uttryck returnerar en str�ng som beskriver uttrycket. (En s�dan funktion �r ocks� anv�ndbar under fels�kningen.) Str�ngen m�ste vara riktig enligt vanliga matematiska regler, t.ex. skall multiplikation ha h�gre precedens �n addition, men den beh�ver inte vara elegant. Om du vill slippa fundera p� s�dana saker som precedens f�r operatorer s� kan du helt enkelt s�tta ut parenteser runt alla deluttryck...

Derivering

Du skall skriva en funktion deriv : expr * string -> expr s�dan att om f representerar ett uttryck f och x �r namnet p� en representerad variabelx s� skall deriv(f,x) ber�kna ett uttryck som representerar derivatan av f med avseende p� x. Kortare och slarvigare uttryckt: deriv tar fram derivatan av sitt f�rsta argument med avseende p� sitt andra argument.

Funktionen deriv f�r inte vara en primitiv till den abtrakta datatypen f�r matematiska uttryck.

Ditt program skall kunna derivera ett godtyckligt uttryck med avseende p� en variabel. De resulterande uttrycken skall f�renklas s� l�ngt det �r m�jligt genom att utnyttja enkla matematiska samband som t ex att x + 0 �r x, att 1 × x �r x, etc. En god strategi �r att l�gga f�renklingen i konstruktorerna f�r uttryck, men det �r ocks� fullt m�jligt att skriva en speciell funktion f�r att f�renkla uttryck. D�remot skall man inte f�rs�ka g�ra deriveringen och f�renklingen i samma funktion -- det blir bara r�rigt.

Deriveringsregler

Ditt program skall klara av �tminstone f�ljande deriveringsregler.

dc/dx	=	0	Derivatan av en konstant eller en annan variabel �n den vi deriverar med avseende p� �r 0.
dx/dx	=	1	Derivatan av en variabel med avseende p� sig sj�lv �r 1.
d(u+v)/dx	=	du/dx+dv/dx	Derivatan av en summa �r summan av derivatan av argumenten.
d(u-v)/dx	=	du/dx-dv/dx	Derivatan av en differens �r differensen av derivatorna av argumenten.
d(u×v)/dx	=	u(dv/dx)+v(du/dx)	Derivatan av en produkt uv* �r u g�nger (derivatan av v) plus (derivatan av u) g�nger v
d(uⁱ)/dx	=	i×u^i-1(du/dx)	Derivatan av en potens uⁱ �r exponenten (i), multiplicerat med basen (u) upph�jt i exponenten minus 1, multiplicerat med derivatan av basen (u).

F�renklingsregler

Ditt program skall utnyttja �tminstone f�ljande f�renklingsregler.

En summa, differens eller produkt av heltal skall f�renklas till ett heltal.
En potens av heltal skall f�renklas till ett heltal d�r s� �r m�jligt. 2² skall allts� f�renklas till 4, medan 2^-2 inte skall f�renklas eftersom 0,25 inte �r ett heltal.
Summan av ett uttryck e och 0 (eller vice versa) skall f�renklas till e.
Differensen av ett uttryck e och 0 skall f�renklas till e.
Produkten av ett uttryck e och 0 (eller vice versa) skall f�renklas till 0 medan produkten av ett uttryck e och 1 (eller vice versa) skall f�renklas till e.
Potensen av ett uttryck e och 0 skall f�renklas till 1 medan potensen av ett uttryck e och 1 skall f�renklas till e.

Man kan t�nka sig m�nga ytterligare f�renklingsregeler, t ex f�r distributivitet etc, men kr�ngla inte till detta steg f�r mycket. Du beh�ver till exempel inte kunna f�renkla 3+x+5 till 8+x.

Exempel

Derivering av x×y med avseende p� x: exprToString(deriv(makeProd(makeSym("x"),makeSym("y")),"x")) skulle kunna ha v�rdet "y". (Derivatan �r just y och exprToString applicerat p� representationen av symbolen y borde ge just str�ngen "y".

Derivering av x²-5x+7 med avseende p� x:

exprToString(deriv(makeSum(makeDiff(makePow(makeSym("x"),makeNum(2)),
                                     makeProd(makeNum(5),makeSym("x"))),
                            makeNum(7)),
                    "x"))

skulle kunna ha v�rdet "(2*x)-5". (Derivatan �r 2x-5 och exprToString applicerat p� representationen av det givna uttrycket borde ge n�got i stil med str�ngen "(2*x)-5".

Notera att s�v�l namn p� primitiver som str�ngrepresentation �r s�dant du sj�lv v�ljer. Det �r inte alls n�dv�ndigt att det ska se ut exakt som ovan.

Dokumentation

Du skall skriva dokumentation till ditt program. F�rutom de vanliga specifikationerna till varje funktion som skall finnas i programkoden, s� inneb�r det att du skall skriva ett separat dokument som beskriver hur ditt program fungerar och hur man skall anv�nda det.

Dokumentet skall l�mnas in som en pdf-fil (helst) eller en textfil. Intesom en Microsoft Word .doc-fil, TeX-k�llkod eller liknande.

Dokumentationen skall inneh�lla:

titel, f�rfattarnamn, uppgift om att detta �r inl�mningsuppgift 1 p� denna kurs detta �r, inneh�llsf�rteckning, inledning med sammanfattning av vad programmet g�r.
En "anv�ndarbeskrivning": en anvisning f�r hur man praktiskt anv�nder ditt program f�r att l�sa utf�ra symbolisk derivering, inklusive k�rexempel.
En "programdokumentation": en beskrivning av hur ditt program egentligen fungerar:
- beskrivning av hur din abstrakta datatyp f�r uttryck fungerar, hur du har representerat uttrycken och hur man skall anv�nda den abstrakta datatypen
- beskrivning av hur deriveringen fungerar, vilka uttryck som kan deriveras och hur man skall anv�nda deriveringsfunktionen.
- beskrivning av hur f�renklingen fungerar, vilka uttryck som kan f�renklas och hur man anv�nder f�renklingsfunktionen (om den �r en separat funktion).
- Beskrivning av vad de olika delfunktionerna g�r och hur programfl�det ser ut (allts� hur funktionerna anropar varandra). Det skadar inte att ge en beskrivning av algoritmen h�r.
Beskrivning av k�nda brister hos programmet. Det kan vara s�dant som du sj�lv tycker �r mindre lyckat gjort, funktioner enligt uppgiften som du trots tappra f�rs�k inte lyckats f� till ordentligt eller saker som du tycker programmet borde g�ra fast�n det inte kr�vs i uppgiften.

Det skall r�cka att l�sa dokumentationen f�r att f�rst� ditt program. Du kan inte utg� ifr�n att l�saren ocks� l�st denna uppgiftsbeskrivning. Du kan allts� inte utl�mna information fr�n dokumentationen bara f�r att den finns i uppgiftsbeskrivningen. � andra sidan beh�ver du inte ta med allt som finns i uppgiftsbeskrivningen. Instruktionerna f�r hur uppgiften skall genomf�ras beh�ver f�rst�s inte finnas i programdokumentationen.

Dokumentationen �r lika viktig som sj�lva programmet. �r dokumentationen d�lig s� kommer du att f� komplettering p� uppgiften �ven om ditt program fungerar. Det �r sv�rt att skriva en godk�nd dokumentation som inte �r minst tv� hela sidor l�ng.

Det finns ett exempel taget fr�n ett tidigare �rs inl�mningsuppgift som visar hur dokumentationen kan se ut. Exemplet visar en bra dokumentation som v�l uppfyller minimikraven utan att f�r den skull vara perfekt.

Inl�mning

Inl�mningsuppgiften skall l�sas individuellt! Du f�r givetvis diskutera uppgiften och olika l�sningsmetoder med kurskamrater, men du skall sj�lv ha konstruerat din l�sning.
L�sningen skall l�mnas in i tv� delar -- en ML-fil och en dokumentationsfil. �verst i ML-filen skall du l�gga en kommentar med kursens namn, texten "Inl�mningsuppgift 1", datum och ditt namn. Dokumentationsfilen skall inneh�lla samma uppgifter i rubriken.
Du skall f�lja kodstandarden, bl.a. skall du skriva funktionsdeklarationer f�r alla funktioner du definierar och varianter f�r alla rekursiva funktioner. Detta �r �nnu viktigare �n f�r labbarna. Eftersom du har n�stan full frihet att utforma din l�sning som du vill -- t.ex. betr�ffande vilka hj�lpfunktioner du inf�r -- s� �r det mycket viktigt att assistenterna snabbt kan s�tta sig in i vad din kod g�r. D�r spelar bra funktionsspecifikationer en viktig roll.
L�mna in din l�sning enligt anvisningarna senast den 2:a mars klockan 08:00!

Tips

N�gra praktiska tips som kommer att underl�tta utf�randet av uppgiften.

L�s om syntaxtr�d i OH-bilderna fr�n f�rel�sning 7 f�r id�er om hur datatypen expr kan se ut.
Skriv s� l�ngt m�jligt dokumentationen -- b�de funktionsspecifikationerna och den externa dokumentationen -- innan du b�rjar skriva programmet. Det vill s�ga: T�nk igenom hur du skall l�sa uppgiften, skriv sedan dokumentationen och sist programmet.
Skriv den abstrakta datatypen f�rst (inklusive alla primitiver) innan du skriver resten av koden.
Anv�nd datatype f�r uttrycken medan du testar och fels�ker -- det underl�ttar eftersom du f�r datastrukturerna utskrivna av ML. Prova att ladda programmet med abstype d� och d� f�r att kontrollera att du inte av misstag inf�rt n�gon kod som �r beroende av datatypens utseende -- konstruktorer ("taggar") till exempel -- i de funktioner som har hand om deriveringen. Hela den egentliga l�sningen av deriveringen skall allts� ligga utanf�r datatypsdefinitionen -- denna skall enbart hantera uttryck. Gl�m inte att det skall st� abstype n�r du l�mnar in l�sningen!
Starta om ML d� och d� s� att du �r s�ker p� att du inte av misstag anv�nder gamla definitioner. Antag att du i funktionen foo anropar funktionen bar. Sedan best�mmer du dig f�r att ta bort bar och �ndrar p� alla st�llen d�r bar anv�nds, utom just i foo som du gl�mmer att �ndra. S� l�nge du inte startar om ML kommer bar att finnas kvar och foo fungerar fortfarande. N�r du startar om ML s� f�rsvinner definitionen av bar och foo slutar att fungera. Ju f�rr du uppt�cker det, dess b�ttre.
Be om hj�lp n�r du k�r fast. Antingen via mail eller genom att s�ka upp din assistent eller f�rel�sare. Det �r inte meningen att ni ska sitta i timtal och jaga en och samma bug. Om du � andra sidan inte skrivit ner hur du t�nkt g�ra, typ, etc, s� �r det det f�rsta du kommer att bli ombedd att g�ra, s� det �r ingen mening att fr�ga om kodhj�lp om du inte gjort det (annat �n allm�nna fr�gor f�rst�s).

Vanliga fallgropar

Se till att du har r�tt typ p� dina tv� huvudfunktioner. deriv ska f� ett uttryck och en str�ng och returnera ett uttryck. exprToString ska f� ett uttryck och returnera en str�ng. Detta inneb�r bland annat att deriv inte ska anv�nda sig av exprToString.
Datatypen expr ska vara definierad med hj�lp av abstype.
Datatypen expr skall inte k�nna till n�got om derivering. Det enda som f�r ligga mellan with och end �r primitiver f�r datatypen, dvs konstruktorer, selektorer och predikat. (exprToString kan r�knas som primitiv om man vill.)
Alla funktioner och hj�lpfunktioner som h�r till deriveringen ska ligga utanf�r datatypdefinitionen.
Gl�m inte att f�lja kodstandarden!.
Gl�m inte att f�lja minneslistan f�r programutveckling!.