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

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