WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

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

ГоловнаМатематика, Геометрія, Статистика → Визначення функцій в Ліспі - Реферат

Визначення функцій в Ліспі - Реферат

y)
Примітивна функція EQL використовується для порівняння атомів. Часто виникає потреба порівнювати списки. Напишемо функцію EQLIST, яка порівнює списки. Її побудуємо на основі наступних фактів:
1. Якщо перший список порожній, то, якщо і другий список порожній, повернути Т, інакше повернути NIL (або просто повернути (NULL другого списку)).
2. Якщо другий список порожній, повернути NIL.
3. Якщо голова першого списку не дорівнює голові другого списку, повернути NIL.
4. Перевірити рівність хвостів першого та другого списків.
$ (DEFUN EQLIST (lst1 lst2) $ (DEFUN NOT (obj)
((NULL lst1) (NULL lst2)) (EQL obj NIL) )
((NULL lst2) NIL)
((NOT (EQL (CAR lst1) (CAR lst2))) NIL)
(EQLIST (CDR lst1) (CDR lst2)) )
Функція NOT повертає NIL, якщо список не порожній і Т інакше.
Розглянемо задачу об'єднання списків. Роботу функції 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) $ (REVER '(q w e) NIL)
((NULL lst1) lst2) (e w q)
(REVER (CDR lst1) (CONS (CAR lst1) lst2)) )
Середовище системи muLisp
Середовище muLisp або поточний стан системи складається з усіх активних на даний момент структур даних, значень змінних та визначених функцій. Команда SAVE зберігає поточне середовище muLisp у вигляді SYS - файлу. Команда (SAVE 'C:HOME) зберігає середовище в файл HOME.SYS на диску C. Після успішного виконання команди запису повертається Т, інакше - NIL.
Середовище muLisp може бути завантажене за допомогою команди LOAD: (LOAD file). Якщо файл не знайдено, повертається NIL, інакше жодне значення не повертається, а mulisp починає працювати з новим середовищем.
Трасировка функцій в muLisp
Мова програмування muLisp для трасировки має програму debug.lsp, яка загружається в середовище Ліспу. Для того, щоб дозволити трасировку будь-якої функції необхідно дати команду (TRACE-FUNCTION func). Якщо після цього викликати функцію function, то на екрані відобразиться шлях виконання функції. Команда (UNTRACE-FUNCTION func) забороняє трасировку функції func. Якщо в тілі функції func існує виклик інших функцій, і ми хочемо побачити їх трасировку, необхідно дозволити їх трасировку. Вираз func=value в трасі означає те, що функція func повертає значення value.
Наприклад, після команд (TRACE-FUNCTION APPEND) (APPEND '(q w e) (r t y u)) на екрані відобразиться траса (спочатку перший стовпчик, потім - другий):
APPEND [(q w e) (r t y u)] APPEND = (r t y u)
APPEND [(w e) (r t y u)] APPEND = (e r t y u)
APPEND [(e) (r t y u)] APPEND = (w e r t y u)
APPEND [NIL (r t y u)] APPEND = (q w e r t y u)
Розглянемо трасу функції REVERSE з дозволом трасировки функції APPEND для виразу (REVERSE '(q w)) (спочатку перший стовпчик, потім - другий):
REVERSE [(q w)] REVERSE = (w)
REVERSE [(w)] APPEND [(w), (q)]
REVERSE [NIL] APPEND [NIL, (q)]
REVERSE = NIL APPEND = (q)
APPEND [NIL, (w)] APPEND = (w q)
APPEND = (w) REVERSE = (w q)
Завдання
I Варіант завдань
1. Написати функцію, яка знаходить:
a) третій елемент четвертого підсписку г) останній атом лінійного списку
б) перший елемент другого підсписку д) останній атом списку з підсписками
в) перший атом списку з підсписками е)перевіряє належність елемента до списку
2. Написати функцію REVERSE, не використовуючи функцій селектора та конструктора. Вказівка: використайте функції PUSH та POP.
3. Написати функцію, яка:
а) з вихідного списку робить множину в) знаходить різницю двох множин
б) об'єднує дві множини г) знаходить перетин двох множин
II Варіант завдань
1. Написати функції:
а) (REVERSE lst), де lst- список з підсписками. Функція повертає обернений на усіх рівнях список lst.
$ (reverse_all '(1 2 3 (q w e (r t) y) 7 9))
(9 7 (Y (T R) E W Q) 3 2 1)
б) (FIND_NEIGHBOURS lst node), де lst - список ребер графу (ребро графу є списком з двох чисел - номерів вершин), node - номер вершини. Функція повинна повернути список вершин, суміжних з вершиною node. Граф вважати неорієнтованим.
$ (find_neighbours '((1 2) (3 1) (4 5) (9 1) (2 3) (1 5)) 1)
(2 3 9 5)
в) (LINER lst), де lst - список з підсписками. Лінеризувати список lst.
$ (liner '(3 (q w e r (t) () y ) 4 (5) o (p () )))
(3 Q W E R T Y 4 5 O P)
г) (SYMDIFF lst1 lst2), де lst1 та lst2 - множини. Повернути їх симетричну різницю.
$ (symdiff '(2 3 4 5) '(3 41 1 5))
(2 4 41 1)
Loading...

 
 

Цікаве