\documentclass[12pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage{concrete}
\usepackage[utf8]{inputenc}
\usepackage[MeX]{polski}
\usepackage{minted}
\usepackage{graphicx}

\usetheme{Antibes}
\usefonttheme{serif}
\usecolortheme[RGB={100,10,10}]{structure} 
\setbeamercovered{invisible}

\title{Implementacja języków EDSL w~Haskellu}
\author{Piotr Krzemiński}
\date{Wrocław, 14 listopada 2013}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\scriptsize \tableofcontents
\end{frame}

\section{Języki dziedzinowe}

\subsection{Definicja}

\begin{frame}
  \emph{Domain Specific Language} -- język dziedzinowy,
        wyspecjalizowany w konkretnej dziedzinie zastosowań 
\end{frame}

\begin{frame}{Cechy}
\begin{itemize}
  \item ograniczone środki abstrakcji
  \item semantyka dostosowana do konkretnej dziedziny
  \item nie musi być językiem ogólnego przeznaczenia
  \item mogą być używane przez ekspertów dziedzinowych,
        niekoniecznie będących programistami
\end{itemize}
\end{frame}

\begin{frame}{Cechy}
W językach DSL:
\begin{itemize}
  \item programy są bardziej zwięzłe
  \item szybciej się je pisze
  \item są tańsze w utrzymaniu
  \item możemy łatwiej o nich wnioskować
\end{itemize}
\end{frame}

\subsection{Przykłady}
\begin{frame}{Szeroko używane języki dziedzinowe}
\begin{itemize}
  \item \emph{OpenGL} -- wysokopoziomowa grafika 3D
  \item \emph{PostScript} -- niskopoziomowa grafika
  \item \emph{VHDL} -- język opisu sprzętu
  \item \emph{Lex, Yacc} -- generatory lekserów, parserów
  \item \emph{HTML} -- język znaczników
  \item \emph{\LaTeX} -- składanie dokumentów
  \item \emph{Maple, Mathematica} -- obliczenia symboliczne
  \item \emph{DOT} -- wizualizacja grafów
  \item \emph{SQL} -- zapytania do relacyjnych baz danych
\end{itemize}
\end{frame}

\subsection{Sposoby implementacji}

\begin{frame}{Co musimy zrobić?}
\begin{itemize}
  \item wybrać precyzyjnie dziedzinę
  \item zaprojektować składnię języka, nadać jej znaczenie
  \item zaimplementować narzędzia (parser, interpreter,
        analizator, translator, debugger)
\end{itemize}
\end{frame}

\begin{frame}{Koszt}
\begin{center}
\begin{figure}
\includegraphics[scale=0.25]{cost.png}
\end{figure}
\tiny źródło: Paul Hudak, \emph{Modular Domain Specific Languages and Tools}
\end{center}
\end{frame}


\begin{frame}{Teoria vs. rzeczywistość}
\begin{itemize}
  \item trudno zaprojektować i zaimplementować nowy język od zera
  \item może nam się nie udać za pierwszym razem
  \item duża szansa, że doświadczymy wszystkich bolączek ewolucji
        języka programowania...
  \item ...i tak możemy nie osiągnąć zamierzonego celu
\end{itemize}
\end{frame}

\begin{frame}{Podejście Embedded}
\begin{itemize}
  \item nie chcemy budować naszego języka od zera
  \item wolelibyśmy wykorzystać infrastrukturę istniejącego
        języka programowania, tzw. języka-gospodarza (ang.~\emph{host language})
  \pause \item EDSL (DSEL) -- \emph{Embedded Domain Specific Language}
\end{itemize}
\end{frame}

\begin{frame}{Podejście Embedded}
\begin{itemize}
  \item możemy skupić się na semantyce naszej dziedziny
  \item nie musimy implementować od zera narzędzi deweloperskich
  \item za darmo możemy korzystać z większości cech języka-gospodarza
        (np. składnia, funkcje, system typów)
\end{itemize}
\end{frame}

\begin{frame}{EDSL -- sposób implementacji}
\begin{itemize}
  \item metaprogramowanie + preprocessing (np. LISP-owe makra)
  \item \emph{pure embedding}
\end{itemize}
\end{frame}


\section{Implementacja EDSL w Haskellu}

\subsection{Dlaczego Haskell?}

\begin{frame}
\begin{center}
Czy Haskell nadaje się do implementacji języków EDSL?
\end{center}
\end{frame}

\begin{frame}
\begin{itemize}
  \item elastyczna składnia
  \item klasy typów
  \item funkcje wyższego rzędu
  \item monady, transformatory monad
  \item silny system typów
\end{itemize}
\end{frame}

\begin{frame}{Elastyczna składnia}
\begin{itemize}
  \item definiowane przez użytkownika operatory (i ich priorytety)
  \item przeciążanie (w szczególności przeciążanie literałów)
  \item notacja wywołań funkcji: bez nawiasów, infiksowa
  \item \texttt{do}-notacja
  \item rozszerzenia
\end{itemize}

Pozwala zbudować unikalny \emph{look and feel}
\end{frame}

\begin{frame}{Monady}
\begin{itemize}
  \item pełna kontrola nad efektami ubocznymi
  \item pozwalają ukryć stan obliczeń
\end{itemize}
\end{frame}

\begin{frame}{Własności i prawa algebraiczne}
\begin{itemize}
  \item elementy neutralne
  \item operatory łączne
  \item operatory przemienne
  \item ...
\end{itemize}

Własności te możemy wyrazić, otypować, a często
nawet automatycznie testować (np. korzystając z QuickChecka)
\end{frame}

\subsection{Stopień integracji}
\begin{frame}
Implementując język EDSL w Haskellu, wyróżniamy dwa zasadnicze
podejścia:
\begin{itemize}
  \item płytka integracja (ang. \emph{shallow embedding})
  \item głęboka integracja (ang. \emph{deep embedding})
\end{itemize}
\end{frame}

\begin{frame}{Płytka integracja -- cechy}
\begin{itemize}
  \item konstrukcje języka reprezentowane bezpośrednio w~semantyce
  \item względnie łatwo możemy korzystać z haskellowych mechanizmów
        (rekursja, współdzielenie, typy)
  \item zazwyczaj proste w implementacji
  \item przyzwoita wydajność
  \item mniejsza elastyczność
  \item jedyna słuszna interpretacja
  \item trudności przy debugowaniu/analizie
\end{itemize}
\end{frame}

\begin{frame}{Głęboka integracja -- cechy}
\begin{itemize}
  \item konstrukcje języka reprezentowane w postaci składni abstrakcyjnej,
        interpretowane w osobnym etapie
  \item dostępne różne możliwości interpretacji (ewaluacja, translacja do
        innego języka, np. maszynowego, pretty print)
  \item większa elastyczność
  \item implementacja może być bardziej lub mniej wydajna
  \item trudniejsze wykorzystanie haskellowego współdzielenia i rekursji
\end{itemize}
\end{frame}


\subsection{Przykład}

\begin{frame}[fragile]{Analiza obszarów geometrycznych}
\footnotesize \begin{minted}[mathescape]{haskell}
type Point = ...
type Vector = ...
type Region = ...
inRegion :: Point -> Region -> Bool
distance :: Point -> Point -> Double
empty :: Region
circle :: Region
square :: Region
outside :: Region -> Region
scale :: Vector -> Region -> Region
translate :: Vector -> Region -> Region
(/\) :: Region -> Region -> Region
(\/) :: Region -> Region -> Region
\end{minted}
\end{frame}

\begin{frame}[fragile]{Implementacja -- płytka integracja}
Obszar geometryczny będziemy reprezentować za
pomocą funkcji charakterystycznej:
\footnotesize \begin{minted}{haskell}
type Region = Point -> Bool
\end{minted}
\normalsize Aby sprawdzić czy punkt należy do
obszaru, zdefiniujmy funkcję:
\footnotesize \begin{minted}{haskell}
inRegion :: Point -> Region -> Bool
inRegion p r = r p
\end{minted}
\end{frame}

\begin{frame}[fragile]{Implementacja -- płytka integracja}
\footnotesize \begin{minted}{haskell}
inRegion p r = r p
distance (x1, y1) (x2, y2) =
  sqrt ((x1 - x2) ** 2 + (y1 - y2) ** 2)
empty _ = False
circle p = distance p (0,0) <= 1
square (x,y) = abs x <= 1 && abs y <= 1
outside r p = not (r p)
scale (sx, sy) r (x, y) = r (x / sx, y / sy)
translate (dx, dy) r (x, y) = r (x - dx, y - dy)
(r1 /\ r2) p = r1 p && r2 p 
(r1 \/ r2) p = r1 p || r2 p 
\end{minted}
\end{frame}

\begin{frame}[fragile]{Implementacja -- płytka integracja}
Możemy wykorzystać haskellowe funkcje do zdefiniowania
bardziej złożonych obszarów
\footnotesize \begin{minted}{haskell}
circleAt :: Double -> Point -> Region
circleAt r center = translate center (scale (r, r) circle)

circleRow :: Integer -> Region
circleRow n = foldr (\/) empty
              [circleAt 1 (fromInteger x,0) | x <- [0..n-1]]
\end{minted}
\end{frame}



\begin{frame}[fragile]{Implementacja -- głęboka integracja}
Teraz reprezentacja danych wygląda tak:
\footnotesize \begin{minted}[mathescape]{haskell}
type Point = (Double, Double)
type Vector = (Double, Double)
data Region = Empty
            | Circle
            | Square
            | Scale Vector Region
            | Translate Vector Region
            | Outside Region
            | Intersect Region Region
            | Union Region Region
\end{minted}
\end{frame}


\begin{frame}[fragile]{Implementacja -- głęboka integracja}
\footnotesize \begin{minted}[mathescape]{haskell}
inRegion p Empty = False
inRegion p Circle = distance p (0,0) <= 1
inRegion (x, y) Square = abs x <= 1 && abs y <= 1
inRegion p (Outside r) = not (inRegion p r)
inRegion (x, y) (Scale (sx, sy) r) =
  inRegion (x / sx, y / sy) r
inRegion (x, y) (Translate (sx, sy) r) =
  inRegion (x - sx, y - sy) r
inRegion p (Intersect r1 r2) = inRegion p r1 && inRegion p r2
inRegion p (Union r1 r2) = inRegion p r1 || inRegion p r2
\end{minted}
\end{frame}

\begin{frame}[fragile]{Implementacja -- głęboka integracja}
\footnotesize \begin{minted}[mathescape]{haskell}
empty = Empty
circle = Circle
square = Square
outside = Outside
scale = Scale
translate = Translate
(/\) = Intersect
(\/) = Union
\end{minted}
\end{frame}

\begin{frame}[fragile]{Własności geometryczne}
\footnotesize \begin{minted}[mathescape]{haskell}
...
\end{minted}
\end{frame}



\section{Trudności}

\begin{frame}
Implementując języki EDSL w Haskellu, powinniśmy mieć
świadomość, że w zależności od wybranego stopnia integracji
mogą się pojawić problemy ze współdzieleniem obliczeń (ang.
\emph{sharing}) lub rekursją.
\end{frame}

\begin{frame}[fragile]{Prosty kalkulator}
W celu zobrazowania problemów zdefiniujmy bardzo prosty
język EDSL, o następującym interfejsie:
\footnotesize \begin{minted}{haskell}
data Expr
one :: Expr
plus :: Expr -> Expr -> Expr
eval :: Expr -> Int
\end{minted}
\end{frame}


\subsection{Współdzielenie}

\begin{frame}
\begin{center}
Jaki jest problem ze współdzieleniem?
\end{center}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji płytkiej}
\footnotesize \begin{minted}{haskell}
type Expr = Int
one = 1
plus = (+)
eval = id
\end{minted}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji płytkiej}
\footnotesize \begin{minted}{haskell}
*Main> one `plus` one `plus` one
3
*Main> eval (one `plus` one `plus` one)
3
\end{minted}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji płytkiej}
Zdefiniujmy teraz prostą funkcję
\footnotesize \begin{minted}{haskell}
treeI :: Int -> Expr
treeI 0 = one
treeI n = let shared = treeI (n-1) in shared `plus` shared
\end{minted}
\pause
\normalsize Współdzielenie za pomocą Haskellowego \texttt{let}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji płytkiej}
Współdzielenie rzeczywiście działa w tym przypadku!
\footnotesize \begin{minted}{haskell}
*Main> treeI 30
1073741824
\end{minted}
\pause
\normalsize Liczy się w ułamku sekundy, bo jest liniowe!
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji płytkiej}
Niestety, płytka integracja jest za słaba, aby zdefiniować
funkcję, która drukuje wyrażenie
\footnotesize \begin{minted}{haskell}
text :: Expr -> String
text = ???
\end{minted}
\pause
\normalsize \begin{itemize}
   \item płytka integracja ma swoje ograniczenia
   \item zbyt szybko zadaliśmy semantykę naszym termom
