По-настоящему понимая разницу между процедурным и функциональным

114

Мне действительно сложно понять разницу между парадигмами процедурного и функционального программирования.

Вот первые два абзаца из статьи Википедии о функциональном программировании :

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

На практике разница между математической функцией и понятием «функция», используемым в императивном программировании, заключается в том, что императивные функции могут иметь побочные эффекты, изменяя значение состояния программы. Из-за этого им не хватает ссылочной прозрачности, т. Е. Одно и то же языковое выражение может приводить к различным значениям в разное время в зависимости от состояния выполняющейся программы. И наоборот, в функциональном коде выходное значение функции зависит только от аргументов, которые вводятся в функцию, поэтому fдвойной вызов функции с одним и тем же значением для аргумента xприведет к тому же результату.f(x)оба раза. Устранение побочных эффектов может значительно облегчить понимание и прогнозирование поведения программы, что является одной из ключевых мотиваций для разработки функционального программирования.

В пункте 2, где говорится

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

Разве это не тот же самый случай процедурного программирования?

На что следует обратить внимание в отличии процедурного от функционального?

Филоксоф
источник
1
Ссылка "Очаровательный Python: функциональное программирование на Python" от Abafei не работает. Вот хороший набор ссылок: ibm.com/developerworks/linux/library/l-prog/index.html ibm.com/developerworks/linux/library/l-prog2/index.html
Крис Koknat
Другой аспект этого - именование. Например. в JavaScript и Common Lisp мы используем термин «функция», даже если для них разрешены побочные эффекты, а в схеме он последовательно называется процедурой. Чистая функция CL может быть записана как чисто функциональная процедура схемы. Почти во всех книгах о Scheme используется термин процедура, поскольку это термин, используемый в стандарте, и он не имеет ничего общего с процедурным или функциональным характером.
Sylwester

Ответы:

276

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

Функциональное программирование относится к способности рассматривать функции как значения.

Рассмотрим аналогию с «обычными» значениями. Мы можем взять два целых значения и объединить их с помощью +оператора, чтобы получить новое целое число. Или мы можем умножить целое число на число с плавающей запятой, чтобы получить число с плавающей запятой.

В функциональном программировании мы можем комбинировать два значения функции для создания нового значения функции, используя такие операторы, как compose или lift . Или мы можем объединить значение функции и значение данных для создания нового значения данных, используя такие операторы, как map или fold .

Обратите внимание, что многие языки обладают возможностями функционального программирования - даже языки, которые обычно не считаются функциональными языками. Даже дедушка FORTRAN поддерживал значения функций, хотя и не предлагал много способов объединения функций. Чтобы язык назывался «функциональным», он должен в значительной степени охватывать возможности функционального программирования.

Процедурное программирование

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

Контраст

Эти два стиля на самом деле не являются противоположностями - они просто отличаются друг от друга. Есть языки, которые полностью охватывают оба стиля (например, LISP). Следующий сценарий может дать представление о некоторых различиях в двух стилях. Давайте напишем код для бессмысленного требования, в котором мы хотим определить, все ли слова в списке содержат нечетное количество символов. Во-первых, процедурный стиль:

function allOdd(words) {
  var result = true;
  for (var i = 0; i < length(words); ++i) {
    var len = length(words[i]);
    if (!odd(len)) {
      result = false;
      break;
    }
  }
  return result;
}

Считаю само собой разумеющимся, что этот пример понятен. Теперь о функциональном стиле:

function allOdd(words) {
  return apply(and, map(compose(odd, length), words));
}

Работая изнутри, это определение выполняет следующие функции:

  1. compose(odd, length)сочетает в себе oddи lengthфункции , чтобы произвести новую функцию , которая определяет , является ли длина строки нечетно.
  2. map(..., words)вызывает эту новую функцию для каждого элемента в words, в конечном итоге возвращая новый список логических значений, каждое из которых указывает, имеет ли соответствующее слово нечетное количество символов.
  3. apply(and, ...)применяет к полученному списку оператор «и» и объединяет все логические значения вместе, чтобы получить окончательный результат.

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

В примере также показаны типичные относительные размеры процедурного и функционального кода. Более того, это демонстрирует, что характеристики производительности процедурного кода легче увидеть, чем характеристики функционального кода. Подумайте: вычисляют ли функции длины всех слов в списке или каждое останавливается сразу после нахождения первого слова четной длины? С другой стороны, функциональный код позволяет качественной реализации выполнить довольно серьезную оптимизацию, поскольку он в первую очередь выражает намерение, а не явный алгоритм.

Дальнейшее чтение

Этот вопрос возникает часто ... см., Например:

Лекция Джона Бэкуса о награждении Тьюринга очень подробно раскрывает мотивы функционального программирования:

Можно ли освободить программирование от стиля фон Неймана?

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


Приложение - 2013

Комментаторы отмечают, что популярные современные языки предлагают другие стили программирования помимо процедурных и функциональных. Такие языки часто предлагают один или несколько из следующих стилей программирования:

  • запрос (например, составление списка, запрос, интегрированный с языком)
  • поток данных (например, неявная итерация, массовые операции)
  • объектно-ориентированный (например, инкапсулированные данные и методы)
  • ориентированный на язык (например, синтаксис для конкретного приложения, макросы)

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

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

WReach
источник
1
Действительно хороший ответ, но не могли бы вы немного упростить код, например: «function allOdd (words) {foreach (auto word in words) {odd (length (word)? Return false:;} return true;}»
Дайниус
Функциональный стиль там довольно трудно читать по сравнению с «функциональным стилем» в python: def odd_words (words): return [x for x in words if odd (len (x))]
штучной упаковке
@boxed: ваше odd_words(words)определение отличается от ответа allOdd. Для фильтрации и сопоставления часто предпочтительнее составление списков, но здесь allOddпредполагается, что функция сокращает список слов до одного логического значения.
ShinNoNoir
@WReach: я бы написал ваш функциональный пример следующим образом: function allOdd (words) {return and (odd (length (first (words))), allOdd (rest (words))); } Он не более элегантен, чем ваш пример, но в языке с хвостовой рекурсией он будет иметь те же характеристики производительности, что и императивный стиль.
mishoo
@mishoo Я считаю, что язык должен быть как хвостовой рекурсивной, так и строгой и сокращающей в операторе and, чтобы ваше предположение было выполнено.
kqr
46

Настоящая разница между функциональным и императивным программированием заключается в мировоззрении: императивные программисты думают о переменных и блоках памяти, в то время как функциональные программисты думают: «Как мне преобразовать свои входные данные в выходные данные?» - ваша «программа» - это конвейер и набор преобразований данных, чтобы перевести их из входа в выход. ИМО, это интересная часть, а не бит «Не использовать переменные».

Как следствие такого образа мыслей, программы FP обычно описывают то, что произойдет, вместо конкретного механизма того, как это произойдет - это мощный инструмент, потому что, если мы можем четко указать, что означает «Выбрать», «Где» и «Агрегировать», мы могут свободно менять свои реализации, как мы это делаем с AsParallel (), и внезапно наше однопоточное приложение масштабируется до n ядер.

Ана Беттс
источник
каким-либо образом вы можете противопоставить их, используя фрагменты кода? действительно ценю это
Philoxopher
1
@KerxPhilo: Вот очень простая задача (сложить числа от 1 до n). Обязательно: изменить текущее число, изменить сумму до сих пор. Код: int i, сумма; сумма = 0; для (я = 1; я <= п; я ++) {сумма + = я; }. Функциональный (Haskell): возьмите ленивый список чисел, сложите их вместе, прибавляя к нулю. Код: foldl (+) 0 [1..n]. Извините, в комментариях нет форматирования.
dirkt 08
+1 к ответу. Другими словами, функциональное программирование заключается в написании функций без побочных эффектов, когда это возможно, т.е. функция всегда возвращает одно и то же, когда заданы одни и те же параметры - это основа. Если вы будете следовать этому подходу до крайности, ваши побочные эффекты (они вам всегда нужны) будут изолированы, а остальные функции просто преобразуют входные данные в выходные данные.
beluchin 08
12
     Isn't that the same exact case for procedural programming?

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

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

Энди Томас
источник
1
Можете показать пример и сравнение? Я искренне признателен, если бы мог.
Philoxopher 07
8
Функция rand () в C обеспечивает разные результаты для каждого вызова. Он сохраняет состояние между вызовами. Он не является ссылочно прозрачным. Для сравнения, std :: max (a, b) в C ++ всегда будет возвращать один и тот же результат с теми же аргументами и не имеет побочных эффектов (о которых я знаю ...).
Энди Томас
11

Я не согласен с ответом WReach. Давайте немного разберем его ответ, чтобы увидеть, откуда взялось разногласие.

Во-первых, его код:

function allOdd(words) {
  var result = true;
  for (var i = 0; i < length(words); ++i) {
    var len = length(words[i]);
    if (!odd(len)) {
      result = false;
      break;
    }
  }
  return result;
}

и

function allOdd(words) {
  return apply(and, map(compose(odd, length), words));
}

Первое, что следует отметить, это то, что он объединяет:

  • Функциональный
  • Ориентация на экспрессию и
  • Итератор ориентированный

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

Давайте быстро поговорим об этом.

Стиль, ориентированный на выражения, - это стиль, в котором вещи, насколько это возможно, оценивают вещи. Хотя функциональные языки славятся своей любовью к выражениям, на самом деле возможно иметь функциональный язык без составных выражений. Я собираюсь придумать такой, где нет выражений, только утверждения.

lengths: map words length
each_odd: map lengths odd
all_odd: reduce each_odd and

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

Стиль программирования, ориентированный на итератор, может быть принят Python. Давайте использовать чисто итеративный стиль, ориентированный на итераторы:

def all_odd(words):
    lengths = (len(word) for word in words)
    each_odd = (odd(length) for length in lengths)
    return all(each_odd)

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

Конечно, вы можете сжать это:

def all_odd(words):
    return all(odd(len(word)) for word in words)

Императив сейчас не так уж и плох, а? :)

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

