4
\$\begingroup\$

I am trying to design a DSL for writing C. Here is my code as a GitHub gist (Github does not allow me to have slashes in the filenames so I have used underscores instead). It depends on packages free and process.

My goal is to make the DSL low level enough that one can reasonably predict the output code, and convenient enough to build abstractions on top of.

I would like especially to receive comments on the design. How can I use standard idioms to make the code more maintainable, extendable, composable and easy to use?

Notes on design:

Some functions are prefixed with c- to avoid clashes with Haskell keywords/common functions, e.g. cunion, cwhile, others are not, e.g. struct, typedef. I realize this is confusing, comments on naming convention are welcome.

Operators are suffixed with :, e.g. +: (add), =: (assign), ~: (bitwise complement), ^: (xor).

Generally the constructors are implemented as functions which generate functions.

For example:

varDecl  :: Type -> Iden -> Free Stmt Expr
chgType  :: (Type -> Type) -> (Iden -> Free Stmt a) -> Iden -> Free Stmt Expr
ptr      :: (Iden -> Free Stmt a) -> Iden -> Free Stmt Expr
fun      :: (Iden -> Free Stmt a) -> Iden -> [Free Stmt b] -> Free Stmt () -> Free Stmt ([Expr] -> Free Stmt ())

varDecl t i = let
  v = Var $ TypedIden t i
  in liftF $ VarDecl v (VarExpr v)
int = varDecl CInt

chgType l f i = let
  t = unsafeExtractType f
  in varDecl (l t) i

ptr = chgType CPtr

fun l i vs s = let
  ti = unVar $ extractDecl $ unFree $ l i
  f  = Fun ti (map (extractDecl . unFree) vs) s
  in liftF $ FunDecl f (\es -> stmt $ FunCall f es)

This is ugly but it allows us to write statements like:

x <- ptr int "x"
f <- fun int "f" [int "x1"] $ do
  creturn $ x +: "x1"
f[x]

So, ptr simply takes a TypedIden-like generating function and gives another function which changes the Type in the output. fun takes a TypedIden-like generating function, identifier, list of arguments and a Free Stmt (which really must be a VarDecl) and gives back a function which creates a FunCall expression. This is nice is because now function calls in the target are modeled by function application to a list of Expr.

Here's an example using the DSL:

import Language.C.DSL
import Language.Format
main = prettyPrint $ do
  include "stdio.h"
  includeLocal "foo.h"
  intptr_t <- typedef (ptr int) "intptr_t"
  x <- int "x"
  y <- double "y"
  z <- ptr intptr_t "z"
  w <- carray int "w" 21
  ptrToConstInt <- ptr (cconst int) "a"
  constPtrToInt <- cconst (ptr int) "b"
  f <- fun int "f" [int "x1"] $ do
    cswitch y $ do
      ccaseBreak (boolCompl x) $ do
        cif (bitCompl "x1") $ do
          cwhile (insertComment "Lorem ipsum" (1::Int) !=: postincr x) $ do
            x +: "x1"
      cdefaultCase $ do
        x +: z
    creturn $ x +: "x1"

  block $ do
    x' <- int "x"
    boolCompl x'
  x +: y
  x =: y +: f[x, insertComment "Lorem ipsum dolor sit amet" y]
  swap [x,y,z]

Which generates the following code:

#include <stdio.h>
#include "foo.h"
typedef int* intptr_t;
int x;
double y;
intptr_t* z;
int w[21];
int const* a;
int* const b;
int f(int x1) {
  switch (y) {
    case (!x) : {
      if (~x1) {
        while (1/*Lorem ipsum*/ != x++) {
          x + x1;
        }
      }
      break;
    }
    default : {
      x + z;
    }
  }
  return x + x1
}
{
  int x;
  !x;
}
x + y;
x = y + f(x, y/*Lorem ipsum dolor sit amet*/);
int tmp;
tmp = x;
x = y;
y = z;
z = tmp;

