Лісп

Лабораторна робота № 1.

Тема: Ознайомча робота у середовищі MuLisp. Базові функції Лиспа. Символи, властивості символів. Средст-ва мови до роботи з числами.

Мета: Ознайомитися з середовищем MuLisp. Вивчити базові функції Лиспа, символи й їх властивості, і навіть кошти на роботи з числами.

Основные становища програмування на Лиспе. Завантаження системи, системний редактор. Базові функції мови. Символи, властивості символів. Кошти мови до роботи з числами. Завдання до лабораторної роботі. Вопросы.

1. Основні становища програмування на Лиспе. Лисп орієнтовано обробку нечисловых завдань. Він грунтується на алгебрі спискових структур, лямбда-исчислении і теорії рекурсий. Мова має функціональну спрямованість, т. е. на будь-яку пропозицію укладене дужки, запроваджене поза редактора вважається функцією і виконується відразу після натискання «ENTER». Щоб запобігти обчислення значення висловлювання, потрібно які були вираженням поставити апостроф «'». Апостроф перед вираженням — це самому справі скорочення лисповской функції QUOTE. У Лиспе форми уявлення програми розвитку й оброблюваних нею даних однакові. І те й інше представляється списковою структурою має однакову форму. Типи даних пов’язані із конкретними іменами об'єктів даних, а супроводжують самі об'єкти. Змінні можуть у різні моменти часу представляти різні об'єкти. Основні типи даних мови — атоми і списки.

Атоми — це символи й числа.

Список — упорядкована послідовність, елементами якої є атоми або списки. Списки полягають у круглі дужки, елементи списку поділяються прогалинами. Кілька прогалин між символами еквівалентні одному пробілу. Перший елемент списку називається «головою», а залишок, т. е. список без першого елемента, називається «хвостом. Список в якому немає жодної елемента, називається пустим і позначається «()» або NIL. Символ — це, що складається з літер, цифр і спеціальних знаків, яке позначає який-небудь предмет, об'єкт, дію. У Лиспе символи позначають числа, інші символи чи більше складні структури, програми (функції) та інші лисповские об'єкти. Символи можуть бути що з прописних, що з малих літер літер, хоча у більшості Лисп-систем, як й у описуваної тут версії MuLisp, великі та рядкові літери ототожнюються і видаються прописними літерами. Символи T і NIL мають у своєму Лиспе спеціальне призначення: T — позначає логічне значення істина, а NIL — логічне значення брехня. При генерації чи зчитуванні MuLispом нового символу, над його величину приймається вона сама. Така посилання символу він називається автоссылкой. Створення програми на Лиспе — написання деякою функції, можливо складної, при обчисленні використовує інші функції або рекурсивно саму себе. Насправді, написання програм здійснюється записом в файл визначень функцій, даних, і інших об'єктів із допомогою наявного в програмному оточенні редактора. Файлу присвоюється розширення LSP. Необов’язково робити відступи в рядках висловів, які входять у ваші функції. Насправді, за бажання, ви можете написати всю програму одну рядок. Проте відступи в рядках і порожні рядки роблять структуру програми зрозуміліше і більше читабельней. Також вирівнювання початкових і кінцевих скобок основних висловів допомагають переконатися у балансі ваших скобок. Визначення функцій можуть зберігатися в файлах і завантажуватися використовуючи функцію LOAD:

(load).

Ця функція завантажує файл висловів і виконує ці висловлювання. — це строковая константа, що дає ім'я файла без розширення (мається на увазі розширення " .lsp "). Якщо операція успішно завершено, LOAD повертає ім'я останньої функції, певної в файлі. Якщо операція не виконано, LOAD повертає ім'я файла як строкового выражения.

Функція LOAD неспроможна викликатися з іншої функції LISP. Вона повинна викликатися безпосередньо з клавіатури, тоді як ніяка інша функція LISP не в процесі виконання. Інтерпретатор вважає файлами, що містять вихідні тексти програм на Лиспе, все файли, мають розширення LSP. У зв’язку з тим, що діалект MuLisp включає у собі порівняно невеличкий набір базових функцій, зазначена Лисп-система забезпечується бібліотеками Лисп-функций, дополняющими базовий набір функціями, наявними в Common Lisp-е та інших диалектах (Common.lsp, Array. lsp тощо. буд. …).

2. Завантаження системи. Системний редактор.

Запуск системи MuLisp з розширенням Common. lsp здійснюється командой:

MuLisp87.com Common.lsp.

Після кількох секунд завантаження на екрані дисплея з’явиться сообщение:

MuLisp-87 IBM PC MS-DOS Version 6.01 (11/05/87).

(З) Copyright SoftWarehouse, Inc., 1983, 1985, 1986, 1987.

All rights Reserved Worldwide.

; Loading C: Common.lsp.

Після цього з’явиться знак $, що означає запрошення системи на роботу. Для завантаження системного редактора необхідно набрати таку команду:

(LOAD edit. lsp).

Системний редактор починає працювати. Він чистить екран малює рамку і видає на екран своє меню:

Alpha, Block, Delete, Jump, List, Options, Print, Quit, Replace, Search, Transfer, Undelete і Window.

Потім система чекає, поки користувач не вибере жодну з опцій. Для цього потрібні встановити курсор на обраної опції й тицьнути на клавішу «Enter». Перехід від однієї опції в іншу проводиться за допомогою клавіші «Tab». Alpha: включення режиму редагування. Block: роботу з блоком. Виділення, копіювання, видалення, перенесення та інших. Delete: видалення блоку, символу, слова, рядки. Jump: перехід у початок чи кінець тексту програми, вгору-вниз сторінки. List: робота з списком. Видалення, перехід до попередньому, наступному. Options: роботу з квітами, монітором, звуком. Print: печатку тексту програми. Quit: вихід із системи. Replace: зміна рядки. Search: пошук рядки. Причому рядкові і великі літери різняться. Transfer: роботу з файлами. Запис, перебування, об'єднання, видалення. Undelete: відновлення. Window: роботу з вікнами. Відкрити, закрити, можливість перейти до іншому та т. д.

3. Базові функції языка.

Функції разбора.

Функція CAR повертає у ролі значення перший елемент списка.

