Comments
Сам SQL, точнее его DML часть, является декларативной (не полной по Тюрингу, но тем не менее) — из плюсов все то что перечислено в статье, из минусов — оптимизатор иногда подтупливает слегка — имперетивно можно предложить более эффективное решение, но декларативно это не возможно выразить.
Декларативно всегда легче сформулировать цель — не убий, ну укради...., но без императивных подзаконных актов это не работает.
Императивный подход пришел из жизни потому что он там работает.
Совсем недавно в MSSQL добавляли функции ранжирования, а вот в новых стандартах уже и оконные функции — было что-то не удобно, можно это учесть и доработать…
Еще в начале 2000-х был разработан Transact-SQL (T-SQL) — процедурное расширение языка SQL, созданное компанией Microsoft (для Microsoft SQL Server) и Sybase (для Sybase ASE). Сам пользовался в Sybase.
Это в очередной раз подтверждает, что декларативный подход в чистом виде неудобен для программирования.
Вы считаете оконные функции элементом декларативного подхода к программированию?
Конечно, это способ избавится от обработки данных циклами.
вот пример
SELECT bid_date,
MAX(bid_amount)
OVER (ORDER BY bid_date
ROWS BETWEEN UNBOUNDED PRECEDING
AND CURRENT_ROW) AS high_bid_amount FROM Auction_Log;

Блин! Опять быстрая сортировка! Вы рискуете распугать тех, кто действительно заинтересован декларативным подходом и призвать троллей. Это, увы, не самый лучший пример. Дело в том, что хоаровский вариант реально быстр и сортирует на месте. Рекурсивный же только записывается красиво, но хоаровским, увы, не является. Это разные алгоритмы с разными свойствами. Об этом уже много раз писали на разных языках, статьи легко гуглятся. Главный аргумент троллей: евангелисты-декларативщики опять и опять приводят два-три примера неработающих алгоритмов! В хаскеллевском Data.List используется mergesort, поскольку сам по себе quicksort непрактичен и в функциональной реализации жаден до памяти. Декларативный подход серьезно играет в большем: в построении реактивных систем, в алгебраическом описании сложных архитектур, в принципиальной доказуемости декларативных утверждений. Я понимаю и полностью разделяю восхищение, испытываемое при первом знакомстве с ленивым "решетом Эратосфена" на Хаскеле (которое тоже вовсе не оно), или тем же рекурсивным quicksort, но прошу: не останавливайтесь на этом! Мы не должны выглядеть евангелистами с одними и теми же простыми притчами, у функционального и логического программирования есть гораздо больше классных результатов. Правда, они сложнее . А главное: не противопоставляйте парадигмы. Это мешает искусству владения ими всеми.

Спасибо, может немного и наивно получилось, но выразить декларативно сортировку слиянием, у меня выходит без обращений к первоисточнику, а вот представить себе алгоритм (Фон-Неймана)[http://www.sql.ru/forum/719824/sortirovka-sliyaniem] в алгоритмическом виде — совсем не просто.
Есть принцип сортировки, а он алгоритмический или декларативный, вот это меня интересует, как мы представляем себе вычисления?
Как вы формулируете решения, удобно ли задумываясь о последовательности действий?

Может и правда хватит изучать императивные языки, а что для вас более привлекательно?

Аналогично, зачем стричь ногти, когда есть топор?
Мы как путешественники по своим мыслям, и анализаторы своего состояния, должны понимать где хорошо, а где иначе, где же именно мы находимся, вот к этому хочу привлечь внимание читателей.

Чтобы понимать, где хорошо, а где иначе, полезно бы уметь выражать свои мысли.


Как мы складываем цепочки мыслей,

По-разному. А вам это не очевидно?


выражать все последовательностью команд и переходов между ними, мне кажется архаичным и устаревшим

Рецепты вам тоже кажутся "архаичными и устаревшими"?


Мне кажется, если выражать программу логическим языком, она будет выглядеть понятнее

Вам кажется. Программы бывают разные, и для разных программ удобнее разные способы выражения.

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

Вы, простите, много знаете о том, как готовят шеф-повара? Про, скажем, сложные десерты во французском стиле?

При небольшой разнице в производительности

На глаз — qsort всего процентов на пятьдесят дольше выполняется. Совершенно небольшая разница. Незначительная.

Вот, правильное замечание, там два генератора списка, которые сканируют весь список целиком, а если заменить это на один цикл, какая будет разница по скорости?
По поводу примера на Эрланге:
qsort([H|T])->qsort([X||X<-T,X<H]++[H|qsort([X||X<-T,X>=H])].

Тут закрывающая круглая скобка не пропущена, случайно?
Да, похоже, вот работающий пример
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].


А вот так, работает еще быстрее:
qsort2([])->[];
qsort2([H|T])->{S1,S2}=part(H,T,[],[]),qsort2(S1)++[H|qsort2(S2)].

part(_,[],S1,S2)->{S1,S2};
part(H,[H1|T],S1,S2) when H1<H->part(H,T,[H1|S1],S2);
part(H,[H1|T],S1,S2)->part(H,T,S1,[H1|S2]).

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


===Мысль вслух.===


Декларативность может идти в разных направлениях:


1) Контрактное программирование.
Мы расписываем все предусловия, инварианты, постусловия до самых мелочей, — и вуаля, если у нас последнее постусловие — "набор состоит из тех же элементов, что были на входе, и упорядочен", — мы описали сортировку. Плюс, конечно, мы должны расписать проблему остановки, а потом напихать эвристик для выбора более-менее эффективной стратегии среди прочих равновозможных.


