Introduction

MetaFun is a program to compile functional programs into C++ template metaprograms. It allows you to write programs in the very Haskell-like language Kiff (for Keep It Fun & Functional), and then use them as compile-time C++ metaprograms.

You can download the latest version of MetaFun using Git:

Kiff: The input language

MetaFun's input language, Kiff, is a simplified version of Haskell. It supports the following features of Haskell:

• Algebraic data types (data)
• (!) Type synonyms (type)
• Declared types for definitions
• Parametric polymorphism (but not typeclasses)
• The following builtin keywords:
  • let ... in ...
  • (!) λ ... -> ...
  • if ... then ... else ...
  • Special [x, y] syntax for lists

(note that features marked with a (!) are not actually supported by the MetaFun compiler yet.)

Kiff also includes the following primitives, mapped to the native C++ operators and types:

• The types Bool and Int
• The bool literals True and False
• Numeric literals
• Bool operators &&, || and !
• Int comparison: ==, !=, <, <=, >=, >
• Int operators: +, -, *, /, %

To give you an idea of what Kiff code looks like, here's a possible definition of sum:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f x [] = x
foldl f x (y:ys) = foldl f (f x y) ys

add x y = x + y -- The builtin operators are not first-class functions

sum xs = foldl add 0 xs -- Currying is not yet supported      

The compiler

The C++ code generated by the compiler consists of a bunch of template structs, one for each definition. Constructors are represented as structs with template parameters for constructor parameters. Bools and Ints are boxed.

For reference, here's MetaFun's C++ output for the above code of sum:

template< int > struct Int;
template< bool > struct Bool;
struct nil;
template< class, class > struct cons;
template< template< class, class > class, class, class > struct foldl;
template< class, class > struct add;
template< class > struct sum;

template< int x >
struct Int
{
  static const int v = x;
};

template< bool b >
struct Bool
{
  static const bool v = b;
};

template< template< class, class > class f, class x >
struct foldl< f, x, nil >
{
  typedef x v;
};

template< template< class, class > class f, class x, class y, class ys >
struct foldl< f, x, cons< y, ys > >
{
  typedef typename foldl< f, typename f< x, y >::v, ys >::v v;
};

template< class x, class y >
struct add
{
  typedef Int< (x::v) + (y::v) > v;
};

template< class xs >
struct sum
{
  typedef typename foldl< add, Int< 0 >, xs >::v v;
};      

Caveats

MetaFun is the result of me spending a week in bed because of a knee injury, and toying around with the concept of an easy-to-use language to write compile-time programs. The fact that it was thrown together in a couple of days shows: MetaFun is but a proof-of-concept demo. It's barely finished enough to compile the 9-digit solution program below. Here's a list of some notable known problems:

• Patterns are not matched in the order they appear in the source code. This is a serious problem, and one that I intend to fix one day. The problem is that when C++ chooses a template specializations, it favors the most specific one that matches, as opposed to the first one. This makes sense in the context of "sane" usages of templates, but this is definitely not what one would expect with a Haskell-like language.
• No currying in function calls
• No support for lambda expressions
• The type checker doesn't actually support type synonyms
• Zero optimization: Local definitions are lifted even when they could be local nested structs in C++

A detailed example

The following program solves the 9-digit problem using a simple backtracking algorithm. In fact, it is the result of a direct, manual backwards translation of Károly Lőrentey's solution, and was the motivating example behind writing MetaFun.

length [] = 0
length (first:rest) = 1 + (length rest)

value :: [Int] -> Int
value [] = 0
value (first:rest) = 10 * (value rest) + first

contains :: Int -> [Int] -> Bool
contains elem [] = False
contains elem (first:rest) = elem == first || (contains elem rest)


divisor_test :: [Int] -> Bool
divisor_test (first:rest) = let num = value (first:rest)
                                div = (length rest) + 1
                                mod = num % div
                            in mod == 0
                              
test_candidate :: [Int] -> Bool
test_candidate (first:rest) = divisor_test (first:rest) && !(contains first rest)

search_i :: Int -> Bool -> Bool -> [Int] -> Int
search_i len True True  (digit:rest) = value (digit:rest)
search_i len True False (digit:rest) = search len (1:digit:rest)
search_i len good final (digit:rest) = search len ((digit+1):rest)
                                          
search :: Int -> [Int] -> Int
search len []             = search len [1]
search len [10]           = -1
search len (10:next:rest) = search len ((next+1):rest)
search len (digit:rest)   = let good = test_candidate (digit:rest)
                                final = good && 1 + (length rest) == len
                            in search_i good final

run = search 9 []