Как я могу обрабатывать операции над многими различными типами в моем DSL?

Question

Как я могу обрабатывать операции над многими различными типами в моем DSL?

Предположим, что Haskell должен использоваться для реализации интерпретатора для предметно-ориентированного языка. DSL имеет большое количество типов, представленных в виде конструкторов данных, и большое количество двоичных выражений. Наивной первой попыткой будет класс типа BinaryOps инкапсуляция всех бинарных операций над MyType в DSL:

data MyType = A String
            | B Integer
            | C Bool
            | D Double
         {- | E .. Z -}

class BinaryOps a where
    f :: a -> a -> a
    g :: a -> a -> a
    h :: a -> a -> a
    j :: a -> a -> a
    {- many more binary ops -}

instance BinaryOps MyType where
    f (A s1) (A s2) = {- Haskell expression on s1 and s2 -}
    f (A s1) (B s2) = {- ... -}
    f (B s1) (D s2) = {- ... -}
    f _ _ = error "f does not support argument types"

    g (D s1) (A s2) = {- Haskell expression on s1 and s2 -}
    g (D s1) (C s2) = {- ... -}
    g _ _ = error "g does not support argument types"

    h (B s1) (B s2) = {- Haskell expression on s1 and s2 -}
    h (B s1) (C s2) = {- ... -}
    h (B s1) (D s2) = {- ... -}
    h (C s1) (B s2) = {- ... -}
    h (D s1) (C s2) = {- ... -}
    h (D s1) (D s2) = {- ... -}
    h _ _ = error "h does not support argument types"

В DSL будет много бинарных выражений и много встроенных типов. Решение, приведенное выше, не будет особенно хорошо масштабироваться: определение класса будет большим, и число "неподдерживаемых" недопустимых комбинаций типов DSL будет расти (error звонки).

Есть ли более элегантный способ использования классов типов для интерпретации бинарных выражений в DSL? Или действительно, есть что-то вроде GADT, которое обеспечивает более масштабируемое решение?

4

haskell dsl typeclass

Источник

user1526266 18 мар '14 в 21:16

2 ответа

Решение

Вы можете использовать GADT для лучшего кодирования семантики вашего dsl.

{-# LANGUAGE GADTs, TypeSynonymInstances, FlexibleInstances #-} 

data MyType a where 
  A :: String -> MyType String
  B :: Integer -> MyType Integer 
  C :: Bool -> MyType Bool
  D :: Double -> MyType Double

Возникает проблема присвоения типа вашим функциям. принимать f например. Я не могу представить себе функцию, которая достаточно полиморфна, чтобы принимать две строки: строку и целое число или целое число и двойное число, но не строку и двойное число. Вы не включили семантику, поэтому я не знаю, что она делает. Итак, пока вы хотели бы сделать что-то вроде этого:

class BinaryOps r where 
  add :: r Integer -> r Integer -> r Integer

или даже

class BinaryOps r where 
  add :: Num a => r a -> r a-> r a

ты не можешь, потому что f слишком полиморфен Лучшее, что я мог придумать:

class BinaryOps r where 
  f :: FArg a b c => r a -> r b -> r c  

class FArg a b c 
instance FArg String String a  -- a should be the actual output type
instance FArg String Integer a
instance FArg Integer Double a

instance BinaryOps MyType where 
    f (A s1) (A s2) = undefined 
    f (A s1) (B s2) = undefined 
    f (B s1) (D s2) = undefined

Это не очень хорошее решение, потому что FArg ничего не говорит об аргументах, тогда пользователь должен будет найти определение класса, если экземпляр добавлен в FArg, например FArg Double Double Double ты сможешь позвонить f (D 0) (D 0) и получить ошибку соответствия шаблона времени выполнения. Мое предложение состояло бы в том, чтобы изменить функции на более разумные типы; написать функции как мономорфные и реализовать неявное или явное приведение в вашем dsl; включите определение некоторых реальных функций, чтобы легче было решить эту проблему.

1

Источник

user2407038 19 мар '14 в 08:25

Другие вопросы по тегам haskell dsl typeclass

user286871 18 мар '14 в 21:50 2014-03-18 21:50 · Accepted Answer · 2014-03-18 21:50

Я не понимаю, почему вы используете класс типов в первую очередь. Что дает вам класс типов по сравнению с обычными функциями?

Просто определите бинарные операторы как, ну, бинарные операторы Haskell, которые являются просто нормальными функциями:

f :: MyType -> MyType -> MyType
f = ...

Поскольку все ваши типы DSL находятся в MyTypeНет причин использовать класс типов.

Упаковка и распаковка

Конечно, это все еще не решает ваши error проблема. Один из подходов, который я использовал в прошлом, заключается в использовании классов типов для определения способов "упаковки" и "извлечения" примитивных типов в ваш DSL:

class Pack a where
  pack :: a -> MyType

class Extract a where
  extract :: MyType -> a

Вот то, что экземпляр для String будет выглядеть так:

instance Pack String where pack = A
instance Extract String where
  extract (A str) = str
  extract _       = error "Type error: expected string!"

Extract Класс может иметь дело с обработкой ошибок для несовместимых типов.

Это позволяет вам равномерно "поднять" функции в ваш DSL:

-- Lifts binary Haskell functions into your DSL
lift :: (Extract a, Extract b, Pack c) => (a -> b -> c)
          -> MyType -> MyType -> MyType
lift f a b = pack $ f (extract a) (extract b)

Если вы делаете MyType экземпляр Pack а также Extractэто будет работать как для чисто Haskell-функций, так и для функций, осведомленных о вашем DSL. Тем не менее, осведомленные функции просто получат какую-то MyType и придется разобраться с этим вручную, позвонив error если их MyType аргумент не то, что они ожидали.

Так что это решает ваш error проблема для функций, которые вы можете написать прямо на Хаскеле, но не совсем для тех, которые зависят от MyType,

Обработка ошибок

С помощью pack также приятно, потому что довольно просто переключиться на лучший механизм обработки ошибок, чем error, Вы бы просто переключить тип extract (или даже pack, при необходимости). Может быть, вы могли бы использовать:

class Extract a where
  extract :: MyType -> Either MyError a

а затем потерпеть неудачу с Left (TypeError expected got) что позволит вам написать хорошие сообщения об ошибках.

Это также позволит вам легко объединить несколько примитивных функций в "кейсы" в MyType уровень. Основная идея заключается в том, что мы объединяем несколько поднимаемых функций в одну MyType -> MyType -> MyType а внутри мы просто используем первый, который не дает нам ошибки. Это также может дать нам красивый синтаксис:).

