понедельник, 19 ноября 2012 г.

Декларативное и императивное программирование


Вступление
Допустим, наше приложение тем или иным образом хранит информацию о странах и городах мира. Предположим, что нам нужно вывести все города, начинающиеся на букву "V", расположенные в странах, которые начинаются на "R". Представим, что программа написана на Java без использования СУБД, и данные хранятся в обыкновенных коллекциях. Тогда код получения требуемых городов может иметь вид:

for(Country country : countryList){
            if(country.getName().startsWith("R"))
                for(City city:country.getCityList())
                    if(city.getName().startsWith("V")){
                        //что-то делаем с городом
                    }
        }

Теперь пусть приложение использует СУБД, к примеру, Oracle. Теперь данные можно извлечь посредством простого запроса:

select ctr.name country_name, c.name city_name, c.city_id
            from countries ctr, cities c
        where 1=1
              and c.country_id = ctr.country_id
              and ctr.name like 'R%'
              and c.name like 'V%'

Чем отличаются эти два способа извлечения данных? Помимо синтаксических отличий есть одно очень важное разграничение. В первом случае мы задаем инструкции, пошаговое выполнение которых приводит к извлечению нужных данных, а во втором - описываем данные, которые хотим получить, предоставляя СУБД возможность решить самостоятельно, каким способом эти данные извлечь. Первый подход называется императивным, а второй - декларативным. Рассмотрим эти понятия более подробно

