Декларативное программирование
 | В данной статье поднимается несколько вопросов. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В информатике декларативное программирование — это парадигма программирования — стиль построения структуры и элементов компьютерных программ, — который выражает логику вычислений без описания потока управления . [1]
Многие языки, применяющие этот стиль, пытаются минимизировать или устранить побочные эффекты, описывая то, что программа должна выполнить, в терминах проблемной области , а не описывая, как это выполнить, в виде последовательности примитивов языка программирования. [2] ( как это языка остается на усмотрение реализации ). Это контрастирует с императивным программированием , которое реализует алгоритмы в виде явных шагов. [3] [4]
Декларативное программирование часто рассматривает программы как теории формальной логики , а вычисления — как выводы в этом логическом пространстве. Декларативное программирование может значительно упростить написание параллельных программ . [5]
Общие декларативные языки включают языки запросов к базам данных (например, SQL , XQuery ), регулярные выражения , логическое программирование (например, Prolog , Datalog , программирование набора ответов ), функциональное программирование , управление конфигурацией и алгебраического моделирования системы .
Определение [ править ]
Декларативное программирование часто определяют как любой стиль программирования, который не является обязательным. Ряд других распространенных определений пытаются определить его, просто противопоставляя его императивному программированию. Например:
- Программа высокого уровня, описывающая, какие вычисления должны выполняться.
- Любой язык программирования, в котором отсутствуют побочные эффекты (или, точнее, является ссылочно прозрачным ).
- Язык с четким соответствием математической логике . [6]
Эти определения существенно пересекаются.
Декларативное программирование — это неимперативный стиль программирования, при котором программы описывают желаемые результаты без явного перечисления команд или шагов, которые необходимо выполнить. Функциональные и логические языки программирования характеризуются декларативным стилем программирования. В логическом программировании программы состоят из предложений, выраженных в логической форме, и вычисления используют эти предложения для решения задач, которые также выражены в логической форме.
В чисто функциональном языке , таком как Haskell , все функции не имеют побочных эффектов , а изменения состояния представляются только как функции, преобразующие состояние, которое явно представлено как первоклассный в программе объект. Хотя чистые функциональные языки не являются обязательными, они часто предоставляют возможность описать эффект функции в виде серии шагов. Другие функциональные языки, такие как Lisp , OCaml и Erlang , поддерживают смесь процедурного и функционального программирования.
Некоторые языки логического программирования, такие как Пролог , и языки запросов к базам данных, такие как SQL, хотя и являются в принципе декларативными, также поддерживают процедурный стиль программирования.
Субпарадигмы [ править ]
Декларативное программирование — это общий термин , включающий ряд более известных парадигм программирования .
Программирование ограничений [ править ]
Программирование с ограничениями устанавливает отношения между переменными в форме ограничений, которые определяют свойства целевого решения. Набор ограничений решается путем присвоения значения каждой переменной, чтобы решение соответствовало максимальному количеству ограничений. Программирование с ограничениями часто дополняет другие парадигмы: функциональное, логическое или даже императивное программирование.
Языки, специфичные для предметной области [ править ]
Хорошо известные примеры декларативных предметно-ориентированных языков (DSL) включают язык ввода генератора синтаксического анализатора yacc , QML , язык спецификации сборки Make , Puppet язык управления конфигурацией , регулярные выражения , журнал данных , программирование набора ответов и подмножество SQL ( например, запросы SELECT). Преимущество DSL заключается в том, что они полезны, но не обязательно должны быть полными по Тьюрингу , что позволяет языку быть чисто декларативным.
Многие языки разметки, такие как HTML , MXML , XAML , XSLT или другие языки разметки пользовательского интерфейса, часто являются декларативными. HTML, например, описывает только то, что должно отображаться на веб-странице — он не определяет ни поток управления для отрисовки страницы, ни возможные взаимодействия страницы с пользователем .
По состоянию на 2013 год [update], некоторые программные системы [ который? ] объединить традиционные языки разметки пользовательского интерфейса (такие как HTML) с декларативной разметкой, которая определяет, что (но не как) должны делать серверные системы для поддержки объявленного интерфейса. , специфичное для предметной области Такие системы, обычно использующие пространство имен XML , могут включать абстракции синтаксиса базы данных SQL или параметризованные вызовы веб-служб с использованием передачи репрезентативного состояния (REST) и SOAP . [ нужна цитата ]
Функциональное программирование [ править ]
Языки функционального программирования, такие как Haskell , Scheme и ML, оценивают выражения через приложение-функцию. В отличие от родственной, но более императивной парадигмы процедурного программирования , функциональное программирование уделяет мало внимания явному упорядочению. Вместо этого вычисления характеризуются различными видами рекурсивного функций высшего порядка применения и композиции и поэтому могут рассматриваться просто как набор отображений между доменами и кодоменами . Многие функциональные языки, в том числе большинство из семейств ML и Lisp, не являются чисто функциональными и, таким образом, допускают введение эффектов с сохранением состояния в программы .
Гибридные языки [ править ]
Например, файлы Makefile определяют зависимости декларативным образом. [7] но также включите обязательный список действий, которые необходимо предпринять. Аналогично, yacc декларативно определяет контекстно-свободную грамматику, но включает фрагменты кода с основного языка, что обычно является обязательным (например, C ).
Логическое программирование [ править ]
Языки логического программирования, такие как Пролог , Журнал данных и программирование набора ответов , выполняют вычисления, доказывая, что цель является логическим следствием программы, или показывая, что цель верна в модели, определенной программой. Пролог выполняет вычисления, сводя цели к подцелям, сверху вниз, используя обратное рассуждение , тогда как большинство систем Datalog выполняют вычисления снизу вверх, используя прямое рассуждение . Программы набора ответов обычно используют решатели SAT для создания модели программы.
Моделирование [ править ]
Модели или математические представления физических систем могут быть реализованы в декларативном компьютерном коде. Код содержит ряд уравнений, а не императивных присваиваний, которые описывают («декларируют») поведенческие отношения. Когда модель выражается в этом формализме, компьютер может выполнять алгебраические манипуляции, чтобы лучше сформулировать алгоритм решения. Математическая причинность обычно накладывается на границы физической системы, тогда как поведенческое описание самой системы является декларативным или акаузальным. декларативного моделирования Языки и среды включают Analytica , Modelica и Simile . [8]
Примеры [ править ]
Лисп [ править ]
Lisp — это семейство языков программирования, вдохновленное математической записью и Алонзо Чёрча лямбда-исчислением . Некоторые диалекты, такие как Common Lisp , в первую очередь обязательны, но поддерживают функциональное программирование. Другие, такие как Scheme , предназначены для функционального программирования.
В Scheme функцию факториала можно определить следующим образом:
( define ( факториал n )
( if ( = n 0 )
1 ;;; 0! = 1
( * n ( факториал ( - n 1 ))))) ;;; н! = n*(n-1)!
Это определяет функцию факториала, используя ее рекурсивное определение. Напротив, более типично определять процедуру для императивного языка.
В лиспе и лямбда-исчислении функции обычно являются первоклассными гражданами . В общих чертах это означает, что функции могут быть входными и выходными данными для других функций. Это может упростить определение некоторых функций.
Например, написать функцию для вывода первых n квадратных чисел в Racket можно следующим образом:
( define ( first-n-squares n )
( map
( лямбда ( x ) ( * x x )) ;;; Функция, отображающая x -> x^2
( диапазон n ))) ;;; Список первых n неотрицательных целых чисел
Функция карты принимает функцию и список; выходные данные представляют собой список результатов входной функции для каждого элемента входного списка.
МЛ [ править ]
МЛ (1973) [9] означает «Метаязык». ML статически типизирован, а аргументы функций и возвращаемые типы могут быть аннотированы. [10]
fun times_10 ( n : int ) : int = 10 * n ;
ML не так ориентирован на скобки, как Lisp , и вместо этого использует более широкий спектр синтаксиса для кодификации отношений между элементами кода, а не обращается к упорядочиванию списков и вложенности для выражения всего. Ниже приводится применение times_10:
раз_10 2
Он возвращает «20 : int», то есть 20, значение типа int.
Как и Lisp , ML адаптирован для списков процессов, хотя все элементы списка должны быть одного типа. [11]
Пролог [ править ]
Пролог (1972) означает «Программирование в ЛОГИКЕ». Он был разработан для ответов на вопросы на естественном языке , [12] с использованием разрешения SL [13] как для получения ответов на запросы, так и для анализа и генерации предложений на естественном языке.
Строительными блоками программы на Прологе являются факты и правила . Вот простой пример:
кот ( Том ). % Том — кот-мышь
( Джерри ) . % Джерри —
животное -мышь ( 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.
Пролог выполняет программы сверху вниз, используя разрешение SLD для обратного рассуждения , сводя цели к подцелям. В этом примере используется последнее правило программы, чтобы уменьшить цель ответа на запрос. eat(X,jerry) к подцелям сначала найти X такое, что big(X) держится, а затем показать, что small(jerry)держит. Он неоднократно использует правила для дальнейшего сведения подцелей к другим подцелям, пока в конечном итоге не достигнет успеха в объединении всех подцелей с фактами в программе. Эта стратегия обратного рассуждения и сокращения целей рассматривает правила в логических программах как процедуры и делает Пролог одновременно декларативным и процедурным языком программирования. [14]
Широкий спектр приложений Пролога освещается в Году книги Пролога. [15] празднование 50-летия Пролога.
Журнал данных [ править ]
Истоки Datalog восходят к началу логического программирования, но примерно в 1977 году он был выделен в отдельную область. Синтаксически и семантически он является подмножеством Пролога. Но поскольку в нем нет составных членов , он не является полным по Тьюрингу .
Большинство систем Datalog выполняют программы снизу вверх, используя правила для дальнейшего анализа , извлекая новые факты из существующих и завершая работу, когда нет новых фактов, которые можно получить, или когда производные факты объединяются с запросом. В приведенном выше примере типичная система Datalog сначала получает новые факты:
животное ( том ).
животное ( джерри ).
большой ( Том ).
маленький ( Джерри ).
Используя эти факты, он затем выведет дополнительный факт:
ест ( Том , Джерри ).
Затем он прекратится как потому, что новые дополнительные факты не могут быть получены, так и потому, что вновь полученный факт объединяется с запросом.
ест ( X , Джерри ).
Datalog применяется для решения таких задач, как интеграция данных , извлечение информации , работа в сети , безопасность , облачные вычисления и машинное обучение . [16] [17]
Программирование набора ответов [ править ]
Программирование набора ответов (ASP) развилось в конце 1990-х годов на основе семантики стабильной модели (множества ответов) логического программирования. Как и Datalog, это подмножество Пролога; и, поскольку в нем нет составных членов, он не является полным по Тьюрингу.
Большинство реализаций ASP выполняют программу, сначала «заземляя» программу, заменяя все переменные в правилах константами всеми возможными способами, а затем используя пропозициональный решатель SAT, такой как алгоритм DPLL , для создания одной или нескольких моделей программы.
Его приложения ориентированы на решение сложных задач поиска и представления знаний . [18] [19]
См. также [ править ]
- Сравнение парадигм программирования
- Индуктивное программирование
- Список декларативных языков программирования
Ссылки [ править ]
- ^ Ллойд, Дж. У., Практические преимущества декларативного программирования
- ^ «декларативный язык» . ФОЛДОК . 17 мая 2004 г. Архивировано из оригинала 7 сентября 2023 г. Проверено 7 сентября 2023 г.
- ^ Себеста, Роберт (2016). Понятия языков программирования . Бостон: Пирсон. ISBN 978-0-13-394302-3 . OCLC 896687896 .
- ^ «Императивное программирование: Обзор старейшей парадигмы программирования» . Цифровой гид IONOS . 21 мая 2021 г. Архивировано из оригинала 3 мая 2022 г. Проверено 23 мая 2023 г.
- ^ «DAMP 2009: Семинар по декларативным аспектам многоядерного программирования» . Cse.unsw.edu.au. 20 января 2009 г. Архивировано из оригинала 13 сентября 2013 г. . Проверено 15 августа 2013 г.
- ^ Чакраварти, Мануэль М.Т. (14 февраля 1997 г.). О массово-параллельном выполнении декларативных программ (Докторская диссертация). Технический университет Берлина . Архивировано из оригинала 23 сентября 2015 года . Проверено 26 февраля 2015 г.
В этом контексте критерием для того, чтобы назвать язык программирования декларативным, является наличие четкого, математически установленного соответствия между языком и математической логикой, при котором декларативная семантика языка может быть основана на модели или теории доказательства (или на том и другом). логики.
- ^ «Обзор dsls» . Архивировано из оригинала 23 октября 2007 года.
- ^ «Декларативное моделирование» . Симулистика. Архивировано из оригинала 11 августа 2003 года . Проверено 15 августа 2013 г.
- ^ Гордон, Майкл Дж. К. (1996). «От LCF до HOL: краткая история» . Архивировано из оригинала 5 сентября 2016 г. Проверено 30 октября 2021 г.
- ^ Уилсон, Лесли Б. (2001). Языки сравнительного программирования, третье издание . Аддисон-Уэсли. п. 233. ИСБН 0-201-71012-9 .
- ^ Уилсон, Лесли Б. (2001). Языки сравнительного программирования, третье издание . Аддисон-Уэсли. п. 235. ИСБН 0-201-71012-9 .
- ^ «Рождение Пролога» (PDF) . Ноябрь 1992 г. Архивировано (PDF) из оригинала 2 апреля 2015 г. Проверено 25 мая 2022 г.
- ^ Роберт Ковальски; Дональд Кюнер (зима 1971 г.). «Линейное разрешение с функцией выбора» (PDF) . Искусственный интеллект . 2 (3–4): 227–260. дои : 10.1016/0004-3702(71)90012-9 . ISSN 0004-3702 . Архивировано (PDF) из оригинала 23 сентября 2015 г. Проверено 13 августа 2023 г.
- ^ Роберт Ковальски Логика предикатов как язык программирования. Архивировано 7 февраля 2016 г. в Wayback Machine Memo 70, Департамент искусственного интеллекта, Эдинбургский университет. 1973. Также в материалах Конгресса ИФИП, Стокгольм, North Holland Publishing Co., 1974, стр. 569–574.
- ^ Уоррен, DS (2023). «Введение в Пролог». В Уоррене, Д.С.; Даль, В.; Эйтер, Т.; Эрменегильдо, М.В.; Ковальски, Р.; Росси, Ф. (ред.). Пролог: Следующие 50 лет . Конспект лекций по информатике (). Том. 13900. Спрингер, Чам. стр. 3–19. дои : 10.1007/978-3-031-35254-6_1 . ISBN 978-3-031-35253-9 .
- ^ Хуан, Шань Шань; Грин, Тодд Дж.; Лоо, Бун Тау (12–16 июня 2011 г.). Журнал данных и новые приложения (PDF) . SIGMOD 2011. Афины, Греция: Ассоциация вычислительной техники. ISBN 978-1-4503-0661-4 . Архивировано (PDF) из оригинала 22 октября 2020 г. Проверено 13 августа 2023 г.
- ^ Мэй, Хунъюань; Цинь, Гуанхуэй; Сюй, Минджи; Эйснер, Джейсон (2020). «Нейронная регистрация данных во времени: обоснованное временное моделирование с помощью логической спецификации». Материалы ICML 2020 . arXiv : 2006.16723 .
- ^ Барал, Читта (2003). Представление знаний, рассуждения и декларативное решение проблем . Издательство Кембриджского университета. ISBN 978-0-521-81802-5 .
- ^ Гельфонд, Майкл (2008). «Наборы ответов» . Ин ван Хармелен, Франк; Лифшиц, Владимир; Портер, Брюс (ред.). Справочник по представлению знаний . Эльзевир. стр. 285–316. ISBN 978-0-08-055702-1 . в формате PDF. Архивировано 3 марта 2016 г. на Wayback Machine.
Внешние ссылки [ править ]
- Франс Коэнен. Характеристики декларативных языков программирования . 1999.
- Роберт Харпер .
- Улоф Торгерссон. Заметка о парадигмах декларативного программирования и будущем дефиниционального программирования . 1996.
