Abstrakcija#
Ko pišemo večje programe, je dobro, da jih razdelimo na manjše dele, ki jih lahko ločeno razumemo, razvijamo in preizkušamo. Pravimo, da programe pišemo modularno. V programskih jezikih modularnost dosežemo na več načinov. Eden, na katerega smo že navajeni, je razbitje kode na funkcije. Dostikrat pa želimo sorodne funkcije in podatke združiti v povezane enote.
V Pythonu to lahko storimo z razredi, ki združujejo določeno vrsto podatkov s funkcijami za delo na njih. Včasih je med seboj povezanih več razredov, ki jih združujemo v posamezne datoteke, ki jim pravimo tudi moduli.
Tudi OCaml pozna module, ki imajo enako ime kot Pythonovi, a so precej naprednejši, saj omogočajo tudi skrivanje podrobnosti implementacije, čemur pravimo abstrakcija. Namen skrivanja podrobnosti seveda ni v zaščiti industrijskih skrivnosti, saj običajno delamo z lastnimi moduli, temveč v tem, da skrijemo podrobnosti in s tem poenostavimo razumevanje, preprečimo nepričakovano uporabo in olajšamo kasnejše spremembe implementacije.
Moduli#
OCamlovi moduli so zbirke definicij tipov, funkcij, vrednosti, (kasneje tudi drugih modulov), kot smo jih do sedaj pisali v datoteke ali v ukazno vrstico. V resnici vsaka .ml
datoteka predstavlja modul, ki vsebuje vse definicije v njej. Do sedaj smo spoznali že nekaj modulov iz standardne knjižnice: String
za delo z nizi, List
za delo s seznami ali Random
za delo z naključnimi vrednostmi.
Sestavimo svoj modul Datum
za delo z datumi, v katerega za začetek naberimo funkcije in tipe, ki smo jih videli že prej. Module definiramo z ukazom module
, vse definicije v modulu pa morajo biti znotraj bloka struct ... end
. Glavni tip modula običajno poimenujemo t
, da pišemo Datum.t
namesto Datum.datum
.
module Datum = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi dan mesec leto =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
module Datum :
sig
type t = { dan : int; mesec : int; leto : int; }
val je_prestopno : int -> bool
val dolzina_meseca : int -> int -> int
val je_veljaven : t -> bool
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
Do funkcij iz modula dostopamo prek ImeModula.ime_funkcije
, tako kot smo do sedaj dostopali do funkcij iz modulov List
, String
in Random
.
{ dan = 25; mesec = 6; leto = 1991} |> Datum.to_string
- : string = "1991-06-25"
Datum.dolzina_meseca 1991 6
- : int = 30
Signature#
Tako kot ima vsaka vrednost v OCamlu svoj tip, lahko zgoraj vidimo, da ga imajo tudi moduli. Tipom modulov pravimo signature. Signatura opisuje definirane tipe ter tipe definiranih vrednosti (ne pa njihovih implementacij). Signature pišemo podobno kot module, le da uporabimo blok sig ... end
, tipe vrednosti pa podamo s ključno besedo val
. Definicije tipov ostanejo enake.
Definicije signatur#
Signature definiramo podobno kot module, le da uporabimo ukaz module type
.
module type DATUM =
sig
type t = { dan : int; mesec : int; leto : int; }
val je_prestopno : int -> bool
val dolzina_meseca : int -> int -> int
val je_veljaven : t -> bool
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
module type DATUM =
sig
type t = { dan : int; mesec : int; leto : int; }
val je_prestopno : int -> bool
val dolzina_meseca : int -> int -> int
val je_veljaven : t -> bool
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
Kot smo videli zgoraj, zna OCaml tako signaturo izračunati tudi sam. Toda tako kot smo morali prej nekaterim funkcijam z označbami sami vsiliti tip, bomo enako želeli s signaturami modulov. Razloga sta dva:
preverjanje skladnosti in
skrivanje implementacije.
Preverjanje skladnosti implementacije#
Prvi namen signatur je specifikacija vsebine modula. Običajno delo začnemo tako, da v signaturi opišemo, kaj bodo sestavni deli modula, nato pa začnemo pisati implementacijo, ki ji zadošča. Ko definiramo modul, lahko zraven z označbo podamo tudi njegovo signaturo:
module Datum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi dan mesec leto =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
module Datum : DATUM
Isti signaturi lahko zadošča več modulov, ki se med seboj razlikujejo le v implementaciji. Na primer, tu je malo bolj ohlapna implementacija datumov. Seveda si take implementacije ne želimo, je pa morda dobro začetno izhodišče. Od vsega začetka razvoja pa bo OCaml preverjal, ali se implementacija ujema s signaturo.
module VednoVeljavenDatum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto = false
let dolzina_meseca _ _ = 31
let je_veljaven _ = true
let naredi dan mesec leto = Some { dan; mesec; leto }
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
module VednoVeljavenDatum : DATUM
Če kakšna od naštetih funkcij manjka, bo OCaml to opazil in javil napako:
module Datum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi dan mesec leto =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
end
File "[7]", lines 1-22, characters 23-3:
1 | .......................struct
2 | type t = { dan : int; mesec : int; leto : int }
3 |
4 | let je_prestopno leto =
5 | (leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
...
19 | let naredi dan mesec leto =
20 | let datum = { dan; mesec; leto } in
21 | if je_veljaven datum then Some datum else None
22 | end
Error: Signature mismatch:
...
The value `to_string' is required but not provided
File "[4]", line 8, characters 4-31: Expected declaration
Podobno bo preveril, ali se pri vseh definicijah ujemajo tipi.
module Datum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi (dan, mesec, leto) =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
File "[8]", lines 1-25, characters 23-3:
1 | .......................struct
2 | type t = { dan : int; mesec : int; leto : int }
3 |
4 | let je_prestopno leto =
5 | (leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
...
22 |
23 | let to_string { dan; mesec; leto } =
24 | Format.sprintf "%04d-%02d-%02d" leto mesec dan
25 | end
Error: Signature mismatch:
...
Values do not match:
val naredi : int * int * int -> t option
is not included in
val naredi : int -> int -> int -> t option
The type int * int * int -> t option is not compatible with the type
int -> int -> int -> t option
Type int * int * int is not compatible with type int
File "[4]", line 7, characters 4-46: Expected declaration
File "[8]", line 19, characters 6-12: Actual declaration
Skrivanje implementacije#
Glavna prednost uporabe signatur pa je v tem, da lahko z njimi implementacij ne le preverjamo, temveč tudi deloma skrivamo. Če uporabljamo pomožno funkcijo, ki ni del signature, navzven ne bo vidna. Na primer, funkcije za izračun veljavnosti datuma lahko skrijemo.
module type DATUM =
sig
type t = { dan : int; mesec : int; leto : int; }
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
module type DATUM =
sig
type t = { dan : int; mesec : int; leto : int; }
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
module Datum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi dan mesec leto =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
module Datum : DATUM
Modul še vedno vsebuje vse funkcije iz signature, zato se OCaml ne pritoži. A če poskusimo dostopati do dodatnih funkcij, bomo dobili napako:
Datum.naredi 25 6 1991
- : Datum.t option = Some {Datum.dan = 25; mesec = 6; leto = 1991}
Datum.dolzina_meseca 1991 6
File "[12]", line 1, characters 0-20:
1 | Datum.dolzina_meseca 1991 6
^^^^^^^^^^^^^^^^^^^^
Error: Unbound value Datum.dolzina_meseca
Skrivanje implementacij uporabnikom poenostavi uporabo, saj izpostavi le ključne funkcije. Hkrati pa razvijalcem olajša kasnejše spremembe implementacije, če na primer najdejo boljši algoritem. Če pomožne funkcije ne bi bile skrite, bi se lahko nanje kdo zanašal, kar bi otežilo kasnejše spremembe.
Abstraktni tipi#
Poleg pomožnih funkcij lahko skrivamo tudi definicije tipov. To ne poenostavlja samo uporabe in kasnejših razširitev, temveč tudi zagotavlja pravilnost podatkov. Recimo, kljub temu, da smo pripravili funkcijo naredi
, ki bo vedno ustvarila veljaven datum, lahko uporabnik še vedno ustvari neveljaven datum.
{ dan = 32; mesec = 13; leto = 2024 } |> Datum.to_string
- : string = "2024-13-32"
Temu se lahko izgonemo tako, da skrijemo definicijo tipa, samo povemo, da obstaja.
module type DATUM =
sig
type t
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
module type DATUM =
sig
type t
val naredi : int -> int -> int -> t option
val to_string : t -> string
end
module Datum : DATUM = struct
type t = { dan : int; mesec : int; leto : int }
let je_prestopno leto =
(leto mod 4 = 0 && leto mod 100 <> 0) || leto mod 400 = 0
let dolzina_meseca leto =
function
| 4 | 6 | 9 | 11 -> 30
| 2 -> if je_prestopno leto then 29 else 28
| _ -> 31
let je_veljaven datum =
let veljaven_dan = 1 <= datum.dan && datum.dan <= dolzina_meseca datum.leto datum.mesec
and veljaven_mesec = 1 <= datum.mesec && datum.mesec <= 12
in
veljaven_dan && veljaven_mesec
let naredi dan mesec leto =
let datum = { dan; mesec; leto } in
if je_veljaven datum then Some datum else None
let to_string { dan; mesec; leto } =
Format.sprintf "%04d-%02d-%02d" leto mesec dan
end
module Datum : DATUM
Sedaj je edini način, da ustvarimo vrednosti tipa Datum.t
ta, da pokličemo funkcijo naredi, ki preveri veljavnost. Tudi če uporabnik uporabi identični tip, kot je v implementaciji, bo OCaml preprečil neposredno manipulacijo z njim.
{ dan = 32; mesec = 13; leto = 2024 } |> Datum.to_string
File "[16]", line 1, characters 2-5:
1 | { dan = 32; mesec = 13; leto = 2024 } |> Datum.to_string
^^^
Error: Unbound record field dan
Poleg tega lahko uporabimo tudi drugačno implementacijo datumov, recimo da mesece predstavimo z naštevnim tipom.
Primer: štetje različnih elementov#
Za primer izračunajmo, koliko različnih elementov vsebuje dani seznam. Ena izmed možnosti je, da se sprehajamo čez seznam ter beležimo seznam elementov, ki smo jih že videli, začenši s praznim seznamom. Vsak element primerjamo z že videnimi in če ga še nismo videli, ga dodamo v seznam. Seveda bo ta primer majhen in ga ne bi bilo treba razčlenjevati, a bomo to vseeno storili, da spoznamo pristop.
let stevilo_razlicnih xs =
let rec aux ze_videni = function
| [] -> List.length ze_videni
| x :: xs ->
if List.mem x ze_videni
then aux ze_videni xs
else aux (x :: ze_videni) xs
in
aux [] xs
val stevilo_razlicnih : 'a list -> int = <fun>
stevilo_razlicnih [1; 2; 1; 2; 1; 2; 3]
- : int = 3
Napišimo še nekaj funkcij, s katerimi bomo izmerili (ne)učinkovitost take implementacije.
let nakljucni_seznam m n = List.init n (fun _ -> Random.int m)
val nakljucni_seznam : int -> int -> int list = <fun>
nakljucni_seznam 5 20
- : int list = [4; 0; 2; 1; 4; 0; 4; 0; 1; 0; 2; 0; 4; 3; 0; 2; 1; 1; 3; 4]
stevilo_razlicnih @@ nakljucni_seznam 5 20
- : int = 5
let seznam_zaporednih n = List.init n (fun i -> i)
val seznam_zaporednih : int -> int list = <fun>
seznam_zaporednih 10
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
stevilo_razlicnih @@ seznam_zaporednih 10
- : int = 10
let stopaj f x =
let zacetek = Sys.time () in
let y = f x in
let konec = Sys.time () in
let izpis =
Printf.sprintf "Porabljen čas: %f ms\n" (1000. *. (konec -. zacetek))
in
print_endline izpis;
y
val stopaj : ('a -> 'b) -> 'a -> 'b = <fun>
stopaj stevilo_razlicnih (seznam_zaporednih 1000)
Porabljen čas: 9.378000 ms
- : int = 1000
stopaj stevilo_razlicnih (seznam_zaporednih 2000)
Porabljen čas: 35.539000 ms
- : int = 2000
Za dvakrat daljši seznam smo potrebovali okoli štirikrat več časa, saj se mora funkcija List.mem
sprehajati po vedno daljšem seznamu, da ugotovi, da elementa ni v njem. Razlog za neučinkovitost je v tem, da za beleženje videnih elemente uporabljamo sezname, čeprav potrebujemo samo množice, ki se ne ozirajo na vrstni red in število ponovitev. V kratkem bomo spoznali učinkovite podatkovne strukture za predstavitev množic, zaenkrat pa si pripravimo teren za spremembe implementacij.
module type MNOZICA = sig
type 'a t
val prazna : 'a t
val dodaj : 'a -> 'a t -> 'a t
val velikost : 'a t -> int
val vsebuje : 'a -> 'a t -> bool
end
module type MNOZICA =
sig
type 'a t
val prazna : 'a t
val dodaj : 'a -> 'a t -> 'a t
val velikost : 'a t -> int
val vsebuje : 'a -> 'a t -> bool
end
module Mnozica : MNOZICA = struct
type 'a t = 'a list
let prazna = []
let velikost m = List.length m
let vsebuje x m = List.mem x m
let dodaj x m = if vsebuje x m then m else x :: m
end
module Mnozica : MNOZICA
Na ta način naš algoritem namesto kot
let stevilo_razlicnih xs =
let rec aux ze_videni = function
| [] -> List.length ze_videni
| x :: xs ->
if List.mem x ze_videni
then aux ze_videni xs
else aux (x :: ze_videni) xs
in
aux [] xs
val stevilo_razlicnih : 'a list -> int = <fun>
napišemo kot:
let stevilo_razlicnih xs =
let rec aux ze_videni = function
| [] -> Mnozica.velikost ze_videni
| x :: xs -> aux (Mnozica.dodaj x ze_videni) xs
in
aux Mnozica.prazna xs
val stevilo_razlicnih : 'a list -> int = <fun>
Vidimo, da je definicija precej bolj pregledna, saj smo implementacijo in uporabo množic razdelili na dva dela.
Vaje#
Naravna števila#
Definirajte signaturo NAT
, ki določa strukturo naravnih števil. Ima osnovni tip, funkcijo enakosti, ničlo in enko, seštevanje, odštevanje in množenje. Hkrati naj vsebuje pretvorbe iz in v OCamlov int
tip. Opomba: Funkcije za pretvarjanje ponavadi poimenujemo to_int
and of_int
, tako da skupaj z imenom modula dobimo ime NAT.of_int
, ki nam pove, da pridobivamo naravno število iz celega števila.
module type NAT = sig
type t
val eq : t -> t -> bool
val zero : t
(* Dodajte manjkajoče! *)
(* val to_int : t -> int *)
(* val of_int : int -> t *)
end
module type NAT = sig type t val eq : t -> t -> bool val zero : t end
Napišite implementacijo modula Nat_int
, ki zgradi modul s signaturo NAT
, kjer kot osnovni tip uporablja OCamlov tip int
. Namig: dokler ne implementirate vse funkcij v Nat_int
, se bo OCaml pritoževal. Temu se lahko izognete tako, da funkcije, ki še niso napisane nadomestite z failwith "later"
, vendar to ne deluje za konstante.
module Nat_int : NAT = struct
type t = int
let eq x y = failwith "later"
let zero = 0
(* Dodajte manjkajoče! *)
end
module Nat_int : NAT
Napišite implementacijo NAT
, ki temelji na Peanovih aksiomih. Osnovni tip modula definirajte kot naštevni tip, ki vsebuje konstruktor za ničlo in konstruktor za naslednika nekega naravnega števila. Večino funkcij lahko implementirate s pomočjo rekurzije. Naprimer, enakost števil k
in l
določimo s hkratno rekurzijo na k
in l
, kjer je osnoven primer Zero = Zero
.
module Nat_peano : NAT = struct
type t = unit (* To morate spremeniti! *)
let eq x y = failwith "later"
let zero = () (* To morate spremeniti! *)
(* Dodajte manjkajoče! *)
end
module Nat_peano : NAT
Z ukazom let module ImeModula = ... in ...
lahko modul definiramo samo lokalno. To bomo uporabili za to, da bomo lahko enostavno preklapljali med moduloma Nat_int
in Nat_peano
, saj bomo enega ali drugega shranili pod ime Nat
. OCaml sicer pozna tudi ustrezne abstrakcije, ki omogočijo preklapljanje med moduli, na primer funktorje ali prvorazredne module, a bomo uporabili preprostejšo rešitev.
Spodnji izračun dopolnite tako, da sešteje prvih 100 naravnih števil. Ker bo taka vsota tipa NAT.t
, ki je abstrakten, končni rezultat pretvorite v tip int
z uporabo funkcije Nat.to_int
. Če ste oba modula implementirali pravilno, bi morali dobiti enak rezultat ne glede na to, katerega poimenujete Nat
.
let sum_nat_100 =
(* let module Nat = Nat_int in *)
let module Nat = Nat_peano in
Nat.zero (* to popravite na ustrezen izračun *)
(* |> Nat.to_int *)
val sum_nat_100 : Nat_peano.t = <abstr>
Kompleksna števila#
Once upon a time, there was a university with a peculiar tenure policy. All faculty were tenured, and could only be dismissed for moral turpitude. What was peculiar was the definition of moral turpitude: making a false statement in class. Needless to say, the university did not teach computer science. However, it had a renowned department of mathematics.
One Semester, there was such a large enrollment in complex variables that two sections were scheduled. In one section, Professor Descartes announced that a complex number was an ordered pair of reals, and that two complex numbers were equal when their corresponding components were equal. He went on to explain how to convert reals into complex numbers, what “i” was, how to add, multiply, and conjugate complex numbers, and how to find their magnitude.
In the other section, Professor Bessel announced that a complex number was an ordered pair of reals the first of which was nonnegative, and that two complex numbers were equal if their first components were equal and either the first components were zero or the second components differed by a multiple of 2π. He then told an entirely different story about converting reals, “i”, addition, multiplication, conjugation, and magnitude.
Then, after their first classes, an unfortunate mistake in the registrar’s office caused the two sections to be interchanged. Despite this, neither Descartes nor Bessel ever committed moral turpitude, even though each was judged by the other’s definitions. The reason was that they both had an intuitive understanding of type. Having defined complex numbers and the primitive operations upon them, thereafter they spoke at a level of abstraction that encompassed both of their definitions.
The moral of this fable is that: Type structure is a syntactic discipline for enforcing levels of abstraction.
John C. Reynolds, Types, Abstraction, and Parametric Polymorphism, IFIP83
Definirajte signaturo modula kompleksnih števil. Potrebujemo osnovni tip, test enakosti, ničlo, enko, imaginarno konstanto i, negacijo, konjugacijo, seštevanje in množenje.
module type COMPLEX = sig
type t
val eq : t -> t -> bool
(* Dodajte manjkajoče! *)
end
module type COMPLEX = sig type t val eq : t -> t -> bool end
Napišite kartezično implementacijo kompleksnih števil, kjer ima vsako kompleksno število realno in imaginarno komponento.
module Cartesian : COMPLEX = struct
type t = {re : float; im : float}
let eq x y = failwith "later"
(* Dodajte manjkajoče! *)
end
module Cartesian : COMPLEX
Sedaj napišite še polarno implementacijo kompleksnih števil, kjer ima vsako kompleksno število radij in kot (angl. magnitude in argument). Priporočilo: Seštevanje je v polarnih koordinatah zahtevnejše, zato si ga pustite za konec (lahko tudi za konec stoletja).
module Polar : COMPLEX = struct
type t = {magn : float; arg : float}
(* Pomožne funkcije za lažje življenje. *)
let pi = 2. *. acos 0.
let rad_of_deg deg = (deg /. 180.) *. pi
let deg_of_rad rad = (rad /. pi) *. 180.
let eq x y = failwith "later"
(* Dodajte manjkajoče! *)
end
module Polar : COMPLEX