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

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

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

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

функції 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 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 ). Якщо файл не знайдено, повертається NIL, інакше жодне значення не повертається, а mulisp починає працювати з новим середовищем.
Трасировка функцій в muLisp.
Мова програмування muLisp для трасировки має програму debug.lsp, яка загружається в середовище Ліспу. Для того, щоб дозволити трасировку будь-якої функції необхідно дати команду (TRACE-FUNCTION ). Якщо після цього викликати функцію function, то на екрані відобразиться шлях виконання функції. Команда (UNTRACE-FUNCTION ) забороняє трасировку функції . Якщо в тілі функції існує виклик інших функцій, і ми хочемо побачити їх трасировку, необхідно дозволити їх трасировку. Вираз = в трасі означає те, що функція повертає значення .
Наприклад, після команд (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)
Завдання.
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)
Відповіді.
1. a) $ (DEFUN F1 (lst) б) $ (DEFUN F2 (lst)
(CADDR (CADDDR lst))) ) (CAADR lst) )
в) $ (DEFUN FATOM (lst) г) $ (DEFUN LAST (lst)
((ATOM (CAR lst) (CAR lst)) ((CDR lst) (LAST (CDR lst)))
(FATOM (CAR lst)) ) (CAR lst) )
д) $ (DEFUN FLAST (lst) е) $ (DEFUN IN (obj lst)
((ATOM lst) lst) ((NULL lst) NIL)
((CDR lst) (FLAST (CDR lst))) ((EQL obj (CAR lst)) T)
(FLAST (CAR lst)) ) (IN obj (CDR lst)) )
2. $ (DEFUN rev (lst1 lst2)
((NULL lst1) lst2)
(PUSH (POP lst1) lst2)
(REV lst1 lst2) )
3. а) $ (DEFUN NO-DOUBLES(lst)
(NULL lst) NIL)
(CONS (CAR lst) (NO-DOUBLES (REMBER-ALL (CAR lst) lst))) )
б) $ (DEFUN UNION (lst1 lst2)
(NO-DOUBLES (APPEND lst1 lst2)) )
в) $ (DEFIN MINUS (lst1 lst2)
((NULL lst2) lst1)
(MINUS (REMBER (CAR lst2) lst1) (CDR lst2)) )
г) $ (DEFUN INTERSECT (lst1 lst2)
((NULL lst1) NIL)
((IN (CAR lst1) lst2) (CONS (CAR lst1) (INTERSECT (CDR lst1) lst2)))
(INTERSECT (CDR lst1) lst2) )
II Варіант завдань
а) (DEFUN REVERSE_ALL (lst)
((NULL lst) NIL)
((ATOM (CAR lst)) (APPEND (REVERSE_ALL (CDR lst)) (CONS (CAR lst))))
(APPEND (REVERSE_ALL (CDR lst)) (CONS (REVERSE_ALL (CAR lst)))) )
б) (DEFUN find_neighbours (lst node)
((NULL lst) NIL)
((EQL (CAAR lst) node) (CONS (CADAR lst) (find_neighbours (CDR lst) node)))
((EQL (CADAR lst) node) (CONS (CAAR lst) (find_neighbours (CDR lst) node)))
(find_neighbours (CDR lst) node) )
в) (DEFUN liner (lst)
((NULL lst) NIL)
((LISTP (CAR lst)) (APPEND (liner (CAR lst)) (liner (CDR lst))))
(CONS (CAR lst) (liner (CDR lst))) )
г) (DEFUN symdiff (lst1 lst2)
(UNION (minus lst1 lst2) (minus lst2 lst1)) )
Loading...

 
 

Цікаве