Uvod v OCaml

Uvod v OCaml#

Zaradi vseh teh lastnosti veliko modernih programskih jezikov vpeljuje ideje iz funkcijskega programiranja. Da se bomo lahko osredotočili na te ideje, si bomo ogledali programski jezik OCaml, ki je bil eden prvih in je še danes eden najbolj popularnih funkcijskih jezikov.

Delo z OCamlom#

Poženimo prvi program v OCamlu:

let odgovor = min 8 7 * 6

val odgovor : int = 42

Vidimo lahko več stvari:

vrednosti definiramo s ključno besedo let
OCaml je poleg končne vrednosti izračunal tudi njen tip int
funkcije kličemo tako, da argumente naštejemo brez oklepajev
pri tem ima uporaba funkcij (aplikacija) višjo prioriteto kot računske operacije

Vrednosti lahko definiramo tudi lokalno z izrazom let ... in ...

let odgovor =
    let prvi_delni_izracun = min 8 7 in
    let drugi_delni_izracun = 6 in
    prvi_delni_izracun * drugi_delni_izracun

val odgovor : int = 42

V tem primeru bodo definicije na voljo v delu in ..., izven pa ne:

prvi_delni_izracun

File "[4]", line 1, characters 0-18:
1 | prvi_delni_izracun
    ^^^^^^^^^^^^^^^^^^
Error: Unbound value prvi_delni_izracun

Če želimo, lahko več lokalnih definicij hkrati podamo tako, da jih ločimo z and.

let odgovor =
    let prvi_delni_izracun = min 8 7
    and drugi_delni_izracun = 6
    in
    prvi_delni_izracun * drugi_delni_izracun

val odgovor : int = 42

Razlika med tem in gnezdenimi let ... in ... je v tem, da so vrednosti definirane hkrati, zato se ne morejo nanašati ena na drugo:

let a = 6 in
let b = a + 1 in
a * b

- : int = 42

let a = 6
and b = a + 1 in
a * b

File "[7]", line 2, characters 8-9:
2 | and b = a + 1 in
            ^
Error: Unbound value a

Vgrajeni tipi#

Ena izmed največjih prednosti OCamla je njegov bogat in dovršen sistem tipov. Vsak pravilen program v OCamlu ima svoj tip, ki ga OCaml samodejno preveri pred vsakim izvajanjem, kar polovi ogromno napak.

Tip `int`#

Cela števila pripadajo tipu int, z njimi pa delamo podobno kot v Pythonu:

12 * (34 + 67) - 89

- : int = 1123

Za razliko od Pythona celoštevilsko delimo z /, ostanek pa izračunamo z mod:

22 / 7

- : int = 3

22 mod 7

- : int = 1

OCamlov tip int ne podpira poljubno velikih števil, zato lahko pri nekaterih operacijah pride do prekoračitve obsega:

4611686018427387902 + 1

- : int = 4611686018427387903

4611686018427387902 + 2

- : int = -4611686018427387904

Tip `float`#

Tipu float pripadajo števila s plavajočo vejico, ki jih pišemo kot v Pythonu, razlika pa se pojavi pri operacijah. Kot smo že omenili, OCaml preverja ustreznost tipov, in tako na primer operacija * sprejme dva argumenta tipa int in int tudi vrne. Če ji damo argumente tipa float, se bo OCaml pritožil, saj med tema dvema tipoma strogo loči:

2 * 3.141592

File "[13]", line 1, characters 4-12:
1 | 2 * 3.141592
        ^^^^^^^^
Error: This expression has type float but an expression was expected of type
         int

Operacije, ki sprejemajo števila s plavajočo vejico, se končajo s piko:

12.0 *. (34.0 +. 67.0) -. 89.0

- : float = 1123.

22. /. 7.

- : float = 3.14285714285714279

let pi = 4. *. atan 1.

val pi : float = 3.14159265358979312

cos pi

- : float = -1.

