stringtranslate.com

Декларативное программирование

В информатике декларативное программирование — это парадигма программирования — стиль построения структуры и элементов компьютерных программ, — который выражает логику вычислений без описания потока управления . [1]

Многие языки, применяющие этот стиль, пытаются свести к минимуму или устранить побочные эффекты , описывая то, что должна выполнить программа, в терминах предметной области , а не описывая, как это выполнить, в виде последовательности примитивов языка программирования [2] ( оставление «как» вплоть до реализации языка ). Это контрастирует с императивным программированием , которое реализует алгоритмы в виде явных шагов. [3]

Декларативное программирование часто рассматривает программы как теории формальной логики , а вычисления — как выводы в этом логическом пространстве. Декларативное программирование может значительно упростить написание параллельных программ . [4]

Общие декларативные языки включают в себя языки запросов к базам данных (например, SQL , XQuery ), регулярные выражения , логическое программирование (например , Prolog , Datalog , программирование набора ответов ), функциональное программирование и системы управления конфигурацией .

Этот термин часто используется в отличие от императивного программирования, которое явно диктует шаги преобразования своего состояния. [5]

Определение

Декларативное программирование часто определяют как любой стиль программирования, который не является обязательным. Ряд других распространенных определений пытаются определить его, просто противопоставляя его императивному программированию. Например:

Эти определения существенно пересекаются.

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

В чисто функциональном языке , таком как Haskell , все функции не имеют побочных эффектов , а изменения состояния представляются только как функции, преобразующие состояние, которое явно представлено в программе как первоклассный объект. Хотя чистые функциональные языки не являются обязательными, они часто предоставляют возможность описать эффект функции в виде серии шагов. Другие функциональные языки, такие как Lisp , OCaml и Erlang , поддерживают смесь процедурного и функционального программирования.

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

Субпарадигмы

Декларативное программирование — это общий термин , включающий ряд более известных парадигм программирования .

Программирование ограничений

Программирование с ограничениями устанавливает отношения между переменными в форме ограничений, которые определяют свойства целевого решения. Набор ограничений решается путем присвоения значения каждой переменной, чтобы решение соответствовало максимальному количеству ограничений. Программирование с ограничениями часто дополняет другие парадигмы: функциональное, логическое или даже императивное программирование.

Языки, специфичные для предметной области

Хорошо известные примеры декларативных предметно-ориентированных языков (DSL) включают язык ввода генератора синтаксического анализатора yacc , QML , язык спецификации сборки Make , язык управления конфигурацией Puppet , регулярные выражения , журнал данных , программирование набора ответов и подмножество SQL ( например, запросы SELECT). Преимущество DSL заключается в том, что они полезны, но не обязательно должны быть полными по Тьюрингу , что позволяет языку быть чисто декларативным.

Многие языки разметки, такие как HTML , MXML , XAML , XSLT или другие языки разметки пользовательского интерфейса, часто являются декларативными. HTML, например, описывает только то, что должно отображаться на веб-странице — он не определяет ни поток управления для отрисовки страницы, ни возможные взаимодействия страницы с пользователем .

По состоянию на 2013 год некоторые программные системы [ какие? ] объединяют традиционные языки разметки пользовательского интерфейса (такие как HTML) с декларативной разметкой, которая определяет, что (но не как) должны делать серверные системы для поддержки объявленного интерфейса. Такие системы, обычно использующие пространство имен XML, специфичное для предметной области , могут включать абстракции синтаксиса базы данных SQL или параметризованные вызовы веб-служб с использованием передачи репрезентативного состояния (REST) ​​и SOAP . [ нужна цитата ]

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

Языки функционального программирования, такие как Haskell , Scheme и ML , оценивают выражения через приложение-функцию. В отличие от родственной, но более императивной парадигмы процедурного программирования , функциональное программирование уделяет мало внимания явному упорядочению. Вместо этого вычисления характеризуются различными видами рекурсивного применения и композиции функций высшего порядка и поэтому могут рассматриваться просто как набор отображений между доменами и кодоменами . Многие функциональные языки, в том числе большинство из семейств ML и Lisp, не являются чисто функциональными и, таким образом, допускают введение в программы эффектов с сохранением состояния .

Гибридные языки

Например, файлы Makefile определяют зависимости в декларативной форме [7] , но также включают обязательный список действий, которые необходимо предпринять. Аналогично, yacc декларативно определяет контекстно-свободную грамматику, но включает фрагменты кода с основного языка, что обычно является обязательным (например, C ).

Логическое программирование

Языки логического программирования , такие как Пролог , Журнал данных и программирование набора ответов , выполняют вычисления, доказывая, что цель является логическим следствием программы, или показывая, что цель верна в модели, определенной программой. Пролог выполняет вычисления, сводя цели к подцелям, сверху вниз, используя обратное рассуждение , тогда как большинство систем Datalog выполняют вычисления снизу вверх, используя прямое рассуждение . Программы набора ответов обычно используют решатели SAT для создания модели программы.

Моделирование

Модели или математические представления физических систем могут быть реализованы в декларативном компьютерном коде. Код содержит ряд уравнений, а не императивных присваиваний, которые описывают («декларируют») поведенческие отношения. Когда модель выражается в этом формализме, компьютер может выполнять алгебраические манипуляции, чтобы лучше сформулировать алгоритм решения. Математическая причинность обычно накладывается на границы физической системы, тогда как поведенческое описание самой системы является декларативным или акаузальным. Языки и среды декларативного моделирования включают Analytica , Modelica и Simile. [8]

Примеры

Лисп

Lisp — это семейство языков программирования, вдохновленное математической записью и лямбда-исчислением Алонзо Чёрча . Хотя некоторые диалекты, такие как Common Lisp , в первую очередь императивны, эти Lisp поддерживают функциональное программирование, а другие Lisp, такие как 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 неотрицательных целых чисел

Карта в приведенном выше примере принимает функцию и список, применяя функцию к каждому члену списка.

МЛ