\end{itemize}
\end{frame}


\begin{frame}[fragile]{Kalkulator w wersji głębokiej}
Spróbujmy zatem głębszej integracji
\footnotesize \begin{minted}{haskell}
data Expr = One | Add Expr Expr

one = One
plus = Add

eval One = 1
eval (Add e1 e2) = eval e1 + eval e2
\end{minted}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji głębokiej}
\footnotesize \begin{minted}{haskell}
*Main> one `plus` one `plus` one
Add (Add One One) One
*Main> eval (one `plus` one `plus` one)
3
\end{minted}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji głębokiej}
Teraz bez problemu możemy zdefiniować funkcję
drukującą wyrażenia
\footnotesize \begin{minted}{haskell}
text :: Expr -> String
text One = "1"
text (Add e1 e2) = "(" ++ text e1 ++ " + " ++ text e2 ++ ")"
\end{minted}
\pause
\begin{minted}{haskell}
*Main> text (one `plus` one `plus` one)
"((1 + 1) + 1)"
\end{minted}
\end{frame}

\begin{frame}[fragile]{Kalkulator w wersji głębokiej}
Ale przy okazji popsuliśmy sobie współdzielenie :(
\footnotesize \begin{minted}{haskell}
treeI :: Int -> Expr
treeI 0 = one
treeI n = let shared = treeI (n-1) in shared `plus` shared
\end{minted}
\pause
\footnotesize \begin{minted}{haskell}
*Main> eval (treeI 30)
\end{minted}
\normalsize Obliczenie trwa koszmarnie długo; czas wykładniczy
\end{frame}

\begin{frame}{Co się stało?}
Współdzielenie wprowadzone dzięki \texttt{let} jest tracone
podczas \texttt{plus}

Winna jest reprezentacja danych
\end{frame}

\begin{frame}{Remedium}
Musimy jawnie zaimplementować współdzielenie
\end{frame}


\begin{frame}[fragile]{Drugie podejście}
Dodajemy własną konstrukcję \texttt{let}
\footnotesize \begin{minted}{haskell}
data Expr = One
          | Add Expr Expr
          | Let Expr (Expr -> Expr)

one = One
plus = Add
let_ = Let
\end{minted}
\end{frame}


\begin{frame}[fragile]{Drugie podejście}
Ale nadal mamy problem...
\footnotesize \begin{minted}{haskell}
eval One = 1
eval (Add e1 e2) = eval e1 + eval e2
eval (Let e1 e2) = let shared = eval e1 in (e2 (??? shared))
\end{minted}
\pause
\normalsize \begin{itemize}
   \item nie zgadzają nam się typy
   \item \texttt{shared} jest typu \texttt{Int}
   \item \texttt{e2} jest typu \texttt{Expr -> Expr}
\end{itemize}
\end{frame}


\begin{frame}{Co teraz?}
Moglibyśmy ,,cytować'' policzony term z powrotem do
reprezentacji języka, ale takie podejście jest mało
efektywne, tracimy zalety współdzielenia
\end{frame}

\begin{frame}{Co teraz?}
Jawnie zdefiniować w języku ,,opakowanie'' dla policzonej
wartości. Reprezentacja przestaje być drzewem, a zaczyna być
grafem.

\bigskip
Bruno~C.~d.~S.~Oliveira, Andres~Löh --- \emph{Abstract Syntax
Graphs for Domain Specific Languages}
\end{frame}


\begin{frame}[fragile]{Jawne współdzielenie w ASG}
Do reprezentacji grafu użyjemy PHOAS (ang. \emph{parametric
higher-order abstract syntax})

\footnotesize \begin{minted}{haskell}
data Expr a = One
            | Add (Expr a) (Expr a)
            | Var a
            | Let (Expr a) (a -> Expr a)

type ClosedExpr = forall a. Expr a

one = One
plus = Add
let_ :: Expr a -> (Expr a -> Expr a) -> Expr a
let_ e1 e2 = Let e1 (\x -> e2 (Var x))
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
\footnotesize \begin{minted}{haskell}
eval :: Expr Int -> Int
eval One = 1
eval (Add e1 e2) = eval e1 + eval e2
eval (Var n) = n
eval (Let e1 e2) = let shared = eval e1 in eval (e2 shared)
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
Wreszcie możemy zdefiniować naszą funkcję budującą term
z wykorzystaniem jawnego współdzielenia.
\footnotesize \begin{minted}{haskell}
treeE :: Int -> ClosedExpr
treeE 0 = one
treeE n = let_ (treeE (n - 1)) (\shrd -> shrd `plus` shrd)
\end{minted}
\pause
\normalsize Ale nadal możemy korzystać z Haskellowego \texttt{let}
\footnotesize \begin{minted}{haskell}
treeI :: Int -> ClosedExpr
treeI 0 = one
treeI n = let shrd = treeI (n-1) in shrd `plus` shrd
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
Takie współdzielenie jest również obserwowalne
\footnotesize \begin{minted}{haskell}
text :: ClosedExpr -> String
text e = go e 0
 where
  go :: Expr String -> Int -> String
  go One _ = "1"
  go (Add e1 e2) c = "(" ++ go e1 c ++ " + " ++ go e2 c ++ ")"
  go (Var x) _ = x
  go (Let e1 e2) c =
   "(let " ++ v ++ " = " ++ go e1 (c + 1) ++
   " in " ++ go (e2 v) (c + 1) ++ ")"
    where
     v = "v" ++ show c
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
\footnotesize \begin{minted}{haskell}
*Main> text $ treeI 2
"((1 + 1) + (1 + 1))"
*Main> text $ treeE 2
"(let v0 = (let v1 = 1 in (v1 + v1)) in (v0 + v0))"
*Main> text $ treeI 3
"(((1 + 1) + (1 + 1)) + ((1 + 1) + (1 + 1)))"
*Main> text $ treeE 3
"(let v0 = (let v1 = (let v2 = 1 in (v2 + v2)) in (v1 + v1))
in (v0 + v0))"
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
\footnotesize \begin{minted}{haskell}
inline :: Expr (Expr a) -> Expr a
inline One = One
inline (Add e1 e2) = Add (inline e1) (inline e2)
inline (Var x) = x
inline (Let e1 e2) = inline (e2 (inline e1))
\end{minted}
\end{frame}


\begin{frame}[fragile]{Jawne współdzielenie w ASG}
\footnotesize \begin{minted}{haskell}
*Main> text $ inline $ treeI 3
"(((1 + 1) + (1 + 1)) + ((1 + 1) + (1 + 1)))"
*Main> text $ inline $ treeE 3
"(((1 + 1) + (1 + 1)) + ((1 + 1) + (1 + 1)))"
\end{minted}
\end{frame}

\begin{frame}[fragile]{Jawne współdzielenie w ASG}
\footnotesize \begin{minted}{haskell}
*Main> eval $ treeE 30 -- szybkie
*Main> eval $ treeI 30 -- powolne
*Main> eval $ inline $ treeE 30 -- powolne
\end{minted}
\end{frame}

\begin{frame}[fragile]{Sharing -- podsumowanie}
\begin{itemize}
   \item dwa rodzaje współdzielenia: \emph{preservable}
         i \emph{observable}   
   \item przy płytkiej integracji wykorzystujemy haskellowy
         \emph{preservable sharing} (\texttt{let}), nie możemy wyrazić
         \emph{observable sharing}         
   \item przy głębokiej integracji zazwyczaj sami musimy
         zaimplementować współdzielenie
   \item eleganckie rozwiązanie w postaci jawnego współdzielenia
         za pomocą ASG
