Loading
Företag som bedriver god utveckling av programvara har kodkonventioner - på samma sätt kan det användas i kurser i programmering och mjukvaruutveckling. Kraven i denna kodkonvention har utformats som verktyg att hjälpa och vägleda ditt tänkande före och under programmeringen - inte som ett ytterligare hinder efter att du lyckats färdigställa ditt program.
Reglerna underlättar också förståelsen för ditt program hos andra - t.ex. lärare och assistenter som skall bedöma dem.
Att sluta använda dessa goda vanor efter att du avslutat kurserna som kräver dem är att göra dig själv en otjänst. En kompetent och erfaren programmerare kan förstås göra specifikationer i huvudet, men det är till föga hjälp om hon ser tillbaka på programmet en tid senare eller om någon annan måste arbeta med programmet. Ingen ingenjör arbetar på en konstruktion utan en kravspecifikation!
Lösningen av en uppgift - vare sig det gäller på laboration (från och med laboration 4), inlämningsuppgift eller tentamen - där inte alla funktioner, värden och datastrukturer är beskrivna enligt nedanstående kan komma att underkännas! Detta oberoende av ifall lösningen i övrigt skulle vara fullständigt korrekt.
Varje funktion skall föregås av en kommentar med dess specifikation. Det gäller oavsett om den är deklarerad lokalt eller globalt, är "stuvad" (curried) eller inte, är angiven i uppgiftsbeskrivningen eller påhittad av dig.
Det enda undantaget från ovanstående gäller anonyma funktioner som ges som argument till en annan funktion. Där slipper du skriva specifikation, men å andra sidan skall en sådan funktion vara mycket enkel. Om den inte är det så skall du inte använda en anonym funktion utan namnge den.
Kommentaren skall vara utformad på följande sätt:
(* funktionsnamn argument TYPE: argumenttyp -> resultattyp PRE: ... förvillkor (på argumenten) ... POST: ... eftervillkor (beskrivning av resultatet) ... EXAMPLES: ... representativa exempel på anrop och resultat ... *)
Om du använder ackumulatorvariabler (som t.ex. i svansrekursion), se till att PRE inte kräver att dessa skall ha ett konstant värde. Det kanske gäller för första anropet, men inte i de rekursiva anropen.
Om inget förvillkor behövs, så är det bättre att skriva "PRE: (inget)" eller "PRE: (none)" i stället för att utelämna PRE eller lämna blankt.
I PRE och POST finns ingen anledning att ange typerna hos argument eller resultat eftersom detta redan framgår av TYPE-raden.
I POST räcker det att ange ett uttryck för värdet. Att t.ex. skriva ut "Det beräknade värdet är..." är onödigt.
Observera att specifikationen normalt inte kan vara riktig om inte samtliga argument förkommer i POST (eller i SIDE-EFFECTS, om det är aktuellt - se nedan).
Varje värde i en abstrakt datatyp skall föregås av en kommentar med dess specifikation. Kommentaren skall vara utformad på följande sätt:
(* valuenamn TYPE: typ VALUE: ... beskrivning ... *)
Beskrivningarna skall ges i klartext. Specifikationer skrivs
vanligen oberoende av programspråket, så långt möjtligt. En lämplig
blandning av klartext och vanlig matematisk notation är normalt bäst.
Skriv alltså 0 och inte 0.0. Om det finns möjlighet är ≠ bättre än
<>, och · är bättre än *.
Varje identifierare skall beskriva den funktion/värde den namnger.
Varje identifierare skall börja med liten bokstav. Om man vill ha flera ord i identifieraren så stapla dem på varandra och låt alla ord utom det första börja med stor bokstav. Använd inte understrykningstecken (`_') mellan ord.
Exempel:
maxValue endOfTheGame
Varje rekursiv funktion skall föregås av en kommentarrad som anger rekursionsvarianten. T.ex. så här:
(* VARIANT: ... *)
Precis som PRE och POST så skall varianten referera till argumentnamnen i specifikationen, inte till argumentnamn i programmet. Anledningen är att varianten skall skrivas innan programmet konstrueras eftersom den avspeglar en designfråga. Dessutom är varianten inte en del av specifikationen, utan en del av ett argument för att programmet är riktigt. För en given specifikation kan man skriva flera olika program med olika varianter.
På inlämningsuppgift 3, 5 och 6 ska varje funktion föregås av kommentarrader som anger tidskomplexiteten för relevanta fall (bästa, sämsta, medel, alla) och, vid behov, en indikation på den valda algoritmen. T.ex. så här:
(* TIME COMPLEXITY: ... *) (* ALGORITHM: ... *)
Precis som PRE, POST och VARIANT så skall tidskomplexiteten referera till argumentnamnen i specifikationen, inte till argumentnamn i programmet.
Varje funktion med sidoeffekter skall ha en rad i funktionsspecifikationen som beskriver sidoeffekterna. T.ex. så här:
SIDE-EFFECTS: ...
Varje definierad datatyp (datatype och
abstype) skall inledas med en kommentar om hur den
skall användas och vilken invariant som gäller för den:
(* REPRESENTATION CONVENTION: ... beskrivning av hur typen representerar data ... REPRESENTATION INVARIANT: ... egenskap hos representationen som alltid måste gälla... *)
Layout och indentering av funktionsdefinitioner skall göras på följande vis:
fun namn mönster1 = uttryck1
...
| namn mönsterN = uttryckN
Alternativt kan uttryck skrivas på raden efter mönstret:
fun namn mönster1 =
uttryck1
...
| namn mönsterN =
uttryckN
Layout och indentering av if-then-else-uttryck skall göras på följande vis:
...
if boolsktUttryck then
uttryck1
else
uttryck2
...
Om ytterligare if-uttryck följer efter ett else bör layout och indentering göras på följande vis:
...
if boolsktUttryck1 then
uttryck1
else if boolsktUttryck2 then
uttryck2
...
else
uttryckN
...
Layout och indentering av case-uttryck skall göras på följande vis:
case uttryck of mönster1 => uttryck1 ... | mönsterN => uttryckN
Layout och indentering av let-uttryck skall göras på följande vis:
...
let
deklaration1
...
deklarationN
in
uttryck
end
...
Layout och indentering av lokala deklarationer skall göras på följande vis:
...
local
deklaration11
...
deklaration1N
in
deklaration21
...
deklaration2M
end
...
Det exakta antalet blanktecken i indenteringen är inte viktig, men all indentering måste vara konsekvent, dvs varje uttryck inom "..." ovan måste börja lika långt från vänsterkanten utom där indenteringen skall ändras enligt ovanstående regler.
Indentering av andra uttryck än de som beskrivs ovan skall göras efter bästa förstånd. Titta gärna på program i kursboken och på OH-bilderna från föreläsningarna för ideer.
(* myMax (a,b)
TYPE: int * int -> int
PRE: (none)
POST: the largest value among a and b
EXAMPLES: myMax ( 2, 5) = 5
myMax (~2,~5) = ~2
*)
(* TIME COMPLEXITY: Theta(1) always *)
fun myMax (a,b) =
if a > b then
a
else
b
(* fact n
TYPE: int -> int
PRE: n >= 0
POST: the factorial of n
EXAMPLES: fact 0 = 1
fact 3 = 6
*)
(* VARIANT: n
TIME COMPLEXITY: Theta(n) always
*)
fun fact 0 = 1
| fact m = m * fact (m-1)
(* REPRESENTATION CONVENTION: the head of the list is the top of
the stack, the 2nd element of the list is the element below
the top, and so on
REPRESENTATION INVARIANT: (none)
*)
abstype 'a stack = Stack of 'a list
with
(* empty
TYPE: 'a stack
VALUE: the empty stack
*)
val empty = Stack []
(* push (S, t)
TYPE : 'a stack * 'a -> 'a stack
PRE: (none)
POST: the stack S with t added as new top element
*)
(* TIME COMPLEXITY: Theta(1) always *)
fun push (Stack S, t) = Stack(t::S)
...
end
(* REPRESENTATION CONVENTION: the empty binary search tree is represented by Void;
a binary search tree with key-value pair (k,v) in the root, left subtree L,
and right subtree R is represented by Bst((k,v),L,R)
REPRESENTATION INVARIANT: for Bst((k,v),L,R):
- every element of L has a key smaller than k
- every element of R has a key larger than k
and recursively so on, for L and R
*)
datatype 'b bsTree = Void
| Bst of (int * 'b) * 'b bsTree * 'b bsTree
(* empty
TYPE: 'b bsTree
VALUE: the empty binary search tree
*)
val empty = Void
...
(* exists (T, k)
TYPE: 'b bsTree * int -> bool
PRE: (none)
POST: true if T contains a node with key k, and false otherwise
*)
(* VARIANT: the height of T
TIME COMPLEXITY: Theta(|T|) at worst
*)
fun exists (Void, k) = false
| exists (Bst((key,value),L,R), k) =
if k = key then
true
else
if k < key then
exists (L, k)
else
exists (R, k)
...
(* function sort L
TYPE: int list -> int list
PRE: (none)
POST: a non-decreasingly sorted permutation of L
EXAMPLE: sort [5,7,3,12,1,7,2,8,13] = [1,2,3,5,7,7,8,12,13]
*)
(* ALGORITHM: merge sort
VARIANT: |L|
TIME COMPLEXITY: Theta(|L| * lg |L|) always
*)
fun sort [] = []
| sort [x] = [x]
| sort xs =
let
val (ys, zs) = split xs
in
merge (sort ys, sort zs)
end
...