Реферат на тему:

Мова програмування Лiсп

За однiєю з класифiкацiй мови програмування (МП) дiляться на процедурнi, якi також називаються операторними або iмперативними та декларативнi мови. Бiльшiсть мов що сьогоднi використовуються - Бейсiк, Фортран, Паскаль, Сi, вiдносяться до процедурних мов. До класу декларативних мов вiдносяться функцiональнi або апплiкативнi - Лiсп, Лого та логiчнi мови, вiдомим представником якого є Пролог. На практицi МП не є чисто процедурними, функцiональними чи логiчними. На процедурнiй мовi можна написати функцiональну програму i навпаки.

Процедурна програма складається з послiдовностi операторiв та виразiв, якi керують її виконанням. Типичними операторами є оператори присвоєння, ввода-виводу, керування та циклу.

Функцiональна програма складається з сукупностi визначених функцiй. Функцiї, в свою чергу, можуть викликати iншi функцiї. Обчислення починається з виклику деякої функцiї. Чисте функцiональне програмування не має присвоєнь та засобiв передачi керування. Повторнi обчислення здiйснюються за допомогою рекурсiї, яка є основним засобом функцiонального програмування.

muLisp працює на комп'ютерi з операцiйною системою MS-DOS або PC-DOS. Програма mulisp.com є iнтерпретатором МП muLisp. muLisp є потужною МП, має великi функцiональнi засоби для обробки структур даних, створених користувачем. muLisp є символьною МП, яка призначена для обробки спискiв.

(Lisp - List Processing). Будь-яка структура даних є об'єктом.

