Лабораторна робота № 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)
(C) 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 список) (S - вираз (атом або список ).
_ (CAR '(abcd)) (a
_ (CAR' ((ab) cd)) ((ab)
_ ( CAR '(a)) (a
_ (CAR NIL) (NIL «Голова порожнього списку - порожнійсписок. »
Виклик функції CAR з аргументом (abcd) без апострофа був бипроінтерпретувати як виклик функції «a» з аргументом «bcd», і було ботримано повідомлення про помилку.
Функція CAR має сенс тільки для аргументів, що є списками.
(CAR 'a) (Error
Функція CDR - повертає в якості значення хвостову частину списку,тобто список, який отримують із вихідного списку після видалення з ньогоголовного елемента:
(CDR список) (список
Функція CDR визначена тільки для списків.
_ (CDR '(abcd)) ((bcd)
_ (CDR '((ab) cd)) ((cd)
_ (CDR' (a (bcd))) (((bcd)) < p> _ (CDR '(a)) (NIL
_ (CDR NIL) (NIL
_ (CDR' a) (Error
Функція створення CONS.
Функція CONS будує новий список з переданих їй якаргументів голови і хвоста.
(CONS голова хвіст)
Для того щоб можна було включити перший елемент функції CONS вяк перший елемент значення другого аргументу цієї функції, другийаргумент повинен бути списком. Значним функції CONS завжди буде список:
(CONS s-вираз список) (список
_ (CONS 'a' (bc)) ((abc)
_ (CONS '(ab)' (cd)) (((ab) cd)
_ (CONS (+ 1 2) '(+ 3)) ((3 + 3)
_ (CONS '(abc) NIL) (((abc))
_ (CONS NIL' (abc)) ((NIL abc)
Предикати ATOM, EQ, EQL, EQUAL.
Предикат - функція, яка визначає, чи має аргументпевною властивістю, і повертає як значення NIL або T.
Предикат ATOM - перевіряє, чи є аргумент атомом:
(ATOM s - вираз)
Значенням виклику ATOM буде T, якщо аргументом є атом, та NIL --в іншому випадку.
_ (ATOM 'a) (T
_ (ATOM' (abc)) (NIL
_ (ATOM NIL) (T
_ (ATOM '(NIL)) (NIL
Предикат EQ порівнює два символи і повертає значення T, якщо вониідентичні, інакше - NIL. За допомогою EQ порівнюють тільки символиабо константи T та NIL.
_ (EQ 'a' b) (NIL
_ (EQ 'a (CAR' (abc))) (T < p> _ (EQ NIL ()) (T
Предикат EQL працює так само як і EQ, але додатково дозволяєпорівнювати однотипні числа.
_ (EQL 2 2) (T
_ (EQL 2.0 2.0) (T
_ (EQL 2 2.0) (NIL
Для порівняння чисел різних типів використовують предикат «=».< br>Значним предиката «=» є T в разі рівності чисел незалежно відїх типів і зовнішнього вигляду запису.
(= 2 2.0) (T
Предикат EQUAL перевіряє ідентичність записів. Він працює як EQL,але додатково перевіряє спільність двох списків. Якщо зовнішняструктура двох лісповскіх об'єктів однакова, то результатом EQUAL буде
T.
_ (EQUAL 'a' a) (T
_ (EQUAL '(abc)' (abc)) (T
_ (EQUAL '(abc)' (CONS 'a' (bc))) (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 '((abcd) e)) ((cd)
_ (CDDR '(klm)) ((M)
Функція LIST - створює список з елементів. Вона повертає в якостісвого значення список з значень аргументів. Кількість аргументівдовільно.
_ (LIST 'a' b 'c) ((abc)
_ (LIST' a 'b (+ 1 2)) ((ab 3)
4. Символи, властивості символів.
Опції присвоювання: SET, SETQ, SETF.
Функція SET - присвоює символу або пов'язує з ним якийсьзначення. Причому вона обчислює обидва своїх аргументу. Встановлена зв'язокдійсна до кінця роботи, якщо цього імені не буде присвоєно новезначення функцією SET.
_ (SET 'a' (bcd)) ((bcd)
_a ((bcd)
_ (SET (CAR a ) (CDR (ofg)) ((fg)
_a ((bcd)
_ (CAR a) (b
_b ((fg)
Значення символу обчислюється за допомогою спеціальної функції Symbol -value, яка повертає в якості значення значення свого аргументу.
_ (Symbol-value (CAR a)) ((fg)
Функція SETQ - пов'язує ім'я, не обчислюючи його. Ця функція відрізняєтьсявід SET тим, що обчислює тільки другий аргумент.
_ (SETQ d '(lmn)) ((lmn)
Функція SETF - узагальнена функція присвоєння. SETF використовується длязанесення значення в комірку пам'яті.
(SETF осередок-пам'яті значення)
_ (SETF осередок '(abc)) ((abc)
_ комірка ( (abc)
Змінна «осередок» без апострофа вказує на комірку пам'яті, кудипоміщається в якості значення список (abc).
Шрифт.
У Лісп із символом можна зв'язати іменовані властивості. Властивостісимволу записуються в що зберігається разом з символом список властивостей. Властивістьмає ім'я і значення. Список властивостей може бути порожній. Його можна змінюватиабо видаляти без обмежень.
(імя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. Засоби мови для роботи з числами. (Математичні та логічніфункції).
У мові Лісп як для виконання функцій, так і для запису виразуприйнята однакова префіксная форма запису, при якій як ім'я функціїабо дії, так і самі аргументи записуються всередині дужок:
(fx), (gxy), (hx (gyz)) і т. д.
Арифметичні дії:
(+ числа) - додавання чисел
(- число числа) - віднімання чисел з числа
(* числа) - множення чисел і т. д.
_ (+ 5 7 4) (16
_ (- 10 3 4 1) (2
_ (/ 15 3) (5 < p> Порівняння чисел:
(= число числа) (рівні (все)
(<число числа) (менше (для всіх)
(> число числа) (більше (для всіх) і т. д.
Числові предикати:
(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 ))));< br>(NULL (CDDR (QUOTE ((5 6) (7 8 )))));< br>(EQUAL (CAR (QUOTE ((7)))) (CDR (QUOTE (5 7 ))));< br>(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) < p> 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 (xy) (+ xy))
формальних параметрів означає, що їх можна замінити на будь-якіінші символи, і це не позначиться на обчисленнях, що визначаються функцією.
Лямбда-вираз - це визначення обчислень і параметрів функції вчистому вигляді без фактичних параметрів, або аргументів. Для того, щобзастосувати таку функцію до деяких аргументів, потрібно у виконанні функціїпоставити лямбда-визначення на місце імені функції:
(лямбда-вираз а1 а2 ... аn)
Тут ai - форми, що задають фактичні параметри, які обчислюютьсяяк завжди.
_ ((lambda (xy) (+ xy)) 1 2) (3
Лямбда-виклики можна вільно об'єднувати між собою та іншимиформами. Вкладені лямбда-виклики можна ставити як на місце тіла лямбда -вираження, так і на місце фактичних параметрів.
_ ((lambda (x)
; Тіло лямбда-виклику -
((lambda (y) (list xy)) 'b))' a) ((ab)лямбда-дзвінок.
Записувати виклики функцій повністю за допомогою лямбда-викликів нерозумно, оскільки дуже скоро вираження у виклику довелося б повторювати,хоча різні виклики однієї функції відрізняються лише в частині фактичнихпараметрів. Проблема можна вирішити шляхом іменування лямбда-виразів івикористання у виклику лише імені.
Дати ім'я та визначити нову функцію можна за допомогою функції DEFUN:
(DEFUN ім'я лямбда-список тіло)
DEFUN з'єднує символ з лямбда-виразом, і символ починаєпредставляти визначені цим лямбда-виразом обчислення. Значення цієїформи є ім'я нової функції.
Після іменування функції її виклик здійснюється по імені іпараметрами.
_ (defun list1 (xy)
(cons x (cons y nil))) (list1
_ (list1 'c' n) ((cn)
(eval)
Функція повертає результат виразу, де --будь-який вираз мови LISP. Наприклад, дано:
(setq a 123)
(setq b 'a)
(eval 4.0) (4.000000
( 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; значення < p> 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 (xy)
(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 '(bcd)) ((bcd)
_ (RPLACA a' d) ((dcd)
_ (RPLACD a '(onm)) ((donm)
_a ((donm)
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 xx) і (RPLACD xx),якщо:x = '(a b);x = '(a);
11. Розрахуйте значення наступних виразів:
(RPLACD '(a)' b);
(RPLACA '(a)' b);
(RPLACD (CDDR '(a b x))' c);
(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 'c)) (LIST xyz))) ((abc)
_ (LET ((x (LET ((z' a)) z)) (y 'b))
(LIST xy)) ((ab)
_ (LET ((x 1) (y (+ x 1 )))
(LIST xy) ) (ERROR
При обчисленні у У і Х ще немає зв'язку. Значення зміннимприсвоюються одночасно. Це означає, що значення всіх змінних miобчислюються до того, як здійснюється зв'язування з формальнимипараметрами.
Подібної помилки можна уникнути за допомогою форми LET *:
_ (LET * ((x 1) (y (+ x 1 )))
(LIST xy)) ((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 (+ xj) )) (9
3. розгалуження обчислень.
Умовне пропозицію COND:
(COND (p1 a1)
...
(pn an))
предикатами pi і результуючими виразами ai можуть бутидовільні форми. Вирази pi обчислюються послідовно до тих пір,поки не зустрінеться вираз, значенням якого є T. Обчислюєтьсярезультуюче вираз, відповідне цього предикату, і отриманезначення повертається як значення за все пропозиції COND. Якщоістинного предиката нет то значенням COND буде NIL.
Рекомендується як останнього предиката використовувати символ T.
Тоді відповідне йому an буде обчислюватися в тому випадку, якщо іншіумови не виконуються.
Якщо умові не ставиться у відповідність результуюче вираз, тояк результат видається саме значення предиката. Якщо ж умовівідповідають декілька форм, то при його істинності форми обчислюютьсяпослідовно зліва на право і результатом пропозиції COND будезначення останньої форми.
Пропозиції COND можна комбінувати.
(COND ((> x 0) (SETQ рез x))
(( ((= х 0))
(Т 'помилка))
Пропозиція IF.
(IF умова то-форма інакше-форма)
(IF (> x 0) (SETQ y (+ yx)) (SETQ y (- yx )))
Якщо виконується умова (тобто х> 0), то до значення y додаєтьсязначення х, інакше (xxy) (IF ( (PRINT
«Середня (1 )»))
(IF (> yz) (PROGN (PRINTy)
(TERPRI)
(PRINT «середня (2 )»))
(PROGN
(PRIN1 z)
(PRIN1 «середня (3 )»)))))
(( (TERPRI)
(PRIN1 «середня (4 )»))
(IF (> xz) (PROGN (PRINCx)
(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) hk (iu)) ((T NIL NIL T)
_ (SETQ x '(abc) ) ((abc)
_ (MAPCAR 'CONS x' (1 2 3)) (((a. 1) (b. 2) (c. 3))
MAPLIST.
MAPLIST діє подібно MAPCAR, але дії здійснює не наделементами списку, а над послідовними CDR цього списку.
_ (MAPLIST 'LIST' ((f) hk (iu)) ((TTTT)
_ (MAPLIST 'CONS' ( abc) '(1 2 3)) ((((abc) 1 2 3) ((bc) 2 3) ((c
) 3))
функціонали MAPCAR і MAPLIST використовуються для програмування циклівспеціального виду і у визначенні інших функцій, оскільки з їх допомогоюможна скоротити запис повторюваних обчислень.
Опції MAPCAN і MAPCON є аналогами функцій MAPCAR і MAPLIST.
Відмінність полягає в тому, що MAPCAN і MAPCON не будують, використовуючи LIST, новийсписок з результатів, а об'єднують списки, які є результатами, в одинсписок.
4. Макроси.
Програмне формування виразів найбільш природноздійснюється за допомогою макросів. Макроси дають можливість писатикомпактні, орієнтовані на завдання програми, які автоматичноперетворюються в більш складний, але більш близький машині ефективнийлісповскій код. За наявності макросредств деякі функції в мові можутьбути визначені у вигляді макрофункцій. Таке визначення фактично задаєзакон попереднього побудови тіла функції безпосередньо перед фазоюінтерпретації.
Синтаксис визначення макроса виглядає так само, як синтаксисщо використовується при визначенні функцій форми DEFUN:
(DEFMACRO ім'я лямбда-список тіло)
Виклик макроса співпадає за формою з викликом функції, але його обчисленнявідрізняється від обчислення виклику функції. Перша відмінність полягає в тому, щов макросі не обчислюються АРГументи. Тіло макросу обчислюється з аргументамив тому вигляді, як вони записані.
Друга відмінність полягає в тому, що інтерпретація функцій, визначенихяк макро, проводиться у два етапи. На першому, званомумакрорасшіреніем, відбувається формування лямбда-визначення функції вЗалежно від поточного контексту, на другому здійснюється інтерпретаціяствореного лямбда-вирази.
_ (DEFMACRO setqq (xy)
(LIST 'SETQ x (LIST' QUOTE y))) (setqq
_ ( setqq a (bc)) ((bc)
_a ((bc)
Макроси відрізняються від функцій і відносно контексту обчислень. Підчас розширення макросу доступні синтаксичні зв'язку з контекстувизначення. Обчислення ж отриманої в результаті розширення формиздійснюється поза контекстом макровизова, і тому статичні зв'язку змакросу не діють. Використання макрофункцій полегшує побудова мовиз ліспоподобной структурою, що має свій синтаксис, більш зручний длякористувача. Надмірне використання макросредств ускладнює читання ірозуміння програм.
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;видаляє повторні входження елементів в список;яка із списку будує список списків його елементів, наприклад, (ab) (((a) (b));обчислює максимальний рівень вкладення підсписки у списку;єдиним аргументом якої був би список списків, що об'єднує всіці списки в один;що залежить від трьох аргументів X, N і V, що додає X на N-е місце в список
V.
5. Напишіть функцію:аналогічну функції SUBST, але в якій третій аргумент W обов'язковоповинен бути списком;що повинна робити заміни X на Y тільки на верхньому рівні W;замінюючу Y на число, яке дорівнює глибині вкладення Y в W, наприклад Y = A, W = ((A
B) A (C (A (A D)))) (((2 B) 1 (C (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 '(ab);
7. Визначте функціонал (A-APPLY fx), який застосовує кожнуфункцію fi списку f = (f1 f2 ... fn) до відповідного елементу xi списку x = (x1 x2 ... xn) і повертає список, сформований з результатів.
8. Визначте функціональний предикат (КОЖЕН перед список), якийправдивий в тому і тільки в тому випадку, коли, що є функціональнимаргументом предикат перед правдивий для всіх елементів списку список.
9. Визначте функціональний предикат (Деякі перед список),який правдивий, коли предикат правдивий хоча б для одного елемента списку.
10. Визначте FUNCALL через ф