Tipa `string` in `char`#

Nizi pripadajo tipu string, pišemo pa jih med dvojne narekovaje. Pogosta operacija na nizih je stikanje, ki ga pišemo kot ^. Na voljo imamo tudi funkcije za pretvorbo v nize in iz nizov, pri čemer slednje lahko sprožijo napako:

"Programiranje " ^ string_of_int 1

- : string = "Programiranje 1"

6 * int_of_string "7"

- : int = 42

6 * int_of_string "sedem"

Exception: Failure "int_of_string".
Raised by primitive operation at unknown location
Called from Stdlib__Fun.protect in file "fun.ml", line 33, characters 8-15
Re-raised at Stdlib__Fun.protect in file "fun.ml", line 38, characters 6-52
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 89, characters 4-150

Tipu char pripadajo posamezni znaki, ki jih pišemo med enojne narekovaje.

'a'

- : char = 'a'

Tip `bool`#

Tipu bool pripadajo logične vrednosti, kjer imamo na voljo obe logični konstanti ter običajne logične operacije, pri čemer konjunkcijo pišemo kot &&, disjunkcijo pa kot ||:

false && not (false || true)

- : bool = false

Na voljo imamo tudi običajne relacije za primerjavo:

3 < 5 || 3 >= 5

- : bool = true

Za primerjavo enakosti uporabljamo operaciji = in <>, ki argumente primerjata glede na vrednosti. Na voljo sta tudi primerjavi == in !=, ki gledata identičnost argumentov in ju uporabljamo le takrat, kadar smo v to popolnoma prepričani, saj nam sicer dajeta nepričakovane odgovore:

"A" == "A"

- : bool = false

Dobili smo false, ker je OCaml naredil dva različna niza in ju shranil na dve različni mesti v pomnilniku. Če si naredimo en sam niz, pa enakost velja:

let a = "A"

val a : string = "A"

a == a

- : bool = true

Logične vrednosti lahko uporabljamo v pogojnih izrazih:

if 3 <> 5 then 10 else 20

- : int = 10

Pogojni izrazi so lahko tudi vsebovani v drugih izrazih. Na primer, funkcija v spodnjem izrazu je rezultat pogojnega izraza:

(if 3 = 4 then cos else sin) pi

- : float = 1.22464679914735321e-16

Tipi naborov#

Nabore v OCamlu pišemo med navadne oklepaje, komponente pa ločimo z vejico. Včasih lahko oklepaje tudi izpustimo, vendar tega raje ne počnimo.

(1, 2 < 3, cos pi)

- : int * bool * float = (1, true, -1.)

1, 2, 3

- : int * int * int = (1, 2, 3)

Kot vidimo, imajo nabori tip označen s kartezičnim produktom τ₁ * τ₂ * … * τ_n, kjer so τ_i tipi posameznih komponent. Naborov velikosti ena ni, ker niso potrebni, nabor velikosti 0 pa je natanko en:

()

- : unit = ()

Ker kartezičnega produkta nič tipov ne moremo zapisati, tip praznega nabora označujemo z unit.

Na parih (torej naborih velikosti 2) imamo na voljo funkciji fst in snd, ki projecirata na prvo in drugo komponento.

fst (5, true)

- : int = 5

snd (5, true)

- : bool = true

Tip seznamov#

Sezname v OCamlu pišemo med oglate oklepaje, vrednosti pa ločimo s podpičji. Vse vrednosti v seznamih morajo biti enakega tipa, seznam pa ima potem tip oblike tip_el list, kjer je tip_el tip komponent.

[1; 2; 3; 4]

- : int list = [1; 2; 3; 4]

['a'; 'b'; 'c'; 'd']

- : char list = ['a'; 'b'; 'c'; 'd']

Če se zatipkamo in namesto podpičij pišemo vejice, dobimo seznam z enim elementom, ki je nabor (spomnimo se, da lahko nabore pišemo brez oklepajev):

