$ (DEFUN sm (lst) $ (sm ‘()) $ (sm ‘(q w e))
((NULL lst) 10 1) 1 12
(SETQ b 2)
((CDR lst) 12) $ (sm ‘(i)) $ (sm ‘g)
(SETQ b 3) ) 3 3
Як бачимо, після виконання простого завдання керування завжди передається наступному завданню (якщо таке є). Якщо предикат умовного завдання істинний, то виконується його хвіст і повертається результат останнього виразу хвоста.
Вмонтована функція (LIST x1 ... xn) утворює та видає список, елементами якого є x1, ..., xn. Якщо аргументи не задані, результатом буде NIL.
$ (LIST ‘a ‘b ‘c ‘d) $ (LIST ‘a ‘(b c) ‘d) $ (LIST)
(a b c d) (a (b c) d) NIL
Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку. Інтуїтивно необхідно порівняти символ з першим елементом списку, потім з другим елементом і так далі. Проблема в такому розв’язку виникає в тому, що ми не знаємо наперед довжини списку. А якщо ми і знаємо цю довжину, і якщо вона велика, то тіло функції буде дуже великим. Така функція буде мати приблизно такий вигляд (перший стовпчик):
$ (DEFUN MEMBER (nam lst) $ (DEFUUN MEMBER (nam lst)
((EQL nam (FIRST lst))) ((NULL lst) NIL)
((EQL nam (SECOND lst))) ((EQL nam (CAR lst)) T)
((EQL nam (THIRD lst))) (MEMBER nam (CDR lst)) )
((EQL nam (THIRD (CAR lst))))
. . . . . . . . . . . . . . .
Змінимо наш підхід до побудови функції. В другому стовпчику побудовано функцію MEMBER, в основі якої лежить рекурсивний підхід, який базується на наступних фактах:
1. Якщо список порожній (не має елементів), то nam не належить списку.
2. Якщо nam дорівнює голові списку, то nam належить списку.
3. Якщо nam не дорівнює голові списку, то nam може належити списку тоді і тільки тоді коли nam належить хвосту списку.
Розглянемо дві рекурсивні функції: REMBER (REMove memBER), яка має два аргументи — атом obj та список lst і яка видаляє перше зустрічання атома obj в списку lst. REMBER-ALL яка видаляє всі атоми obj в списку lst.
$ (DEFUN REMBER (obj lst) (DEFUN REMBER-ALL (obj lst)
((NULL lst) NIL) ((NULL lst) NIL)
((EQL obj (CAR lst)) (CDR lst)) ((EQL obj (CAR lst))
(CONS (CAR lst) (REMBER-ALL obj (CDR lst))
(REMBER obj (CDR lst))) ) (CONS (CAR lst)
(REMBER-ALL obj (CDR lst))))
Результат роботи цих функцій проілюструємо на прикладах:
$ (REMBER ‘a ‘(q a w e r t a y)) $ (REMBER-ALL ‘a ‘(q a w e r t a y))
(q w e r t a y) (q w e r t y)
Примітивна функція EQL використовується для порівняння атомів. Часто виникає потреба порівнювати списки. Напишемо функцію EQLIST, яка порівнює списки. Її побудуємо на основі наступних фактів:
1. Якщо перший список порожній, то, якщо і другий список порожній, повернути Т, інакше повернути NIL (або просто повернути (NULL другого списку)).
2. Якщо другий список порожній, повернути NIL.
3. Якщо голова першого списку не дорівнює голові другого списку, повернути NIL.
4. Перевірити рівність хвостів першого та другого списків.
$ (DEFUN EQLIST (lst1 lst2) $ (DEFUN NOT (obj)
((NULL lst1) (NULL lst2)) (EQL obj NIL) )
((NULL lst2) NIL)
((NOT (EQL (CAR lst1) (CAR lst2))) NIL)
(EQLIST (CDR lst1) (CDR lst2)) )
Функція NOT повертає NIL, якщо список не порожній і Т інакше.
Розглянемо задачу об’єднання списків. Роботу функції APPEND, аргументами якої є два списки lst1 та lst2, можна описати наступним чином:
1. Якщо lst1 порожній, повернути lst2.
2. З’єднати голову першого списку зі списком, який отримано в результаті об’єднання хвоста першого списку з другим списком.
$ (DEFUN APPEND (lst1 lst2)
((NULL lst1) lst2)
(CONS (CAR lst1) (APPEND (CDR lst1) lst2)) )
Функція (REVERSE lst1) обертаєсписок lst1. Якщо вихідний список порожній, то і результатом буде порожній список. Інакше необхідно об’єднати обернений хвіст вихідного списку з його першим елементом. Оскільки на вхід другого аргумента функції APPEND повинен подаватися список, необхідно з першого елемента списку зробити список, який складається лише з нього. Цевиконуєкоманда (CONS (CAR lst) NIL).
$ (DEFUN REVERSE (lst)
((NULL lst) NIL)
(APPEND (REVERSE (CDR lst)) (CONS (CAR lst) NIL)) )
Напишемофункцію REVERSE безвикористанняфункції APPEND. Для цього побудуємо функцію REVERSE з двома аргументами на принципі обробки стеку. Вихідний список — стек символів. Якщо він порожній, то і результуючий стек буде порожнім. Інакше взяти символ з вершини стеку і покласти його на другий стек. Другий стек при виклику повинен бути NIL: (REVER <list> NIL).
$ (DEFUN REVER (lst1 lst2) $ (REVER ‘(q w e) NIL)
((NULL lst1) lst2) (e w q)
(REVER (CDR lst1) (CONS (CAR lst1) lst2)) )
5. Середовище системи muLisp
Середовище muLisp або поточний стан системи складається з усіх активних на даний момент структур даних, значень змінних та визначених функцій. Команда SAVE зберігає поточне середовище muLisp у вигляді SYS - файлу. Команда (SAVE ’C:HOME) зберігає середовище в файл HOME.SYS на диску C. Після успішного виконання команди запису повертається Т, інакше — NIL.
Середовище muLisp може бути завантажене за допомогою команди LOAD: (LOAD <file>). Якщо файл не знайдено, повертається NIL, інакше жодне значення не повертається, а mulisp починає працювати з новим середовищем.
Для завантаження SYS-файлів безпосередньо після запуску muLISP може використовуватися команда операційного середовища (ОС). Наприклад, команда ОС
> muLISP C:HOME
завантажує SYS-файл HOME.SYS із пристрою C після запуску muLISP із пристрою, взятого по замовченню. Відмітимо, що тип SYS-файла у команді не вказується. Якщо SYS-файл не знайдено при завантаженні з використанням команди ОС, на екран дисплею видається повідомлення: File not found.
Після завантаження SYS-файла кількість пам’яті, призначеної для кожної області даних, коректується у відповідності до поточного об’єму пам’яті. Це означає, що поточний об’єм пам’яті не обов’язково повинен бути точно таким, як і при створенні SYS-файлів. Але якщо пам’яті для розташування середовища SYS-файлів недостатньо, то виникає помилка типу "Недостатньо пам’яті, переривання", і muLISP буде завершено.
6. Трасировка функцій в muLisp.
Мова програмування muLisp для трасировки використовує програму debug.lsp, яка завантажується в середовище Ліспу. Для того, щоб дозволити трасировку функції <func>, необхідно дати команду (TRACE-FUNCTION <func>). Якщо після цього викликати функцію func з параметрами, то на екрані відобразиться шлях виконання функції. На кожному кроці буде виводитися ім’я функції та список фактичних параметрів. Після виконання функції на екран виводиться значення функції. Команда (UNTRACE-FUNCTION <func>) забороняє трасировку функції <func>. Якщо в тілі функції <func> існує виклик інших функцій, і ми хочемо побачити їх трасировку, необхідно дозволити їх трасировку. Вираз <func>=<value> в трасі означає те, що функція <func> повертає значення <value>.
Якщо вивід траси відбувається дуже швидко, для тимчасової зупинки траси можна використати <CTRL-S>.
Наприклад, розглянемо трасування функціі APPEND (злиття двох списків), яка була визначена раніше. Післявиконаннякоманд
$ (TRACE-FUNCTION ‘APPEND)
$ (APPEND ‘(q w e) (r t y u))
на екрані відобразиться траса:
APPEND [(Q W E), (R T Y U)]
APPEND [(W E), (R T Y U)]
APPEND [(E), (R T Y U)]
APPEND [NIL, (R T Y U)]
APPEND = (R T Y U)
APPEND = (E R T Y U)
APPEND = (W E R T Y U)
APPEND = (Q W E R T Y U)
(Q W E R T Y U)
Виведемонаекрантрасуфункції REVERSE здозволом (лівийстовпчик) табездозволу (правийстовпчик) трасировкифункції APPEND длявиразу (REVERSE ‘(q w)).
$ (TRACE-FUNCTION ‘REVERSE) $ (TRACE-FUNCTION ‘REVERSE)
$ (TRACE-FUNCTION ‘APPEND) $ (REVERSE ‘(q w))
$ (REVERSE ‘(q w)) REVERSE [(Q W)]
REVERSE [(Q W)] REVERSE [(W)]
REVERSE [(W)] REVERSE [NIL]
REVERSE [NIL] REVERSE = NIL
REVERSE = NIL REVERSE = (W)
APPEND [NIL, (W)] REVERSE = (W Q)
APPEND = (W) (W Q)
REVERSE = (W)
APPEND [(W), (Q)]
APPEND [NIL, (Q)]
APPEND = (Q)
APPEND = (W Q)
REVERSE = (W Q)
(W Q)