\end{itemize}
\end{frame}


\subsection{Rekursja}
\begin{frame}
\begin{center}
  \Large Po co nam rekursja?
\end{center}
\end{frame}

\begin{frame}[fragile]{Wzbogacamy składnię}

\footnotesize \begin{minted}{haskell}
data Expr a = Lit Int
            | Add (Expr a) (Expr a)
            | IfZero (Expr a) (Expr a) (Expr a)
            | Var a
            | Let (Expr a) (a -> Expr a)
            | Lam (a -> Expr a)
            | App (Expr a) (Expr a)

type ClosedExpr = forall a. Expr a
\end{minted}

\end{frame}

\begin{frame}[fragile]{Sprytne konstruktory}

\footnotesize \begin{minted}{haskell}
plus = Add
apply = App
let_ e1 e2 = Let e1 (\x -> e2 (Var x))
lam_ e = Lam (\x -> e (Var x))
\end{minted}

\end{frame}

\begin{frame}[fragile]{Funkcje jako wartości}
\footnotesize \begin{minted}{haskell}
data Value = N Int | F (Value -> Value)
\end{minted}
\end{frame}

\begin{frame}[fragile]{Ewaluator}
\footnotesize \begin{minted}{haskell}
eval :: Expr Value -> Value
eval (Lit n) = N n
eval (Add e1 e2) = add (eval e1) (eval e2)
  where add (N m) (N n) = N (m + n)
