Среди всех структур данных, имеющихся в распоряжении у замечательной науки информатики, есть одна, которой многие люди восхищаются больше, чем другими. Это – хеш-таблица (Hash Table), несомненное достижение в области компьютерных наук. Практически все современные языки программирования имеют реализации хеш-таблиц в своих библиотеках. Чаще всего мы работаем с ними в виде словарей (или ассоциативных массивов), представляющих собой контейнеры множества пар ключ-значение.

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

Введение в хеш-таблицы

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

• Добавление новой пары ключ-значение
• Поиск значения по ключу
• Удаление пары ключ-значение по ключу

Так, простой пример сессии работы с хеш-таблицой может выглядеть так (пример на Python):

>>> a = { "Vasya" : "123-23-12", "Petya" : "223-21-32" }
>>> a["Vasya"]
‘123-23-12′
>>> a["Masha"] = “264-32-32″
>>> a["Vasya"] = “000-00-00″
>>> a
{’Vasya’: ‘000-00-00′, ‘Petya’: ‘223-21-32′, ‘Masha’: ‘264-32-32′}

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

Что же такое хеширование? Идея хеширования основана на распределении ключей в обычном массиве H[0..m-1]. Распределение осуществляется вычислением для каждого ключа элемента некоторой хеш-функции h. Эта функция на основе ключа вычисляет целое число n, которое служит индексом для массива H. Конечно, необходимо придумать такую хеш-функцию, которая бы давала различный хеш-код для различных объектов.

Например, если в качестве ключа хеш-таблицы нам нужно использовать строки, то можно выбрать хеш-функцию, основанную на следующем алгоритме (пример на С):

int hash(char* str) {
    int h = 0;
    for (int i=0; i<strlen(str); i++)
        h = (h*C + ord(str[i])) % m;
}

Где m – размер хеш-таблицы, C – константна, большая любого ord(c), а ord() – функция, возвращающая числовой код символа. Для каждого типа данных можно разработать свою хеш-функцию. Однако есть основные требования к хеш-функции: она должна распределять ключи по ячейкам хеш-таблицы как можно более равномерно, и должна просто вычисляться.

Вот иллюстрация хеш-таблицы. Мы видим, что индексами ключей в хеш-таблице является результат хеш-функции h, применённой к ключу.

Так же этот рисунок иллюстрирует одну из основных проблем. При достаточно маленьком значении m (размера хеш-таблицы) по отношению к n (количеству ключей) или при плохой хеш-функции, может случиться так, что два ключа будут хешированны в одну и ту же ячейку массива H. Такая ситуация называется коллизией. Хорошие хеш-функции стремятся минимизировать вероятность коллизий, однако, учитывая то, что пространство всех возможных ключей может быть больше размера нашей хеш-таблицы H, всё же избежать их вряд ли удастся. На этот случай имеются несколько технологий для разрешения коллизий. Основные из них мы и рассмотрим далее.

Хеширование с цепочками

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

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

Процедура вставки выполняется даже в наихудшем случае за O(1), учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно O(n). Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время O(1). Ссылки на рассуждения и математические выкладки будут даны в конце статьи.

Хеширование с открытой адресацией

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

Для разрешения же коллизий применяются несколько подходов. Самый простой из них – это метод линейного исследования. В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Так, при достижении последнего индекса таблицы, мы перескакиваем в начало, рассматривая её как «цикличный» массив. Иллюстрация этого способа представлена на следующем рисунке:

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

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

Практика. Хеширование и ООП-языки

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

• a.Equals(a) == true
• a.Equals(b) == b.Equals(a)
• Если a.Equals(b) и b.Equals(c), то а.Equals(c)
• Переопределяя в потомке Equals, следует переопределить и GetHashCode()
• Если a.Equals(b) == true, то a.GetHashCode() == b.GetHashCode()
• Значение a.GetHashCode() зависит только от внутреннего состояния объекта (его полней и свойств).

Так, реализация хеш-функции GetHashCode() зависит от класса объекта, и здесь мы можем использовать различные техники при расчётах.

Заключение

В статье было дано введение в хеш-таблицы. Однако многие темы остались за «бортом», например, методология подбора хорошей хеш-функции, и идеальное хеширование, при котором поиск даже в наихудшем случае выполняется за O(1). Так же формальный анализ и доказательства некоторых приведённых утверждений вы можете найти в литературе, обозначенной ниже.

Дополнительная литература

Тема хеширования достаточно широко описана в литературе. Следующие книги я могу рекомендовать в качестве авторитетных и достоверных источников информации:

• Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы. Построение и анализ. Издание 2-е, Вильямс, 2007 г. – Глава 11, страница 282.
• Дональд Э. Кнут – Искусство программирования, том 2. Получисленные алгоритмы, Вильямс, 2007 г. – Глава 6.4.
• Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы, Вильямс, 2000 г.
• Левитин – Алгоритмы. Введение в разработку и анализ, Вильямс, 2006 г. – Глава 7.3, страница 323.

Пример реализации хеширования с цепочками можно найти в следующей книге:

• Керниган, Пайк – Практика программирования. Издание 4-е, Вильямс, 2004 г. – Глава 2.9, страница 72.

Если что-то ходит как утка, и крякает как утка, то будем относиться к этому как к утке. Так неформально описывается принцип утиной типизации (Duck Typing). Утиная типизация «развязывает нам руки», позволяя полиморфно работать с объектами, которые не связаны в иерархии наследования, но имеют необходимый набор методов. Здесь мы подходим к извечному спору о том, что лучше – динамическая или статическая типизация. Обойдём его стороной, сославшись на известную статью Мейера и Дрейтона под названием «The End of the Cold War Between Static and Dynamic Languages», и лучше посмотрим, как реализовать «утиное» поведение на Java.

Зачем мне эти утки?

Зачем может нам понадобиться утиная типизация в Java? Например, мы работаем с классом, к исходному коду которого мы не имеем доступа. Этот класс, как и некоторые наши собственные, имеет некий одинаковый набор методов, так что мы хотели бы работать со всеми этими классами через единый интерфейс. Если для наших классов мы можем залезть в исходный текст и указать, что они реализуют этот интерфейс, то с чужими классами такое не пройдёт. Конечно, мы можем написать класс-адаптер, или обвёртку, которая реализует необходимый интерфейс и вызывает нужные методы. Но мы можем выполнить всё это «на лету», воспользовавшись рефлексией, proxy-классами и прочими полезными штуками из пакета java.lang.reflect, эмулируя утиную типизацию.

Рассмотрим ситуацию на тривиальном примере. У нас есть интерфейс

  public interface IQuackable {
         void quack();
      }

И какие-то классы:

  public class Duck {
         public void quack () {
             System.out.println(“I am a Duck!”);
         }
     }

    public class Frog {
         public void quack () {
              System.out.println(“I am a Frog!”);
         }
     }

Видно, в определениях Duck и Frog не указано, что они реализует IQuackable, однако необходимый метод у них имеется. Мы хотим получить такое поведение:

    // ...
    IQuackable[] quakers = new IQuackable[] {
         Cast(IQuackable.class, new Duck()),
         Cast(IQuackable.class, new Frog())
    };   for(IQuackable q : quakers) {
          q.quack();
    }
    // …

Стоит отметить, что наши искомые классы должны быть объявлены с модификатором доступа public, иначе во время преобразования может возникнуть исключение java.lang.IllegalAccessException. Это требование обусловлено тем, что реализация должна иметь доступ к искомому классу, чтобы вызывать его методы.

Необходимость в использовании интерфейса вытекает из статической типизации Java. Например, в Groovy, который напрямую поддерживает динамическую и утиную типизацию, мы могли бы поступить так и обойтись без интерфейсов вовсе:

    class Duck {
        quack() { println "I am a Duck" }
    }
    class Frog {
        quack() { println "I am a Frog" }
    }

    quackers = [ new Duck(), new Frog() ]

    for (q in quackers) {
        q.quack()
    }

Реализация и Proxy-уточки

Вернёмся к Java, и посмотрим, как же всё это реализовать.

Так, мы создадим три статических метода, которые будут преобразовывать объекты к соответствующим интерфейсам:

• <I> I Cast(Class<I> i, Object o) – приводит ссылку на Object к ссылке на интерфейс I. o должен иметь соответствующий этому интерфейсу набор методов.
• <C> C UnCast(Class<C> c, Object o) – обратное преобразование.
• boolean CanCast(Class<?> i, Object o) – проверяет, может ли объект o быть приведён к соответствующему интерфейсу.

Прежде, чем приступить к реализации этих методов следует уделить время рассмотрению динамических proxy-классов, которые впервые появились в стандартной библиотеке Java 1.3. Они полезны в случае, когда программист на этапе разработки ещё не знает, какие интерфейсы ему предстоит реализовать. Proxy-классы особо полезны для генерации классов-заглушек в технологиях вроде RMI. Но здесь мы воспользуемся ими для эмуляции утиной типизации.