[1, 2, 3, 4]

- : (int * int * int * int) list = [(1, 2, 3, 4)]

Sezname sestavljamo z dvema operacijama. Z :: sestavimo nov seznam z dano glavo in repom:

1 :: [2; 3; 4]

- : int list = [1; 2; 3; 4]

Kasneje bomo videli, da ima :: prav posebno vlogo, saj je tako imenovani konstruktor seznamov. Vsak neprazen seznam je namreč prek :: sestavljen iz glave in repa. Tudi [1; 2; 3; 4] je v resnici samo okrajšava za 1 :: (2 :: (3 :: (4 :: [])))).

Če želimo stakniti dva seznama, pa uporabimo funkcijo @:

[1; 2; 3] @ [4; 5; 6]

- : int list = [1; 2; 3; 4; 5; 6]

Za vajo lahko preverite, kateri izmed spodnjih seznamov so veljavni:

[1; 2] :: [3; 4]

NE

1 :: 2 :: 3 :: []

DA

[1; 2] @ [3; 4]

DA

1 @ 2 @ [3]

NE

[1, 2] @ [3]

NE

1 :: 2 :: 3

NE

[1; 2] @ []

DA

[1; 2] :: []

DA

Tipi funkcij#

Vsaka vrednost v OCamlu ima svoj tip, tudi funkcije. Tip funkcije je oblike tip_arg -> tip_rez, kjer je tip_arg tip argumenta funkcije, tip_rez pa tip njenega rezultata. Na primer string_of_int vzame int in vrne string:

string_of_int

- : int -> string = <fun>

Podoben tip imajo tudi funkcije več argumentov (kaj točno ta tip predstavlja, pa bomo še videli):

atan2

- : float -> float -> float = <fun>

Definicije funkcij#

Funkcije v OCamlu definiramo podobno kot vrednosti, le da za njihovim imenom naštejemo še imena argumentov:

let kvadriraj n = n * n

val kvadriraj : int -> int = <fun>

Funkcije potem uporabimo kot običajno:

kvadriraj 8

- : int = 64

Na podoben način lahko definiramo funkcije več argumentov:

let zmnozi x y = x * y

val zmnozi : int -> int -> int = <fun>

zmnozi 6 7

- : int = 42

Funkcije so lahko tudi argumenti drugih funkcij. Na primer, spodnja funkcija vzame funkcijo f ter jo dvakrat zaporedoma uporabi na 0. Iz tega sledi, da mora f sprejeti argument tipa int. Ker rezultat f 0 znova podamo f, mora tudi ta biti int, zato je tip funkcije f enak int -> int, kar OCaml sam izračuna:

let dvakrat_na_nic f = f (f 0)

val dvakrat_na_nic : (int -> int) -> int = <fun>

dvakrat_na_nic succ

- : int = 2

let podvoji_in_pristej_ena x = 2 * x + 1

val podvoji_in_pristej_ena : int -> int = <fun>

dvakrat_na_nic podvoji_in_pristej_ena

- : int = 3

Včasih majhnih funkcij kot je zgornja ni smiselno poimenovati. V tem primeru lahko pišemo anonimne funkcije oblike fun arg -> ..., na primer:

dvakrat_na_nic (fun x -> 2 * x + 1)

- : int = 3

Anonimne funkcije lahko sprejmejo tudi več argumentov:

(fun x y -> x * y) 2 3

- : int = 6

Vzorci#

V lokalnih definicijah in argumentih funkcij lahko argumente razstavimo s pomočjo vzorcev. Na primer, namesto:

let razdalja koord1 koord2 =
  let dx = fst koord1 -. fst koord2
  and dy = snd koord1 -. snd koord2
  in
  sqrt (dx ** 2. +. dy ** 2.)

val razdalja : float * float -> float * float -> float = <fun>

lahko pišemo:

