Our last version of this project was a bit … underwhelming. The Lambda Calculus is Turing-equivalent, but it’s hard to imagine expressing much in the way of interesting computations with what we have right now. In fact, we can’t, since our calculator is missing the most important tool of the Lambda Calculus: functions.

In this section, we’ll look at generating first-order functions. It’s easier to understand how functions in LLVM work if we aren’t dealing with the machinery for closures. As always, this post is literate Haskell. You’ll need the parser from the first section to compile it.

Our finished product this time will compile our code into LLVM bytecode, then disassemble it and print the corresponding LLVM assembly. It wouldn’t be much of a stretch to run it as we did last time, but it also wouldn’t really explain much either. We’re still at a point where reading the generated assembly can convince us of correct results.

> module Main where

> import Parser

As before, we’re going to need a bunch of imports.

> import Control.Monad.State(forever)
> import Data.Int
> import Data.List
> import LLVM.Core
> import LLVM.Util.File(writeCodeGenModule)

> import System.IO
> import System.Cmd

Our environment from the calculator needs to be extended to keep track of functions. In theory we could look up and store the name of newly generated functions here, but it’s easier to store the functions directly.

> data Env = Env {
>       vars :: [(String, Value Int32)]
>     , funs :: [(String, Function (Int32 -> IO Int32))]
>     }

It’s nice to be able to print the variables we already have, so we’ll make Env an instance of Show to help with that.

> instance Show Env where
>     show e = "vars: " ++ (m $ vars e) ++ ", " ++
>              "funs: " ++ (m $ funs e) where
>                   m l = show $ names l

At several times we’ll need to separate the names from the values in our environment. In fact we’ve already needed to once.

> names = map fst

Here’s our familiar AST -> LLVM translation of arithmetic operations.

> getOpt Add = add
> getOpt Mul = mul

Detecting Closures

Since we’re restricting ourselves to first-order functions, we need to take some steps to detect (and fail on) higher-order functions. In some ways we can continue to be bad compiler writers and rely on the user to follow arcane and senseless rules. This is exactly the technique I will be using to prevent functions as arguments and functions as return values.

However, there’s one other feature we need to prevent, and that’s closures. Obviously we could expect the user to avoid those as well, but in this case the code we need to detect them now will be convenient later. Since this project is all about doing things that are convenient for us as the compiler writers (enjoy it now, this almost never happens in real life), we’ll go ahead and implement that check.

So, what does a closure look like in an abstract syntax tree? The answer is pretty simple: a closures references variables from its surrounding environment, so build up a list of all the name references in a piece of the AST and eliminate the ones that are declared in that piece. What is left is the variables that are being closed over.

Here’s an example of a perfectly valid first-order function, the identity function:

\x. x

There’s only one variable involved, x, and we can easily see that it is introduced in the lambda terms, so the identity function has no free variables.

In this example, the function bound to g is a closure:

let f = 5; g = \x. x + f in g 2

That’s easy to see when we pull it out of its context:

\x. x + f

We can still identify where x “comes from”, but now there’s nothing to provide the definition of f. In this situation f is called a free variable, and it’s the presence of these that differentiates closures from more ordinary functions.

Now that we have a handle on what free variables are, on to detecting them. We’ll need a function that takes an expression and generates a list of the free variables in it.

> fv              :: Exp -> [Var]

Perhaps the simplest way to structure this is to go through each constructor for our AST and decide how to find free variables for that constructor. Vars are simple, since they’re just a variable name with nothing to bind them to a value, they’re automatically free variables.

> fv (EVar v)      = [v]

Constants have no variables, so there’s no free variables to be found here.

> fv (Con _)       = []

Function applications have two places they could contain free variables. The obvious one is the expression the function is being applied to, but the slightly-less-obvious case inovlves the function itself. Remember, we eventually will have functions that can return functions, so something like (f 2) 2 will eventually be valid, and leaves plenty of room to start closing over variables.

This isn’t tough to account for though, just have to look up the free variables in both, then filter the list to eliminate duplicates. Luckily, nub from Data.List has already been written to take care of just this issue.

> fv (App f x)     = nub (fv f ++ fv x)

Lambda terms are one of our two constructs that are capable of binding a name. We need to make sure we don’t accidentally declare the function argument as a free variable, since we know exactly what it’s value is. The function (\\) scans a list on the left to remove any items from the list on the right, so we can just look up the free variables in our lambda terms expression then pluck out the one that doesn’t belong.

> fv (Lam v e)     = fv e \\ [v]

Arithmetic operations can close over variables in their left or right terms. Again, we should clean up the list so any given free variable is only present once.

> fv (EOp _ l r)   = nub (fv l ++ fv r)

Let bindings are our other construct that can bind a name. The steps needed here are about the same as those for lambda expressions.

> fv (Let v eq xp) = nub $ fv eq ++ ([v] \\ fv xp)

Generating Functions

Now that we can identify free variables, we’re pretty much ready to start compiling functions. This has to happen within the CodeGenModule monad, which is fine now but will complicate our closure code a bit in the next section. We’ll rewrite compileFun from the calculator to support the kinds of functions we’re defining. We’ll have to change the type signature to match the Int -> Int functions our lambda calculus uses.

While creating a function, we’re inside of the CodeGenFunction monad, and thus can compile its body using the code from our calculator (remember, we’re trusting the users not to write any “interesting” functions).

The only tricky part left is distinguishing closures from non-closures, but that’s pretty simple, just look up the free variables of the function. If there are any we have a closure and throw an error, otherwise we can compile it.

