В в е д е н и е
Дисциплина "Логическое и функциональное программирование" входит в группу дисциплин углубленной подготовки в программировании студентов направления "Компьютерная инженерия", проводимой на кафедре Информационных и компьютерных систем. Эта дисциплина вводит качественно новые подходы и инструменты решения задач обработки сложных структур данных, поиска и логического вывода. Ее концепции базируются на результатах теоретической подготовки в фундаментальных разделах математической логики – исчисление предикатов и l - исчисление, а ее инструменты являются основой создания современных систем искусственного интеллекта и принятия решений.
Опыт изучения дисциплин "Программирование", "Алгоритмы и структуры данных" и "Дискретная математика", а также опыт выполнения курсовых проектов по дисциплинам "Программирование" и "Дискретная математика" позволяет сделать вывод о важности задач представления и обработки сложных списковых структур данных, задач поиска и логического вывода. В качестве основного инструмента программирования в этих дисциплинах использовались языки программирования типа Паскаль и Си.
Современные универсальные языки программирования типа Паскаль и Си имеют необходимые средства для решения таких задач, однако использование этих средств требует от программиста высокой квалификации, искусного программирования и значительных затрат времени. При этом логическая суть таких задач уходит на второй план, скрываясь за наборами процедур, параметров и вызовов. Это затрудняет понимание и отображение логики решаемых задач и ее оперативной модификации при изменении внешних условий, а программист сосредотачивается не на логике задач, а на трудоемком манипулировании средствами конкретного универсального языка программирования.
С другой стороны, бурное развитие информатики и ее проникновение во все более сложные сферы человеческой деятельности ставит перед программистами качественно новые логические задачи вплоть до задач создания сложноассоцируемых баз данных и знаний, систем принятия решений в условиях неопределенности и искусственного интеллекта. Решение этих задач средствами универсальных языков программирования в силу указанных причин оказывается малопродуктивным. Поэтому естественным было бы ожидать создание таких средств программирования, которые позволили бы вынести на передний план именно логическую и структурную суть задачи и, практически, избавили бы программиста от процедурного программирования действий компьютера по решению этих задач. Фактически речь идет о создании средств, обеспечивающих дальнейшее повышение уровня абстракции компьютера, когда задача формулируется в терминах конкретной проблемной области, а не в терминах аппаратных возможностей компьютера или универсального языка программирования. Это позволяет качественно расширить круг задач и круг специалистов, способных качественно решать указанные задачи и в сжатые сроки.
Ответом на возникшую проблему явилось появление двух качественно отличных систем программирования – системы функционального программирования Лисп и системы логического программирования Пролог. Исторически эти системы появились в разное время и отражают разные подходы к решению логических задач, задач поиска и построения динамических структур данных.
Система программирования Лисп - первая система высокоуровневого программирования логических задач. Она является ровесницей исторически первой системы автоматического программирования инженерных задач Фортран, которая успешно существует до настоящего времени.
Система программирования Лисп ориентирована на списковое представление сложных структур данных и связей между ними, а решение логических задач в этой системе сводится к навигации по соответствующей списковой структуре. Именно концепции системы Лисп оказали значительное влияние на развитие универсальных языков программирования в плане их расширения средствами по обработке списковых структур данных.
Система программирования Пролог появилась значительно позже и отражала математические подходы к решению задач представления данных и связей между ними с помощью отношений (предикатов) и проведения с помощью единообразных процедур логического вывода на этих данных и связях.
На сегодня системы программирования Лисп и Пролог переживают бурное развитие и получили большое распространение в наиболее развитых странах в таких областях как решение сложных логических задач управления летательными аппаратами, электротехническими системами, высокотехнологическими производствами и т.п. Эти системы программирования являются основным инструментом создания современных систем искусственного интеллекта, используемых при диагностике заболеваний, синтезе лекарственных препаратов, поиске полезных ископаемых и т.д. На их основе созданы оболочки для построения различных экспертных систем.
Реализации систем программирования Лисп и Пролог имеются практически для всех современных программных и аппаратных платформ. В последнее время эти систем программирования получили значительное развитие в плане построения серверных приложений и программирования баз данных и Интернет.
К сожалению в нашей стране системы программирования Лисп и Пролог долгое время не получали должного распространения, что вызвано длительным отсутствием развитого спектра задач, ориентированных на создание баз знаний, экспертных систем, систем принятия решений в условиях неопределенности и систем искусственного интеллекта. Однако интеграция Украины в международные работы по информатике и необходимость успешно конкурировать на этом рынке, а также необходимость инновационного обновления производства, систем управления и принятия решений в нашей стране ставит задачу глубокого освоения специалистами компьютерной инженерии методов и средств решения логических задач в средах Лисп и Пролог.
Методические указания “Логическое и функциональное программирование” предназначены для подготовки и выполнения лабораторных работ по дисциплине «Логическое и функциональное программирование» студентами направления 6.0915 "Компьютерная инженерия". Материал указаний полезен при подготовке к лекционным занятиям и выполнении расчетно-графических работ по указанной дисциплине.
Содержание методических указаний соответствует программе курса «Логическое и функционально программирование», разработанной кафедрой Информационных и компьютерных систем в рамках общего цикла дисциплин углубленной подготовки специалистов в программировании и в области искусственного интеллекта. Большое внимание уделено рассмотрению таких важных вопросов как: рекурсивные и итерационные алгоритмы, представление и обработка сложноассоциативных структур данных, методы поиска в пространствах состояний и методы логического вывода.
Важным достоинством предлагаемого материала является наличие сравнительного анализа реализации конкретных алгоритмов средствами универсального языка программирования Паскаль и языков логического и функционального программирования Пролог и Лисп.
Материал методических указаний служит хорошим подспорьем для закрепления знаний, полученных студентами в курсах "Программирование", "Алгоритмы и структуры данных" и "Дискретная математика". Глубокое усвоение представленного материала служат основой успешного изучения курсов "Модели и структуры данных", "Организация баз данных", "Экспертные системы" и "Моделирование знаний и искусственный интеллект", которые вместе с указанным курсом являются составными частями подготовки специалистов в программировании, обработке данных и искусственном интеллекте.
Лабораторная работа №1
Знакомство с языком логического программирования Пролог