Scheme (programski jezik)

Из Википедије, слободне енциклопедије



Scheme
Racket logo
Logo programskog jezika Scheme
Originalni naziv Scheme
Izgovara se Skim
Model fukncionalni, proceduralni
Pojavio se 1975
Autor(i) Guy L. Steele
Gerald Jay Sussman
Aktuelna verzija R7RS (ratifikovan standard)
Datum aktuelne verzije 2013
Tipovi promenljivih dinamički, jako tipiziran
Implementacije mnogobrojne (pogledaj: )
Uticaji Lisp, Algol
Uticao na Common Lisp, Racket, Haskell, Ruby, Scala
Veb-sajt www.schemers.org

Scheme je multiparadigmatski programski jezik opšte namene. Nastao je 1970-ih godina pod uticajem jednog imperativnog (Algol-60) i jednog funkcionalnog (Lisp) programskog jezika. Scheme je u početku bio zvan "Schemer", u skladu sa tradicijom imenovanja jezika koji potiču od Lisp-a (kao što su npr. Planner ili Conniver).

Scheme su 1975. godine predstavili Gerald J. Sussman i Guy L. Steele serijom papira na koje se sada referiše kao "Lambda papiri". Razvijen je u MIT-ovim laboratorijama, prvobitno namenjen za istraživanja i podučavanje studenata.

Smatra se jednim od dva glavna dijalekta programskog jezika Lisp. Za razliku od Common Lisp-a, drugog glavnog dijalekta, Scheme prati filozofiju minimalističkog dizajna definisanjnem malog standardnog jezgra jezika (primitivnih konstrukata), ali sa moćnim alatima za proširenje jezika. Jezik definišu dva standarda:

  • IEEE 1178-1990 (R1995) – službeni standard [1]
  • RnRS (Revisednth Report on the Algorithmic Language Scheme) - de facto standard

Poslednji ratifikovan je R7RS (2013), dok je najčešče implementiran standard R5RS (1998). [2]

Zbog svoje kompaktnosti i elegancije, Scheme je programski jezik koji se koristi u raznovrsne namene. Međutim, zbog svoje minimalističke filozofije i standarda, nastale su i raznovrsne implementacije i nadogradnje jezika, što dovodi do nekompatibilnosti kodova pisanih u različitim implementacijama. Razilaženja u implementacijama su mnogobrojna, toliko da Scheme-ov upravni odbor naziva Scheme "najnekompatibilnijim programskim jezikom na svetu", pritom govoreći radije o Scheme-u kao o kolekciji dijalekata umesto jedinstvenom jeziku.

Razvoj jezika[уреди]

Poreklo[уреди]

Scheme je nastao 1970-ih kao pokušaj da se razume Carl Hewitt-ov matematički Actor model. U tu svrhu su Sussman i Steele napisali “mali Lisp prevodilac”, koristeći se dijalektom MacLisp kome su pridodali mehanizam za kreiranje aktera i slanje poruka. [3]

Uticaj[уреди]

Scheme je prvi dijalekat Lisp-a koji je zahtevao samu implementaciju kako bi se izvela eliminacija repne rekurzije, dajući time veću podršku funkcionalnom programiranju, kao i drugim tehnikama koje koriste rekurziju. Smatra se da je Scheme imao veliki uticaj na nastanak i razvoj drugog dijalekta Lisp-a, Common Lisp jezika. [4]

R7RS standard[уреди]

Prethodni standard R6RS je izazvao mnogo kontroverznosti zbog svoje glomaznosti, što je odudaralo od prvobitne minimalističke filozofije. Stoga je Scheme-ov upravni odbor koji nadgleda standardizacije 2009. godine objavio nameru da se Scheme podeli na dva jezika – jedan veliki moderni programski jezik pogodan za praktičnu upotrebu i jedan mali pogodan za istraživanja, koji bi bio podskup velikog, pri čemu bi se zadržao samo minimalni podskup podržanih koncepata.

Karakteristike jezika[уреди]

