Uvod v OCaml

Funkcijsko programiranje je pristop k pisanju programov prek sestavljanja funkcij in njihove uporabe na vrednostih. Nasproten pristop bi bilo na primer imperativno programiranje, v katerem programe pišemo kot zaporedja ukazov, ki spreminjajo računalnikovo stanje. Programi, napisani v funkcijskem stilu, so dostikrat krajši in preglednejši, poleg tega pa dostikrat omogočajo porazdeljeno računanje. 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 Toploop.load_lambda in file "toplevel/toploop.ml", line 212, characters 17-27

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 τ1 * τ2 * … * τ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.

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 tipel list, kjer je tipel 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 tiparg -> tiprez, kjer je tiparg tip argumenta funkcije, tiprez 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 pa 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

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>

kjer sta fst in snd projekciji na prvo in drugo komponento para, 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 "[61]", line 3, characters 4-12:
3 |   | "Matija" -> "Dober dan, gospod predavatelj!"
        ^^^^^^^^
Warning 11: 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 "[63]", lines 1-3, characters 23-30:
1 | .......................function
2 |   | "Matija" -> "Dober dan, gospod predavatelj!"
3 |   | "Filip" | "Žiga" -> "Oj!"
Warning 8: 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 ("[63]", 1, 23).
Raised at nepopoln_pozdrav in file "[63]", line 1, characters 23-111
Called from Toploop.load_lambda in file "toplevel/toploop.ml", line 212, characters 17-27

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 "[70]", 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 množi, 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]