[Haskell-cafe] New Layout Rule

[John Meacham]

Motivated by some recent discussion, I thought I would explore the
possibilty of formalizing the haskell layout rule without the dreaded
parse-error clause, as in, one that can be completly handled by the
lexer.

motivated by that I have written a little program that takes a haskell
file with layout on stdin and spits out one without layout on stdout.

it can be gotten here:
darcs get http://repetae.net/repos/getlaid/

the code is designed to make the layout algorithm completly transparent,
so that we might experiment with it. The function layout in 'Layout.hs'
is the single and complete layout algorithm and the only thing that need
be modified by experimentors.

I have come up with a simple improvement to the algorithm given in the
paper that seems to catch a very large number of layouts. basically,
whenever it comes across something that must come in matched pairs (, ), case
of, if then. it pushes a special context onto the stack, when it comes
across the closing token, it pops every layout context down to the
special context.

there is a special case for "in" that causes it to pop only up to the
last context created with a "let", but not further.

here is the complete algorithm (with my modification, sans the
parse-error rule):
 
> data Token = Token String | TokenVLCurly String !Int | TokenNL !Int deriving(Show)
> 
> data Context = NoLayout | Layout String !Int
>
> -- the string on 'Layout' and 'TokenVLCurly' is the token that
> -- created the layout, always one of "where", "let", "do", or "of"
> 
> layout :: [Token] -> [Context] -> [Token]
> layout (TokenNL n:rs) (Layout h n':ls)
>     | n == n' = semi:layout rs (Layout h n':ls)
>     | n > n' = layout rs (Layout h n':ls)
>     | n < n' = rbrace:layout (TokenNL n:rs) ls
> layout (TokenNL _:rs) ls = layout rs ls
> layout (TokenVLCurly h n:rs) (Layout h' n':ls)
>     | n >= n' = lbrace:layout rs (Layout h n:Layout h' n':ls)
>     | otherwise = error "inner layout can't be shorter than outer one"
> layout (TokenVLCurly h n:rs) ls = lbrace:layout rs (Layout h n:ls)
> layout (t@(Token s):rs) ls | s `elem` fsts layoutBrackets = t:layout rs (NoLayout:ls)
> layout (t@(Token s):rs) ls | s `elem` snds layoutBrackets = case ls of
>     Layout _ _:ls -> rbrace:layout (t:rs) ls
>     NoLayout:ls -> t:layout rs ls
>     [] -> error $ "unexpected " ++ show s
> layout (t@(Token "in"):rs) ls = case ls of
>     Layout "let" n:ls -> rbrace:t:layout rs ls
>     Layout _ _:ls -> rbrace:layout (t:rs) ls
>     ls -> t:layout rs ls
> layout (t:rs) ls = t:layout rs ls
> layout [] (Layout _ n:ls) = rbrace:layout [] ls
> layout [] [] = []
>
> layoutBrackets = [ ("case","of"), ("if","then"), 
>                    ("(",")"), ("[","]"), ("{","}") ]

now. there are a few cases it doesn't catch. the hanging case at the end
of a guard for instance, I believe this can be solved easily by treating 

'|' and '='  as opening and closing pairs in lets and wheres
'|' and '->' as opening and closing pairs in case bodies.

it is easy to see which one you are in by looking at the context stack.


commas are trickier and are the only other case I think we need to
consider.

I welcome people to experiment and send patches or brainstorm ideas, I
have what I believe is a full solution percolating in my head, but am
unhappy with it, I am going to sleep on it and see if it crystalizes by
morning. In the meantime, perhaps someone can come up with something
more elegant for dealing with the remaining cases. or at least find some
real programs that this code breaks down on!

(bug fixes for the lexer and everything are very much welcome. it will
probably choke on some ghc extensions that would be trivial to add to
the alex grammar)

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