Сцхеме (програмски језик)

Scheme је мултипарадигматски програмски језик опште намене. Настао је 1970-их година под утицајем једног императивног (Алгол-60) и једног функционалног (Лисп) програмског језика. Scheme је у почетку био зван "Schemer", у складу са традицијом именовања језика који потичу од Лисп-а (као што су нпр. Planner или Conniver).

Scheme
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
Implementacije	mnogobrojne (pogledaj: )
Uticaji	Lisp, Algol
Утицао на	Common Lisp, Racket, Haskell, Ruby, Scala
Веб-сајт	www.scheme.org

Scheme су 1975. године представили Gerald J. Sussman и Guy L. Steele серијом папира на које се сада реферише као "Ламбда папири". Развијен је у МИТ-овим лабораторијама, првобитно намењен за истраживања и подучавање студената.

Сматра се једним од два главна дијалекта програмског језика Лисп. За разлику од Common Lisp-а, другог главног дијалекта, Сцхеме прати филозофију минималистичког дизајна дефинисањнем малог стандардног језгра језика (примитивних конструката), али са моћним алатима за проширење језика. Језик дефинишу два стандарда:

• IEEE 1178-1990 (R1995) – службени стандард
• RnRS (Revisednth Report on the Algorithmic Language Scheme) - de facto стандард

Последњи ратификован је R7RS (2013), док је најчешче имплементиран стандард R5RS (1998).

Због своје компактности и елеганције, Scheme је програмски језик који се користи у разноврсне намене. Међутим, због своје минималистичке филозофије и стандарда, настале су и разноврсне имплементације и надоградње језика, што доводи до некомпатибилности кодова писаних у различитим имплементацијама. Разилажења у имплементацијама су многобројна, толико да Scheme-ов управни одбор назива Scheme "најнекомпатибилнијим програмским језиком на свету", притом говорећи радије о Scheme-у као о колекцији дијалеката уместо јединственом језику.

Развој језика

Порекло

Scheme је настао 1970-их као покушај да се разуме Carl Hewitt-ов математички Actor model. У ту сврху су Sussman и Steele написали “мали Лисп преводилац”, користећи се дијалектом MacLisp коме су придодали механизам за креирање актера и слање порука.

Утицај

Scheme је први дијалекат Лисп-а који је захтевао саму имплементацију како би се извела елиминација репне рекурзије, дајући тиме већу подршку функционалном програмирању, као и другим техникама које користе рекурзију. Сматра се да је Scheme имао велики утицај на настанак и развој другог дијалекта Лисп-а, Common Lisp језика.

R7RS стандард

Претходни стандард R6RS је изазвао много контроверзности због своје гломазности, што је одударало од првобитне минималистичке филозофије. Стога је Scheme-ов управни одбор који надгледа стандардизације 2009. године објавио намеру да се Scheme подели на два језика – један велики модерни програмски језик погодан за практичну употребу и један мали погодан за истраживања, који би био подскуп великог, при чему би се задржао само минимални подскуп подржаних концепата.

Карактеристике језика

Scheme је први, у фамилију Лисп језика, увео статички досег идентификатора (енгл. static (lexical) scope). Меморијски простор за податке се алоцира динамички и аутоматски деалоцира помоћу сакупљача отпада (енгл. garbage collector). Scheme је јако типизиран програмски језик, чији се параметри преносе по вредности. Функије у Scheme-у се третирају једнако са осталим типовима података. Scheme има својство хомоиконичности. Имплементације репне рекурзије се обављају помоћу наредби скока, па се тиме избегава непотребна употреба меморијског простора.

Типови података

Булов тип податка

У Scheme-у две Булове вредности се означавају са #t за тачно и #f за нетачно (или #T и #F), али се и празна листа може користити као ознака за нетачно у неким имплементацијама, док је било која непразна листа ознака за тачно. За проверу да ли је неки тип податка Булов, користи се предикатска функција boolean?.

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

Функција not се користи за инвертовање Булових вредности.

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

Последњи пример илуструје да ће Scheme сваку вредност различиту од #f третирати као #t.

