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

ЛАБАРАТОРНА РОБОТА №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 можна використовувати як спеціальну функцію з одним аргументом, яка нічого з ним не робить, а повертає як результат сам аргумент.

Lisp має п’ять примітивних функцій. Виклик функції має наступний формат:

(name arg1 arg2...), де name — ім’я функції, arg1,arg2,... — її аргументи.

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 в іншому випадку.

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

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

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

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

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). Як результат функція присвоєння повертає другий аргумент.

 

Виконання роботи:

1. Побудувати список, який задовільняє наступним умовам:

а) містить два підсписки, перший з яких має три атоми, а другий — чотири атоми;

$ (ATOM ‘(q w e)(r t y u))

Результат: NIL

 

б) містить три атоми, але його хвіст дорівнює NIL;

$ (ATOM ‘(q w e)())

Результат: NIL

 

в) містить три складені об’єкти, і лише його другий елемент є атомом;

$ (CAR (CDR ‘(q w e)))

Результат: W

 

г) голова списку містить три атоми, а кількість атомів в усьому списку дорівнює

$(CAR ‘(q w e) (ATOM 3))

Результат: Q

 

д) містить тільки порожній список, а голова списку не є атомом.

$(CAR ‘() (ATOM ‘()))

Результат: NIL

 

е) голова та хвіст є списками з підсписками.

(CONS ‘(q w) ‘(r (t y)))

Результат: ((Q W) R (T Y))

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

a) (CONS NIL NIL)

Результат: NIL

 

б) (CONS (CAR ‘((q w))) (CDR ‘((q (w e)))))

Результат: ((QW)Q(WE))

 

в) (EQL (CDR ‘(q)) NIL)

Результат: T

 

г) (ATOM (CDR ‘(q NIL)))

Результат: NIL

 

д) (EQL NIL ‘NIL)

Результат: T

 

е) (PUSH nil nil) (EQL (ATOM ‘(q w)) nil)

Результат: NIL

 

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

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

$ (CONS (CAR ‘(A B C)) (CDR ‘(X Y Z)))

Результат: (A, Y, Z).

 

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

$ (CADDR (CADDR ‘((one 1) (two 2 3) (three 4 5 6))))

Результат: 5

 

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

$ (CDDR ‘((q w (r) t) y))

Результат: NIL

 

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

$ (SETQ t ‘((q (w (e) r) t) y))

$ (CONS (CONS (CAAR t) (CADAR t))

Результат: ((Q) W (E) R)

 

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

$ (SETQ a ‘(q (w e)))

$ (CAADR a) -> w (CADADR a) -> e

 

 

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

$ (cons (cons ‘(q w) nil) nil)

Результат: (((q w)))

 

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

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

$ (SETQ one 1 two 2 three 3)

$ (PSETQ one two two three thee one)

 

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

$ (PSETQ house sky sky house)

SKY

$ (PSETQ house sky sky house)

HOUSE

 

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

$ (CONS (CONS q q) q)

((q) q) q)

 

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

$ (SETQ w (CONS s (CONS s)))

(s s)

 

5. Не використовуючи селекторні функції:

а) дано: Val(a) = (q w e r t y)                зробити: Val(a) = q

$ (SETQ a ‘(q w e r t y))

$ (SETQ a (POP a))

Результат: q

 

б) дано: Val(a) = (q w e r t y)                зробити: Val(a) = (w)

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

$ (SETQ a (POP a)) Val(a) = w

$ (SETQ a (CONS aNIL))

 

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

(SET one ‘two)

Val(one) = two

(SETQ two ‘one)

Val(one) = two, Val(two) = one

(SET three two four ‘one two three)

Val(one) = two, Val(two) = one, Val(three) = one, Val(four) = four

(PSETQ four one three ‘four two three one four)

Val(one) = four, Val(two) = one, Val(three) = four, Val(four) = two

Висновок: в результаті виконання лабораторної роботи навчилися будувати списки, типи списків, функції Луспу та функції призначення.