Что это
От: Adopt  
Дата: 06.06.05 04:29
Оценка:
Что такое Декларативное программирование?
В чем различие от ООП допустим или от функционального?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Императивное и декларативное программирование
От: Oyster Украина https://github.com/devoyster
Дата: 06.06.05 06:33
Оценка: 16 (2) +2
#Имя: FAQ.declprog.defines
Здравствуйте, Adopt, Вы писали:

A>Что такое Декларативное программирование?

A>В чем различие от ООП допустим или от функционального?

Попробую ответить... хотя плохо во всём этом разбираюсь

Есть программирование императивное и программирование декларативное. В императивном программировании программа представлена в виде набора действий, которые должны быть выполнены (т.е. эдакий ассемблер высокого уровня). Т.е. код описывает решение задачи. Типичные представители императивных языков — C, Pascal, BASIC.

В идеале декларативного программировании код описывает саму задачу (а не один из способов её решения, как в императивном). Например, атрибуты в C# — это элемент декларативного программирования. Применяя к методу атрибут DllImport[], мы декларируем тот факт, что должна быть использована библиотечная функция, а в какой машинный код это в итоге превратится — нас не волнует. Представители декларативных языков: Lisp, ML, Prolog, Haskell...

Часто декларативные языки содержат элементы императивных (OCaml, например) и наоборот (всё тот же C#).

Вот так вот... может, немного расплывчато — но как смог.

А ООП — это вообще методика, т.е. нечто из другой оперы. Принципы ООП можно использовать как в императивном (C++, Java, Object Pascal), так и в декларативном (OCaml, Haskell [imho то, что есть в Хаскеле, тоже имеет отношение к ООП]) программировании.

PS: функциональное программирование — это подвид декларативного (как и логическое). Т.е. Haskell — это чисто функциональный язык декларативного программирования

PPS: ссылок не подкину, но в форуме должны быть.
Что такое «функциональный язык»
От: Gaperton http://gaperton.livejournal.com
Дата: 06.06.05 11:12
Оценка: 63 (8) +1
#Имя: FAQ.declprog.funclang
Здравствуйте, 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++.]

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

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

Re[2]: Что это
От: Кодёнок  
Дата: 16.06.05 10:32
Оценка:
Здравствуйте, Gaperton, Вы писали:

Scheme:

( define sum
   ( lambda ( from total )
       ( if ( = 0 from )
           total
           ( sum ( - from 1 ) ( + total from ) ) ) ) )
( sum 10 0 )


Неужели кто-то на лиспах отбивает скобки пробелами, по-моему черт знает что получается

Лучше классика:
(define sum
   (lambda (from total)
       (if (= 0 from)
           total
           (sum (- from 1) (+ total from)))))

(sum 10 0)


Или так:
(define sum
   (lambda (from total)
       (if (= 0 from)
           total
           (sum (- from 1 ) (+ total from)) 
       ) 
   ) 
)

(sum 10 0)
Re[3]: Что это
От: Gaperton http://gaperton.livejournal.com
Дата: 16.06.05 10:47
Оценка:
Здравствуйте, Кодёнок, Вы писали:

Кё>Неужели кто-то на лиспах отбивает скобки пробелами, по-моему черт знает что получается

Э-э-э... Виноват, буду знать.
Re[3]: Что это
От: Трурль  
Дата: 17.06.05 05:44
Оценка:
Здравствуйте, Кодёнок, Вы писали:

Кё>Лучше классика:

Кё>
Кё>(define sum
Кё>   (lambda (from total)
Кё>       (if (= 0 from)
Кё>           total
Кё>           (sum (- from 1) (+ total from)))))

Кё>(sum 10 0)
Кё>


А еще лучше без лямбды.
(define (sum from total)
   (if (= 0 from)
       total
       (sum (- from 1) (+ total from))))
Re: Что такое «функциональный язык»
От: maggot  
Дата: 12.10.07 22:15
Оценка:
Здравствуйте, Gaperton, Вы писали:

G>Естественно, жизнь — это не только музыка и цветы. Вариант quicksort на C использует чрезвычайно эффективную технику, изобретенную Хоаром, где массив сортируется на месте, без использования дополнительной памяти. В результате, quicksort на С выполняется быстрее. В противоположность ему, программа на Haskell выделяет «за сценой» достаточно много памяти, и, соответственно, выполняется медленнее.

Вообще то память дополнительная используется.
Вот здесь, на стеке.
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
И вообще быстрая сортировка на то и быстрая, что используется разумное отношение между используемой дополнительно памятью и временем.
Re[2]: Что такое «функциональный язык»
От: thesz Россия http://thesz.livejournal.com
Дата: 13.10.07 00:16
Оценка:
M>Вот здесь, на стеке.
M>qsort( a, lo, l-1 );
M>qsort( a, l+1, hi );

Кто сказал, что здесь стек?

M>И вообще быстрая сортировка на то и быстрая, что используется разумное отношение между используемой дополнительно памятью и временем.


Это только в отношении массивов, я так думаю.

Для списков сортировка слиянием однозначно лучше.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re: Что это
От: thesz Россия http://thesz.livejournal.com
Дата: 13.10.07 00:25
Оценка:
A>Что такое Декларативное программирование?
A>В чем различие от ООП допустим или от функционального?