Нумерички типови

Нумерички типови у Scheme-у су: целобројни (42), рационални (22/7), реални (3.14) и комплексни (2+3и). Целобројни типови не морају бити записани декадно, већ могу и бинарно, октално или хексадекадно, помоћу префикса #b, #o, #x. На пример, #b1010 је запис броја десет у бинарном систему.

Карактери

Карактери у Scheme-у се представљају помоћу префикса #\ испред жељеног карактера. На пример, #\c представља карактер c. Неки карактери, као што су белине, имају описна имена: #\newline, #\tab, #\space. За проверу да ли је тип податка карактер, користи се предикатска функција char?. Још неке од предикатских функција за рад са карактерима су: char=?, char<?, char<=?, char>?, char>=? (ако char заменимо са char-ic, добијамо функције које не праве разлуку између малих и великих слова). Примери:

(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

За конверзију великих у мала слова и обрнуто, користе се функције char‑downcase и char‑upcase.

Симболи

Симболи се користе као идентификатори. Задају се секвенцом карактера и једино ограничење приликом задавања имена симбола јесте да се не помешају са осталим типовима података. Тако, симбол може бити ovo-je-simbol, <=>, !#$*, i24o, али не 16, -i, #t, "ovo-je-string". Због употребе као идентификатора, симболи се евалуирају у ону вредност коју именују. Да их Scheme не би тако евалуирао, потребно је користити стандардну форму quote:

(quote xyz)
===> xyz

Због честе употребе, могуће је quote заменити са ', па је (quote xyz) еквивалентно са 'xyz.

За проверу да ли је неки тип податка симбол, користи се предикатска функција symbol?:

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

Ниске и вектори

Ниске (стрингови) представљају низове карактера. Дефинишу се уметањем жељених карактера између два знака наводника.

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

Вектори су слични нискама, али њихови елементи не морају бити искључиво карактери. Дакле, вектори за своје елементе могу имати било шта, па чак и саме векторе. Вектори имају знак # као свој префикс, за којим следи пар заграда у којима су наведени елементи, искључиво одвојени размаком. На пример, #(0 1 2 3).
Функције за рад са нискама и векторима су готово идентичне. За креирање ниске, односно вектора, користи се функицја string, односно vector.За алокацију ниске (вектора) одређене дужине, користи се make-string (make-vector).Постављане појединачних елемената ниске (вектора) на одређену вредност се врши помоћу функције string-set! (vector-set!). За реферисање на појединачан елемент ниске (вектора), користи се string-ref (vector-ref). Провера да ли је ниска (вектор) се обавља предикатском функцијом 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)

Уређени парови и листе

Пар је структура података која се састоји од два елемента, произвољног типа. Елементи пара се традиционално означавају са цар, први елемент пара и цдр, други елемент пара. Управо тако изгледају и функције за приступ елементима пара, car и cdr. За конструкцију пара се користи функција cons.

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

Листе су специјални случај угњеждених парова. Код листа сваки други члан пара је опет пар, све до последњег који садржи празну листу, (), као свој други елемент.

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

Конверзије између типова података

Scheme поседује велики број функција за конверзију једног типа податка у други. У табели Стандардне процедуре дефинисане Р5РС стандардом су наведени типови конверзија које Scheme подржава. Пример:

