`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Язык Erlang и программирование для мультиядерных процессоров

Статья опубликована в №48 (567) от 19 декабря

0 
 

История знает много примеров решений, которые опередили свое время и, не получив признания современности, отправлялись пылиться на полку. Сегодня IT-индустрия переживает очередной виток развития, вызванный переходом к многоядерным микропроцессорам, и сталкивается с новыми проблемами – например, рост количества ядер центрального процессора совсем не приводит к пропорциональному увеличению скорости исполнения приложений на нем. Быть может, наилучшее решение этой проблемы следует искать не в новых методах оптимизации прикладных программ, а в радикальной смене парадигмы программирования, оживив ранее забытые проекты?

На самом деле системы на Erlang вовсе не масштабируемые и не надежные. Это системы на Java такие. Системы на Erlang просто непробиваемы как скалы.
Вячеслав Ахмечет, Functional Programming For The Rest of Us, www.defmacro.org

Две парадигмы программирования

Язык Erlang и программирование для мультиядерных процессоров

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

При всем разнообразии языков программирования они делятся на два главных класса: императивные (процедурные, алгоритмические) и декларативные (аппликативные, функциональные). Главное отличие между ними – способ решения задачи: императивный подход описывает последовательность шагов для обеспечения необходимого результата (т. е. отвечает на вопрос «Как достичь решения?»), тогда как декларативный – сам результат (т. е. отвечает на вопрос «Что нужно получить?»).

Несмотря на то что декларативный подход занимает важное место в программных решениях (к примеру, к декларативным относятся языки HTML, XAML и SQL), когда речь идет не о языках разметки гипертекста, описания интерфейса или выборки данных, позиции декларативных языков гораздо скромнее – практически все популярные и используемые в индустрии языки программирования являются императивными.

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

Известно, что программа, написанная на императивном языке и преобразующая входные данные в выходные по какому-либо алгоритму на основе процесса пошагового вычисления, может быть выполнена на абстрактной вычислительной машине, теоретически обоснованной в 1936 г. английским ученым Аланом Тьюрингом (Alan Turing). Упрощенно машина Тьюринга представляет собой бесконечную ленту, разграфленную на клетки, и передвигающуюся по ней каретку, которая выполняет простые арифметические операции, считывает и записывает значения в клетки ленты.

Но гораздо менее известным остается факт, что в том же 1936 г. американский ученый Алонзо Черч (Alonzo Church) независимо от Тьюринга (и даже несколько раньше его) опубликовал статью по вопросам неразрешимой арифметики, ставшую основой так называемого лямбда-исчисления – раздела дискретной математики, изучающего вычисления как математический процесс. Лямбда-исчисление, как и машина Тьюринга, является описанием формальной вычислительной системы. В отличие от машины Тьюринга, базировавшейся на механическом представлении алгоритма как последовательности элементарных преобразований над данными, лямбда-исчисление построено на математических функциях, которые принимали функции в качестве параметров и возвращали функции в качестве результата.

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

Лямбда-исчисление послужило теоретической базой для особой категории декларативных языков – функциональных, первым из которых стал LISP, созданный в 1958 г.

Есть еще одна разновидность декларативных языков программирования – логические языки, основанные на исчислении предикатов (самый известный из них – Prolog, созданный в 1972 г.). Не останавливаясь на рассмотрении логического программирования, отметим только, что по своим фундаментальным принципам оно близко к функциональному, существуют даже функционально-логические языки, такие как Mercury. Далее, когда мы будем говорить о декларативном программировании, то будем иметь в виду прежде всего функциональное программирование, поскольку язык Erlang принадлежит именно к этому классу.

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

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

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

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

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

История проекта Erlang

Разработка Erlang началась с момента основания компанией Ericsson исследовательской лаборатории Ericsson Computer Science Laboratory (CSLab) в 1981 г. Занималась она вопросами совершенствования технологий, используемых при разработке телекоммуникационных систем, и одной из первых задач, стоящих перед ней, была реализация параллелизма в языке Prolog.

Ранее никаких упоминаний об отдельном языке не было, поскольку исследователи фактически расширяли возможности языка Prolog, однако в 1987 г. начался первый серьезный эксперимент с применением теоретических разработок для реализации практических задач, и появились первые упоминания о языке Erlang. Несмотря на то что данное название может быть истолковано как сокращение от Ericsson Language, согласно официальной версии, оно происходит от фамилии датского математика Агнера Крарупа Эрланга (Agner Krarup Erlang, 1878–1929), известного своими исследованиями в сфере телекоммуникаций, в честь которого названа также мера телекоммуникационного трафика в телефонии.

Хотя Erlang уже получил название, до 1990 г. он не имел своего синтаксиса и мог считаться диалектом Prolog. Напомним, что Prolog принадлежит к языкам логического программирования, а Erlang – функционального, поэтому, чтобы сделать язык выразительнее и одновременно избавиться от тени Prolog, в 1990 г. синтаксис языка был переработан, а интерпретатор Prolog заменен значительно более эффективной собственной виртуальной машиной. Именно этот год следует считать годом рождения языка в современном понимании, а его коммерческое распространение началось в 1993 г., когда компания Ericsson сформировала независимое подразделение Erlang Systems AB.

В 1995 г. компания Ericsson признала неудовлетворительными и прекратила работы над проектом по созданию ATM-коммутатора нового поколения, которые длились с 1987 г., и решила повторно запустить его «с нуля» на основе Erlang. Через три года, в достаточно краткие сроки для проекта подобного уровня, был отгружен первый коммутатор AXD301, программная часть которого, написанная на Erlang, насчитывала свыше 1,7 млн строк кода, что на текущий момент является абсолютным рекордом для программ, созданных на основе функционального программирования.

В конце 1998 г. язык Erlang, а также набор библиотек под названием OTP (The Open Telecom Platform) были опубликованы под открытой лицензией на сайте erlang.org. С этого момента на Erlang реализовано множество проектов разного уровня сложности, а армия его сторонников ежегодно пополняется тысячами новобранцев.

В доступный для загрузки с сайта erlang.org дистрибутив для платформы Windows входят компилятор языка, среда исполнения с поддержкой эмуляции многопроцессорных систем, документация, а также набор библиотек и инструментов OTP, среди которых следует отметить Mnesia – написанную полностью на Erlang распределенную СУБД с поддержкой репликации данных и возможности динамического изменения их схемы и обновления своего кода без приостановки работы. Mnesia использует Erlang в качестве управляющего языка и делает работу с распределенными данными полностью прозрачной для приложений – они работают абсолютно одинаково как с локальными данными, так и размещенными на удаленном узле.

Характеристики языка

Среди наиболее важных характеристик Erlang следует отметить следующие.

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

Поддержка распределенной среды – масштабируемость изначально заложена в природу языка. Каждая виртуальная машина Erlang называется узлом (node). Распределенная система состоит из множества узлов, каждый из которых может запускать процессы на других узлах, даже работающих под управлением других ОС. Притом взаимодействие между процессами различных узлов происходит таким же образом, как и для процессов, исполняемых под управлением одной виртуальной машины.

Отказоустойчивость – Erlang обладает множеством механизмов для обеспечения отказоустойчивости создаваемых программ, к примеру, в случае отказа одного из узлов его процессы начнут исполняться на других и вернутся обратно при восстановлении работоспособности узла.

Поддержка проектирования систем реального времени – Erlang имеет встроенные средства для создания систем реального времени, для которых ограничены задержки при обработке информации.

«Горячее» обновление кода – программы на Erlang позволяют обновлять свой код прямо во время исполнения, предусмотрена также возможность отката обновлений в том случае, если они приводят к нарушению работы системы.

Инкрементная загрузка кода – пользователь может управлять загрузкой модулей в память при исполнении программы. Если какие-то из них в данный момент не нужны, их можно не загружать, а новые загружать непосредственно во время исполнения программы.

Поддержка внешних интерфейсов – Erlang содержит средства для взаимодействия с внешними системами, притом их реализация выполнена таким образом, чтобы они не могли негативно повлиять на выполнение программ на данном языке.

Знакомимся с синтаксисом и особенностями языка

Начнем с простой задачи вычисления факториала. Его рекурсивное описание выглядит следующим образом:

0! = 1,
n! = n · (n – 1)!

А исходный код модуля на Erlang, экспортирующего рекурсивную функцию вычисления факториала, выглядит так:

- module(math).
- export([fac/1]).
fac(0)-> 1;
fac(N)-> N * fac(N-1).

Как видно, программа практически идентична математическому описанию задачи. Именно в этом и проявляется сила декларативного программирования – мы говорим, что хотим получить, а не как этого достичь.

Неплохо было бы проверить, как эта функция работает. Итак, компилируем модуль (в оболочке Erlang это делается командой c (fac.erl)) и запускаем функцию с аргументом, скажем, 20 000 (команда: fac(20 000)).

После небольшой задержки на экран начинает выводиться результат – свыше 70 тыс. цифр. Может быть, на неспециалиста это не произведет особого впечатления, но любой программист, работающий с «обычными» языками, сразу же испытает к Erlang уважение. Во-первых, мы получили результат с невероятной точностью (к примеру, в C# без использования специализированных библиотек «длинной арифметики» программистам доступны целые числа с максимальной 64-разрядной точностью – а это всего каких-то 20 знаков), а во-вторых, он получен рекурсивной функцией с огромной глубиной вложенности – в том же C# неминуемо произойдет переполнение стека.

Но самое поразительное то, что в Erlang вообще нет никаких ограничений ни на длину целых чисел, ни на глубину рекурсивных функций! Единственный ограничивающий фактор – это вычислительные возможности компьютера. Таким образом, программист не должен отвлекаться на такие вопросы, как «Сколько знаков способен хранить используемый тип данных?» или «Cколько уровней вложенности может иметь рекурсивный вызов?».

Рассмотрим еще один пример – реализацию быстрой сортировки по методу Хоара. На языке Erlang программа будет выглядеть так:

qs([])-> [];
qs([Pivot|Tail])->
qs([X||X<-Tail, X =< Pivot]) ++
[Pivot] ++
qs([X||X<-Tail, X > Pivot]).

Отметим исключительную лаконичность и выразительность языка (аналогичная процедура на С в несколько раз длиннее). Вероятно, здесь следует упомянуть, что объем исходного кода обладающей богатыми функциональными возможностями СУБД Mnesia, о которой мы говорили ранее, составляет всего лишь около 20 тыс. строк на Erlang. Несмотря на то что на первый взгляд языковые конструкции Erlang выглядят очень непривычно, разобраться в них достаточно просто, особенно если не упускать из виду, что в декларативном языке мы просто описываем требуемый результат.

Итак, первая строка – это выражение, которое возвращает пустой массив и вызывается при условии, что параметром также является пустой массив (с ее помощью происходит прекращение рекурсии). Во второй строке описано выражение, которое в качестве параметра должно принимать список элементов, причем из функции, как отдельный элемент, доступен только первый – «Pivot», а «Tail» означает оставшуюся часть списка. Далее, строки с третьей по пятую конструируют результат посредством оператора конкатенации («++»), притом четвертая строка попросту возвращает первый элемент (Pivot), а третья и пятая рекурсивно вызывают функцию быстрой сортировки, упорядочивая все элементы списка со значениями, меньшими первого элемента, равными ему (третья строка) и большими (пятая строка).

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

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

Параллельно-ориентированное программирование

О том, что Erlang эффективно поддерживает параллельное программирование, мы уже говорили. Однако и современные императивные языки также его поддерживают, но в отличие от них Erlang располагает к параллельному программированию. Это достигается прежде всего чрезвычайной простотой, с которой эта задача решается, а также выгодами, получаемыми в результате. В частности, при описании процессов в Erlang часто употребляется выражение «share nothing semantics» – процессы не разделяют никаких общих данных. Поэтому нет необходимости беспокоиться об их сохранности, используя для этого привычные по императивным языкам механизмы вроде мьютексов (mutex) и семафоров, и бороться с клинчами (deadlock) и конкуренцией за ресурсы. А в связи с тем, что сбои при исполнении одного процесса никак не могут влиять на другие, то создание процесса для выполнения рискованных операций – самый логичный способ изолировать потенциально опасные действия.

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

Заключение

В конце нашего достаточно поверхностного знакомства с миром функционального программирования и языком Erlang отметим, что на самом деле существует множество функциональных языков, в том числе и гораздо более выразительных, например довольно популярный Haskell (haskell.org). Однако Erlang выбран неслучайно: в отличие от многих академических языков – это живой индустриальный язык, приложения на котором работают в самых сложных коммерческих системах. И хотя на текущий момент сфера применения Erlang ограничена в основном телекоммуникационными продуктами и системами реального времени, на официальном сайте проекта о нем говорится как об универсальном языке программирования, пригодном для решения различных прикладных задач.

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

Напрашивается вопрос: вытеснят ли в ближайшем будущем функциональные языки своих императивных конкурентов? Скорее всего, нет. И причина здесь не в недостатках функциональной парадигмы, которые также существуют, а в инертности процессов, происходящих в программной индустрии. Достаточно вспомнить так называемое потерянное поколение языков программирования, когда в 70–80-е годы появились даже не сотни, а тысячи языков и диалектов, множество из которых были объектными и объектно-ориентированными. Им пророчили большое будущее, но в действительности они не выжили, поскольку их идеи были ассимилированы популярными структурными языками, получившими ОО-возможности. К примеру, C преобразился в C++, а Pascal был просто дополнен поддержкой ОО-подхода. Все это позволило сделать переход постепенным и относительно безболезненным.

То же происходит и сегодня. На самом деле современные императивные языки поддерживают функциональный стиль программирования – построение программных конструкций способом, близким к функциональным языкам (хотя пока он выглядит громоздко и работает недостаточно эффективно), и в процессе своего развития приобретают все больше изначально присущих исключительно им возможностей. Именно по такому пути идет Microsoft, развивая C#, и с каждой новой версией круг предоставляемых им средств для функционального программирования увеличивается. К примеру, в C# 1.0 существовали делегаты, позволяющие рассматривать функции в качестве типа данных, в C# 2.0 были добавлены анонимные методы, реализующие функциональность замыкания, встречающуюся преимущественно в функциональной парадигме, а в грядущей версии C# 3.0 обещают быть реализованы лямбда-выражения, которые напрямую перекочевали из функциональных языков. Нужно ли сомневаться в том, что функциональная парадигма постепенно побеждает в изначально императивном языке C#?

Но, пожалуй, особое преимущество декларативного подхода состоит в том, что он, по мнению автора, скорее соответствует самой идее применения вычислительной системы. Действительно, наиболее сложным является описание, что именно мы хотим получить от компьютерной программы. Это следует сделать независимо от того, какого подхода мы придерживаемся – императивного или декларативного. Однако императивный подход требует, чтобы мы еще и указали путь достижения желаемого результата, а это уже дополнительная сложность. И понятия «работающая программа» и «правильно работающая программа» далеко не тождественны. А что можно сказать о таком утверждении: «Если программа компилируется, то она почти наверняка работает правильно»? Неужели такое возможно? Если речь идет о декларативном программировании – то вполне, и эта фраза нередко звучит в адрес уже упомянутого нами функционально-логического языка Mercury. Просто достаточно вспомнить, что при декларативном подходе программа описывает желаемый результат, т. е. если программисту удалось описать то, что он хочет получить, именно это он и получит.

P.S. Если читатель заинтересовался темой функционального программирования и языком Erlang, то ему можно порекомендовать некоторые дополнительные источники информации. Начать следует, пожалуй, со статьи Вячеслава Ахмечета «Functional Programming For The Rest of Us» (defmacro.org/ramblings/fp.html), которую к тому же можно найти в русскоязычном варианте на сайте rsdn.ru. Помимо достаточно последовательного введения в мир функционального программирования, эта статья отличается тем, что примеры рассмотрены на известном многим языке Java. Можно ознакомиться также с размещенной в Википедии книге по функциональному программированию (ru.wikibooks.org/wiki/Основы_функционального_программирования).

e-mail автора: koldovsky@koldovsky.com

0 
 

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT