В информатике декларативное программирование — это парадигма программирования — стиль построения структуры и элементов компьютерных программ , — которая выражает логику вычисления без описания его потока управления . [1]
Многие языки, применяющие этот стиль, пытаются минимизировать или устранить побочные эффекты , описывая то, что программа должна выполнить в терминах проблемной области , а не описывая, как это выполнить, как последовательность примитивов языка программирования [2] ( как остается на усмотрение реализации языка ). Это контрастирует с императивным программированием , которое реализует алгоритмы явными шагами. [3] [4]
Декларативное программирование часто рассматривает программы как теории формальной логики , а вычисления как выводы в этом логическом пространстве. Декларативное программирование может значительно упростить написание параллельных программ . [5]
К распространенным декларативным языкам относятся языки запросов к базам данных (например, SQL , XQuery ), регулярные выражения , логическое программирование (например, Prolog , Datalog , программирование наборов ответов ), функциональное программирование , управление конфигурацией и системы алгебраического моделирования .
Декларативное программирование часто определяется как любой стиль программирования, который не является императивным. Ряд других распространенных определений пытаются определить его, просто противопоставляя его императивному программированию. Например:
Эти определения во многом пересекаются.
Декларативное программирование — это неимперативный стиль программирования, в котором программы описывают желаемые результаты без явного перечисления команд или шагов, которые должны быть выполнены. Функциональные и логические языки программирования характеризуются декларативным стилем программирования. В логическом программировании программы состоят из предложений, выраженных в логической форме, а вычисления используют эти предложения для решения задач, которые также выражены в логической форме.
В чисто функциональном языке , таком как Haskell , все функции не имеют побочных эффектов , а изменения состояния представлены только как функции, преобразующие состояние, которое явно представлено как объект первого класса в программе. Хотя чисто функциональные языки не являются императивными, они часто предоставляют возможность описывать эффект функции как последовательность шагов. Другие функциональные языки, такие как Lisp , OCaml и Erlang , поддерживают смесь процедурного и функционального программирования.
Некоторые языки логического программирования, такие как Prolog , и языки запросов к базам данных, такие как SQL, хотя и являются декларативными по своей сути, также поддерживают процедурный стиль программирования.
Декларативное программирование — это обобщающий термин , включающий в себя ряд наиболее известных парадигм программирования .
Программирование в ограничениях устанавливает отношения между переменными в форме ограничений, которые определяют свойства целевого решения. Набор ограничений решается путем присвоения значения каждой переменной, чтобы решение соответствовало максимальному количеству ограничений. Программирование в ограничениях часто дополняет другие парадигмы: функциональное, логическое или даже императивное программирование.
Известные примеры декларативных предметно-ориентированных языков (DSL) включают в себя язык ввода генератора парсеров yacc , QML , язык спецификации сборки Make , язык управления конфигурацией Puppet, регулярные выражения , Datalog , программирование наборов ответов и подмножество SQL (например, запросы SELECT). DSL имеют то преимущество, что они полезны, не обязательно должны быть полными по Тьюрингу , что упрощает для языка возможность быть чисто декларативным.
Многие языки разметки, такие как HTML , MXML , XAML , XSLT или другие языки разметки пользовательского интерфейса, часто являются декларативными. HTML, например, описывает только то, что должно отображаться на веб-странице — он не определяет ни поток управления для рендеринга страницы, ни возможные взаимодействия страницы с пользователем .
По состоянию на 2013 год [update]некоторые программные системы [ которые? ] объединяют традиционные языки разметки пользовательского интерфейса (такие как HTML) с декларативной разметкой, которая определяет, что (но не как) должны делать внутренние серверные системы для поддержки заявленного интерфейса. Такие системы, как правило, использующие доменно-специфическое пространство имен XML , могут включать абстракции синтаксиса базы данных SQL или параметризованные вызовы веб-сервисов с использованием передачи репрезентативного состояния (REST) и SOAP . [ необходима цитата ]
Функциональные языки программирования, такие как Haskell , Scheme и ML, оценивают выражения через применение функций. В отличие от связанной, но более императивной парадигмы процедурного программирования , функциональное программирование уделяет мало внимания явному упорядочиванию. Вместо этого вычисления характеризуются различными видами рекурсивного применения и композиции функций высшего порядка , и как таковые могут рассматриваться просто как набор отображений между доменами и кодоменами . Многие функциональные языки, включая большинство языков семейств ML и Lisp, не являются чисто функциональными и, таким образом, позволяют вводить в программы эффекты с сохранением состояния .
Например, файлы Makefiles определяют зависимости декларативным образом, [7] , но также включают императивный список действий, которые необходимо предпринять. Аналогично, yacc определяет контекстно-свободную грамматику декларативно, но включает фрагменты кода из языка-хоста, который обычно является императивным (например, C ).
Языки логического программирования, такие как Prolog , Datalog и программирование набора ответов , выполняют вычисления, доказывая, что цель является логическим следствием программы, или показывая, что цель истинна в модели, определенной программой. Prolog выполняет вычисления, сводя цели к подцелям, сверху вниз, используя обратные рассуждения , тогда как большинство систем Datalog выполняют вычисления снизу вверх, используя прямые рассуждения . Программы набора ответов обычно используют решатели SAT для генерации модели программы.
Модели или математические представления физических систем могут быть реализованы в компьютерном коде, который является декларативным. Код содержит ряд уравнений, а не императивных назначений, которые описывают («декларируют») поведенческие отношения. Когда модель выражается в этом формализме, компьютер способен выполнять алгебраические манипуляции, чтобы наилучшим образом сформулировать алгоритм решения. Математическая причинность обычно накладывается на границы физической системы, в то время как поведенческое описание самой системы является декларативным или акаузальным. Декларативные языки моделирования и среды включают Analytica , Modelica и Simile. [8]
Lisp — это семейство языков программирования, в основе которого лежат математические обозначения и лямбда-исчисление Алонзо Чёрча . Некоторые диалекты, такие как Common Lisp , в первую очередь императивные, но поддерживают функциональное программирование. Другие, такие как Scheme , предназначены для функционального программирования.
В Схеме факториальную функцию можно определить следующим образом:
( определить ( факториал n ) ( если ( = n 0 ) 1 ;;; 0! = 1 ( * n ( факториал ( - n 1 ))))) ;;; n! = n*(n-1)! Это определяет функцию факториала, используя ее рекурсивное определение. Напротив, более типично определять процедуру для императивного языка.
В lisp и лямбда-исчислении функции обычно являются гражданами первого класса . Грубо говоря, это означает, что функции могут быть входами и выходами для других функций. Это может упростить определение некоторых функций.
Например, написать функцию для вывода первых n квадратных чисел в Racket можно следующим образом:
( define ( first-n-squares n ) ( map ( lambda ( x ) ( * x x )) ;;; Функция, отображающая x -> x^2 ( range n ))) ;;; Список первых n неотрицательных целых чисел Функция map принимает функцию и список; на выходе получается список результатов функции ввода для каждого элемента списка ввода.
ML (1973) [9] означает «Meta Language». ML является статически типизированным, а аргументы функций и возвращаемые типы могут быть аннотированы. [10]
развлечение_10 ( n : int ) : int = 10 * n ; ML не так сильно ориентирован на скобки, как Lisp , и вместо этого использует более широкий спектр синтаксиса для кодификации отношений между элементами кода, а не апеллирует к упорядочиванию списков и вложенности для выражения всего. Ниже приведен пример применения times_10:
раз_10 2
Возвращает «20 : int», то есть 20значение типа int.
Как и Lisp , ML предназначен для обработки списков, хотя все элементы списка должны быть одного типа. [11]
Prolog (1972) означает «PROprogramming in LOGic». Он был разработан для ответов на вопросы на естественном языке [12] с использованием разрешения SL [13] как для вывода ответов на запросы, так и для анализа и генерации предложений на естественном языке.
Строительными блоками программы Prolog являются факты и правила . Вот простой пример:
кот ( том ). % том — кот, мышь ( джерри ) . % джерри — мышьживотное ( X ) :- кошка ( X ). % каждая кошка является животным животное ( X ) :- мышь ( X ). % каждая мышь является животнымбольшой ( X ) :- кот ( X ). % каждый кот большой маленький ( X ) :- мышь ( X ). % каждая мышь маленькаяешьте ( X , Y ) :- мышь ( X ), сыр ( Y ). % каждая мышь ест каждый сыр ешьте ( X , Y ) :- большой ( X ), маленький ( Y ). % каждое большое существо ест каждое маленькое существоПри наличии этой программы запрос выполняется успешно, а не выполняется. Более того, запрос выполняется успешно с заменой ответа .eat(tom,jerry)eat(jerry,tom)eat(X,jerry)X=tom
Prolog выполняет программы сверху вниз, используя разрешение SLD для рассуждений в обратном порядке , сводя цели к подцелям. В этом примере он использует последнее правило программы, чтобы свести цель ответа на запрос к подцелям сначала найти X, такой что выполняется, а затем показать, что выполняется. Он многократно использует правила для дальнейшего сведения подцелей к другим подцелям, пока в конечном итоге не преуспеет в объединении всех подцелей с фактами в программе. Эта стратегия обратного рассуждения и сведения цели рассматривает правила в логических программах как процедуры и делает Prolog как декларативным, так и процедурным языком программирования . [14]eat(X,jerry)big(X)small(jerry)
Широкий спектр приложений Prolog освещается в книге «Год Prolog» [15] , посвященной 50-летию Prolog.
Истоки Datalog восходят к началу логического программирования, но он был идентифицирован как отдельная область около 1977 года. Синтаксически и семантически он является подмножеством Prolog. Но поскольку он не имеет составных терминов , он не является полным по Тьюрингу .
Большинство систем Datalog выполняют программы снизу вверх, используя правила для рассуждений вперед , выводя новые факты из существующих фактов и завершая работу, когда нет новых фактов, которые можно вывести, или когда выведенные факты унифицируются с запросом. В приведенном выше примере типичная система Datalog сначала выводит новые факты:
животное ( том ). животное ( джерри ). большой ( том ). маленький ( джерри ).Используя эти факты, он затем выведет дополнительный факт:
ест ( том , джерри ).Затем он будет завершен, как потому, что не может быть получено никаких новых дополнительных фактов, так и потому, что вновь полученный факт объединяется с запросом.
ест ( X , Джерри ).Datalog применяется к таким проблемам, как интеграция данных , извлечение информации , сетевое взаимодействие , безопасность , облачные вычисления и машинное обучение . [16] [17]
Программирование набора ответов (ASP) развилось в конце 1990-х годов на основе стабильной модели (набора ответов) семантики логического программирования. Как и Datalog, это подмножество Prolog; и, поскольку в нем нет составных терминов, он не является полным по Тьюрингу.
Большинство реализаций ASP выполняют программу, сначала «заземляя» ее, заменяя все переменные в правилах константами всеми возможными способами, а затем используя пропозициональный решатель SAT, такой как алгоритм DPLL , для генерации одной или нескольких моделей программы.
Его приложения ориентированы на решение сложных задач поиска и представления знаний . [18] [19]
этом контексте критерием для обозначения языка программирования как декларативного является существование четкого, математически установленного соответствия между языком и математической логикой, такого, что декларативная семантика для языка может быть основана на модели или теории доказательств (или на обеих) логики.