The only interesting aspect of compiling the body of our function is that we have to add the argument to our environment while compiling the body. Since the code for this looks kind of ugly, we’ll wrap it in a slightly prettier function.

> addv :: Var -> Value Int32 -> Env -> Env
> addv v x e = e {vars = ((v::String),x):vars e}

Finally, we’re ready to compile functions. Since the only piece of our AST that can product a function is a lambda term, that’s the only piece we can meaningfully compile.

> compileFun :: Env -> Exp -> CodeGenModule (Function (Int32 -> IO Int32))
> compileFun env f@(Lam v e) = case (fv f) of
>                                []        ->  createFunction ExternalLinkage $ \x -> do
>                                                        t <- compileExp (addv v x env) e
>                                                        ret t
>                                otherwise -> error "No closures yet!"
> compileFun _ _ = error "undefined"

Due to the restrictions we have in place, we’ll expect to see a set of nested lets that introduce functions, and a final body that uses them. We can special case the compilation of this to ensure our eventual body is in a special function.

First, we’ll need a convenience function to introduce a function to the environment. This is almost the same as addv, with an obvious change to the record being updated.

> addf :: Var -> (Function (Int32 -> IO Int32)) -> Env -> Env
> addf f x e = e {funs = ((f::String),x):funs e}

When compiling lets, we’re going to start out only dealing with lets that bind a lambda term to a name. The process is relatively simple: compile the function, store it in the environment under the name it was bound do, and compile the let body with that environment.

> compileLet :: Env -> Exp -> CodeGenModule Env
> compileLet env l@(Let v fun@(Lam x exp) body) =
>                         do fn <- compileFun env fun
>                            letBody v (addf v fn env) body
> compileLet _ _ = error "undefined"

While we’re compiling the let body, we need so way to decide where to “stop” and emit our final function. We can pile on one more restriction to help with this: let bindings that introduce functions must come before those that bind non-function values. That way once we see a let which doesn’t introduce a function, we can emit our main function and compile as normal in that.

Note that we don’t really need this restriction. Since functions aren’t being allowed to close over their environment, we could pull all of the non-function bindings past the function bindings without changing the meaning of the program. That would be a good exercise to try.

To decide when to stop making more functions, we need to distinguish lets that bind a function from those that bind a value. It doesn’t get much simpler than this:

> isFunLet :: Exp -> Bool
> isFunLet (Let _ (Lam _ _) _) = True
> isFunLet _                   = False

The body of each let can meet one of two criteria. It either contains another let that defines a function, in which case we need to keep compiling functions, or it doesn’t, in which case we’ve hit the “body” of our main function and can compile that. For convenience we’re adding an unused parameter to the main function so its type matches that of the others and we can return it with the entire environment.

> letBody :: Var -> Env -> Exp -> CodeGenModule Env
> letBody v env expr | isFunLet expr = do compileLet env expr
>                    | otherwise     =
>                        do f <- createNamedFunction ExternalLinkage "main" $ \n ->
>                                                      do t <- compileExp env expr; ret t
>                           return $ addf v f env
>                                                                     

Compilation, extended

Since we now have functions and variables, let’s add a bit more useful error handling to make life simpler.

> envError :: String -> String -> Env -> a
> envError "function" n e = error $ "could not find function: " ++ n ++ ", have: " ++ (show $ names $ funs e)
> envError "variable" n e = error $ "could not find variable: " ++ n ++ ", have: " ++ (show $ names $ vars e)
> envError t _ _ = error $ "unrecognized error type: " ++ t

The code to compile expressions is largely unchanged, with the exception that we’re now supporting function application.

> compileExp :: Env -> Exp -> CodeGenFunction r (Value Int32)
> compileExp _ (Con x)       = return $ valueOf ((fromIntegral x)::Int32)

> compileExp e (EOp o l r)   = do
>                              l' <- compileExp e l
>                              r' <- compileExp e r
>                              getOpt o l' r'

> compileExp e (EVar v)      = case lookup v $ vars e of
>                             Just a  -> return a
>                             Nothing -> envError "variable" v e

> compileExp env@(Env e f) (Let v val body) = do
>                  v' <- compileExp env val
>                  let e' = Env (((v::String),v'):e) f in
>                           compileExp e' body

Due to the restrictions we have in place, we don’t have to worry about expressions that result in a function. Our code just has to handle variables bound to a give function. It does this by looking up the function in our environment (obviously failing if it isn’t found), then compiling the argument into a register and calling the function with that register as its argument.

> compileExp e (App (EVar v) e2)  = case lookup v $ funs e of
>                                     Just a -> do
>                                       t1 <- compileExp e e2
>                                       call a t1
>                                     Nothing -> envError "function" v e
> compileExp _ _            = error "undefined"

To start off our compilation, we’ll need an empty environment. Here it is.

> emptyEnv = Env [] []

Our main function is unchanged from last time.

> main =
>     forever $ 
>     do putStr "> "
>        hFlush stdout -- have to flush for proper output ordering
>        s <- getLine
>        go s

Now, go has been rewritten to compile our code into llvm bytecode, use a shell command to disassemble it, then read the disassembled output and print it to the screen.

> go s =
>   case runwith letexpr id s of
>   Left err  -> putStrLn $ show err
>   Right exp -> do writeCodeGenModule "FirstClass.bc" $ compileLet emptyEnv exp
>                   rawSystem "llvm-dis" ["-f", "FirstClass.bc"]
>                   f <- readFile "FirstClass.ll"
>                   putStr f