2) Наглядное программирование.
Мы декомпозируем задачу на детальки, каждая из которых очевидным образом решает свою подзадачу, — получаем самодокументируемый код.
Сводим к минимуму залезание в чужие зоны ответственности, — именно это ставится в упрёк императивному программированию, где практикуется переприсваивание значений, и пойди отследи кто что когда.


Иммутабельность — это не самоцель, а полезная фишечка. Так-то мы спокойно можем рассмотреть изменяемый массив как некую функцию от времени на массивы: в каждый отсчёт времени (после каждой правки) — новый массив.
А если потом завернём в какую нибудь идеологию CPS и/или STM, — получим мутабельность поверх иммутабельности (или просто мутабельность, но с битьём по пальцам при желании вспомнить ушедшее былое).




===Мысль вслух.===


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


В этом нет никакой декларативности! Декларативно было бы — "здесь мы выполняем одну операцию над набором данных в цикле!", вот операция, вот набор, давай-мапь-редюсь!




У квиксорта есть две большие беды.


Первое: честная рекурсия, в силу того, что задача разбивается на две подзадачи. И если один из вызовов мы можем вывернуть мясом наружу и превратить в концевую рекурсию, то второй-то уж точно никак. Тут нам пригодится эвристика, говорящая о том, что — давайте будем проваливаться в более короткую подзадачу, а более длинную оставлять на десерт.


Второе: при неудачном стечении обстоятельств декомпозиция вырождается в линейную. Соответственно, N памяти (если только мы не исхитримся с концевыми рекурсиями) и N**2 времени.
Тут нам пригодится другая эвристика, говорящая следующее: нам, в общем-то, пофиг, как именно будут отсортированы подмассивы.


Код на псевдо-эрланге, не тестировал, не обессудьте. Чисто пруф оф концепт.


qsort([]) -> [];
qsort(Xs) ->
  {Ls, X, Rs} = partition(Xs),
  qsort(Ls) ++ [X] ++ qsort(Rs).

% переделаем на концевую

sort(Xs) -> qsort_tail([], Xs).  % голова - упорядочена и меньше хвоста

qsort_tail(Hs, []) -> Hs;
qsort_tail(Hs, [X]) -> Hs ++ [X];
qsort_tail(Hs, Xs) ->
  {Ls, X, Rs} = partition(Xs),
  qsort_tail(Hs ++ sort(Ls) ++ [X], Rs).

% переделаем на концевую с эвристикой - куда лучше сваливаться

sort(Xs) -> qsort_tail([], Xs, []). % голова и хвост упорядочены и меньше-больше середины

qsort_tail(Hs, [], Ts) -> Hs ++ Ts;
qsort_tail(Hs, [X], Ts) -> Hs ++ [X] ++ Ts;
qsort_tail(Hs, Xs, Ts) ->
  {Ls, X, Rs} = partition(Xs),
  if length(Ls) < length(Rs) ->
    qsort_tail(Hs ++ sort(Ls) ++ [X], Rs, Ts);
  true ->
    qsort_tail(Hs, Ls, [X] ++ sort(Rs) ++ Ts)
  end.

% напишем сортировку более тупую, но гарантирующую логлинейное время
heapsort(Xs) -> sort_heap(make_heap(Xs)).

% и более медленную (квадратичную) на больших наборах, но стремительную на маленьких
introsort(Xs) -> ?????. % лень выдумывать

sort(Xs) -> sort(Xs, 0).

sort(Xs, Depth) when length(Xs) < ThresholdOfIntrosort -> introsort(Xs);
sort(Xs, Depth) when Depth > ThresholdOfRecursion -> heapsort(Xs);
sort(Xs, Depth) -> qsort_tail([], Xs, [], Depth+1).

Примерно так работает std::sort в реализациях C++ для современных компиляторов — gcc, clang, VS. Ну, только с той разницей, что там всё inplace.


Кстати! Вы можете сказать: "зачем ты делаешь [X] ++ Ts, это же неэффективно? Почему не [X|Ts]?"
Да, неэффективно по скорости. Хотя и единообразно.
Но мы ведь можем сформулировать задачу сортировки так:


  • разбить массив на кучу внутренне упорядоченных и взаимно упорядоченных массивов
  • а потом склеить их одним махом