Робота з Лiспом нагадує роботу з карманним калькулятором: користувач вводить вираз (вiн обов'язково повинен закiнчуватися символом та мати збалансовану кiлькiсть дужок), який читає машина, потiм обчислює (iнтерпретує), та видає результат. Цей процес введення-читання-обчислення-видачi результату буде вiдбуватися в циклi доти, доки користувач не введе команду (SYSTEM), яка завершує роботу з muLisp i передає керування операцiйнiй системi.

Об'єкти Лiспу

Об'єкти можуть бути двох типiв: простi та складенi. Простi об'єкти називаються атомами. До атомiв вiдносяться символи та числа. Символ не може починатися з цифри. muLisp не розрiзняє маленькi та великi лiтери, а перетворює всi введенi лiтери в великi. Атом є неподiльним, тобто його не можна розбити на компоненти. Атом, як i людина, має iм'я. Iменами атомiв є рядки символiв. DOG, CAT, qw1232df, -32 є типовими iменами атомiв. Символи T та NIL мають в Лiспi спецiальне призначення: вони позначають вiдповiдно логiчнi значення iстини та хибностi. Цi символи завжди повиннi мати одне фiксоване значення. Їх не можна використовувати в якостi iмен iнших об'єктiв Лiспу.Числа та логiчнi значення T та NIL є константами, всi iншi символи - змiнними.

Складними об'єктами даних є списки. Список мiстить нуль (тодi говорять про порожнiй список) або бiльше об'єктiв, кожний з яких може бути як простим, так i складеним. (FACE, LOOK, NOSE) є списком, який складається з трьох атомiв. Порожнiй список позначається NIL = (), який є атомом. Список називається лiнiйним, якщо його елементи є атомами. Iнакше говорять про списки з пiдсписками, наприклад: (7 (8 9) TR).

Для того щоб введений вираз не обчислювався, перед ним ставиться апостроф ('). Якщо вираз вводиться без апострофа, то повертається його значення. При запуску програми muLisp значенням кожного атома вважається вiн сам. Значенням числа завжди є саме число, тому перед числами апостроф не ставиться. Тобто пiсля старту системи при вводi Q результатом буде його значення - Q, а при вводi 'Q - буде завжди Q. Апостроф перед виразом - це скорочення форми QUOTE, яка записується в наступнiй формi: 'вираз = (QUOTE вираз). QUOTE можна використовувати як спецiальну функцiю з одним аргументом, яка нiчого з ним не робить, а повертає як результат сам аргумент.

Списки задаються перелiком елементiв, взятих в дужки, перед якими ставиться апостроф. Наприклад: '(ice, hen) або '((one 1) (two 2) (three 3)).

Примiтивнi функцiї Лiспу

Lisp має п'ять примiтивних функцiй. Виклик функцiї має наступний формат:
(name arg1 arg2 ...), де name - iм'я функцiї, arg1,arg2,... - її аргументи.

1. (CAR list) - голова списку.

2. (CDR list) - хвiст списку.

3. (CONS object list) - об'єднання (конкатенацiя) об'єкта зi списком.

4. (EQL atom1 atom2) - порiвняння двох атомiв.

5. (ATOM object) - перевiрка чи є object атомом.

CAR та CDR називаються селекторними функцiями, оскiльки вони дають можливiсть вибирати або знищувати частину об'єкта. Результатом функцiї (CAR list) завжди є перший елемент списку list, якщо вiн непорожнiй i NIL в iншому випадку. Результатом функцiї (CDR list) є список list без першого елемента, якщо list мiстить бiльш одного елемента i NIL в iншому випадку.

$ (CAR '(q w e r t y)) $ (CDR '(q w e r t y)) $ (CAR '((one 1) (two 2)))

q (w e r t y) (one 1)

$ (CAR '()) $ (CDR '(tree)) $ (CDR '((q w)) $ (CDR '())

NIL NIL NIL NIL

За допомогою функцiй CAR, CDR можна знаходити за даним списком будь-який його пiдсписок або атом. Дозволяється використовувати функцiї, якi є комбiнацiями CAR та CDR. Iмена таких функцiй починаються на C i закiнчуються на R, а мiж ними знаходиться послiдовнiсть лiтер A та D (але не бiльше 4 лiтер в реалiзацiї muLisp), яка вказує шлях обчислення.

$ (CAR (CDR (CDR '(q w e r t y)))) $ (CAR (CDR (CDR '((q 1) (w 2) (e 3)))))

$ (CADDR '(q w e r t y)) $ (CADDR '((q 1) (w 2) (e 3)))

e (e 3)

$ (CDR (CDR '((q 1) (w 2) (e 3)))) $ (CAR (CAR '((q w))))

$ (CDDR '((q 1) (w 2) (e 3))) $ (CAAR '((q w)))

((e 3)) q

Функцiя конструктора CONS використовується для додання об'єкту до заданого списку. Об'єкт який додається, стає головою списку. Якщо другий аргумент не задано, то вiн вважається рiвним NIL.

$ (CONS '(q w) '(r (t y))) $ (CONS apple '(q w)) $ (CONS '(q w) '(r t y)) $ (CONS 5)

((q w) r (t y)) (apple q w) ((q w) r t y) (5)

Якщо результатом виразу (CONS object list) буде new, то результатом (CAR new) буде object, а результатом (CDR new) буде list.

$ (CAR (CONS '(q w) '(r (t y)))) $ (CAR (CONS apple NIL))

(q w) apple

Функцiєю порiвняння є EQL. Вона порiвнює значення першого та другого аргумента, якi обов'язково повиннi бути атомами, та повертає значення iстини (Т) або хибностi (NIL).

$ (EQL 'qw 'qw) $ (EQL (CAR '(q w)) q) $ (EQL (CAR '(q,w) NIL)

T T F

При написаннi програм на Лiспi часто виникає запитання: чи є даний об'єкт атомом? Це питання вирiшує предикат ATOM. Вiн повертає Т, якщо об'єкт є атомом i NIL в iншому випадку. Порожнiй список NIL є атомом.

$ (ATOM qwerty) $ (ATOM '(q w e)) $ (ATOM '())

T F T

$ (ATOM '(q)) $ (ATOM 3)

F T

Функцiї призначення

Функцiї призначення застосовуються для надання значень програмним змiнним. До них вiдносяться:

1. (SET symbol object) - замiна символа об'єктом

2. (SETQ sym1 form1 sym2 form2 ... ) - спецiальна форма функцiї SET

3. (PSETQ sym1 form1 sym2 form2 ... ) - спецiальна форма функцiї SET

4. (POP symbol) - повертає вершину стека (списку)

5. (PUSH symbol form) - кладе символ symbol в стек (список) form.

Операцiя замiни значення символа здiйснюється за допомогою функцiї SET. Вона присвоює символу symbol значення object, або зв'язує symbol з object. Для скорочення замiсть SET ' пишуть SETQ (SET Quote). Як результат функцiя присвоєння повертає другий аргумент.

$ (SET 'fox '(a s d)) $ (SETQ vowels '(a e i o u)))

$ (SETQ fox '(a s d)) $ (SETQ vowels (CONS 'y vowels))

(a s d) (y a e i o u)

Функцiя SETQ дозволяє здiйснювати замiну значень декiльком символам в однiй командi: (SETQ a 1 b 2 c 3). При цьому змiни виконуються послiдовно злiва направо. Пiсля цього значенням символу a стане 1, b - 2, c - 3.

Функцiя PSETQ iдентична до функцiї SETQ за винятком того, що всi форми оцiнюються до того, як будуть здiйсненi будь-якi замiни. Проiлюструємо це на прикладi. Значення символа Sym позначатимемо через Val(Sym).

$ (SETQ w 1 e 2) Val(w)=1, Val(e)=2 $ (SETQ w 1 e 2) Val(w)=1, Val(e)=2

$ (SETQ w e e w) Val(w)=2, Val(e)=2 $ (PSETQ w e e w) Val(w)=2, Val(e)=1

При виконаннi операцiї замiни необхiдно розрiзняти символ та значення. При стартi системи mulLsp значенням кожного символа є вiн сам. Якщо ми введемо DOG, то i результатом буде DOG. Присвоїмо символовi DOG значення CAT: (SET 'DOG 'CAT). Результатом виразу (SET DOG 'HEN) буде HEN, але значення HEN ми присвоювали не символу DOG, а значенню символа DOG, тобто символу CAT. Значення символа DOG залишилося без змiни. Розглянемо результат наступних дiй:

(SET 'car 'road) Val(car) = road Val(road) = road

(SET car flower) Val(car) = road Val(road) = flower Val(flower) = flower

(SET 'car car) Val(car) = road Val(road) = flower Val(flower) = flower

(SET road car) Val(car) = road Val(road) = flower Val(flower) = road

(SET 'road 4) Val(car) = road Val(road) = 4 Val(flower) = road

(SET road 'hen) помилка, 4 не є символом i не може приймати iншi значення

POP повертає голову списка (вершину стека) i замiнює значення symbol на його хвiст. PUSH кладе в стек та змiнює його значення на збiльшений стек.

$ (SETQ a '(q w e r t)) Val(a) = (q w e r t)

$ (POP a) Val(a) = (w e r t)

$ (PUSH 'n a) Val(a) = (n w e r t)

Завдання

I Варiант завдань

1. Побудувати список, який задовiльняє наступним умовам:
а) мiстить два пiдсписки, перший з яких має три атоми, а другий - чотири атоми;
б) мiстить три атоми, але його хвiст дорiвнює NIL;
в) мiстить три складенi об'єкти, i лише його другий елемент є атомом;
г) голова списку мiстить три атоми, а кiлькiсть атомiв в усьому списку дорiвнює 3.
д) мiстить тiльки порожнiй список, а голова списку не є атомом.
е) голова та хвiст є списками з пiдсписками.

2. Що буде в результатi обчислення наступних виразiв:

a) (CONS NIL NIL) г) (ATOM (CDR '(q NIL)))

б) (CONS (CAR '((q w))) (CDR '((q (w e))))) д) (EQL NIL 'NIL)

в) (EQL (CDR '(q)) NIL) е) (PUSH nil nil) (EQL (ATOM '(q w)) nil)

3. Скласти вираз, який би за вхiдними даними побудував би заданий результат.

a) дано: (A, B, C), (X, Y, Z). побудувати: (A, Y, Z).

б) дано: ((one 1) (two 2 3) (three 4 5 6)) побудувати: 5.

в) дано: ((q w (r) t) y) побудувати: NIL

г) дано: ((q (w (e) r) t) y) побудувати: ((q) w (e) r)