Как становится ясно из приведенных примеров, языки подобные Java ( С++, C#, JavaScript) являются императивными, в то время как SQL - декларативный язык. Является ли он единственным примером декларативного языка?

Нет. К примеру, HTML, задающий то, как выглядит веб-страница, является декларативным. Декларативными же являются и каскадные таблицы стилей (CSS). Последние как раз хорошо подходят для сравнения с императивным языком JavaScript - ведь многие визуальные эффекты для элементов страницы можно реализовать обоими способами - как задать декларативно с помощью CSS, так и реализовать алгоритм на JavaScript.

Сами по себе пользовательские интерфейсы являются примером таких задач, где декларативный подход однозначно выигрывает. HTML-подобная разметка, задающая внешний вид пользовательского интерфейса является гораздо наглядней, скажем, последовательности инструкций вида mainForm.add(topPanel,BorderLayout.NORTH), которые можно встретить при формировании пользовательского интерфейса оконных приложений посредством библиотеки JavaSwing.

Еще пример - пакеты для автоматизации сборки Java-проекты. В сценарии сборки Apach Ant мы задаем последовательность действий, в то время как в дескрипторе проекта для Apache Maven декларативно описываем структуру проекта и взаимодействие его компонентов с внешней средой.

Границы.

Являются ли описанные подходы "чистыми", или же в действительности эти парадигмы могут смешиваться? Является ли, к примеру, программирование на Java исключительно императивным, или же примеси декларативного подхода тоже могут иметь место?

Декларативность в Java
Конечно, же в чистом виде ни той ни другой парадигмы не существует. Например, что происходит при вызове метода sort класса java.util.Arrays ? Мы сообщаем системе, что хотим получить массив отсортированным, и получаем его. Метод сортировки нас при этом не интересует, нам важен лишь результат - отсортированный массив. Да, этот вызов - инструкция, вызов метода, который тоже состоит из инструкций. Но ведь и вызов SQL-запроса в конечном виде порождает последовательность инструкций, выполняющихся в соответствии с планом оптимизатора. Процессоры могут работать только императивно, поэтому всякие декларативные описания в конечном итоге все равно превращаются в последовательность инструкций, вопрос лишь в количестве промежуточных звеньев.

Итак, вызов Arrays.sort() имеет декларативные черты. Противоположной императивной реализацией является самостоятельно выполненная сортировка. Надо сказать, что кое-какая информация о методе сортировки, нам все-таки иногда может потребоваться. Если массив состоит из объектов, и отношение порядка задано по конкретному полю(назовем его ключом), то нас может заинтересовать, как будут расположены после сортировки объекты с одинаковыми ключами(ведь другие характеристики объекта не обязаны совпадать). В этом отношении алгоритмы сортировки бывают стабильными и нестабильными. Стабильный алгоритм сортировки гарантирует сохранность порядка элементов с одинаковыми ключами, нестабильный, соответственно, - нет.

Реализации Arrays.sort() для примитивных типов используют нестабильный QuickSort, так как никаких других полей попросту нет, и в первую очередь важна скорость сортировки. При сортировке же объектов используется стабильный MergeSort. Но это является как раз еще одним аргументом в пользу декларативной сортировки - мы можем узнать требуемые свойства алгоритма (к примеру из документации), не заостряя внимание на деталях его реализации.

Другой пример - синхронизированные методы в многопоточном программировании. Конструкцию synchronized, относящуюся к методу или блоку кода, можно заменить блокированием и освобождением объектов Lock в начале и конце требуемого участка кода соответственно. Однако в первом случае мы просто говорим что помеченный код является критическим для разделяемого объекта, не вдаваясь в подробности реализации этой синхронизации, а во втором - самостоятельно ее реализуем.

Императивность в Oracle SQL
Вообще, декларативные языки обычно более "чисты", но иногда императивность может просачиваться и в них.

Как происходит обработка SQL-запросов в СУБД Oracle? Первым делом происходит синтаксический разбор запроса, потом семантическая проверка, затем поиск запроса в library cache, на случай, если он уже оптимизировался. Если запроса в кэше не оказалось, то происходит оптимизация запроса, которая заключается в построении его плана, то есть как раз на этом этапе происходит преобразование декларативного запроса в последовательность действий по извлечению данных из БД.

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

Поэтому разработчики СУБД Oracle включили в ее состав средство, позволяющее влиять на построение плана. Речь идет о хинтах, или подсказках оптимизатору. С помощью хинта можно указать конкретный способ соединения или доступа к данным. Естественно, их использование всегда является крайним случаем - жестко задав алгоритм действий, мы лишаем оптимизатор возможности подстроиться к изменившейся обстановке.

На стыке - PL/SQL
В разрезе данной темы весьма интересным является программирование на PL/SQL. PL/SQL является императивным языком, однако в него очень тесно интегрирован SQL, и мы имеем возможность переключать парадигму в буквальном смысле.

Если бы запрос, приведенный мной во вступлении, был частью процедуры PL/SQL-пакета, то тех же результатов можно было добиться следующим вложенным циклом:

for c_country in (select ctr.country_id
                        ,ctr.name country_name
    from countries ctr 
                        where ctr.name like 'R%')     
loop
 for c_city in (select c.city_id
                     , c.name city_name 
         from cities c
                   where 1=1 
         and c.name like 'V%' 
        and c.country_id = c_country.country_id)
  loop
   -- какие-то действия
  end loop;
end loop;

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

Поэтому крупнейший специалист по Oracle Том Кайт в своей книге "Oracle для профессионалов" приводит следующую "мантру":
  • если  можно,  сделай  это  с  помощью  одного  оператора  SQL;
  • если  это  нельзя  сделать с  помощью одного оператора  SQL,  сделай  это  в  PL/SQL;
  • если  это  нельзя  сделать  в  PL/SQL,  попытайся  использовать хранимую  процедуру на  языке Java;
  • если  это  нельзя  сделать в Java,  сделай  это  в  виде  внешней  процедуры  на языке  С;
  • если  это  нельзя  реализовать  в  виде  внешней  процедуры  на  языке  С,  надо  серьезно  подумать,  зачем  это  вообще делать...

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

Если можно, сделай это декларативно

Почему в большинстве случаев следует написать Arrays.sort(someObjects) вместо того, чтобы реализовывать сортировку самому? Да просто потому, что проблема сортировки изучается уже не первое десятилетие, и на настоящий момент вряд ли можно найти что-то более эффективное, чем то, что реализовано в стандартной библиотеке. Потому что сортировка в стандартной библиотеке может быть реализована с учетом особенностей виртуальной машины, которых рядовой разработчик может не знать. Потому что за Java SDK стоит много умных людей, в конце концов.

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

То же относится и к synchronized. Если нужны какие-то более тонкие манипуляции с блокировками, то объекты Lock к вашим услугам. Иначе все за вас сделает synchronized.

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

Предпочтительность декларативного SQL императивному PL/SQL уже была продемонстрирована, поэтому общий принцип можно сформулировать так:
  • если можно, сделай это декларативно
  • если декларативная реализация не удовлетворяет требованиям, сделай это императивно

5 комментариев:

  1. Хорошая статья, знаний прибавилось

    Спасибо

    ОтветитьУдалить
  2. Огромное спасибо! Первый источник, после прочтения которого у меня осталось ощущение, что я понял разницу и суть этих подходов.

    ОтветитьУдалить
  3. Все понятно, большое спасибо

    ОтветитьУдалить
  4. Да, хоть более-менее понял суть и отличия =) Спасибо.

    ОтветитьУдалить