Göm menyn

Dataabstraktion

Abstrakt eller konkret?

Vad är det egentligen som är abstrakt och vad är konkret? Man brukar säga att abstrakt är:

  • Teoretiskt
  • Konstruerad
  • Overklig
  • Svårfattig
  • Dunkel
  • Akademisk

Och att konkret är:

  • Verklig
  • Påtaglig
  • Faktisk
  • Åskådlig
  • Existerande
  • Tydlig
  • Gripbar

Inom datavärlden finns det många typer av abstraktion. Framförallt så brukar man prata om procedurabstraktion, det vill säga att gömma hur vi i detalj gör något. Med det menar vi att vi inte är intresserade av hur den inbyggda funktionen sum faktiskt summerar, utan bara att den är korrekt. Detta betyder också att implmentationen av sum kan ändras i ett senare skede utan att påverka övriga delar av systemet så länge den uppfyller samma kontrakt.

En annan vanlig typ av abstraktion är dataabstraktion, vilket handlar om att konstruera mer komplexa "datatyper" ur befintliga, primitiva, datatyper för att förenkla hanteringen av sammanhängande data. Vi kallar denna sorts datatyper abstrakta (även om implementationen är konkret) då de underliggande primitiva datatyperna och hanteringen av dessa abstraherats bort.

Definition av datatyp (igen)

En datatyp är en väldefinierad sorts information som ett datorprogram kan använda. Datatypen talar om vilka dataobjekt som ingår i typen (vilken domän som typen har) samt vilka operationer som är tillåtna.

Datatypen svarar alltså på frågorna:

  • Hur ser objekten ut?
  • Vad kan man göra med dem?

Datatyper på olika nivåer

Alt text

Datatypens definitionsmängd

  • Ändlig: Till exempel sanningsvärden (True, False).
  • Oändlig: Till exempel heltal.
  • Sammansatt: Till exempel tal (Number i Python) som en union av heltal, flyttal och komplexa tal.
  • Rekursivt definerad: Till exempel ett binärt sökträd. Det kan vara ett tomt träd, ett löv eller en nod som innehåller upp till två binära sökträd.

Primitiva operationer på datatyper

De primitiva operationerna utgör datatypens gränssnitt (eng. interface) gentemot resten av programkoden. Några exempel på typer av primitiver:

  • Konstruktorer (eng. constructors) för att skapa objekt.
  • Selektorer (eng. selectors) för att plocka ut delarna.
  • Igenkännare (eng. recognizers) för att känna igen objekt av viss datatyp eller objekt med särkilda egenskaper.
  • Iteratorer (eng. iterators) för att bearbeta alla elementen i ett objekt, ofta med hjälp av högre ordningens funktioner.
  • Jämförare (eng. comparator) för att kontrollera när objekt är lika.
  • Modifikatorer (eng. modifiers) för att ändra elementen i ett objekt.

Exempel: Symbolisk derivering

Deriveringsregler

Alt text

Exempel

Alt text

Denna lösning är representationsberoende. Programkod som relaterar till hur vi har valt att lagra de matematiska uttrycken är sammanblandad med programkod som behandlar algoritmen för symbolisk derivering. En av de stora poängerna med att införa abstraka datatyper är att vi vill gömma informationen om hur data är representerat (eng. information hiding).

Arbetsmetodik

  1. Identifiera datatyper. Studera tillämpningsområdet och karaktärisera den information som hanteras. För sammansatt information, bestäm hur de ingående delarna relaterar till varandra.
  2. Bestäm primitiver. Se olika typer ovan.
  3. Bestäm representation. För varje datatyp, bestäm hur de enskilda objekten ska representeras (i termer av de datatyper som finns i det språk som används).
  4. Definiera primitiver. Implementera.

Identifiera datatyper

Vilka delar består ett matematiskt uttryck av?

Ett uttryck kan vara en konstant, en variabel eller ett sammansatt uttryck. Ett sammansatt uttryck består i sin tur av två utryck med en operator emellan.

Orden i kursiv stil ovan är våra abstrakta datatyper. Ofta kan fler detaljer behöva specificeras, men i det här exemplet nöjer vi oss så här.

Bestäm primitiver

Var och en av de fem datatyperna behöver åtminstonne en basuppsättning primitiver: konstruktor (som skapar objekt från dess delar), selektorer (som plockar ut de olika delarna) och igenkännare. Det är dock inte säkert att alla primitiver är nödvändiga för varje datatyp i just det exempel vi ska implementera.

Bestäm representation

  • Konstant: Ett vanligt tal så som det skrivs i Python.
  • Variabel: En sträng i Python som innehåller bokstäver.
  • Operator: En sträng i Python som innehåller någon av symbolerna + eller *.
  • Sammansatt uttryck: En lista bestående av tre element; två uttryck med en operator mellan.

Definiera primitiver

Symbolisk derivering (abstraherad version)

Sätt att konstruera sammansatta datatyper

Många sammansatta abstrakta datatyper liknar varandra strukturellt och därför kan det vara bra att försöka hitta överordnade begrepp för att beskriva dem. Följande diskretmatematiska begrepp brukar användas för att karaktärisera olika sorters sammansatta datatyper:

  • Tupel
  • Ändlig avbildning
  • Sekvens
  • Mängd

Tupel

Begrepp Tupel
Vad är det? En datatyp med ett fixt antal element där varje element har en given datatyp, d.v.s ordningen mellen elementen spelar roll och elementen i sig har olika betydelser
Hur beskriver vi det?
Exempel datum = <år, månad, dag>
Motsvarighet i Python tuple

Ändlig avbildning

Begrepp Ändlig avbildning (eng. finite mapping)
Vad är det? En datatyp med fixt antal element av samma datatyp där ordningen mellan elementen egentligen inte spelar så stor roll (enbart om indexmänden är ordnad)
Hur beskriver vi det? [data-1, ..., data-n]
Exempel veckoschema = [dagschema-1, ..., dagschema-n]
Motsvarighet i Python list (även om Python listor är mer generösa), dict (om indexmängden är annat än heltal)

Sekvens

Begrepp Sekvens
Vad är det? En datatyp med ett valfritt antal element av samma datatyp där ordningen mellan elementen spelar roll
Hur beskriver vi det? {{datatyp}}* om det är okej med tomma sekvenser, {{datatyp}}+ om sekvensen måste innehålla något
Exempel utbildningsprogram = {{kurs}}*
Motsvarighet i Python list

Mängd

Begrepp Mängd
Vad är det? En datatyp med ett valfritt antal element av samma datatyp där ordningen mellan elementen inte spelar roll
Hur beskriver vi det? {datatyp}
Exempel studieresultat = {kurs}
Motsvarighet i Python set

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-15