Вот соответствующий код:

type MyFun = MyType -> MyType -> Either MyError MyType

(|:) :: (Extract a, Extract b, Pack c) => MyFun -> (a -> b -> c) -> MyFun
(f |: option) a b = case f a b of
  Right res -> return res
  Left err  -> (lift option) a b 

match :: MyFun
match _ _ = Left EmptyFunction

test = match |: (\ a b -> a ++ b :: String)
             |: (\ a b -> a || b)

К сожалению, мне пришлось добавить :: String подпись типа, потому что это было неоднозначно в противном случае. То же самое произойдет, если я использую +, поскольку он не знает, на какой номер полагаться.

Сейчас test это функция, которая работает правильно на двух Aс или два Bs и выдает ошибку в противном случае:

*Main> test (A "foo") (A "foo")
Right (A "foofoo")
*Main> test (C True) (C False)
Right (C True)
*Main> test (A "foo") (C False)
Left TypeError

Также обратите внимание, что это отлично сработало бы для разных типов аргументов, например, для случая, когда A а также B ценности.

Это означает, что теперь вы можете легко переделать свой f, g, h и так далее в качестве имен верхнего уровня в Haskell. Вот как вы можете определить f:

f :: MyFun
f = match |: \ s1 s2 -> {- something with strings -}
          |: \ s i   -> {- something with a string and an int -}
          |: \ i d   -> {- something with an int and a double -}
          |: {- ...and so on... -}

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

Вы также должны обновить lift правильно обрабатывать ошибки. Это включает в себя изменение его, чтобы вернуть Either и добавление необходимой сантехники. Моя версия выглядит так:

lift :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> MyFun
lift f a b = fmap pack $ f <$> extract a <*> extract b

Newtypes

Это в основном решает ваши error проблема с наличием |: Построить проверки ошибок для вас. Основным недостатком этого подхода является то, что он не будет работать очень хорошо, если вы хотите, чтобы ваш DSL имел несколько типов, имеющих один и тот же базовый тип Haskell, например:

data MyType = A Double
            | B Double
            {- ... -}

Вы можете исправить это, используя newtype создать обертку для Double, Что-то вроде этого:

newtype BDouble = B Double

instance Pack Double where pack = A

instance Pack BDouble where pack = B

-- same for Extract