Conway's Life - Gunstar

Life Pattern - Gunstar

In the last post, we built a simulator for Conway’s Life in Haskell using repa and OpenGL. The initial life pattern in that implementation was hard coded. In this post, I’ll build a framework for parsing patterns from files.

Broadly, a pattern parser needs to read a set of live cell positions from a file and make those available for the grid initialization. It should also support reading some metadata that is common between different file formats. The common file formats are documented on LifeWiki. They all have similar metadata that we can easily support: pattern name, comments or description, and a pattern offset position. The file formats can also define alternate rules for how the cells evolve, but this version won’t support any rules other than the standard Life.

The grid initializer needs a function that determines if each position in the grid is alive or dead, given a pattern. The type of that function should look something like this:

isCellLive :: LifePattern -> (Int, Int) -> Bool

I chose to use a Set that holds the positions of the live cells, so the implementation of this function is just a thin wrapper around Set.member that takes the pattern offset into account. The LifePattern type holds the set and other metadata read from the file. Look at LifePattern.hs for the full definition.

The next abstraction we can make is converting a file into a LifePattern. All of the formats, except small object, only have one pattern per file, and each format can be distinguished by the file extension. LifeWiki doesn’t have many small object format files, so we can ignore those for now and assume one pattern per file. The client of the parsing framework shouldn’t have to care about file formats, so the API should expose one function which accepts a file path and returns either a pattern or an error. The framework will detect the format automatically and apply the correct parser. Let’s break that down into a working design.

Given a file name, we need to check if the extension matches each parser. If one of the parsers matches, run it on the file and return the result. The result of applying this process to each parser is encoded in the type PatternParseResult.

data PatternParseResult = SuccessfulParse LifePattern
                        | ParseError String P.ParseError
                        | UnknownFormat String
                        | FileError IOException
                        | IncorrectFormat
 

P.ParseError is from Text.Parsec, the parsing library I chose to use.

With a function FilePath -> IO PatternParseResult for each parser, we can easily try each of them and select the first one that evaluates to something other than IncorrectFormat. This is exactly the implementation of the top level file parsing function.

parseFile :: FilePath -> IO PatternParseResult
parseFile fname = do
  attempts <- mapM tryParser parsers
  return $ foldr selectAttempt (UnknownFormat fname) attempts

    where

      -- | Try to apply the parser. Catch any IOException
      -- and convert it to a FileError.
      tryParser :: (FilePath -> IO PatternParseResult)
                -> IO PatternParseResult
      tryParser parser = parser fname `catch` (return . FileError)

      -- | Select the first parser that was run.
      selectAttempt IncorrectFormat next = next
      selectAttempt result _ = result
 

UnknownFormat is the end value in the foldr call, which indicates that no parser could recognize the file.

The function tryParser is mapped over parsers, which is a list generated from each parser along with its name and file extension. Those are passed to a wrapper function that checks the extension, opens the file, runs the parser, and then prints any warnings generated by the parser.

makeParser :: (String, String, PatternParser T.Text IO LifePattern)
           -> FilePath
           -> IO PatternParseResult
makeParser (extension, name, parser) fname =
    if (takeExtension fname) == extension
    then do
      contents <- T.readFile fname
      result <- parsePatternFile parser fname contents
      either err success result

    else return IncorrectFormat

    where
      err = return . ParseError name

      success (pattern, warnings) = do
        when (not . null $ warnings) $
             putStrLn . unlines . map ("Warning: " ++) $ warnings
        return $ SuccessfulParse pattern
 

T.readFile is from the Text library, which is generally more efficient than the String version. The function parsePatternFile is a thin wrapper around Parsec’s runPT which hides how the parsers report warnings.

type PatternParser s m = ParsecT s [String] m

patternWarning :: Stream s m Char => String -> PatternParser s m ()
patternWarning msg = modifyState (++ [msg])

parsePatternFile :: Stream s m Char => PatternParser s m LifePattern
                 -> FilePath -> s
                 -> m (Either ParseError (LifePattern, [String]))
parsePatternFile parser fname contents =
    runPT parser' [] fname contents

    where
      parser' = (,) <$> parser <*> getState
 

That’s enough for this post. The next installment will look at the parsers for the RLE and plain text formats. Remember, all the code for this post is available on Bitbucket. Fork it, show me how awesome you can make this.