Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторна робота №2
Визначення функції та рекурсія
Цілі роботи:
Завдання:
Скласти рекурсивну функцію для обробки списку з будь-якої кількості атомів, які складені з будь-яких знаків. Якщо у результаті обробки з атому видалені всі знаки, замінити його на атом <ПУСТО>.
Таблиця 2.1 – Варіанти завдань
|
№ п.п. |
Спосіб обробки |
|
|
Упорядкувати цифри у кожному атомі списку (a53r2 a23r5) |
|
|
Розрахувати суму цифр у всьому списку (сума цифр списку ‘(a35f ab28 t1g) рівна 19) |
|
|
У кожному атомі списку латинські літери змінити на знак + (плюс), літери кирилиці – на знак – (мінус). |
|
|
Кожний атом списку будь-якої вкладеності замінити на кількість літер в атомі (a2е54 der5e) (2 4) |
|
|
У кожному атомі списку цифри розмістити у зворотному порядку |
|
|
Розрахувати добуток цифр у всьому списку |
|
|
Замінити кожну цифру у атомах списку на перші три літери їй назви. |
|
|
В кожному атомі списку замінити літери кирилиці замінити на знаки ~K~. |
|
|
У всіх атомах списку літери англійського алфавіту перетворити у прописні. |
|
|
У всіх атомах списку поміняти регістр літер англійського алфавіту на протилежний. |
|
|
У всіх атомів списку видалити знак із зазначеним номером. |
|
|
Кожний атом скласти з літер, знаку підкреслення та суми цифр |
|
|
Кожний атом списку скласти з упорядкованих цифр, знаку підкреслення та літер |
|
|
Кожний атом скласти з цифр, знаку підкреслення та літер англійського алфавіту. |
|
|
У кожному списку замінити літери англійського алфавіту на відповідний номер у алфавіті (aф6Гs4 1ф6Г194) |
|
|
Зі всіх атомів списку видалити зазначений знак |
|
|
Розрахувати суму цифр у атомах вкладених підсписків |
|
|
У всіх атомах списку видалити однакові знаки (знаки, що присутні в атомі більш одного разу). |
|
|
Кожний атом класти з суми цифр, знаку підкреслення та кодів літер. |
|
|
Кожний атом скласти з кількості цифр, знаку підкреслення, кількості літер, знаку підкреслення та кількості останніх знаків. (sa3+$4d4-r 3_3_3) |
|
|
Знаки кожного атома списку розташувати у вигляді послідовності цифр, а потім літер. Інші знаки видалити. (sa3+$4d4-r 344sad) |
|
|
Скласти список зі зазначеної кількості атомів, що складені зі зазначеної кількості знаків з використанням зазначеного знака. |
|
|
У кожному атомі видалити одиночні знаки |
|
|
У кожному атомі видалити цифри і літери, залишити тільки спеціальні знаки. |
Теоретичні відомості
Визначення функції
Визначення нової функції в мові Lisp виконується за допомогою функції DEFUN, яка має наступний формат:
(DEFUN <ім’я> <лямбда-список> <тіло функції>)
Як можна побачити, визначення функції подібне визначенням лямбда-виразу, за винятком того, що визначення функції передбачає обов’язкове завдання імені, яке використовується у подальшому для виклику функції.
Лямбда-вираз є контекстною функцією і знищується після виклику. У відмінність від цього функція DEFUN зв’язує символ (ім’я функції) з лямбда-виразом і зберігає цей зв'язок на весь сеанс роботи інтерпретатору. Для перевірки існування зв’язку символу з визначенням функції у мові Lisp служить предикатна функція FBOUNDP, а для отримання самого лямбда-виразу – функція SYMBOL-FUNCTION [7].
Наприклад, розглянемо визначення функції для розрахунку квадрату різниці двох величин:
(defun s2 (x y) (+ (- (* x x) (* 2 x y)) (* y y))),
де:
S2 – символ, що представляє ім’я функції, який функція DEFUN зв’язує з лямбда-виразом (+ (- (* x x) (* 2 x y)) (* y y));
(x y) – лямбда-список або список формальних параметрів функції.
Застосування функції:
(fboundp ‘s2)
повертає значення T (істина), а виклик функції:
(symbol-function ‘s2)
дозволяє отримати список:
(+ (- (* x x) (* 2 x y)) (* y y)).
Для розрахунку квадрату різниці чисел 2 і 3 слід записати виклик функції S2 у вигляді: (s2 2 3)
Функції – предикаты
Предикат – це функція, що визначає наявність деяких властивостей аргументу і повертає логічне значення NIL (хибне), або T (істина) [7].
У мові Lisp базовими предикатами є функції ATOM і EQ.
Функція ATOM перевіряє, якщо аргумент є атомом. В табл. 2.2 наведені низка прикладів застосування функції. Слід звернути увагу на те, що предикат ATOM сприймає пустий список як атом NIL.
Предикат EQ порівнює два символьних атома і повертає T, якщо вони ідентичні. Предикат можна використовувати тільки для символів та констант T и NIL. Функція не перевіряє логічну рівність аргументів, а тільки їх представлення у пам’яті, тому для чисел і списків можна отримати неадекватний результат. Для порівняння таких об’єктів використовуються інші функції.
|
Таблиця 2.2 – Приклади застосування базових предикатів ATOM и EQ |
||
|
Вираз |
Результат |
Пояснення |
|
(atom ‘abc) |
T |
ABC є символьним атомом |
|
(atom ‘(a b c)) |
NIL |
(A B C) є списком |
|
(atom nil) |
T |
NIL є атомом |
|
(atom ‘()) |
T |
Пустий список може бути представлений як атом NIL, тому функція повертає T |
|
(atom ‘(nil)) |
NIL |
Аргумент є список, що містить один елемент |
|
(eq ‘a ‘b) |
NIL |
Аргументи – різні символи |
|
(eq ‘a (car ‘(a b c)) |
T |
Другий аргумент – виклик функції CAR, яка повертає голову списку – атом A |
|
(eq nil (atom ‘(a b))) |
T |
Другий аргумент повертає значення NIL |
Крім функцій ATOM і EQ у мові Lisp передбачено ще ряд предикатів, що широко використовуються при композиції програм. Найбільш відомі функції-предикати представлені в табл. 2.3. Застосування предикатів сприяє розробці більш зрозумілих та читабельних програм і відповідає принципам функціонального програмування [7, 8].
|
Таблиця 2.3 - Функції – предикати у мові Lisp |
|
|
Найменування |
Призначення |
|
LISTP |
Перевіряє, чи є аргумент списком |
|
CONSP |
Перевірка структури списку (cons-осередку) |
|
NULL |
Перевірка пустого списку |
|
NUMBERP |
Перевіряє, чи є аргумент числовим атомом |
|
PLUSP |
Перевірка числового атома на додатне значення |
|
MINUSP |
Перевірка числового атома на від’ємне значення |
|
ZEROP |
Перевірка числового атома на нуль |
|
BOUNDP |
Перевіряє, чи існує зв'язок символу з деяким значенням |
|
FBOUNDP |
Перевірка зв’язку символу з лямбда-виразом |
Псевдофункції
У функціональному програмуванні функція повинна мати властивість математичної функціональності – виконання обчислень і повернення значення. Однак в програмуванні часто застосовуються функції, що виконують додаткові дії, крім обчислення виразу, тобто мають побічний ефект. Такі функції називаються псевдофункціями [7, 8].
У мові Lisp застосовується ряд псевдофункцій, що потрібні для написання практичних програм. Найбільш широко використовуються наступні функції:
Додаткові матеріали про ці функції можна знайти в [7].
Рекурсивні функції
Застосування рекурсивних функцій у повній мірі відповідає функціональному стилю програмування, а точніше, головному принципу – композиція програм з викликів функцій без накопичення у змінних проміжних результатів [6]. Основне призначення рекурсивних функцій – виконання циклічних операцій.
Функція є рекурсивною, якщо їй визначення містить виклик самої функції. Якщо деяка гілка програми містить один рекурсивний виклик, така рекурсія називається простою. При двох і більш рекурсивних викликах в одної гілці програми говорять про паралельну рекурсію. Якщо деяка функція F містить виклик другої функції G, а визначення функції G містить виклик функції F, то така організація функції називається взаємною рекурсією. Якщо рекурсивний виклик містить у якості фактичних параметрів рекурсивний виклик, то це – рекурсія більш високого порядку [7].
Будь-яка рекурсивна функція містить щонайменше дві гілки: рекурсивну і термінальну. Термінальна гілка повертає значення, що заздалегідь відоме при деяких умовах. Рекурсивна гілка містить рекурсивний виклик функцій з фактичними параметрами, значення яких приведе у подальшому до термінальної гілки. Це є обов’язковою умовою завершення рекурсивного процесу і, відповідно, рекурсивної функції.
У якості прикладу розглянемо функцію розрахунку довжини списку. На підставі того, що існує лише можливість отримання доступу до голови (першого елементу) і хвосту списку, кількість елементів можна полічити як суму:
L(s) = 1 + L(st), (2.1)
де:
S – список;
St – хвіст списку S
L(s) – довжина списку S
L(st) – довжина хвоста списку S, яка обчислюється по формулі 2.1
Для функції L(s) можна однозначно казати, що, якщо S – пустий список, то L(s) = 0.
Таким чином, попередні міркування можна записати на мові Lisp у наступному вигляді:
(defun LENLIST (x) ; визначення функції (x – список)
(if (NULL x) ; якщо список пустий
0 ; кількість елементів рівно(дорівнює) 0
; (це термінальна гілка функції)
; інакше здійснюється рекурсивний виклик функції
(+ 1 (LENLIST (cdr x)))
; LENLIST для хвоста списку, до результату
; якого додається 1
) ; заключна дужка функції IF
) ; заключна дужка визначення функції
Методичні вказівки
Загальні вказівки щодо виконання завдання
Для рішення завдання відповідно до варіанту необхідно розробити рекурсивні функції обробки списку. У якості фактичного параметру може бути використаний будь-який однорівневий список з довільної кількості атомів, кожний з яких може складатися з будь-яких припустимих знаків.
Виконання завдання варто почати з декомпозиції всієї задачі на більш дрібні підзадачі, які згодом будуть втілені в окремі прості функції. Обов'язково варто передбачити розробку функцій - предикатів, які можна використати при реалізації умов рекурсивного виклику в більш складних функціях.
Для роботи із символьними атомами їх варто перетворити в список знаків, а після відповідної обробки виконати зворотне перетворення в символ. Для цього можна застосувати функції, представлені нижче.
Розробка функцій повинна виконуватися в строгій відповідності із принципами функціонального програмування. Так, у розроблених функціях у даній лабораторній роботі повинні бути відсутні локальні та глобальні змінні, функції зв'язування, функції циклів. Визначення функцій повинні містити лише рекурсивні виклики, або виклики інших функцій.
Функції розгалужених операцій
Умовна пропозиція COND
Функція COND є основним засобом розгалуження обчислень у мові Lisp. Функція має наступний формат:
(COND (p1 a1) (p2 a2) … (pі aі) …(pn an) )
де: pi – будь-яка предикатна форма;
Ai – форма, яка обчислюється у разі, якщо предикат pi дорівнює T (істина) і повертається у якості результату функції COND.
Якщо предикат pi дорівнює NIL (хибне), відповідна форма ai не обчислюється і виконується перехід до наступного предикату. Якщо всі N предикатів хибні, функція COND повертає NIL.
Умовна пропозиція IF
Функція IF є спрощеною формою функції COND, й використовується у випадках коли існує лише одна альтернатива. Функція має наступний формат:
(IF p a1 a2)
де: p – предикатна форма;
a1 – форма, яка обчислюється у разі, якщо предикат p дорівнює T (істина) і повертається у якості результата функції IF;
a2 – форма, яка обчислюється у разі, якщо предикат p дорівнює NIL і повертається у якості результата функції IF
Функції для роботи з ім'ям символу
Для отримання доступу до кожного знаку символа атома використовуються наступні функції перетворювання (табл. 2.4):
|
Таблиця 2.4 – Функції перетворення даних |
||
|
Функція |
Призначення |
Пояснення |
|
(string <symbol>) |
перетворювання символа в рядок |
symbol – символьний атом |
|
(coerce <arg> <type>) |
универсальна функція перетворювання |
arg – об’єкт, що перетворюється type – тип, до якого здійснюється перетворення |
|
(intern <string>) |
створення символа з рядка |
string – рядок |
|
(char-code <mark> |
визначення ASCII-коду знака |
mark – знак |
|
(code-char <int>) |
визначення знака по ASCII-коду |
int – ціле число |
|
Таблиця 2.5 – Приклади застосування функцій перетворення даних |
|
|
Применение функции |
Результат |
|
(string ‘data43b) |
“DATA43B” |
|
(string ‘|daTA43b|) |
“daTA43b” |
|
(coerce “daTA43b” ‘list) |
(#\d #\a #\T #\A #\4 #\3 #\b) |
|
(coerce ‘(#\d #\a #\T #\A #\b) ‘string) |
“daTAb” |
|
(intern “daTAb”) |
|daTAb| |
|
(char-code #\3) |
51 |
|
(code-char 97) |
#\a |
Приклад виконання завдання
Завдання: У кожному атому списку залишити лише парні цифри. Якщо у атомі не залишаються знаки, тоді слід замінити словом ПУСТО
Рішення:
Розглянемо рішення задачі взагалі. Припустимо, що маємо функцію CONVERT, яка виконує перетворення атому відповідно до завдання. Тоді, для обробки всього списку X, запишемо рекурсивну функцію MAIN, яка перетворює голову списку, а потім створює новий список за допомогою конструктора CONS. У якості фактичних параметрів використаємо перетворену голову списку й рекурсивний виклик для перетворення хвоста:
(cons (convert (car X)) (main (cdr X))) (2.1)
Вираз (2.1) використаємо як рекурсивну гілку функції. Термінальну гілку створюємо з умов, що перетворення пустого списку є пустий список. Таким чином, функцію MAIN запишемо у вигляді:
(defun main (X)
(if ((null X) ; якщо список X пустий
nil ; функція повертає пустий список
(cons (convert (car X)) (main (cdr X)))
; інакше створюється новий список
)
)
Дія функції CONVERT представимо з наступних кроків:
Перший крок можна реалізувати на основі функцій перетворення (табл. 2.1). Відповідна функція AtomToList має наступний вигляд:
(defun AtomToList (X) (coerce (string X) ‘list))
Аналогічно реалізуємо третій крок, однак при цьому необхідно повертати атом ПУСТО у разі, якщо список знаків пустий. Напишемо функцію ListToAtom, яка здійснює ці дії :
(defun ListToAtom (X)
(if (null x) ‘ПУСТО
(intern (coerce X ‘string)))
Реалізація другого кроку більш складна. По-перше, необхідна предикатна функція для визначення знаку, що є парною цифрою. Очевидно, що парну цифру можна визначити через ASCII код знаку. Тоді відповідну функцію напишемо таким чином:
(defun IsEven (x)
(and
(< 47 (char-code x) 58) ; перевірка, чи є знак цифрою
(evenp (char-code x)) ; перевірка, чи є код парним числом
))
Далі розглянемо, яким чином можна перетворити список знаків, залишивши тільки парні цифри:
Напишемо функцію ConvertList, що перетворює список знаків відповідно вищевказаного:
(defun ConvertList (Lst)
(cond
; список пустий, функція повертає пустий
; список (термінальна гілка)
((null Lst) nil)
; якщо голова списку – парна цифра, створюємо
; новий список з голови списку та хвоста, який
; перетворюється за допомогою рекурсивного виклику
((IsEven (car Lst)) (cons (car Lst)
(ConvertList (cdr Lst))))
; якщо голова списку не парна цифра –
; функція повертає лише перетворений хвіст
(T (ConvertList (cdr Lst)))
))
Нарешті, запишемо функцію Convert, що складається з викликів вже розроблених функцій:
(defun Convert (X)
(ListToAtom (ConvertList (AtomToList X))))
Контрольні запитання
PAGE \* MERGEFORMAT 23