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

[kodt-rsdn.livejournal.com]

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

Собственно, претензии к императивному в том и состоят, что из описания "как" не видно "чего". А чистая декларативность - это блажь, оттуда не видно "как", причём не видно никому. У императивного-то кода есть автор, который видит "чего", так хоть какие-то шансы на работоспособностиь остаются :-)

[thedeemon.livejournal.com]

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

[kodt-rsdn.livejournal.com]

Компилятор хорошо справляется с изоморфизмами, переводит "как" в "как" с абстрактной человечной машины в процессорную.
Оптимизирующий компилятор может сглаживать человеческое несовершенство, заменяя, например O(n) цикл на O(1) формулу, хотя цикл был и нагляднее и описательнее :-)
Но вот чтобы не преобразовывать, а порождать алгоритмы по задаче, - тут компилятору помошник нужен. Хотя, для каких-то типовых задач достаточно может залезть в базу знаний и найти готовое?
Это и есть "эврика!" в смысле "нашел!"