Что делает функциональные языки программирования декларативными, а не императивными?

Во многих статьях, описывающих преимущества функционального программирования, я видел функциональные языки программирования, такие как Haskell, ML, Scala или Clojure, называемые «декларативными языками», отличными от императивных языков, таких как C / C ++ / C # / Java. Мой вопрос заключается в том, что делает функциональные языки программирования декларативными, а не императивными.

Часто встречающееся объяснение, описывающее различия между декларативным и императивным программированием, состоит в том, что в императивном программировании вы говорите компьютеру «Как сделать что-то», а не «Что делать» в декларативных языках. Проблема с этим объяснением состоит в том, что вы постоянно делаете оба на всех языках программирования. Даже если вы переходите к сборке самого низкого уровня, вы все еще говорите компьютеру «Что делать», вы указываете ЦПУ добавить два числа, но не указываете, как выполнить сложение. Если мы перейдем к другому концу спектра, высокоуровневому чисто функциональному языку, такому как Haskell, вы на самом деле говорите компьютеру, как выполнить конкретную задачу, это то, что ваша программа представляет собой последовательность инструкций для достижения конкретной задачи, которую компьютер не знает, как выполнить в одиночку. Я понимаю, что такие языки, как Haskell, Clojure и т. Д., Очевидно, имеют более высокий уровень, чем C / C ++ / C # / Java, и предлагают такие функции, как отложенная оценка, неизменные структуры данных, анонимные функции, каррирование, постоянные структуры данных и т. Д. функциональное программирование возможно и эффективно, но я бы не классифицировал их как декларативные языки.

Для меня чисто декларативными языками был бы тот, который полностью состоит только из объявлений, примером таких языков может быть CSS (да, я знаю, что CSS технически не будет языком программирования). CSS просто содержит объявления стилей, которые используются HTML и Javascript страницы. CSS не может ничего делать, кроме как делать объявления, он не может создавать функции класса, то есть функции, которые определяют стиль отображения на основе некоторого параметра, вы не можете выполнять скрипты CSS и т. Д. Это для меня описывает декларативный язык (обратите внимание, я не сказал декларативный язык программирования ).

Обновить:

Я недавно играл с Прологом, и для меня Пролог - самый близкий язык программирования к полностью декларативному языку (по крайней мере, на мой взгляд), если это не единственный полностью декларативный язык программирования. Чтобы разработать программирование в Прологе, нужно сделать декларации, в которых указывается либо факт (функция предиката, которая возвращает истину для определенного ввода), либо правило (функция предиката, которая возвращает истину для данного условия / шаблона на основе входных данных), правила определяются с помощью метода сопоставления с образцом. Чтобы сделать что-либо в прологе, вы запрашиваете базу знаний, заменяя один или несколько входных данных предиката переменной, и пролог пытается найти значения для переменной (ей), для которой прецедент завершается успешно.

Суть в том, что в прологе нет обязательных инструкций: вы в основном рассказываете (объявляете) компьютеру, что он знает, а затем спрашиваете (спрашиваете) о знаниях. В функциональных языках программирования вы все еще даете инструкции, то есть берете значение, вызываете функцию X и добавляете к ней 1 и т. Д., Даже если вы не управляете непосредственно ячейками памяти или не записываете вычисления шаг за шагом. Я бы не сказал, что программирование на Haskell, ML, Scala или Clojure декларативно в этом смысле, хотя я могу ошибаться. Является ли правильное, истинное, чисто функциональное программирование декларативным в том смысле, что я описал выше.

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

Вопрос в том, является ли такая перспектива разумной и, наоборот, насколько близко последовательность инструкций напоминает декларацию вычисляемого результата. Для CSS декларативная перспектива явно более полезна. Для C императивная перспектива явно преобладает. Что касается языков, как Haskell, ну ...

Язык уточнил, конкретная семантика. То есть, конечно, можно интерпретировать программу как цепочку операций. Даже не требуется слишком много усилий для выбора примитивных операций, чтобы они красиво отображались на обычном оборудовании (это то, что делают машины STG и другие модели).

Однако то, как пишутся программы на Haskell, часто может быть разумно прочитано как описание результата, который нужно вычислить. Возьмем, к примеру, программу для вычисления суммы первых N факториалов:

sum_of_fac n = sum [product [1..i] | i <- ..n]

Вы можете удалить это и прочитать его как последовательность операций STG, но гораздо более естественным является чтение его как описания результата (которое, я думаю, является более полезным определением декларативного программирования, чем «что вычислять»): Результатом является сумма произведений [1..i]для всех i= 0,…, n. И это гораздо более декларативно, чем почти любая программа или функция на Си.

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

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

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

Реальная определяющая характеристика, которая отделяет декларативное от императивного программирования, - в декларативном стиле, вы не даете последовательных инструкций; на более низком уровне да, CPU работает таким образом, но это проблема компилятора.

Вы предлагаете CSS «декларативный язык», я бы не стал называть его языком вообще. Это формат структуры данных, такой как JSON, XML, CSV или INI, просто формат для определения данных, который известен интерпретатору некоторой природы.

Некоторые интересные побочные эффекты возникают, когда вы убираете оператор присваивания из языка, и это реальная причина потери всех этих обязательных инструкций step1-step2-step3 в декларативных языках.