function allOdd(words) {
    for (var i = 0; i < length(words); ++i) {
        if (!odd(length(words[i]))) {
            return false;
        }
    }
    return true;
}

Используя итераторы, вы можете:

function allOdd(words) {
    for (word : words) { if (!odd(length(word))) { return false; } }
    return true;
}

Так что это точка функционального языка , если разница между:

return all(odd(len(word)) for word in words)
return apply(and, map(compose(odd, length), words))
for (word : words) { if (!odd(length(word))) { return false; } }
return true;


Главной отличительной чертой функционального языка программирования является то, что он устраняет мутации как часть типичной модели программирования. Люди часто понимают, что это означает, что в функциональном языке программирования нет операторов или выражений, но это упрощения. Функциональный язык заменяет явное вычисление объявлением поведения, которое затем сокращается.

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

Когда у вас есть функциональный язык, создание новых функций, как правило, так же просто, как создание тесно связанных функций.

all = partial(apply, and)

Это непросто или, возможно, даже невозможно, если вы явно не контролировали глобальные зависимости функции. Лучшая особенность функционального программирования состоит в том, что вы можете последовательно создавать более общие абстракции и верить, что их можно объединить в единое целое.

Veedrac
источник
Знаете, я почти уверен, что это applyне совсем такая же операция, как foldили reduce, хотя я согласен с прекрасной способностью иметь очень общие алгоритмы.
Бенедикт Ли
Я никогда не слышал о applyзначении foldили reduce, но мне кажется, что оно должно быть в этом контексте, чтобы возвращать логическое значение.
Veedrac
А, ладно, я запутался в названии. Спасибо, что прояснили это.
Бенедикт Ли
6

В процедурной парадигме (лучше сказать «структурированное программирование»?) У вас есть общая изменяемая память и инструкции, которые читают / записывают ее в некоторой последовательности (одну за другой).

В функциональной парадигме у вас есть переменные и функции (в математическом смысле: переменные не меняются с течением времени, функции могут вычислять что-то только на основе своих входных данных).

(Это слишком упрощенно, например, FPL обычно имеют средства для работы с изменяемой памятью, тогда как процедурные языки часто могут поддерживать процедуры более высокого порядка, поэтому все не так однозначно; но это должно дать вам представление)

Артём Шалхаков
источник
2

Очаровательный Python: Функциональное программирование на Python от IBM Developerworks действительно помог мне понять разницу.

Особенно для тех, кто немного знаком с Python, примеры кода в этой статье, в которых противопоставляются разные действия функционально и процедурно, могут прояснить разницу между процедурным и функциональным программированием.

Abbafei
источник
2

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

В процедурном программировании, если вы хотите ответить на вопрос, какова ценность, xвам также необходимо знать, как вы к этому пришли, одной лишь области видимости и имени недостаточно. И это то, что я считаю самой большой проблемой, потому что этот путь выполнения является свойством «времени выполнения» и может зависеть от стольких разных вещей, что большинство людей учатся просто отлаживать его, а не пытаться восстановить путь выполнения.

Василий
источник
1

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

Джон Л
источник
0

Одно четкое различие между двумя парадигмами программирования - это состояние.

В функциональном программировании состояние избегается. Проще говоря, не будет переменной, которой присвоено значение.

Пример:

def double(x):
    return x * 2

def doubleLst(lst):
    return list(map(double, action))

Однако в процедурном программировании используется состояние.

Пример:

def doubleLst(lst):
    for i in range(len(lst)):
        lst[i] = lst[i] * 2  # assigning of value i.e. mutation of state
    return lst
Tox
источник