Реферат на тему:
Основи мови програмування Лісп
1. Об’єкти Ліспу
Будь-яка структура даних є об’єктом. Об’єкти можуть бути двох типів: простіта складені. Прості об’єкти називаються атомами. До атомів відносяться символи та числа. Символ не може починатися з цифри. muLisp не розрізняє маленькі та великі літери, а перетворює всі введені літери у великі. Атом є неподільним, тобто його не можна розбити на компоненти. Атом, як і людина, має ім’я. Іменами атомів є рядки символів. DOG, CAT, qw1232df, -32 є типовими іменами атомів. Символи T та NIL мають в Ліспі спеціальне призначення: вони позначають відповідно логічні значення істини та хибності. Ці символи завжди повинні мати одне фіксоване значення. Їх не можна використовувати в якості імен інших об’єктів Ліспу. Числа та логічні значення T та NIL є константами, всі інші символи – змінними.
Складними об’єктами даних є списки. Список містить нуль (тоді говорять про порожній список) або більше об’єктів, кожний з яких може бути як простим, так і складеним. (FACE, LOOK, NOSE) є списком, який складається з трьох атомів. Порожній список позначається NIL = (), який є атомом. Список називається лінійним, якщо його елементи є атомами. Інакше говорять про списки з підсписками, наприклад: (7 (8 9) TR).
Для того щоб введений вираз не обчислювався, перед ним ставиться апостроф (‘). Якщо вираз вводиться без апострофа, то повертається його значення. При запуску програми muLisp значенням кожного атома вважається він сам. Значенням числа завжди є саме число, тому перед числами апостроф не ставиться. Тобто після старту системи при вводі Q результатом буде його значення – Q, а при вводі ‘Q — буде завжди Q. Апостроф перед виразом – це скорочення форми QUOTE, яка записується в наступній формі: ‘вираз = (QUOTE вираз). QUOTE можна використовувати як спеціальну функцію з одним аргументом, яка нічого з ним не робить, а повертає як результат сам аргумент.
Списки задаються переліком елементів, взятих в дужки, перед якими ставиться апостроф. Наприклад: ‘(ice, hen) або ‘((one 1) (two 2) (three 3)).
2. ПримітивніфункціїЛіспу
ВикликдоівльноїфункціїуЛіспімаєнаступнийформат:
(name arg1 arg2 ...), деname — ім’яфункції, arg1,arg2, ... — їїаргументи.
Мова програмування Lisp має п’ять примітивних функцій.
1. (CAR <list>) — знаходження голови списку.
2. (CDR <list>) — знаходження хвосту списку.
3. (CONS <object> <list>) — об’єднання (конкатенація) об’єкта зі
списком.
4. (EQL <atom1> <atom2>) — порівняння двох атомів.
5. (ATOM <object>) — перевірка, чи є об’єкт <object> атомом.
CAR та CDR називаються селекторними функціями, оскільки вони дають можливість вибирати або знищувати частину об’єкта. Результатом функції (CAR list) завжди є перший елемент списку list, якщо він непорожній і NIL в іншому випадку. Результатом функції (CDR list) є список list без першого елемента, якщо list містить більш одного елемента і NIL в іншому випадку.
$ (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
За допомогою функцій CAR, CDR можна знаходити за даним списком будь-який його підсписок або атом. Дозволяється використовувати функції, які є комбінаціями CAR та CDR. Імена таких функцій починаються на C і закінчуються на R, а між ними знаходиться послідовність літер A та D (але не більше 4 літер у реалізації інтерпретатора muLisp), яка вказує шлях обчислення.
$ (CAR (CDR (CDR ‘(q w e r t y))))
$ (CADDR ‘(q w e r t y))
e
$ (CAR(CDR (CDR ‘((q 1) (w 2) (e 3)))))
$ (CADDR ‘((q 1) (w 2) (e 3)))
(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
Функція конструктора CONS використовується для додання об’єкту до заданого списку. Об’єкт який додається, стає головою списку. Якщо другий аргумент не задано, то він вважається рівним NIL.
$ (CONS ‘(q w) ‘(r (t y))) $ (CONS apple ‘(q w))
((q w) r (t y)) (apple q w)
$ (CONS ‘(q w) ‘(r t y)) $ (CONS 5)
((q w) r t y) (5)
Зазначимо, щоякщорезультатомобчисленнявиразу (CONS objectlist) будеnew, торезультатом (CAR new) будеobject, арезультатом (CDR new) будеlist, тобто
(CAR (CONS objectlist)) = object,
(CDR (CONS objectlist>)) = list.
$ (CAR (CONS ‘(q w) ‘(r (t y)))) $ (CAR (CONS apple NIL))
(q w) apple
Функцієюпорівнянняє EQL. Вона порівнює значення першого та другого аргумента, які обов’язково повинні бути атомами, та повертає значення істини (Т) або хибності (NIL).
$ (EQL ‘qw ‘qw) $ (EQL (CAR ‘(q w)) q)
T T
$ (EQL (CAR ‘(q, w) NIL) $ (EQL nil ‘(nil))
NIL NIL
При написанні програм на Ліспі часто виникає запитання: чи є даний об’єкт атомом? Це питання вирішує предикат ATOM. Він повертає Т, якщо об’єкт є атомом і NIL в іншому випадку. Порожній список NIL є атомом.
$ (ATOM qwerty) $ (ATOM ‘(q w e)) $ (ATOM ‘())
T NIL T
$ (ATOM ‘(q)) $ (ATOM 3) $ (ATOM ‘(NIL))
F T NIL
3. Функції призначення
Функції призначення застосовуються для надання значень програмним змінним. До них відносяться:
1. (SET symbol object)
— замінасимволаоб’єктом
2. (SETQ sym1 form1 sym2 form2 ... )
— спеціальна форма функції SET
3. (PSETQ sym1 form1 sym2 form2 ... )
— спеціальна форма функції SET
4. (POP symbol)
— повертає вершину стека (списку)
5. (PUSH symbol form)
— кладе символ symbol в стек (список) form.
Операція замінизначення символа здійснюється за допомогою функції SET. Вона присвоює символу symbol значення object, або зв’язує symbol з object. Для скорочення замість SET ‘ пишуть SETQ (SET Quote). Як результат функція присвоєння повертає другий аргумент.
$ (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)
Функція SETQ дозволяє здійснювати заміну значень декільком символам в одній команді: (SETQ a 1 b 2 c 3). При цьому зміни виконуються послідовно зліва направо. Після цього значенням символу a стане 1, b-2,c-3.
Функція PSETQ ідентична до функції SETQ за винятком того, що всі форми оцінюються до того, як будуть здійснені будь-які заміни. Проілюструємо це на прикладі. Значення символа 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
При виконанні операції заміни необхідно розрізняти символ та значення. При старті системи mulLsp значенням кожного символа є він сам. Якщо ми введемо DOG, то і результатом буде DOG. Присвоїмо символові DOG значення CAT: (SET ‘DOG ‘CAT). Результатом виразу (SET DOG ‘HEN) буде HEN, але значення HEN ми присвоювали не символу DOG, а значенню символа DOG, тобто символу CAT. Значення символа DOG залишилося без зміни. Розглянемо результат наступних дій:
(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 не є символом і не може приймати інші значення
POP повертає голову списка (вершину стека) і замінює значення <symbol> на його хвіст. PUSH кладе <symbol> в стек та змінює його значення на збільшений стек.
$ (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)
4. Визначення функцій в Ліспі
Поряд з примітивними функціями можуть існувати функції, визначені користувачем. Функція викликається набором аргументів і повертає єдине значення. Визначення функції в Ліспі має наступний вигляд:
(DEFUN name (arg1 arg2 ...)
task1
task 2
. . . . . )
де name — ім’яфункції, arg1, arg2, ... — аргументи (параметри). Тіло функції містить послідовність задач. Ключовеслово DEFUN виниклоз DEfine FUNction.
$ (DEFUN FIRST (lst) $ (FIRST ‘(q w e r t y))
(CAR lst) ) q
$ (DEFUN THIRD (lst) $ (THIRD ‘(q w e r t y))
(CADDR lst) ) e
ВизначимофункціюNULL, яка розпізнає порожній список. Вона повертає істину, якщо її аргументом є порожній список і хибність в іншому випадку.
$ (DEFUN NULL (obj) $ (NULL ‘(q w e r)) $ (NULL (CDR ‘(r)))
(EQL obj NIL) ) F T
Намвжевідомітрифункціїрозпізнання: EQL, ATOM, NULL. Функції, які застосовуються для перевірки певних умов та можуть повертати лише два значення – істини чи хиби, називаються предикатами.
Тіло функції складається з послідовності завдань. Завдання можуть бути двох типів: прості та умовними. Будь-яке завдання береться в круглі дужки і може розглядатися як список виразів, які треба проінтерпретувати.
Якщо завдання є атомом або його перший елемент є атомом, то таке завдання називається простим. Наприклад, (CONS ‘NR LST).
Якщо перший елемент списка, який описує завдання не є атомом, то таке завдання називається умовним. Наприклад, ((ATOM lst) (CONS expr lst)).
В умовному завданні перший елемент списку обов’язково є предикатом. Якщо значення предикату NIL, то значення завдання стає рівним NIL і Лісп переходить до виконання наступного завдання. Якщо предикат повертає не NIL, відбувається виконання хвосту списку завдання, а інші завдання ігноруються. Якщо предикат повертає Т, а хвіст завдання порожній, то результатом всієї функції буде T.
Напишемо предикат, який розпізнає списки. Якщо аргументом є список, то предикат повертає істину, інакше — хибність. Функцію LISTP можна проінтерпретувати наступним чином: “Якщо obj є атомом, то повернути NIL, інакше повернути T”.
$ (DEFUN LISTP (obj) $ (DEFUN LISTP (obj)
((ATOM obj) NIL) ((NULL obj))
T ) ((ATOM obj) NIL)
T )
В другій колонці написано предикат LISTP, який розпізнає додатково порожній список (повертає істину). Перше завдання є умовним, хвіст якого порожній. Його можна проінтерпретувати так: перевірити об’єкт obj на порожній список, і якщо він є таким, передати як результат функції істину. Немає потреби писати: ((NULL obj) T), оскільки це те ж саме, що і ((NULL obj)). Останнім завданням цих предикатів є атом Т. Це означає, що якщо жодне з умовних завдань не виконане (лише за цієї умови керування програмою дійде до останнього завдання), то як результат функції повернути Т. Для другого визначення функції LISTP маємо:
$ (LISTP ‘tree) $ (LISTP ‘()) $ (LISTP ‘(q w e r t y))
NIL T T
Длякращогорозумінняроботитілафункціїтапростихіумовнихзавданьрозглянемофункцію sm тарезультати, яківонабудегенеруватиприпевнихвхіднихзначеннях: