Вікіпідручник

Common Lisp/Об'єкти Ліспу

< Common Lisp

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

ред.

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

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

Common Lisp (Коммон Лісп) є стандартом мови програмування. Існує декілька реалізацій стандарту. Серед найпоширеніших та найдоступніших (безкоштовних) можна назвати SBCL, Clozure CL, та CLISP. Ці реалізації працюють на багатьох операційних системах та процесорних архітектурах. Common Lisp є потужною мовою програмування, має великі функціональні засоби для обробки структур даних, створених користувачем. Common Lisp є символьною мовою програмування, яка призначена для обробки списків. (Lisp — List Processing). Будь-яка структура даних є об’єктом.

Робота з Ліспом нагадує роботу з кишеньковим калькулятором: користувач вводить вираз (він обов’язково повинен закінчуватися символом <RETURN> та мати збалансовану кількість дужок), який читає машина, потім обчислює (інтерпретує), та видає результат. Цей процес введення-читання-обчислення-видачі результату буде відбуватися в циклі доти, доки користувач не введе команду (QUIT), яка завершує роботу з Лісп-машиною і передає керування операційній системі.

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

ред.

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

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

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

Списки задаються переліком елементів, взятих в дужки, перед якими ставиться апостроф. Наприклад: '(ICE HEN) або '((ONE 1) (TWO 2) (THREE 3)).

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

ред.

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 називаються селекторними функціями, оскільки вони дають можливість вибирати або знищувати частину об’єкта[1]. Результатом функції (CAR list) завжди є перший елемент списку list, якщо він непорожній і NIL в іншому випадку. Результатом функції (CDR list) є список list без першого елемента, якщо list містить більш одного елемента і NIL в іншому випадку. 

