Domain Specific Languages

• Computer languages for specific problems, e.g.
  • AWK: text extraction
  • SQL: database query
  • AMPL: mathematical modeling
  • PostScript: page rendering
  • TeX, LaTeX: document typesetting
  • HTML, CSS: hypertext markup and styling
• Domain specific by contrast with general purpose programming languages

Domain Specific Embedded Languages

• DSLs embedded as libraries in a general-purpose host language
• Avoids need for custom parser, typechecker, interpreter, compiler, etc.
• Allows escaping to the host language when necessary
• Makes it easier to experiment DSL changes
• Easier if the host language supports:
  • lightweight, flexible syntax
  • operator overloading
  • higher-order functions
  • delayed evaluation
  • monads (“programable semicolon”)

Anatomy of a DSEL

• A set of types modeling concepts of the domain
• Constructor functions for building elements of these types
• Combinators for combining and modifying elements
• Run functions for making observations of the elements

Primitive vs derived operations

• A primitive operation is defined directly from the values of types involved
• A derived operation can be defined from other operations

Try to keep the set of primitive operations as small as possible!

Think about

Composition

• Basic elements should be as simple as possible
• Complex elements should be described by combining together basic elements

Abstraction

• The user shouldn’t have to know (or be allowed to exploit) the underlying implementation

Case study: DSEL for shapes

Designing the interface

type Shape
-- Constructor functions
empty      :: Shape
disc       :: Shape  -- at origin, unit radius 
square     :: Shape  -- at origin, unit size
-- Combinators
translate  :: Vec -> Shape -> Shape
scale      :: Vec -> Shape -> Shape
rotate     :: Angle -> Shape -> Shape
union      :: Shape -> Shape -> Shape
intersect  :: Shape -> Shape -> Shape
difference :: Shape -> Shape -> Shape
-- Run function
inside     :: Point -> Shape -> Bool

Primitive vs derived operations

• No obvious derived operations
• Sometimes introducing additional primitives allows simplifying other operations

Additional primitives

invert :: Shape -> Shape
transform :: Matrix -> Shape -> Shape

-- derived transformations;
-- recall sets and linear algebra
scale :: Vec -> Shape -> Shape
scale v = transform (matrix (vecX v) 0
                            0 (vecY v))

rotate :: Angle -> Shape -> Shape
rotate a = transform (matrix (cos a) (-sin a)
                             (sin a) (cos a))
difference :: Shape -> Shape -> Shape
difference a b = a `intersect` invert b

Mini-DSEL for linear algebra

type Matrix
type Vec
type Point = Vec -- represented as vectors

-- Constructor functions
vec   :: Double -> Double -> Vec
matrix :: Double -> Double ->
          Double -> Double -> Matrix

Mini-DSEL for linear algebra (2)

-- Combinator functions
mul :: Matrix -> Vec -> Vec
inv :: Matrix -> Matrix
sub :: Vec -> Vec -> Vec

-- Run functions
vecX, vecY :: Vec -> Double

Could add more operations, but this is enough for our purpose.

Implementing a DSEL

Shallow embedding

• Represent elements by their semantics
• Constructor functions and combinators do most of the work
• Run functions for free

Deep embedding

• Represent elements by their abstract syntax
• Constructors and combinators for free
• Most work done by the run functions

…or something in between.

Shallow embedding

What observations can we make of shapes?

inside :: Point -> Shape -> Bool

newtype Shape = Shape (Point -> Bool)

inside :: Point -> Shape -> Bool
inside p (Shape f) = f p

Shallow embedding (2)

If we choose the right embedding, the operations should be easy to implement.

empty = Shape $ \_ -> False
disc = Shape $ \p -> (vecX p)^2+(vecY p)^2 <= 1
square = Shape $ \p -> abs (vecX p) <= 1 &&
                       abs (vecY p) <= 1

union a b  = Shape $ \p -> inside p a ||
                           inside p b
intersect a b = Shape $ \p -> inside p a &&
                              inside p b
invert a = Shape $ \p -> not (inside p a)

Shallow embedding (3)

transform m a
    = Shape $ \p -> (m'`mul`p) `inside` a
    where m' = inv m  -- inverse matrix
    
translate v a
    = Shape $ \p -> (p`sub`v) `inside` a

Note that in both cases we modify the point rather than shape.

Deep embedding

Just a datatype of the primitive operations:

data Shape = Empty | Disc | Square
    | Translate Vec Shape
    | Transform Matrix Shape
    | Union Shape Shape
    | Intersect Shape Shape
    | Invert Shape

empty = Empty
disc = Disc
square = Square
translate = Translate
...

Deep embedding (2)

Using generalized algebraic data type (GADT) syntax:

data Shape where 
    -- Constructor functions
    Empty :: Shape
    Disc :: Shape
    Square :: Shape
    -- Combinators
    Translate :: Vec -> Shape -> Shape
    Transform :: Matrix -> Shape -> Shape
    Union     :: Shape -> Shape -> Shape
    Intersect :: Shape -> Shape -> Shape
    Invert    :: Shape -> Shape

Deep embedding (3)

All work happens in the run function.

inside :: Point -> Shape -> Bool
p `inside` Empty = False
p `ìnside` Disc  = (vecX p)^2+(vecY p)^2<=1
p `inside` Square= abs (vecX p)<=1 &&
                   abs (vecY p)<=1

(continues next slide)

Deep embedding (4)

(continued from previous slide)

p `inside` Translate v a
   = (p`sub`v) `inside` a
p `inside` Transform m a
   = mul (inv m) p `inside` a
p `inside` Union a b
   = p `inside` a || p `inside` b
p `inside` Intersect a b
   = p `inside` a && p `inside` b
p `inside` Invert a = not (p `inside` a)

Abstraction

module Shape
    ( module Matrix -- re-export matrix library
    , Shape -- don't export the implementation
    , empty, disc, square
    , translate, transform, scale, rotate
    , union, intersect, difference, invert
    , inside)
    where

import Matrix
...

The interface is the same for shallow and deep embedding — no visible difference to the user!

Exercise: render to ASCII art

data Window = Window
    { bottomLeft :: Point
    , topRight :: Point
    , resolution :: (Int,Int)
    }

pixels :: Window -> [[Point]]
...

render :: Window -> Shape -> String
render win sh
  = unlines $ map (map pixelAt) (pixels win)
  where pixelAt p | p`inside`sh = 'X'
                  | otherwise   = ' '