(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

Примитивне нумеричке функције

Scheme садржи примитивне функицје за основне аритметичке операције. То су +, -, * и / за сабирање, одузимање, множење и дељење. + и * могу имати нула или више параметара. Ако се +, односно *, позове без параметара, враћа се 0, односно 1. У случају да се проследе аргументи, врши се њихово сабирање, односно множење. - и / могу имати један или више параметара. За -, у случају више од једног аргумента, од првог се одузимају остали, а слично и за /. У случају једног аргумента, за - се враћа супротан број вредност, а за / реципрочна вредност. Примери:

Израз	Резултат
175	175
(+)	0
(* 7 8)	56
(+ 10 12 14)	36
(- 24 (* 2 6))	12
(/ 28 7 2)	2
(/ 4)	0.25

Постоји и велики број других нумеричких функција у Scheme-у, међу којима су mod, round, max, min, log, sin, expt и sqrt.

Нумеричке предикатске функције

Предикатска функција је она која враћа Булов тип податка. Scheme поседује колекцију предикатских функција за нумеричке типове. Међу њима су:

Функција	Значење
=	Једнако
<>	Различито
>	Веће од
<	Мање од
>=	Веће или једнако
<=	Мање или једнако
number?	Да ли је број?
integer?	Да ли је цео број?
rational?	Да ли је рационалан број?
real?	Да ли је реалан број?
complex?	Да ли је комплексан број?
even?	Да ли је паран?
odd?	Да ли је непаран?
zero?	Да ли је нула?

Имена свих предикатских функција се завршавају упитником.

Дефинисање функција

Scheme програм јесте колекција функција, па писање програма подразумева дефинисање великог броја функција. Безимена функција се конструише помоћу кључне речи lambda и представља ламбда израз. На пример, (lambda (x) (* x x)) је безимена функција која враћа квадрат свог нумеричког аргумента. Ова функција се може користити као и било која именована функција, тако што се стави на почетак листе која садржи аргумент функције. На пример, следећи израз враћа 49:

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

Ламбда изрази могу имати и већи број аргумената.

Сцхеме-ова функција специјалне форме define служи да веже име за вредност или ламбда израз. (define simbol izraz) се користи да веже име за вредност. На пример:

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

Након овога pi ће се интерпретирати као 3.14159, а two_pi као 6.28318.
Друга употреба define функције јесте да веже ламбда израз за име. У овом случају, define узима две листе као аргументе. Прва садржи прототип функције, име за којим следе аргументи. Друга садржи израз за који се име везује. Ово се може описати следећим изразом,
define (ime_funkcije parametri) (izraz))
Пример коришћења:

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

Још један пример:

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

Контрола тока

Постоји више начина контроле тока у Scheme-у.
На пример, помоћу функције if која има три параметра и која је општег облика (if predikat then_izraz else_izraz). Пример:

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

Даље, коришћењем функицје специјалне форме cond. cond нема фиксиран број параметара и сваки параметар представља пар, предикат - израз. Уопштени облик ове функције изгледа овако: (cond (predikat1 izraz1) (predikat2 izraz2) . . . (predikatN izrazN) [(else izrazN+1)] )
Предикати параметара се евалуирају један по један, почевши од првог наведеног, све док се неки не евалуира на #т. Потом се евалуира израз иза првог тачног предиката и његова вредност представља вредност cond функције. Ако ниједан предикат није тачан, онда се евалуира израз иза else, ако постоји, и његова вредност се враћа. Ако не постоји else и ниједан предикат није тачан, вредност функције cond није дефинисана. Пример:

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

Специјалан случај функције cond јесте функицја case.
Још један начин за контролу тока јесте рекурзија. Пример:

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

Поред ових функција, постоје још when и unless.

Рад са листама

Пре самих функицја за рад са листама, неопходно је напоменути неизоставну примену примитивне функције quote. Наиме, да не би дошло до покушаја интерпретирања листе као функције, односно покушаја евалуације елемената листе, користи се функција quote (') која ће вратити саму листу.
Поред већ вићеног начина за креирање листе, преко угњеждених парова, Scheme нуди и прегледнију опцију помоћу функције list.

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

Функција car враћа главу листе, односно први елемент листе, а cdr враћа реп листе, односно остатак листе.

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

Композиције функција, до четири функције, car и cdr је могуће записати помоћу једне функције. Тако, (caar x) је еквивалентно са (car (car x)), (cadr x) са (car (cdr x)), (caddar x) је еквивалентно са (car (cdr (cdr (car x))))...

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

Приступ елементима листе се врши помоћу list-ref функције, док list-tail функција враћа реп листе почев од задатог елемента.

(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)

Функција cons је, на неки начин, инверзна функцијама car и cdr. Она конструише листу од дате главе и репа. Дакле, ако је дата нека листа a, резултат следеће композиције функција (cons (car a) (cdr a)) јесте управо почетна листа 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)