No comments

Rather than dive entirely into working on a compiler, I’m going to approach the task in pieces. This post will go over how the Haskell LLVM bindings work while creating support for computing algebraic expressions. The next post will cover first-order functions, with closures to follow.

This calculator will be a standalone program that takes in algebraic equations on the command line, compiles them into LLVM bytecode, runs that code and prints the result. At the time of this writing, the LLVM bindings cannot load functions generated at runtime in ghci, so if you’re following along you’ll have to statically compile the result.

As before, this post is literate Haskell. It needs the LLVM bindings installed and set up correctly, and uses the parser from the last post. Please note that I needed to make a couple of changes to the parser module, so if you downloaded a copy before this post existed, you should grab an update.

> module Main where

> import Parser

> import Control.Monad.State
> import Control.Monad(join)

> import Data.Int

> import LLVM.Core
> import LLVM.ExecutionEngine
> import LLVM.Util.Arithmetic
> import LLVM.Util.File(writeCodeGenModule)

> import System.IO

The Haskell LLVM bindings can be split into two levels. There’s a low level interface that doesn’t give much more than direct bindings to the C++ api. This is great as a fallback, but can be rather tedious to work with.

The high level api provides translation between Haskell and LLVM values, and heavy-duty abstractions for generating LLVM bytecode. Most of this abstraction is provided by a CodeGen monad, which keeps track of basic blocks and uses the syntactic sugar of do blocks to make your code look significantly like assembly psuedocode.

Simplifying Assumptions

In order to get very far in compiling arithmetic expressions in a reasonable amount of time, we’ll need to make a few simplifying assumptions. Some are obvious, like that we won’t be dealing with functions at this point and can unhelpfully error out when someone tries to use one. Others are slightly more subtle.

In reality, after we’ve parsed the input, we should really be doing some checks on the output to ensure it is valid. This includes things like ensuring someone doesn’t try to add together a number and a lambda expression. If you look back at the parser, you’ll notice it was carefully structured to avoid this specific problem.

An issue we aren’t going to deal with is name conflicts. A real compiler would add an identifier renaming pass that ensures all name references are unique. Since this is a budget compiler, we’re going to assume the program was careful and did that for us. It isn’t exactly hard to do this, just a bit tedious, and might be worth experimenting with as an exercise.

It also makes life a lot easier if we require that names be defined before they are used. Haskell allows code like this:

let f = g + 5
    g = 10 in
    ...

In order to compile f, we need to know what g is. The obvious answer is to come up with a way to wait on compiling f until we’ve either compiled g or compiled everything there is to compile and not seen g, but that is a lot of work. This also might be something worth doing for practice though.

Another simplifying assumption that we’re making is assuming our programmers are only interested in creating functions that add or multiply 32-bit integer values. Partly this is done to avoid work, like supporting floating point values, that I feel isn’t quite interesting enough to be worth the effort for this kind of toy project. The 32-bit part is just plain cheating so we can easily convert from a Haskell Int32 to an LLVM integer on any kind of system.

Compilation Miscellany

In order to compile our programs, we need an environment that tracks the register a value was compiled into. This can be done with a simple association list of identifier names to register values, which the prelude handily defines a few functions to work with.

The type: Value Int32 corresponds to an llvm register storing a 32-bit integer. This environment would obviously need some adjusting if we wanted to support other kinds of values. The LLVM bindings approach this through limiting Value a based on appropriate type classes and the existential types extension. That would probably be the best bet to proceed from here.

> type Env = [(String, Value Int32)]

The LLVM bindings provide add and mul instructions that take two registers (or immediate values) and produce the appropriate result. We’ll need a function to translate the operations from our AST into the equivalent LLVM functions.

> getOpt Add = add
> getOpt Mul = mul

Compiling Expressions

Our entire compilation step can be expressed with a single function. Since we will want to reference variables bound in a containing let, that function will obviously need to accept the environment as an argument. The function will walk the AST, compiling results as it goes and trusting the CodeGen monad to do all of the bookkeeping.

The result of our expression compilation will be a register, bound up in the CodeGen monad. This is about the area where my understanding of Haskell gets fuzzy, so I can’t fully explain the reasoning behind the return value of this function.

> compileExp :: Env -> Exp -> CodeGenFunction r (Value Int32)

Compiling a constant is simple, just convert the AST’s string (we already know it’s an integer, thanks to the parser) to a Haskell Int32, then pass that to valueOf for conversion to an LLVM Int32, and bind the whole thing up in our monad.

> compileExp _ (Con x)       = return $ valueOf ((fromIntegral x)::Int32)

Likewise, compiling a variable is as simple as looking up the register it was previously compiled into based on the variable name. Since we’re not trying to be useful compiler writers, we’ll just give an error and exit if we can’t find the variable name.

> compileExp e (EVar v)      = case lookup v e of
>                             Just e  -> return e
>                             Nothing -> error $ "could not find variable: " ++ v

Compiling an arithmetic expression is a simple matter of compiling each side, then performing the arithmetic on the result.

> compileExp e (EOp o l r)   = do
>                              l' <- compileExp e l
>                              r' <- compileExp e r
>                              (getOpt o) l' r'

Let bindings are the only way to introduce variable names into the environment. The body of the let needs the variable to be bound to the value. For now we’re going to assume the value is not a lambda expression, in which case we can simply compute it into a register and associate that register with the variable name when compiling the body of the let.