let razdalja koord1 koord2 =
  let (x1, y1) = koord1
  and (x2, y2) = koord2 in
  sqrt ((x1 -. x2) ** 2. +. (y1 -. y2) ** 2.)

val razdalja : float * float -> float * float -> float = <fun>

ali še bolje kot:

let razdalja (x1, y1) (x2, y2) =
  sqrt ((x1 -. x2) ** 2. +. (y1 -. y2) ** 2.)

val razdalja : float * float -> float * float -> float = <fun>

Med večimi vzorci se lahko odločimo s pomočjo konstrukta match, ki sprejme več vej, ločenih z |, nato pa vrne prvo, ki ustreza danemu vzorcu. Na primer, namesto

let ustrezen_pozdrav ime =
  if ime = "Matija" then
    "Dober dan, gospod predavatelj!"
  else if ime = "Filip" || ime = "Žiga" then
    "Oj!"
  else
    "Dober dan, " ^ ime ^ "!"

val ustrezen_pozdrav : string -> string = <fun>

raje pišemo:

let ustrezen_pozdrav ime =
  match ime with
  | "Matija" -> "Dober dan, gospod predavatelj!"
  | "Filip" | "Žiga" -> "Oj!"
  | _ -> "Dober dan, " ^ ime ^ "!"

val ustrezen_pozdrav : string -> string = <fun>

Z vzorci lahko razstavljamo tudi sezname, pri čemer lahko z :: seznam razstavimo na glavo in rep. Pozor: @ v vzorcih ne more nastopati, saj je funkcija in ne konstruktor.

let citiraj_knjigo avtorji naslov =
  match avtorji with
  | [] -> naslov
  | [avtor] -> avtor ^ ": " ^ naslov
  | prvi :: _ -> prvi ^ " in ostali: " ^ naslov

val citiraj_knjigo : string list -> string -> string = <fun>

citiraj_knjigo [] "Skrivnosti podzemlja"

- : string = "Skrivnosti podzemlja"

citiraj_knjigo ["Kos"; "Golob"] "Fizika 1"

- : string = "Kos in ostali: Fizika 1"

Vzorce lahko tudi gnezdimo:

let za_lase_privlecena_funkcija = function
  | [] -> 0
  | [(x, _); (y, z)] -> x + y + z
  | ((_, x) :: _) -> 3 * x

val za_lase_privlecena_funkcija : (int * int) list -> int = <fun>

za_lase_privlecena_funkcija []

- : int = 0

za_lase_privlecena_funkcija [(1, 2)]

- : int = 6

za_lase_privlecena_funkcija [(1, 2); (3, 4)]

- : int = 8

Za funkcije, ki takoj izvedejo match na svojem zadnjem argumentu, lahko uporabimo bližnjico function:

let ustrezen_pozdrav = function
  | "Matija" -> "Dober dan, gospod predavatelj!"
  | "Filip" | "Žiga" -> "Oj!"
  | ime -> "Dober dan, " ^ ime ^ "!"

val ustrezen_pozdrav : string -> string = <fun>

Vsakič, ko pišemo match ali function, moramo biti pozorni na vrstni red vzorcev:

let neustrezen_pozdrav = function
  | ime -> "Dober dan, " ^ ime ^ "!"
  | "Matija" -> "Dober dan, gospod predavatelj!"

File "[64]", line 3, characters 4-12:

3 |   | "Matija" -> "Dober dan, gospod predavatelj!"

        ^^^^^^^^

Warning 11 [redundant-case]: this match case is unused.

val neustrezen_pozdrav : string -> string = <fun>

OCaml nas je opozoril, da druga veja nikoli ne bo uporabljena, saj bo prvi vzorec ustrezal vsem primerom.

neustrezen_pozdrav "Matija"

- : string = "Dober dan, Matija!"

Prav tako nas OCaml opozori, če na kakšen primer pozabimo, saj bo ob izvajanju sicer lahko prišlo do napake:

