Въведение в Lisp/Scheme
Благодарности на www.dhstudio.eu
Статията „Въведените в Lisp/Scheme“ е написана за потребителите на Gnu/Linux. Инсталацията на DrScheme под Gnu/Linux (Debian 3.1/4.0) се извършва по следния начин: apt-get install drscheme.
Lisp e разработен от Джон Маккарти през 1958 г. докато е бил в MIT (Massachusetts Institute of Technology). Lisp е базиран на Ламбда- смятането въведено от Алонсо Чърч през 1930 година. Името на Lisp произхожда от "Lisp Processing". Lisp има доста голям брой диалекти като най- популярни са: Common Lisp и Scheme. Той бързо става един от най- популярните програмни езици за изкуствен интелект. Ние ще разгледаме диалекта Scheme които е бил разработен през 1970 година от Гай Стиили и Джерард Джей Сусман. Езика Scheme има два дефинирани стандарта: Официалния IEEE стандарт и стандарта наречен Revisedn Report on the Algorithmic Language Scheme които е абревиатура от RnRS, където n е номер на ревизия. Сегашния стандарт е R5RS и R6RS е в процес на разработка. Приложението което ще ползваме в GNU/Linux ще бъдe: drscheme
1.0 Оператори и Операнди
Съставна част от повечето езици са неговите оператори и операнди. Основните оператори са: /, *, +, - .Нека разгледаме следния пример за събиране на две числа използвайки оператори и операнди:
Пример 1. > (+ 5 4) 9 Основните оператори ползват следния синтаксис: (<оператор> <операнд1> <операнд2> <операнд N>) Термините оператори, процедури и функции имат еднозначно значение както и термините аргумент и операнд. Сложността при употребата на оператори може да се увеличи при употребата на повече от един оператор в съставянето на конкретен израз. Пример за израз използващ повече от един оператор е следния: Пример 2. > (+ 5 (* 3 2)) 11 Пример 3. > (+ 5 (/ 14 2)) 12 Пример 4. > (+ (* 1 2) (- (+ 3 4) (/ 6 3))) 7 Нека разгледаме подробно действието което извършва пример 2. Разгледания пример 2 казва следното: събери числото 5 с числото получено от умножението на числата 3 и 2 и изведи получения резултат . 2.0 Идентификатори, Празни места и Коментари
Идентификаторите са последователност от букви, числа и следните символи: ! $ % & * + - . / : < = > ? @ ^ _ ~
Целта на празните места е да направят кода по- лесен за четене. Пример с използване на празни места може да видите в следния Scheme израз:
Пример 5.
> (* (+ 1 2 )
(+ (- 13 3) ))
30
Коментарите са една фундаментална част във всеки програмен език. Коментарите също благоприятстват за по- голямата четливост на кода. Използването на коментари предразполага използването и разработването на кода от всеки програмист. Коментарите в Scheme се означават със ' ; '. Всеки текст разположен от ';' до края на реда се игнорира от компилатора. В Scheme няма коментари опериращи на повече от един ред.
Фундаментални типове
В Scheme има девет типа. Ние ще разгледаме основните: булеви, числа, низове и символи.
3.1 Булев тип
При употребата на булеви типове е необходимо да се знае, че този тип извежда „истина“ или „лъжа“. Истината при използването на булев тип се отбелязва със „#t“, а лъжата със „#f“ . Нека следваме изречената мъдрост „Хиляди думи се равняват на един поглед“ и разгледаме следните примери:
Пример 6.
> (boolean? 3.14) #f > (number? 131) #t > (boolean? #t) #f > (boolean? #f) #t
Различни булеви оператори включват и, или и не:
Пример 7.
> (and #f #t) #f > (or #f #t) #t > (and (not #f) (or #f #t)) #t 3.2 Числа Числовите типове имат няколко подтипа като: number, complex, real, rational, и integer. За да разберете точността на конкретно число може да ползвате : exact?“ или „inexact?“. Нека разгледаме следните примери: Пример 8. > (/ 4 7) 4/7 > (number? (/ 4 7)) #t > (rational? (/ 4 7)) #t > (integer? (/ 4 7)) #f > (exact? (/ 4 7)) #t > (inexact? (/ 4 7)) #f > (sqrt (/ 4 7)) 0.7559289460184545 > (exact? (sqrt (/ 4 7))) #f > (inexact? (sqrt (/ 4 7))) #t 3.3 Низове Низ е разположения текст между двойни кавички „“. В низовете е възможна употребата на специални символи благодарение на „\“ . Много често използвани са низовете и функциите опериращи с тях. Често срещани низ функции са: substring, string-ref. Пример 9. > (substring "www.dhstudio.eu" 4 15) "dhstudio.eu" > (substring "testing" 4 7) "ing" > (substring "www.dhstudio.eu" 4) "dhstudio.eu" > (string-ref "testing" 3) #\t 3.4 Символи Употребата на символи увеличава размера на структурите данни които езика обработва. За работа със символи се употребява предиката eq? известен също като предикат за идентичност. Дефиницията за идентичност на два символа гласи, че двата символа трябва да се състоят от едни и същи знаци записани в един и същ ред. Нека разгледаме синтаксиса на предиката eq ? Пример 10. > (eq? m1 m2) Семантиката на предиката eq? се базира на истина и лъжа т.е. ако: символните изрази m1 и m2 са оценени като едни и съши изрази то резултата е #t (true/истина) докато в противен случай е #f (false/лъжа). Често срещан е предиката symbol? , който има за цел да оцени конкретен обект и да изведе #t (true/лъжа) , ако обекта е символ и обратното. Примера по- долу илюстрира действието на предиката symbol? Пример 11. > (symbol? 10) #f > (symbol? 'martin) #t 4.0 Променливи Деклариране на глобални променливи се извършва с оператора define. Стойността на променливата по- рано указана с оператора define може да бъде променяна с оператора set! . Следния пример изобразява изказаното до момента. Пример 12. > (define sbor 26) > (set! Sbor (+ 20 5)) > sbor 25 5.0 Списъци Числата, низовете, символите и булевите константи (#t | #f) се наричат също атоми. Основна конструкция на лиспо- подобните функционални езици е S- изразът. S- изразът се нарича точкова двойка или само двойка. Дефиниция за S- израз: 1.> Всеки атом е S- израз 2.> Ако A и B са S- изрази, то (A.B) е S- израз 3.> S- Израз се определя само по правилата 1> и 2> Чрез точкова двойка се „слепват“ два обекта и се конструира съставен обект. Графично изобразено слепване на два обекта изглежда по следния начин: ***************************** * първи обект * втори обект * ***************************** Лявата част на клетката съдържа първия обект, а дясната част втория обект. Нека разгледаме пример за двойката (9 . 8) Пример 13. ************* * 9 * 8 * ************* Нека разгледа малко по- усложнен пример на двойката ((2.3).(4.5)) Пример 14. ************* ************* ************* * 2 * 3 * -> * <- * -> * <- * 4 * 5 * ************* ************* ************* Дефиниране на списък в Scheme се извършва със примитивната процедура list. Пример за дефиниране на списък: Пример 15. > (define dhstudio.eu ( list 'm 'a 'r 't 'i 'n) ) > dhstudio.eu (m a r t i n) Във всеки лиспо- подобен език са вградени средства за реализиране на двойки и работа с тях. В Scheme тези средства са фундаменталните процедури cons, car и cdr. 5.1 Процедура cons Процедурата cons е съкращение от construct или конструктор на двойки. Конструктора има сравнително лесен синтаксис от вида: (cons b2 c3), където cons e използваната процедура, а b2, c3 са изрази чиито оценки са S-изрази, т.е. атоми или точкови двойки. Семантиката на процедура cons се наблюдава в следващия разгледан пример които конструира двойки: Пример 16. > (define b1 10) > (define c2 20) > (cons b1 c2) (10 . 20) 5.2 Процедура car Идеята на процедурата car е да намери първия обект на двойка или списък. Семантиката и синтаксис на разглежданата процедура car най- лесно се обяснява със следния пример които извежда първи елемент от списък: Пример 17. > (define testlist (list 0 1 2 3 4 5 6 7 8 9 )) > (car testlist) 0 Предходния пример изобразява извеждане първи член на списък. Пример 18. > (define a 10) (define b 20) > (define c (cons a b) ) > (cаr c) 20 Предходния пример извежда първия обект на двойка. 5.3 Процедура cdr Процедурата cdr е реципрочна на car, т.е. нейната идея е да изведе втория обект от списък или двойка. Семантиката и синтаксиса е аналогичен на процедурата car. Следния пример изобразява действието на процедурата cdr: Пример 19. (define a 10) (define b 20) (define c (cons a b) ) (cdr c) 5.4 Процедура append Действието което извършва текущата процедура append е конкатенация на списъци. Конкатенация на списъци може да наблюдаваме в следния пример: Пример 20. > (define a(list 1 2 3 )) (define b(list 4 5 6 ) ) > (append a b) (1 2 3 4 5 6) 5.5 Процедура reverse Процедурата reverse (обръщане) обръща елементите на списък. Нека разгледаме следния пример за процедурата reverse: Пример 21. > (define a(list 1 2 3 )) > (reverse a) (3 2 1) 6.0 Фундаментални контролни структури 6.1 Контролна структура cond (short for conditional) Структурата cond има за цел да оцени конкретен израз и да върне резултат (истина | лъжа ). Синтаксиса на структурата cond e следния: (cond (<condition1> <expression1>) (<condition2> <expression2>) ... (else <expressionN>)) Следния пример онагледява целта на контролната структура cond. Пример 22. > (define (abs1 x) > (cond ((> x 0) x) > ((= x 0) 0) > (else (- 0 x)) )) 6.2 Процедура „case“ Процедура „case“ е подобна на switch при C/C++/Java. Процедурата дефинира предварително конкретен брой варианти които могат да бъдат избирани. Синтаксиса и семантиката на процедура „case“ може да наблюдаваме във следния пример: Пример 23. define get-type (lambda (data) (case data ((0 1 2 3 4 5 6 7 8 9) 'digit) ((#\A #\E #\I #\O #\U #\Y #\a #\e #\i #\o #\u #\y) 'vowel) (else (if (and (char? data) (char-alphabetic? data)) 'consonant 'other))))) > (get-type "Hawaii") other > (get-type 5) digit > (get-type #\o) vowel > (get-type #\s) consonant 6.3 Процедура „or“ Scheme процедурата „or“ се обяснява доста добре в следния пример: Пример 24. > (or #f #f #f #f) #f > (or #f 42 #f) 42 > (or #t #f) #t 6.4 Процедура „and“ Scheme процедурата „and“ се обяснява доста добре в следния пример: Пример 25. > (and #t #t #t #t) #t > (and #t 3.14 'squirrel) squirrel > (and 'false '() #f 'only-the-#f-is-false) #f > (and 'false '() 'only-the-#f-is-false) only-the-#f-is-false 6.5 Процедура if Процедурата if е подобна на процедурата cond. Scheme процедурата „if“ се обяснява доста добре в следния пример: Пример 26. (define (chislo num) > ( cond > ((> num 0) "Polojitelno") > ((< num 0) "Otricatelno") > ((= num 0) "Rawno na 0") > (else "zero"))) > (chislo 10) "Polojitelno" > (chislo 0) "Rawno na 0" > (chislo -1) "Otricatelno" Scheme e доста интересен и забавен диалект на Lisp успяващ да ни заинтригува със своята красота и ясно. Scheme си остава напълно подходящ език за учебни цели, но също така намира и други приложения. СЪДЪРЖАНИЕ 1.0 Оператори и Операнди 2.0 Идентификатори, Празни места и Коментари 3.0 Фундаментални типове 3.1 Булев тип 3.2 Числа 3.3 Низове 3.4 Символи 4.0 Променливи. 5.0 Списъци 5.1 Процедура cons 5.2 Процедура car 5.3 Процедура cdr 5.4 Процедура append 6.0 Фундаментални контролни структури 6.1 Контролна структура cond (short for conditional) 6.2 Процедура „case“ 6.3 Процедура „or“ 6.4 Процедура „and“ 6.5 Процедура if БИБЛИОГРАФИЯ 1. Езици за функционално и логическо програмиране, М. Тодорова 2. http://cs.gettysburg.edu/~tneller/cs341/scheme-intro/index.html 3. http://www.scheme.com/tspl3/