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 from GitHub.

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 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:

• 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 []