ML (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 для обратного рассуждения , сводя цели к подцелям. В этом примере оно использует последнее правило программы, чтобы свести цель ответа на запрос к подцелям сначала найти X, такой, который выполняется, а затем показать, что это выполняется. Он неоднократно использует правила для дальнейшего сведения подцелей к другим подцелям, пока в конечном итоге не достигнет успеха в объединении всех подцелей с фактами в программе. Эта стратегия обратного рассуждения и сокращения целей рассматривает правила в логических программах как процедуры и делает Пролог одновременно декларативным и процедурным языком программирования . [14]eat(X,jerry)big(X)small(jerry)

Широкий спектр приложений Пролога освещен в книге «Год Пролога» [15] , посвященной 50-летнему юбилею Пролога.

Журнал данных

Истоки Datalog восходят к началу логического программирования, но примерно в 1977 году он был выделен в отдельную область. Синтаксически и семантически он является подмножеством Пролога. Но поскольку в нем нет составных членов , он не является полным по Тьюрингу .

Большинство систем Datalog выполняют программы снизу вверх, используя правила для дальнейшего анализа , извлекая новые факты из существующих и завершая работу, когда нет новых фактов, которые можно получить, или когда производные факты объединяются с запросом. В приведенном выше примере типичная система Datalog сначала получает новые факты:

животное ( том ). животное ( джерри ). большой ( Том ). маленький ( Джерри ).

Используя эти факты, он затем выведет дополнительный факт:

ест ( Том ,  ​​Джерри ).

Затем он прекратится как потому, что новые дополнительные факты не могут быть получены, так и потому, что вновь полученный факт объединяется с запросом.

ест ( X ,  Джерри ).

Datalog применяется для решения таких задач, как интеграция данных , извлечение информации , работа в сети , безопасность , облачные вычисления и машинное обучение . [16] [17]

Программирование набора ответов

Программирование набора ответов (ASP) развилось в конце 1990-х годов на основе семантики стабильной модели (множества ответов) логического программирования. Как и Datalog, это подмножество Пролога; и, поскольку в нем нет составных членов, он не является полным по Тьюрингу.

Большинство реализаций ASP выполняют программу, сначала «заземляя» программу, заменяя все переменные в правилах константами всеми возможными способами, а затем используя пропозициональный решатель SAT, такой как алгоритм DPLL , для создания одной или нескольких моделей программы.

Его приложения ориентированы на решение сложных задач поиска и представления знаний . [18] [19]

Смотрите также

Рекомендации

  1. ^ Ллойд, Дж.В., Практические преимущества декларативного программирования
  2. ^ «декларативный язык». ФОЛДОК . 17 мая 2004 года . Проверено 7 сентября 2023 г.
  3. ^ Себеста, Роберт (2016). Понятия языков программирования . Бостон: Пирсон. ISBN 978-0-13-394302-3. OCLC  896687896.
  4. ^ «DAMP 2009: Семинар по декларативным аспектам многоядерного программирования». Cse.unsw.edu.au. 20 января 2009 года. Архивировано из оригинала 13 сентября 2013 года . Проверено 15 августа 2013 г.
  5. ^ «Императивное программирование: обзор старейшей парадигмы программирования». Цифровой гид IONOS . 21 мая 2021 г. Проверено 23 мая 2023 г.
  6. ^ Чакраварти, Мануэль М.Т. (14 февраля 1997 г.). О массово-параллельном выполнении декларативных программ (Докторская диссертация). Технический университет Берлина . Проверено 26 февраля 2015 г. В этом контексте критерием для того, чтобы назвать язык программирования декларативным, является наличие четкого, математически установленного соответствия между языком и математической логикой, при котором декларативная семантика языка может быть основана на модели или теории доказательства (или на том и другом). логики.
  7. ^ «Обзор dsls» . Архивировано из оригинала 23 октября 2007 года.
  8. ^ «Декларативное моделирование». Симулистика . Проверено 15 августа 2013 г.
  9. ^ Гордон, Майкл Дж. К. (1996). «От LCF до HOL: краткая история» . Проверено 30 октября 2021 г.
  10. ^ Уилсон, Лесли Б. (2001). Языки сравнительного программирования, третье издание . Аддисон-Уэсли. п. 233. ИСБН 0-201-71012-9.
  11. ^ Уилсон, Лесли Б. (2001). Языки сравнительного программирования, третье издание . Аддисон-Уэсли. п. 235. ИСБН 0-201-71012-9.
  12. ^ «Рождение Пролога» (PDF) . Ноябрь 1992 года.
  13. ^ Роберт Ковальски; Дональд Кюнер (зима 1971 г.). «Линейное разрешение с функцией выбора» (PDF) . Искусственный интеллект . 2 (3–4): 227–260. дои : 10.1016/0004-3702(71)90012-9. ISSN  0004-3702.
  14. ^ Роберт Ковальски Логика предикатов как язык программирования, памятка 70, Департамент искусственного интеллекта, Эдинбургский университет. 1973. Также в материалах Конгресса ИФИП, Стокгольм, North Holland Publishing Co., 1974, стр. 569–574.
  15. ^ Уоррен, DS (2023). «Введение в Пролог». В Уоррене, Д.С.; Даль, В.; Эйтер, Т.; Эрменегильдо, М.В.; Ковальски, Р.; Росси, Ф. (ред.). Пролог: Следующие 50 лет . Конспект лекций по информатике (). Том. 13900. Спрингер, Чам. стр. 3–19. дои : 10.1007/978-3-031-35254-6_1. ISBN 978-3-031-35253-9.
  16. ^ Хуан, Шань-Шань; Грин, Тодд Дж.; Лоо, Бун Тау (12–16 июня 2011 г.). Журнал данных и новые приложения (PDF) . SIGMOD 2011. Афины, Греция: Ассоциация вычислительной техники. ISBN 978-1-4503-0661-4.
  17. ^ Мэй, Хунъюань; Цинь, Гуанхуэй; Сюй, Минджи; Эйснер, Джейсон (2020). «Нейронная регистрация данных во времени: обоснованное временное моделирование с помощью логической спецификации». Материалы ICML 2020 . arXiv : 2006.16723 .
  18. ^ Барал, Читта (2003). Представление знаний, рассуждения и декларативное решение проблем . Издательство Кембриджского университета. ISBN 978-0-521-81802-5.
  19. ^ Гельфонд, Майкл (2008). «Наборы ответов». Ин ван Хармелен, Франк; Лифшиц, Владимир; Портер, Брюс (ред.). Справочник по представлению знаний . Эльзевир. стр. 285–316. ISBN 978-0-08-055702-1.в формате PDF. Архивировано 3 марта 2016 г. на Wayback Machine.

Внешние ссылки