(CAR список) (P.S — вираз (атом або список).

_(CAR ‘(a b з d)) (a.

_(CAR ‘((a b) з d)) ((a b).

_(CAR ‘(a)) (a.

_(CAR NIL) (NIL «Голова порожнього списку — порожній список.».

Виклик функції CAR з аргументом (a b з d) без апострофа було б проінтерпретований як виклик функції «a» з аргументом «b з d», і було б отримано повідомлення про ошибке.

Функція CAR має сенс тільки для аргументів, є списками.

(CAR ‘a) (Error.

Функція CDR — повертає у ролі значення хвостову частина списку, т. е. список, отримуваний з вихідного списку після видалення потім із нього головного элемента:

(CDR список) (список.

Функція CDR визначено лише списков.

_(CDR ‘(a b з d)) ((b з d).

_(CDR ‘((a b) з d)) ((з d).

_(CDR ‘(a (b з d))) (((b з d)).

_(CDR ‘(a)) (NIL.

_(CDR NIL) (NIL.

_(CDR ‘a) (Error.

Функція створення CONS.

Функція CONS будує новий список з переданих їй у ролі аргументів голови і хвоста.

(CONS голова хвост).

Щоб можна було включити перший елемент функції CONS в ролі першого елемента значення другого аргументу цієї функції, другий аргумент може бути списком. Значенням функції CONS завжди буде список:

(CONS s-выражение список) (список.

_(CONS ‘a ‘(b з)) ((a b c).

_(CONS ‘(a b) ‘(з d)) (((a b) з d).

_(CONS (+ 1 2) ‘(+ 3)) ((3 + 3).

_(CONS ‘(a b з) NIL) (((a b c)).

_(CONS NIL ‘(a b з)) ((NIL a b c).

Предикати ATOM, EQ, EQL, EQUAL.

Предикат — функція, що визначає, чи має аргумент певним властивістю, і повертає у ролі значення NIL чи T.

Предикат ATOM — перевіряє, чи є аргумент атомом:

(ATOM p. s — выражение).

Значенням виклику ATOM буде T, якщо аргументом є атом, і NIL — у протилежному случае.

_(ATOM ‘a) (T.

_(ATOM ‘(a b з)) (NIL.

_(ATOM NIL) (T.

_(ATOM ‘(NIL)) (NIL.

Предикат EQ порівнює два символу і повертає значення T, якщо вони ідентичні, інакше — NIL. З допомогою EQ порівнюють лише символи чи константи T і NIL.

_(EQ ‘a ‘b) (NIL.

_(EQ ‘a (CAR ‘(a b з))) (T.

_(EQ NIL ()) (T.

Предикат EQL працює як і і EQ, але додатково дозволяє порівнювати однотипні числа.

_(EQL 2 2) (T.

_(EQL 2.0 2.0) (T.

_(EQL 2 2.0) (NIL.

Порівняйте чисел різних типів використовують предикат «=». Значенням предиката «=» є T у разі рівності чисел незалежно від їх типів та зовнішності записи.

(= 2 2.0) (T.

Предикат EQUAL перевіряє ідентичність записів. Він працює як EQL, але додатково перевіряє однаковість двох списків. Якщо зовнішня структура двох лисповских об'єктів однакова, то результатом EQUAL буде T.

_(EQUAL ‘a ‘a) (T.

_(EQUAL ‘(a b з) ‘(a b з)) (T.

_(EQUAL ‘(a b з) ‘(CONS ‘a ‘(b з))) (T.

_(EQUAL 1.0 1) (NIL.

Функція NULL перевіряє на порожній список.

_(NULL ‘()) (T.

Вкладені виклики CAR і CDR.

Комбінації викликів CAR і CDR утворюють які у глибину списку звернення, в Лиспе при цьому використовується понад коротка запис. Бажану комбінацію викликів CAR і CDR можна записати як одного виклику функции:

(C…R список).

Замість крапки записується потрібна комбінація з літер A і D (для CAR і CDR відповідно). Одного виклик можна об'єднувати трохи більше чотирьох функцій CAR і CDR.

(CADAR x) ((CAR (CDR (CAR x))).

_(CDDAR ‘((a b з d) e)) ((з d).

_(CDDR ‘(k l m)) ((M).

Функція LIST — створює список з елементів. Вона повертає у ролі значення список з значень аргументів. Кількість аргументів произвольно.

_(LIST ‘a ‘b ‘з) ((a b c).

_(LIST ‘a ‘b (+ 1 2)) ((a b 3).

4. Символи, властивості символов.

Функції присвоювання: SET, SETQ, SETF.

Функція SET — привласнює символу чи пов’язує із нею якийсь значення. Причому вона обчислює обидва своїх аргументу. Встановлена зв’язок діє остаточно роботи, якщо цьому імені нічого очікувати присвоєно нове значення функцією SET.

_(SET ‘a ‘(b з d)) ((b з d).

_a ((b з d).

_(SET (CAR a) (CDR (o f g)) ((f g).

_a ((b з d).

_(CAR a) (b.

_b ((f g).

Значення символу обчислюється з допомогою спеціальної функції Symbolvalue, яка повертає у ролі значення значення свого аргумента.

_(Symbol-value (CAR a)) ((f g).

Функція SETQ — пов’язує ім'я, не вираховуючи його. Ця функція відрізняється від SET тим, що обчислює лише другою аргумент.

_(SETQ d ‘(l m n)) ((l m n).

Функція SETF — узагальнена функція присвоювання. SETF використовується для занесення значення осередок памяти.

(SETF ячейка-памяти значение).

_(SETF осередок ‘(a b з)) ((a b c).

_ осередок ((a b c).

Змінна «осередок» без апострофа свідчить про осередок пам’яті, куди міститься у ролі значення список (a b c).

Властивості символа.

У Лиспе з символом можна зв’язати іменовані властивості. Властивості символу записуються в бережене разом із символом список властивостей. Властивість має ім'я і значення. Список властивостей то, можливо порожній. Його можна змінювати чи видаляти без ограничений.

(имя1 знач1 имя2 знач2 … имяN значN).

Нехай ім'я студент має наступний список свойств:

(ім'я Іван по батькові Іванович прізвище Иванов).

Функція GET — повертає значення властивості, що з символом.

(GET символ властивість).

За відсутності властивості функція GET повертає NIL як ответа.

_(GET ‘студент ‘ім'я) (Иван.

_(GET ‘студент ‘група) (NIL.

Присвоювання і видалення свойств.

Для присвоювання символу властивостей в MuLisp (як й у Common Lisp) окремої функції немає. І тому використовуються вже знані нами функции:

(SETF (GET символ властивість) значение).

_(SETF (GET ‘студент 'група) 'РВ-90−1) (РВ-90−1.

_(GET ‘студент 'група) (РВ-90−1.

Видалення властивості та її значення здійснюється псевдофункцией REMPROP:

Ця функція повертає у ролі значення ім'я удаляемого властивості. Якщо удаляемого властивості немає, то повертається NIL.

(REMPROP символ свойство).

_(REMPROP ‘студент 'група) (группа.

_(GET ‘студент 'група) (NIL.

_(REMPROP ‘студент 'ср_бал) (NIL.

Для перегляду всього списку властивостей використовують функцію SYMBOL-PLIST. Значенням функції є весь список свойств.

(SYMBOL-PLIST ‘СИМВОЛ).

(SYMBOL-PLIST ‘студент) ((ім'я Іван по батькові Іванович прізвище Иванов).

Властивості символів незалежно від своїх значень доступні із усіх контекстів коли будуть явно змінені чи віддалені. Зміна значення символу впливає інші властивості. Властивості символу передаються іншому символу з допомогою функції SETQ.

5. Кошти мови до роботи з числами. (Математичні і логічні функции).

У мові Лисп як виклику функцій, так записи висловлювання прийнята единообразная префиксная форма записи, коли він як ім'я функції чи дії, і самі аргументи записуються всередині скобок:

(f x), (g x y), (h x (g y z)) тощо. д.

Арифметичні действия:

(+ числа) — складання чисел.

(- число числа) — віднімання чисел з числа.

(* числа) — множення чисел тощо. д.

_(+ 5 7 4) (16.

_(- 10 3 4 1) (2.

_(/ 15 3) (5.

Порівняння чисел:

(= число числа) (рівні (все).

(< число числа) (менше (для всех).

(> число числа) (більше (всім) тощо. д.

Числові предикаты:

(ZEROP число) (перевірка на ноль.

(MINUSP число) (перевірка на заперечність тощо. д.

Логічні действия:

(NOT об'єкт) (логічне отрицание.

(AND (форми)) (логічне И.

(OR (форми)) (логічне ИЛИ.

_(AND (ATOM NIL) (NULL NIL) (EQ NIL NIL)) (T.

_(NOT (NULL NIL)) (NIL.

Крім наведених, існує інших, але з менш корисні функций.

6. Завдання до лабораторної работе.

1. Запишіть послідовності викликів CAR і CDR, які виділяють з наведених нижче списків символ «а». Спростите виклики з допомогою функцій C… R. а) (1 2 3 а 4) б) (1 2 3 4 а) ((1) (2 3) (а 4)) р) ((1) ((2 3 а) (4))) буд) ((1) ((2 3 а 4))) е) (1 (2 ((3 4 (5 (6 а)))))).

2. Яке значення кожного з таких висловів: (ATOM (CAR (QUOTE ((1 2) 3 4)))); (NULL (CDDR (QUOTE ((5 6) (7 8))))); (EQUAL (CAR (QUOTE ((7)))) (CDR (QUOTE (5 7)))); (ZEROP (CADDDR (QUOTE (3 2 1 0))));

3. Проробіть такі обчислення з допомогою інтерпретатора Лиспа: а) 3.234*(45.6+2.43) б) 55+21.3+1.54*2.5432−32 в) (34−21.5676−43)/(342+32*4.1).

4. Визначте значення наступних висловів: а) ‘(+ 2 (* 3 5)) б) (+ 2 ‘(* 3 5)) в) (+ 2 (' * 3 5)) р) (+ 2 (* 3 '5)) буд) (quote ‘quote) е) (quote 6).

5.1 Складіть список студентів своєї группы.

(ФИО ФИО … ФИО).

5.2 До кожного студента і з допомогою функції LIST складіть такі списки:

Для самого студента — (дата народження), (адресу), (середній бал по лекційним занять), (середній бал по практичним занять), (середній бал по лабораторним роботам). Для батька і материна родини — (ФИО), (дата народження), (адресу), (місце роботи). з допомогою функцій CONS і SETQ об'єднаєте отримані списки і привласніть у вигляді значень символів, що означає ФИО кожного студента:

ФИО ст. — (((дата народження ст.) (адресу ст.)((ср. бал (до десятих) по лекційним занять) (порівн. бал по практичним занять) (порівн. бал по лабораторним роботам))) (((ФИО батька) (дата народження батька) (адресу) (місце роботи батька)) ((ФИО матері) (дата народження матері) (адресу) (місце роботи матери)))).

5.3 Для довільно вибраних студентів із допомогою базових функцій порівняйте: а) рік народження; б) успішність (з огляду на те, що кількість, характеризує середній бал, може бути як цілим, і дробовим); в) з’ясуйте, чи є вони родичами; р) з’ясуйте, живуть вони з родителями.

6.1 До кожного студента складіть списки властивостей а) оцінки за лекцій; б) оцінки за практикам; в) оцінки за лабораторним работам.

6.2 Для довільно вибраних студентів порівняти свойства.

7. Вопросы.

1 Перелічіть базові функции.

2 Які типи аргументів базових функций?

3 Які значення вони возвращают?

4 Що таке предикат?

5 Назвіть основні відмінності предикатів EQ, EQL, EQUAL і =.

6 Назвіть відмінності функцій CONS і LIST.

7 Що таке символ?

8 Відмінності функцій SET, SETQ, SETF?

9 Особливості властивостей символов?

Лабораторна робота № 2.

Тема: Визначення функцій. Функції вводу-виводу. Обчислення, які змінюють структуру.

Мета: Одержати навички в написанні функцій. Вивчити функції введеннявывода.

Функции, зумовлені користувачем. Функція введення. Функції виведення. Обчислення, які змінюють структуру. Завдання до лабораторної роботі. Вопросы.

1. Функції, зумовлені пользователем.

Визначення функцій та його обчислення в Лиспе грунтується на лямбдаобчисленні Черча.

У Лиспе лямбда-выражение має вид.

(LAMBDA (x1 x2 … xn) fn).

Символ LAMBDA означає, що ми маємо справу з визначенням функції. Символи xi є формальними параметрами визначення, які мають аргументи на описывающем обчислення тілі функції fn. Вхідний у складі форми список, освічений з параметрів, називають лямбда-списком.

Тілом функції є довільна форма, значення може обчислити інтерпретатор Лиспа.

_(lambda (x y) (+ x y)).

Формальність параметрів означає, що можна замінити на будь-які інші символи, і це позначиться на обчисленнях, визначених функцией.

Лямбда-выражение — визначення обчислень і параметрів функції в чистому вигляді без фактичних параметрів, чи аргументів. А, щоб застосувати таку функцію до деяких аргументів, у виклик функції поставити лямбда-определение цього разу місце імені функции:

(лямбда-выражение а1 А2 … аn).

Тут ai — форми, що задають фактичні параметри, які обчислюються як обычно.

_((lambda (x y) (+ x y)) 1 2) (3.

Лямбда-вызовы можна вільно об'єднувати між собою й іншими формами. Вкладені лямбда-вызовы можна порушувати як у місце тіла лямбдависловлювання, і цього разу місце фактичних параметров.

_((lambda (x) ;Тіло лямбда-вызова ;

((lambda (y) (list x y)) ‘b)) ‘a) ((a b) лямбда-вызов.

Записувати виклики функцій цілком згодна з допомогою лямбда-вызовов не розумно, бо дуже скоро висловлювання на виклик довелося б повторювати, хоча різні виклики однієї функції відрізняються лише частини фактичних параметрів. Проблема можна шляхом іменування лямбда-выражений і використання їх у виклик лише имени.

Дати ім'я і побачити нову функцію можна з допомогою функції DEFUN:

(DEFUN ім'я лямбда-список тело).

DEFUN з'єднує символ з лямбда-выражением, і символ починає представляти певні цим лямбда-выражением обчислення. Значенням цієї форми є ім'я нової функции.

Після іменування функції її виклик здійснюється за імені Ілліча та параметрам.

_(defun list1 (x y).

(cons x (cons y nil))) (list1.

_(list1 ‘з ‘n) ((з n).

(eval).

Функція повертає результат висловлювання, де — будь-яке вираз мови LISP. Наприклад, дано:

(setq a 123).

(setq b «a).

(eval 4.0) (4.0.

(eval (abs -10)) (10.

(eval a) (123.

(eval b) (123.

2. Функція ввода.

Лисповская функція читання READ обробляє вираз повністю. Виклик функції ввозяться виде.

_(READ).

(Введені вираз) (;вираз пользователя.

((ВВЕДЕНІ ВИРАЗ) ;значення функції READ.

…

Функція не показує, що вона чекає введення висловлювання. Вона лише читає вираз і повертає у ролі значення саме ця вираз, після чого обчислення продолжаются.

Якщо прочитане вираз необхідно зберегти задля її подальшого використання, то виклик READ може бути аргументом який-небудь форми, наприклад присвоювання (SETQ), яка зв’яже отримане выражение:

_(SETQ input (READ)).

(+ 1 2) ;запроваджене выражение.

(+ 1 2) ;значение.

_input ((+1 2).

3. Функції вывода.

Для виведення висловів використовують кілька функцій: PRINT, PRIN1, PRINC.

Функція PRINT.

Це функція з однією аргументом, що спочатку обчислює значення аргументу, та був виводить це значення. Функція PRINT перед висновком аргументу переходить нові рядок, а після нього виводить прогалину. Таким чином, значення виводиться завжди нові строку.

_(PRINT (+ 1 2)).

3 ;вывод.

3 ;значение.

PRINT є псевдофункцией, що має як побічний ефект, і значення. Значенням функції є значення її аргументу, а побічним ефектом — печатку цього значения.

Функції PRIN1 і PRINC.

Ці функції працюють як і, як PRINT, але з переходять нові рядок і виводять пробел:

(PRIN1 5) (55.

(PRINC 4) (44.

Обома функціями можна виводити крім атомів і списків та інші типи даних які ми розглянемо позже:

_(PRIN1 «CHG») («CHG""CHG».

_(PRINC «tfd») (tfd"tfd" ;висновок без кавычек,.

;результат — значення аргумента.

З допомогою функція PRINC можна отримати роботу приємніший вид. Вона виводить лисповские об'єкти у тому самому вигляді, як і PRIN1, але перетворює деякі типи даних у простішу форму.

Функція TERPRI.

Ця функція переводить рядок. У функції TERPRI немає і в ролі значення вона повертає NIL:

_(DEFUN out (x y).

(PRIN1 x) (PRINC y).

(TERPRI) (PRINC (LIST ‘x ‘y)) (out.

_(out 1 2) (12.

(1 2).

4. Обчислення, які змінюють структуру.

Основними функціями, змінюють фізичну структуру списків, є RPLACA і RPLACD, які знищують колишні і записують нові значення поля CAR і CDR списковій ячейки:

(RPLACA осередок значение-поля) ;полі CAR.

(RPLACD осередок значение-поля) ;полі CDR.

Першим аргументом є покажчик на списочную осередок, другим — записываемое у ній нового значення поля CAR чи CDR. Обидві функції повертають як результату покажчик на змінену списочную ячейку:

_(SETQ a ‘(b з d)) ((b з d).

_(RPLACA a ‘d) ((d з d).

_(RPLACD a ‘(o n m)) ((d o n m).

_a ((d o n m).

5. Завдання до лабораторної работе.

1. Визначте з допомогою лямбда-выражения функцію, вычисляющую: +y-x*y; x*x+y*y; x*y/(x+y)-5*y;

2. Визначте функції (NULL x), (CADDR x) і (LIST x1 x2 x3) з допомогою базових функцій. (Використовуйте імена NULL1, CADDR1 і LIST1, ніж перевизначати однойменні вбудовані функції системы.

3. Використовуючи композицію, напишіть функції, які проводять звернення списку з 2, 3, …, n элементов.

4. Використовуючи композицію описаних вище предикатів і логічних зв’язок, побудуйте функцію, що перевіряє, чи є її аргумент: a) списком з 2, 3, … елементів; b) списком з 2, 3, … атомов;

5. Напишіть функцію: таку, що P (n) для довільного цілого n є список із трьох елементів, а саме: квадрата, куба й четвертою ступеня числа n; обох аргументів значенням якої є список з цих двох елементів (різниці і залишку від розподілу); таку, що A (n) є список (The answer is n). Так, значенням (A 12) буде (The answer is 12); семи аргументів, значенням якій служить сума всіх семи аргументов.

6. До кожного з таких умов визначити функцію одного аргументу L, має значення T, якщо умова задовольняється, і NIL інакше: n-ий елемент L є 12; n-ий елемент L є атом; L має більш n елементів (атомів чи подсписков).

7. Напишіть функцію, яка фразу природному мовою й перетворює їх у список.

8. Напишіть функцію, яка запитує у свого користувача ФИО студента із групи (список групи складено раніше) видає такі даних про ньому: рік народження; середній бал; батьків; списки властивостей, присвоєні йому раньше.

9. Напишіть функцію: від однієї аргументу (ФИО будь-якого студента), замещающую у списку з цими про ньому (написаному раніше) подсписки зі середніми балами на списки властивостей; вычисляющую середні бали, беручи дані з списків свойств.

10. Якими будуть значення висловів (RPLACA x x) і (RPLACD x x), якщо: x = '(a b); x = '(a);

11. Обчислите значення таких висловів: (RPLACD ‘(a) ‘b); (RPLACA ‘(a) ‘b); (RPLACD (CDDR ‘(a b x)) ‘з); (RPLACD ‘(nil) nil).

6. Вопросы.

1. Що таке лямбда-выражение?

2. Навіщо використовується функція DEFUN?

3. Чим різняться основні функції вывода?

4. Що повертає у ролі значення функція READ?

5. Особливості функцій, змінюють структуру?

Лабораторна робота № 3.

Тема: Організація обчислень в Лиспе.

Мета: Вивчити основні функції та його особливості в організацію обчислень в Лиспе.

1. Пропозиції LET і LET*.

2. Послідовні вычисления.

3. Розгалуження вычислений.

4. Циклічні вычисления.

5. Передача управления.

6. Завдання до лабораторної работе.

7. Вопросы.

1. Пропозиції LET і LET*.

Пропозиція LET створює локальну зв’язок всередині формы:

(LET ((m1 знач1) (m2 знач2)…) форма1 форма2 …).

Спочатку статичні перемінні m1, m2, … зв’язуються (одночасно) з відповідними значеннями знач1, знач2, …. Потім зліва на право обчислюються значення формы1, формы2, …. Значення останньої форми повертається у ролі значення всієї форми. Після обчислення зв’язку статичних змінних ликвидируются.

Пропозиції LET можна зробити вкладеними одне в другое.

_(LET ((x ‘a) (y ‘b)).

(LET ((z ‘з)) (LIST x y z))) ((a b c).

_(LET ((x (LET ((z ‘a)) z)) (y ‘b)).

(LIST x y)) ((a b).

_(LET ((x 1) (y (+ x 1))).

(LIST x y)) (ERROR.

При обчисленні у У і Х ще зв’язку. Значення змінним присвоюються одночасно. Це означає, що значення всіх змінних mi обчислюються доти, як здійснюється зв’язування з формальними параметрами.

Такої помилки можна запобігти з допомогою форми LET*:

_(LET* ((x 1) (y (+ x 1))).

(LIST x y)) ((1 2).

2. Послідовні вычисления.

Пропозиції PROG1 і PROGN дозволяють працювати з кількома вычисляемыми формами:

(PROG1 форма1 … формаN).

(PROGN форма1 … формаN).

Ці спеціальні форми послідовно обчислюють свої аргументи й у ролі значення повертають значення першого (PROG1) чи останнього (PROGN) аргумента.

_(PROG1 (SETQ x 1) (SETQ y 5)) (1.

_(PROGN (SETQ j 8) (SETQ z (+x j))) (9.

3. Розгалуження вычислений.

Умовне пропозицію COND:

(COND (p1 a1).

…

(pn an)).

Предикатами pi і результирующими висловлюваннями ai може бути довільні форми. Висловлювання pi обчислюються послідовно до того часу, доки зустрінеться вираз, значенням якого є T. Обчислюється результуюче вираз, відповідне цьому предикату, й отримане значення повертається у ролі значення всього пропозиції COND. Якщо істинного предиката немає то значенням COND буде NIL.

Рекомендується як останнього предиката використовувати символ T. Тоді відповідне йому an буде обчислюватись у разі, якщо інші умови не выполняются.

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

Пропозиції COND можна комбинировать.

(COND ((> x 0) (SETQ рез x)).

((< x 0) (SETQ xx) (SETQ рез х)).

((= x 0)).

(Т ‘ошибка)).

Пропозиція IF.

(IF умова то-форма иначе-форма).

(IF (> x 0) (SETQ y (+ y x)) (SETQ y (- y x))).

Якщо виконується умова (т. е. х>0), чи до значенням y додається значення x, інакше (x x y) (IF (< x z) (PROGN (PRINT x).

(PRINT «середнє (1)»)).

(IF (> y z) (PROGN (PRINT y).

(TERPRI).

(PRINT «середнє (2)»)).

(PROGN (PRIN1 z).

(PRIN1"среднее (3)"))))).

((< x y) (IF (< y z) (PROGN (PRIN1 y).

(TERPRI).

(PRIN1 «середнє (4)»)).

(IF (> x z) (PROGN (PRINC x).

(PRINC «середнє (5)»)).

(PROGN (PRINC z).

(TERPRI).

(PRINC «середнє (6)»))))).

(T (PRINC «помилка ввода»)))).

7. Вопросы.

1. Навіщо використовується пропозицію LET?

2. У чому його на відміну від пропозиції LET*?

3. Чим різняться функції COND і IF?

4. Які які повертаються ними значения?

5. Чим різняться функції PROG1 і PROGN?

6. Чому бажано використовувати оператори передачі управління? Чим їх можна заменить?

Лабораторна робота № 4.

Тема: Рекурсія в Лиспе. Функционалы і макросы.

Мета: Вивчити основи програмування із застосуванням рекурсії. Навчитися працювати з функционалами і макросами.

1. Рекурсія. Різні форми рекурсии.

2. Які Застосовують функционалы.

3. Які Відображатимуть функционалы.

4. Макросы.

5. Завдання до лабораторної работе.

6. Вопросы.

1. Рекурсія. Різні форми рекурсии.

Основна ідея рекурсивного визначення у тому, що функцію можна з допомогою рекуррентных формул зводити до деяким початковим значенням, до раніше певним функцій або до самої обумовленою функції, але з більш «простими» аргументами. Обчислення такий функції закінчується той момент, як його зводиться до відомим початковим значениям.

Рекурсивна процедура, по-перше містить за крайнього заходу одну термінальну гілка і умова закінчення. По-друге, коли процедура доходить до рекурсивної галузі, то функціонуючий процес припиняється, і новий такий процес запускається спочатку, але вже новий рівень. Перерваний процес якимось чином запам’ятовується. Він чекати, і почне виконуватися лише по закінченні нового процесу. Натомість, новий процес може призупинитися, очікувати й т. д.

Говоритимемо про рекурсії за значенням і рекурсії по аргументів. У першому випадку виклик є вираженням, визначальним результат функції. У другому — як результату функції повертається значення деякою інший функції і рекурсивний виклик бере участь у обчисленні аргументів цієї функції. Аргументом рекурсивного виклику то, можливо знову рекурсивний виклик і такі викликів то, можливо много.

Розглянемо такі форми рекурсії: проста рекурсія; паралельна рекурсія; взаємна рекурсия.

Рекурсія називається простий, якщо виклик функції є у деякою галузі лише одне раз. Простий рекурсії в процедурному програмуванні відповідає звичайний цикл.

Наприклад напишемо функцію обчислення чисел Фібоначчі (F (1)=1; F (2)=1; F (n)=F (n-1)+F (n-2) при n>2):

(DEFUN FIB (N).

(IF (> N 0).

(IF (OR N=1 N=2) 1.

(+ (FIB (- N 1)) (FIB (- N 2)))).

‘ОШИБКА_ВВОДА)).

Рекурсию називають паралельної, якщо вона зустрічається одночасно у кількох аргументах функции:

(DEFUN f …

…(g … (f …) (f …) …).

…).

Розглянемо використання паралельної рекурсії з прикладу перетворення списковою структури в одноуровневый список:

(DEFUN PREOBR (L).

(COND.

((NULL L) NIL).

((ATOM L) (CONS (CAR L) NIL)).

(T (APPEND.

(PREOBR (CAR L)).

(PREOBR (CDR L)))))).

Рекурсія є взаємної між двома і більше функціями, якщо вони викликають друг друга:

(DEFUN f …

…(g …) …).

(DEFUN g …

…(f …) …).

Наприклад напишемо функцію звернення чи дзеркального відображення в вигляді двох взаємно рекурсивних функцій наступним образом:

(DEFUN obr (l).

(COND ((ATOM l) l).

(T (per l nil)))).

(DEFUN per (l res).

(COND ((NULL l) res).

(T (per (CDR l).

(CONS (obr (CAR l)) res))))).

2. Які Застосовують функционалы.

Функції, що дозволяють викликати інші функції, т. е. застосовувати функціональний аргумент для її параметрами називають застосовують функционалами. Вони дають можливість інтерпретувати і перетворювати дані у програмі і застосовувати їх у вычислениях.

APPLY.

APPLY є функцією двох аргументів, у тому числі перший аргумент є функцію, яка використовується до елементам списку, що становить другий аргумент функції APPLY:

(APPLY fn список).

_(SETQ a ‘+) (+.

_(APPLY a ‘(1 2 3)) (6.

_(APPLY ‘+ ‘(4 5 6)) (15.

FUNCALL.

Функціонал FUNCALL за своєю дією аналогічний APPLY, але аргументи для спричиненої він швидко приймає не списком, а, по отдельности:

(FUNCALL fn x1 x2 … xn).

_(FUNCALL ‘+ 4 5 6) (15.

FUNCALL і APPLY дозволяють ставити обчислення (функцію) довільній формою, наприклад, як і виклик функції, чи символом, значенням якого є функціональний об'єкт. Отже з’являється можливість використовувати синоніми імені функції. З іншого боку, ім'я функції можна використовувати як звичайну зміну, наприклад для зберігання інший функції (імені чи лямбда-выражения), й інші два сенсу (значення і визначення) ні заважати друг другу:

_(SETQ list ‘+) (+.

_(FUNCALL list 1 2) (3.

_(LIST 1 2) ((1 2).

3. Які Відображатимуть функционалы.

Які Відображатимуть чи MAP-функционалы є функціями, що є функціями, які певним чином відбивають список (послідовність) на нову послідовність чи породжують побічний ефект, пов’язаний із цією послідовністю. Кожна їх має як двох аргументів, значенням першого має бути ім'я певної раніше чи базової функції, чи лямбдавираз, викликаного MAP-функцией итерационно, інші ж аргументи служать для завдання аргументів з кожної ітерації. Природно, що кількість аргументів на її зверненні до MAP-функции має бути узгоджується з передбачених кількістю аргументів у аргумента-функции. Різниця між усіма MAP-функциями полягає у правилах формування возвращаемого значення і механізм вибору аргументів итерирующей функції кожному шаге.

Розглянемо основні типи MAP-функций.

MAPCAR.

Значення цієї функції обчислюється шляхом застосування функції fn до послідовним елементам xi списку, що є другим аргументом функції. Наприклад у разі одного списку виходить таке выражение:

(MAPCAR fn ‘(x1 x2 … xn)).

Як значення функціоналу повертається список, побудований з результатів викликів функціонального аргументу MAPCAR.

_(MAPCAR ‘LISTP ‘((f) h k (і u)) ((T NIL NIL T).

_(SETQ x ‘(a b з)) ((a b c).

_(MAPCAR ‘CONS x ‘(1 2 3)) (((a. 1) (b. 2) (з. 3)).

MAPLIST.

MAPLIST діє подібно MAPCAR, але дії здійснює не над елементами списку, а над послідовними CDR цього списка.

_(MAPLIST ‘LIST ‘((f) h k (і u)) ((T T T T).

_(MAPLIST ‘CONS ‘(a b з) ‘(1 2 3)) ((((a b з) 1 2 3) ((b з) 2 3) ((з) 3)).

Функционалы MAPCAR і MAPLIST йдуть на програмування циклів спеціального виду та у визначенні інших функцій, оскільки з допомогою можна скоротити запис повторюваних вычислений.

Функції MAPCAN і MAPCON є аналогами функцій MAPCAR і MAPLIST. Відмінність у тому, що MAPCAN і MAPCON не будують, використовуючи LIST, новий список із наслідків, а об'єднують списки, є результатами, до одного список.

4. Макросы.

Програмне формування висловів найприродніше здійснюється з допомогою макросів. Макроси дають можливість писати компактні, зорієнтовані завдання програми, які автоматично перетворюються на складніший, а більш близький машині ефективний лисповский код. За наявності макросредств деякі функції у мові можуть визначити як макрофункций. Таке визначення фактично задає закон попереднього побудови тіла функції безпосередньо перед фазою интерпретации.

Синтаксис визначення макросу така ж, як синтаксис використовуваної щодо функцій форми DEFUN:

(DEFMACRO ім'я лямбда-список тело).

Виклик макросу збігається формою з викликом функції, та його обчислення відрізняється від обчислення виклику функції. Перше відмінність у тому, що в макросе не обчислюються аргументи. Тіло макросу обчислюється з аргументами у вигляді, як вони записаны.

Друге відмінність у тому, що інтерпретація функцій, певних як макро, виробляється у два етапу. У першому, званому макрорасширением, відбувається формування лямбда-определения функції в залежність від поточного контексту, другою здійснюється інтерпретація створеного лямбда-выражения.

_(DEFMACRO setqq (x y).

(LIST ‘SETQ x (LIST ‘QUOTE y))) (setqq.

_(setqq a (b з)) ((b c).

_a ((b c).

Макроси від функцій у питаннях контексту обчислень. У час розширення макросу доступні синтаксичні зв’язку з контексту визначення. Обчислення ж отриманого результаті розширення форми виробляється поза контекстом макровиклику, і тому статичні зв’язку з макросу не діють. Використання макрофункций полегшує побудова мови з лиспоподобной структурою, має свій синтаксис, зручніший для користувача. Надмірне використання макросредств утрудняє читання і розуміння программ.

5. Завдання до лабораторної работе.

1. Напишіть рекурсивную функцію, визначальну скільки ж разів функція FIB викликає себе. Вочевидь, що FIB (1) і FIB (2) не викликають функцію FIB.

2. Напишіть функцію для обчислення полиномов Лежандра (P0(x)=1, P1(x)=x, Pn+1(x)= ((2*n+1)*x*Pn (x)-n*Pn-1(x))/(n+1) при n>1).

3. Напишіть функцію: вычисляющую число атомів на верхньому рівні списку (Для списку (а ((і з) е) воно одно трьом.); визначальну число подсписков на верхньому рівні списку; вычисляющую повне число подсписков, які входять у даний список будь-якою уровне.

4. Напишіть функцію: від двох аргументів X і N, що створює список з N раз повторених елементів X; удаляющую повторні входження елементів до списку; що з даного списку будує список списків його елементів, наприклад, (a b) (((a) (b)); вычисляющую максимальний рівень вкладення подсписков у списку; єдиним аргументом якого був б список списків, що об'єднує все ці списки до одного; яка від трьох аргументів X, N і V, добавляющую X на N-е місце у список V.

5. Напишіть функцію: аналогічну функції SUBST, але у якої третій аргумент W обов’язково може бути списком; які мають виробляти заміни X на Y лише з верхньому рівні W; заменяющую Y на число, однакову глибині вкладення Y в W, наприклад Y=A, W=((A B) A (З (A (A D)))) (((2 B) 1 (З (3 (4 D)))); аналогічну функції SUBST, але що виробляє взаємну заміну X на Y, т. е. X (Y, Y (X.

6. Обчислите значення наступних викликів: (APPLY ‘LIST ‘(a b)); (FUNCALL ‘LIST ‘(a b)); (FUNCALL ‘APPLY ‘LIST ‘(a b)); (FUNCALL ‘LIST ‘APPLY ‘(a b);

7. Визначте функціонал (A-APPLY f x), який застосовує кожну функцію fi списку f = (f1 f2 … fn) до відповідного елементу xi списку x = (x1 x2 … xn) і повертає список, сформований з результатов.

8. Визначте функціональний предикат (КОЖЕН перед список), який щирий у тому в тому разі, коли, є функціональним аргументом предикат перед щирий всім елементів списку список.

9. Визначте функціональний предикат (ПЕВНИЙ перед список), який щирий, коли предикат щирий хоча для одного елемента списка.

10. Визначте FUNCALL через функціонал APPLY.

11. Визначте функціонал (MAPLIST fn список) на одне спискового аргумента.

12. Визначте макрос, який повертає свій вызов.

13. Визначте лисповскую форму (IF умова p q) як макроса.

Примеры написання функцій. ;Subst — заміняє все входження Y в W на X. (DEFUN subst (x y w).

(COND ((NULL w) NIL) ;перевірка на закінчення списка.

((EQUAL ‘y ‘w) x).

((ATOM ‘w) w) ;

(t (CONS (subst x y (car w)) ;пошук в глубину.

(subst x y (cdr w)))))) ;пошук в ширину.

;COMPARE1 — порівнювати з зразком (defun compare1 (p d).

(cond ((and (null p) (null d)) t) ;вичерпалися списки?

((or (null p) (null d)) nil) ;однакова довжина списков?

((or (equal1 (car p) «&) ;є у зразку атом &.

(equal1 (car p) (car d))) ;чи голови списків равны.

(compare1 (cdr p) (cdr d))) ;& можна з будь-яким атомом.

((equal1 (car p) «*) ;є у зразку атом *.

(cond ((compare1 (cdr p) d)) ;* ні із чим не сопоставима.

((compare1 (cdr p) (cdr d))) ;* можна з одним атомом.

((compare1 p (cdr d))))))) ;* можна порівняти з неяк ;кими атомами.

6. Вопросы.

1. Що таке рекурсия?

2. Назвіть гідності її использования?

3. Що таке функционал?

4. Назвіть особливості які використовують і які відбивають функционалов?

5. Навіщо вони используются?

6. Що таке макрос?

7. Коли їх используют?

Лабораторна робота № 5.

Тема: Типи даних, і кошти роботи із нею. Уявлення знаний.

Мета: Вивчити типи даних, використовувані в MuLisp, а як і навчитися застосовувати в программах.

Точечная нотація. Структуровані типи даних. Уявлення знань. Завдання до лабораторної роботі. Вопросы.

1. Точкова нотация.

У Лиспе існує поняття точкової пари. Назва точкової пари відбувається з використаної у її записи точкової нотації, у якій для поділу полів CAR і CDR використовується виділена прогалинами точка. Базові функції CAR і CDR діють цілком симметрично.

_(CONS ‘a ‘d) ((a. d).

_(CAR ‘(a. b)) (a.

_(CDR ‘(a. (b. з))) ((b. c).

Будь-який список можна записати в точкової нотації. Перетворення можна здійснити (всіх рівнях списку) наступним образом:

(a1 a2 … an) ((a1. (a2. …(an. nil)…)).

_(a b з (d e)) ((a. (b. (з. ((d. (e. nil)). nil)))).

Ознакою списку тут служить NIL на полі CDR останнього елемента списку, котрий символізує його окончание.

Використання точкових пар в програмуванні на Лиспе загалом зайве. Точкові пари застосовують у теорії, книжках та довідниках по Лиспу. З іншого боку їх використовують що з деякими типами даних, і з асоціативними списками, соціальній та системному программировании.

2. Структуровані типи данных.

Списки (ассоциативные).

Асоціативний список чи навіть а-список — складається з точкових пар, тому її також називають списком пар.

((a1. t1) (a2. t2) … (an. tn)).

Перший елемент пари називають ключем, а другий — пов’язані з ключем даними. Зазвичай ключем є символ. пов’язані з нею дані може бути символами, списками чи якими якби іншими лисповскими объектами.

Діяльність зі списками пар треба вміти будувати списки, шукати дані про ключу і оновлювати их.

PAIRLIS.

Функція PAIRLIS будує а-список зі списку ключів і списку, сформованого з відповідних даних. Третім аргументом є старий а-список, на початок якого додаються нові пары:

(PAIRLIS ключі дані а-список).

_(SETQ спис ‘(один. Іванов)) ((один. Иванов).

_(SETQ спис.

(PAIRLIS ‘(три два) ‘(Петров Сидоров) спис)) (((три. Петров) (два. Сидоров) (один. Иванов)).

ASSOC.

Асоціативний список вважатимуться відображенням з багатьох ключів в безліч значень. Дані можна з допомогою функции.

(ASSOC ключ а-список).

яка шукає у списку пар дані, відповідні ключу, порівнюючи шуканий ключ з ключами пар зліва направо.

_(ASSOC ‘три спис) ((три. Петров).

ACONS.

Асоціативний список можна оновлювати і залучити до режимі стека. Нові пари додаються щодо нього лише у початок списку, хоча у списку вже може бути дані з тим самим ключем. Це здійснюється функцією ACONS:

(ACONS x y а-список).

Оскільки ASSOC переглядає список зліва праворуч і доходить лише до першої пари з потрібним ключем, то більш давні пари хіба що залишаються у тіні більш новых.

Строки.

Рядок складається з послідовності знаків. У рядку знаки записуються в послідовності друг за іншому, обмеження якої з обох сторін у ролі обмежувача використовується знак ««.

При введення рядки у інтерпретаторі, як результату отримуємо ту ж строку.

CHAR.

Довільний елемент рядки можна прочитати (т. е. послатися нею з допомогою індексу) функцією CHAR:

(CHAR рядок n).

(CHAR «рядок» 0) (з ;індексація починається з 0.

Порівняння строк.

(STRING= строка1 строка2).

(STRING< строка1 строка2).

(STRING> строка1 строка2).

(STRING/= строка1 строка2).

Массивы.

Робота з масивами в MuLisp необхідно завантажити файл ARRAY.LSP.

Масиви створюються формой:

(MAKE-ARRAY (n1 n2 … nN) режимы).

Функція повертає у ролі значення новий об'єкт — масив. n1, n2, … nN — цілі числа, їх кількість N відбиває розмірність масиву, а значення — розмір з кожної розмірності. Необов’язковими аргументами можна поставити тип елементів масиву, вказати їх початкові значення чи надати самому масиву динамічний розмір. Загальний розмір масиву у разі знати і закріплювати не обязательно.

Для обчислень, які з масивами, поруч із функцією створення масиву використовуються функції для вибірки та елементів масиву. Посилання на елемент N-мерного масиву здійснюється з допомогою вызова:

(ARREF масив n1 n2… nN).

n1, n2, …, nN — координати, чи індекси, елемента, який посилаються. Як функції присвоювання використовується узагальнена функція присвоювання SETF.

_(SETQ мас (MAKE-ARRAY ‘(5 4).

:ELEMENT-TYPE ‘ATOM.

:INITIAL-ELEMENT A)) ((ARRAY ((A A A A) … (A A A A) (5 6))).

_(SETF (AREF мас 0 1) B) (B.

_мас ((ARRAY ((A B A A) … (A A A A))).

Структуры.

Для об'єднання основних типів даних (чисел, символів, рядків, масивів) до комплексів, які відображатимуть предмети, факти використовується складовою тип, що називається структурами.

Визначення структурного типу здійснюється з допомогою макросу DEFSTRUCT, формою якого является.

(DEFSTRUCT класс-структур поле1 поле2.

…).

Визначимо структурний тип БАЗА що з компонент ПРОФІЛЬ, ПЛОЩ і ВМЕСТИМ:

_(DEFSTRUCT база профіль площ вместим) (БАЗА.

До кожного нових типів даних генерується начинающаяся з MAKEфункція створення структури такого типу. Наприклад об'єкт типу БАЗА можна створити, й привласнити перемінної БАЗА1 наступним вызовом:

_(SETQ БАЗА1 (MAKE-БАЗА)).

Полю з допомогою ключового слова, яким є ім'я половіючі жита із двокрапкою проти нього, привласнити під час створення початкова значение.

Виклик MAKE-БАЗА повертає у ролі значення створену структуру.

Для копіювання структури генерується функція, начинающаяся з COPY- (COPY-БАЗА).

До кожного поля обумовленою структури створюється функція доступу, чиє ім'я утворюється написанням після імені типу через тирі імені поля, например:

_(БАЗА-ПРОФИЛЬ x).

Виклик повертає значення поля ПРОФІЛЬ для БАЗИ, задаваемой структурою x.

Для присвоювання значень полях структури використовується узагальнена функція присвоювання SETF:

_(SETF (БАЗА-ПРОФИЛЬ БАЗА1) ОВОЧ) (ОВОЩ.

3. Уявлення знаний.

Продукционные системы.

Для уявлення знань використовують різні формализмы і мови уявлення даних. Найпоширенішим і простим розуміння є уявлення знань з допомогою правил продукції вида:

«ЯКЩО, ТЕ «.

Умови і негативні наслідки — це прості пропозиції природної мови. Такі формализмы називають продукционными. Ці правила нагадують умовні оператори IF-THEN мов програмування, однак з іншого интерпретируются.

(ЯКЩО на лампочку подано напруга й лампочка не горить то лампочка перегорела).

Через правила можна визначити, як програма повинна реагувати на зміна даних. У цьому непотрібно заздалегідь знати блок-схему управління обробкою даних. У звичайному програмі схема передачі управління і використання даних приречення самої програмою. Галуження в програмах можна тільки в заздалегідь вибраних точках. Для завдань, хід вирішення яких управляється самими даними, де галуження скоріш норма, ніж виняток, цей спосіб малоэффективен.

Фреймы.

Це окреме питання семантичних мереж. Це метод уявлення знань, який пов’язує властивості з вузлами, котрі представляють поняття і об'єкти. Властивості описуються атрибутами (званими слотами) та його значениями.

[f (,, …)] де f — ім'я фрейму; - слот; v — ім'я слота; g — його значение.

Використання фреймів зі своїми атрибутами і взаємозв'язками дозволяє зберігати знання про предметної області у структурованому вигляді, представляти в БЗ абстракції і аналогії. Система знань представляється в вигляді мережі під фреймом чи субфреймом. Кожен із фреймів відбиває певних властивостей, поняття, т. е. дозволяє задовольняти вимозі структурованості і связности.

З операціями присвоювання значень фреймам та інші операціями можна поєднувати складні побічні дії і взаимовлияния.

Однією з найважливіших концепцій формалізму фреймів є успадкування. Можна дати вказівку, що й значення слота у одному з фреймів не задається, то фрейм повинен успадкувати умалчивамое значення цього слота з фрейму вищого рівня. Успадкування фреймами значень слотів відбуватиметься у тому випадку, тоді як фреймі буде може бути слот РІЗНОВИД, де міститься ім'я іншого фрейма.

Використовуються й інші пов’язані з конкретною застосуванням способи уявлення, але де вони менш часті і, зазвичай, не годяться для використання їх у загальному случае.

Не можна однозначно сказати, який формалізм уявлення використаний у системі. У межах одному й тому ж системи до подання різних видів знань можна використовувати різні формализмы.

Пример1.

Як приклад уявлення знань у вигляді продукций розглянемо програму що зберігається в файлі EXSIS.LSP.

;EXSIS.LSP — приклад уявлення знань у вигляді продукций.

;определим пропозиції є правилами як структур, які з імені правила, умов і висновків, які у вигляді списку фактов.

(defstruct prav ім'я умови висновки) ;визначення структурного типу PRAV.

;створення структур типу PRAV і присвоювання їх змінним PRAV1 … PRAV5.

(setq prav1 (make-prav :ім'я «prav1 ;присвоєння полю ім'я значения.

:умови «((живий має шерсть)).

:висновки «((живий млекопитающее)))).

(setq prav2 (make-prav :ім'я «prav2.

:умови «((живий годує дитинчат молоком)).

:висновки «((живий млекопитающее)))).

(setq prav3 (make-prav :ім'я «prav3.

:умови «((живий має перья)).

:висновки «((живий птица)))).

(setq prav4 (make-prav :ім'я «prav4.

:умови «((живий вміє летать).

(живий несе яйца)).

:висновки «((живий птица)))).

(setq prav5 (make-prav :ім'я «prav5.

:умови «((живий їсть мясо)).

:висновки «((живий хищник)))).

(setq *правила* «(prav1 prav2 prav3 prav4 prav5) ;список, який зберігає правила системы.

(defun проверь-правило (правило).

;перевіряє чи підходить правило.

(подмнож (prav-условия правило) *факты*)).

(defun подмнож (подмнож множ).

;перевіряє, чи є множ подмнож.

(equal подмнож (intersection1 подмнож множ))).

(defun добавь-выводы (правило).

;розширює список фактів правилами вывода.

(do ((висновки (prav-выводы правило))) ;ініціалізація початкового значения.

((null висновки) *факти*) ;умова окончания.

(if (member (car висновки) *факти*) nil ;перевірка — входить «голова».

(progn (prin1 «Відповідно до правила: ») ;висновків до списку фактов.

(prin1 (prav-name правило)).

(push (car висновки) *факты*))).

(setq висновки (cdr висновки)))) ;крок изменения.

Для перевірки працездатності програми необхідні таку послідовність команд:

MuLisp-87.com Common. lsp — Завантаження системы.

(load structur. lsp) — підключення докладання до роботи зі структурами.

(load rash. lsp) — підключення розширення, яку ми розглянемо позже.

(load exsis. lsp) — підключення тестируемой программы.

На початку роботи з програмою необхідно форматувати список фактов.

(SETQ *факти* ‘(початкові факти)) де початкові факти — умови з якогось правила.

Пример2.

Приклад уявлення знань з допомогою фреймів. У прикладі згадуються три фрейму — ЗАХІД, ЗБОРИ і СОБРАНИЕ1. Фрейм ЗАХІД — найбільш загальний, фрейм ЗБОРИ — конкретніший, описує вид ЗАХОДИ, а фрейм СОБРАНИЕ1 — найбільш уточнений фрейм, описує конкретне ЗБОРИ. Фрейм ЗБОРИ називається субфреймом фрейму ЗАХІД, а СОБРАНИЕ1 — субфрейм фрейму СОБРАНИЕ.

(збори ім'я фрейма.

(різновид (захід)) імена і значення слотов.

(час (середовище 14.00)) (умалчиваемые значения.

(місце (зал засідань)) успадковуються субфреймами).

).

(собрание1.

(різновид (собрание)).

(присутні ((Вася) (Петя) (Маша))).

).

Реалізація фрейм-программы на Лиспе.

;EXSIS2 — реалізація фрейм-программы на Лиспе.

(setf (get ‘збори ‘різновид) ‘мероприятие).

(setf (get ‘збори ‘час) ‘(середовище 14.00)).

(setf (get ‘збори ‘місце) ‘(зал заседаний)).

(setf (get ‘собрание1 ‘різновид) ‘собрание).

(setf (get ‘собрание1 ‘присутні) ‘((Вася) (Петя) (Маша))).

;функція — визначальна наслідувані властивості (defun успадкування (фрейм имя_слота).

(cond ((get фрейм имя_слота)) ;є в фреймі даний слот? ;якщо так, то повернути його значение.

(t (cond ((get фрейм ‘різновид) ;інакше — перевірити наявність ;слота різновид. У випадку присутності - рекурсивно застосувати ;функцію до верхнім фреймам.

(успадкування (get фрейм ‘різновид) имя_слота)).

(t nil))))).

4. Завдання до лабораторної работе.

1.Переведите такі спискові запис у точкові: (w (x)); ((w) x); (nil nil nil); (v (w) x (y z)); ((v w) (x y) z); (((v) w x) y z).

2. Переведіть такі точкові запис у спискові: (a. (b. (з. nil))); ((a. nil). nil); (nil. (a. nil)); (a. ((b. (з. nil)). ((d. (e. nil)). nil))); (a. (b. ((з. (d. ((e. nil). (nil))). nil))); ((a. (b. nil)). (з. ((d. nil). (e. nil)))).

3. Напишіть функцію: від трьох аргументів, аналог вбудованої функції pairlis, будуючи список пар; від двох аргументів, аналог вбудованої функції assoc, яка шукає пару, відповідну ключу.

4. Напишіть функцію, аналог функції putassoc яка фізично змінює а-список (putassoc1 ключ дані а-список).

5. Розширте можливості програми EXSIS. LSP: напишіть функцію, пополняющую базу знань новими знаннями; напишіть функцію, удаляющую непотрібні знання; розширте базу знань; напишіть головну програму, до якої мають залучити всіх раніше написані функції (та наявні в EXSIS. LSP), і який виконувала в діалоговому режиме.

6. Подібною зміните програму EXSIS1.LSP.

7. Розробіть базу знань і правил бази знань РОЗКЛАД ЗАНЯТИЙ використовуючи: формалізм фреймів; формалізм продукций.

5. Вопросы.

1. У чому особливості точкової нотации?

2. Назвіть структуровані типи даних, їх особенности?

3. Способи уявлення знаний?

4. Їх гідності й недостатки?

Лабораторна робота № 6.

Тема: Вивчення навчальної версії мови Лисп — dlisp. Розширення бібліотеки функцій dlisp.

Мета: Ознайомитися із навчальною версією Лиспа — dlisp. Вивчити її можливості й особливо. Розширити бібліотеку функцій dlisp.

Интерфейс користувача. Функції, підтримувані dlisp. Розширення бібліотеки функцій dlisp. Завдання до лабораторної роботі. Вопросы.

1. Інтерфейс пользователя.

Запуск системи здійснюється командой:

DLISP.EXE.

При завантаженні системи починає працювати редактор, він чистить екран, малює рамку видає на екран головне меню:

Файл. Має такі опції: новий, відкрити, зберегти, зберегти як, выход.

Перегляд: екран виведення, екран интерпретатора.

Редактор.

Пошук: пошук, повторити пошук, замена.

Запуск: виконати, перезапустить, продолжить.

Налагодження: крок, трасування, контрольна точка, очистити все.

Параметри: режим екрана, перевірка синтаксиса.

Справка.

Потім система чекає, поки користувач не вибере жодну з опций.

Редактор працює із файлами, мають розширення LSP і перебувають в тієї ж директорії, як і файл DLISP.EXE.

Результати обчислень виводяться на спеціальний екран. Для перегляду цих результатів необхідно вибрати опцію «Перегляд» головного меню, а ній — «екран виведення». На повернення тому необхідно натиснути будь-яку клавишу.

Для перемикання в режим діалогу використовують клавіші SHIFT+TAB.

Для повтору попередньої команди використовують клавішу F3.

2. Функції, підтримувані dlisp.

Dlisp підтримує кілька різних типів данных:

* списки.

* символы.

* строковые константы.

* справжні числа.

* цілі числа.

По синтаксису і угодам Dlisp близький до MuLispу, більше, він є невеличкий його частью.

Dlisp містить певна кількість заздалегідь визначених функцій. Кожна функція викликається як список, першим елементом якого є ім'я функції, а іншими — аргументи цієї функції (якщо що є). Чимало понять з функцій — стандартні функції LISP, їх можна знайти у кожному посібнику з языку.

Функції MuLispа підтримувані dlispом і певні нами в попередніх лабораторних работах.

(+ …).

(- …).

(* …).

(/ …).

(= …).

(/=).

(< …).

(…).

(>= …).

(and …).

(atom).

(boundp).

(car).

(cdr).

(cond (…)…).

(cons).

(defun …).

(eq).

(if []).

(lambda …).

(list …).

(listp).

(mapcar …).

(not).

(null).

(numberp).

(or …).

(princ []).

(print []).

(progn …).

(quote).

(read).

(set).

(setq [ ]. .).

(while …).

(zerop).

Функції dlispа які використовуються MuLispом.

(co).

Ця функція повертає косинус, де — виявляється у радіанах. Например:

(co 0.0) повертає 1.0.

(co pi) повертає -1.0.

(sin).

Ця функція повертає синус як справжній число, де виражений в радіанах. Например:

(sin 1.0) повертає 0.841 471.

(sin 0.0) повертає 0.0.

(min …).

Ця функція повертає найменше із заданих. Кожне то, можливо справжнім або целым.

(nth).

Ця функція повертає «енний «елемент, де — номер елемента (нуль — перший елемент). Якщо більше, ніж номер останнього елемента, повертається nil. Например:

(nth 3 «(a b з d e)) повертає D.

(nth 0 «(a b з d e)) повертає A.

(nth 5 «(a b з d e)) повертає nil.

(strcat …).

Ця функція повертає рядок, що є результатом зчеплення строки1>, тощо. Например:

(strcat «a „“ bout ») повертає «about «.

(strcat «a „“ b „“ з ») повертає «abc «.

(strcat «a „“ „“ з ») повертає «ac «.

(strlen).

Ця функція повертає довжину в символах строковой константи як цілу величину. Например:

(stalen «abcd ») повертає 4.

(stalen «ab ») повертає 2.

(stalen «») повертає 0.

(subst).

Ця функція переглядає у пошуках і повертає копію заміняючи кожного зустрічного на. Не знайдений за, SUBST повертає незмінним. Наприклад, дано:

(setq sample «(a b (з d) b)) тогда:

(subst «qq «b sample) повертає (A QQ (З D) QQ).

(subst «qq «z sample) повертає (A B (З D) B).

(subst «qq «(з d) sample) повертає (A B QQ B).

(subst «(qq «rr) «(з d) sample) повертає (A B (QQ RR) B).

(subst «(qq «rr) «z sample) повертає (A B (З D) B).

У поєднанні з функцією ASSOC, SUBST забезпечує зручний спосіб заміни величини, знайденою по ключу в структурованому списку. Наприклад, дано:

(stq who «((ferst john) (mid q) (last public))) тогда:

(setq old (assoc «first who)) повертає (FIRST JOHN).

(setq new «(first j)) повертає (FIRST J).

(setq new old who) повертає ((FIRST J) (MID Q) (LAST PUBLIC)).

(type).

Ця функція повертає TYPE (тип), де TYPE — одна з наступних значень (як атом):

REAL числа з плаваючою запятой.

STR строковые константы.

INT цілі величины.

SYM символы.

LIST списки (і функції пользователя).

3. Розширення бібліотеки функцій dlisp.

Основні засади програмування на dlisp самі, що у MuLisp, у своїй зберігається синтаксис MuLispа.

Ніколи не використовуйте імена вбудованих функцій чи символів для функцій, визначених вами, оскільки зробить недоступними вбудовані функции.

Приклад розширення бібліотеки функцій dlispа міститься у файлі rash.lsp. На його запуску необхідні таку послідовність команд:

MuLisp87.com Common.lsp.

(load rash. lsp).

;File rash. lsp ;(Додаток до навчальної версії мови Лисп dlisp). ;Містить функції, розширюють бібліотеку dlisp Лиспа.

;Функция APPEND1 з'єднує два списку на один (defun append1 (l p).

(if (null l) p ;L порожній — повернути P (умова окончания),.

(cons (car l) ;інакше — створити список,.

(append1 (cdr l) p)))) ;використовуючи рекурсию.

;EQUAL1 — логічна ідентичність об'єктів (паралельна рекурсія) (defun equal1 (u v).

(cond ((null u) (null v)) ;повертає T якщо U і V пустые.

((numberp u) (if (numberp v) (= u v); перевірка nil)) ;на идентичность.

((numberp v) nil); чисел.

((atom u) (if (atom v) (eq u v) ;порівняння атомів nil)).

((atom v) nil).

(t (and (equal1 (car u) (car v)); ідентичність «голів «.

(equal1 (cdr u) (cdr v)))))) ;ідентичність «хвостів «.

;DELETE1 — видаляє елемент X зі списку L (defun delete1 (x l).

(cond ((null l) nil).

((equal1 (car l) x) (delete1 x (cdr l))).

(t (cons (car l) (delete1 x (cdr l)))))) ;гілка выполняется.

;у разі невиконання предыдущих.

;FULLENGTH1 — визначає повну довжину списку L (всіх рівнях) (defun fullength1 (l).

(cond ((null l) 0) ;для порожнього списку повертається 0.

((atom l) 1) ;якщо L є атомом — повертається 1.

(t (+ (fullength1 (car l)) ;підрахунок в глубину.

(fullength1 (cdr l)))))) ;підрахунок в ширину.

;DELETELIST1 — видаляє все елементи, що входять до список U зі списку V (defun deletelist1 (u v).

(cond ((null u) v).

(t (delete1 (car u).

(deletelist1 (cdr u) v))))).

;MEMBER1 — перевіряє входження елемента U до списку V на верхньому рівні (defun member1 (u v).

(cond ((null v) nil).

((equal1 u (car v)) v).

(t (member1 u (cdr v))))) ;Що стосується присутності S-выражения U у списку V функція повертає залишок списку V, який з U, інакше результатом обчислення є NIL.

;INTERSECTION1 — обчислює список загальних елементів двох списків (defun intersection1 (u v).

(cond ((null u) nil).

((member1 (car u) v);проверка ввійти «голови «сп. U в сп. V.

(cons (car u) (intersection1 (cdr u) v)));создание списка.

(t (intersection1 (cdr u) v))));ненужные елементи отбрасываются.

;UNION1 — об'єднує два списку, та на відміну від APPEND1, ;в результуючий список не додаються повторювані елементи (defun union1 (u v).

(cond ((null u) v).

((member1 (car u) v) ;отсеивание.

(union1 (cdr u) v)); непотрібних элементов.

(t (cons (car u).

(union1 (cdr u) v))))).

;COPY-LIST1 — копіює верхній рівень списку (defun copy-list1 (l).

(cond ((null l) nil).

(t (cons (car l).

(copy-list1 (cdr l)))))).

;COPY_TREE1 — копіює списочную структуру (defun copy-tree1 (l).

(cond ((null l) nil).

((atom l) l).

(t (cons (copy-tree1 (car l)).

(copy-tree1 (cdr l)))))).

;ADJOIN1 — додає елемент до списку (defun adjoin1 (x l).

(cond ((null l) nil).

((atom l) (cons x ;якщо L атом, він перетворюється на список,.

(cons l nil))) ;та був щодо нього додається X.

(t (cons x l)))).

;SET-DIFFERENCE1 — знаходить різницю двох списків (defun set-difference1 (w e).

(cond ((null w) nil).

((member1 (car w) e) ;відкидаються ненужные.

(set-difference1 (cdr w) e)) ;элементы.

(t (cons (car w).

(set-difference1 (cdr w) e))))).

;COMPARE1 — порівнювати з зразком (defun compare1 (p d).

(cond ((and (null p) (null d)) t) ;вичерпалися списки?

((or (null p) (null d)) nil) ;однакова довжина списков?

((or (equal1 (car p) «&) ;є у зразку атом &.

(equal1 (car p) (car d))) ;чи голови списків равны.

(compare1 (cdr p) (cdr d))) ;& можна з будь-яким атомом.

((equal1 (car p) «*) ;є у зразку атом *.

(cond ((compare1 (cdr p) d)) ;* ні із чим не сопоставима.

((compare1 (cdr p) (cdr d))) ;* можна з одним атомом.

((compare1 p (cdr d))))))) ;* можна з несколькими.

;атомами.

;SUBSTITUTE1 — заміна у списку L атома P. S на атом N (defun substitute1 (n p. s l).

(cond ((null l) nil).

((atom (car l)).

(cond ((equal1 p. s (car l)).

(cons n (substitute1 n p. s (cdr l)))).

(t (cons (car l) (substitute1 n p. s (cdr l)))))).

(t (cons (substitute1 n p. s (car l)).

(substitute1 n p. s (cdr l)))))).

;DELETE-DUPLICATES1 — видалення повторюваних елементів (defun delete-duplicates1 (l).

(cond ((null l) nil).

((member1 (car l) (cdr l)).

(delete-duplicates1 (cdr l))).

(t (cons (car l) (delete-duplicates1 (cdr l)))))).

;ATOMLIST1 — перевірка на одноуровневый список (defun atomlist1 (l).

(cond ((null l) t).

((listp (car l)) nil).

(t (atomlist1 (cdr l))))).

;REVERSE1 — звертає верхній рівень списку (DEFUN REVERSE1 (l).

(COND ((NULL l) NIL).

(T (APPEND1 (REVERSE1 (CDR l)).

(CONS (CAR l) NIL))))).

4. Завдання до лабораторної работе.

Напишіть функцію, аналог системної функції Лиспа:

1. а) (1+) Результат функції -, збільшене на одиницю. в) (1-) Результат функції -, зменшене на единицу.

2. а) (incf пам’ять прирощення) Додавання збільшення до в пам’яті. в) (decf пам’ять прирощення) Віднімання збільшення у складі в памяти.

3. (expt) Ця функція повертає, споруджений зазначену. Якщо обидва аргументу цілі, то результат — ціла кількість. У іншому разі, результат — дійсне число.

4. (gcd) Функція повертає найбільший загальний дільник і. повинні бути целыми.

5. а) (first), second, third, тощо. буд. повертають відповідно перший, другий, третій, тощо. буд. елемент списку. в) (last) Ця функція повертає останній елемент списку. ні дорівнювати nil. LAST повертає або атом або список.

6. а) (max …) Ця функція повертає найбільше з заданих чисел. в) (min …) Ця функція повертає найменше із заданих чисел.

7. а) (evenp) Перевіряє, парне чи число. Вона повертає T — якщо число парне і NIL — інакше. в) (oddrp) Ця функція — протилежна дією функції evenp.

8. яка сортує числа: а, по зростанню. в) по убыванию.

9. предикат — що визначає: а) числа з плаваючою коми. в) цілі числа. р) строковые константи. буд) символи. е) списки.

10. яка від одного аргументу, яка генерує все циклічні перестановки списка.

11. яка від одного елемента, котра, за даному списку обчислює список його елементів: а) можна зустріти у ньому більше однієї, 2, … раз. в) можна зустріти у ньому щонайменше 2, 3, … раз.

S. Запишіть всі функції, написані вами, до одного файл. Для налагодження програми використовуйте вбудовані кошти dlispа.

5. Вопросы.

1. Які способи тестування програм передбачені в цьому dlisp?

2. У чому їхнє различия?

3. Які функції передбачені до роботи зі строковыми константами в dlisp?

4. Назвіть їх основні особенности?