Файл: Анализ методов современного программирования (Понятие технологии программирования).pdf

Порядок правил

Два синтаксических понятия, несущественные в логических программах, важны при создании программ на Прологе. В каждой процедуре должен быть принят порядок правил, или порядок предложений. Кроме того, в теле каждого предложения должен быть определён порядок целей. Последствия этих решений могут оказаться колоссальными: эффективность программирования на Прологе может измениться в десятки раз. В крайних и тем не менее распространённых случаях корректные логические программы вообще не приведут к решению вследствие не завершающегося вычисления.[30]

Порядок правил определяет порядок поиска решений.

Изменение порядка правил в процедуре приводит к перестановке ветвей в любом дереве поиска цели, использующей данную процедуру. Обход дерева поиска происходит в глубину. Поэтому перестановка ветвей дерева изменяет порядок обхода дерева и порядок нахождения решений. Этот эффект очевиден при использовании фактов для нахождения ответов на экзистенциальный вопрос.

Порядок, в котором находятся ответы на вопросы при работе рекурсивной программы, определяется порядком предложений.

Порядок предложений в программах на общепринятом Прологе важнее, чем порядок предложений в программах на чистом Прологе.[29]

Проблема завершения программ.

Используемый в Прологе принцип обхода дерева в глубину приводит к серьёзным проблемам. Если дерево поиска цели относительно некоторой программы содержит бесконечную ветвь, то вычисление не завершится. Пролог может не найти решение цели, даже если существует конечное вычисление, решающее вопрос.

Бесконечные вычисления появляются при использовании рекурсивных правил. Рекурсивные правила, в которых рекурсивная цель является первой целью в теле правила, называются левыми рекурсивными правилами. Левые рекурсивные правила в Прологе приносят немало хлопот. В случае несоответствующих аргументов использование этих правил приводит к бесконечным вычислениям.[26]

Лучшее решение этой проблемы – отказаться от использования левой рекурсии. В общем случае невозможно избавиться от всех появлений левой рекурсии. Однако соответствующий анализ позволяет определить вопросы, решение которых относительно рекурсивных программ приводит к результату. Другой, не всегда замечаемый случай, который заведомо приводит к не завершающимся вычислениям – это порочный круг. Ввиду порочного круга дерево поиска обязательно содержит бесконечную ветвь.

• Язык логического программирования KL0.

KL0 (от англ. “kernel-language version 0” – ядро-язык версии 0) – язык, в основу которого положено расширение языка логического программирования Пролог. Среди особенностей, новых в KL0 по отношению к Прологу, можно выделить:

• • более гибкую структуру управления.
  • многопроцессовость
  • операции с побочным эффектом
  • машинно-ориентированные операции.

К наиболее существенным механизмам Пролога, не поддерживаемым в KL0, относятся:

• • средства управления базой данных
  • средства управления таблицей имён.

Так как KL0 мало, чем отличается от Пролога, ограничимся лишь рассмотрением типов данных.

К базовым типам языка относятся:

• символы,
• целые и действительные числа
• строки
• др.

Символы в основном предназначены для представления символьных атомов Пролога и, как правило, никак не связаны ни со строками символов, используемыми для текстуального представления программ, ни с определениями предикатов, в которых символы задают имена предикатов. Такие атрибуты при необходимости могут быть приписаны символам средствами ESP[1] . KL0 более прост и не поддерживает подобных механизмов. В этом отношении он только обеспечивает структуры данных прямого доступа и стандартную функцию хеширования для доступа к определениям атрибутов в хеш-таблице. Символы в KL0 можно проверять только на идентичность.[30]

Целые и действительные числа введены для эффективного выполнения арифметических операций. Арифметические операции в KL0 не обладают свойством двойственности: сложение и вычитание, здесь различные предикаты. Аппаратно поддерживаются только числа фиксированной длины, определяемой разрядной сеткой. Целые числа произвольной длины (bignums), действительные числа произвольной точности и, возможно, рациональные числа могут быть реализованы с помощью обработчика исключений. Исключение возбуждается, если операндами встроенных арифметических предикатов (машинных инструкций в традиционном смысле) являются, например, нечисловые данные. Обработчик исключения может проверить аргументы и, если они соответствуют ожидаемым, выполнить предписанные операции; в противном случае вызывается обработчик ошибок. После обработки исключения дальнейшее выполнение программы может быть возобновлено.[32]

Выводы по 4 части.

• Логическое программирование хорошо подходит для решения проблем, для работы с формальными и естественными языками, для баз данных, запросных и экспертных систем и для других дискретных не вычислительных задач. Пользователя привлекает ясность, содержательность программ и их нетехнический характер. В программе не нужно описывать, каким образом решается задача. Достаточно описания самой задачи и того, что желательно узнать.
• Однако логическое программирование с использованием лишь хорновских предложений было бы слишком узконаправленным. Поэтому, кроме этого, используются другие методы программирования. Некоторые задачи по своему характеру процедурные, и программировать их чисто декларативными языками непрактично. Нужны более развитые типы данных. Пролог и логическое программирование непрерывно расширяются, охватывая все новые методы программирования и формы изображения именно в направлении процедурного и объектно-ориентированного программирования, а также в направлении параллельных вычислений.

4.5. Функциональное программирование

