(Repost mog starog tutoriala o Scheme programskom jeziku koji je do sada čamio u Pages dijelu ovog bloga…)
U ovom tekstu opisani su osnovni elementi jednog od dijalekta LISP-a, programskog jezika Scheme. Scheme je bitno pojednostavljeni i pročišćeni dijalekt LISP-a, i zbog toga je idealan za učenje, iako mu okorjeli LISP-eri zamjeraju da je zbog toga igračka od jezika. Razlike između Scheme i ostalih popularnih LISP dijalekata se mogu bez problema zanemariti pri prvom susretu sa ovim programskim jezicima – jedino što odmah upada u oči je malo drugačija sintaksa (LISP ima defun, Scheme ima define, itd).
Napomena oko velikih i malih slova – Scheme ne razlikuje velika i mala slova u imenima varijabli i ključnih rijeći, tako da je potpuno svejedno pišete li npr. DEFINE, define, ili DeFiNe. U ovom tekstu koristit ću velika slova prilikom opisivanja, a mala slova prilikom navođenja primjera koda.
Prefiks notacija, odnosno sve je funkcija
Ako želite zbrojiti dva broja u recimo C-u, napisali biste nesto tipa:
1 + 2
u Scheme-i, to se radi ovako:
(+ 1 2)
Na prvi pogled, izgleda zbunjujuće i ne baš previše praktično. Ovakva sintaksa je pravi izvor šoka za sve one koji se prvi put susreću sa LISP jezicima. No, stvar itekako ima smisla, a ovdje ću malo pojasniti i zašto.
Što zapravo predstavlja ‘+‘? Pa, to je operator, rekli bi programeri. S druge strane, matematičari bi rekli da je to funkcija (koja zbraja svoje argumente). Funkcije smo navikli pisati u prefiks notaciji (npr f(x,y), a ne x f y); eto razloga.
No, ovo je ipak programiranje a ne matematika. A ionako čak i matematičari pišu ‘+‘ kao infiks operator, zašto sad komplicirati? Zato jer u Schemi
(kao i svim drugim LISP-oidima), ‘+‘ i jest prava pravcata funkcija. Funkcije se u Schemi pozivaju tako da se navede tzv. forma:
( funkcija arg1 arg2 ... )
Prvi element forme interpretira se kao funkcija, kojoj se prosljeđuju drugi elementi kao argumenti. Iz gornjeg primjera, dakle, ako želimo zbrojiti brojeve 1 i 2, to radimo tako da funkciji ‘+‘ proslijedimo te brojeve kao argumente, dakle:
(+ 1 2)
Evo, vidite da ovo ipak ima nekog smisla :-))
Zapravo nije sve funkcija
Pa, dobro, malo sam pojednostavio stvari i lagao. Ipak nije sve funkcija. Naime, kad bismo sve shvatili kao funkciju, neke stvari bi postale komplicirane za izvesti. Primjerice, ‘if‘:
(if (= y 0) 0 (/ x y))
Namjera nam je da u slučaju da je y jednak 0 vratimo vrijednost nula, a inače podijelimo x i y. No, ako je ‘if‘ obična funkcija, prvo će se evaluirati njezini argumenti, a tek nakon toga će se njihove vrijednosti proslijediti ‘if‘ kao parametri. Ali to ne želimo! Želimo da se samo jedan dio evaluira, i to ovisno o nekom uvjetu. Očito to ne možemo izvesti sa čistim funkcijama.
Ovo se izvodi pomoću tzv. specijalnih formi. One su također oblika:
( ključna-riječ ... )
Ali u ovom slučaju ključna-riječ označava da se radi o specijalnoj formi a ne o pozivu funkcije. Sintaksa svake specijalne forme je posebna, no ima ih malo, a one najvažnije mogu navesti i ovdje:
- IF
- Specijalna forma IF testira vrijednost uvjet (to može biti i funkcija koja vraća neku vrijednost), te ako je vrijednost istinita, evaluira i vraća then vrijednost (to opet može biti funkcija koja vraća neku vrijednost). Prošireni oblik podržava i else-izraz.
(if uvjet onda-izraz)
(if uvjet onda-izraz inace-izraz)
- DEFINE
- Specijalna forma koja pridružuje vrijednost varijabli.
(define varijabla izraz)
- SET!
- Specijalna forma koja mijenja vrijednost varijabli. Scheme je funkcijski jezik u kojemu se u pravilu varijablama ne mijenja vrijednost osim kad je to apsolutno nužno (za razliku od recimo Haskella koji je čisti funkcijski jezik, u kojem je nemoguće promijeniti vrijednost varijabli).
(set! varijabla izraz)
- LAMBDA
- Specijalna forma koja kreira i vraća novu funkciju. Više o ovome ću spomenuti u zasebnom poglavlju. Sintaksa je:
(lambda (argument ...) tijelo_funkcije)
Zapravo je sve podatak
Evo, opet si uskačem riječ ;-)
Primjetite da se u LAMBDA formi nigdje ne spominje naziv nove funkcije. To je zato što nova funkcija niti nema imena. Kako onda možemo koristiti tu novu funkciju? Primjetite da piše da LAMBDA vraća novu funkciju. Što to znači?
To znaci da su i funkcije najobičniji podaci u LISP-u. Dakle, ne samo ono što funkcija vraća, već i sama funkcija je podatak. Shodno tome, bez problema možemo napisati:
(define zbroji (lambda (x y) (+ x y)))
(define isti-taj-zbroji zbroji)
(set! zbroji (lambda (x) (+ x 2)))
Ovo prvo pridružuje novostvorenu funkciju varijabli zbroji. Zatim istu tu funkciju (tj. vrijednost varijable zbroji) pridružuje novoj varijabli isti-taj-zbroji, a nakon toga mijenja vrijednost varijable zbroji i to tako da ona sad označava funkciju koja svom argumentu dodaje broj 2.
Zapravo je sve podatak
Koncept varijable u LISP-u se lagano razlikuje od varijabli u, recimo, C-u ili Pascalu. U spomenutim jezicima varijabla obično označava mjesto u memoriji koje može sadržavati neku vrijednost. U LISP-u, varijabla pokazuje na neku vrijednost u memoriji. Definicije su gotovo iste; u čemu je razlika? Koristeći terminologiju iz drugih jezika, sve varijable u LISP-u su reference.
Prva posljedica ovakvog pristupa je u tome da su tipovi podataka vezani uz sam podatak, a ne uz varijablu koja pokazuje na njega – dakle, u LISP-u varijable nemaju tipove (možete to shvatiti kao da su sve varijable tipa ‘void *‘, odnosno pokazivač na bilo što). Što to znači da varijable nemaju tipove? Je li to korisno ili štetno? Ako ne postoji kontrola tipova, što je s izrazima poput (+ 1 “foo”)? Činjenica da varijable nemaju tipove omogućuje veliku fleksibilnost programeru. S druge strane, zbog takvog pristupa potrebno je u određenim trenucima tijekom izvođenja programa provjeravati tip varijable. Primjer funkcije zbrajanja koja prvo provjerava jesu li oba podatka tipa integer:
(define zbroji (lambda (x y)
(if (and (integer? x) (integer? y))
(+ x y)
(display "greska: brojevi trebaju biti integeri"))))
CAR, CDR i CONS
Jedan od osnovnih pojmova u LISP-u je CONS ćelija (cons cell). Što je to? To bismo mogli definirati kao strukturu koja se sastoji od dva polja, zvana CAR i CDR.
Za one vične C jeziku, ono sto je u LISP-u CONS ćelija mogli bismo u C-u definirati kao:
struct cons {
void *car;
void *cdr;
};
Zašto ovdje koristim ‘void *‘? U C-u, tip ‘void *‘ oznacava pokazivač na bilo koji tip. U LISP-u, varijable nemaju tipove.
Primjer Scheme koda koji kreira novu CONS ćeliju:
(define x (cons 3 4))
Ovom naredbom kreirali smo CONS ćeliju čija je CAR vrijednost 3 a CDR vrijednost 4, i tu ćeliju pridružili varijabli ‘x‘. Istu stvar mogli smo dobiti sa:
(define x '(3 . 4))
Apostrof (quote) znači da se izraz citira (odnosno da taj izraz Scheme ne smije shvatiti kao naredbu koju treba izvršiti nego kao podatak). Unutar izraza, točka (‘.‘) odvaja CAR i CDR polja ćelije.
Usporedbe radi, istu stvar u C-u radi:
struct cons *x = malloc(sizeof(struct cons));
x->car = 3; x->cdr = 4;
Kratko objašnjenje zašto CONS, CAR i CDR imaju baš takva imena. CONS jos ima nekog smisla, od recimo CONStruct cell, ali čemu CAR i CDR? Objašnjenje leži u samom dizajnu LISP interpretera. LISP se prvo prevodi u odredjeni oblik stogovno-orjentiranog koda (tipa P-Code za pascal, JVM za Javu ili CLR za .NET). U virtualnom procesoru koji se koristio
u tu svrhu, za realizaciju CONS ćelije koristio se jedan registar, koji je imao dva dijela: adresni i dio za povezivanje. Mnemonik CAR je označavao instrukciju Contents of Address part of Register, a CDR je predstavljao Contents of Decrement part of Register.
Liste
Zašto je CONS ćelija toliko bitna? Zato što je ona osnovni građevni element pri izradi kompliciranijih struktura podataka. Jedan primjer je:
'(1 . (2 . (3 . '())))
Ovaj izraz definira CONS ćeliju čiji je prvi element broj 1, a drugi element CONS čelija ćiji je prvi element broj 2, a drugi element CONS ćelija čiji je prvi element broj 3, a drugi je null pointer (zvan još i NIL ili prazna lista).
Ok, ovo je definitivno kompliciranija struktura podataka, ali što to predstavlja? Ako se prisjetimo korištenja jednostruko povezanih lista sjetit ćemo se da je jedno polje čvora liste sadržavalo element, a drugo pokazivač na slijedeći čvor liste. U gornjem primjeru imamo točno taj slučaj. Ako to prikažemo graficki:
.-----+-----. .-----+-----. .-----+-----.
| car | cdr *-----> | car | cdr *-----> | car | cdr *-----> '()
`--*--+-----' `--*--+-----' `--*--+-----'
| | |
1 2 3
Dakle, gornja komplicirana struktura stvarno tvori listu. Posto se u LISP programskim jezicima liste koriste vrlo često (moglo bi se reći i češće nego “čiste” CONS ćelije), postoji i ljepši i jednostavniji oblik zapisivanja liste. Gornji izraz ekvivalentan je sa:
'(1 2 3)
Primjetite da nema točaka izmedju elemenata liste. Također, umjesto pisanja:
(cons 1 (cons 2 (cons 3 '())))
možemo listu definirati sa:
(list 1 2 3)
Kako pristupati elementima liste? Opet pomoću CAR i CDR polja. Prema ovakvoj implementaciji liste, očito je da CAR polje određuje prvi element liste, dok CDR polje određuje ostatak liste. Dakle vrijedi:
(car '(1 2 3)) => 1
(cdr '(1 2 3)) => '(2 3)
(car (cdr '(1 2 3))) => 2
Prolaženje kroz sve elemente liste tada se može napraviti jednostavnom rekurzijom. Primjer funkcije koja vraća zbroj svih brojeva u listi:
(define zbroj (lambda (lista)
(if (null? lista) 0
(+ (car lista)
(zbroj (cdr lista))))))
Ovo se tumači kao: Ako je lista prazna, zbroj je 0, inače je zbroj dobiven zbrajanjem trenutnog elementa sa zbrojem ostatka liste.
Stabla
Osim lista, CONS ćelija je pogodna i za izradu binarnih stabala. U tu svrhu CAR se proglasi referencom na lijevo pod-stablo a CDR referencom na desno pod-stablo.
Ovakva upotreba CONS ćelije koristi se za izradu unutrašnjih čvorova stabla, a za listove se može koristiti bilo koji podatak. Ovakva upotreba možda zvuči restriktivna jer se podaci mogu zapisivati samo u listove, ali za većinu primjena ovakva je sasvim dovoljna, a u slučaju da nam treba podatak i u unutrašnjim čvorovima, stvar možemo dodatno zakomplicirati (recimo proglasiti CAR podatkom, a CDR referencom na CONS ćeliju koja pokazuje na lijevo i desno podstablo).
Za primjer, evo binarnog stabla u kojem slova označavaju unutrašnje čvorove a brojevi podatke u listovima:
A
B C
D E F G
1 2 3 4 5 6 7 8
U Scheme-i ovaj podatak možemo izgraditi počevsi sa dna:
(define D (cons 1 2))
(define E (cons 3 4))
(define F (cons 5 6))
(define G (cons 7 8))
(define B (cons D E))
(define C (cons F G))
(define A (cons B C))
Naravno, ne moramo stablo ovako rastavljati na dijelove. Cijelu stvar smo mogli odmah definirati kao:
(define A (cons (cons (cons 1 2) (cons 3 4))
(cons (cons 5 6) (cons 7 8))))
ili
(define A '( ( (1 . 2) . (3 . 4) ) . ( ( 5 . 6 ) . ( 7 . 8 ) ) ) )
Opet primjer sa zbrajanjem vrijednosti, ovaj put za stablo. U Scheme-i bismo to mogli napraviti kao:
(define zbroj (lambda (stablo)
(cond ((null? stablo) 0)
((cons? stablo) (+ (zbroj (car stablo))
(zbroj (cdr stablo))))
(else stablo))))
Ovo se tumači kao: Ako je stablo prazno, zbroj je nula; ako stablo ima djecu, zbroj se dobiva zbrajanjem zbroja lijevog i desnog djeteta, inače je zbroj vrijednost trenutnog elementa.
Funkcijsko programiranje i Lambda račun
Sve dosad opisano možda izgleda egzotično ali, složit ćete se, nije ništa specijalno i komplicirano. Na sličan ili identičan način se iste stvari rade i u drugim programskim jezicima. Zato, evo malo egzotike – funkcijsko programiranje. Funkcijsko programiranje polazi od sasvim drugačijih temelja i stajališta od imperativnog programiranja.
Imperativno (naredbeno) programiranje sastoji se od čitanja i pisanja vrijednosti u memoriji, ispitivanju tih vrijednosti i donošenja odluka na temelju tih ispitivanja. Programski jezici poput C-a i Pascala u tom smislu predstavljaju samo napredne izvedbe Turingovih strojeva.
S druge strane, funkcijsko programiranje bazira se na evaluaciji funkcija, odnosno izlaz pojedinih funkcija ovisi isključivo o parametrima same funkcije, bez obzira na trenutno stanje ostatka sustava (“globalne varijable”). U (čistom) funkcijskom programiranju nema tzv. usputnih efekata (side-effects). Primjer funkcije sa usputnim efektima u C-u je npr:
int count = 0;
int update_count(void)
{
return count++;
}
Ovu funkciju svaki put pozivamo sa istim argumentima (odnosno, sa 0 argumenata), ali ona svaki put daje drugačiji rezultat. Sa matematičkog stajališta ovo nema previše smisla. Osim što se to ne sviđa matematičarima, ne sviđa se ni mnogim programerima – naime u ovakvim funkcijama ponekad usputni efekti djeluju na nepredvidljiv način, što cini ovakve programe puno težima za ispravljati (ili ispravno napisati otprve).
Kao drugi primjer pogledajmo ovaj izraz:
i = i + 1;
Sa staništa funkcijskog programiranja, ovaj izraz je besmislica. i će uvijek biti i, a i + 1 će uvijek biti i + 1. Kod funkcijskog programiranja varijable više ne predstavljaju mjesta u memoriji čiju vrijednost možemo promijeniti, već samo naziv za neku specifičnu vrijednost. Stoga, jednom kad se varijabli pridjeli vrijednost, ta vrijednost se ne mijenja. Ova restrikcija također se temelji na odbacivanju usputnih efekata (usputni efekt je promjena vrijednosti varijable i).
I imperativni i funkcijski način programiranja imaju svoje primjene, zato većina programskih jezika podržava i jedan i drugi. Npr u Scheme-i možemo napisati
(set! i (+ i 1))
(ovaj uskličnik je tu da nas podsjeti da postoji usputni efekt) ako baš trebamo.
Slijedeći korak…
Ako ste uspjeli doći pročitati sve do ovdje i nije vam se zavrtjelo u glavi niti vam se čini da je cijela stvar bezveze, svaka čast!
Ako vas zanima više o ovom programskom jeziku, preporučam vam da pogledate slijedeće online knjige posvećene Schemi:
Osim ovih knjiga, mnoštvo drugih resursa možete pronaći i na schemers.org stranici.
Happy Scheming!
