Líně, čistě, funkcionálně

Obsah práce

„Užití funkcionálního programovacího jazyka Haskell k řešení úloh Ústředních kol ČR Soutěže v programování“

Řešené úlohy

Krunimír ‐ jednoduchý programovací jazyk kreslící želví grafiku

Bílá paní ‐ hledání cesty v bludišti s pohyblivými zvědy a možností procházet zdmi.

Krunimír

Jednoduchý programovací jazyk na kreslení želví grafiky.

Želví grafika

Po písku se pohybuje želva a kreslí za sebou stopu. Uživatel želvu ovládá jednoduchým procedurálním programovacím jazykem.

Jazyk

Základní příkazy:

• forward(délka)
• right(úhel), left(úhel)
• pen(tloušťka pera)
• color(červená,zelená,modrá)

Řídící struktury:

• if(podmínka) { ... }
• repeat(počet iterací) { ... }
• define jméno_procedury(param1, param2, ...) {...}
• jméno_procedury(arg1, arg2, ...)
• split { ... }

Jako výrazy (argumenty příkazů a procedur) lze použít:

• číselné literály,
• parametry aktuální procedury,
• binární operace +, -, *, / (dělení celočíselné, priority a asociativity jako v matematice),
• prefixovou negaci (operátor -).

Jediným „typem“ je celé číslo.

Řešení

Program je rozdělen na několik částí:

• Parser přečte program a vytvoří abstraktní syntaktický strom (AST).
• Evaluator vyhodnotí dané AST a vrátí výslednou stopu, kterou želva za sebou zanechá.
• Renderer stopu vykreslí do obrázku.

Jednotlivé části jsou víceméně nezávislé.

Krunimir.Ast

Definice typů představující syntaktický strom (AST)

Typ Stmt reprezentuje příkaz:

data Stmt = 
    ForwardStmt Expr
  | LeftStmt Expr
  | RightStmt Expr
  | PenStmt Expr
  | ColorStmt Expr Expr Expr
  | RepeatStmt Expr [Stmt]
  | IfStmt Expr [Stmt]
  | SplitStmt [Stmt]
  | CallStmt String [Expr]
  deriving Show

Expr představuje výraz:

data Expr =
    LiteralExpr Integer
  | VariableExpr String
  | BinopExpr Op Expr Expr
  | NegateExpr Expr
  deriving Show

data Op = AddOp | SubOp | MulOp | DivOp
  deriving Show

Krunimir.Parser

Exportuje jedinou funkci parse:

parse :: FilePath -> String -> Either ParseError Program

Založen na PEG gramatice:

program      <- space* top-stmt* eof
top-stmt     <- define / stmt

define       <- "define" space+ identifier 
                lparen (identifier (comma identifier)*)? rparen
                lbrace stmt* rbrace

stmt         <- repeat-stmt / if-stmt / split-stmt / proc-stmt
repeat-stmt  <- "repeat" lparen expr rparen lbrace stmt* rbrace
if-stmt      <- "if" space* lparen expr rparen lbrace stmt* rbrace
split-stmt   <- "split" space* lbrace stmt* rbrace
proc-stmt    <- "forward" space* lparen expr rparen
              / "left" space* lparen expr rparen
              / "right" space* lparen expr rparen
              / "pen" space* lparen expr rparen
              / "color" space* lparen expr comma expr comma expr rparen
              / identifier space* lparen (expr (comma expr)*)? rparen

expr         <- add-expr
add-expr     <- mul-expr (add-op space* mul-expr)*
mul-expr     <- neg-expr (mul-op space* neg-expr)*
neg-expr     <- (neg-op space*)? a-expr

add-op       <- "+" / "-"
mul-op       <- "*" / "/"
neg-op       <- "-"

a-expr       <- lit-expr / var-expr / lparen expr rparen
lit-expr     <- integer
var-expr     <- identifier

integer      <- digit+ space*
identifier   <- letter alpha-num space*

lparen       <- "(" space*
rparen       <- ")" space*
lbrace       <- "{" space*
rbrace       <- "}" space*
comma        <- "," space*

digit        <- [0-9]
letter       <- [a-zA-Z]
alpha-num    <- [a-zA-Z0-9]
space        <- [ \t\r\n\v\f]
eof          <- !.

Implementován pomocí monadických parserů z knihovny parsec.

Gramatika PEG:

define       <- "define" space+ identifier
              lparen (identifier (comma identifier)*)? rparen
              lbrace stmt* rbrace

Odpovídající kód Haskellu:

define :: Parser Define
define = do
  string "define" >> skipMany1 space
  name <- identifier
  params <- parens $ identifier `sepBy` comma
  stmts <- braces $ many stmt
  return $ Define name params stmts

Dílčí parsery se skládají do větších celků...

...užitím vysokoúrovňových kombinátorů.

Z výsledků se sestavuje AST.

Krunimir.Evaluator

Exportuje funkci eval, která vyhodnotí program:

eval :: Program -> Trace

Trace představuje stopu želvy:

data Trace
  = EmptyTrace
  | SplitTrace Trace Trace
  | SegmentTrace Segment Trace
  deriving Show

data Segment = Segment Point Point Color Int 
  deriving Show

type Point = (Float,Float)
type Color = (Int,Int,Int)

Vykreslování

• PNG — rastrový formát, použita knihovna GD.
• SVG — vektorový formát, založen na XML.

Gosperova křivka

Hilbertova křivka

Křivka arrowhead

Algoritmus

Použitý algoritmus je založen na prohledávání do šířky.

Implementace

moves :: Bool -> Slice -> Slice -> (Loc,Path) -> [(Loc,Path)]
flood :: Castle -> [Slice] -> STArray s (Int,Loc) (Maybe Path) ->
  [(Loc,Path)] -> ST s (Either Path [(Loc,Path)])
navigate :: Castle -> [Slice] -> Bool -> Maybe [Loc]

Demo