> compileExp e (Let v val body) = do
>                  v' <- compileExp e val
>                  let e' = ((v::String),v'):e in
>                           compileExp e' body

Just to be clear, we’ll make sure that everything else (function application and lambda expressions) gives an error.

> compileExp _ _            = error "none of that, I'm still cheating"

Our “calculator” portion is formed by wrapping the expression in an LLVM function that computes it and returns the result. Here’s a simple function that does just that.

Since this is the first time we’ve actually made a function, it warrants going over what’s happening here. The createFunction function does pretty much what you would expect. It needs an argument detailing the link-time visibility of the function. For our specific purposes the parameter is irrelevant, but it’s there if you need it.

Notice that we aren’t providing a name for the function. Even according to our bindings we’re still working with anonymous functions! Of course, if you decompile the resulting bytecode you’ll see that LLVM comes up with names like @_fun1.

Our function takes no arguments, and simply compiles the expression, stores the result into a register, and returns it. Couldn’t be easier than that. The Function type represents this. If our function had taken a single integer argument its type would look like Function (Int32 -> IO Int32). Since we’re calling out to bindings that do all kinds of IO work, it’s reasonable to expect the IO monad to show up. With this type of declaration it’s impossible to call the function we’re making without being in the IO monad or committing irredeemable sins. We’ll try to keep our functional hearts pure, at least for the rest of this module.

> compileFun :: Exp -> CodeGenModule (Function (IO Int32))
> compileFun exp = createFunction ExternalLinkage $ do
>                    t <- compileExp [] exp
>                    ret t

Now we can wrap up the process of compiling our function and binding to it in Haskell. The LLVM bindings provide simpleFunction for just this task.

> compileToFun :: Exp -> IO Int32
> compileToFun exp = join $ simpleFunction $ compileFun exp

Our main function will simply loop forever, pulling in user input and running it through something to respond to it.

> main =
>     forever $ 
>     do putStr "> "
>        hFlush stdout -- have to flush for proper output ordering
>        s <- getLine
>        go s

Here’s the heart of our calculator. It attempts to parse the user’s input (generating an error message on failure), then compiles it and runs the containing function to get the result. Finally it writes the bytecode out to Calc.bc.

> go s =
>   case runwith letexpr id s of
>   Left err  -> putStrLn $ show err
>   Right exp -> do let fun = compileToFun exp in
>                             do r <- fun
>                                putStrLn $ "result: " ++ (show r)
>                                writeCodeGenModule "Calc.bc" $ compileFun exp
>                                                          

This file can be disassembled with llvm-dis, which generates somewhat surprising output. No matter how complicated your let bindings or arithmetic expression, you’ll always get a function that simply returns the pre-computed result. LLVM has an extensive number of optimization passes, and a good selection of them are enabled for you by default in the Haskell bindings. One of these is the constant propogation pass, which looks for arithmetic that can be done at compile time and eliminates the intermediary computation.

I’ll walk through an example, to show how the magic works. We’ll start with this expression:

let f = 5; g = 2 in 4 * f + (20 + 2)

It parses into:

Let "f" (Con 5)
  (Let "g" (Con 2)
    (EOp Add
      (EOp Mul (Con 4) (EVar "f"))
      (EOp Add (Con 20) (Con 2))))

A (very) naive “hand-compilation” would give us something like the following:

define internal i32 @_fun1() {
_L1:
        %1 = $5
        %2 = $2
        %3 = mul $4 %1
        %4 = add $20 %2
        %5 = add %3 %4
        ret i32 %5
}

First off, we obviously don’t need the %1 and %2 registers, all they do is hold constants. It’s simple to push their values into the relevant expressions. This act of recognizing a constant and using it to replace the register it was being stored in is constant propagation. Once that push has happened, the %1 and %2 registers become unused, and can be dropped.

define internal i32 @_fun1() {
_L1:
        %3 = mul $4 $5
        %4 = add $20 $2
        %5 = add %3 %4
        ret i32 %5
}

Now we can look at the %3 register, which just multiplies two constants. We know how to do that too, and it’s no stretch to handle the addition on %4. This optimization, called constant folding, is closely related to constant propagation.

define internal i32 @_fun1() {
_L1:
        %3 = $20
        %4 = $22
        %5 = add %3 %4
        ret i32 %5
}

But now we’ve got more registers that are nothing but labels for constants, you know what to do.

define internal i32 @_fun1() {
_L1:
        %5 = add $20 $22
        ret i32 %5
}

Now we’re another constant fold & propagate step away from the exact output LLVM gives us, which is:

define internal i32 @_fun1() {
_L1:
        ret i32 $42
}

Tune in next time for first-order functions.

No comments

In this series of posts, I’m going to walk through building a compiler for a simple Lambda Calculus to llvm. I’ll try to keep things to the point that nothing more than a general understanding of Haskell, Parsec, and the basic concepts of LLVM are required.

If you’d like to follow along, this post is a Literate Haskell file. That is unless Wordpress broke it, in which case let me know and I’ll fix it.

This first post concentrates on the parser. We’re going to target the abstract syntax found below. It’s a relatively simple untyped Lambda Calculus, with the conceit of adding let bindings to make life a bit more interesting. Note that we’re simplifying things considerably by limiting our types and arithmetic operations to stay within the realm of positive integers.

For educational value, I will not be using Text.ParserCombinators.Parsec.Language. Please note that, if you’re trying to implement a “real” language parser, that’s a much more sane option.

