Декларативное программирование
Непроцедурное (декларативное) программирование появилось в начале 70-х годов 20 века, но стремительное его развитие началось в 80-е годы, когда был разработан японский проект создания ЭВМ пятого поколения, целью которого явилась подготовка почвы для создания интеллектуальных машин.
При использовании декларативного языка программист указывает исходные информационные структуры, взаимосвязи между ними и то, какими свойствами должен обладать результат. При этом процедуру его получения («алгоритм») программист не строит (по крайней мере, в идеале). Особое внимание в декларативном программировании уделяется тому, что нужно сделать, а не тому, как это нужно сделать. В этих языках отсутствует понятие «оператор» («команда»).
Декларативное программирование можно подразделить на два семейства – функциональное (Лисп) и логическое (типичный представитель – Пролог).
Функциональное программирование
Функциональное программирование не использует концепцию памяти как хранилища значений переменных. Операторы присваивания отсутствуют, вследствие чего переменные обозначают не области памяти, а объекты программы. В принципе, можно составлять программы и вообще без переменных. Кроме того, нет существенных различий между константами и функциями, то есть между программами и данными. В результате этого функция может быть значением вызова другой функции и может быть элементом структурированного объекта. При этом функции часто либо прямо, либо опосредованно вызывают сами себя (рекурсия). Число аргументов при вызове функции не обязательно должно совпадать с числом параметров, указанных при ее описании.
Каждая функция возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока начавшая процесс вычислений функция не вернет конечный результат пользователю.
Отсутствие оператора присваивания делает переменные, используемые в функциональных языках программирования, очень похожими на переменные в математике - получив однажды свои значения, они больше никогда их не меняют. Отсутствие побочных эффектов в процессе вычисления функций приводит к тому, что порядок выполнения отдельных фрагментов программы не существенен - итоговое значение в любом случае будет одинаковым.
Для успешного овладения данным стилем программирования, необходимо весьма глубокое понимание многих разделов математики.
Логическоепрограммирование
Центральным понятием в логическом программировании является отношение. Программа представляет собой совокупность определений отношений между объектами (в терминах условий или ограничений) и цели (запроса). Процесс выполнения программы трактуется как процесс общезначимости логической формулы, построенной из программы по правилам, установленным семантикой используемого языка. Результат вычисления является побочным продуктом этого процесса. В логическом программировании нужно только специфицировать факты, на которых алгоритм основывается, а не определять последовательность шагов, которые требуется выполнить.
В этом программировании программа представляет собой не набор команд и инструкций, а описание абстрактной модели решаемой задачи в виде логических аксиом. Формулируются сведения о задаче и предположения, достаточные для её решения.
Программа выполняется путем постановки задачи, описанной в виде задачи проверки целевого логического утверждения (вопроса). Выполнение программы состоит в попытке доказать целевое утверждение, используя сформулированные предположения (аксиомы и способы их преобразования).
Пролог - это наиболее известный язык логического программирования. Этот язык (наряду с функциональным языком Lisp) часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков.
При выборе языка программирования пользователь должен учитывать, что описание алгоритма решаемой задачи можно выполнить на любом алгоритмическом языке в силу его универсальности. Однако изобразительные средства языков очень сильно отличаются, и задача выбора заключается в том, чтобы выбранный язык наилучшим образом соответствовал требуемым процедурам обработки данных в задании пользователя.
Лекция 13
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
1 Определение алгоритма и понятие его исполнителя
2 Классы моделей алгоритмов
3 Формы записи алгоритмов