sort(Xs) -> flatten(sorted(Xs)).
sorted(Xs) -> qsort_tail([], Xs, []).

qsort_tail(Hs, [], Ts) -> [Hs, [], Ts];
qsort_tail(Hs, Xs, Ts) ->
  {Ls,X,Rs} = partition(Xs),
  if length(Ls) < length(Rs) ->
    qsort_tail( [Hs, sorted(Ls), [X]], Rs, Ts );
  true ->
    qsort_tail( Hs, Ls, [[X], sorted(Rs), Ts] ).

(вот это — вообще пруф оф концепт, тут я специально оставил за кадром ряд возникающих проблем, которые мне лень решать на псевдоэрланге)

О, мой вопрос, в каком виде храниться или рождается мысль, как появляется следствие — решение задачи из полученных требований. какое количество входов требуется проанализировать, сортировка списка или массива, это один из входов на получение выхода "подход к сортировке", надо учесть, что каждая отдельная структура будет иметь свой эффективнейший способ обработки, для данных на магнитной ленте потребуется метод слияний и никаких быстрых сортировок не реализовать, а для Питона-массива не надо получать хвост как [1:]
Упрощение мыслей и получение более коротких упрощений, позволяет точнее формулировать решение задачи — тут перебор, а тут энлогарифм, и это решает то, какой способ выбран для описании, какова будет структура программы, накладывает структура данных и способ конвертирования данных, появляются накопительные параметры, только как промежуточное состояние, которое по цепочке приводит к нужному следствию...


А если Питону представить список как составной терм, как структуру из головы и хвоста, или кортеж из двух элементов, то уместно будет обработать его рекурсивно:


def qsort(lst):
  if lst==None: return None
  else:
      h,t=lst
      slst, ulst=parts(h,t)
      return app(qsort(slst),(h,qsort(ulst)))

def app(a,b):
  if a==None: return b
  else:
    h,t=a 
    return (h,app(t,b))

def parts(a,lst):
  if lst==None: return (None,None)
  else:
    h,t=lst
    mlst,ulst=parts(a,t)
    if h>a: return (mlst, (h,ulst))
    else: return ((h,mlst), ulst)

def flattern(lst):
  if lst==None: return None
  else:
   if type(lst) is tuple: 
     h,t=lst 
     return app(flattern(h),flattern(t))
    else: return (lst, None)

А если хвостовую рекурсию?, он превратит в цикл или просто в "гоуту"… или тут сборщик мусора все потянет на себя?

stackless python, возможно, и будет снисходителен к концевой рекурсии.
Но, скорее всего, даже ему сплохеет.
А уж референтные реализации CPython и PyPy — точно вычерпают весь стек.


Концевая рекурсия — это такое рукодельное неявное continuation passing style.
Это как на фортране — ты пишешь цикл, а компилятор такой "эге! здесь же векторная, а то и матричная, операция! дай-ка вставлю векторную команду или вызову функцию из библиотеки линейной алгебры!"


Беда в том, что интерпретаторы питона не настолько сильны, чтобы говорить "эге!"


Поэтому лучше выражать операции над списками именно через операции над ними — в виде циклов, генераторных выражений, вызовов функций высшего порядка.
Концевая рекурсия — это некоторая свёртка. Поэтому мы можем декомпозировать её на элементарную операцию и на диспетчерский код, выполняющий забег в цикле. (Возможно, что это будет явно написанный цикл :) )


Кстати, для настраивания мозгов рекомендую статью Эрика Мейера "бананы, линзы, конверты и колючая проволока" — про всевозможные разновидности преобразования списков.
Нашёл только английский пдф https://maartenfokkinga.github.io/utwente/mmf91m.pdf — вроде, кто-то брался переводить на русский, но то ли заглохло, то ли утонуло в поисковой выдаче.


И ещё момент. Конс-пары безжалостны к памяти.
В языках, где конс-пары являются фундаментальным типом — а это практически все ФП и пролог, — куча устроена так, чтобы как можно дешевле хранить огромную тучу пар. Например, отдельно пул памяти для пар, отдельно для атомов, и отдельно — для больших объектов.
В питоне все примитивные структуры — это массивы переменной длины. Даже кортеж содержит, помимо своих данных, ещё заголовок объекта с указателем на тип, счётчиком ссылок и размером массива…
Получается, на каждый элемент списка мы разворачиваем рядом кортеж.
Ну и поскольку кортежи и прочие данные ничем особо друг от друга не отличаются, то все они хранятся в одном общем пуле и бешено фрагментируют его.
Как игрушечный код — можно делать список по-лисповски. Как промышленный — лучше даже не пробовать.

Only those users with full accounts are able to leave comments. Log in, please.