Domniemana obsada typu statycznego (przymus) w Haskell

9

Problem

Rozważ następujący problem projektowy w Haskell. Mam prosty, symboliczny EDSL, w którym chcę wyrażać zmienne i wyrażenia ogólne (wielomiany wielomianowe), takie jak x^2 * y + 2*z + 1. Ponadto chcę wyrazić pewne równania symboliczne zamiast wyrażeń, powiedzmy x^2 + 1 = 1, a także definicji , takich jak x := 2*y - 2.

Celem jest:

  1. Mają osobny typ dla zmiennych i wyrażeń ogólnych - niektóre funkcje mogą być stosowane do zmiennych, a nie wyrażeń złożonych. Na przykład operator definicji:= może być typu (:=) :: Variable -> Expression -> Definitioni przekazanie złożonego wyrażenia jako parametru po lewej stronie nie powinno być możliwe (chociaż powinno być możliwe przekazanie zmiennej jako parametru po prawej stronie, bez jawnego rzutowania ) .
  2. Mają wyrażenia na przykład Num, aby można było promować dosłowne liczby całkowite do wyrażeń i używać wygodnej notacji do typowych operacji algebraicznych, takich jak dodawanie lub mnożenie, bez wprowadzania niektórych pomocniczych operatorów opakowujących.

Innymi słowy, chciałbym mieć niejawny i statyczny typ rzutowania (przymusu) zmiennych na wyrażenia. Teraz wiem, że jako takie nie ma w Haskell rzutów typu niejawnego. Niemniej jednak niektóre koncepcje programowania obiektowego (w tym przypadku proste dziedziczenie) są wyrażalne w systemie typów Haskell, z rozszerzeniami językowymi lub bez nich. Jak mogłem spełnić oba powyższe punkty, zachowując lekką składnię? Czy to w ogóle możliwe?

Dyskusja

Oczywiste jest, że głównym problemem jest tutaj Numograniczenie typu, np

(+) :: Num a => a -> a -> a

Zasadniczo możliwe jest napisanie jednego (uogólnionego) algebraicznego typu danych zarówno dla zmiennych, jak i wyrażeń. Następnie można by napisać :=w taki sposób, że wyrażenie po lewej stronie jest dyskryminowane i akceptowany jest tylko konstruktor zmiennej, z innym błędem wykonania. Nie jest to jednak czyste, statyczne (tj. Czas kompilacji) rozwiązanie ...

Przykład

Idealnie chciałbym uzyskać lekką składnię, taką jak

computation = do
  x <- variable
  t <- variable

  t |:=| x^2 - 1
  solve (t |==| 0)

W szczególności chcę zabronić notacji, t + 1 |:=| x^2 - 1ponieważ odtąd :=powinna zawierać definicję zmiennej, a nie całe wyrażenie po lewej stronie.

Maciej Bendkowski
źródło
1
może mógłbyś użyć class FromVar emetody z fromVar :: Variable -> ei podać instancje dla, Expressioni Variablewtedy twoje zmienne mają typy polimorficzne x :: FromVar e => eitp. Nie testowałem, jak dobrze to działa, ponieważ jestem teraz na telefonie.
Mor A.
Nie jestem pewien, w jaki sposób FromVarrodzaj czcionki byłby pomocny. Chcę uniknąć jawnych rzutów, zachowując Exprinstancję Num. Zredagowałem pytanie, dodając przykład notacji, którą chciałbym osiągnąć.
Maciej Bendkowski

Odpowiedzi:

8

Aby wykorzystać polimorfizm zamiast podtypu (ponieważ to wszystko, co masz w Haskell), nie myśl, że „zmienna jest wyrażeniem”, ale „zarówno zmienne, jak i wyrażenia mają pewne wspólne operacje”. Te operacje można umieścić w klasie typu:

class HasVar e where fromVar :: Variable -> e

instance HasVar Variable where fromVar = id
instance HasVar Expression where ...

Następnie zamiast rzucać rzeczy, uczyń je polimorficznymi. Jeśli tak v :: forall e. HasVar e => e, możesz go użyć zarówno jako wyrażenia, jak i zmiennej.

example :: (forall e. HasVar e => e) -> Definition
example v = (v := v)  -- v can be used as both Variable and Expression

 where

  (:=) :: Variable -> Expression -> Definition

Szkielet, aby wykonać kod poniżej, sprawdź typ: https://gist.github.com/Lysxia/da30abac357deb7981412f1faf0d2103

computation :: Solver ()
computation = do
  V x <- variable
  V t <- variable
  t |:=| x^2 - 1
  solve (t |==| 0)
Li-yao Xia
źródło
Ciekawe dzięki! Zastanawiałem się przez chwilę nad ukrywaniem zmiennych i wyrażeń za typami egzystencjalnymi, jednak odrzuciłem ten pomysł, ponieważ wprowadził on dodatkową notację, do zobaczenia V. Początkowo nie tego chciałem, ale być może byłem zbyt szybki, aby to odrzucić ... Prawdopodobnie nie mogę pozbyć się nieprzezroczystości V. W powiązanej notatce, jak mogę utworzyć instancję V (forall e . HasVar e => e)? W Coq używałbym obliczeń typu i dopasowywania wzorów dla typu indukcyjnego, ale nie jest jasne, jak to osiągnąć w Haskell.
Maciej Bendkowski
1
Można chwycić w :: Variablejakoś i zastosować fromVardo niego: variable = (\w -> V (fromVar w)) <$> (_TODO_ :: Solver Variable).
Li-yao Xia
1
I Vmożna tego uniknąć za pomocą impredykatywnych typów, ale nadal jest to PWT. Lub możemy variablepodjąć kontynuację z polimorficznym argumentem jawnie zamiast pośrednio przez (>>=).
Li-yao Xia