ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ -
УДК 681.3.06
АССОЦИИРОВАННЫЕ ТИПЫ И РАСПРОСТРАНЕНИЕ
ОГРАНИЧЕНИЙ НА ПАРАМЕТРЫ-ТИПЫ ДЛЯ ОБОБЩЕННОГО ПРОГРАММИРОВАНИЯ НА SCALA
© 2015 г. A.M. Пеленицын
Южный федеральный университет 344006 Ростов-на-Дону, ул. Б. Садовая, 105/42 E-mail: apel@sfedu.ru Поступила в редакцию 05.03.2015
Обобщённое программирование представляет собой принцип создания программных компонент, характеризующихся высокой степенью повторной используемости за счёт отделения реализации алгоритмов от конкретных определений типов данных, с которыми работают эти алгоритмы. В последние годы проведён ряд исследований, направленных на выявление имеющихся и разработку новых механизмов поддержки обобщённого программирования в различных языках программирования. В данной работе анализируются и развиваются подходы к реализации обобщённого программирования с использованием различных элементов языка программирования Scala, разработанного в Федеральной политехнической школе Лозанны специалистом в теории и реализации языков программирования Мартином Одерски.
1. ВВЕДЕНИЕ
Обобщённое программирование представляет собой принцип создания программных компонент, характеризующихся высокой степенью повторной используемости за счёт отделения реализации алгоритмов от конкретных определений типов данных, с которыми работают эти алгоритмы [1].
Различные языки программирования предоставляют разные средства поддержки обобщённого программирования. Можно выделить три подхода к выражению идей обобщённого программирования с помощью современных языков программирования. Первый состоит в использовании имеющихся в языках стандартных средств. Примером этого подхода является применение шаблонов С++, а также обобщённых типов в распространённых объектно-ориентированных языках (Java, С#). Второй подход состоит в проектировании соответствующих расширений для известных языков программирования (например, расширение С# в [2], JavaGI [3]). В рамках третьего подхода
разрабатываются новые языки, изначально содержащие нужные механизмы. Главным примером здесь является язык программирования Scala, хотя можно упомянуть и другие, направленные в основном на академические исследования языки построения доказательств, такие как Agda и Coq.
Отдельным примером языка, имеющего развитые средства обобщённого программирования, является язык Haskell. Он изначально проектировался как язык с одним главным компилятором, открытым для экспериментов в области теории типов. Часть результатов такого рода постепенно включается в новые редакции стандарта языка. Однако даже базовые средства Haskell, классы типов и повсеместно используемый параметрический полиморфизм представляют собой довольно развитую инфраструктуру для применения обобщённого программирования. Таким образом, в отношении предложенной выше классификации этот язык равноправно поддерживает первый и второй подходы к реализации и развитию средств обобщённого программирования. Ряд нестандартных, но широко использу-
емых расширений компилятора Glasgow Haskell Compiler (GHC), такие как мультипараметриче-ские классы типов и функциональные зависимости, укрепляют позиции языка в этом отношении.
Исторически первым примером языка, в котором достаточно широко были применены принципы обобщённого программирования, стал язык С++. Так называемые неограниченные шаблоны С++ дают достаточно широкую свободу в использовании параметров-типов (один из главных инструментов обобщённого программирования). Однако использование этих шаблонов имеет ряд известных издержек, в первую очередь это сложность поиска и исправления ошибок (в том числе трудночитаемые сообщения компиляторов об ошибках), а также недоступность раздельной трансляции обобщённых программных модулей (шаблонов классов и функций). Повысить удобство использования обобщённого подхода был призван, в том числе, новый стандарт языка С++11. Однако отказ от включения в него концептов (concepts) по ряду причин сильно ослабил позиции нового стандарта в этом отношении. Тем не менее сегодня, когда речь идёт об испытании тех или иных средств, призванных поддерживать обобщённое программирование, сравнение зачастую проводится либо с известными примерами из области С++, либо с языком Haskell.
Так, статья [2] предлагает расширение языка С# и демонстрирует, как на этом пути снимаются недостатки, заметные при попытке воспроизвести фрагмент известной обобщённой С++-библиотеки Boost Graph Library (BGL) на обычном С#. Само расширение состоит в добавлении так называемых ассоциированных типов и механизма распространения ограничений для параметров-типов.
Работа [4] посвящена описанию одного из самых незаурядных элементов языка Scala — им-плиситам. В ней приводится решение ряда задач разной степени сложности, начиная от моделирования классов типов Haskell, что автоматически вводит Scala в ряд языков, развивающих обобщённый подход, заканчивая довольно сложными примерами вычислений на уровне типов (type-level computations), такими как вычисление типа функции:
где n является параметром (на входе — функция от n — 1 аргумента, а также n — 1 списков, на выходе — список результатов применений данной функции к соответствующим элементам данных списков). Похожая техника для представления многочленов многих переменных на С++ рассмотрена в [5].
Детальное рассмотрение одного элемента языка, имплиситов, не мешает сделать [4] ряд важных выводов в отношении поддержки обобщённого программирования со стороны Scala в целом. В частности, в статье приведено расширение карты поддержки обобщённого программирования современными языками, первая версия которой была опубликована в одной из основополагающих работ [6]. В последней работе сравнение обобщённых возможностей разных языков программирования, не включая Scala, проводилось на примере реализации упомянутой выше библиотеки BGL.
В [2] проводится анализ возможной реализации фрагмента BGL с использованием расширенного С#. В настоящей работе предложен аналогичный анализ для языка Scala, который представляется более удобным инструментом обобщённого программирования. Выделяются элементы языка Scala. которые позволяют более лаконично реализовать идеи ассоциированных типов и распространения ограничений для решения типичных проблем обобщённого программирования на примере, рассмотренном в [2].
Первым основным результатом работы является применение уточнённых типов Scala (refinement types) для описания ограничений на ассоциированные типы. Далее, показано, как с помощью типов методов, зависящих от цепочек, подход [2] освобождается от необходимости использования параметрического полиморфизма, что в конкретном примере из [2] делает решение более кратким и ясным.
Второй основной результат работы состоит в выявлении и устранении недостатка подхода [2], связанного с отсутствием возможности ретроактивного моделирования, которая представляет собой один из критериев поддержки обобщённого программирования, выделенных в [6]. Общий
подход к решению этой проблемы на основе им-плиеитов Seala предложен в [4|, мы показываем, как адаптировать его в типичной ситуации промышленного библиотечного кода из [2|.
Полученные в настоящей работе результаты дополняют описание методов обобщенного программирования на Seala, которое дано в [4|. При этом используется материал, который, с одной стороны более доступен для понимая сути обобщенного программирования, а с другой стороны, более близок к индустриальному программированию, чем в [4|, а именно фрагмент BGL. Более реалистичный пример заставляет привлекать элементы языка Seala, которые ранее не использовались (уточненные типы) или использовались в малой степени (абстрактные типы-члены и типы, зависящие от цепочек) в такого рода задачах. Полученная в настоящей работе конструкция сопоставляется с результатами [2|, а также с некоторыми элементами обобщенного программирования в языках С++ и Haskell.
В работе [7] в заключительных замечаниях (п. 6, Связанные работы) отмечаются перспективы Seala в отношении обобщенного программирования. Авторы [7] упоминают о своих планах провести исследование но использованию ассоциированных типов и имилиеитов для прояснения этих перспектив, аналогичное тому, как это сделано в настоящей работе. Однако в доступной литературе такие результаты не найдены.
Статья состоит из введения, трех разделов и заключения. Во втором разделе излагаются результаты [2| в удобном для нас виде: описывается фрагмент BGL и приводится его реализация на С#, в том числе с расширениями из работы [2]. Кроме того, здесь обсуждаются различные недостатки имеющихся решений. В третьем разделе демонстрируются возмо^жности Seala в области обобщенного программирования на примере реализации того же фрагмента BGL, при этом отмечаются преимущества Seala перед расширенным С# из [2]. В разделе 4 отмечается несоответствие подхода [2| некоторым требованиям обобщенного программирования и конструируется решение этой проблемы с использованием идей |4|. Здесь же проводится краткий анализ дополнительных затрат как клиента, так и автора библиотеки, которая использует такой подход, а также делаются замечания относительно других языков про-
граммирования в этом отношении. Два основных результата работы, упомянутых выше, изложены, соответственно, во третьем и четвертом разделах статьи.
2. ФРАГМЕНТ BGL И ЕГО РЕАЛИЗАЦИЯ НА С# С РАСШИРЕНИЯМИ
В качестве примера для иллюстрации обобщенных возможностей предлагаемого расширения С# в [2] использована следующая функция из состава BGL (С++):
first neighbor (Graph g, typeriame
Приведенная функция по заданному экземпляру графа и некоторой вершине, принадлежащей этому графу, возвращает одну из вершин, смежных данной ("первую" в некотором упорядочении). Один очевидный технический недостаток этого кода связан с необходимостью использовать ключевое слово typename для указания того, что зависимый от параметра шаблона Graph идентификатор vertex_type является именем типа, а не обычным членом класса. Другой, более фундаментальный недостаток "неограниченных" шаблонов языка С++: заголовок и тело данной функции содержат довольно большо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.