declarative
Dec. 25th, 2012 01:34 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать 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
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-25 07:20 am (UTC)======
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор).
В выходном потоке байт Х <= 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.
======
В-общем, спецификации декларативны. (Может, ещё что-то декларативно, я не знаю).
Язык тестов, например, очень близок к языку спецификаций, т.е. декларативен.
Идея декларативности в том, что для большинства задач "условие" проще "решения".
no subject
Date: 2012-12-25 07:30 am (UTC)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
no subject
Date: 2012-12-25 07:30 am (UTC)И как бы выглядела достаточная спецификация на формализованном языке? Процитированная как минимум неполна - не описана связь входа и выхода.
no subject
Date: 2012-12-25 07:47 am (UTC)rle [1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200]
Декларативное просто говорит сделай мне.
no subject
Date: 2012-12-25 07:49 am (UTC)> построить дерево такое-то и т.д. - это все про "как"
Это не обязательно императивно, и не обязательно "как". "Императивность" означает (имхо) всего лишь необходимость работать в темпоральной логике при доказательстве свойств программ. Императивный код вполне может быть декларативным - например, многие спецификации пишутся в псевдокоде.
"Как" (имхо) всего лишь означает, что мы жестко прибиваем гвоздями способ решения.
Гипотетическая запись fold foo . map bar . unfold baz может означать как конкретный способ решения, так и множество возможных решений, в зависимости от спецификации языка, т.е. быть как декларативной, так и нет.
Более того, чем более зрелый у языка компилятор - тем более декларативно можно на нём писать. Подсказки компилятору - антидекларативны.
no subject
Date: 2012-12-25 07:52 am (UTC)no subject
Date: 2012-12-25 07:52 am (UTC)no subject
Date: 2012-12-25 07:57 am (UTC)no subject
Date: 2012-12-25 07:58 am (UTC)no subject
Date: 2012-12-25 08:01 am (UTC)no subject
Date: 2012-12-25 08:02 am (UTC)no subject
Date: 2012-12-25 08:03 am (UTC)no subject
Date: 2012-12-25 08:07 am (UTC)no subject
Date: 2012-12-25 08:11 am (UTC)no subject
Date: 2012-12-25 08:36 am (UTC)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 foofoo по умолчанию жадный
На рефале вроде можно что то похожее сделать, но давно это было, не уверен.
no subject
Date: 2012-12-25 08:53 am (UTC)no subject
Date: 2012-12-25 09:27 am (UTC)1, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200?
no subject
Date: 2012-12-25 09:29 am (UTC)1) для Лист1 и Лист2 проверять, является ли Лист2 ужатнадо явым Лист1
2) для Лист2, который ужат, востанавливать Лист1, который его оригинал.
К сожалению из обычный лист Лист1 он не ужимает, потому что с его точки зрения, Лист1 является валидной сжатием самого себя.
А заставить его ужимать уже сложнее, надо явно считать одинаковые элементы, изымать их, специальным образом обрабатывать элементы больше 192, короче не очень декларативно пока получается
no subject
Date: 2012-12-25 09:30 am (UTC)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?
no subject
Date: 2012-12-25 09:32 am (UTC)Первое, с чем мы столкнемся при написании rle, это нечеткость постановки задачи. Исходно сказано было: сделать по формату. А подразумевается: сделать оптимально.
Неоптимальное решение - тупо снабжать каждый символ префиксом 193, и оно очень легко декларируется.
Эрго, мы или не вводим в декларацию проверку оптимальности, и на выходе получаем что попало в формате рле, или вводим и получаем тотальный перебор решений. (пролог это сумеет).
Значит, придется тащить эвристики. Например, рассмотреть несколько видов контекста (головы списка), которые очевидно (программисту) надо кодирлвать именно таким способом, а не другим. А это уже императив...
Да и на таком декларативном языке, как пролог, можно схитрить и написать программу, которая выдаст лучшее решение сразу, но если кому хочется доказать, что оно лучшее, то переберет и все остальные пути. Выглядеть будет как декларативное, но мы-то знаем :-)
no subject
Date: 2012-12-25 09:45 am (UTC)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]Единую спецификацию я пока даже на словах не придумал.
no subject
Date: 2012-12-25 10:01 am (UTC)Видимо, это некоторая логика. Причём, такая, чтобы описание в ней было сильно более краткое, по сравнению с операционной семантикой. И возможно, что ещё бы и сильно более другое описание.
Например, интуиционистская логика, видимо, не подходит. Или критерии другие. А что подходит?
Видимо, формулировки теорем могут восприниматься, как декларативное. А их доказательство, как решение.
no subject
Date: 2012-12-25 10:04 am (UTC)no subject
Date: 2012-12-25 10:04 am (UTC)no subject
Date: 2012-12-25 10:06 am (UTC)