ЛИСП
((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 <число1> <число2>) Функция возвращает наибольший общий делитель <числа1> и <числа2>. <Число1> и <число2> должны быть целыми.
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. Назовите их основные особенности?
Список использованной литературы.
Э. Чювенен, И. Сеппянен
«Мир Лиспа»
Москва «Мир» 1990 г. Т.1
2. Э. Чювенен, И. Сеппянен
«Мир Лиспа»
Москва «Мир» 1990 г. Т.2
«Программирование на языке R-Lisp»
Москва «Радио и связь» 1991 г.
У. Маурер
«Введение в программирование на языке Лисп»
Москва «Мир» 1976 г.
5. П. Уинстон
«Искусственный интеллект»
Москва «Мир» 1980 г.
«Искусственный интеллект применение в интегрированных
производственных системах»
Москва «Машиностроение» 1991 г.
«Искусственный интеллект:
программные и аппаратные средства» Справочник.
Москва «Радио и связь» 1990 г. Т.3
Дж. Малпас
«Реляционный язык Пролог и его применение»
Москва «Наука» 1990 г.
И. Братко
«Программирование на языке Пролог для искусственного интеллекта»
Москва «Мир» 1990 г.
П. Грей
«Логика, алгебра и базы данных»
Москва «Машиностроение» 1983 г.
Л. Н. Преснухин, В. А. Шахнов
«Конструирование электронных вычислительных машин и систем»
Москва «Высшая школа» 1986 г.
«Основы инженерной психологии»
Москва «Высшая школа» 1986 г.
1 Литературный обзор.
- Краткая история развития искусственного интеллекта.
Искусственный интеллект (ИИ) - это область исследований, находящаяся на стыке наук, специалисты, работающие в этой области, пытаются понять, какое поведение, считается разумным (анализ), и создать работающие модели этого поведения (синтез). Практической целью является создание методов и техники, необходимой для программирования «разумности» и ее передачи вычислительным машинам (ВМ), а через них всевозможным системам и средствам.[1]
В 50-х годах исследователи в области ИИ пытались строить разумные машины, имитируя мозг. Эти попытки оказались безуспешными по причине полной непригодности как аппаратных так и программных средств.
В 60-х годах предпринимались попытки отыскать общие методы решения широкого класса задач, моделируя сложный процесс мышления. Разработка универсальных программ оказалась слишком трудным и бесплодным делом. Чем шире класс задач, которые может решать одна программа, тем беднее оказываются ее возможности при решении конкретной проблемы.[5]
В начале 70-х годов специалисты в области ИИ сосредоточили свое внимание на разработке методов и приемов программирования, пригодных для решения более специализированных задач: методов представления (способы формулирования проблемы для решения на средствах вычислительной техники (ВТ)) и методах поиска (способы управления ходом решения так, чтобы оно не требовало слишком большого объема памяти и времени).
И только в конце 70-х годов была принята принципиально новая концепция, которая заключается в том, что для создания интеллектуальной программы ее необходимо снабдить множеством высококачественных специальных знаний о некоторой предметной области. Развитие этого направления привело к созданию экспертных систем (ЭС).[6]
В 80-х годах ИИ пережил второе рождение. Были широко осознаны его большие потенциальные возможности как в исследованиях, так и в развитии производства. В рамках новой технологии появились первые коммерческие программные продукты. В это время стала развиваться область машинного обучения. До этих пор перенесение знаний специалиста-эксперта в машинную программу было утомительной и долгой процедурой. Создание систем, автоматически улучшающих и расширяющих свой запас эвристических (не формальных, основанных на интуитивных соображениях) правил - важнейший этап в последние годы. В начале десятилетия в различных странах были начаты крупнейшие в истории обработки данных национальные и международные исследовательские проекты, нацеленные на «интеллектуальные ВМ пятого поколения».[1]
Исследования по ИИ часто классифицируются, исходя из области их применения, а не на основе различных теорий и школ. В каждой из этих областей на протяжении десятков лет разрабатывались свои методы программирования, формализмы; каждой из них присущи свои традиции, которые могут заметно отличаться от традиций соседней области исследования. В настоящее время ИИ применяется в следующих областях:
обработка естественного языка;
экспертные системы (ЭС);
символьные и алгебраические вычисления;
доказательства и логическое программирование;
программирование игр;
обработка сигналов и распознавание образов;
и др.
1.2 Языки программирования ИИ.
1.2.1 Классификация языков и стилей программирования.
Все языки программирования можно разделить на процедурные и декларативные языки. Подавляющее большинство используемых в настоящее время языков программирования (Си, Паскаль, Бейсик и т. п.) относятся к процедурным языкам. Наиболее существенными классами декларативных языков являются функциональные (Лисп, Лого, АПЛ и т. п.) и логические (Пролог, Плэнер, Конивер и др.) языки (рис.1).
На практике языки программирования не являются чисто процедурными, функциональными или логическими, а содержат в себе черты языков различных типов. На процедурном языке часто можно написать функциональную программу или ее часть и наоборот. Может точнее было бы вместо типа языка говорить о стиле или методе программирования. Естественно различные языки поддерживают разные стили в разной степени.[1]
Процедурная программа состоит из последовательности операторов и предложений, управляющих последовательностью их выполнения. Типичными операторами являются операторы присваивания и передачи управления, операторы ввода-вывода и специальные предложения для организации циклов. Из них можно составлять фрагменты программ и подпрограммы. В основе процедурного программирования лежат взятие значения какой-то переменной, совершение над ним действия и сохранения нового значения с помощью оператора присваивания, и так до тех пор пока не будет получено (и, возможно, напечатано) желаемое окончательное значение.[2]
ЯЗЫКИ
ПРОГРАММИРОВАНИЯ
![]()
![]()
![]()
![]()
![]()
ПРОЦЕДУРНЫЕ
ЯЗЫКИ ДЕКЛАРАТИВНЫЕ
ЯЗЫКИ
Паскаль,
Си, Фортран,
...
![]()
![]()
![]()
ЛОГИЧЕСКИЕ
ЯЗЫКИ ФУНКЦИОНАЛЬНЫЕ
ЯЗЫКИ
Пролог, Mandala... Лисп, Лого, АРЛ, ...
Рис.1 Классификация языков программирования
Логическое программирование - это один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна. Логика предикатов первого порядка - это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений. Логическое программирование базируется на подмножестве логики предикатов первого порядка, при этом оно одинаково широко с ней по сфере охвата. Логическое программирование дает возможность программисту описывать ситуацию при помощи формул логики предикатов, а затем, для выполнения выводов из этих формул, применить автоматический решатель задач (т. е. некоторую процедуру). При использовании языка логического программирования основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать. Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ.[8].
Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает функции, входящие в ее определение и т. д. в соответствии с иерархией определений и структурой условных предложений. Функции часто либо прямо, либо опосредованно вызывают сами себя.[2]
Каждый вызов возвращает некоторое значение в вызывавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор пока запустившая вычисления функция не вернет конечный результат пользователю.
«Чистое» функциональное программирование не признает присваиваний и передач управления. Разветвление вычислений основано на механизме обработки аргументов условного предложения. Повторные вычисления осуществляются через рекурсию, являющуюся основным средством функционального программирования.[1]
- Сравнительные характеристики языков ИИ.
На первом этапе развития ИИ (в конце 50-х - начале 60-х годов) не существовало языков и систем, ориентированных специально на области знаний. Появившиеся к тому времени универсальные языки программирования казались подходящим инструментом для создания любых (в том числе и интеллектуальных ) систем, поскольку в этих языках можно выделить декларативную и процедурную компоненты. Казалось, что на этой базе могут быть интерпретированы любые модели и системы представления знаний. Но сложность и трудоемкость таких интерпретаций оказались настолько велики, что прикладные системы для реализации были недоступны. Исследования показали, что производительность труда программиста остается постоянной независимо от уровня инструментального языка, на котором он работает, а соотношение между длиной исходной и результирующей программ примерно 1:10. Таким образом, использование адекватного инструментального языка повышает производительность труда разработчика системы на порядок, и это при одноступенчатой трансляции. Языки предназначенные для программирования интеллектуальных систем содержат иерархические (многоуровневые) трансляторы и увеличивают производительность труда в 100-ни раз. Все это подтверждает важность использования адекватных инструментальных средств.[7]
- Языки обработки символьной информации.
Лисп.
Язык Лисп был разработан в Стэнфорде под руководством Дж. Маккарти в начале 60-х годов. По первоначальным замыслам он должен был0 включать наряду со всеми возможностями Фортрана средства работы с матрицами, указателями и структурами из указателей и