Подробную информацию можно найти на странице руководства.

Динамические proxy-классы реализуют интерфейсы во время выполнения. Каждый вызов методы этого класса через какой-то интерфейс приводит к вызову единственного метода объекта обработчика вызовов, в который передаётся информация о вызванном методе в виде объекта java.lang.reflect.Method и массив Object, содержащий аргументы. Внутри обработчика вызовов мы можем определить необходимое нам поведение. Однако мы не можем генерировать новый код во время выполнения, а всего лишь выполнять заранее подготовленный.

Мы создадим обработчик вызова DuckHandler, который будет вызывать необходимый метод на экземпляре искомого объекта. Сам искомый объект будем хранить внутри обработчика вызовов. Изображение всего этого в виде произвольной схемы будет выглядеть следующим образом:

Так, определение класса-обработчика:

    class DuckHandler implements InvocationHandler {
        public DuckHandler(Object t) {
            target = t;
            targetclass = target.getClass();
    }   @Override
    public Object invoke(Object p, Method m, Object[] args)
      throws Throwable {
        Method me = targetclass.getMethod(m.getName(),
                                         m.getParameterTypes());
        return me.invoke(getTarget(),args);
    }   public Object getTarget() {
        return target;
    }

    private Object target;
    private Class<?> targetclass;
}

Всё «мясо» находится в методе invoke. Видно, в ему передаётся экземпляр proxy-класса, который мы игнорируем, метод и аргументы.

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

    public static boolean CanCast(Class<?> i, Object o) {
        Class<?> c = o.getClass();
        for (Method method : i.getMethods()) {
            try {
                c.getMethod(method.getName(), method.getParameterTypes());
            }
            catch (NoSuchMethodException e) {
                return false;
            }
        }
        return true;
    }

Далее, само «преобразование». Перед созданием proxy-класса мы проверяем с помощью метода, определённого выше, может ли класс нашего объекта реализовать необходимый интерфейс. Если может, используя статический метод Proxy.newProxyInstance мы создаём proxy-класс. Первый аргумент этого метода – загрузчик класса, второй – массив интерфейсов, которые необходимо реализовать (у нас один интерфейс). И наконец, третий аргумент – обработчик вызовов. Сюда мы передаём экземпляр нашего класса, в котором сохраняется искомый объект о (помните, на нём вызываются все методы).

  @SuppressWarnings("unchecked")   public static <I> I Cast(Class<I> c, Object o) {   if (!CanCast(c, o))
             throw new ClassCastException();
         Object proxy = Proxy.newProxyInstance(
                     ClassLoader.getSystemClassLoader(),
                     new Class[]{c}, new DuckHandler(o));   return (I) proxy;
    }

Ну и обратный предыдущему метод, который принимает тип искомого класса и объект proxy-класса, и возвращает исходный объект. Он хранится внутри обработчика вызовов, так что получить его не составляет особого труда.

  @SuppressWarnings("unchecked")   public static <C> C UnCast(Class<C> c, Object o) {   DuckHandler h = (DuckHandler) Proxy.getInvocationHandler(o);   return (C) h.getTarget();
    }

Заключение

Утиная типизация представляется одной из тех вещей, без которых с успехом можно обойтись. Но в некоторых случаях она может прийтись весьма кстати, помогая сократить ручное кодирование. Так, в этой статье было рассмотрено, как с помощью рефлексии и динамических Proxy-классов Java добиться эмуляции такого «утиного» поведения. Была так же создана совсем крохотная инструментальная библиотека для демонстрации.

Исходный код вы можете загрузить отсюда.

Как раз во время написания статьи наткнулся на аналогичную. Вот ссылка: Java does Duck Typing (англ).

Как правило, языки программирования сами по себе не рождаются. Их создают для того, чтобы было легче писать программы. Или, чтобы было легче писать компиляторы других языков, на которых будет ещё легче (быстрее, надёжнее, интереснее) писать программы (или другие компиляторы). На сегодняшний день этих самых языков программирования существует уже сотни. Чтоб представить себе их разнообразие можно хотя бы бегло взглянуть на замечательный сайт «99 бутылок пива». И хотя все они (языки, хотя, и бутылки тоже) по-разному выглядят и воспринимаются, зачастую у них есть кое-что, что определяет их общность. Это – парадигма (или несколько парадигм), которой они отвечают.