eval (IfZero e1 e2 e3) = ifZero (eval e1) (eval e2) (eval e3)
  where ifZero (N n) v1 v2 = if n == 0 then v1 else v2
eval (Var x) = x
eval (Let e1 e2) = eval (e2 (eval e1))
eval (Lam e) = F (\v -> eval (e v))
eval (App e1 e2) = app (eval e1) (eval e2)
  where app (F f) v = f v
\end{minted}
\end{frame}

\begin{frame}[fragile]{Przykład, jeszcze bez rekursji}
Chcemy zakodować w naszym EDSL-u haskellowy term:
\footnotesize \begin{minted}{haskell}
let dec x = x - 1
    twice f x = f (f x)
in  twice twice dec 10
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
example1 = let_ (lam_ (\x -> x `plus` Lit (-1)))
  (\dec ->
    let_ (lam_ (\f -> lam_ (\x -> f `apply` (f `apply` x))))
     (\twice ->
       (twice `apply` twice `apply` dec `apply` (Lit 10))
     )
  )
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
*Main> eval example1
6
\end{minted}
\end{frame}

\begin{frame}[fragile]{Dodajemy rekursję}
\footnotesize \begin{minted}{haskell}
data Expr a = ... -- jak poprzednio
            | Mu (a -> Expr a)