Scheme je prvi, u familiju Lisp jezika, uveo statički doseg identifikatora (енгл. static (lexical) scope). Memorijski prostor za podatke se alocira dinamički i automatski dealocira pomoću sakupljača otpada (енгл. garbage collector). Scheme je jako tipiziran programski jezik, čiji se parametri prenose po vrednosti. Funkije u Scheme-u se tretiraju jednako sa ostalim tipovima podataka. Scheme ima svojstvo homoikoničnosti. Implementacije repne rekurzije se obavljaju pomoću naredbi skoka, pa se time izbegava nepotrebna upotreba memorijskog prostora.[5]

Tipovi podataka[уреди]

Bulov tip podatka[уреди]

U Scheme-u dve Bulove vrednosti se označavaju sa #t za tačno i #f za netačno (ili #T i #F), ali se i prazna lista može koristiti kao oznaka za netačno u nekim implementacijama, dok je bilo koja neprazna lista oznaka za tačno.[а] Za proveru da li je neki tip podatka Bulov, koristi se predikatska funkcija boolean?.

(boolean? #t) 
===> #t
(boolean? "Hello, World!") 
===> #f

Funkcija not se koristi za invertovanje Bulovih vrednosti.

(not #f) 
===> #t
(not #t) 
===> #f
(not "Hello, World!") 
===> #f

Poslednji primer ilustruje da će Scheme svaku vrednost različitu od #f tretirati kao #t.

Numerički tipovi[уреди]

Numerički tipovi u Scheme-u su: celobrojni (42), racionalni (22/7), realni (3.14) i kompleksni (2+3i). Celobrojni tipovi ne moraju biti zapisani dekadno, već mogu i binarno, oktalno ili heksadekadno, pomoću prefiksa #b, #o, #x.[б] Na primer, #b1010 je zapis broja deset u binarnom sistemu.

Karakteri[уреди]

Karakteri u Scheme-u se predstavljaju pomoću prefiksa #\ ispred željenog karaktera. Na primer, #\c predstavlja karakter c. Neki karakteri, kao što su beline, imaju opisna imena: #\newline, #\tab, #\space. Za proveru da li je tip podatka karakter, koristi se predikatska funkcija char?. Još neke od predikatskih funkcija za rad sa karakterima su: char=?, char<?, char<=?, char>?, char>=? (ako char zamenimo sa char-ic, dobijamo funkcije koje ne prave razluku između malih i velikih slova). Primeri:

(char? #\c)
===> #t
(char? 1) 
===> #f
(char? #\;) 
===> #t
(char=? #\a #\a) 
===> #t
(char<? #\a #\b) 
===> #t
(char>=? #\a #\b) 
===> #f
(char-ci=? #\a #\A) 
===> #t
(char-ci<? #\a #\B) 
===> #t

Za konverziju velikih u mala slova i obrnuto, koriste se funkcije char‑downcase i char‑upcase.

Simboli[уреди]

Simboli se koriste kao identifikatori. Zadaju se sekvencom karaktera i jedino ograničenje prilikom zadavanja imena simbola jeste da se ne pomešaju sa ostalim tipovima podataka. Tako, simbol može biti ovo-je-simbol, <=>, !#$*, i24o, ali ne 16, -i, #t, "ovo-je-string". Zbog upotrebe kao identifikatora, simboli se evaluiraju u onu vrednost koju imenuju. Da ih Scheme ne bi tako evaluirao, potrebno je koristiti standardnu formu quote:

(quote xyz)
===> xyz

Zbog česte upotrebe, moguće je quote zameniti sa ', pa je (quote xyz) ekvivalentno sa 'xyz.

Za proveru da li je neki tip podatka simbol, koristi se predikatska funkcija symbol?:

(define xyz 10)
(symbol? 'xyz)
===> #t
(symbol? xyz)
===> #f ; jer se xyz evaluira kao 10
(symbol? 42)
===> #f

Niske i vektori[уреди]

Niske (stringovi) predstavljaju nizove karaktera. Definišu se umetanjem željenih karaktera između dva znaka navodnika.

"Zdravo, svete!"
===> "Zdravo, svete!"

Vektori su slični niskama, ali njihovi elementi ne moraju biti isključivo karakteri. Dakle, vektori za svoje elemente mogu imati bilo šta, pa čak i same vektore. Vektori imaju znak # kao svoj prefiks, za kojim sledi par zagrada u kojima su navedeni elementi, isključivo odvojeni razmakom. Na primer, #(0 1 2 3).
Funkcije za rad sa niskama i vektorima su gotovo identične. Za kreiranje niske, odnosno vektora, koristi se funkicja string, odnosno vector.Za alokaciju niske (vektora) određene dužine, koristi se make-string (make-vector).Postavljane pojedinačnih elemenata niske (vektora) na određenu vrednost se vrši pomoću funkcije string-set! (vector-set!).[в] Za referisanje na pojedinačan element niske (vektora), koristi se string-ref (vector-ref). Provera da li je niska (vektor) se obavlja predikatskom funkcijom string? (vector?).

(define zdravo (string #\Z #\d #\r #\a #\v #\o))
zdravo
===> "Zdravo"
(string-ref zdravo 0)
===> #\Z

(define v (make-vector 2 0))
v
===> #(0 0)
(vector-set! v 0 10)
v
===> #(10 0)

Uređeni parovi i liste[уреди]

Par je struktura podataka koja se sastoji od dva elementa, proizvoljnog tipa. Elementi para se tradicionalno označavaju sa car, prvi element para i cdr, drugi element para. Upravo tako izgledaju i funkcije za pristup elementima para, car i cdr. Za konstrukciju para se koristi funkcija cons.

(cons 1 #t)
===> (1 . #t)
(car (cons 1 #t))
===> 1
(cdr (cons 1 #t))
===> #t

Liste su specijalni slučaj ugnježdenih parova. Kod lista svaki drugi član para je opet par, sve do poslednjeg koji sadrži praznu listu, (), kao svoj drugi element.

(cons 1 (cons 2 (cons 3 (cons 4 '()))))
===> (1 2 3 4)

Konverzije između tipova podataka[уреди]

Scheme poseduje veliki broj funkcija za konverziju jednog tipa podatka u drugi. U tabeli Standardne procedure definisane R5RS standardom su navedeni tipovi konverzija koje Scheme podržava. Primer:

(string->list "hello") 
===> (#\h #\e #\l #\l #\o)
(number->string 16) 
===> "16"
(string->number "16")
===> 16
(string->number "Ovo nije broj!")
===> #f
(string->number "1010" 2) 
===> 10 ; jer je "1010" zapis boja deset u binarnom sistemu

Primitivne numeričke funkcije[уреди]

Scheme sadrži primitivne funkicje za osnovne aritmetičke operacije. To su +, -, * i / za sabiranje, oduzimanje, množenje i deljenje. + i * mogu imati nula ili više parametara. Ako se +, odnosno *, pozove bez parametara, vraća se 0, odnosno 1. U slučaju da se proslede argumenti, vrši se njihovo sabiranje, odnosno množenje. - i / mogu imati jedan ili više parametara. Za -, u slučaju više od jednog argumenta, od prvog se oduzimaju ostali, a slično i za /. U slučaju jednog argumenta, za - se vraća suprotan broj vrednost, a za / recipročna vrednost. Primeri:

Izraz Rezultat
175 175
(+) 0
(* 7 8) 56
(+ 10 12 14) 36
(- 24 (* 2 6)) 12
(/ 28 7 2) 2
(/ 4) 0.25

Postoji i veliki broj drugih numeričkih funkcija u Scheme-u, među kojima su mod[г], round, max, min, log, sin, expt i sqrt.[д]

Numeričke predikatske funkcije[уреди]

Predikatska funkcija je ona koja vraća Bulov tip podatka. Scheme poseduje kolekciju predikatskih funkcija za numeričke tipove. Među njima su:

Funkcija Značenje
= Jednako
<> Različito
> Veće od
< Manje od
>= Veće ili jednako
<= Manje ili jednako
number? Da li je broj?
integer? Da li je ceo broj?
rational? Da li je racionalan broj?
real? Da li je realan broj?
complex? Da li je kompleksan broj?
even? Da li je paran?
odd? Da li je neparan?
zero? Da li je nula?

Imena svih predikatskih funkcija se završavaju upitnikom.

Definisanje funkcija[уреди]

Scheme program jeste kolekcija funkcija, pa pisanje programa podrazumeva definisanje velikog broja funkcija. Bezimena funkcija se konstruiše pomoću ključne reči lambda i predstavlja lambda izraz. Na primer, (lambda (x) (* x x)) je bezimena funkcija koja vraća kvadrat svog numeričkog argumenta. Ova funkcija se može koristiti kao i bilo koja imenovana funkcija, tako što se stavi na početak liste koja sadrži argument funkcije. Na primer, sledeći izraz vraća 49:

((lambda (x) (* x x)) 7)

Lambda izrazi mogu imati i veći broj argumenata.

Scheme-ova funkcija specijalne forme define služi da veže ime za vrednost ili lambda izraz. (define simbol izraz) se koristi da veže ime za vrednost. Na primer:

(define pi 3.14159)
(define two_pi (* 2 pi))

Nakon ovoga pi će se interpretirati kao 3.14159, a two_pi kao 6.28318.[ђ]
Druga upotreba define funkcije jeste da veže lambda izraz za ime. U ovom slučaju, define uzima dve liste kao argumente. Prva sadrži prototip funkcije, ime za kojim slede argumenti. Druga sadrži izraz za koji se ime vezuje. Ovo se može opisati sledećim izrazom,
define (ime_funkcije parametri) (izraz))
Primer korišćenja:

(define (kvadrat broj)
 (* broj broj)
)
(kvadrat 5)
===> 25

Još jedan primer:

(define (hipotenuza kateta1 kateta2)
 (sqrt (+ (kvadrat kateta1) (kvadrat kateta2)))
)
(hipotenuza 3 4)
===> 5

Kontrola toka[уреди]

Postoji više načina kontrole toka u Scheme-u.
Na primer, pomoću funkcije if koja ima tri parametra i koja je opšteg oblika (if predikat then_izraz else_izraz). Primer:

(define (pozitivan x)
(if (> x 0) #t #f)
)
(pozitivan 5)
===> #t

Dalje, korišćenjem funkicje specijalne forme cond. cond nema fiksiran broj parametara i svaki parametar predstavlja par, predikat - izraz. Uopšteni oblik ove funkcije izgleda ovako: (cond (predikat1 izraz1) (predikat2 izraz2) . . . (predikatN izrazN) [(else izrazN+1)] ) [е]
Predikati parametara se evaluiraju jedan po jedan, počevši od prvog navedenog, sve dok se neki ne evaluira na #t. Potom se evaluira izraz iza prvog tačnog predikata i njegova vrednost predstavlja vrednost cond funkcije. Ako nijedan predikat nije tačan, onda se evaluira izraz iza else, ako postoji, i njegova vrednost se vraća. Ako ne postoji else i nijedan predikat nije tačan, vrednost funkcije cond nije definisana. Primer:

(define (prestupna? godina)
 (cond
 ((zero? (mod godina 400)) #t)
 ((zero? (mod godina 100)) #f)
 (else (zero? (mod godina 4)))
))
(prestupna? 2016)
===> #t

Specijalan slučaj funkcije cond jeste funkicja case.
Još jedan način za kontrolu toka jeste rekurzija. Primer:

(define (faktorijel n)
 (if (<= n 1)
 1
 (* n (faktorijel (- n 1)))
))
(faktorijel 5)
===> 120

Pored ovih funkcija, postoje još when i unless.

Rad sa listama[уреди]

Pre samih funkicja za rad sa listama, neophodno je napomenuti neizostavnu primenu primitivne funkcije quote. Naime, da ne bi došlo do pokušaja interpretiranja liste kao funkcije, odnosno pokušaja evaluacije elemenata liste, koristi se funkcija quote (') koja će vratiti samu listu.
Pored već vićenog načina za kreiranje liste, preko ugnježdenih parova, Scheme nudi i pregledniju opciju pomoću funkcije list.

'(1 2 3 4)
===> (1 2 3 4)
(list 1 2 3 4)
===> (1 2 3 4)

Funkcija car vraća glavu liste, odnosno prvi element liste, a cdr vraća rep liste, odnosno ostatak liste.

(car '(A B C))
===> A
(cdr '(A B C))
===> (B C)
(define (drugi lista) (car (cdr lista)))
(drugi '(A B C))
===> B

Kompozicije funkcija, do četiri funkcije, car i cdr je moguće zapisati pomoću jedne funkcije. Tako, (caar x) je ekvivalentno sa (car (car x)), (cadr x) sa (car (cdr x)), (caddar x) je ekvivalentno sa (car (cdr (cdr (car x))))...

(define (treci lista) (caddr lista))
(treci '(jabuka kruska banana)) ; lista simbola
===> banana

Pristup elementima liste se vrši pomoću list-ref funkcije, dok list-tail funkcija vraća rep liste počev od zadatog elementa.

(define a (list 1 2 3 4))

(list-ref a 1)
===> 2
(list-ref a 3)
===> 4

(list-tail a 0)
===> (1 2 3 4)
(list-tail a 2) 
===> (3 4)

Funkcija cons je, na neki način, inverzna funkcijama car i cdr. Ona konstruiše listu od date glave i repa. Dakle, ako je data neka lista a, rezultat sledeće kompozicije funkcija (cons (car a) (cdr a)) jeste upravo početna lista a.

(cons 'A '())
===> (A)
(cons 'A '(B C))
===> (A B C)
(cons '() '(A B))
===> (() A B)
(cons '(A B) '(C D))
===> ((A B) C D)

Predikatska funkcija null? proverava da li je lista prazna i, kao za sve tipove podataka, postoji funkcija za proveru tipa, list?.

(list? '(1 2 3 4))
===> #t
(null? '())
===> #t

Pregled standardnih formi i procedura jezika[уреди]

Jezik je formalno definisan standrardima R5RS (1998) i R6RS (2007). Tu su opisane standardne forme za pisanje programa, kao i standardne procedure jezika.

Standardne forme[уреди]

Naredna tabela opisuje standardne forme jezika Scheme. Neke od formi se pojavljuju u više od jednog reda, iz razloga što neke forme imaju višestruku funkciju primene u jeziku, te se ne mogu jednoznačno klasifikovati.
Forme obeležene sa "B" u tabeli predstavljaju izvedene "bibliotečke" forme koje su zapravo definisane pomoću nekih drugih, osnovnijih formi. Uglavnom su implementirane kao makroi.

Standardne forme definisane R5RS standardom
Svrha Forme
definisanje define
povezivanje lambda, do (B), let (B), let* (B), letrec (B)
uslovni izrazi if, cond (B), case (B), and (B), or (B)
sekvenca begin [ж]
iteracija lambda, do (B), named let (B)
sintaksna proširenja define-syntax, let-syntax, letrec-syntax, syntax-rules (R5RS), syntax-case (R6RS)
navođenje quote('), unquote(,), quasiquote(`), unquote-splicing(,@)
dodela set!
odloženo izvršavanje delay (B)

Standardne procedure[уреди]

Naredne dve tabele prikazuju standardne procedure definisane R5RS standardom. Standard R6RS je mnogo obimniji i rezime ove vrste ne bi bio tako praktičan i reprezentativan. Neke standardne procedure se pojavljuju u više od jednog reda, iz istog razloga kao kod standardnih formi.

Standardne procedure definisane R5RS standardom
Svrha Procedure
osnovni konstrukti vector, make-vector, make-string, list
predikati za proveru jednakosti eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci?
konverzije tipova podataka vector->list, list->vector, number->string, string->number, symbol->string, string->symbol, char->integer, integer->char, string->list, list->string
numeričke procedure vidi sledeću tabelu
stringovi string?, make-string, string, string-length, string-ref, string-set!, string=?, string-ci=?, string<? string-ci<?, string<=? string-ci<=?, string>? string-ci>?, string>=? string-ci>=?, substring, string-append, string->list, list->string, string-copy, string-fill!
karakteri char?, char=?, char-ci=?, char<? char-ci<?, char<=? char-ci<=?, char>? char-ci>?, char>=? char-ci>=?, char-alphabetic?, char-numeric?, char-whitespace?, char-upper-case?, char-lower-case?, char->integer, integer->char, char-upcase, char-downcase
vektori make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!
simboli symbol->string, string->symbol, symbol?
liste i uređeni parovi pair?, cons, car, cdr, set-car!, set-cdr!, null?, list?, list, length, append, reverse, list-tail, list-ref, memq. memv. member, assq, assv, assoc, list->vector, vector->list, list->string, string->list
predikati za proveru tipa boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?
prekidanje i nastavljanje programa call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind
okruženje eval, scheme-report-environment, null-environment, interaction-environment (opciono)
ulaz/izlaz display, newline, read, write, read-char, write-char, peek-char, char-ready?, eof-object? open-input-file, open-output-file, close-input-port, close-output-port, input-port?, output-port?, current-input-port, current-output-port, call-with-input-file, call-with-output-file, with-input-from-file(opciono), with-output-to-file(opciono)
sistemski interfejs load (opciono), transcript-on (opciono), transcript-off (opciono)
odloženo izvršavanje force
funkcionalno programiranje procedure?, apply, map, for-each
booleans boolean? not

Stringovske i karakterske procedure koje sadrže "-ci" u svom nazivu vrše poređenja koja ne prave razliku između malih i velikih slovnih karaktera.

Standardne numeričke procedure definisane R5RS standardom
Svrha Procedure
osnovni aritmetički operatori +, -, *, /, abs, quotient, remainder, modulo, gcd, lcm, expt, sqrt
relacioni operatori <, <= , >, >=, =
maksimum i minimum max, min
zaokruživanje brojeva floor, ceiling, truncate, round
racionalni brojevi numerator, denominator, rational?, rationalize
kompleksini brojevi make-rectangular, make-polar, real-part, imag-part, magnitude, angle, complex?
predikati za proveru tipa integer?, rational?, real?, complex?, number?
tačnost brojeva inexact->exact, exact->inexact, exact?, inexact?
raznovrsni predikati zero?, negative?, positive?, odd?, even?
trigonometrijske funkcije sin, cos, tan, asin, acos, atan
eksponencijalne funkcije expt, log
ulaz/izlaz number->string, string->number

Napomene[уреди]

  1. U nekim implementacijama se koristi true i false, umesto #t i #f
  2. Prefiks za dekadni je #d, ali se on podrazumeva pa ga nije potrebno navoditi.
  3. Ako je niska (vektor) nepromenljiva, ove funkcije neće raditi.
  4. U nekim implementacijama: modulo
  5. U definiciji jezika se ne pravi razlika između malih i velikih slova prilikom pisanja rezervisanih reči i ugrađenih funkcija. Međutim, neke implementacije zahtevaju korišćenje malih slova.
  6. U oba slučaja, broj cifara se može razlikovati od prikazanog.
  7. else klauza je opciona.
  8. Kljucna rec begin za obeležavanje sekvence (bloka) naredbi je definisana u standardu R5RS, ali ne i u standardu R6RS.

Reference[уреди]

  1. 1178-1990 IEEE Standard for the Scheme Programming Language; IEEE proizvođački broj STDPD14209; ratifikovan na sastanku IEEE-SA Standards Board komisije za pregled standarda (RevCom); 26. mart 2008; NAPOMENA: ovaj dokument nije dostupan na Internetu, ali se može kupiti.
  2. Revised5 Report on the Algorithmic Language Scheme; Richard Kelsey, William Clinger, Jonathan Rees, i drugi; Kluwer Academic Publishers, avgust 1998.
  3. First Report on Scheme Revisited(PDF); Gerald Jay Sussman, Guy L. Steele, Jr; Kluwer Academic Publishers, Boston, decembar 1998.; serijska publikacija ISSN: 1388-3690; Posećeno 9.8.2012.
  4. Common LISP: The Language, 2nd Ed., Guy L. Steele Jr. Digital Press; 1981. knjiški broj ISBN978-1-55558-041-4. "Common Lisp is a new dialect of Lisp, a successor to MacLisp, influenced strongly by ZetaLisp and to some extent by Scheme and InterLisp."
  5. The Scheme Programming Language, 4th Edition,Chapter 1. Introduction, R. Kent Dybvig; The MIT Press; September 30, 2009

Literatura[уреди]