Sun Jul 24 10:43:55 CEST 2011

Higher-order abstract syntax

It's quite neat really: instead of using a concrete type + operations,
use a type class that can abstract over many representation types.

The downside is that when you want to make the representation into a
data type, something more powerful than ordinary algebraic types is
necessary.  However, functional representation isn't an issue, and
since terms are necessary well-typed, an untyped rep might also be
enough to generate assembly code.

type Tfloat = Double
type Tint   = Integer
type Tbool  = Bool

type Op2 repr t = repr t -> repr t -> repr t
type Op1 repr t = repr t -> repr t

class (Show (repr Tint),   Eq (repr Tint),
       Show (repr Tfloat), Eq (repr Tfloat)) 
      => Semantics repr where
  -- Literals
  int   :: Tint   -> repr Tint
  float :: Tfloat -> repr Tfloat
  bool  :: Tbool  -> repr Tbool
  -- Integer primitives
  isign :: Op1 repr Tint
  iabs  :: Op1 repr Tint
  iadd  :: Op2 repr Tint
  isub  :: Op2 repr Tint
  imul  :: Op2 repr Tint
  idiv  :: Op2 repr Tint
  imod  :: Op2 repr Tint
  -- Float primitives
  fsign :: Op1 repr Tfloat
  fabs  :: Op1 repr Tfloat
  fadd  :: Op2 repr Tfloat
  fsub  :: Op2 repr Tfloat
  fmul  :: Op2 repr Tfloat
  fdiv  :: Op2 repr Tfloat
  fsin  :: Op1 repr Tfloat
  fcos  :: Op1 repr Tfloat
  fexp  :: Op1 repr Tfloat
  -- Conditional
  if_ :: repr Tbool -> repr a -> repr a -> repr a
  -- Type converssions
  i2f   :: repr Tint   -> repr Tfloat
  f2i   :: repr Tfloat -> repr Tint