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

[nponeccop.livejournal.com]

Как-то так:

======
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор).

В выходном потоке байт Х <= 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.
======

В-общем, спецификации декларативны. (Может, ещё что-то декларативно, я не знаю).

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

Идея декларативности в том, что для большинства задач "условие" проще "решения".

[thedeemon.livejournal.com]

Хитрец! :)

И как бы выглядела достаточная спецификация на формализованном языке? Процитированная как минимум неполна - не описана связь входа и выхода.

[tonsky.livejournal.com]

На гипотетическом как-то так:

deftask Есть последовательность байтов, нужно их сжать: в выходном потоке байт Х <= 192 обозначает сам себя, а байт Х > 192 означает Х-192 повторений следующего за ним байта.

deftest последовательность
1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200
должна превращаться в
194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200

[norguhtar.livejournal.com]

Если кратко то к примеру

rle [1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200]

Декларативное просто говорит сделай мне.

[thedeemon.livejournal.com]

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

[alll]

Вообще-то императивное тоже "просто говорит сделай мне". Только почему-то требует слишком уж много микроменеджмента.

[nponeccop.livejournal.com]

> "создать список такой-то, свернуть его так-то,
> построить дерево такое-то и т.д. - это все про "как"

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

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

Гипотетическая запись fold foo . map bar . unfold baz может означать как конкретный способ решения, так и множество возможных решений, в зависимости от спецификации языка, т.е. быть как декларативной, так и нет.

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

[thedeemon.livejournal.com]

Да, вот это прибивание гвоздями способа решения - это и есть потеря декларативности, по моим ощущениям.

[alexandr alexeev (from livejournal.com)]

Декларативное программирование - это миф. Даже в SQL вы принимаете во внимание наличие или отсутствие индексов или пишите запрос SELECT ... FROM ... WHERE id > $cursor LIMIT 50 вместо SELECT ... FROM ... LIMIT 100500, 50. В общем, говорите СУБД, не какие данные вам нужны, а как их нужно достать.

[thedeemon.livejournal.com]

Ну, всякие курсоры, триггеры и хранимки - это уже императивщина, да. Но база SQL, реляционная алгебра, все же декларативна, имхо.

[aisx.myopenid.com (from livejournal.com)]

> чисто гипотетическом

isequal :: int list -> bool
foo isequal ([x..] as l) = 
    case l.count of
    | 1 -> if x <= 192 then [x] else [193,x]
    | count -> [192 + count,x] 


foo :: [int] -> [int]
result = [1,1,2,3] |> patternMap foo 

foo по умолчанию жадный
На рефале вроде можно что то похожее сделать, но давно это было, не уверен.

[thedeemon.livejournal.com]

Есть несколько ошибок, но идея ясна.

[thedeemon.livejournal.com]

Похоже на рабочее решение. Но максимально ли оно декларативно? Достаточно ли записать алгоритм на F#, чтобы решение стало декларативным?

[voidex.livejournal.com]

А почему не в
1, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200?

[voidex.livejournal.com]

И почему бы не в
193, 1, 193, 1, 193, 2, 193, 3, 193, 2, 193, 2, 193, 2, 193, 200, 193, 0, 193, 200, 193, 200, 193, 200, 193, 200?

[gianthare.livejournal.com]

На Прологе можно сделать (очень) простенько предикат, который будет
1) для Лист1 и Лист2 проверять, является ли Лист2 ужатнадо явым Лист1
2) для Лист2, который ужат, востанавливать Лист1, который его оригинал.

К сожалению из обычный лист Лист1 он не ужимает, потому что с его точки зрения, Лист1 является валидной сжатием самого себя.

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

[thedeemon.livejournal.com]

>Лист1 является валидной сжатием самого себя

Не должон - одиночные значения больше 192 должны раздуваться при таком кодировании.

[kodt-rsdn.livejournal.com]