mu_ e = Mu (\x -> e (Var x))

eval :: ClosedExpr -> Value
eval ... = ... -- jak poprzednio
eval (Mu e) = fix (\v -> eval (e v))
  where
    fix :: (a -> a) -> a
    fix f = let r = f r in r
\end{minted}
\end{frame}

\begin{frame}[fragile]{Przykład z rekursją -- mnożenie}
Chcemy zakodować w naszym EDSL-u haskellowy term:
\footnotesize \begin{minted}{haskell}
mul m = let rec n =
          if n == 0 then 0
          else m + (rec (n - 1))
        in rec
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
mul :: ClosedExpr
mul = lam_ (\m -> mu_ (\rec -> lam_ (\n ->
        IfZero n (Lit 0)
        (m `plus` (rec `apply` (n `plus` Lit (-1))))
      )))
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
*Main> eval (mul `apply` (n 6) `apply` (n 3))
18
\end{minted}
\end{frame}


\begin{frame}[fragile]{Przykład z rekursją -- silnia}
\footnotesize \begin{minted}{haskell}
letrec_ :: (Expr a -> Expr a) -> (Expr a -> Expr a) -> Expr a
letrec_ e1 e2 = Let (Mu (\x -> e1 (Var x))) (\x -> e2 (Var x))
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
fact :: ClosedExpr
fact = letrec_ (\rec -> lam_ (\n ->
    IfZero n (Lit 1)
    (mul `apply` n `apply` (rec `apply` (n `plus` Lit (-1))))
  ))
  (\rec -> lam_ (\m -> rec `apply` m))
\end{minted}
\pause

\footnotesize \begin{minted}{haskell}
*Main> eval (fact `apply` (n 5))
120
\end{minted}
\end{frame}


\begin{frame}[fragile]{Rekursja wzajemna}
Tak zaimplementowana rekursja nie wystarczy jednak do zakodowania
takiego termu:

\footnotesize \begin{minted}{haskell}
let dec  x     = x - 1
    even x f e = if x == 0 then t else odd (dec x) t e
    odd  x f e = if x == 0 then e else even (dec x) t e
in even 4 1 0
\end{minted}
\pause

\normalsize Musimy jawnie reprezentować rekursję wzajemną!
\end{frame}

\begin{frame}[fragile]{Rekursja wzajemna}
\footnotesize \begin{minted}{haskell}
data Expr a = ... -- jak poprzednio
            | LetRec ([a] -> [Expr a]) ([a] -> Expr a)

letrec_ :: ([Expr a]->[Expr a])->([Expr a]->Expr a)->Expr a
letrec_ es e = LetRec (\xs -> es (map Var xs))
                      (\xs -> e (map Var xs))

eval :: ClosedExpr -> Value
eval ... = ... -- jak poprzednio
eval (LetRec es e) = let rs = map eval (es rs) in eval (e rs)
\end{minted}
\end{frame}

\begin{frame}[fragile]{Rekursja wzajemna}
Teraz możemy zdefiniować już wspomniany term:
\footnotesize \begin{minted}{haskell}
example = letrec_ (\ ~[dec,even,odd] ->
  [ lam_ (\x -> x `plus` Lit (-1))
   ,lam_ (\x -> lam_ (\t -> lam_ (\e ->
      IfZero x t
      (odd `apply` (dec `apply` x) `apply` t `apply` e)
    )))
   ,lam_ (\x -> lam_ (\t -> lam_ (\e ->
      IfZero x e
      (even `apply` (dec `apply` x) `apply` t `apply` e)
     )))
  ])
  (\ [dec,even,odd] ->
     even `apply` Lit 4 `apply` Lit 1 `apply` Lit 0)
\end{minted}
\end{frame}

\begin{frame}[fragile]{Rekursja wzajemna}
\footnotesize \begin{minted}{haskell}
*Main> eval example
1
\end{minted}
\end{frame}

\begin{frame}[fragile]{Cechy}
\begin{itemize}
  \item w naszym EDSL-u potrafimy wyrazić $\lambda$-abstrakcję,
        aplikację, jawne współdzielenie i (wzajemną) rekursję
  \item korzystając z haskellowych mechanizmów, nie musimy jawnie
        zajmować się środowiskami, domknięciami czy wiązaniem
  \item rekursja pozostaje obserwowalna! możemy napisać funkcję:
        \mint{haskell}|text :: ClosedExpr -> String|
        która wydrukuje nam nasze wyrażenie
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Cechy}
\begin{itemize}
  \item możemy używać haskellowego \texttt{let} do współdzielenia,
  \item obserwowanie takiego współdzielenia nadal jest możliwe,
        ale wymaga sztuczki
  \item odbudowa naszego termu w jawnie reprezentowalny graf
  \item funkcja \texttt{reifyGraph} z pakietu \texttt{data-reify}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Co dalej?}
\begin{itemize}
  \item nasza implementacja rekursji wzajemnej operuje na dwu listach
  \item zmusza nas do użycia leniwego pattern matchingu w naszej reprezentacji
  \item wymaga to niejawnego niezmiennika, że rozmiar obu list musi być ten sam
  \item sprawniejsza implementacja: lista par
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Co dalej?}
\begin{itemize}
  \item nasza reprezentacja nadal pozwala zdefiniować źle otypowane termy
  \item aby temu zaradzić, możemy wykorzystać system typów Haskella
        (aka. \emph{well typed ASG})
\end{itemize}
\end{frame}



\section{Praktyczny przykład}

\subsection*{Problem współdzielonych wydatków}
\begin{frame}{Idea}
\begin{itemize}
   \item wiele osób jedzie razem na wycieczkę
   \item nie zawsze każdy płaci za siebie
   \item pod koniec wycieczki chcemy się sprawnie rozliczyć
\end{itemize}
\end{frame}

\begin{frame}[fragile]
Zaczynamy od zdefiniowania osoby
\footnotesize \begin{minted}{haskell}
newtype Person = Person { name :: String }
                 deriving (Eq, Ord, Show)

