ЛИСП
ЛИСП
Лабораторная работа № 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 ‘(a b c d)) ( a
_(CAR ‘((a b) c d)) ( (a b)
_(CAR ‘(a)) ( a
_(CAR NIL) ( NIL «Голова пустого списка - пустой
список.»
Вызов функции CAR с аргументом (a b c d) без апострофа был бы
проинтерпретирован как вызов функции «a» с аргументом «b c d», и было бы
получено сообщение об ошибке.
Функция CAR имеет смысл только для аргументов, являющихся списками.
(CAR ‘a) ( Error
Функция CDR - возвращает в качестве значения хвостовую часть списка,
т. е. список, получаемый из исходного списка после удаления из него
головного элемента:
(CDR список) ( список
Функция CDR определена только для списков.
_(CDR ‘(a b c d)) ( (b c d)
_(CDR ‘((a b) c d)) ( (c d)
_(CDR ‘(a (b c d))) ( ((b c d))
_(CDR ‘(a)) ( NIL
_(CDR NIL) ( NIL
_(CDR ‘a) ( Error
Функция создания CONS.
Функция CONS строит новый список из переданных ей в качестве
аргументов головы и хвоста.
(CONS голова хвост)
Для того чтобы можно было включить первый элемент функции CONS в
качестве первого элемента значения второго аргумента этой функции, второй
аргумент должен быть списком. Значением функции CONS всегда будет список:
(CONS s-выражение список) ( список
_(CONS ‘a ‘(b c)) ( (a b c)
_(CONS ‘(a b) ‘(c d)) ( ((a b) c d)
_(CONS (+ 1 2) ‘(+ 3)) ( (3 + 3)
_(CONS ‘(a b c) NIL) ( ((a b c))
_(CONS NIL ‘(a b c)) ( (NIL a b c)
Предикаты ATOM, EQ, EQL, EQUAL.
Предикат - функция, которая определяет, обладает ли аргумент
определенным свойством, и возвращает в качестве значения NIL или T.
Предикат ATOM - проверяет, является ли аргумент атомом:
(ATOM s - выражение)
Значением вызова ATOM будет T, если аргументом является атом, и NIL -
в противном случае.
_(ATOM ‘a) ( T
_(ATOM ‘(a b c)) ( NIL
_(ATOM NIL) ( T
_(ATOM ‘(NIL)) ( NIL
Предикат EQ сравнивает два символа и возвращает значение T, если они
идентичны, в противном случае - NIL. С помощью EQ сравнивают только символы
или константы T и NIL.
_(EQ ‘a ‘b) ( NIL
_(EQ ‘a (CAR ‘(a b c))) ( 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 c) ‘(a b c)) ( T
_(EQUAL ‘(a b c) ‘(CONS ‘a ‘(b c))) ( 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 c d) e)) ( (c d)
_(CDDR ‘(k l m)) ( (M)
Функция LIST - создает список из элементов. Она возвращает в качестве
своего значения список из значений аргументов. Количество аргументов
произвольно.
_(LIST ‘a ‘b ‘c) ( (a b c)
_(LIST ‘a ‘b (+ 1 2)) ( (a b 3)
4. Символы, свойства символов.
Функции присваивания: SET, SETQ, SETF.
Функция SET - присваивает символу или связывает с ним некоторое
значение. Причем она вычисляет оба своих аргумента. Установленная связь
действительна до конца работы, если этому имени не будет присвоено новое
значение функцией SET.
_(SET ‘a ‘(b c d)) ( (b c d)
_a ((b c d)
_(SET (CAR a) (CDR (o f g)) ( (f g)
_a ( (b c d)
_(CAR a) ( b
_b ( (f g)
Значение символа вычисляется с помощью специальной функции Symbol-
value, которая возвращает в качестве значения значение своего аргумента.
_(Symbol-value (CAR a)) ( (f g)
Функция SETQ - связывает имя, не вычисляя его. Эта функция отличается
от SET тем, что вычисляет только второй аргумент.
_(SETQ d ‘(l m n)) ( (l m n)
Функция SETF - обобщенная функция присваивания. SETF используется для
занесения значения в ячейку памяти.
( SETF ячейка-памяти значение)
_(SETF ячейка ‘(a b c)) ( (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 ‘c ‘n) ( (c n)
(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 ;значение
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 c d)) ( (b c d)
_(RPLACA a ‘d) ( (d c 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)) ‘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 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 x -x) (SETQ рез х))
((= х 0))
(Т ‘ошибка))
Предложение IF.
(IF условие то-форма иначе-форма)
(IF (> x 0) (SETQ y (+ y x)) (SETQ y (- y x)))
Если выполняется условие (т. е. х>0), то к значению y прибавляется
значение х, иначе (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 (i u)) ( (T NIL NIL T)
_(SETQ x ‘(a b c)) ( (a b c)
_(MAPCAR ‘CONS x ‘(1 2 3)) ( ((a . 1) (b . 2) (c . 3))
MAPLIST.
MAPLIST действует подобно MAPCAR, но действия осуществляет не над
элементами списка, а над последовательными CDR этого списка.
_(MAPLIST ‘LIST ‘((f) h k (i u)) ( (T T T T)
_(MAPLIST ‘CONS ‘(a b c) ‘(1 2 3)) ( (((a b c) 1 2 3) ((b c) 2 3) ((c
) 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 c)) ( (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 (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 ‘(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 . c))) ( (b . c)
Любой список можно записать в точечной нотации. Преобразование можно
осуществить (на всех уровнях списка) следующим образом:
(a1 a2 ... an) ( (a1 . (a2 . ...(an . nil)... ))
_(a b c (d e)) ( (a . (b . (c . ((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 . (c . nil)));
((a . nil) . nil);
(nil . (a . nil));
(a . ((b . (c . nil)) . ((d . (e . nil)) . nil)));
(a . (b . ((c . (d . ((e . nil) . (nil))) . nil)));
((a . (b . nil)) . (c . ((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ом.
(cos )
Эта функция возвращает косинус , где - выражается в
радианах. Например:
(cos 0.0) возвращает 1.000000
(cos pi) возвращает -1.000000
(sin )
Эта функция возвращает синус как действительное число, где
выражен в радианах. Например:
(sin 1.0) возвращает 0.841471
(sin 0.0) возвращает 0.000000
(min ...)
Эта функция возвращает наименьшее из заданных .
Каждое может быть действительным или целым.
(nth )
Эта функция возвращает "энный" элемент , где - номер
элемента (ноль - первый элемент). Если больше, чем номер последнего
элемента , возвращается nil. Например:
(nth 3 '(a b c d e)) возвращает D
(nth 0 '(a b c d e)) возвращает A
(nth 5 '(a b c d e)) возвращает nil
(strcat ...)
Эта функция возвращает строку, которая является результатом
сцепления строки1>, и т.д. Например:
(strcat "a" "bout") возвращает "about"
(strcat "a" "b" "c") возвращает "abc"
(strcat "a" "" "c") возвращает "ac"
(strlen )
Эта функция возвращает длину в символах строковой константы
как целую величину. Например:
(stalen "abcd") возвращает 4
(stalen "ab") возвращает 2
(stalen "") возвращает 0
(subst )
Эта функция просматривает в поиске и
возвращает копию с заменой каждого встречного
на . Если не найден в , SUBST
возвращает неизменным. Например, дано:
(setq sample '(a b (c d) b))
тогда:
(subst 'qq 'b sample) возвращает (A QQ (C D) QQ)
(subst 'qq 'z sample) возвращает (A B (C D) B)
(subst 'qq '(c d) sample) возвращает (A B QQ B)
(subst '(qq 'rr) '(c d) sample) возвращает (A B (QQ RR) B)
(subst '(qq 'rr) 'z sample) возвращает (A B (C 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 атома S на атом N
(defun substitute1 (n s l)
(cond ((null l) nil)
((atom (car l))
(cond ((equal1 s (car l))
(cons n (substitute1 n s (cdr l))))
(t (cons (car l) (substitute1 n s (cdr l))))))
(t (cons (substitute1 n s (car l))
(substitute1 n 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. зависящую от одного элемента, которая по данному списку вычисляет
список его элементов:
а) встречающихся в нем более 1, 2, ... раз.
в) встречающихся в нем не менее 2, 3, ... раз.
S. Запишите все функции, написанные вами, в один файл. Для отладки
программы используйте встроенные средства dlispа.
5. Вопросы.
1. Какие способы тестирования программ предусмотрены в dlisp?
2. В чем их различия?
3. Какие функции предусмотрены для работы со строковыми константами в
dlisp?
4. Назовите их основные особенности?