Функциональным называется программирование при помощи функций в математическом их понимании. Функциональное программирование основано на следующей идее: в результате каждого действия возникает значение, которое может быть аргументом следующего действия. Программы строятся из логически расчлененных определений функций. Каждое определение функции состоит из организующих вычисления управляющих структур и из вложенных, в том числе вызывающих самих себя (рекурсивных) вызовов функций.

Язык LISP (LISt Processing) – язык программирования высокого уровня, разработан в 1961 году Дж. Маккарти. В основе Лиспа лежит функциональная модель вычислений, ориентированная прежде всего на решение задач нечислового характера.[31]

Основы функционального программирования:

• Вызов функций является единственной разновидностью действий,

выполняемых в функциональной программе,

• В алгоритмических языках программа является последовательностью операторов, вызовов процедур в соответствии с алгоритмом. В функциональном программировании программа состоит из вызовов функций (рис. 14) и описывает то, что нужно делать и что собой представляет результат решения, а не как нужно действовать для получения результата.

Рис.14 Структура функциональной программы.

• Основными методами программирования являются суперпозиция функций и рекурсия.
• В алгоритмических языках с именем переменной связана некоторая область памяти, соответствие строго сохраняется в течение всего времени выполнения программы. В функциональном программировании переменная обозначает только имя некоторой структуры, имена символов, переменных, списков, функций и других объектов не закреплены предварительно за какими-либо типами данных. В ФП одна и та же переменная в различные моменты времени может представлять различные объекты.[32]
• В языках функционального программирования программа и обрабатываемые ею данные имеют единую списочную форму представления.
• Функциональное программирование предполагает наличие функционалов – функций, аргументы и результаты которых могут быть функциями. Всякий язык функционального программирования предполагает наличие ядра, называемого строго функциональным языком.

Требования к функциональному языку

• Всякая функция должна однозначно определять результат по любому набору аргументов.
• Отсутствует оператор присваивания.
• Переменная обозначает только имя структуры. 4. В языке присутствуют функционалы.

Применение языков функционального программирования.

• Системы автоматизированного проектирования.
• Программирование игр.
• Математическая лингвистика.
• Реализация ленивых вычислений.[33]

Выводы по 5 части.

Основные преимущества языков функционального программирования:

• Краткость программы.
• Функциональные программы поддаются формальному анализу легче своих аналогов на алгоритмических языках за счет использования математической функции в качестве основной конструкции.
• Возможность реализации с параллельной архитектурой

Заключение

Анализ рассмотренных методов систематического и теоретического программирования показывает постоянное их развитие, совершенствование, пополнение новыми возможностями и возможностью объединения. Классическим примером объединения является язык UML, в результате объектно-ориентированное программирование обогатилось новыми возможностями, которые удовлетворили многих пользователей визуальным и наглядным моделированием программных систем на основе разнообразных диаграмм. Каждый метод программирования может развиваться как самостоятельно, так и в сообществе с другими. Как считают многие специалисты в области информатики, перспективными среди рассмотренных методов программирования являются методы модульного и ориентированного программирования.

Список использованной литературы

1. Хомский Н. Аспекты теории синтаксиса. – МГУ, 2006.
2. Гладкий А.В. Формальные грамматики и языки. – М.: Наука, 1973.
3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. – М.: Мир, 2008.
4. Агальцев В.П. Информатика для экономистов: учебник / В.П. агальцев В.М. Титов. – М.: Форум, Инфра-М, 2011. – 448 с.
5. Информатика: учебник / Под ред. проф. Н.В. Макаровой – 3-е изд. – М.: Финансы и статистика, 2000. – 768 с.
6. Волков В.Б. Информатика: учеб. для вузов /В.Б. Волков Н.В. Макарова. – СПб.: Питер, 2011. – 576 с.
7. Гагарина Л.Г. Технология разработки программного обеспечения / Л.Г. ГагаринаЕ.В. КокореваБ.Д. Виснадул. – М.: Форум, Инфра-М, 2007. – 400 с.
8. Жоголев Е.А. Технология программирования / Е.А. Жоголев. – М.: Научный мир, 2004. – 216 с.
9. Иванова Г.С. Технология программирования: учебник / Г.С. Иванова. - 2-е изд. - М.: МГТУ им. Н.Э. Баумана, 2002. – 416 с.
10. Информатика: Базовый курс: учеб. для вузов / под ред. С.В. Симоновича. – 3-е изд. – СПб.: Питер, 2011. – 640 с.
11. Информатика: учебник / Соболь Б.В. [и др.] -3-е изд., доп. и перераб. - Ростов н/Д: Феникс, 2007. — 446 с.
12. Меняев М.Ф. Информатика и основы программирования: учеб. пособие / М.Ф. Меняев. – 3-е изд.стер. – М.: Омега-Л, 2007. – 458 с.
13. Методы программирования: учеб. пособие / Н.И. Минаков [и др.] -2-е изд. – М.: Вузовская книга, 2000. – 280 с.
14. Окулов С.М. Основы программирования / С.М. Окулов. – М.: ЮНИМЕДИАСТАЙЛ, 2002. – 424 с.
15. Фельдман С.Системное программирование на персональном компьютере / С. Фельдман.– 2-е изд. – М.: Новый издательский дом, 2004. – 512 с.
16. Шелест В. Д. Программирование: учеб. пособие / В. Д. Шелест. – СПб.: БХВ-Петербург, 2002. – 592 с.
17. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. –