Let’s get started. We’re going to need to define a module for htis, and we obviously need some parsec libraries as well as the AST we’re translating to, so let’s take care of that.

> module Parser(letexpr, runwith, runIO,
>               Exp(EVar, Let, App, Lam, EOp, Con),
>               Op(Add, Mul),
>               Var) where

> import Data.List

> import Text.ParserCombinators.Parsec
> import Text.ParserCombinators.Parsec.Error(messageString, errorMessages)

Here’s the AST I will be using:

> data Exp  = EVar Var
>           | Let Var Exp Exp
>           | App Exp Exp
>           | Lam Var Exp
>           | EOp Op Exp Exp
>           | Con Int
>             deriving Show

> type Var  = String

> data Op = Add
>         | Mul
>           deriving Show

I’m going to start out by defining a few useful tools. It’s entirely likely that these already exist in Parsec, and furthermore that my implementations are inferior, so please let me know if you spot a problem.

Expressing “this should be between spaces” is a pain, so we’ll make something to handle that. But, we don’t want “expected space or…” in all of our errors, so this isn’t as intuitive as it would seem:

> spaced x = between spaces' spaces' x where
>     spaces' = spaces <?> ""

We’ll need a similar construct for things in parentheses, and while we’re at it a “this string should be spaced out” construct wouldn’t hurt either:

> symbol s = spaced $ string s

> parens = between (symbol "(") (symbol ")")

Here’s a few example expressions to “sketch out” what the language should look like:

The identity function:

\x. x

A sample let expression:

let id = \x. x in
id 5

Some math:

\x. x * 3 + 2

Closures

\x. (\y. x+y)

From this, we can see that there are only two keywords, “let” and “in”. We’ll define those now:

> letKW = try $ do string "let"
>                  notFollowedBy alphaNum

> inKW = try $ do string "in"
>                 notFollowedBy alphaNum

> keywords = ["in", "let"]

A “this is a keyword” test will also be useful:

> isKW c = null ([c] \\ keywords)

Pretty much entirely stolen from the code for Parsec’s token parser library.

> kwfail f = do{ x <- f
>              ; if isKW x
>                then unexpected ("reserved word '" ++ x ++ "'")
>                else return x
>              }

Variable names are pretty simple, just have to check that the identifier we’ve parsed is not a keyword.

> var = spaced $ do
>                name <- kwfail ident
>                return $ EVar name

> ident = do
>         c <- letter <|> char '_'
>         cs <- many (letter <|> char '_' <|> digit)
>         return (c:cs)

We’re going to have literal integer values, which are pretty straightforward except that we need to convert the value into an integer when putting it in the ast.

> literal = spaced $ do
>                    n <- many1 digit
>                    return $ Con ((read n)::Int)

We’re going to have two arithmetic operations, addition and multiplication. Just to be fancy, we’ll abstract out the process of recognizing an operator. The following code is a function that takes a symbol and the AST representation and generates a function that, given a left and right value, generates the AST for that operation.

> mkOp sym val = do
>      symbol sym
>      return (\l r -> EOp val l r)

Now we can trivially define operators for addition and multiplication (and anything else, when we need to):

> add = mkOp "+" Add
> mul = mkOp "*" Mul

Order of operations can be tricky here. The standard “definition” (stolen from wikipedia) looks like this:

expression ::= additive-expression
additive-expression ::= multiplicative-expression ( '+' multiplicative-expression ) *
multiplicative-expression ::= primary ( '*' primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE

Unfortunately, it’s left recursive, which will throw Parsec into an infinite loop. Fortunately, there’s tools to deal with this, namely chainl1. Our arithmetic expression looks pretty similar to the above, once that’s taken into account:

> arithExpr    = arithTerm   `chainl1` add
> arithTerm    = arithFactor `chainl1` mul
> arithFactor  = parens aexpr <|> var <|> literal

Obviously we need a definition for an expression. Since we’re only concerned with what is useful in the context of arithmetic expressions, we’ll limit what can happen here to the things that could have an arithmetic value.

> aexpr = spaced $ do
>   n <- (try app) <|> (try $ parens app) <|> arithExpr <|> literal <|> var <|> parens aexpr
>   return n

A function application is composed of a (parenthesized) lambda expression or variable on the left and an arithmetic expression on the right.

> app = do
>   f <- (parens lam) <|> var
>   x <- (try $ parens arithExpr) <|>
>        (try $ parens app)       <|>
>        var                      <|>
>        literal
>   return $ App f x

A let expression binds a var to either a value or a lambda expression. Nested let expressions are allowed, but we have to take care to ensure that ultimately an arithmetic expression is evaluated. We’re also going to allow multiple bindings in a single let, immediately desugaring them into equivalent nested let expressions. Note that, unlike in Haskell, the order of variable naming is relevant. Fixing that is an exercise left to the reader.

Sample desugaring:

let f = 5
    g = \x. x + x in
    g f

let f = 5 in
let g = \x. x + x in
g f

First, we’ll start with the name binding. To aid in using this for our syntactic sugar, it produces a (Var, Exp) pair for the expression bound to a given name:

> binding = do
>   (EVar v) <- var
>   spaced (char '=')
>   x <- aexpr <|> lam <|> var <|> literal
>   return $ (v,x)

Desugaring the lets is as simple as taking a list of the binding results, along with the eventual body, and walking the list to nest each binding in the let expression for the binding before it. For completeness, we’ll handle the empty list case as well, even though it won’t be permitted by the parser:

> desugarLets :: [(Var,Exp)] -> Exp -> Exp
> desugarLets [] b         = b
> desugarLets ((v,x):[]) b = Let v x b
> desugarLets ((v,x):xs) b = Let v x (desugarLets xs b)

> letexpr = do
>   spaced letKW
>   xs <- sepBy1 binding (newline <|> char ';')
>   spaced inKW
>   many $ newline <|> char ';'
>   b <- letexpr <|> aexpr
>   return (desugarLets xs b)

A lambda expression starts with a backslash, introduces a variable name, and has either a let expression, a raw arithmetic expression, or another lambda expression for its body.

> lam = do
>   symbol "\\"
>   (EVar v) <- var
>   symbol "."
>   x <- letexpr <|> (try aexpr) <|> (try app) <|> lam <|>
>        parens lam
>   return $ Lam v x

We’ll need this function later on to ease the process of running functions over the parser’s output.

> runwith :: Parser a -> (a -> b) -> String -> Either ParseError b
> runwith p conv input
>         = case (parse p "" input) of
>                 Left err -> Left err
>                 Right x  -> Right $ conv x

Finally, we have a simple function to run a parser and print the output.

> runIO :: Show a => Parser a -> String -> IO ()
> runIO p input
>         = case (parse p "" input) of
>             Left err -> do{ putStr "parse error at "
>                           ; print err
>                           }
>             Right x  -> print x

Next time, we’ll start working on an llvm-based simple calculator.

2 comments

I promised I would give a bit more in the way of details on the ray tracer. Here they are.

During the last three weeks of the term we were directed to come up with a “term project” for the functional programming course. [1] We needed to come up with something that was interesting and exercised the features we’d been learning about all term. I’ve wanted to write a ray tracer for a while now, so I picked that. The assignment, as I gave it to myself, was to write a minimal but complete ray tracer and report on the experience of profiling and parallelizing it.

The ray tracer itself took around 30 hours of work. Partially this was me struggling with the language, partially me struggling with the topic, and partially me being picky and/or making and fixing bad design decision. When I turned it in it would only do spheres in flat colors and reflection (or a combination) with specular and diffuse lighting. I’ve been working on transparency and diffraction, but that code isn’t really worth showing off yet. I’ll eventually do some more complicated shapes and may explore more interesting materials.

Writing a ray tracer in Haskell was a … luxurious experience. The heart of a ray tracer is almost entirely math, and Haskell represents that very well. The only real difference between my Haskell code and the math behind it was some additional let bindings I introduced while profiling. I enjoyed being able to avoid unnecessary computations implicitly through laziness, instead of explicitly through conditionals, as I would have needed to do in other languages.

I originally planned to spend a few hours working on parallelization. I started playing around with it for fun while I was waking up with coffee one morning. Half an hour and 53 characters later I had around a 40% speedup on two cores. In this, Haskell kind of ruined the project for me. It was too easy to introduce parallelization into the program and have it just work. A very helpful co-worker ran some benchmarks for me on a few systems. Here’s the performance chart.

Performance chart

These results are rather informal, but you can see the impressive increases from parallel execution. I’m not entirely sure what is going on at the eight core mark, but I think it has something to do with an issue with (GHC only?) multicore support on Linux.

If you’d like to point and laugh at my code, you can find it here. I compile it on ghc with “ghc -O -threaded -o ray –make Main.lhs”. Comments are very welcome.

[1] Taught by Mark Jones (the initial author of Hugs) and Tim Sheard (who is just FP brilliant) amazing class.

7 comments

199 Lines of Haskell, about 30 hours of work. My first ever ray tracer! My first ever considerable Haskell program! Runs in parallel for ~40% speedup. More details to come.

No comments

Wow, a lot happened last month. Since this term for school is coming to a close, the work involved is piling up. As such I haven’t really been able to get much done for my projects. In addition to that, I started an internship at the very end of the month. I’m working as a tester for weogeo. They run a “geographic data marketplace”, which allows people to buy and sell pretty much any information with locations attached to it. (like geological survey results and census data)

The game development project has pretty well stalled out. I’m realizing now that my decision to develop it in flash was partly motivated by a pie-in-the-sky dream of earning money from it. Now that I’m working, this isn’t really as pressing of a motivation and the problems of working with in flash are starting to outweigh the benefits.

My compiler project is coming along a bit better. I have a lexer, written in alex for JavaScript. It doesn’t support unicode in the identifiers, but that is more of the same from the compiler’s viewpoint. I’ve been playing around with an abstract syntax tree to use in the parsing phase. OOP implementations of this can take advantage of inheritance to encode things like “a bit operation is an and, or, or xor of two expressions” in an inheritance relationship and use that to ensure valid trees are created. Since Haskell doesn’t (easily) support this kind of inheritance, we instead have to flatten things out and do this with the functions that construct the AST instead of encoding it in the type of the AST. Well, that or write a giant pile of data type definitions to do the encoding manually, which produces a bunch of almost-redundant constructors and a lot of busywork.

I’m probably going to go the “flat AST and functions to ensure valid construction” route. Either way I’m planning to write the parser twice. One version will use happy (Haskell’s equivalent to yacc) and one using Parsec (a nifty parser combinator library). So, I’d like the AST to be easy to work with. We’ll see how that goes.

No comments

This is a repost of something I wrote for the forums. Now that it’s lost to that refuse heap I thought it could also wait out its days in solitude here. If you haven’t played the video game “Left 4 Dead”, this will probably be just about unintelligible.

It’s understandable that a lot of people don’t really understand the Tank. He’s a rare spawn in general, and splitting the chance to play as him with three other people means little chance to practice. This affects the survivors too, as his scarcity makes getting experience dealing with him more difficult. That said, here’s a bunch of things about the Tank that people either don’t know, don’t think about, or are just flat out wrong on:

1. We should run like headless chickens:

This is just about never the solution, especially on VS. In most Tank encounters the real problem isn’t the Tank, it’s the other infected. Don’t panic and run like nuts, carefully stay out of his range and concentrate on keeping the area clear of other infected. They move faster than you do, the Tank (usually) doesn’t. A single normal infected can mean the difference between escaping unscathed and as that big wall of muscle turns you into a pothole.

The other problem here is that, while everyone is busy running away, they aren’t shooting him. The real approach to handling a Tank is to work as a group to keep your distance from him, and whoever isn’t being chased by him is shooting him in the ass. There’s two reasons for this: A) it does damage, which will eventually kill him (that’s the point, remember), and B) being shot temporarily slows him down, so being shot continuously will give his pursuee breathing room. This is key for saving someone who is < 50 health, or who runs into an unexpected obstruction. Try it, it works.