let nepopoln_pozdrav = function
  | "Matija" -> "Dober dan, gospod predavatelj!"
  | "Filip" | "Žiga" -> "Oj!"

File "[66]", lines 1-3, characters 23-30:

1 | .......................function

2 |   | "Matija" -> "Dober dan, gospod predavatelj!"

3 |   | "Filip" | "Žiga" -> "Oj!"

Warning 8 [partial-match]: this pattern-matching is not exhaustive.

Here is an example of a case that is not matched:

""

val nepopoln_pozdrav : string -> string = <fun>

nepopoln_pozdrav "naključni študent"

Exception: Match_failure ("[66]", 1, 23).
Raised at nepopoln_pozdrav in file "[66]", line 1, characters 23-111
Called from Stdlib__Fun.protect in file "fun.ml", line 33, characters 8-15
Re-raised at Stdlib__Fun.protect in file "fun.ml", line 38, characters 6-52
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 89, characters 4-150

Rekurzivne funkcije#

Če želimo definirati rekurzivno funkcijo, jo moramo podati z let rec:

let rec fakulteta = function
  | 0 -> 1
  | n -> n * fakulteta (n - 1)

val fakulteta : int -> int = <fun>

fakulteta 10

- : int = 3628800

let rec fib = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n - 1) + fib (n - 2)

val fib : int -> int = <fun>

Zgornja definicija je precej neučinkovita, zato si lahko pomagamo s pomožno funkcijo, ki deluje veliko hitreje:

let hitri_fib n =
  let rec aux n a b =
    if n = 0 then a else aux (n - 1) b (a + b)
  in aux n 0 1

val hitri_fib : int -> int = <fun>

Hkrati lahko definiramo tudi več rekurzivnih funkcij:

let rec je_sodo = function
  | 0 -> true
  | n -> je_liho (n - 1)

and je_liho = function
  | 0 -> false
  | n -> je_sodo (n - 1)

val je_sodo : int -> bool = <fun>
val je_liho : int -> bool = <fun>

Primerjava s Pythonom#

Kljub temu da Python in OCaml podpirata precej podobnih konceptov (funkcije, pogojne stavke, sezname, nabore, tipe, …), pa imata tudi kar nekaj razlik. Ena izmed njih je način, na katerega te konstrukte uporabljamo. OCaml je deklarativni jezik, kar pomeni, da programe sestavljamo s pomočjo definicij vrednosti. Natančneje, OCaml je funkcijski jezik, saj pri sestavljanju ključno vlogo igrajo funkcije (poznamo tudi logične deklarativne jezike, kot na primer Prolog, kjer vrednosti opisujemo s pogoji, ki računalnik vodijo do končne rešitve). Na primer, \(10!\) v OCamlu najenostavneje izračunamo tako, da napišemo njeno matematično definicijo:

let rec fakulteta n =
  if n = 0 then 1 else n * fakulteta (n - 1)
in fakulteta 10

Kljub temu da tudi Python vsebuje prvine funkcijskega programiranja, pa je v osnovi imperativni (zaradi vloge objektov pa tudi objektni) jezik, kjer računalnik usmerjamo prek zaporedja ukazov, ki začetno stanje spravijo v želeno stanje. Na primer, fakulteto bi izračunali tako, da bi si izbrali spremenljivko za hranjenje vrednosti, nato pa to spremenljivko postopoma spreminjali, dokler ne bi dobili iskanega števila:

fakulteta = 1
for i in range(1, 11):
    fakulteta *= i

Ena izmed razlik med jezikoma je tudi v sistemu tipov. OCaml tipe preverja statično, torej še pred izvajanjem. Če napišemo:

let je_majhen x =
  if x < 10 then "Da" else false

File "[73]", line 2, characters 27-32:
2 |   if x < 10 then "Da" else false
                               ^^^^^
Error: This expression has type bool but an expression was expected of type
         string

