Здравствуйте, Adopt, Вы писали:
A>Что такое Декларативное программирование? A>В чем различие от ООП допустим или от функционального?
Попробую ответить... хотя плохо во всём этом разбираюсь
Есть программирование императивное и программирование декларативное. В императивном программировании программа представлена в виде набора действий, которые должны быть выполнены (т.е. эдакий ассемблер высокого уровня). Т.е. код описывает решение задачи. Типичные представители императивных языков — C, Pascal, BASIC.
В идеале декларативного программировании код описывает саму задачу (а не один из способов её решения, как в императивном). Например, атрибуты в C# — это элемент декларативного программирования. Применяя к методу атрибут DllImport[], мы декларируем тот факт, что должна быть использована библиотечная функция, а в какой машинный код это в итоге превратится — нас не волнует. Представители декларативных языков: Lisp, ML, Prolog, Haskell...
Часто декларативные языки содержат элементы императивных (OCaml, например) и наоборот (всё тот же C#).
Вот так вот... может, немного расплывчато — но как смог.
А ООП — это вообще методика, т.е. нечто из другой оперы. Принципы ООП можно использовать как в императивном (C++, Java, Object Pascal), так и в декларативном (OCaml, Haskell [imho то, что есть в Хаскеле, тоже имеет отношение к ООП]) программировании.
PS: функциональное программирование — это подвид декларативного (как и логическое). Т.е. Haskell — это чисто функциональный язык декларативного программирования
Здравствуйте, Adopt, Вы писали:
A>Что такое Декларативное программирование? A>В чем различие от ООП допустим или от функционального?
Нельзя сравнивать — совершенно разные вещи. Объясню, что такое "декларативное программирование" на примере "функционального" (благо могу просто скопировать из документа).
Что такое «функциональный язык» (ФЯ)?
Единого мнения на предмет точного определения функционального языка не существует, в том числе и среди сообщества функционального программирования. Тем не менее, возможно дать определение, характеризующее тип языков, обсуждаемых в форуме comp.lang.functional:
Функциональное программирование — это стиль программирования, который опирается на вычисление выражений, а не на выполнение команд. Выражения формируются посредством комбинирования функций. Функциональный язык — это язык, который поддерживает и поощряет программирование в функциональном стиле.
Рассмотрим, например, вычисление суммы целых чисел от 1 до 10. На императивном языке, таком как С, это может быть сделано при помощи простого цикла, на каждом шаге которого изменяется значение накопленной суммы в переменной total и переменной цикла i.
int total = 0;
for (i=1; i<=10; ++i)
total += i;
В функциональном языке та же программа будет записана без использования операций, изменяющих значения переменных. Например, на языке Haskell результат может быть вычислен выражением:
sum [1..10]
Здесь [1..10] — это выражение, обозначающее список целых чисел от 1 до 10, а sum – это функция, которая вычисляет сумму заданного списка значений.
Тот же принцип может быть использован в программах на таких ФЯ как SML или Scheme, но с применением более распространнной записи с явным циклом, часто — выраженным рекурсивно. В любом случае, нет необходимости изменять значения используемых переменных.
SML:
let fun sum i tot =
if i = 0 then tot
else sum ( i - 1 ) ( tot + i )
in sum 10 0
end
Scheme:
( define sum
( lambda ( from total )
( if ( = 0 from )
total
( sum ( - from 1 ) ( + total from ) ) ) ) )
( sum 10 0 )
Часто возможно писать программы в функциональном стиле на императивном языке, и наоборот. Соответственно, возможны разные мнения на тему «является-ли некий язык функциональным, или нет».
Зачем нужны функциональные языки?
В ряде случаев применение функциональных языков может увеличить продуктивность и качество работы программиста в разы. Это увеличение продуктивности, разумеется, зависит от сочетания задачи, языка, и программиста.
О том, как такое возможно в принципе, нетрудно получить представление, сравнив производительность труда программиста, применяющего декларативный язык запросов SQL, и программиста баз данных с интерфейсом ISAM (индексно-последовательный доступ — как в dBase). Стоит отметить, что для некоторых задач применять ISAM выгоднее и даже проще (например, для хранения истории котировок акций), или, по крайней мере, разница не заметна. Но для более сложных структур данных очевиден выигрыш декларативного SQL, в котором программист вместо перечисления последовательности действий, необходимых для получения результата, просто описывает, что он хочет получить.
Похожая ситуация будет и при сравнении императивных и функциональных языков. Применяя последние, программист сфокусирован на высокоуровневом «что требуется», а не на низкоуровневом «как делать» — это отличительная черта функционального стиля. Другими словами, программа состоит не из "алгоритмов", и из "определений". Для иллюстрации возьмем реализацию quicksort на языке Haskell, где фактически дается рекурсивное определение сортированного массива.
qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
Первая строчка читается так: "Результат сортировки пустого списка (записывается как []) – пустой список". Вторая строчка: "Чтобы отсортировать список с первым элементом x и хвостом xs, достаточно отсортировать все элементы xs которые меньше чем x (назовем их elts_lt_x), отсортировать все элементы xs которые больше, либо равны x (назовем их elts_greq_x), и объединить (++) результаты, поставив x между ними."
Определение elts_lt_x, которое дано следом, читается так: "elts_lt_x это список всех y таких, что y является элементом списка xs, и y меньше чем x". elts_greq_x определено таким же образом. Синтаксис похож на обычную математическую запись, где "|" произносится как "такие, что", а "<-" — как "принадлежит множеству (здесь: является элементом списка)".
При сортировке непустого списка qsort вызывает себя для сортировки elts_lt_x и elts_greq_x. Все в порядке, потому что оба этих списка меньше, чем список, переданный как аргумент qsort, так что процесс разделения и сортировки однажды приведет к сортировке пустого списка, что тривиальным образом производится первой строкой qsort.
Сравните с программой на С:
qsort( a, lo, hi ) int a[], hi, lo;
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
t = a[l];
a[l] = a[hi];
a[hi] = t;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Естественно, жизнь — это не только музыка и цветы. Вариант quicksort на C использует чрезвычайно эффективную технику, изобретенную Хоаром, где массив сортируется на месте, без использования дополнительной памяти. В результате, quicksort на С выполняется быстрее. В противоположность ему, программа на Haskell выделяет «за сценой» достаточно много памяти, и, соответственно, выполняется медленнее.
Фактически, quicksort на С реализует предельно эффективную технику управления памятью, разменивая простоту реализации на эффективность.
В приложениях, где требуется производительность любой ценой, или когда целью является тонкая низкоуровневая оптимизация, императивный стиль программирования будет лучшим выбором, чем функциональный, поскольку он предоставляет более полный контроль над процессом выполнения программы.
Но немногие программы требуют производительности любой ценой! В конце концов, мы уже давно прекратили писать программы на ассемблере, кроме, возможно, ключевых внутренних циклов и других избранных мест. Преимущества более удобной программной модели (большое количество именованых локальных переменных вместо ограниченного количества регистров, например) существенно перевешивают недостатки в виде [потенциально] меньшей скорости выполнения. [Когда-то было и "кинетически", но в наше время уже "потенциально" — программист на ассемблере практически не способен сгенерировать более эффективный код, чем современные компиляторы, например IC++.]
Так же, мы готовы мириться с накладными издержками виртуальной страничной памяти, в обмен на более удобную программную модель бесконечного виртуального адресного пространства. Дни явного управления оверлеями прошли — многие ли теперь знают, что это такое?
Функциональные языки представляют собой очередной шаг к более высокоуровневой программной модели, сокращая «семантическую пропасть» между постановкой задачи и реализацией. Программы становятся проще в разработке и поддержке, но применение функционального стиля оставляет программисту меньше контроля над машиной. Во многих случаях результат получается вполне адекватен.
Здравствуйте, Кодёнок, Вы писали:
Кё>Неужели кто-то на лиспах отбивает скобки пробелами, по-моему черт знает что получается
Э-э-э... Виноват, буду знать.
G>Естественно, жизнь — это не только музыка и цветы. Вариант quicksort на C использует чрезвычайно эффективную технику, изобретенную Хоаром, где массив сортируется на месте, без использования дополнительной памяти. В результате, quicksort на С выполняется быстрее. В противоположность ему, программа на Haskell выделяет «за сценой» достаточно много памяти, и, соответственно, выполняется медленнее.
Вообще то память дополнительная используется.
Вот здесь, на стеке.
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
И вообще быстрая сортировка на то и быстрая, что используется разумное отношение между используемой дополнительно памятью и временем.
M>Вот здесь, на стеке. M>qsort( a, lo, l-1 ); M>qsort( a, l+1, hi );
Кто сказал, что здесь стек?
M>И вообще быстрая сортировка на то и быстрая, что используется разумное отношение между используемой дополнительно памятью и временем.
Это только в отношении массивов, я так думаю.
Для списков сортировка слиянием однозначно лучше.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, Трурль, Вы писали:
Т>А еще лучше без лямбды. Т>
Т>(define (sum from total)
Т> (if (= 0 from)
Т> total
Т> (sum (- from 1) (+ total from))))
Т>
Выглядит всё равно заумно, ни на грамм не проще императивного цикла. Получается, чтобы почуять выгоду функциональщины на сложных вычислениях (а годится ли функциональщина где-нибудь ещё, кроме вычислений?), нужно сначала сполна хлебнуть её недостатков на простых вычислениях?
Здравствуйте, Дм.Григорьев, Вы писали:
ДГ>Выглядит всё равно заумно, ни на грамм не проще императивного цикла. Получается, чтобы почуять выгоду функциональщины на сложных вычислениях (а годится ли функциональщина где-нибудь ещё, кроме вычислений?), нужно сначала сполна хлебнуть её недостатков на простых вычислениях?
Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.
Во вторых в декларативном стиле на порядок больше повторная используемость, ФВП рулят, и очень часто оказывается что на уровень рекурсивных функции отпускатся нет никакой необходимости, все прекрасно решается с помощью комбинации примитивных (типа этой sum) ФВП.
Здравствуйте, FR, Вы писали:
FR>Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, FR, Вы писали:
FR>>Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.
V_>Предлагаю посмотреть на алгоритм Флойда
Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.
Здравствуйте, FR, Вы писали:
V_>>Предлагаю посмотреть на алгоритм Флойда
FR>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.
Ничего не мешает, но это будет не очень просто в отличие от императивного стиля. Вообще многие алгоритмы на графах по сути своей императивны и плохо переносятся на чистые функциональные языки.
Здравствуйте, Vintik_69, Вы писали:
FR>>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.
V_>Ничего не мешает, но это будет не очень просто в отличие от императивного стиля. Вообще многие алгоритмы на графах по сути своей императивны и плохо переносятся на чистые функциональные языки.
Где там будет не просто?
Практически сложность будет одинакова.
Здравствуйте, Vintik_69, Вы писали:
FR>>Где там будет не просто? FR>>Практически сложность будет одинакова.
V_>Сложность в каком смысле? Код вроде бы будет посложнее все-таки, не такой простой, как три цикла.
Практически такой же, сложность одного порядка и главное можно даже на автомате преобразовать.
А вот куча рекурсивных алгоритмов на практике или вообще не приводятся к итерации или результат на порядок сложней.
FR>>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию. V_>Ничего не мешает, но это будет не очень просто в отличие от императивного стиля. Вообще многие алгоритмы на графах по сути своей императивны и плохо переносятся на чистые функциональные языки.
V_>Я имел в виду то, что "классические" алгоритмы на графах в прямую на функциональных языках переписываются плохо. Впрочем, это все не так уж и важно.
Посмотрел на твои сообщения внимательно.
Вкратце, твое сообщение парой уровней выше можно свести к "императивные алгоритмы плохо переносятся на функциональные языки."
Я подозреваю, что надо добавить "если делать бездумно."
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)