Функціональне програмування:Іспит
Матеріал з USIC Wiki
|
Ця стаття відноситься до групи довідкових статей для студентів ФІН. |
Типи даних Ліспу. Типи даних, змінні, числа, літери та символи, конси та списки.
Примітивними об’єктами даних є символи, числа та конси. muLisp має безліч функцій розпізнання, порівняння, комбінування та обробки цих об’єктів. Це дозволяє конструювати будь-які складні об’єкти даних. Як було сказано раніше, muLisp має два типи даних: атоми та списки. Атоми поділяються на символи та числа. Списки є підмножиною об’єктів, які мають більш загальну структуру — бінарне дерево. Вони створені за допомогою консів.
Символ є об’єктом даних, з яким пов’язано 4 атрибути, кожен з яких є вказівником на: — PRINT - ім’я. Це унікальний рядок ASCII символів, за допомогою якого система ідентифікує символ при операціях введення-виведення. PRINT - ім’я не може бути змінене. Імена обмежені за розміром: вони повинні мати не більше від 65536 символів. — поточне значення. Значенням символа може бути будь-який об’єкт даних, який зберігається в комірці пам’яті. Якщо в середовищі Ліспу ввести PRINT-ім‘я символу, то на виході буде його значення. Поточне значення доступно як CAR - елемент символа. — список властивостей. Він містить значення властивостей символа, проіндексова- них за ключем, його форма має вигляд: (ім’я1 значення1 ім’я2 значення2 ... ім’яN значенняN). При ініціалізації системи список властивостей є порожнім (дорівнює NIL). Його можна змінити за допомогою функцій властивостей та прапорців. Доступний як CDR - елемент символа. — визначення функції. При створенні символу в muLisp цей атрибут дорівнює “функція невизначена”. Визначення функції складається або за шаблонами машинної мови, або на D-коді. Значення цього атрибута можна отримати в результаті виконання функції флагів (GETD символ).
SYMBOLP є функція, яка розпізнає символ. Вона повертає Т, якщо аргумент є символом і NIL в протилежному випадку.
$ (SYMBOLP ‘XYZ)
T
$ (SYMBOLP ‘(q w))
NIL
В Коммон Ліспі (файл common.lsp) визначені функції SYMBOL-VALUE, яка повертає значення символа, та функція SYMBOL-PLIST, яка повертає весь список властивостей символа.
(DEFUN SYMBOL-VALUE (SYM)
((SYMBOLP SYM) (CAR SYM) ) )
(DEFUN SYMBOL-PLIST (SYM)
((SYMBOLP SYM) (CDR SYM) ) )
Узагальненою функцією присвоєння є SETF, яка визначена в common.lsp. Вона заносить данні в комірку пам’яті символа: (SETF <комірка пам’яті> <значення>). Через функцію SETF можна представити описані раніше функції SET та SETQ.
(SETQ x y) це (SETF x y)
(SET x y) це (SETF (SYMBOL-VALUE x) y)
Проміжки, дужки, коми, одинарні та подвійні лапки, крапка, крапка з комою відіграють спеціальну роль в Ліспі. Одинарним Escape-символом є \. Багатократним Еscape-символом є |. Спеціальні літери можуть використовуватися у PRINT-іменах символів, але для цього перед ними треба ставити \, або весь рядок брати в |. Вирази |q w e| та |sym(bol| є символами. Для використання літер \ та | в символах необхідно ставити перед ними \. Якщо виводиться на екран символ, який містить спеціальні літери, то він виводиться з багатократним escape-символом. Програмна змінна *PRINT-ESCAPE* булевського типу відповідає за виведення escape-символів. Якщо вона дорівнює NIL, то escape-символи на екран не виводяться. Подвійні лапки “ грають роль літери |. Розглянемо приклади (спочатку *PRINT-ESCAPE*=T):
$ (SETQ *PRINT-ESCAPE* NIL)
Число є іншим примітивним об’єктом. Воно може бути цілим або дробовим. Ціле число вводиться як послідовність цифр, перед якою може стояти знак мінус. За внутрішнім поданням цілі числа діляться на малі цілі (до 65536) та великі цілі. Оскільки значенням числа завжди є саме число, то немає необхідності перед ним ставити апостроф. Чотири атрибути характеризують число як об’єкт даних: — елемент тотожності. Це є вказівник на саме число. Він доступний як CAR-елемент числа. — знак. Значення атрибута знака доступне як CDR-елемент числа. — довжина. Якщо число є малим цілим, то цей атрибут містить значення цілого. Якщо число — велике ціле, то елемент ‘довжина’ містить довжину слова вектора числа. Якщо число дробове — елемент містить вказівник на його чисельник, який обов’язково повинен бути цілим (додатним або від’ємним). — вектор. Якщо число мале ціле, то значення атрибута є вказівником на інше мале ціле (хеш-з’єднувач). Якщо число велике ціле, то це поле містить вказівник на найменший значущий байт. Якщо число дробове — елемент містить вказівник на його знаменник, який повинен бути додатним цілим числом.
Функція порівняння EQL може використовуватися для порівняння чисел. Але більш загальною функцією для порівняння множини чисел є рівність:
$ (EQL -3 4)
NIL
$ (EQL 4 4)
T
$ (= 2 2 2)
T
$ (= 2 2 3 2)
NIL
Дробові числа можуть подаватися у десятковому вигляді та з дробовою рискою. Внутрішня змінна *PRINT-POINT* відповідає за тип виведення дробових чисел. Якщо вона дорівнює NIL, то всі дробові числа подаються на виведення з дробовою рискою. Якщо *PRINT-POINT* = n, то дробові числа виводяться з n знаками після десяткової коми. При введенні дробового числа воно автоматично скорочується.
$ 3/4
3/4
$ 3/9
1/3
$ 5/1
5
$ 12/9
4/3
Внутрішня змінна *PRINT-BASE* відповідає за основу системи числення, в якій обробляються числа. Якщо значення цієї змінної є цілим та перебуває в інтервалі від 2 до 32, то такою і буде основа системи числення, інакше muLisp працює в десятковій системі числення.
$ (SETQ ten 10)
$ (SETQ *PRINT-BASE* 16)
$ ten
0A
$ (SETQ *PRINT-BASE* 2) $ 234
$ ten
1010
Функцією, яка розпізнає цілі числа, є INTEGERP. Вона повертає Т, якщо її аргумент є цілим числом та NIL інакше. Функція NUMBERP розпізнає число.
$ (INTEGERP 100)
T
$ (NUMBERP 3.5)
T
Число в подвійних лапках завжди є символом:
$ (SYMBOLP “23”)
T
$ (NUMBERP “23”)
NIL
Символи та числа є атомами. Наступні вирази повертають істину: (ATOM 3.5), (ATOM “23”), (ATOM ‘APPLE).
Конс є примітивним об’єктом, який вказує на будь-які два інші об’єкти даних.. Він не є атомом. Назва конс пішла від функції конструктора CONS. Кожен конс склада- ється з CAR- та CDR- елементів. Конс часто називають точковою парою. Якщо X і Y об’єкти даних, то вираз (X . Y) є консом, CAR-елемент якого є X, а CDR-елемент – Y.
$ (SETQ A (cons X Y))
$ A
(X . Y)
$ (CAR A)
X
$ (CDR A)
Y
$ (CDR ‘(R . S))
S
За допомогою точкового подання можна показати структуру будь-якого об’єкту. Список (x1 x2 x3) є ланцюгом консів, які зв’язані за допомогою CDR- елементів. Його CAR- елементи вказують на елементи списку. CDR- елемент останнього конса вказує на NIL. Вказаний список можна подати у вигляді (x1 . (x2 . (x3 . NIL))). Функція READ читання виразу розпізнає як точкове подання виразу, так і спискове. Функція виведення PRINT виводить об’єкти в списковому поданні.
$ (SETQ a ‘(q . (w . nil))
(q w)
$ a
(q w)
$ (CONSP ‘(q . w))
T
$ (CONSP (q w))
T
Функція (CONSP obj) розпізнає конси. Список не є примітивним об’єктом, а є ланцюгом консів. Отже, результатом застосування функції CONSP до списку буде Т.
Функції властивостей
Розглянемо, як можна працювати зі списком властивостей символа. Його можна по необхідності створювати, обробляти та видаляти. Властивості символа є глобальними, тобто доступними з довільної точки програми, поки вони не будуть явно змінені чи видалені. Використання символа в якості змінної чи імені функції не впливає на список властивостей.
Функції властивостей керують властивостями символів. CDR - елемент символа вказує на список властивостей. Разом з функціями флагів вони полегшують процес побудови динамічних баз даних.
1. (PUT <символ> <ключ> <об’єкт>). У список властивостей <символа> кладеться значення <об’єкта> відповідно до вказівника <ключ>.
$ (PUT ‘capital ‘usa ‘washington)
2. (GET <символ> <ключ>). Повертає значення властивості, яке відповідає <символу> відповідно до вказівника <ключ>. Якщо такого вказівника не існує, то повертається NIL. Якщо змінна capital має властивості, які їй були надані у попередньому прикладі, то:
$ (GET ‘capital ‘usa)
washington
3. (REMPROP <символ> <ключ>). Видалення зі списка властивостей <символа> властивості, яка відповідає <ключу>. Повертається старе значення властивості, якщо воно знайдено, та NIL – інакше. Нехай символ capital має три попередні властивості.
(REMPROP ‘capital ‘usa)
washington
Функції розпізнання
Функції розпізнання — це твердження, які використовуються для розпізнання або ідентифікації об’єктів даних muLisp. Ці функції мають тільки один аргумент, а повертають булеве значення. Вони розпізнають об’єкт, який може мати довільну структуру. Ми вже розглянули деякі функції розпізнання: SYMBOLP, INTEGERP, NUMBERP, ATOM, LISTP, NULL. Розглянемо інші.
(ZEROP <obj>). Повертає Т, якщо obj — число 0.
(PLUSP <obj>). Повертає Т, якщо obj — додатне ціле число.
(MINUSP <obj>). Повертає Т, якщо obj — від’ємне ціле число.
(ODDP <obj>). Повертає Т, якщо obj — непарне ціле число.
(EVENP <obj>). Повертає Т, якщо obj — парне ціле число.
Функція (ASCII <sym>) повертає ASCII-код символа <sym>. Функція (ASCII <num>) повертає символ, ASCII код якого дорівнює числу <num>. Для того, щоб визначити, чи є символ sym літерою, можна використати функцію: (< (ASCII ‘a) (ASCII sym) (ASCII ‘z)). Оскільки muLisp не розрізняє малі та великі літери, то (ASCII ‘s) = (ASCII ‘S) для будь-якого символа s. Функція ISCHAR розпізнає літери. Для знаходження ASCII кодів символів, які позначають цифри, необхідно використовувати одинарний Escape-символ.
Наступні функції дають можливість розпізнавати символи та числа.
(ALPHA-CHAR-P <obj>) – повертає T, якщо <obj> – літера.
(NUMERIC-CHAR-P <obj>) – повертає T, якщо <obj> – цифра.
(ALPHANUMERICP <obj>) – повертає T, якщо <obj> – літера або цифра.
Зазначимо, що символ проміжку (‘ ‘ ) є літерою.
Функція як головий засіб програмування в Ліспі. Способи визначення функцій.
Поряд з примітивними функціями можуть існувати функції, визначені користувачем. Функція викликається набором аргументів і повертає єдине значення. Визначення функції в Ліспі має наступний вигляд:
(DEFUN name (arg1 arg2 ...) task1 task 2 . . . . . )
name — ім’я функції, arg1, arg2, ... — аргументи (параметри). Тіло функції містить послідовність задач. Ключове слово DEFUN виникло з DEfine FUNction.
$ (DEFUN FIRST (lst) (CAR lst) )
$ (FIRST ‘(q w e r t y))
q
$ (DEFUN THIRD (lst)(CADDR lst) )
$ (THIRD ‘(q w e r t y))
e
Визначимо функцію NULL, яка розпізнає порожній список. Вона повертає істину, якщо її аргументом є порожній список і хибність в іншому випадку.
$ (DEFUN NULL (obj)(EQL obj NIL) )
$ (NULL ‘(q w e r))
F
$ (NULL (CDR ‘(r)))
T
Нам вже відомі три функції розпізнання: EQL, ATOM, NULL. Функції, які застосовуються для перевірки певних умов та можуть повертати лише два значення – істини чи хиби, називаються предикатами.
Тіло функції складається з послідовності завдань. Завдання можуть бути двох типів: прості та умовними. Будь-яке завдання береться в круглі дужки і може розглядатися як список виразів, які треба проінтерпретувати. Якщо завдання є атомом або його перший елемент є атомом, то таке завдання називається простим. Наприклад, (CONS ‘NR LST). Якщо перший елемент списка, який описує завдання не є атомом, то таке завдання називається умовним. Наприклад, ((ATOM lst) (CONS expr lst)). В умовному завданні перший елемент списку обов’язково є предикатом. Якщо значення предикату NIL, то значення завдання стає рівним NIL і Лісп переходить до виконання наступного завдання. Якщо предикат повертає не NIL, відбувається виконання хвосту списку завдання, а інші завдання ігноруються. Якщо предикат повертає Т, а хвіст завдання порожній, то результатом всієї функції буде T.
Списки як структура даних в Ліспі. Функції роботи зі списками. Прості та складні списки.
Напишемо предикат, який розпізнає списки. Якщо аргументом є список, то предикат повертає істину, інакше — хибність. Функцію LISTP можна проінтерпретувати наступним чином: “Якщо obj є атомом, то повернути NIL, інакше повернути T”.
$ (DEFUN LISTP (obj) ((ATOM obj) NIL) T ) $ (DEFUN LISTP (obj)((NULL obj))((ATOM obj) NIL) T )
В другій колонці написано предикат LISTP, який розпізнає додатково порожній список (повертає істину). Перше завдання є умовним, хвіст якого порожній. Його можна проінтерпретувати так: перевірити об’єкт obj на порожній список, і якщо він є таким, передати як результат функції істину. Немає потреби писати: ((NULL obj) T), оскільки це те ж саме, що і ((NULL obj)). Останнім завданням цих предикатів є атом Т. Це означає, що якщо жодне з умовних завдань не виконане (лише за цієї умови керування програмою дійде до останнього завдання), то як результат функції повернути Т. Для другого визначення функції LISTP маємо:
$ (LISTP ‘tree) NIL $ (LISTP ‘()) T $ (LISTP ‘(q w e r t y)) T
Для кращого розуміння роботи тіла функції та простих і умовних завдань розглянемо функцію sm та результати, які вона буде генерувати при певних вхідних значеннях:
$ (DEFUN sm (lst)((NULL lst) 10 1)(SETQ b 2)((CDR lst) 12)(SETQ b 3) )
$ (sm ‘()) 1 $ (sm ‘(q w e)) 12
Як бачимо, після виконання простого завдання керування завжди передається наступному завданню (якщо таке є). Якщо предикат умовного завдання істинний, то виконується його хвіст і повертається результат останнього виразу хвоста.
Вмонтована функція (LIST x1 ... xn) утворює та видає список, елементами якого є x1, ..., xn. Якщо аргументи не задані, результатом буде NIL.
$ (LIST ‘a ‘b ‘c ‘d) (a b c d) $ (LIST) NIL
Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку.
$ (DEFUUN MEMBER (nam lst) ((NULL lst) NIL) ((EQL nam (CAR lst)) T) (MEMBER nam (CDR lst)) )
Розглянемо рекурсивну функцію: REMBER (REMove memBER), яка має два аргументи — атом obj та список lst і яка видаляє перше зустрічання атома obj в списку lst.
$ (DEFUN REMBER (obj lst)
((NULL lst) NIL)
((EQL obj (CAR lst)) (CDR lst))
(CONS (CAR lst)
(REMBER obj (CDR lst))) )
$ (REMBER ‘a ‘(q a w e r t a y))
(q w e r t a y)
Примітивна функція EQL використовується лише для порівняння атомів. Часто виникає потреба порівнювати списки. Напишемо функцію EQLIST, яка порівнює списки. Її побудуємо на основі наступних фактів:
1. Якщо перший список порожній, то, якщо і другий список порожній, повернути Т, інакше повернути NIL (або просто повернути (NULL другого списку)). 2. Якщо другий список порожній, повернути NIL. 3. Якщо голова першого списку не дорівнює голові другого списку, повернути NIL. 4. Перевірити рівність хвостів першого та другого списків.
$ (DEFUN EQLIST (lst1 lst2)
((NULL lst1) (NULL lst2))
((NULL lst2) NIL)
((NOT (EQL (CAR lst1) (CAR lst2))) NIL)
(EQLIST (CDR lst1) (CDR lst2)) )
Розглянемо задачу об’єднання списків. Роботу функції APPEND, аргументами якої є два списки lst1 та lst2, можна описати наступним чином:
1. Якщо lst1 порожній, повернути lst2. 2. З’єднати голову першого списку зі списком, який отримано в результаті об’єднання хвоста першого списку з другим списком. $ (DEFUN APPEND (lst1 lst2)
((NULL lst1) lst2) (CONS (CAR lst1) (APPEND (CDR lst1) lst2)) )
Функція (REVERSE lst1) обертає список lst1. Якщо вихідний список порожній, то і результатом буде порожній список. Інакше необхідно об’єднати обернений хвіст вихідного списку з його першим елементом. Оскільки на вхід другого аргумента функції APPEND повинен подаватися список, необхідно з першого елемента списку зробити список, який складається лише з нього. Це виконує команда (CONS (CAR lst) NIL).
$ (DEFUN REVERSE (lst)
((NULL lst) NIL) (APPEND (REVERSE (CDR lst)) (CONS (CAR lst) NIL)) )
Напишемо функцію REVERSE без використання функції APPEND. Для цього побудуємо функцію REVERSE з двома аргументами на принципі обробки стеку. Вихідний список — стек символів. Якщо він порожній, то і результуючий стек буде порожнім. Інакше взяти символ з вершини стеку і покласти його на другий стек. Другий стек при виклику повинен бути NIL: (REVER <list> NIL).
$ (DEFUN REVER (lst1 lst2) ((NULL lst1) lst2) (REVER (CDR lst1) (CONS (CAR lst1) lst2)) )
$ (REVER ‘(q w e) NIL) (e w q)
Наступні функції є вмонтованими: FIRST, SECOND, …, TENTH з єдиним аргументом списком і повертають відповідно перший, другий, ..., десятий його елементи. (LAST lst) повертає останній елемент списку lst. (LENGTH lst) повертає довжину списку lst.
$ (FOURTH ‘(3 4 5 k j h g) k
$ (LAST ‘(3 4 5 k j h g) g
$ (LENGTH ‘(3 4 5 k j h g) 7
Управляючі та циклічні конструкції Ліспу.
Булеві оператори:
NOT
(NOT object)
>(not (zerop 1))
T
>(not nil)
T
AND
(AND arg1 arg2 arg3 …)
>(and 5 nil)
NIL
>(and 'a 'b)
B
OR
(OR arg1 arg2 arg3 …)
>(or t nil)
T
PROG1, PROG2 та PROGN
> (prog1 (setf x ’foo)
(setf x ’bar)
(setf x ’baz)
(format t "~&X is ~S" x))
X is BAZ
FOO
LET (Встановлює локальні змінні)
(defun rectangle (dim)
(let ((len (car dim)) (wid (cadr dim)))
(print (list 'area (* len wid)))
(print (list 'perimeter (* (+ len wid) 2))))))
>(rectangle '(4 5))
(area 20)
(perimetr 18)
(perimetr 18)
Умовні оператори:
IF
(if test then [else])
Приклад:
(if (atom x) 'аtоm 'not-аtom)
WHEN
(when test form1 form2 …)
UNLESS
(unless test form1 form2 …)
CASE
(case keyform
(key1 form1)
(key2 form2)
…)
CASE
>(setq color ‘red)
RED
>(case color
(blue "Blue is okay")
(red "Red is actually her favorite color")
(green "Are you nuts?")))
"Red is actually her favorite color")
COND
(cond
(test1 form1)
(test2 form2)
(test3 form3)
...)
COND та IF
(cond
(p …)
(r …)
(q …)(t …))
Цикли
LOOP
(LOOP form1 form2..)
Нескінченний цикл
LOOP
(defun add-integers (last)
(let (( count 1) (total 1))
(loop
(cond (( equal count last) (return total)))
(setq count (+ 1 count))
(setq total (+ total count)))))
>(add-integers 5)
15
DO
(DO ((var1 init1 [step1])
(var2 init2 [step2])
...)
(test action-1,.. action-n)
body)
DO
(defun list-abs (lis)
(do ((oldlist lis (cdr oldlist))
(newlist nil (cons (abs (car oldlist)) newlist)))
((null oldlist) (reverse newlist)))))
DO
>(list-abs ‘(1 -2 3 -4 5 -6))
(1 2 3 4 5 6)
DOTIMES
(DOTIMES (var n [result-form])
body)
DOTIMES
> (dotimes (i 4)
(format t "~&I is ~S." i))
I is 0.
I is 1.
I is 2.
I is 3.
NIL
DOLIST
(DOLIST (var list [result-form])
body)
Макроси в Ліспі.
Як працюють макроси:
(nil! x) (setq x nil)
>(defmacro nil! (var)
(list ‘setq var nil))
NIL!
Кажемо Ліспу: “Коли побачиш вираз, що виглядає (nil! var) заміни його на форму (setq var nil)”
Лісп розпізнає макрос (nil! x) та:
1. будує вираз, що зазначено у визначенні макросу
2. обчислює вираз в місці виклику макросу
При написанні макросів слід враховувати, що в них діє зворотнє блокування:
`(a b c) <--> ’(a b c)
`(a b c) <--> (list ’a ’b ’c)
`(a ,b c ,d) <--> (list ’a b ’c d)
Приклад:
>(defmacro mac(x) `(1+ ,x))
MAC
Залежність від макросів:
1. Визначайте макроси перед визначенням функцій або макросів, що їх викликають.
2. Коли перевизначаєте макрос, також перекомпілюйте всі функції (макроси) які його викликають.
Функціонали Ліспу.
1. FUNCALL (<функцiя> <arg1> <arg2> ... <argN>)
Виконуються дiї функцiї <функцiя> над аргументами та повертається результат. <Функцiя> повинна бути або iменем обчислюваної функцiї, або тiлом LAMBDA. Якщо <функцiя> - це iм'я макро або невизначеної функцiї, виникає переривання по помилцi <невизначена функцiя>.
$ (FUNCALL 'CONS 'a '(b c d)) $ (FUNCALL '(LAMBDA (n) (* n n)) 5)
(a b c d) 25
2. EVAL <об'єкт>
Iнтерпретатор Лiспа називається EVAL, його можна як i iншi функцiї викликати з програми. У звичайнiй роботi iнтерпретатор викликати не має потреби, оскiльки його виклик має мiсце неявно. Зайвий виклик iнтерпретатора може зняти ефект блокування (QUOTE), або дозволить знайти значення виразу. EVAL - це унiверсальна функцiя Лiспа, яка може обчислити довiльний правильно побудований лiсповський вираз.
4. APPLY <функцiя> <арг1> <арг2> ... <арг-список>
Застосовує функцiю до списку аргументiв. (APPLY f x1 x2 ... xN) еквiвалентно (f x1 x2 ... xN). Використання функцiї APPLY є бiльщ гнучким у порiвняннi з прямим викликом функцiї. Дiє як i функцiя FUNCALL, тiльки аргументи функцiї приймає не окремо, а списком.
Якщо функцiя - iм'я визначеної користувачем функцiї або тiло LAMBDA, APPLY
пов'язує формальнi аргументи функцiї з фактичними аргументами, обчислює тiло
функцiї, вiдтворює вихiднi значення формальних аргументiв i повертає значення
обчислення тiла функцiї.
Якщо функцiя - не iм'я функцiї i не тiло LAMBDA, APPLY генерує переривання по
помилцi "невизначена функцiя".
$ (APPLY 'CONS '(a (b c d))) $ (SETQ z '(LAMBDA (n) (* n n))) (a b c d) $ (APPLY z '(4)) 16
5. UNDEFINED <символ> <форма1> ... <формаN>
Ця функцiя iнiцiює преривання по помилцi "Невизначена функцiя". Ця функцiя керування помилками використовується тодi, коли намагаються обчислити форму, CAR-елемент якої є символом, який не має визначення функцiї.
Функцiї модифiкатора виконують переадресацiю вказiвникiв в структурах даних
мови програмування Лiсп.
1. RPLACA <об'єкт1> <об'єкт2>. Вiдбувається замiна CAR-елемента об'єкта1
вказiвником на об'єкт2, повертається модифiкований об'єкт. Якщо об'єкт1 -
список, то перший елемент списка замiнюється на об'єкт2. Якщо об'єкт1 -
бiнарне дерево, то його лiвий син замiнюється на об'єкт2. Якщо об'єкт1 -
символ (aле не NIL), то символ приймає значення об'єкт2.
$ (SETQ a '(a b c d)) $ (SETQ b '((1 . 2) . (3 . 4))) $ (SETQ s 'd)
$ (RPLACA a '(11 12)) $ (RPLACA b 5) $ (RPLACA s 'g)
((11 12) b c d) (5 . (3 . 4)) Val(s)=d,Val(d) = g
2. RPLACD <об'єкт1> <об'єкт2>. Вiдбувається замiна CDR-елемента об'єкта1
вказiвником на об'єкт2, повертається модифiкований об'єкт. RPLACA та RPLACD
є основними функцiями, якi змiнюють фiзичну структуру спискiв. Їх можна
представити через узагальнену функцiю присвоєння SETF:
(RPLACA x y) - це (SETF (CAR x) y) (RPLACD x y) - це (SETF (CDR x) y)
3. NSUBSTITUTE <новий><старий> <список> <тест>. Модифiкуються конси найвищого
рiвня списку. Старi елементи замiнюються на новi на нульовому рiвнi
вкладеностi, для яких перевiрка по тесту не дорiвнює NIL. Якщо тест не
вказано, то по замовченню тест = EQL.
$ (NSUBSTITUTE 1 3 '(4 5 6 (3 3 4 5) 3 4 1)) (4 5 6 (3 3 4 5) 1 4 1)
$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) >) $ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) <) (10 5 6 10 10 10) (4 5 10 3 4 1)
4. NSUBST <новий><старий> <список> <тест>. Функцiя працює як i NSUBSTITUTE,
але модифiкуються конси всiх рiвнiв списку.
$ (NSUBST 1 3 '(4 5 6 (3 3 4 5) 3 4 1)) (4 5 6 (1 1 4 5) 1 4 1)
5. DELETE <елемент> <список> <тест>. Вилучає зi списку всi елементи, для яких
ознака перевiрки за тестом не дорiвнює NIL.
$ (DELETE 3 '(1 2 3 4 3 2 1)) (1 2 4 2 1)
6. NREVERSE <список> <об'єкт>. Обертає елементи списку, зчеплених з об'єктом.
$ (NREVERSE '(a b c d)) $ (NREVERSE '(1 2 3 (1 2 3) 4 5 6) '(1 2 3)) (d c b a) (6 5 4 (1 2 3) 3 2 1 1 2 3)
7. NBUTLAST <список> <n>. Якщо n - нуль або додатне цiле, то функцiя NBUTLAST
повертає список без n останнiх елементiв (вiдбувається замiна n-го конса,
взятого з кiнця списку на NIL). Якщо другий аргумент не вказано, то за
замовченням n=1.
$ (NBUTLAST '(a b c d e)) $ (NBUTLAST '(a b c d e) 3) (a b c d) (a b)
8. NCONC <список1> <список2> ... <списокN>. Повертається список, який
складається з елементiв спискiв - аргументiв у вказаному порядку. Вiдбувається
модифiкацiя останнiх CDR-елементiв спискiв. Якщо виконати команду
(NCONC list list), де list - будь-який список, то результатом буде
циркулянтний список, процес побудови якого буде нескiнченним.
$ (NCONC '(1 2) '(3 4) '(5 6 7)) (1 2 3 4 5 6 7)
9. SPLIT <список>. Розбиває список на два списки посерединi. Значенням списку
стає його перша половина. Функцiя SPLIT повертає другу половину списку.
$ (SETQ a '(1 2 3 4 5 6)) $ a $ (SPLIT a) (1 2 3) (4 5 6)
10. SORT <список> <тест>. Сортуються елементи списку на основi тесту.
$ (SORT '(2 5 3 4 1 6 8 9 7) >) (9 8 7 6 5 4 3 2 1)
Реалізація бінарних дерев в Ліспі.
Означення. Деревом називається граф без циклів, в якому виділено окрему вершину, яку називають коренем дерева.
Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру (Значення . (Лівий син . Правий син)), де лівий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).
Функція INSEL вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Інакше вставити елемент в ліве піддерево якщо n менше за значення поточної вершини або в праве піддерево, якщо більше. Функція INSL створює за списком сортуюче дерево, вершинами якого будуть всі елементи списка. Дерево називається сортуючим, оскільки при обході його зліва направо ми отримаємо відсортований список елементів у зростаючому порядку.
(DEFUN insel (n tree)
((NULL tree) (CONS n (CONS NIL NIL)))
((> n (CAR tree)) (cons (car tree) (cons (cadr tree) (insel n (cddr tree)))))
(cons (car tree) (cons (insel n (cadr tree)) (cddr tree))) )
(DEFUN INSL (lst tree)
((NULL lst) tree)
(SETQ tree (insel (car lst) tree))
(INSL (CDR lst) tree) )
Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) — обхід згори вниз, PLR (Print Left-Right) — обхід зліва направо.
(DEFUN PUD (tree)
((NULL tree))
(PRIN1 (CAR tree)) (SPACES 3)
(PUD (CADR tree))
(PUD (CDDR tree)) )
(DEFUN PLR (tree)
((NULL tree))
(PLR (CADR tree))
(PRIN1 (CAR tree)) (SPACES 3)
(PLR (CDDR tree)) )
Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає лівим піддеревом і навпаки.
(DEFUN REVT (tree)
((NULL tree) NIL)
(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )
Функція HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між висотами лівого та правого піддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.
(DEFUN HEIGHT (tree)
((NULL tree) 0)
(MAX (ADD1 (HEIGHT (CADR tree))) (ADD1 (HEIGHT (CDDR tree)))) )
Робота з графами в Ліспі.
Функції модифікатори в Ліспі.
Функції модифікатори
RPLACA
(RPLACA obj1 obj2)
>(setq a ‘(a b c d))
>(rplaca a ‘(11 12))
((11 12) b c d)
>a
((11 12) b c d)
RPLACA
>(setq b ‘((1 . 2).(3 . 4))
>(rplaca b 5)
(5 3 . 4)
RPLACD
>(setq c ‘(1 2 3 4))
>(rplac c ‘(a b))
(1 a b)
(RPLACA x y)<-->(setf (car x) y)
(RPLACD x y)<-->(setf (cdr x) y)
NSUBSTITUTE
>(nsubstitute 1 3 ‘(4 5 6 (3 3 4 5) 3 4 1))
(4 5 6 (3 3 4 5) 1 4 1)
>(nsubstitute 10 5 ‘(4 5 6 3 4 1) :test #’>)
(10 5 6 10 10 10)
>(nsubstitute 10 5 ‘(4 5 6 3 4 1) :test #’<)
(4 5 10 3 4 1)
NSUBST
>(nsubst 1 3 ‘(4 5 6 (3 4 3 5) 3 4 1))
(4 5 6 (1 4 1 5) 1 4 1)
DELETE
>(delete 3 ‘(1 2 3 4 3 2 1))
(1 2 4 2 1)
NBUTLAST
>(nbutlast ‘(4 5 6))
(4 5)
>(nbutlast ‘(4 5 6 7 8 9) 3)
(4 5 6)
NREVERSE
>(nreverse ‘(a b c d))
(D C B A)
>(nreverse ‘(1 2 3(1 2 3)4 5 6))
(6 5 4 (1 2 3) 3 2 1)
NCONC
>(nconc ‘(1 2) ‘(3 4) ‘(5 6 7))
(1 2 3 4 5 6 7)
>(setq a ‘(1 2 3 4))
>(nconc a ‘(8 9 0))
(1 2 3 4 8 9 0)
>a
(1 2 3 4 8 9 0)
SORT
>(setq a ’(7 1 8 2 3 5 4 0)
>(sort a ‘<)
(0 1 2 3 4 5 6 7 8)
>a
(0 1 2 3 4 5 6 7 8)
Обчислювані та необчислювані функцї Ліспу.
Обчислюванi функцiї необхiднi в тих випадках коли необхiдно безпосередньо обчислити вираз або звернутися до функцiй. Визначенням функцiї є список, який складається з трьох частин: iменi типу функцiї, формальних параметрiв та тiла функцiї.
CAR-елементом визначення функцiї є iм'я типу фукцiї - LAMBDA, NLAMBDA чи MACRO.
Тип функцiї дає iнтерпретаторовi iнформацiю про те, як використовувати дану
функцiю.
Функцiя типу NLAMBDA називається необчислюваною. Якщо викликається необчислювана функцiя, то їй аргументи передаються без обчислення - так, як вони стоять в рядку виклику. Пояснимо це на прикладi. Визначимо двi функцiї f1 та f2, якi на перший погляд однаковi:
(DEFUN f1 (LAMBDA (x y) (DEFUN f2 (NLAMBDA (x y) (+ x y)) ) (+ x y)) )
Якщо викликати (f1 5 6) або (f2 5 6), то результат буде однаковим - 11. Нехай змiнним k та l присвоєнi деякi значення: (SETQ k 5 l 6). Тодi
$ (f1 k l) $ (f2 k l) 11 помилка: (+ k l) / а не (+ 5 6),