1. Set him on fire, then run like headless chickens:

In addition to all of the problems above, (in co-op only) setting the Tank on fire makes him run faster, which also means he runs faster than you. If your teammates are busy running in three separate directions he can now easily catch up to you and turn you into a pothole. Fire is great insurance against the Tank, but it won’t kill him fast enough to make a difference on all but the easiest difficulties. Fire+scatter is just as lethal in VS as scattering is.

1. As Tank, the rock throw is useless:

This just isn’t true. In some situations where the survivors are grouped together somewhere that puts you in easy range of a molotov and/or spray of bullets, it’s better to hang back and go for some rock throws from a safe distance. Picking up a rock tends to make anyone you aren’t pointed at brave, and makes them forget that the direction of the throw isn’t determined until just before it happens. Learn to grab a rock and do a last second turn and throw at someone pelting you in the back. It’s pretty much the only option to handle survivors that are kiting you well if your buddies let you down.

1. As a Tank, I should just charge in and do some DAMAGE!!!:

No, you shouldn’t. Well, maybe, but it isn’t that simple. You start out with a lot of rage time (I think 40 seconds). Take advantage of it. If the survivors keep advancing, look for the best spot to hit them (tight hallways) and bide your time. At the least, give your teammates time to spawn in and help you. If need be, try to get a distance rock throw in and retreat with your freshly regenerated rage timer. Like any other class in the game, the Tank depends on teamwork to get the job done. The only reason this doesn’t seem true is also the point of this post: statistically, no one knows how to deal with a Tank.

The other problem with charging in is that it’s predictable, and can be costly. On the NM5 roof the absolute worst thing to do is charge right through minigun fire at the survivors. Congrats on losing half of your health before you even get close to anyone. You’ll probably get set on fire too. If you hang back, especially if you run around the roof for an alternate route, you can hit them from a better position and give your teammates time to distract them. A survivor ready to throw a molly looks pretty distinctive, and there’s nothing funnier than owning up as a Tank because you waited long enough for a hunter to pounce the guy trying to set you on fire.

Parking a tank is pretty much sitting somewhere and letting your rage run out, so the tank remains stationary until triggered by the survivors, like in Campaign. The most notable place to do this is in NM4, in the final safe room. Not very honorable, but if the survivors are vent camping (behind the elevator) with a full stock of mollies and auto shotties, it’s just the way to stick it to them.

(Portion in *’s is courtesy of OmNomNomNom, thanks)

1. As a Tank, I should hit anything I can reach:

Usually, this is true, but if one of your teamates has pounced or grabbed a survivor your new priority is to protect that situation at all costs. In practice, a Hunter pounce does more DPS than Tank punches unless you consistently land every single punch as fast as you can swing (hint: no). If one of your teammates has a survivor, do your best to keep the rest busy and away from him. At the very least, don’t knock him free. Given that you have the ability to hit anyone else, you’re cutting into the team’s DPS by doing so.

1. As a Tank, I should hurry up or else I’ll lose control:

This can be a good thing. IMO they shouldn’t have put individual scores for infected in L4D, it just encourages people to play for their score instead of for the team’s benefit. Sometimes you need to wait for the right moment to strike, and sometimes that moment is after your rage timer expires. In my opinion it’s usually better to run in rather than let the AI take over, so if you’re the second one with it take your best chance within the rage timer. The only time this doesn’t work is if you’re trying to park him somewhere, but that’s obvious.

Other important facts:

1. The Tank’s swing takes a little time to connect. Try to lead your swing a bit if you’re running up to a survivor. Otherwise you give them a little time to get out from in front of you before they get hit.

2. The rock throw doesn’t auto fire if it’s held down after it charges. You have to spam the button if you’re trying to bombard the survivors.

3. In co-op, fire makes the Tank run faster. Be sure you have plenty of space to run around him, and are able to kite him around something while everyone else shoots him. In VS, it’s just about a win-win, just make sure you don’t have to run through the fire too much.

4. Vents and windows seriously slow down the Tank. Abuse/avoid this as appropriate. In co-op NM5, jumping through the window gives you a good 10-20s of shooting gallery time while he squeezes his fat ass through (portion in *’s courtesy of thomasng1989)

5. The AI Tank likes to climb stuff. If you’re kiting him around something watch for him to try and shortcut over it.

