.

Засоби та принципи програмування на Ліспі (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1488
Скачать документ

Реферат на тему:

Засоби та принципи програмування на Ліспі

1. Контрольні конструкції

MuLisp використовує неявну форму PROGN для обчислення форм, які
складають тіло функції. Окрім того, інтерпретатор muLіsp розпізнає в
тілі функції неявні COND конструкції. Неявні COND-и роблять визначення
функцій читабельними, короткими та ефективними. Спеціальні форми
забезпечують контроль за обчисленням форм в процесі виконання програм.
Розглянемо деякі контрольні інструкції.

1. QUOTE повертає об’єкт без його обчислення. QUOTE може
використовуватися для запобігання обчислення значень констант, які
передаються як аргумент функції, що обчислюється.

$ (SETQ a 125)

$ a $ (QUOTE a) $ (CAR (CONS 4 7)) $ (CAR ‘(CONS 4 7))

125 a 4 CONS

2. LOOP … Повторно обчислює форми у
послідовному порядку доти, поки не зустрінеться неявний 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] [ELSE] Якщо значення предиката
не дорівнює 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 … Послідовно обчислює форми та
повертає результат обчислення формиN.

6. PROG1 … Послідовно обчислює форми та
повертає результат обчислення форми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 Обчислює 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)

(( (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 над отриманим списком.

(DEFUN move_per (lst)

(PRIN1 lst) (TERPRI 1)

(SETQ cur NIL)

(LOOP

((ATOM (CDR lst)))

(( n (CAR tree)) (cons (car tree) (cons (cadr tree) (insel n (cddr
tree)))))

(cons (car tree) (cons (insel n (cadr tree)) (cddr tree))) )

(DEFUN INSL (lst tree)

((NULL lst) tree)

(SETQ tree (insel (car lst) tree))

(INSL (CDR lst) tree) )

Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) — обхід
згори вниз, PLR (Print Left-Right) — обхід зліва направо.

(DEFUN PUD (tree) (DEFUN PLR (tree)

((NULL tree)) ((NULL tree))

(PRIN1 (CAR tree)) (SPACES 3) (PLR (CADR tree))

(PUD (CADR tree)) (PRIN1 (CAR tree)) (SPACES 3)

(PUD (CDDR tree)) ) (PLR (CDDR tree)) )

Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає
лівим піддеревом і навпаки.

(DEFUN REVT (tree)

((NULL tree) NIL)

(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )

Розглянемо приклади:

$ (SETQ a (INSL ‘(5 1 7 3 9 2 4 8 10) NIL)) $ (SETQ b (REVT a))

$ (PLR a) $ (PLR b)

1 2 3 4 5 7 8 9 10 T 10 9 8 7 5 4 3 2 1

Функція HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього
дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між
висотами лівого та правого піддерев плюс одиниця. (HEIGHT a) = 4, де a
взято з попереднього прикладу.

(DEFUN HEIGHT (tree)

((NULL tree) 0)

(MAX (ADD1 (HEIGHT (CADR tree)))

(ADD1 (HEIGHT (CDDR tree)))) )

6. Робота з файлами

По замовченню за пристрій потокового вводу (CIS – Current Input Stream)
береться консоль.

Для читання даних з вхідного потоку використовують функцію READ. Після
виконання команди (SETQ a (READ)) ви повинні ввести з консолі вираз,
який буде прочитано та присвоєно змінній а. При цьому якщо буде введено
декілька об’єктів, то змінній а буде присвоєно перший об’єкт. Наприклад,
якщо ви введете: as bf gh, то змінна a прийме значення as. Якщо Ви
хочете ввести список (складний об’єкт), то його необхідно вводити в
круглих дужках: (as df gh).

Функція (CLEAR-INPUT) чистить буфер вводу. В будь-якому випадку
повертається NIL.

Функція (READ-LINE) читає елементи з CIS поки не буде прочитано символ
переходу на новий рядок (). Повертається символ, Р-ім’я якого
складається з усіх прочитаних символів як ті були розташовані у вхідному
рядку, окрім .

Функція (READ-CHAR) читає наступний елемент з CIS та повертає його.

Функція (UNREAD-CHAR) повертає в CIS останній прочитаний символ.

Функція (LISTEN) повертає T якщо CIS не порожній, та NIL якщо ми дійшли
до кінця файлу.

Функції (OPEN-INPUT-FILE “”) та (CLOSE-INPUT-FILE “”)
використовуються для відкриття та закриття файла для вводу.

Функції (OPEN-OUTPUT-FILE “”) та (CLOSE-OUTPUT-FILE “”)
відповідно відкривають та закривають файл для виводу інформації.

PAGE

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020