dexter = Person "Dexter"
angel  = Person "Angel"
debra  = Person "Debra"
harry  = Person "Harry"
\end{minted}
\end{frame}

\begin{frame}[fragile]
Chcemy, aby nasz DSL wyglądał tak:
\footnotesize \begin{minted}[mathescape]{haskell}
trip = sharedexpenses $ do
    dexter `spent` 5300
    angel  `spent` 2700
    debra  `spent`  800
    harry  `spent` 1900
    debra  `spent` 1700
    angel  `spent` 2200
    dexter `gave` harry $ 2000
    angel  `gave` debra $ 3200
    angel  `gave` harry $ 500
\end{minted}
\end{frame}

\begin{frame}[fragile]
Na koniec chcemy otrzymać minimalne rozwiązanie
\footnotesize \begin{minted}{haskell}
*Main> solve trip
["Debra pays 4350 to Angel",
 "Harry pays 3650 to Dexter",
 "Harry pays 600 to Angel"]
\end{minted}
\end{frame}

\begin{frame}[fragile]
Wydatki będziemy przechowywać w mapie opakowanej w monadę stanu.
\footnotesize \begin{minted}{haskell}
sharedexpenses :: State (Map Person Int) () -> Map Person Int
sharedexpenses f = execState f empty

spent payer money = modify $ insertWith (+) payer money

gave lender borrower money = modify $
 (adjust (+ money) lender) . (adjust (subtract money) borrower) 
\end{minted}
\end{frame}


\begin{frame}[fragile]
\tiny \begin{minted}{haskell}
solve :: Map Person Int -> [String]
solve st = solve' err $ Map.map (\m -> m - avg) st
 where
  err = 1 + size st
  avg = round $ (toRational $ fold (+) 0 st) / (toRational $ size st)
solve' _ st | Map.null st = []
solve' err st =
 (name payer ++ " pays " ++ show amount ++ " to " ++ name receiver) : solve' err newstate
  where
   (payer, debt) = foldrWithKey (getpers True) (Person "", 0) st
   (receiver, credit) = foldrWithKey (getpers False) (Person "", 0) st
   getpers True p m (_, m0) | m < m0 = (p, m) -- Gets payer
   getpers False p m (_, m0) | m > m0 = (p, m) -- Gets receiver
   getpers _ _ _ e = e
   amount = min (-debt) credit
   newstate = Map.filter (\c -> c < -err || err < c) (mapWithKey statefix st)
   statefix p m | p == receiver = m - amount
   statefix p m | p == payer = m + amount
   statefix _ m = m
\end{minted}
\end{frame}

\begin{frame}[fragile]
Działa!

\footnotesize \begin{minted}{haskell}
*Main> solve $ sharedexpenses $ do
  angel  `spent`  300
  debra  `spent`  500
  dexter `gave` harry $ 200
  harry  `spent` 1000
  dexter `gave` debra $ 200
  dexter `spent`  600
  
["Debra pays 200 to Harry",
 "Angel pays 100 to Harry",
 "Angel pays 100 to Dexter"]
\end{minted}
\end{frame}

\begin{frame}
To wszystko!
\begin{itemize}
   \item składnię naszego języka zaimplementowaliśmy za pomocą
         haskellowych funkcji
   \item do reprezentacji wykorzystaliśmy Haskellowe typy danych
   \item płytka integracja -- obyło się bez parsera, AST, etc.
\end{itemize}
\end{frame}

\section*{Literatura}

\begin{frame}
\begin{itemize}
   \item Modular Domain Specific Language and Tools. Paul~Hudak.
         Department of Computer Science, Yale University.
   \item Abstract Syntax Graphs for Domain Specific Languages.
         Bruno C. d. S. Oliveira, Andres Löh.
   \item Making EDSLs Fly, Lennart Augustsson, TechMesh~2012
         \href{http://www.youtube.com/watch?v=7gF7iFB4mFY}{http://www.youtube.com/watch?v=7gF7iFB4mFY}
   \item DSL lectures, Veronica Gaspes
         \href{http://www2.hh.se/staff/vero/dsl}{http://www2.hh.se/staff/vero/dsl}
\end{itemize}
\end{frame}

\section*{Koniec}

\begin{frame}
\begin{center}
   \LARGE{Pytania?}
\end{center}
\end{frame}

\end{document}