Что вы делаете с оператором присваивания в функции? Вы создаете промежуточные шаги. В этом суть, оператор присваивания используется для пошагового изменения данных. Как только вы больше не можете изменять данные, вы теряете все эти шаги и получаете:

Каждая функция имеет только одно утверждение, это утверждение является единственным объявлением

Теперь есть много способов сделать одно утверждение похожим на множество утверждений, но это, например, просто обман: 1 + 3 + (2*4) + 8 - (7 / (8*3))это однозначное утверждение, но если вы напишите его как ...

1 +
3 +
(
  2*4
) +
8 - 
(
  7 / (8*3)
)

Это может привести к появлению последовательности операций, чтобы мозг мог легче распознать желаемое разложение, которое намеревался автор. Я часто делаю это в C # с кодом, как ..

people
  .Where(person => person.MiddleName != null)
  .Select(person => person.MiddleName)
  .Distinct();

Это отдельное утверждение, но оно показывает, что его можно разложить на множество - обратите внимание, что никаких назначений нет.

Также обратите внимание, что в обоих вышеописанных методах код на самом деле выполняется не в том порядке, в котором вы сразу его прочитали; потому что этот код говорит, что делать, но не диктует как . Обратите внимание, что приведенная выше простая арифметика, очевидно, не будет выполняться в той последовательности, в которой она написана слева направо, и в приведенном выше примере C # эти 3 метода фактически все повторно вводятся и не выполняются до завершения в последовательности, компилятор фактически генерирует код это будет делать то, что хочет это утверждение , но не обязательно, как вы предполагаете.

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

В декларативном языке, если вы хотите, чтобы промежуточная переменная что-то делала - это означает передачу ее в качестве параметра функции, которая делает это. Вот почему рекурсия становится такой важной.

sum xs = (head xs) + sum (tail xs)

Вы не можете создать resultSumпеременную и добавить ее во время цикла xs, вам нужно просто взять первое значение и добавить его к любой сумме всего остального - и получить доступ ко всему остальному, что вы должны передать xsв функцию, tailпотому что Вы не можете просто создать переменную для xs и вытолкнуть голову, что было бы императивным подходом. (Да, я знаю, что вы можете использовать деструктуризацию, но этот пример предназначен для иллюстрации)

Я знаю, что я опоздал на вечеринку, но у меня было прозрение на днях, так что вот оно ...

Я думаю, что комментарии о функциональности, неизменяемости и отсутствии побочных эффектов не попадают в цель, когда объясняют разницу между декларативным и императивным или объясняют, что означает декларативное программирование. Кроме того, как вы упоминаете в своем вопросе, все «что делать» против «как это сделать» слишком расплывчато и на самом деле тоже не объясняет.

Давайте возьмем простой код a = b + cв качестве основы и рассмотрим оператор на нескольких разных языках, чтобы получить представление:

Когда мы пишем a = b + cна императивном языке, таком как C, мы присваиваем текущее значение b + cпеременной aи ничего более. Мы не делаем никаких фундаментальных заявлений о том, что aесть. Скорее, мы просто выполняем шаг в процессе.

Когда мы пишем a = b + cна декларативном языке, таком как Microsoft Excel, (да, Excel является языком программирования и, возможно, самым декларативным из всех их), мы утверждаем связь между ними a, bи cтаким образом, что всегда aесть сумма два других. Это не шаг в процессе, это инвариант, гарантия, декларация правды.

Функциональные языки также декларативны, но почти случайно. В Хаскеле, например , a = b + cтакже утверждает , инвариантные отношения, но только потому , что bи cнеизменны.

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

Вы правы в том, что нет четкого различия между указанием компьютеру, что делать и как это сделать.

Однако с одной стороны спектра вы почти исключительно думаете о том, как манипулировать памятью. То есть, чтобы решить проблему, вы представляете ее на компьютер в форме, подобной «задайте для этой области памяти значение x, затем установите для этой области памяти значение y, перейдите к области памяти z ...», а затем каким-то образом получите результат в другом месте памяти.

В управляемых языках, таких как Java, C # и т. Д., У вас больше нет прямого доступа к аппаратной памяти. Императивный программист теперь занимается статическими переменными, ссылками или полями экземпляров классов, которые в некоторой степени являются абстракциями для областей памяти.

В таких языках, как Haskell, OTOH, память полностью исчезла. Это просто не тот случай, когда в

f a b = let y = sum [a..b] in y*y

должно быть две ячейки памяти, которые содержат аргументы a и b, и еще одна ячейка, которая содержит промежуточный результат y. Конечно, серверная часть компилятора может выдавать окончательный код, который работает таким образом (и в некотором смысле это должно быть сделано, если целевая архитектура является машиной v. Neumann).

Но дело в том, что нам не нужно усваивать архитектуру v. Neumann, чтобы понять вышеуказанную функцию. Нам также не нужен современный компьютер для его запуска. Было бы легко перевести программы на чистом языке FP на гипотетическую машину, которая работает, например, на основе исчисления SKI. Теперь попробуйте то же самое с программой на C!

Чисто декларативные языки для меня будут такими, которые состоят исключительно из деклараций.

Это не достаточно сильно, ИМХО. Даже программа на C - это просто последовательность объявлений. Я чувствую, что мы должны квалифицировать заявления дальше. Например, они говорят нам , что - то есть (декларативный) или то , что он делает (императив).