=========================================================
REDUCERON MEMO 49
hf: a tool that translates (a subset of) Haskell to Flite
Colin R, 17 May 2010
=========================================================

Roughly speaking, Flite is a Haskell subset.  But the process of
hand-translating Haskell to Flite is actually quite a chore -- I speak
from personal experience translating programs like Mate and KnuthBendix!
Not only are there the inherent constraints of a subset, there are
various lexical differences too.

Could the process be automated?  A full press-the-button translator
from Haskell 98 to Flite is infeasible.  For example, the only numbers
in Flite are bounded integers, and IO operations are unavailable.

This memo describes hf tool.  It can *assist* the human translator
in their work.  It takes Haskell source as its standard input.
The standard output gives Flite equivalents of the *translatable*
top-level declarations in the input, with comments to explain why the
missing declarations could not be translated.

Example
-------

Suppose ListFuns.hs contains the following:

  duplicates :: Eq a => [a] -> [a]
  duplicates []      =  []
  duplicates (x:xs)  =
    if not (contains d x) && contains xs x then x:d else d 
    where
    d  =  duplicates xs

  prefixes :: [a] -> [[a]]
  prefixes []      =  [[]]
  prefixes (x:xs)  =  [] : map (x:) (prefixes xs)

  suffixes :: [a] -> [[a]]
  suffixes []      =  [[]]
  suffixes (x:xs)  =  (x:xs) : suffixes xs

  perms :: [a] -> [[a]]
  perms []      =  [[]]
  perms xs      =  [x:p | (x,xs') <- picks xs, p <- perms xs']

  picks :: [a] -> [(a,[a])]
  picks []      =  []
  picks (x:xs)  =  (x,xs) : [(x',x:xs') | (x',xs') <- picks xs]

We apply hf:

  $ hf < ListFuns.hs 
  duplicates Nil = Nil ;
  duplicates (Cons x xs) =
    let { d = duplicates xs ; } in
      case
        case not (contains d x) f
          { True -> contains xs x ; False -> False ; }
        of {
        True -> Cons x d ;
        False -> d ;
        } ;

  -- hf could not translate prefixes (operator section)

  suffixes Nil = Cons Nil Nil ;
  suffixes (Cons x xs) = Cons (Cons x xs) (suffixes xs) ;

  -- hf could not translate perms (non-uniform pattern matching)

  -- hf could not translate picks (list comprehension)

What is translatable?
---------------------

The prototype translates little more than the Flite-equivalent subset of
Haskell.  However, some commonly occurring forms that have no immediate
equivalent are handled.

I have avoided mangling or inventing names.  For example, as (&&) is
not recognised in F-lite, infix expressions involving && are translated
directly to case expressions, to avoid conflicts in the name-space.

The scope of translation could be significantly increased with the
introduction of a lambda lifter, and I intend to add one.  For example,
hf could then translate:

* lambda expressions
* sections
* local function definitions
* comprehensions
* monadic code

The hf translation is purely syntactic.  There is no type-checking
or type-inference, and therefore no attempt to translate type-class
machinery.  Imports and exports between modules are ignored.  These
limitations might be overcome by the use of hf in combination with
other tool.

Uses of hf
----------

As any sequence of one or more declarations is *syntactically* a valid
Haskell source, hf can be applied to *extracts* from of Haskell programs.
For example:

(1) translating function declarations for use in an Flite program;
(2) translating test-data declarations;  
(3) checking that Haskell programs still work with a translated
    version of one more function declarations in place of the originals. 

Closing lexical gaps
--------------------

Some lexical restrictions in F-lite get in the way.  Of the uses noted
above (1) is limited in part by lexical problems, (2) should be
unnecessary, and (3) can be obstructed by lexical issues.

Could we relax F-lite notation to allow at least:

* _ as a pattern
* identifiers including ' and _
* [] (:) and the () (,) (,,) (,,,) ... family as constructors
* (++) and similar as function names

It would also be helpful to allow comments in F-lite.  The comments
currently generated by hf must be addressed and removed by hand.

Download
--------

Source code available from:

  http://www.cs.york.ac.uk/fp/reduceron/hf.tar.gz