д) дано: (q (w e)) побудувати: w, e

е) дано: (q w) побудувати: (((q w)))

4. Скласти вираз, який надає значення вхiдним даним та вираз, який будує заданий результат, використовуючи лише вихiднi символи.

а) дано: one=1, two=2, three=3 зробити: one=2, two=3, three=1.

б) дано: Val(house)=sky, Val(sky)=house зробити: Val(sky)=sky, Val(house)=house

в) дано: Val(lst)=(q) зробити: Val(lst)=(((q) q) q)

г) дано: Val(q)=w, Val(w)=s зробити: Val(q)=(s s)

5. Не використовуючи селекторнi функцiї:
а) дано: Val(a) = (q w e r t y) зробити: Val(a) = q
б) дано: Val(a) = (q w e r t y) зробити: Val(a) = (w)

6. Вказати значення всiх змiнних пiсля виконання наступних дiй:
(SET one 'two)
(SETQ two 'one)
(SET three two four 'one two three)
(PSETQ four one three 'four two three one four)

II Варiант завдань

1. Побудувати список, який задовiльняє наступним умовам:
а) голова та хвiст списку дорiвнює NIL.
б) серед елементiв списку є три списки, але жодного складного об'єкту.
в) серед елементiв списку немає атомiв, хвiст голови не є порожнiм списком, але хвiст хвоста є порожнiм списком.
г) усi елементи списку - атоми, при чому перший та третiй елементи - символи, другий та четвертий - не символи, а п'ятий - не символ i не число.

2. Що буде в результатi обчислення наступних виразiв:

а) (CADR '(nil (nil)))

б) (CONS (ATOM '(ATOM '(q w e))) '(NIL))

в) (CONS '(q w) '(e r) '(t y))

г) (EQL (ATOM (CDR '(nil))) (CADDDR '(w e r t y))

д) (EQL (CONS nil) (CADR '(q (nil) w)))

е) (CDR '(CDR (CONS '(q) '(w))))

3. Вказати значення всiх змiнних пiсля виконання наступних дiй:

а) (SETQ one two two three three one)

(SET one three)

(PSETQ one two two three three one)

б) (SETQ a '(a b) b '(b c) c '(c a))

(SET (CADR b) (CONS a))

(SETQ a (CADR a) b (CADR b) c (CADR c))

Зауваження: якщо a = (a b), b = (b c), c = ((a b)),

то пiсля (SETQ a (CADR a)) буде a = b, b = (b c), c = ((a b)),

а пiсля (SETQ a (EVAL (CADR a))) буде a = (b c), b = (b c), c = ((a b)).

(EVAL a) - обчислити значення символа а, або повернути його значення.