Реферат на тему:
Засоби та принципи програмування на Ліспі
1. Контрольні конструкції
MuLisp використовує неявну форму PROGN для обчислення форм, які складають тіло функції. Окрім того, інтерпретатор muLіsp розпізнає в тілі функції неявні COND конструкції. Неявні COND-и роблять визначення функцій читабельними, короткими та ефективними. Спеціальні форми забезпечують контроль за обчисленням форм в процесі виконання програм. Розглянемо деякі контрольні інструкції.
1. QUOTE <об’єкт> повертає об’єкт <obj> без його обчислення. QUOTE може використовуватися для запобігання обчислення значень констант, які передаються як аргумент функції, що обчислюється.
$ (SETQ a 125)
$ a $ (QUOTE a) $ (CAR (CONS 4 7)) $ (CAR ‘(CONS 4 7))
125 a 4 CONS
2. LOOP <форма1> <форма2> ... <формаN> Повторно обчислює форми у послідовному порядку доти, поки не зустрінеться неявний COND з предикатом, не рівним NIL. Розглянемо функцію LENGTH обчислення довжини списку. В першому стовпчику запропоновано рекурсивний, в лівому — нерекурсивний варіант програми.
(DEFUN LENGTHr (lst) (DEFUN LENGTH (lst)
((NULL lst) 0) (SETQ ct 0)
(+ 1 (LENGTHr (CDR lst))) ) (LOOP
((NULL lst) ct)
(SETQ lst (CDR lst) ct (+ 1 ct)) ) )
3. IF <предикат> [THEN] <форма1> [ELSE] <форма2> Якщо значення предиката не дорівнює NIL, то видається [THEN] форма, інакше видається [ELSE] форма.
$ (IF (EQL ‘r ‘r) (CAR ‘(q w e r t y)) (CDR ‘(q w e r t y))) — q
$ (IF (EQL ‘r ‘w) (CAR ‘(q w e r t y)) (CDR ‘(q w e r t y))) — (w e r t y)
4. IDENTITY <об’єкт> Повертає об’єкт без жодних змін. Ця функція застосовується для використання змінних як предикатів в умовних виразах.
5. PROGN <форма1> <форма2> ... <формаN> Послідовно обчислює форми та повертає результат обчислення формиN.
6. PROG1 <форма1> <форма2> ... <формаN> Послідовно обчислює форми та повертає результат обчислення форми1. Функцію використовують для того, щоб вводити допоміжні змінні для збереження результатів в процесі обчислення інших виразів.
$ (SETQ a ‘(q w e r t y))
$ (PROG1 (CAR a) (SETQ a (CDR a)))
q
$ a
(w e r t y)
7. COND <cond1> <cond2> ... <condN> Обчислює CAR кожної COND форми доти, доки не зустрінеться деяке значення, відмінне від NIL, або доки всі предикати не будуть обчислені. В першому випадку COND обчислює CDR елемент cons - форми з предикатом, який не дорівнює NIL, як тіло функції, використовуючи неявну функцію PROGN. Якщо CDR - елемент COND форми, яка не дорівнює NIL, є порожнім, то повертається значення предиката. Якщо обчислені всі предикати та всі вони повернули NIL, то COND повертає NIL.
8. COMMENT <коментар> Ігнорує свої аргументи та повертає NIL. Визначає засіб включення коментарів безпосередньо у визначені функції.
9. RETURN <об’єкт> Зупиняє виконання функції, яка містить RETURN, звільняє стек та повертає об’єкт в ролі свого значення.
10. RESTART Закриває всі відкриті файли, відмовляється від поточного середовища та ініціює нову систему muLisp. Всі зв’язки між змінними, функції користувача та значення властивостей поточного середовища знищуються.
11. SYSTEM Закриває всі відкриті файли, завершує виконання muLisp та повертає керування операційній системі.
12. EXECUTE <програма> <командний рядок> Зупиняється робота системи muLisp, передається керування програмі з командним рядком. EXECUTE повертає код виходу з програми або NIL, якщо <програма> не знайдена.
$ (EXECUTE “command.com” “/c dir c:”)
2. Обчислення рекурсивних функцій
1. Факторіалом числа n називається число (позначається n!), яке рекурсивно визначається наступним чином:
0! = 1
N! = N*(N-1)! якщо N>0.
$ (DEFUN FACTORIAL (n) $ (FACTORIAL 10)
((ZEROP n) 1) 3628800
(* n (FACTORIAL (- n 1))) )
Якщо в рекурсивній програмі аргументом буде велике число, то може виникнути переповнення стеку. Використовуючи команду циклу LOOP можна уникнути рекурсивного виклику. Наступна функція буде більш ефективною:
$ (DEFUN FACTORIAL1 (n rslt) $ (FACTORIAL1 10)
(SETQ rslt 1) 3628800
(LOOP
((ZEROP n) rslt ) $ (FACTORIAL 0 a)
(SETQ rslt (* n rslt)) 1
(SETQ n (- n 1)) ) )
2. Послідовність чисел, кожен елемент якої дорівнює сумі двох попередніх, а перші два елементи дорівнюють 1, називається послідовністю Фібоначчі. N-те число послідовності Фібоначчі F(N) може бути знайдене за рекурсивною формулою:
F(0)=1, F(1)=1, F(N) = F(N-1) + F(N-2).
$ (DEFUN FIBON (n) $ (FIBON 20)
((<= n 1) 1) 10946
(+ (FIBON (- n 1)) (FIBON (- n 2))) )
Визначена таким чином функція не є ефективною, оскільки для обчислення N-ого числа Фібоначчі необхідно обчислити (N-2) число Фібоначчі двічі, (N-3) — тричі і так далі. Визначимо функцію FIB з трьома аргументами, останні два з яких при виклику функції повинні дорівнювати відповідно F(0) та 0).
$ (DEFUN FIB (n f1 f2) $ (FIB 20 1 0)
((ZEROP n) f1) 10946
(FIB (- n 1) (+ f1 f2) f1) )
3. Обробка масивів
В Ліспі є поняття списку, але немає поняття масиву. Масиви можна емулювати за допомогою списків. Для цього необхідно написати функції конструювання масивів, доступу до елемента масива, та зміни значення елемента масива. Розглянемо цю техніку на прикладі.
Задача. В масивах a:array [0..k] of integer та b:array [0..l] of integer зберігаються коефіцієнти двох многочленів степеней k та l. Заповнити масив c:array[0..m] of integer коефіцієнтами їх добутку. Числа k,l,m — натуральні, m=k+l. Елемент масива з індексом i містить коефіцієнт при x в степені i.
Розв’язок. Розв’язок цієї задачі на Паскалі має наступний вигляд:
for i := 0 to m do c[i] := 0;
for i := 0 to k do
for j := 0 to l do
c[i+j] := c[i+j] + a[i] * b[j];
Масиви коефіцієнтів многочлена представлятимемо списком відповідної довжини. Нехай lst1 та lst2 — списки коефіцієнтів заданих в умові многочленів. Нехай функція (MULTPOL lst1 lst2) повертає список коефіцієнтів добутку вихідних многочленів. Наприклад, вихідні многочлени (x3+2x2+1) та (x2-4x-1) зададуться списками lst1 = (1 2 0 1), lst2 = (1 -4 -1). Результатом їх множення буде многочлен x5 - 2x4 - 9x3 - x2 - 4x -1, який представиться списком lst3 = (1 -2 -9 -1 -4 -1). Спочатку нам необхідно знайти значення k та l (якщо ми не передаємо їх як аргументи). Для цього необхідно просто знайти довжину списків lst1 та lst2. Це зробить функція (LENGTH lst):
(DEFUN LENGTH (lst) (DEFUN GEN0 (n)
((NULL lst) 0) ((ZEROP n) NIL)
(+ 1 (LENGTH (CDR lst))) ) (CONS 0 (GEN0 (- n 1))) )
Знаючи довжини списків lst1 та lst2 (k та l відповідно), ми знаємо довжину результуючого списку lst3 (m=k+l). Необхідно згенерувати список lst3, який складається з m елементів, кожний з яких дорівнює 0. Це зробить функція (GEN0 n).
Функція (mas lst n) повертає n-ий елемент списку lst. Функція (CHANGE lst n value) повертає список lst, в якому n-ий елемент набув значення value.
(DEFUN MAS (lst n)
((ZEROP n) (CAR lst))
(MAS (CDR lst) (- n 1)) )
(DEFUN CHANGE (lst n value)
((ZEROP n) (POP lst) (PUSH value lst))
(CONS (CAR lst) (CHANGE (CDR lst) (- n 1) value)) )
Тоді функція MULTPOL, яка написана на Паскалі, на Ліспі набуває наступного вигляду:
(DEFUN MULTPOL (lst1 lst2)
(SETQ k (LENGTH lst1) l (LENGTH lst2) lst3 (GEN0 (+ k l)))
(SETQ i 0)
(POP lst3)
(LOOP
((= i k) lst3)
(SETQ j 0)
(LOOP
((= j l))
(SETQ lst3 (CHANGE lst3 (+ i j) (+ (MAS lst3 (+ i j)) (* (MAS lst1 i) (MAS lst2 j)))) )
(INCQ j) )
(INCQ i) ) )
Середовище muLisp має також вмонтовану функцію MAKE-LIST, яку можна використовувати для створення списків заданого розміру. Функція (MAKE-LIST n об’єкт список) утворює список з n елементів, кожний з яких приймає значення об’єкту, приєднані до списку. Якщо не задано перший аргумент, то по замовченню n = 0. Якщо другий аргумент не задано, то вважається об’єкт = NIL.
$ (MAKE-LIST 3 ‘(q w)) $ (MAKE-LIST 4) $ (MAKE-LIST 3 5 ‘(2 3))
((q w)(q w)(q w)) (NIL NIL NIL NIL) (5 5 5 2 3)
Наведену функцію можна визначити наступним чином (ім’я змінено на MAKE-LST):
(DEFUN MAKE-LST (N OBJ LST)
((AND (INTEGERP N) (PLUSP N))
(CONS OBJ (MAKE-LIST (SUB1 N) OBJ LST)) )
LST )
Функця (OBLIST) що не має аргументів, утворює та повертає список активних на поточний момент символів у системі. Символи розташовані в тому порядку, в якому вони прочитані або згенеровані строковими функціями: нові символі розташовані зліва від старих.
4. Породження комбінаторних об’єктів.
Розглянемо задачі, в яких необхідно отримати всі елементи деякої множини.
1. Надрукувати всі послідовності довжини n з цифр 0,1. (P11 n).
Функція P11 викликається з одним аргументом n, аргумент lst – допоміжний.
(DEFUN p11 (n lst) (DEFUN p13 (n lst)
((ZEROP n) (PRIN1 lst) (TERPRI)) ((ZEROP n) (PRN13 lst) (TERPRI))
(P11 (- n 1) (CONS 0 lst)) (P13 (- n 1) (CONS 0 lst))
(P11 (- n 1) (CONS 1 lst)) ) (P13 (- n 1) (CONS 1 lst)) )
2. Надрукувати всі послідовності довжини k з чисел 1..n. (P12 k n).
Друкуватимемо послідовності у лексикографічному порядку. За допомогою функції (GEN1 n) згенеруємо список з n елементів, кожен з яких дорівнює 1. Список lst зберігатиме поточну перестановку. Функція (NEXT lst n) знаходить перестановку, яка буде наступною після lst. Функція P12BEST є найкращим рекурсивним розв’язком цієї задачі.
(DEFUN GEN1 n)
((ZEROP n) NIL)
(CONS 1 (GEN1 (- n 1))) )
(DEFUN NEXT (lst n)
((< (CAR lst) n) (CONS (+ (CAR lst) 1) (CDR lst)))
((NULL (CDR lst)) NIL)
(CONS 1 (NEXT (CDR lst) n))
Шукана функція має вигляд:
(DEFUN P12 k n)
(SETQ lst (GEN1 k))
(LOOP
((< (LENGTH lst) k))
(PRIN1 lst) (TERPRI)
(SETQ lst (NEXT lst n))
) )
(DEFUN P12BEST (n k lst c)
((ZEROP n) (PRIN1 lst) (TERPRI))
(PUSH 1 c)
(LOOP
((> (CAR c) k))
(P12BEST (- n 1) k (CONS (CAR c) lst) c)
(SETQ c (CONS (+ 1 (CAR c)) (CDR c)))
) (POP c) )
3. Надрукувати всі підмножини множини {1..n}. (P13 n).
Оскільки всі підмножини будь-якої множини {1..n} перебувають у взаємно однозначній відповідності зі всіма послідовностями з 0 та 1 довжини n, то ця задача зводиться до задачі 1.1. Функція (P13 n) наведена в 1.1. Тільки замість виведення списку з 0 та 1 необхідно виводити номери всіх елементів списку, які дорівнюють 1. Функція (PRN13 lst) виводить необхідні номери елементів.
(DEFUN PRN13 (lst)
(SETQ i 0)
(LOOP
((NULL lst))
(INCQ i)
(IF (= 1 (POP lst)) (PROGN (PRIN1 i) (SPACES 1)))
) )
4. З перестановки (1 2 3 ... n ) необхідно отримати перестановку (n ... 2 1) за найменшу кількість кроків. Кроком будемо називати обмін місцями довільних двох сусідніх чисел. Наприклад, з перестановки (1 3 4 2) можна отримати одну з наступних: (3 1 4 2), (1 4 3 2), (1 3 2 4).
Нехай lst – поточна перестановка. Опишемо алгоритм, за яким будемо знаходити наступну перестановку. Для цього, переглядаючи список lst зліва направо, знайдемо такі два числа що знаходяться поруч, де перше менше за друге. Поміняємо їх місцями та викличемо рекурсивно функцію move_per над отриманим списком.