Пользователь
0,0
рейтинг
19 ноября 2015 в 00:28

Разработка → Включение внешних языков в программы на Haskell

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

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

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

  • inline-c — достаточно простая библиотека, позволяющая делать вставки C кода в код haskell. Практически, эта библиотека является автоматизацией достаточно простой процедуры написания собственных вспомогательных функций и создания FFI обёрток для них. Данная библиотека показывает, как можно сделать включение языка с простым (отсутсвующим runtime) в код на Haskell.
  • inline-r — библиотека позволяющая включать код на R в Haskell код, она уже достаточно интересна, поскольку показывает как можно объединять разные runtime системы. Включать динамически типизированный код на R в код на Haskell, и эффективно управлять данными в системах, где есть два сборщика мусора.


Для того, чтобы реализовать подобное решение, нужно было решить следующие вопросы:
  1. как подключать код на других языках,
  2. какой должен быть синтаксис вставок на другого языка; способ ввода кода,
  3. как преобразовать данные так, чтобы обе библиотеки могли с ними работать

а так же другие вопросы возникающие с различными RTS(runtime system) системами исполнения, такие как несколько сборщиков мусора, использование динамической типизации

Встраивание системы исполнения


Для включения простых языков (C, Rust) не имеющих RTS все достаточно просто, в них средой исполнения является программа на Haskell. В этом случае Тут только поддержка интерфейса вызова внешних функций FFI, и C интерейс подходит для большинства случаев.
Однако в случае наличия системы исполнения, как в R, возникает вопрос способе её запуска и коммуникации. Одним из стандартных подходов к решению данной проблемы является запуск “интерпретатора” (программы целевом языке) отдельным процессом и использование, какого-либо из средств RPC для обмена сообщениями между им и исходной программой. Данный способ однако имеет несколько минусов:

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

Для передачи данных испонителю требуется их отправка по сети (возможно уменьшить сложность при использование zero-copy), сериализация и десериализация. Альтернативой может быть создание механизмов передачи основанных на использовании общей памяти, что однако, может быть достаточно сложной задачей в языках, где прямой доступ к памяти ограничен или возникают дополнительные сложности, такие как использование копирующего сборщика мусора.

Из плюсов данного способа — простота решения, так же в нём нету необходимости интеграции event loop, нужной, например, для отрисовки графики.

Данные ограничения обычно несовместимы с требованием минимальных накладных расходов. Поэтому было часто лучше встраивать среду исполения в Haskell. Такое решение открывает сразу несколько дополнительных возможностей:
  • поскольку мы работаем с общей памятью, то исчезает лишняя работа по сериализации и передаче данных;
  • появляется возможность использовать C API (api предоставляемый экспортируемыми из библиотеки фунциями с C интерфейсом), при его наличии, больший контроль за ошибками интерпретатора/программы;
  • поскольку такой программе «больше известно» о данных и функциях, которые могут их исполнять, то она может дополнительно оптимизировать исполнение.


В данном решении возможны технические сложности, например, если среда исполнения языка накладывает дополнительные ограничения, например использует TLS (Thread Local Storage) или является принципиально однопоточной. В первом случае необходимо использовать Control.Concurrent.forkOS для создания ветки привязанной с нити OS (или использовать только главную нить). Во-втором необходимо сериализовать запросы на стороне языка, например, это можно сделать при помощи достаточно простого «паттерна»:

{-# LANGUAGE ExistentialQuantification #-}
import Control.Concurrent

data Task = forall a . Task (IO a) (MVar (Either SomeException a)) 

sendTask :: Chan -> IO a -> IO a                                                        
sendTask chan f = do 
   result <- newEmptyMVar                                                                  
   writeChan chan  (Task f result)                                                        
   takeMVar result                                                                                 

runTasks :: Chan -> IO ()
runTasks chan = forever $ do
    Task f result <- readChan chan                                                       
    mask_ $ do r <- try f                                                                         
                        putMVar result r                                                           

В данном подходе могут быть некоторые вариации, например хранить канал в окружении ReaderT Chan или глобальной переменной, если единственность этого канала должна быть гарантирована на уровне программы (вы должны трижды подумать перед тем, как выбрать данное решение, но формально оно может быть оправдано). Так же в некоторых случаях лучше передавать в канал действие формирующееся вызывающим, где он будет сам класть результат в MVar для ответа. Но семантически (с точностью (и) до работы с исключениями и завершению исполнения этого потока) другие решения будут эквивалентны данному.

Передача данных


При передаче данных первый из вопросов, который необходимо решить, это каким образом представлять данные из внешнего языка в Haskell, самые простые типы, которые это позволяют являются C-типы: CChar, CInt, CString, CStringLen, Ptr и прочие. Которые являются отображениями C-типов на типы в Haskell и достаточны для представления данных из низкоуровневых языков. Для типобезопасной работы с ними такие данные можно обернуть в типы обертки (newtypes), благодаря, которым с одной стороны система типов позволяет, а другой они не вносят совершенно никакой нагрузки в рантайме.
Поскольку подключаемые языки могут быть динамическими, как в частности, R возникает вопрос, как представить их значения в языке. При этом хочется по возможности иметь статически известную информацию о типах там, где это возможно. В этом случае компилятор может дать больше гарантий корректности кода, и возможно генерировать код по типам (см. классы типов в Haskell). Тут можно вспомнить утверждение о том, что языки с динамической системой типов являются uni-typed языками, т.е. в статике вся вселенная представимых там типов описывается одним единственными типом. Использовав такой подход можно представить значение в языке, как указатель тегированный фантомным типом, указывающим на тип выражения (вместо указателя может быть индекс в таблице или другой идентификатор уникально определяющий значение, в зависимости от того, как они представляются во включаемом языке)
data SEXPTYPE -- generated by hsc2hs
newtype SEXP a  = SEXP (Ptr SEXPTYPE)

SEXPTYPE это тип экспортируемый в C интерфейс языком. Для того же, чтобы указать, что, как это и полагается в динамических языках, выражение может быть неизвестного типа, мы используем следующий подход.
Для передачи информации о типах, можно использовать расширения DataKinds, которое возволяет поднимать конструкторы простых типов данных на уровень типов, т.е. создавать тип, например `SomeThing ‘False`. Далее мы перечисляем все возможные примитивные типы в подключаемом языке, например в случае R это
data SEXPTYPE = NIL | Symbol | List | Closure | Int | Real ... deriving (Eq,Ord,Show)

Теперь, если мы знаем, что выражение имеет определенный тип (например было создано в Haskell), то мы можем явно записать его тип как `SEXP ‘List` или `SEXP ‘Real`. Однако при работе с динамическим языком этого не достаточно, т.к. там не известны все возвращаемые типы и хотелось бы иметь возможность передавать по настоящему динамический тип. Для этого мы можем воспользоваться расширением Rank2Types позволяющим записать следующий тип:
data SomeSEXP = SomeSEXP (forall a . SEXP a)

Данный код обозначает, что SomeSEXP для любого a выражение SomeSEXP a корректно, т.е. в точности отражает факт динамического значения. Теперь методы внешнего языка могут спокойно возвращать SomeSEXP, для преобрахования типа к известному можно создать фунцию
cast :: SomeSEXP -> Maybe (SEXP a)

которая будет проверять тип выражение, и или возвращать выражение или ошибку.
Ещё хотелось бы иметь возможность иметь тип сумму, так как в некоторых функциях на вход можно подавать переменне различных типов.
Для создания таких типов можно воспользоваться расширением TypeFamilies, и создать новый тип `In` который проверяет содержится ли данный тип в списке разрешенных типов:

infix 1 :∈

-- | The predicate @a :∈ as@ states that @a@ is a member type of the set @as@.
type family (a :: SEXPTYPE) :∈ (as :: [SEXPTYPE]) :: Constraint where
  'Any :∈ as = ()
  a :∈ (a ': as) = ()
  a :∈ (b ': as) = a :∈ as

type In a b = a :∈ b

Данное код работает так же как и обычное сопоставление с образцом на уровне типов, где () обозначает успех, а невозможность проверить утверждение ошибку. Рассмотрим на примере, In ‘Int (Env ‘: Int ‘: ‘[]). Сначала мы попадаем во третье условие, поскольку Int не совпадает с ‘Env, и тип получается равен In ‘Int (‘Int ‘: ‘[]). Его компилятор упрощает дальше и мы попадаем во второе выражение, из которого выводим успех, в случае если бы мы проверяли ‘Real, то мы бы дошли до In ‘Real ‘[] для которого образца нет и соотвественно бы возникла ошибка типов.
Проблемой этого подхода является то, что тип не инъективен, т.е. если у нас есть выражение foo :: In a [‘Int,’Real] => a -> SEXP ‘Int, то мы не сможем вывести тип a, что может быть не удобно.

В таком представлении можно уже работать с функциями используя C API и добиваться некоторого удобства написания кода. Сперва может показаться, что данный подход помешает использованию возможностью современных языков программирования, таких, как сравнение с образцом и алгебраические структуры данных, но это не так.
Для того, чтобы использовать такие структуры мы можем воспользоваться следующей техникой. Мы создаем образ для структуры (view) в нём мы определяем только неглубокое (shallow) представление структуры, это делается для того, чтобы не возникало необходимости создавать в памяти все отображение структуры, более того, в общем случае компилятор полностью убирает все промежуточные стуктур, позволяя удобно работать со внешними структурами данных без накладных расходов:
data HExp :: * -> SEXPTYPE -> * where
  -- Primitive types. The field names match those of <RInternals.h>.
  Nil       :: HExp R.Nil
  -- Fields: pname, value, internal.
  Symbol    :: SEXP R.Char
            -> SEXP a
            -> SEXP b
            -> HExp R.Symbol
  -- Fields: carval, cdrval, tagval.
  List      :: (R.IsPairList b, c :∈ [R.Symbol, R.Nil])
            => SEXP  a
            -> SEXP b
            -> SEXP c
            -> HExp R.List
  ...

И введем фунцию `hexp` создающую такой образ:
hexp :: SEXP s a -> HExp s a

Далее при помощи расширения ViewPatternsможно использовать сопоставление с образцом:
foo (hexp -> Symbol s) = ...


Для полноты нужна функция
unhexp ::  HExp s a -> m s (SEXP a) 

Важно заметить, что тут не выполяется ожидаемое правило unhexp . hexp = id поскольку unhexp всегда создает новую структуру.

Данная техника позволяет удобно работать с внешними сложными структурами. И может быть перенесена на любой внешний язык программирования. Последним шагом тут должно быть преобразование marshaling структур данных Haskell в структуры внешнего языка, для этого можно ввести класс типов
class Literal a ty | a -> ty where
    -- | Internal function for converting a literal to a 'SEXP' value. You
    -- probably want to be using 'mkSEXP' instead.
    mkSEXP   :: a -> IO (SEXP V ty)
    fromSEXP :: SEXP s ty -> a

`| a -> ty` это функциональная зависимость между параметрами, которая говорит, что тип `a` однозначно определят тип `ty`. Эта информация сильно помогает компилятору при выводе типов и не возволяет создать ошибочные инстансы. Далее для нативных типов в Haskell мы опредяем функции перевода.

Написание кода на внешнем языке



Для написания кода мы можем создавать внутренний встроенный язык (e-dsl) (правда в высокоуровнем языке, границы между библиотекой и встроенным специализированным языком весьма размыты), или же полноценный dsl. Мы решили использовать “DSL”, т.е. на самом деле слегка модифицированный подключаемый язык. Данный способ выглядит более удобным, поскольку в этом случае код могут писать те, кто не знает Haskell, но знает встраиваемый язык. Как это можно огранизовать, и как это выглядит.

Для генерации исходного кода на Haskell, существует расширение Template Haskell, который позволяет строить AST, однако в нём есть серия ограничений, плюс так же проверка типов весьма ограничена, т.к. у всех генерируемых выражений один и тот же типа Q Exp, соотвественно компилятор не может проверить часть контрактов и в итоге может генерироваться невалидный код, который будет отклонён компилятором при генерации кода.
Также есть возможность создания квази цитат QuasiQuotes [generator|some-code |] тут generator это функция, которая будет разбирать код some-code и получать результат. Результатом может быть код на Haskell сгенерированный с помощью TemplateHaskell, созданние файлов (например внешние файлы на C), вызов find / -delete или в принципе любая работа.

Квази-цитирование является отличным кандидатом для включения кода, в мы можем создать новый парсер. Далее при компиляции проекта, мы вызываем R и передаем ему исходный код и получаем назад AST. После обрабатываем данную AST и генерируем код, который в runtime будет строить такое же AST с учетом подстановки переменных из Haskell.
Например простой код:
let x = [1,2,3]
in [r| x_hs + x_hs|]

Превращаестся в:
eval $ unhexpIO =<< Lang (installIO “+”) (unHexp $ List (mkSEXP x) (List (mkSEXP x) Nil) 

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

Регионы и отображение системы работы с памятью


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

Foreign.StablePtr.newStablePtr — создание “защищающего” объекта
Foreign.StablePtr.freeStablePtr — удаление “защищающего” объекта
extern void hs_free_stable_ptr (HsStablePtr sp); — удаление “защищающего” объекта из внешнего языка

В R это:
preserveObject — отметка объекта как используемого
releaseObject — отметка объекта как не используемого

Тогда в случае использования объекта из R в haskell можно делать
newtype Protected a = Prected (ForeignPtr SEXPPTR)
protect (SEXP p) = do
   preserveObject p
   newForeignPtr p  releaseObject

Данный метод достаточно хорош, однако применим не для всех языков, т.к. необходимого API может не быть, и он не работает для объектов на “стеке”, ну и, наконец, он может иметь очень большую стоимость, например, цена создания и удаления объекта в R O(N), где N количество защищенных таким образом объектов. Поэтому использование такого метода как основного это не лучшая затея.
Однако это не единственный, и не основной, способ защиты объектов в R. Дополнительно к данному методу защиты существует и другой, основанный на “защитном стеке” (protection stack), любой объект может быть положен на стек и со стека можно снять N объектов, данные операции имеют сложность O(1). Такой подход к защите объектов используется как в самом R, так и в функциях написанных на С. И очень хотелось бы данный способ отобразить и на Haskell. И для это можно реализовать при помощи статических регионов, данная техника была описана в статье Олега Киселева.

Замечу, что в силу особенностей системы сборки мусора в R, данный подход отличается от оригинального решения, хотя они и эквивалентны по выразительности

newtype R s m a = R { runR :: ReaderT (IORef Int) m a }
deriving (Functor, Applicative, Monad)


В IORef мы храним количество объектов выделенных на данном сегменте “стека”, так, что при выходе мы можем всех их освободить. Далее вводится вспомогательная функция:

runRegion :: (forall s . R s IO a) -> IO a
runRegion f = do
   ref <- newIORef 0
   runReaderT (runR f) ref 


и основная функция:

region :: (forall s . R (s m) m a) -> m a
region f =  … аналогично

Теперь мы должны расширить тип SEXP дополнительной фантомной переменной s, обозначающей регион, в котором данная переменная была выделена или защищена.

Тут s играет роль региона, дополнительно введем 2 региона:
data V — пустой регион, обозначает, что переменная не принадлежит никакому сегменту стека и не защищена (может быть удалена при следующем выделении памяти)
data G — глобальный регион, обозначает, что переменная была защищена при помощи механизма (preserve) и может быть использована во всех регионах.
А при помощи функции region мы можем строить иерархии структур forall s1 s2 s3 . s1 (s2 s3 V)).

Наиболее интересным тут является то, что мы можем ввести полурешетку (lattice) замкнутую относительно операции вложения регионов (region). В этом случае имеем, что:
V < .. < s2 (s1) < s1 < G
В этом случае мы знаем, что мы можем безопасно использовать элементы из “большего” региона в меньшем и можем или ввести операцию

loosen :: (s1 < s2) => SEXP s2 a -> SEXP s1 a
<source>

или писать методы таким образом, чтобы позволялось использовать операции из старшего региона:

<source language="haskell">
someOperation :: (s < s1, s < s2) => SEXP s1 Int -> SEXP s2 Int -> R s (SEXP s Int)


Осталось только создать отношения в промежуточных регионах:

type Ancestor = (<)
class Ancestor s  s1
instance Ancestor (R s m) (R s m)
instance Ancestor parent region => Ancestor parent (R s region)


Заключение


Выше описаны основные элементы техники, которая может быть применена для включения других языков в Haskell. Техника может быть применена для включения кода на низкоуровневых языках, для увеличения эффективности кода (там, где это уместно и действительно её увеличивает), таких как C или Rust. Или языков с большим количеством библиотек, что может позволить работать с удобным языком программирования, не переделывая уже проведенную работу, например python, или специализированных языков вроде maxima,reduce или проприетарных аналогов.

Так же я понимаю, что тут все направления: взаимодействие с внешним кодом, создание регионов, генерация кода были рассмотрены весьма поверхности и если нужно рассмотреть их подробнее, то я могу сделать это в следующих статьях.
Alexander Vershilov @qnikst
карма
45,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (0)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.