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

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

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

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


Реферат на тему:
Визначення функцій в Ліспі
Поряд з примітивними функціями можуть існувати функції, визначені користувачем. Функція викликається набором аргументів і повертає єдине значення. Визначення функції в Ліспі має наступний вигляд:
(DEFUN name (arg1 arg2 ...)
task1
task 2
. . . . . )
де name - ім'я функції, arg1, arg2, ... - аргументи (параметри). Тіло функції містить послідовність задач. Ключове слово DEFUN виникло з DEfine FUNction.
$ (DEFUN FIRST (lst) $ (FIRST '(q w e r t y))
(CAR lst) ) q
$ (DEFUN THIRD (lst) $ (THIRD '(q w e r t y))
(CADDR lst) ) e
Визначимо функцію NULL, яка розпізнає порожній список. Вона повертає істину, якщо її аргументом є порожній список і хибність в іншому випадку.
$ (DEFUN NULL (obj) $ (NULL '(q w e r)) $ (NULL (CDR '(r)))
(EQL obj NIL) ) F T
Нам вже відомі три функції розпізнання: EQL, ATOM, NULL. Функції, які застосовуються для перевірки певних умов та можуть повертати лише два значення - істини чи хиби, називаються предикатами.
Тіло функції складається з послідовності завдань. Завдання можуть бути двох типів: прості та умовними. Будь-яке завдання береться в круглі дужки і може розглядатися як список виразів, які треба проінтерпретувати.
Якщо завдання є атомом або його перший елемент є атомом, то таке завдання називається простим. Наприклад, (CONS 'NR LST).
Якщо перший елемент списка, який описує завдання не є атомом, то таке завдання називається умовним. Наприклад, ((ATOM lst) (CONS expr lst)).
В умовному завданні перший елемент списку обов'язково є предикатом. Якщо значення предикату NIL, то значення завдання стає рівним NIL і Лісп переходить до виконання наступного завдання. Якщо предикат повертає не NIL, відбувається виконання хвосту списку завдання, а інші завдання ігноруються. Якщо предикат повертає Т, а хвіст завдання порожній, то результатом всієї функції буде T.
Напишемо предикат, який розпізнає списки. Якщо аргументом є список, то предикат повертає істину, інакше - хибність. Функцію LISTP можна проінтерпретувати наступним чином: "Якщо obj є атомом, то повернути NIL, інакше повернути T".
$ (DEFUN LISTP (obj) $ (DEFUN LISTP (obj)
((ATOM obj) NIL) ((NULL obj))
T ) ((ATOM obj) NIL)
T )
В другій колонці написано предикат LISTP, який розпізнає додатково порожній список (повертає істину). Перше завдання є умовним, хвіст якого порожній. Його можна проінтерпретувати так: перевірити об'єкт obj на порожній список, і якщо він є таким, передати як результат функції істину. Немає потреби писати: ((NULL obj) T), оскільки це те ж саме, що і ((NULL obj)). Останнім завданням цих предикатів є атом Т. Це означає, що якщо жодне з умовних завдань не виконане (лише за цієї умови керування програмою дійде до останнього завдання), то як результат функції повернути Т. Для другого визначення функції LISTP маємо:
$ (LISTP 'tree) $ (LISTP '()) $ (LISTP '(q w e r t y))
NIL T T
Для кращого розуміння роботи тіла функції та простих і умовних завдань розглянемо функцію sm та результати, які вона буде генерувати при певних вхідних значеннях:
$ (DEFUN sm (lst) $ (sm '()) $ (sm '(q w e))
((NULL lst) 10 1) 1 12
(SETQ b 2)
((CDR lst) 12) $ (sm '(i)) $ (sm 'g)
(SETQ b 3) ) 3 3
Як бачимо, після виконання простого завдання керування завжди передається наступному завданню (якщо таке є). Якщо предикат умовного завдання істинний, то виконується його хвіст і повертається результат останнього виразу хвоста.
Вмонтована функція (LIST x1 ... xn) утворює та видає список, елементами якого є x1, ..., xn. Якщо аргументи не задані, результатом буде NIL.
$ (LIST 'a 'b 'c 'd) $ (LIST 'a '(b c) 'd) $ (LIST)
(a b c d) (a (b c) d) NIL
Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку. Інтуїтивно необхідно порівняти символ з першим елементом списку, потім з другим елементом і так далі. Проблема в такому розв'язку виникає в тому, що ми не знаємо наперед довжини списку. А якщо ми і знаємо цю довжину, і якщо вона велика, то тіло функції буде дуже великим. Така функція буде мати приблизно такий вигляд (перший стовпчик):
$ (DEFUN MEMBER (nam lst) $ (DEFUUN MEMBER (nam lst)
((EQL nam (FIRST lst))) ((NULL lst) NIL)
((EQL nam (SECOND lst))) ((EQL nam (CAR lst)) T)
((EQL nam (THIRD lst))) (MEMBER nam (CDR lst)) )
((EQL nam (THIRD (CAR lst))))
. . . . . . . . . . . . . . .
Змінимо наш підхід до побудови функції. В другому стовпчику побудовано функцію MEMBER, в основі якої лежить рекурсивний підхід, який базується на наступних фактах:
1. Якщо список порожній (не має елементів), то nam не належить списку.
2. Якщо nam дорівнює голові списку, то nam належить списку.
3. Якщо nam не дорівнює голові списку, то nam може належити списку тоді і тільки тоді коли nam належить хвосту списку.
Розглянемо дві рекурсивні функції: REMBER (REMove memBER), яка має два аргументи - атом obj та список lst і яка видаляє перше зустрічання атома obj в списку lst. REMBER-ALL яка видаляє всі атоми obj в списку lst.
$ (DEFUN REMBER (obj lst) (DEFUN REMBER-ALL (obj lst)
((NULL lst) NIL) ((NULL lst) NIL)
((EQL obj (CAR lst)) (CDR lst)) ((EQL obj (CAR lst))
(CONS (CAR lst) (REMBER-ALL obj (CDR lst))
(REMBER obj (CDR lst))) ) (CONS (CAR lst)
(REMBER-ALL obj (CDR lst))) )
Результат роботи цих функцій проілюструємо на прикладах:
$ (REMBER 'a '(q a w e r t a y)) $ (REMBER-ALL 'a '(q a w e r t a y))
(q w e r t a y) (q w e r t 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, якщо список не порожній і Т інакше.
Розглянемо задачу об'єднання списків. Роботу
Loading...

 
 

Цікаве