Очень неудобно писать на хачкелле и прологе с ведроида, поэтому на пальцах покажу.
Первое, с чем мы столкнемся при написании rle, это нечеткость постановки задачи. Исходно сказано было: сделать по формату. А подразумевается: сделать оптимально.
Неоптимальное решение - тупо снабжать каждый символ префиксом 193, и оно очень легко декларируется.
Эрго, мы или не вводим в декларацию проверку оптимальности, и на выходе получаем что попало в формате рле, или вводим и получаем тотальный перебор решений. (пролог это сумеет).
Значит, придется тащить эвристики. Например, рассмотреть несколько видов контекста (головы списка), которые очевидно (программисту) надо кодирлвать именно таким способом, а не другим. А это уже императив...
Да и на таком декларативном языке, как пролог, можно схитрить и написать программу, которая выдаст лучшее решение сразу, но если кому хочется доказать, что оно лучшее, то переберет и все остальные пути. Выглядеть будет как декларативное, но мы-то знаем :-)

[thedeemon.livejournal.com]

Сказано "сжать RLE методом", a "снабжать каждый символ префиксом 193" - это не "сжать". Но некоторая вольность трактовки имеется, и это нарочно.

[voidex.livejournal.com]

По факту описание задаёт только способ декодирования, и его можно переписать так:

unrle [] = []
unrle (x:xs)
    | x <= 192 = x : unrle xs
    | otherwise = replicate (x - 192) (head xs) ++ unrle (tail xs)

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

rle = concatMap rle' . group where
    rle' [x]
        | x <= 192 = [x]
        | otherwise = [193, x]
    rle' xs = [192 + length xs, head xs]

Единую спецификацию я пока даже на словах не придумал.

[gianthare.livejournal.com]

Прикольно. Но, реально, все на довольно специфическую фунцию group завязано. Т.е. я понимаю, что ее легко написать, но все же.

[nivanych.livejournal.com]

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

[lionet.livejournal.com]

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

[voidex.livejournal.com]

На гипотетическом и не существующем

unrle = stream
    head x where x ≤ 192 → [x]
    elems [x, y] where x > 192 → replicate (x - 192) y

rle = compress unrle

[Игорь Петров (from livejournal.com)]

По-моему, такое определение декларативности ни на что не годится. Зачем нужны определения? Во-первых, для коммуникации, а коммуникации не получится, когда определение каждый понимает по-своему. Во-вторых, для классификации, но и тут проблема, потому что отличать декларативный код от императивного это определение не позволяет. А все потому, что оно характеризует не код, а некое отношение к коду некоего программиста в некий момент времени.
Второе и третье (обсуждаемое там, естественно, первое) определения декларативности из википедии, например, не такие плохие:
2) Any programming language that lacks side effects (or more specifically, is referentially transparent)
3) A language with a clear correspondence to mathematical logic.

Второе, впрочем, испорчено "сайд-эффектами", так что лучше бы они ограничились тем, что после "or more specifically", да и третье не без недостатков.

[thedeemon.livejournal.com]

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

[ircicq.livejournal.com]

Декларативная запись не должна исключать собой никакое (разумное) решение задачи.
Если язык позволяет записать проблему так, что пользуясь формальными преобразованиями можно прийти от описания к любому алгоритму решения - язык декларативен.

[pphantom.livejournal.com]

А вот это не сойдет решение?

===
упрощение([X,X|T],[194,X|T]).
упрощение([A,X,X|T],[B,X|T]):-A>192,B is A+1.

упростить([],[]).
упростить(L,R):-упрощение(L,M),упростить(M,R).
упростить([H|T],[H|R]):-упростить(T,R).
===

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

[thedeemon.livejournal.com]

Да, вариант.

[valentin budaev (from livejournal.com)]

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

Программа при этом, конечно же, одна и та же.

То есть вы можете рассуждать о map f как об утверждении "аргумент - некоторый список, результат - список того же размера, элементы которого являются результатом применения f к элементам аргумента, причем результат применения f к i-тому элементу аргумента имеет i-тую позицию". А можете как о последовательности шагов: "разделить входной список на голову и хвост, применить f к голове, map f к хвосту, вернуть список, полученный из новых головы и хвоста".

Аналогично в вашим rle:

decodeBytes bytes = concat $ map decodeByte bytes
where
decodeByte x =
| x <= 192 = [x]
| x > 192 = replicate (x-192) x

можно воспринимать этот код как описание свойств decode, а можно - как указание вычислителю на действия, которые он должен выполнить.

[thedeemon.livejournal.com]

Код ужасно неправильный, но мысль ценная, спасибо.

[thinker8086.livejournal.com]

А не слишком ли простая задача? Я, конечно, понимаю, что двигаться надо от простого к сложному... Но трансляция из потока в другой поток, да ещё и правосторонняя грамматика - это тривиально. Если есть БНФ - это и являтся достаточным декларативным описанием.

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

[thedeemon.livejournal.com]

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

[raindog-2.livejournal.com]

compress = uncompress^_1
where
uncompress = fun(stream) {
x << stream, return x if x <= 192;
byte << stream, return (x-192).times(byte)
}

[thedeemon.livejournal.com]

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

[oleg kertanov (from livejournal.com)]

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

http://okertanov.github.com/2012/04/14/declarative-factorial

[thedeemon.livejournal.com]

Занятно, спасибо! Интерактивная подсветка показывает, как много на схеме получается синтаксического мусора.

[sassa-nf.livejournal.com]

Смотря что спецификацией считать. У вас задана спецификация формата, но не решения.

У меня такая вот спецификация решения:

Аксиома. Список RLE байт включает либо значения X <= 192, либо счётчик+192, за которым следует значение X.

Отсюда спецификация cons для списка RLE: Чтобы включить X в список, нужно либо скопировать X, если X <= 192, либо записать счётчик 192+1, за которым поставить X.


Но в итоге нас интересует сжатие.

Гипотеза. Сжатие происходит, когда список RLE байт включает X только если за ним до сжатия следует байт Y != X, или цепочка байт Y == X со счётчиком, равным максимальному значению 255. В противном случае за X до сжатия следует цепочка байтов Y == X, у которых после сжатия счётчик, который можно увеличить, либо Y <= 192 в этой цепочке встречается лишь один раз.

rlehead (x:xs) = if x <= 192 then x
                 else head xs

rletail (x:xs) = if x <= 192 then xs
                 else if x == 193 then tail xs
                 else (x-1):xs


rlecons x ys
  | null ys || head ys == 255 || rlehead ys /= x = if x <= 192 then (x : ys) -- спецификация cons говорит нам, как именно вставить X
                                                    else (193:x:ys)
  | otherwise = let y = head ys
                in if y <= 192 then (194:x: tail ys) -- спецификация решения говорит нам, что когда rlehead ys == x, то либо y == счётчик, который можно увеличить, либо y == собственно байт, а счётчик у цепочки == 1.
                   else (y+1): tail ys

rle [] = []
rle (x:xs) = rlecons x $ rle xs

[sassa-nf.livejournal.com]

в связи со спецификацией, имеет смысл newtype Rle = Rle [Word8] и переписать функции с указанием типа.

[sassa-nf.livejournal.com]

О. А как насчёт такой спецификации.

RleStream - это поток байт, где каждому байту соответствует счётчик. (очевидно, map (193,) bs)

Два RleStream эквивалентны, если из одного можно получить другой, сложив или разбив счётчики подряд идущих одинаковых байт. Это свойство транзитивно (т.е. два RleStream эквивалентны, если есть общий RleStream, которому равны оба). (очевидно, для построения эквивалентных списков нужна функция, смотрящая на два подряд идущих счётчика для одинаковых байт)

Rle сжатие - это построение RleStream с как можно меньшим количеством счётчиков.

Представление RleStream. Счётчик записывается в виде байта со значением счётчик+192, за которым следует байт, который в исходном потоке повтоялся указанное счётчиком число раз. Счётчик равный 1 можно опускать для значений байт X <= 192. По условию задачи счётчик должен помещаться в 1 байт, а потому не должен превышать значение 255-192. Это ограничение на степень сжатия, накладываемое представлением RleStream.

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

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

rle = compress . map (193,) where -- конвертируем в канонический RleStream пар "счётчик-байт"
  compress [] = []
  compress ((c,x):ys) {- для построения эквивалентного RleStream, 
нужно смотреть на два подряд идущих элемента, но последнего элемента может не быть, поэтому воспользуемся head и null -}
    | null ys || x /= snd $ head ys || c == 255 = if c == 193 && x <= 192 then x : compress ys {- обнаружена (максимально длинная) 
цепочка повторов -}
                                                  else c: x: compress ys
    | otherwise = compress $ (c-192 + (fst $ head ys), x):(tail ys) {- построение эквивалентного RleStream
путём сложения значений счётчиков по спецификации -}

Очевидно, compress может быть обобщён до сжатия произвольных RleStream (за счёт более общего способа построения для произвольных c >= 255).