6. Meleeing an AI Tank in the back will cause him to focus on you. Use this to get his attention away from a downed survivor. Melee him and run away shooting to keep his attention. Only do this if the other two survivors are there to fire on him as well, otherwise it’s probably suicide. This is just about the only way to save someone on Expert.

7. You can shoot the rock. If you’re out in the open, do this. If you’ve got any kind of cover, that’s probably the better alternative. It takes a few hits to break, so don’t be surprised if this fact doesn’t always give you rock immunity.

8. Explosions (propane tanks, pipe bombs) stagger the Tank. They also do a decent bit of damage. Hitting him with a pipe bomb probably won’t happen, but if you can get him to run over a propane tank or three when you shoot them it can do a lot to help.

9. Unless you’re in green (correction: above 40 health), he runs faster than you. So if you’re in anything less than green the Tank music is your cue to heal up, get your pills ready, or put some distance between you and him and make peace with your maker. As a Tank, be aware that there’s a ten point range where someone having a yellow outline does not mean you can catch them.

Sections in *’s courtesy of madcap, among others.

1. Hitting survivors with an object (car, tree trunk, generator, anything outlined in red) is the fastest way to take them from green to incap. Go for it when possible, but watch out for situations (like the NM2 room below the generator room) where survivors can easily duck behind obstructions.

2. If you aren’t the Tank, he needs you to help slow the survivors down. They run faster than he does, but not if they’re Boomered and surrounded by commons. Likewise it’s pretty easy to meet the survivors at their target when they’re running to help a buddy who’s been pinned or tongued … or hit them with a rock while they’re doing so.

3. Avoid fire at all costs. Many survivors will throw their molotov ahead of you a bit early to give themselves more room to run. Watch their outlines; if they have the molly out look for the opportunity to stop short of running into flames. If you are on fire, you’ve only got a limited amount of time to go do some damage, make everything you do count.

4. Don’t be discouraged if you don’t do well. Sometimes you get outplayed, or your teammates don’t help, or you just get unlucky. If you tried to do what I outlined in this guide and still didn’t do much damage, examine how you (or your teammates) deviated from the suggestions or maybe how the survivors really did outplay you. I very probably do not know everything about the Tank, maybe you can learn something from your defeat and have something to share. Above all, anyone balling you out for not doing well is a punk or just a poor sport, don’t bother listening. Take constructive criticism and spend some time thinking about what (if anything) went wrong.

5. Memorize the finale sequence, and be prepared to help the Tank after the second infected wave. If you get the Tank, make sure to spawn your current infected in before he gets control, a bot infected is better than none at all.

6. If the survivors are doing a great job staying out of your reach, look for a good way to quickly get behind cover. Give your teammates a chance to distract them or give them a chance to slip up and give you an opening.

7. As survivors, be sure to have at least one person with an automatic weapon (Uzi/M16). Since every bullet slows the tank down on impact, these guns do a great job of keeping him away from everyone else. Also, take advantage of the minigun any time you can. It does great damage and also works to slow him down.

8. In stages where it is applicable (namely, NM4/NM5), look for opportunities to knock survivors off the edge of the building. This is a one-hit death for them, and can often be achieved by strafing as you move to position yourself opposite the edge of the building from the survivor. As a survivor, prefer taking a hit from the Tank to putting yourself between him and the ledge. Get off the top of the building (with the mini-gun nest) in NM5 as soon as you can to avoid being punted off. Any of the elevated areas in this level are dangerous, but it is usually difficult for a Tank to position himself to knock you from the lower levels.

No comments

I’m going to try and keep up with what I’ve done towards these resolutions at the end of each month. Hopefully this will help me stay on task. Here’s what I’ve done so far:

• On the game development front: I spent a bit of time this month trying to come up with ways to get a bit of extra money. One of the ideas was to work up some simple web games (in Flash) and try to get them published. I wouldn’t mind eventually doing my game project in this, and am learning to use the Flex compiler to write Flash projects in pure ActionScript 3. If you’re interested, I found a good reference here.

• On the Haskell/compiler front: I’m considering doing an AS3->Flash compiler in Haskell. The mxmlc compiler provided with Flex is written in Java, which means each recompile gets to enjoy the jvm startup time. Anyways, it would be a fun side project that probably will result in a half-finished compiler not suitable for anyone’s use. I’m sure I’ll learn something though.

• On the productivity front: Things are going ok here. I could be doing better, but I’m satisfied with what’s happened so far.

Obviously the “more blogging” goal is happening so far.

No comments

After spending some time thinking about what is going wrong with this game, I came to two conclusions:

1. Repl-based development doesn’t work for me. I ended up spending a lot of time working my way into an inconsistent game state without know it, so most of my time savings were spent figuring out how I’d borked things on the next restart.

2. Haskell is just too damn interesting. Every time I tried to work on the project I found myself goofing off there.

Obviously, these points say much more about me than the tools I was using, but the simple fact was that I still wasn’t getting much done. I actually really liked how clean the more functional bits of my original game code were, so I’m taking the plunge and switching to Haskell for my game.

Since I’ve been wanting to dig deep into Haskell for a while this should really push me there. So far just trying to express something as simple as “a game unit can possibly target something targettable” has been a deeper rabbit hole than I thought, and now that I think about it my current solution won’t work. Luckily the new one is simpler.

I’m well aware that this will probably mean the death of this game, but it already seemed to be in critical condition, and either way the learning experience would be good. Stay tuned to see what happens.

No comments