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