I'm concerned about the style I've used since I am a beginning Haskell programmer. There's some pretty ugly hacks in here:

unsafeExtractType :: (a -> Free Stmt b) -> Type
unsafeExtractType f = let
  app = f undefined
  in extractType . unVar . extractDecl . unFree $ app
chgType :: (Type -> Type) -> (Iden -> Free Stmt a) -> Iden -> Free Stmt Expr
chgType l f i = let
  t = unsafeExtractType f
  in varDecl (l t) i

The intent is to take a function which turns an identifier into a typed identifier, and change the type of the output. To indicate that the identifier is not supposed to be touched, I pass in undefined as an 'assert' that the function passed in does not further touch or pass around the identifier. I think that this is similar to the functor laws, but I am not sure how to encapsulate this as a functor.

Another idiom which seems hack-ish, lift x into the monad and then immediately break the abstraction by extracting it from the monad. For instance,

instance ExprLike (Free Stmt a) where
  expr (Free (ExprStmt e _)) = e
x +: y        :: Free Stmt ()
z =:          :: ExprLike a -> Free Stmt ()
z =: (x +: y) :: Free Stmt ()

Okay so what is going on here? x +: y generates a monadic expression. expr then extracts it from the monad breaking the abstraction. This smells bad because it is a partial function and could generate runtime failure. Further, it is like multiple inheritance where ExprLike is the base class of both Expr and FreeStmt () (which itself may contain an Expr). Unfortunately it is the only boilerplate-free way I have come up with for treating x +: y as a statement or expression depending on context.

EDIT: Here's a potential solution to the functor problem. Instead of thinking of the identifier as the thing that's being carried around, think of the identifier as the container. To wit,

import Data.Functor
type Iden = String
data Identified a = Identified a Iden
instance Functor Identified where
  fmap f (Identified x s) = Identified (f x) s
data Type = CInt | CPtr Type
ptr :: (Iden -> Identified Type) -> (Iden -> Identified Type)
ptr f i = CPtr <$> f i
int :: Iden -> Identified Type
int i = Identified CInt i
type ArgType = Type
type BodyType = String
data FunDef = FunDef Type [ArgType] BodyType
type Fun = Identified FunDef
fun :: (Iden -> Identified Type) -> Iden -> [ArgType] -> BodyType -> Fun
fun f i args body = let
  it :: Identified Type
  it = f i
  in ($ body) <$> ($ args) <$> FunDef <$> it -- a bit ugly but it typechecks

This way we can safely create a container (which is the identifier) and change its 'payload' by way of fmap.

\$\endgroup\$
4
\$\begingroup\$

Cool stuff! You might also be interested in Galois's Ivory DSL, which does similar things, and has been used to write the code for an autonomous quadcopter / some Boeing autonomous helicopter. It's full of cool tricks that may be relevant:

https://hackage.haskell.org/package/ivory

http://dl.acm.org/citation.cfm?id=2804318

For FFI with C, it might also be worth checking out http://hackage.haskell.org/package/inline-c

I'm not sure what to do about unsafeExtractType. I think you have to change the representation to not be a function in order to resolve this.

Another idiom which seems hack-ish, lift x into the monad and then immediately break the abstraction by extracting it from the monad.

One way to solve this is to make Stmt into a GADT. GADTs allow you to safely restrict which constructors are possible in a datatype, and ASTs are a classic use for it. You'll need tags, though. Something like:

data Stmt tag next where
  ExprStmt :: Expr -> next -> Stmt Expr next
  -- ...

Then, if no other constructors provide a Stmt Expr a, we can write a safe ExprLike (Free (Stmt Expr) a).

\$\endgroup\$
  • \$\begingroup\$ Interesting, thanks for the GADT suggestion. I'm posting a possible solution to the functor problem. \$\endgroup\$ – Charles Cooper Sep 9 '15 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.