A blag containing my current adventures in logic, haskell and agents.

Saturday, 22 August 2009

Parsing L-Systems with the uu-parsinglib

So I subscribed to the Utrecht Summer School program Applied Functional Programming a few months ago and got accepted. This week the course finally started. I'm really enjoying the nice lectures, new people I meet and the quick pace of new things to learn.
One of the parts in this course is to do a project with 3 to 5 people with different levels in Haskell. But of course almost everyone is very motivated so the different levels work quite well :). Anyway, the project we chose after some discussion was: Write an L-systems generator and/or visualizer.

So first a small introduction to L-systems. Wikipedia has a really really great page about it here, and it also contains a link to a free book containing even more information.

From Wikipedia: "An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms.[1] L-systems can also be used to generate self-similar fractals such as iterated function systems. L-systems were introduced and developed in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer (1925–1989)."

So quite fitting to do at a summer school in Utrecht :).

If you don't know L-Systems (like I did) just take a short look at the wiki page. They're quite intuitive if you're familiar with something like BNF or grammars in general.

Anyway, we split the project in 4 parts. Namely a GUI for visualizing the L-Systems, a GUI for inputting the generating gramamars and following from that are a parser that can parse the inputted grammar, and an algorithm generating the strings of symbols from an L-System.

The part I started on was the parser. I already knew some Parsec (2) before coming to the summer school, but I thought it would be more interesting and fitting to use another parser combinator library, namely the newest version from the University of Utrecht themselves. So I started learning the uu-parsinglib. For the package and tutorial see the hackage page here.

Anyway before I completely introduce my parser I'll first talk about the datatype we made up. I thought it was a good idea to settle for the most simple kind of L-Systems as a first implementation. And secondly to start with a very basic kind of alphabet to use for drawing the L-Systems. The alphabet will contain symbols directing the drawing, (F means to go forward and draw, f means to go forward without drawing, - means to turn right and + to turn left), the other symbols would only be used to do nothing or to be used in the generating part of the L-Systems.
(The drawing part is called Turtle Graphics and is very similar to the Logo programming language.)

Here is an EBNF I made that might clear up the problem a bit. I make no difference between variables or constants because you can handle that very easily in the generating part.

VariableOrConstant := letter | '+' | '-'
StartSymbol := VariableOrConstant+
Rule := VariableOrConstant "->" VariableOrConstant*
Rules := Rule (('\n' | ',') Rule)*

So we decided rules can generate a variable number of new symbols (possibly none). Spaces are allow everywhere except in the arrow. And we decided it's very easy to use the generation on a starting symbols rather than just one symbol.

So the logical datatype was this:
module DataType where

-- we read in the angle and the movement step size
-- RightAngle = '-', LeftAngle = '+', Forward = 'F', ForwardSkip = 'f', Variable Char = Char
data TurtleMove = RightAngle | LeftAngle | Forward | ForwardSkip | Variable Char
deriving (Show, Eq, Ord)

type Rule = (TurtleMove, [TurtleMove])
type StartSymbol = [TurtleMove]

The variables are just non movement symbols used in the grammar. The types are some shorthands that will be used in the parser.

The parsers I wrote are most importantly for parsing the rules.
I wrote increasingly larger parser building blocks with hopefully enough documentation so I will just give the full parser code. If anyone appreciates some explanation beside the exisisting tutorial you're welcome to ask me.
To get the example working, before compiling do a cabal update and cabal install uu-parsinglib. (Or install it manually.) The most interesting method is probably runPRules which will take a string and produce a set of rules. Note the cool error correcting and online parsing from the uu-parsinglib if you enter too many symbols or incorrect symbols by using test.

module LSystemParser where
import Text.ParserCombinators.UU.Parsing
import Text.ParserCombinators.UU.Examples
import DataType

-- parse one or more
pMany p = (:) <$> p <*> pMany p <|> pReturn []

-- turn a parsed character into a TurtleMove
-- RightAngle = '-', LeftAngle = '+', Forward = 'F', ForwardSkip = 'f', Variable Char = Char
pLetterToDatatype :: Char -> TurtleMove
pLetterToDatatype l = case l of
'-' -> RightAngle
'+' -> LeftAngle
'F' -> Forward
'f' -> ForwardSkip
other -> Variable other

-- parse a number of spaces
spaces :: P_m (Str Char) [Char]
spaces = pList $ pSym ' '

-- parse a variable or turtle graphic primitive
pLetter' :: P_m (Str Char) Char
pLetter' = pLetter <|> pSym '-' <|> pSym '+'

-- parse a letter that is possibly surrounded by spaces
pSimple :: P_m (Str Char) Char
pSimple = (\ _ x _ -> x) <$> spaces <*> pLetter' <*> spaces

-- parse a letter and turn it into a TurtleMove
pVariable :: P_m (Str Char) TurtleMove
pVariable = pLetterToDatatype <$> pSimple

-- parse the right hand side of a rule
pWord :: P_m (Str Char) [TurtleMove]
pWord = map pLetterToDatatype <$> pMany pSimple

-- parse a list of variables separated by commas
pVariables :: P_m (Str Char) [TurtleMove]
pVariables = map pLetterToDatatype <$> pListSep (pSym ',') pSimple

-- *> doesn't work from R to R
-- parse an arrow and the right hand side of a rule
pArrow :: P_m (Str Char) [TurtleMove]
pArrow = pSym '-' *> (pSym '>' *> pWord)

-- parse one production rule
pRule :: P_m (Str Char) Rule
pRule = (\ x y -> (x,y)) <$> pVariable <*> pArrow

-- parse a sequence of production rules separated by commas or newlines
pRules :: P_m (Str Char) [Rule]
pRules = pListSep (pSym '\n' <|> pSym ',') pRule

-- parse the rules and take out the results
runPRules :: String -> [Rule]
runPRules = fst . test pRules

main2 = test pRules $ "x -> blaF+-blabla\n F->SKF"

Well that's it for today :).

1 comment:

  1. Hello,

    Thanks for the post.

    You can actually simplify some of your functions, e.g.

    pSimple :: P_m (Str Char) Char
    pSimple = spaces *> pLetter' <* spaces

    pRule :: P_m (Str Char) Rule
    pRule = (,) <$> pVariable <*> pArrow

    Hope this helps other people reading your blog.