Парадигма определяет то, какой способ написания программ предоставляет (к которому располагает) данный язык программирования. Парадигм существует тоже немало, и все они перекликаются друг с другом. Охватить все не ставилось задачей данной статьи, подробнее с данной темой можно познакомиться, например, на Википедии: http://ru.wikipedia.org/wiki/Парадигма_программирования. Далее мы рассмотрим несколько самых известных парадигм, и то, как они противопоставляются друг другу, и уживаются вместе в рамках отдельного языка.

Хочется отметить, что, по поводу того, какой язык или парадигма «лучше» ведутся вечные «священные войны». Я же не собираюсь вступать в них, и полагаю, что для каждой задачи существует свой более подходящий язык или модель программирования, с помощью которых она решается легче. Поэтому незачем ограничивать себя чем-то только одним, если можно использовать то, что лучше всего подходит в конкретном случае. А ещё лучше – комбинировать несколько подходов, чтобы получить плюсы (ну, или минусы, кому как) каждого.

Итак…

Всё по порядку…

Всем известно императивное программирование, в котором мы пишем программу в виде последовательности приказов, наподобие таких: «запиши значение 1643 в ячейку по адресу 66346» или «если a>10, то выпрыгни из окна». Это то, что мы делали на уроках Паскаля в школе, или при изучении Си ночью под подушкой с фонариком. Мы пошагово описываем компьютеру, что тот должен сделать, чтобы удовлетворить наши потребности. Мы изменяем переменные, используем ветвления с циклами, может быть, вызываем какие-нибудь функции. Эта парадигма настолько широко распространена, что, кажется, является общепринятой. Она лежит ближе всего к «железу», к тому, как работает компьютер. При первом знакомстве с программированием это впечатляет: я пишу магические команды, а эта железяка их исполняет, и ровно так, как я хочу, и никак иначе ;). По сути, перед нами красуется послушная машина Тьюринга.

Мы можем организовывать указания в процедуры, выделяя часто используемые части, объединять их в модули. Однако суть не меняется, мы просто перечисляем команды. Это позволяет писать достаточно высокопроизводительный код, поскольку обычно мы можем себе представить, во что выльются наши программные конструкции, когда над ними поработает компилятор (а иногда и не можем представить, особенно если мы сделали что-то вроде -O3, попросив помощи у проворного оптимизатора).

Например, в Си, нам разрешено многое – мы можем писать за пределы массива, не освобождать выделенную память, путешествовать и портить её при помощи указателей и так далее. В более высокоуровневых языках, например, Java, таких вольностей нам не позволит виртуальная машина. Однако мы всё равно можем писать недетерминистические методы, т.е., такие, которые возвращают разные значения при одних и тех же входящих параметрах. Очевидно, многие методы объектно-ориентированных языков являются таковыми: им неявно передаётся параметр this, который мы и можем изменять на своё усмотрение. В Си тот же недетерминизм и наличие побочных эффектов (изменение каких-то внешних данных) мы можем получить, используя глобальные или статические переменные в наших функциях:

int myglobalvar = 100;
...
...
int MyFunc(int n) {      return myglobalvar += n;
}

При увеличении количества и сложности кода уследить за нашими командами, структурами данных, да и за потоком исполнения программы становиться очень сложно, так что многие предпочитают уже упомянутое объектно-ориентированное программирование. Оно позволяет обернуть императивные приказы в методы объектов, а дальше уже работать непосредственно с ними, «посылая» им «сообщения»: «Раз ты фигура, нарисуй себя!» или «Вася, я не знаю, кто ты, человек или холодильник, но вижу, что ты реализуешь интерфейс ISleepable, так что бегом спать!». В данном случае мы выходим на новый уровень абстракций, пользуясь знаменитыми «китами»: инкапсуляцией, наследованием и полиморфизмом. Объектно-ориентированная парадигма породила множество идей и замечательных языков, которые её воплотили. Мы заботимся о повторном использовании кода, и ООП позволяет отлично с этим справляться. На данный момент ООП считается наиболее важной моделью программирования. Все знают или слышали о C++, Java, C#, и так далее (хоть и не все из перечисленных языков «чистые» объектно-ориентированные). В конечном итоге, мы опять же пишем императивный код, хоть и спрятанный за абстракциями в методах. Но мы уходим от ужасов глобальных переменных и всем доступных данных, и работаем с отдельными сущностями, каждая из которых занимается только своей отдельный задачей.