(CAR '(q w e r t y)) ⇒ Q
 
(CDR '(q w e r t y)) ⇒ (W E R T Y)

(CAR '((one 1) (two 2))) ⇒ (ONE 1)

(CAR '()) ⇒ NIL

(CDR '(three)) ⇒ NIL

(CDR '((q w))) ⇒ NIL

(CDR '()) ⇒ NIL

За допомогою функцій CAR, CDR можна знаходити за даним списком будь-який його підсписок або атом. Дозволяється використовувати функції, які є комбінаціями CAR та CDR. Імена таких функцій починаються на C і закінчуються на R, а між ними знаходиться послідовність літер A та D[1], яка вказує шлях обчислення.[2] 

(CAR (CDR (CDR '(q w e r t y)))) ≡ (CADDR '(q w e r t y)) 
  ⇒ E

(CADDR '((q 1) (w 2) (e 3))) ≡ (CAR (CDR (CDR '((q 1) (w 2) (e 3)))))
  ⇒ (E 3)

(CDR (CDR '((q 1) (w 2) (e 3)))) ≡ (CDDR '((q 1) (w 2) (e 3)))
  ⇒ ((E 3))

(CAR (CAR '((q w)))) ≡ (CAAR '((q w)))
  ⇒ Q

Функція конструктора CONS використовується для додання об’єкту до заданого списку. Об’єкт який додається, стає головою списку[3]. 

(CONS '(q w) '(r (t y))) ⇒ ((Q W) R (T Y))

(CONS apple '(q w)) ⇒ (APPLE Q W)

(CONS '(q w) '(r t y)) ⇒ ((Q W) R T Y)

(CONS 5 NIL) ⇒ (5)

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

(CAR (CONS '(q w) '(r (t y)))) ⇒ (Q W)

(CAR (CONS 'apple NIL)) ⇒ APPLE

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

(EQL 'qw 'qw) ⇒ T

(EQL (CAR '(q w)) 'q) ⇒ T

(EQL (CAR '(q w)) NIL) ⇒ NIL

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

(ATOM 'qwerty) ⇒ T

(ATOM '(q w e)) ⇒ NIL

(ATOM '()) ⇒ T

(ATOM '(q)) ⇒ NIL

(ATOM 3) ⇒ T

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

ред.

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

  1. (SET symbol object) — заміна символа об’єктом[6]
  2. (SETQ sym1 form1 sym2 form2 …) — спеціальна форма функції SET[7]
  3. (PSETQ sym1 form1 sym2 form2 …) — спеціальна форма функції SET[8]
  4. (POP symbol) — повертає вершину стека (списку)[9]
  5. (PUSH symbol form) — кладе символ symbol в стек (список) form.[10]

Перед використанням змінної слід її задекларувати, для цього слід використати макро DEFVAR[11]:

DEFVAR символ [форма [документація]] [12]
тут, символ — назва змінної, форма — її початкове значення, документація — рядок з поясненням змінної. Якщо відсутня форма, змінна зветься незв'язною і не має жодного значення. Якщо змінну не задекларовано (не об'явлено) інтерпретатор Коммон Лісп може видати повідомлення про помилку. Наприклад:
$ (DEFVAR a 10 "Проста змінна")
$ a
10
$ (DEFVAR b '(1 2 3))
$ b
(1 2 3)
$ (DEFVAR c)
$ c
;; Повідомлення про помилку інтерпретатора, оскільки C не має значення

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

$ (DEFVAR FOX)
$ (SET 'fox '(a s d))
(A S D)
$ (SETQ fox '(a s d))
(A S D)

$ (DEFVAR VOWELS)
$ (SETQ vowels '(a e i o u))
(A E I O U)
$ (SETQ vowels (CONS 'y vowels))
(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). 

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

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

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

(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) = roadVal(road) = 4Val(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)

Завдання

ред.
  1. Побудувати список, який задовільняє наступним умовам:
    1. містить два підсписки, перший з яких має три атоми, а другий — чотири атоми;
    2. містить три атоми, але його хвіст дорівнює NIL;
    3. містить три складені об’єкти, і лише його другий елемент є атомом;
    4. голова списку містить три атоми, а кількість атомів в усьому списку дорівнює 3.
    5. містить тільки порожній список, а голова списку не є атомом.
    6. голова та хвіст є списками з підсписками.
  2. Що буде в результаті обчислення наступних виразів:
    1. (CONS NIL NIL)
    2. (CONS (CAR '((q w))) (CDR '((q (w e)))))
    3. (EQL (CDR '(q)) NIL)
    4. (ATOM (CDR '(q NIL)))
    5. (EQL NIL 'NIL)
    6. (PUSH nil nil) (EQL (ATOM '(q w)) nil)
  3. Скласти вираз, який би за вхідними даними побудував би заданий результат.
    1. дано: (A, B, C), (X, Y, Z) побудувати: (A, Y, Z).
    2. дано: ((one 1) (two 2 3) (three 4 5 6)) побудувати: 5.
    3. дано: ((q w (r) t) y) побудувати: NIL
    4. дано: ((q (w (e) r) t) y) побудувати: ((q) w (e) r)
    5. дано: (q (w e)) побудувати: w, e
    6. дано: (q w) побудувати: (((q w)))
  4. Скласти вираз, який надає значення вхідним даним та вираз, який будує заданий результат, використовуючи лише вихідні символи.
    1. дано: one=1, two=2, three=3зробити: one=2, two=3, three=1.
    2. дано: Val(house)=sky, Val(sky)=houseзробити: Val(sky)=sky, Val(house)=house
    3. дано: Val(lst)=(q)зробити: Val(lst)=(((q) q) q)
    4. дано: Val(q)=w, Val(w)=sзробити: Val(q)=(s s)
  5. Не використовуючи селекторні функції:
    1. дано: Val(a) = (q w e r t y) зробити: Val(a) = q
    2. дано: Val(a) = (q w e r t y) зробити: Val(a) = (w)
  6. Вказати значення всіх змінних після виконання наступних дій:
(SET one 'two)
(SETQ two 'one)
(SET three two four 'one two three)
(PSETQ four one three 'four two three one four)

Завдання II

ред.
  1. Побудувати список, який задовільняє наступним умовам:
    1. голова та хвіст списку дорівнює NIL.
    2. серед елементів списку є три списки, але жодного складного об’єкту.
    3. серед елементів списку немає атомів, хвіст голови не є порожнім списком, але хвіст хвоста є порожнім списком.
    4. усі елементи списку – атоми, при чому перший та третій елементи – символи, другий та четвертий – не символи, а п’ятий – не символ і не число.
  2. Що буде в результаті обчислення наступних виразів:
    1. (CADR '(nil (nil)))
    2. (CONS (ATOM '(ATOM '(q w e))) '(NIL))
    3. (CONS '(q w) '(e r) '(t y))
    4. (EQL (ATOM (CDR '(nil))) (CADDDR '(w e r t y))
    5. (EQL (CONS nil) (CADR '(q (nil) w)))
    6. (CDR '(CDR (CONS '(q) '(w))))
  3. Вказати значення всіх змінних після виконання наступних дій:
    1. (SETQ one two two three three one), (SET one three), (PSETQ one two two three three one)
    2. (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)), то після (SETQ a (CADR a)) буде a = b, b = (b c), c = ((a b)), а після (SETQ a (EVAL (CADR a))) буде a = (b c), b = (b c), c = ((a b)).

Відповіді

ред.

Примітки

ред.
  1. ↑ 1,0 1,1 Common Lisp HyperSpec, Accessor CAR, CDR, ....
  2. ↑ Дивіться також: Common Lisp HyperSpec, Accessor FIRST,....
  3. ↑ Common Lisp HyperSpec, Function CONS.
  4. ↑ Common Lisp HyperSpec, Function EQL.
  5. ↑ Common Lisp HyperSpec, Function ATOM.
  6. ↑ Common Lisp HyperSpec, Function SET.
  7. ↑ Common Lisp HyperSpec, Special Form SETQ.
  8. ↑ Common Lisp HyperSpec, Macro PSETQ.
  9. ↑ Common Lisp HyperSpec, Macro POP.
  10. ↑ Common Lisp HyperSpec, Macro PUSH.
  11. ↑ http://www.lisp.org/HyperSpec/Body/mac_defparametercm_defvar.html
  12. ↑ Common Lisp HyperSpec, Macro DEFPARAMETER, DEFVAR.

Див. також

ред.
Отримано з https://uk.wikibooks.org/w/index.php?title=Common_Lisp/Об%27єкти_Ліспу&oldid=34123