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

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

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

Далее мы рассмотрим программную реализацию нейронной сети Хопфилда, предназначенную для распознавания образов. Она предложена Хопфилдом в 1984 году, а на данный момент разработаны многочисленные её усовершенствования, однако мы рассмотрим именно оригинальную модель.

Каждый нейрон сети получает и передаёт сигналы другим. То, как нейроны связаны между собой, зависит от типа сети. Сеть Хопфилда является однослойной сетью, потому что в ней используется лишь один слой нейронов. Она так же является рекурсивной сетью, потому что обладает обратными связями. Она функционирует циклически. Взгляните на пример сети Хопфилда из четырёх нейронов. Каждый из них имеет выходы сигнала, который подаются на входы всех остальных нейронов, кроме себя самого:

Однако эту сеть нельзя научить практически ничему. Нам нужно намного больше нейронов. Сеть, содержащая N нейронов может запомнить не более ~0.15*N образов. Так что реальная сеть должна содержать достаточно внушительное количество нейронов. Это одно из существенных недостатков сети Хопфилда – небольшая ёмкость. Плюс ко всему образы не должны быть очень похожи друг на друга, иначе в некоторых случаях возможно зацикливание при распознавании.

Как работает сеть

Образ, который сеть запоминает или распознаёт (любой входной образ) может быть представлен в виде вектора X размерностью n, где n – число нейронов в сети. Выходной образ представляется вектором Y с такой же размерностью. Каждый элемент вектора может принимать значения: +1 либо -1 (Можно свести к 0 и 1, однако +1 и -1 удобнее для расчётов).

Конечно, в нашей программной реализации мы не будем непосредственно работать с нейронами, а всего лишь эмулировать их работу при помощи векторов и матрицы коэффициентов

Обучение сети

Как было сказано, обучение сети строится на вычислении весовых коэффициентов. Для этого мы будем поддерживать матрицу W размером n x n. При обучении сети некому образу X коэффициенты устанавливаются так:

for i in range(0,n):
    for j in range(0,n):
        if (i == j):
            self.W[i][j] = 0
        else:
            self.W[i][j] += self.X[i] * self.X[j]

Если нам нужно обучить сеть следующему образу, мы просто меняем вектор X и заново повторяем эту процедуру. Вы видите, в элементах матрице сохраняется сумма значений для всех образов, которым мы обучили сеть. Установка значения элемента в 0 при i==j это отражения устройства сети, когда выход некого нейрона не попадает на его же вход.

Распознавание образа

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

В идеале сеть распознает образ и выдаст на выход эталонный вектор, соответствующий искажённому.

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

Сеть выполняет следующую работу пока результат не совпадёт с одним из эталонным образов, либо не привесится порог итераций. Случайным образом выбирается нейрон r для обновления. Для него рассчитывается новое состояние s, используя нашу матрицу коэффициентов следующим образом:

net = 0
for i in range(0, n):
    net += Y[i] * W[i][r]
s = signum(net)

А затем мы обновляем его состояние:

Y[r] = s

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

Пример

Посмотрим как наша реализация сети сможет распознать образы букв. Мы будем представлять их в виде «битовых полей» размера 7х7. Так, имея три эталонных образа и один образ для распознавания, эмуляция нейронной сети даёт следующий результат:

Known Shapes:
- @ @ @ @ @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -

@ @ @ @ @ @ @
- - - @ - - -
- - - @ - - -
- - - @ - - -
- - - @ - - -
- - - @ - - -
- - - @ - - -

@ - - - - - @
@ - - - @ @ -
@ - - @ - - -
@ @ @ - - - -
@ - - @ - - -
@ - - - @ @ -
@ - - - - - @

Teaching...

Modified shape:

@ @ - - - - -
@ - - - @ @ -
@ - - @ - - -
- - @ - - - -
@ - - @ - - -
@ - - - @ @ -
@ @ - - - - @

Shape recognizing...

Neuron   6 : -1  ->   1
Neuron  43 :  1  ->  -1
Neuron  21 : -1  ->   1
Neuron  22 : -1  ->   1
Neuron   1 :  1  ->  -1

Success. Shape recognized in 94 iterations:

@ - - - - - @
@ - - - @ @ -
@ - - @ - - -
@ @ @ - - - -
@ - - @ - - -
@ - - - @ @ -
@ - - - - - @

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

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

Teaching...

[ вырезано ]

Modified shape:
@ @ @ @ @ @ @
- @ - @ - @ -
- @ - @ - @ -
- @ - @ - @ -
- @ - @ - @ -
- @ - @ - @ -
- @ - @ - @ -

Shape recognizing…
Neuron  12 :  1  ->  -1
Neuron   6 :  1  ->  -1
Neuron  40 :  1  ->  -1
Neuron   0 :  1  ->  -1
Neuron  22 :  1  ->  -1
Neuron  17 :  1  ->  -1
Neuron  31 :  1  ->  -1

Fail. Shape not recognized in 273 iterations…
- @ @ @ @ @ -
- @ - @ - - -
- @ - - - @ -
- - - @ - @ -
- @ - - - @ -
- @ - @ - - -
- @ - @ - @ -

Однако запустив программу несколько раз мы сможем наблюдать и такой вариант, когда сеть всё же смогла распознать образ П (а не Т, поскольку входящий образ больше похож именно на П):

Shape recognizing...
Neuron   0 :  1  ->  -1
Neuron  22 :  1  ->   0
Neuron  17 :  1  ->  -1
Neuron   6 :  1  ->  -1
Neuron  31 :  1  ->  -1
Neuron  10 :  1  ->  -1
Neuron  38 :  1  ->  -1
Neuron  22 :  0  ->   1
Neuron  45 :  1  ->  -1
Neuron  24 :  1  ->  -1

Success. Shape recognized in 116 iterations:
- @ @ @ @ @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -
- @ - - - @ -

Заключение

В данной статье была продемонстрирована простая реализация нейронной сети Хопфилда, формирующую ассоциативную память. Как было показано, вся работа сводится к вычислению весовых коэффициентов сети. Здесь опущена вся математика, так что заинтересованному читателю предлагается самостоятельно обратиться к соответствующей литературе за дополнительной информацией.

Исходные коды программы доступны здесь.

Если что-то ходит как утка, и крякает как утка, то будем относиться к этому как к утке. Так неформально описывается принцип утиной типизации (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 лямбда-функции – это, по сути, делегаты, но для них предусмотрен специальный упрощённый синтаксис.

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

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