Объекты одного класса обладают своим состоянием, которые их отличает, и общим набором операций. Для изменения состояния мы снова используем методы с «побочными эффектами» (C#):

class ToggleSwitch
{     public void Toggle()      {         _isOn = !_isOn;     }         public bool IsOn()     {        return _isOn;     }        public override String ToString()     {         return String.Format("Toggled {0}", _isOn ? "On" : "Off");     }    private bool _isOn;
}

То, что методы имеют «побочные эффекты» нисколько не означает, что они «плохие». Здесь эти «побочные эффекты» как раз и являются сутью, поскольку с их помощью мы меняем состояние объекта.

Просто такие методы (как функции) нельзя назвать правильными функциями в строго математическом смысле. В этом есть и свои плюсы, и свои минусы. А если бы они были таковыми? Как и всё математическое, мы получили бы нечто элегантное, но в чистом виде весьма далёкое от практики. Мы можем писать «чистые» функции на любых языках программирования, но за этим нам придется следить самим, а ограничиваясь только такими функциями, мы потеряли бы многие преимущества императивного и объектно-ориентированного программирования. В ООП мы меньше задумываемся о функциях, а больше о классах, объектах, иерархиях наследования, инкапсуляции и отношениях объектов.

Пойди туда, не знаю куда…

Другой парадигмой, кардинально отличающейся от императивной, является декларативная парадигма программирования. В декларативных языках мы уже не программируем в терминах команд. Мы описываем то, что хотим получить, а как мы это получим – уже задача транслятора. Главное предоставить исчерпывающую информацию. Например, с помощью языка SQL мы декларативно описываем то, что хотим от нашей базы данных, а то, что будет происходить далее нас мало волнует: «Дайте мне имена всех студентов, у которых средний был меньше 3, которые умеют стоять на голове, и упорядочьте их по убыванию лексикографически». Мы оперируем «высокоуровневыми» проекциями, пересечениями, объединениями и так далее.

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

Функциональное программирование (ФП) позволяет представить программу в виде функций, в математическом их смысле. Здесь функция – это правило, которое некоторому элементу из области определения ставит в соответствие некоторый элемент из области значений. Таким образом, функция для данного аргумента всегда даст один и тот же результат. А ещё, поскольку функция – это правило, она не может менять «глобальных» или каких-то других переменных. Здесь вообще нет «переменных», как мы их понимаем в императивных языках. В функциональном программировании, переменная один раз получившая значение больше не может его изменить. Это кажется ужасным, как программировать в мире, где объекты не могут изменяться? Как оказывается, программировать можно, и даже очень эффективно.

ФП строится на формальной теории лямбда-исчисления. Вы можете изучить его математические основы, ознакомившись с работами его создателя, Алонзо Чёрча. Но нам, как программистам, более важно то, что мы можем получить в своём коде.

«Чистое» функциональное программирование накладывает довольно строгие ограничения на язык, так что «чистых» функциональных языков не много. Как осуществлять ввод-вывод без функций с побочными эффектами? По сути, ввод-вывод – императивный, и тут никуда не деться. Так что каждый функциональный язык всё же должен какой-то своей частью «соприкоснуться» с императивным миром, поскольку иначе он рискует остаться лишь очень красивым абстрактным инструментом, при помощи которого ничего толком нельзя сделать.

Хватит говорить! Как найти факториал с помощью твоего языка? Возьмём, например, Haskell:

fac :: Integer -> Integer
fac 0 = 1
fac n | n > 0 = n * fac (n - 1)

Первая строчка, в общем, не обязательна, поскольку компилятор сам способен вывести типы. Вообще, вывод типов в функциональных языках достаточно мощный и обычно основывается на модели типизации Хиндли – Милнера. Данная тема широко освящена в соответствующей литературе.

Интересно то, что функции можно передавать как параметры другим функциям, возвращать из функций, и делать с ними что угодно. Здесь функции являются, как говорят, объектами первого класса.

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

# List.map (fun x -> x*x) [1;5;10;20];;
- : int list = [1; 25; 100; 400]

Мы передали функции map другую функцию в качестве первого параметра, которая и будет применяться к каждому элементу списка. Таким образом, map – это функция высшего порядка.

Просто, для сравнения, если бы мы тоже хотели сделать на Java, нам бы, по крайней мере, пришлось создавать объект нового класса, пусть даже и анонимного. Вообразим, что у нас есть функция map, и интерфейс IMappable:

interface IMappable<T> {     T Proceed(T a);
}

Тогда мы можем сделать так (не забывая сделать import java.util.*):

Iterable<Integer> res = map(     new IMappable<Integer>() {         public Integer Proceed(Integer a) {             return a*a;         }     }, new Arrays.asList( new Integer[] {1,5,10,20} ));

Даже с использованием анонимного класса вся эта штука выглядит довольно неуклюже. Здесь метод map мог быть реализован так:

public static <T> Iterable<T> map(IMappable<T> m, Iterable<T> A) {     ArrayList<T> newA = new ArrayList<T>();     for (T pe : A )         newA.add( m.Proceed(pe) );     return newA;
}

Помимо всего здесь идёт работа с обобщениями, что ещё больше усложняет дело. А вот как map может быть определена на функциональном OCaml:

# let rec map f a =     match a with       | [] -> []       | h::t -> (f h) :: (map f t);;
val map : (’a -> ‘b) -> ‘a list -> ‘b list = <fun>

Последняя строка показывает, какой тип для функции был выведен. Здесь мы имеем параметрический полиморфизм, так, map можно использовать с совершенно любыми списками.

Заметьте, в OCaml-версии у нас на выходе может получиться список элементов другого типа. В Java-версии, тип выходного Iterable должен быть тем же. Это ограничение можно исправить, добавив ещё один параметр обобщения в метод map. Вы можете самостоятельно над этим поэкспериментировать.

Функциональные языки имеют много интересных особенностей. Например, сопоставление с образцом, стражи, карринг, поддержка ленивых вычислений и бесконечных списков, и так далее. Здесь всё вроде бы гладко. Однако особые проблемы начинаются, как было сказано, когда мы начинаем говорить, например, о вводе-выводе. Каждый язык находит свою точку соприкосновения с императивным миром. В «чистых» языках, например, Haskell, это монады. В «не чистых», например, OCaml, всё же существует поддержка императивного программирования. Так что мы можем написать так (OCaml):

#  print_string "Hello World!\n"
Hello World!
- : unit = ()

Отсутствие побочных эффектов в функциональных языках позволяет обнаружить несколько замечательных вещей: так как наша программа – лишь набор функций, мы можем выполнять их относительно в любом порядке. Это открывает дверь к таким штукам, как автоматическое распараллеливание, горячая замена кода программы «на лету», и так далее.

Но самое интересное начинается, когда мы вдруг осознаём, что было бы неплохо объединить эти два мира…

Смешаем всё вместе

В последнее всё больше людей начинает интересоваться функциональными «штуками». И развитие объектно-ориентированных языков идёт на пути интеграции с функциональными возможностями. Так, такие языки как Ruby и Python поддерживают лямбда-функции и замыкания. Не так давно появился язык F#, очень похожий на OCaml, но с полной поддержкой платформы .NET. Всё популярнее становятся мультипарадигменные языки, вроде Nemerle, Scala. А новая версия C# 3.0 с расширениями LINQ вводит язык большое количество функциональных возможностей. Есть как сторонники, так и противники такой тенденции. Такими темпами языки, которые изначально задумывались как простые, например, Java, обрастут огромным количеством языковых расширений, которые кто-то может назвать просто «синтаксическим сахаром». Нужно ли смешение парадигм в рамках одного языка, или лучше иметь несколько простых языков, поддерживающих по одной парадигме?

Если вы знакомы с языком C#, взгляните на следующий код, вычисляющий число Пи по формуле Лейбница за N/2 итераций при помощи LINQ:

var pi = 4 * ((from i in Enumerable.Range(1, ITER_COUNT)
                where i % 2 != 0
                let sign = (i / 2) % 2 == 0 ? 1 : -1
                select  (double)sign / i).Sum()
               );

Как вам такой код? Довольно забавно, особенно в контексте обычного синтаксиса C#. Однако, с другой стороны, это может показаться ужасным.

Посмотрим, как императивность и функциональность можно смешать в C# 3.0 на примере с массивом. Вначале мы определяем класс расширения с функцией Map:

static class Util
{     public static IEnumerable<T> Map<T>(this IEnumerable<T> a,                                         Func<T, T> f)     {         foreach (T e in a)             yield return f.Invoke(e);     }
}

И теперь вот как мы можем получить массив, состоящий из квадратов каждого элемента исходного:

var res = new int[] { 2, 5, 10, 12 }.Map(x => x * x);

Ну и распечатаем его:

foreach (var e in res)     Console.Write("{0} ", e);

Func<T, T> представляет собой делегат, который принимает один аргумент типа T, и возвращает значение типа T. В С# 3.0 лямбда-функции – это, по сути, делегаты, но для них предусмотрен специальный упрощённый синтаксис.

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

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