dobimo napako, še preden funkcijo pokličemo. V nasprotju z OCamlom bo Python enako definicijo sprejel:

def je_majhen(x):
    return 'Da' if x < 10 else False

vendar bo ta v nekaterih primerih delala uspešno, v drugih pa ne:

>>> je_majhen(3) + '!'
'Da!'

>>> je_majhen(10) + '!'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s)
  for +: 'bool' and 'str'

Kot vidimo v opozorilu, je Python tipe sicer preveril (zato računalnik ni na slepo delal z ničlami in enicami, kar bi lahko vodilo do hujših napak), vendar šele takrat, ko smo program izvedli. Pravimo, da ima Python dinamičen sistem tipov.

Prav tako so OCamlovi tipi precej bogatejši, na primer za spodnji seznam in funkcijo OCaml zelo natančno pove, kakšne oblike sta:

[(1, ['a']); (10, []); (0, ['x'; 'y'])]

- : (int * char list) list = [(1, ['a']); (10, []); (0, ['x'; 'y'])]

fun x -> [(x ^ "!", 0)]

- : string -> (string * int) list = <fun>

Python pa sporoči le to, da sta seznam in funkcija:

>>> type([(1, ['a']), (10, []), (0, ['x', 'y'])])
<type 'list'>

>>> type(lambda x: [(x + '!', 0)])
<type 'function'>

Polimorfizem#

Vsaka vrednost v OCamlu ima natančno določen tip. Kakšen pa je tip funkcije @, saj lahko z njo stikamo tako sezname logičnih vrednosti, sezname števil, sezname seznamov števil, …

[true; false] @ [false; true]

- : bool list = [true; false; false; true]

[1; 2] @ [3; 4; 5]

- : int list = [1; 2; 3; 4; 5]

[[1]] @ [[2; 3]; [4; 5]]

- : int list list = [[1]; [2; 3]; [4; 5]]

Je @ torej tipa bool list -> bool list -> bool list ali int list -> int list -> int list ali int list list -> int list list -> int list list? V resnici je lahko tipa α list -> α list -> α list za poljuben tip α. To v OCamlu označimo kot 'a list -> 'a list -> 'a list. In res:

(@)

- : 'a list -> 'a list -> 'a list = <fun>

Vrednostim, ki imajo v tipih spremenljivke, pravimo parametrično polimorfne. Polimorfne zaradi tega, ker lahko delujejo pri več tipih, parametrično pa zato, ker pri vseh tipih delujejo na enak način. Poznamo tudi tako imenovani ad hoc polimorfizem, kjer pri nekaterih tipih funkcije delujejo na en način, pri nekaterih na drugačen, pri tretjih pa sploh ne. Primer takega polimorfizma je na primer + v Pythonu: števila sešteva, sezname in nize stika, na funkcijah pa ne deluje. OCaml ad hoc polimorfizma nima, ker povzroča težave pri določanju tipov.

V parametrično polimorfnih funkcijah lahko nastopa več parametrov. Na primer, projekcija na prvo komponento vzame par iz kartezičnega produkta poljubnih dveh tipov in slika v prvega:

fst

- : 'a * 'b -> 'a = <fun>

Tudi nekatere vrednosti so parametrično polimorfne:

[]

- : 'a list = []

([], [[]], ([], 3))

- : 'a list * 'b list list * ('c list * int) = ([], [[]], ([], 3))

Seveda pa so najbolj koristne polimorfne funkcije, na primer:

let rec dolzina =
  function
  | [] -> 0
  | _ :: xs -> 1 + dolzina xs

val dolzina : 'a list -> int = <fun>

dolzina [10; 20; 30]

- : int = 3

let rec preslikaj f =
  function
  | [] -> []
  | x :: xs -> f x :: preslikaj f xs

val preslikaj : ('a -> 'b) -> 'a list -> 'b list = <fun>

preslikaj succ [10; 20; 30]

- : int list = [11; 21; 31]