No F*cking Idea

Common answer to everything

'If' the Real Game Changer

| Comments

Recently i was working on a project that is processing campaigns. I asked my self if I can improve it a bit, but not by refactoring existing code but by trying to approach it from a different angle.

Observations

I started making mind notes of things that i understand about system i’m working with. I never had time to think about grammar of this and really get into it. The system has many parts but i thought it can be reproduced in for of language that is easy to parse and nice to work with. I think i might change my current solution into more LISP looking thing just to make it easier to parse.

Observation 1

Each campaign is a sequence of actions that happens one after another. So my initial thought was “this is simple”. We can represent it by list of actions like this

1
 [step] -> [step] -> [step]

But this is true only for simple campaigns and most of them are NOT like this :(

Observation 2

Most of the campaigns are built around key thing. This thing is making decisions! So if i can incorporate “if” i WIN ! Lets have a look

1
2
3
4
                     /> [step]
                   (No)
                    |
  [step] -> [if a < 5] - ( yes ) -> [step]

Yes! This was it, i think this is solution to all problems, ability to represent campaign as a sequence of steps mixed with if statements essentially abstract syntax tree of campaign.

Observation 3

It is not a tree…its more a graph. But AST will make it :] it is a programming language! So this was in my head and i did not had time to work on it… but today i decided to give a try and I made first impression of AST that we would need to have to make it work.

AST

I wrote simple grammar and made a parser of a very simple “ify” language. My language starts like this…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- Grammar
-- x is variable
-- a is artmetic thing aka number
-- n is actual number eg. 1
-- b is boolean
-- opa is arthmetic operator
-- opb is boolean operator
-- opr is comparison operator
-- S is statement
--  a   ::= x | n | - a | a opa a
--  b   ::= true | false | not b | b opb b | a opr a
--  opa ::= + | - | * | /
--  opb ::= and | or
--  opr ::= > | <
--  S   ::= x | x <- a | S1; S2 | ( S ) | if b then S1 else S2

This shows that the grammar is very simple, we can have assigments, operators to test and compare and ofc IF statement ;) this is our key to divnity!

Parser looks kinda ugly because i used parts of the code i wrote before and had i in different projects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
import System.Environment(getArgs)
import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as Token

--  Grammar
-- x is variable
-- a is artmetic thing aka number
-- n is actual number eg. 1
-- b is boolean
-- opa is arthmetic operator
-- opb is boolean operator
-- opr is comparison operator
-- S is statement
--  a   ::= x | n | - a | a opa a
--  b   ::= true | false | not b | b opb b | a opr a
--  opa ::= + | - | * | /
--  opb ::= and | or
--  opr ::= > | <
--  S   ::= x | x <- a | S1; S2 | ( S ) | if b then S1 else S2 

data AExpr = Var String
            | IntConst Integer
            | Neg AExpr
            | ABinary ABinOp AExpr AExpr
              deriving (Show)

data BExpr = BoolConst Bool
            | Not BExpr
            | BBinary BBinOp BExpr BExpr
            | RBinary RBinOp AExpr AExpr
             deriving (Show)

data ABinOp = Add
            | Subtract
            | Multiply
            | Divide
              deriving (Show)

data BBinOp = And | Or deriving (Show)
data RBinOp = Greater | Less deriving (Show)

data Stmt = Seq [Stmt]
           | Assign String AExpr
           | If BExpr Stmt Stmt
           | Ident String
             deriving (Show)

languageDef =
   emptyDef { Token.commentStart    = "/*"
            , Token.commentEnd      = "*/"
            , Token.commentLine     = "#"
            , Token.identStart      = letter
            , Token.identLetter     = alphaNum
            , Token.reservedNames   = [ "if"
                                      , "then"
                                      , "else"
                                      , "true"
                                      , "false"
                                      , "not"
                                      , "and"
                                      , "or"
                                      ]
            , Token.reservedOpNames = ["+", "-", "*", "/", "<-"
                                      , "<", ">", "and", "or", "not"
                                      ]
            }

lexer = Token.makeTokenParser languageDef

identifier = Token.identifier lexer -- parses an identifier
reserved   = Token.reserved   lexer -- parses a reserved name
reservedOp = Token.reservedOp lexer -- parses an operator
parens     = Token.parens     lexer -- parses surrounding parenthesis:
integer    = Token.integer    lexer -- parses an integer
semi       = Token.semi       lexer -- parses a semicolon
whiteSpace = Token.whiteSpace lexer -- parses whitespace

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

statement :: Parser Stmt
statement =   parens statement
           <|> sequenceOfStmt

sequenceOfStmt =
   do list <- (sepBy1 statement' semi)
      return $ if length list == 1 then head list else Seq list

statement' :: Parser Stmt
statement' =   ifStmt
            <|> assignStmt
            <|> identName

ifStmt :: Parser Stmt
ifStmt =
   do reserved "if"
      cond  <- bExpression
      reserved "then"
      stmt1 <- statement
      reserved "else"
      stmt2 <- statement
      return $ If cond stmt1 stmt2


identName :: Parser Stmt
identName =
   do  varName <- identifier
       return $ Ident varName

assignStmt :: Parser Stmt
assignStmt =
   do var  <- identifier
      reservedOp "<-"
      expr <- aExpression
      return $ Assign var expr

aExpression :: Parser AExpr
aExpression = buildExpressionParser aOperators aTerm

bExpression :: Parser BExpr
bExpression = buildExpressionParser bOperators bTerm

aOperators = [ [Prefix (reservedOp "-"   >> return (Neg             ))          ]
              , [Infix  (reservedOp "*"   >> return (ABinary Multiply)) AssocLeft]
              , [Infix  (reservedOp "/"   >> return (ABinary Divide  )) AssocLeft]
              , [Infix  (reservedOp "+"   >> return (ABinary Add     )) AssocLeft]
              , [Infix  (reservedOp "-"   >> return (ABinary Subtract)) AssocLeft]
               ]

bOperators = [ [Prefix (reservedOp "not" >> return (Not             ))          ]
              , [Infix  (reservedOp "and" >> return (BBinary And     )) AssocLeft]
              , [Infix  (reservedOp "or"  >> return (BBinary Or      )) AssocLeft]
              ]

aTerm =  parens aExpression
      <|> liftM Var identifier
      <|> liftM IntConst integer

bTerm =  parens bExpression
      <|> (reserved "true"  >> return (BoolConst True ))
      <|> (reserved "false" >> return (BoolConst False))
      <|> rExpression

rExpression =
   do a1 <- aExpression
      op <- relation
      a2 <- aExpression
      return $ RBinary op a1 a2

relation =   (reservedOp ">" >> return Greater)
          <|> (reservedOp "<" >> return Less)


parseString :: String -> Stmt
parseString str =
   case parse whileParser "" str of
     Left e  -> error $ show e
     Right r -> r

parseFile :: String -> IO Stmt
parseFile file =
   do program  <- readFile file
      case parse whileParser "" program of
        Left e  -> print e >> fail "parse error"
        Right r -> return r

main = do
  args <- getArgs
  ast <- parseFile(head args)
  putStrLn $ show ast

But it works… we can parse. Now i have to make it more production ready and less unstable ;]. This is first attempt at this idea. I need to expand grammar and think about it more then just few minutes. but i think it is a good start. Next step for me is to make better grammar and parser and move to building interpreter of this mini language.

Comments