declarative

[thedeemon]

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

Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать RLE методом по мотивам формата PCX: в выходном потоке байт Х <= 192 обозначает сам себя, а байт Х > 192 означает Х-192 повторений следующего за ним байта. Т.е. последовательность
1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200
должна превращаться в
194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200

Comments

[norguhtar.livejournal.com]

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

[thesz.livejournal.com]

Почитайте про суперкомпиляцию и дистилляцию (distillation: extracting the essence of program).

[norguhtar.livejournal.com]

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

[thesz.livejournal.com]

Нет, вы неправильно понимаете.

[norguhtar.livejournal.com]

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

[thesz.livejournal.com]

Distillation, например, меняет сложность алгоритмов. С О(N^2) до O(N). Это не выражение функций через более простые.

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

То есть, вы пишите как вам на душу легло - декларативно, - а на выходе эффективно.

[norguhtar.livejournal.com]

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

[nealar.livejournal.com]

Притом, что декларативное описание - настолько неконкретное, что под него подходят алгоритмы с разной сложностью. И поэтому умный компилятор может тут что-то вырулить. А если юзер выразил алгоритм с чётким требованием "хочу N²", то не будет же компилятор с ним спорить!