Точного различия тебе не даст никто, я думаю.

Вот для примера несколько языков:
— SQL
— make

Они получают на входе (частичное) описание проблемы, а не метод ее решения.

Оба имеют внутри себя сложную систему выполнения и оптимизации запросов.

SQL не Тьюринг-полный, в отличии от варианта make в версии GNU.

Среди декларативных языков часто можно встретить, как раз, не Тьюринг полные.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[4]: Что это
От: Дм.Григорьев  
Дата: 13.10.07 04:51
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>А еще лучше без лямбды.

Т>
Т>(define (sum from total)
Т>   (if (= 0 from)
Т>       total
Т>       (sum (- from 1) (+ total from))))
Т>


Выглядит всё равно заумно, ни на грамм не проще императивного цикла. Получается, чтобы почуять выгоду функциональщины на сложных вычислениях (а годится ли функциональщина где-нибудь ещё, кроме вычислений?), нужно сначала сполна хлебнуть её недостатков на простых вычислениях?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
http://dimgel.ru/lib.web — thin, stateless, strictly typed Scala web framework.
Re[5]: Что это
От: FR  
Дата: 13.10.07 06:04
Оценка:
Здравствуйте, Дм.Григорьев, Вы писали:

ДГ>Выглядит всё равно заумно, ни на грамм не проще императивного цикла. Получается, чтобы почуять выгоду функциональщины на сложных вычислениях (а годится ли функциональщина где-нибудь ещё, кроме вычислений?), нужно сначала сполна хлебнуть её недостатков на простых вычислениях?


Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.
Во вторых в декларативном стиле на порядок больше повторная используемость, ФВП рулят, и очень часто оказывается что на уровень рекурсивных функции отпускатся нет никакой необходимости, все прекрасно решается с помощью комбинации примитивных (типа этой sum) ФВП.
Re[6]: Что это
От: Vintik_69 Швейцария  
Дата: 13.10.07 09:57
Оценка:
Здравствуйте, FR, Вы писали:

FR>Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.


Предлагаю посмотреть на алгоритм Флойда
Re[7]: Что это
От: FR  
Дата: 13.10.07 11:37
Оценка:
Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, FR, Вы писали:


FR>>Во первых есть куча алгоритмов которые очень просто реализуется декларативно — рекурсивно, а императивно очень сложно и практически нет обратных примеров.


V_>Предлагаю посмотреть на алгоритм Флойда


Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.
Re[8]: Что это
От: Vintik_69 Швейцария  
Дата: 13.10.07 12:30
Оценка:
Здравствуйте, FR, Вы писали:

V_>>Предлагаю посмотреть на алгоритм Флойда


FR>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.


Ничего не мешает, но это будет не очень просто в отличие от императивного стиля. Вообще многие алгоритмы на графах по сути своей императивны и плохо переносятся на чистые функциональные языки.
Re[9]: Что это
От: FR  
Дата: 13.10.07 13:26
Оценка:
Здравствуйте, Vintik_69, Вы писали:

FR>>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.


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


Где там будет не просто?
Практически сложность будет одинакова.
Re[10]: Что это
От: Vintik_69 Швейцария  
Дата: 13.10.07 14:04
Оценка:
Здравствуйте, FR, Вы писали:

FR>Где там будет не просто?

FR>Практически сложность будет одинакова.

Сложность в каком смысле? Код вроде бы будет посложнее все-таки, не такой простой, как три цикла.
Re[11]: Что это
От: FR  
Дата: 13.10.07 15:00
Оценка:
Здравствуйте, Vintik_69, Вы писали:

FR>>Где там будет не просто?

FR>>Практически сложность будет одинакова.

V_>Сложность в каком смысле? Код вроде бы будет посложнее все-таки, не такой простой, как три цикла.


Практически такой же, сложность одного порядка и главное можно даже на автомате преобразовать.
А вот куча рекурсивных алгоритмов на практике или вообще не приводятся к итерации или результат на порядок сложней.
Re[9]: Что это
От: thesz Россия http://thesz.livejournal.com
Дата: 13.10.07 21:12
Оценка: 18 (2) +1
FR>>Посмотрел, но не понял что мешает там развернуть циклы в рекурсию.
V_>Ничего не мешает, но это будет не очень просто в отличие от императивного стиля. Вообще многие алгоритмы на графах по сути своей императивны и плохо переносятся на чистые функциональные языки.

"Другой смолчал и стал пред ним ходить"

Как люди заменили императивные гарфы индуктивными и как у них после этого случилось всеобщее благорастворение в воздуцях.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[10]: Что это
От: Vintik_69 Швейцария  
Дата: 14.10.07 12:51
Оценка:
Здравствуйте, thesz, Вы писали:

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


Это понятно, есть еще интересная статья по индуктивным графам тут: http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz

Я имел в виду то, что "классические" алгоритмы на графах в прямую на функциональных языках переписываются плохо. Впрочем, это все не так уж и важно.
Re[11]: Что это
От: thesz Россия http://thesz.livejournal.com
Дата: 14.10.07 16:09
Оценка:
V_>Я имел в виду то, что "классические" алгоритмы на графах в прямую на функциональных языках переписываются плохо. Впрочем, это все не так уж и важно.

Посмотрел на твои сообщения внимательно.

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

Я подозреваю, что надо добавить "если делать бездумно."
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.