Предикатска функција null? проверава да ли је листа празна и, као за све типове података, постоји функција за проверу типа, list?.

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

Преглед стандардних форми и процедура језика

Језик је формално дефинисан стандрардима R5RS (1998) и R6RS (2007). Ту су описане стандардне форме за писање програма, као и стандардне процедуре језика.

Стандардне форме

Наредна табела описује стандардне форме језика Scheme. Неке од форми се појављују у више од једног реда, из разлога што неке форме имају вишеструку функцију примене у језику, те се не могу једнозначно класификовати.

Форме обележене са "Б" у табели представљају изведене "библиотечке" форме које су заправо дефинисане помоћу неких других, основнијих форми. Углавном су имплементиране као макрои.

Стандардне форме дефинисане R5RS стандардом

Сврха	Форме
дефинисање	define
повезивање	lambda, do (Б), let (Б), let* (Б), letrec (Б)
условни изрази	if, cond (Б), case (Б), and (Б), or (Б)
секвенца	begin
iteracija	lambda, do (Б), named let (Б)
синтаксна проширења	define-syntax, let-syntax, letrec-syntax, syntax-rules (Р5РС), syntax-case (Р6РС)
навођење	quote('), unquote(,), quasiquote(`), unquote-splicing(,@)
додела	set!
одложено извршавање	delay (Б)

Стандардне процедуре

Наредне две табеле приказују стандардне процедуре дефинисане R5RS стандардом. Стандард R6RS је много обимнији и резиме ове врсте не би био тако практичан и репрезентативан. Неке стандардне процедуре се појављују у више од једног реда, из истог разлога као код стандардних форми.

Стандардне процедуре дефинисане Р5РС стандардом

Сврха	Процедуре
основни конструкти	vector, make-vector, make-string, list
предикати за проверу једнакости	eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci?
конверзије типова података	vector->list, list->vector, number->string, string->number, symbol->string, string->symbol, char->integer, integer->char, string->list, list->string
нумеричке процедуре	види следећу табелу
стрингови	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!
карактери	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
вектори	make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!
симболи	symbol->string, string->symbol, symbol?
листе и уређени парови	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
предикати за проверу типа	boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?
прекидање и настављање програма	call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind
окружење	eval, scheme-report-environment, null-environment, interaction-environment (опционо)
улаз/излаз	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(опционо), with-output-to-file(опционо)
системски интерфејс	load (опционо), transcript-on (опционо), transcript-off (опционо)
одложено извршавање	force
функционално програмирање	procedure?, apply, map, for-each
booleans	boolean? not

Стринговске и карактерске процедуре које садрже "-ci" у свом називу врше поређења која не праве разлику између малих и великих словних карактера.

Стандардне нумеричке процедуре дефинисане Р5РС стандардом

Сврха	Процедуре
основни аритметички оператори	+, -, *, /, abs, quotient, remainder, modulo, gcd, lcm, expt, sqrt
релациони оператори	<, <= , >, >=, =
максимум и минимум	max, min
заокруживање бројева	floor, ceiling, truncate, round
рационални бројеви	numerator, denominator, rational?, rationalize
комплексини бројеви	make-rectangular, make-polar, real-part, imag-part, magnitude, angle, complex?
предикати за проверу типа	integer?, rational?, real?, complex?, number?
тачност бројева	inexact->exact, exact->inexact, exact?, inexact?
разноврсни предикати	zero?, negative?, positive?, odd?, even?
тригонометријске функције	sin, cos, tan, asin, acos, atan
експоненцијалне функције	expt, log
улаз/излаз	number->string, string->number

Литература

• Concepts of Programming Languages Tenth Edition; Robert W. Sebesta; 2012 Addison-Wesley; One Lake Street, Upper Saddle River, New Jersey
• The Scheme Programming Language Second Edition; R.Kent Dybvig; 1996 Prentice Hall PTR; A Simon and Schuster Company, Upper Saddle River, New Jersey
• Хисторy_оф_тхе_Сцхеме_программинг_лангуаге
• Званични веб-сајт