================================ F-lite: a core subset of Haskell Matthew N, 26 November 2008

F-lite is a core subset of Haskell. Unlike GHC Core and Yhc Core, F-lite has a concrete syntax. You can write F-lite programs in a file, and pass them to the F-lite interpreter or compiler. Another way to view F-lite is as a minimalist lazy functional language.

F-lite is untyped

But as it is a subset of Haskell, you can use a Haskell implementation to type-check F-lite programs.

EXAMPLE 0: F-lite definition of 'append'. Definitions of 'Nil' and 'Cons' are not required - there is no need to define algebraic data types.

append Nil ys = ys; append (Cons x xs) ys = Cons x (append xs ys);

(The use of semi-colons to seperate equations is mandatory.)

F-lite supports uniform pattern matching

Pattern matching is uniform if and only if the order of equations doesn't matter (Wadler '86). Uniform pattern matching can be easily and efficiently compiled to core case expressions. A core case expression is one whose patterns all have the form 'constructor applied to zero or more variables'. The fact that the order of equations doesn't matter is also useful when transforming functional programs, for example by fold/unfold transformations.

EXAMPLE 1: F-lite definition of 'zipWith', illustrating uniform pattern matching.

zipWith f Nil ys = Nil; zipWith f (Cons x xs) Nil = Nil; zipWith f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith f xs ys);

EXAMPLE 2: F-lite definition of 'init', illustrating nested, incomplete, uniform pattern matching.

init (Cons x Nil) = Nil; init (Cons x (Cons y ys)) = Cons x (init (Cons y ys));

EXAMPLE 3: F-lite definition of 'init', using a case expression.

init xs = case xs of { Cons x Nil -> Nil; Cons x (Cons y ys) -> Cons x (init (Cons y ys)); };

(The use of semi-colons to seperate case alternatives is mandatory.)

F-lite supports 'let'-expressions

But they may only bind expressions to variables (not patterns).

EXAMPLE 4: F-lite definition of 'pow', the power-list function, illustrating a let expression.

pow Nil = Cons Nil Nil; pow (Cons x xs) = let { rest = pow xs } in append rest (map (Cons x) rest);

EXAMPLE 5: F-lite definition of 'repeat', using a let expression to introduce a cyclic data structure.

repeat x = let { xs = Cons x xs } in xs;

F-lite supports primitive integers

Finite precision integers along with the following arithmetic functions are allowed: (+), (-), (<=), (==), (/=). The latter three return 'True' or 'False' accordingly. These operators must be written in prefix form and cannot be partially applied.

EXAMPLE 6: F-lite definition of 'negate'.

negate n = (-) 0 n;

(Negative literals are not supported.)

EXAMPLE 7: F-lite definition of 'fromTo'.

fromTo n m = case (<=) n m of { True -> Cons n (fromTo ((+) n 1) m); False -> Nil; };

F-lite supports printing

Two primitives, 'emit' and 'emitInt', are provided for printing characters and integers respectively.

EXAMPLE 8: Printing the string "hi!" in F-lite.

sayHi k = emit 'h' (emit 'i' (emit '!' k))

When evaluated, 'sayHi k' will print "hi!" and return 'k' (the continuation).

EXAMPLE 9: 'Hello world' in F-lite.

emitStr Nil k = k; emitStr (Cons x xs) k = emit x (emitStr xs k);

main = emitStr "Hello world!\n" 0;

String literals are internally translated to 'Nil'-'Cons' lists of characters. The result of the 'main' function is expected to be an integer - the displaying of any output must be done explicitly by the programmer.

EXAMPLE 10: Full F-lite program to display the 10th fibonacci number.

{

fib n = case (<=) n 1 of { True -> 1; False -> (+) (fib ((-) n 2)) (fib ((-) n 1)); };

emitStr Nil k = k; emitStr (Cons x xs) k = emit x (emitStr xs k);

main = emitStr "fib(10) = " (emitInt (fib 10) (emit '\n' 0));

}

The braces enclosing the program are indeed mandatory. The primitive 'emitInt' function is like 'emit' but prints an integer rather than a character. Both 'emit' and 'emitInt' must be applied to at least one argument.

Our implementation

Our F-lite implementation includes both an interpreter (written in Haskell) and a compiler (to C code - see Memo 22). It works in both Hugs and GHC. For example, in the source directory, using Hugs:

runhugs fl-pure.hs examples/Fib.hs fib(10) = 89

and likewise using GHC:

ghc -O2 --make fl-pure -o fl

./fl examples/Fib.hs fib(10) = 89

A Cabal script can be used to install the parsec version using GHC:

cabal install

flite examples/Fib.hs fib(10) = 89

or even the pure version:

cabal install -f "pure"

flite-pure examples/Fib.hs fib(10) = 89

To compile F-lite programs, use the '-c' command-line option, and redirect the output to a C file of your choice.

flite -c ../examples/Fib.hs > /tmp/Fib.c

The resulting C file can be compiled (with optimisations) using GCC:

gcc -O3 /tmp/Fib.c -o Fib

./Fib fib(10) = 89