(λblog. blog blog) (λblog. blog blog)

diverging since 2008

Entries from August 2008

2008-08-04 18:35

Assembly Summer 2008 ended yesterday. The level of the entries wasn't quite up to last year's although 64k Intro and Real Wild had some real gems in them. The music compos especially were appalling. I did like moravia, though.

Assembly 2008 also featured my first release: a short film titled Sakura. The flick didn't fare too well but that was to be expected considering the tastes of the masses ;). BTW, the winner of the short film compo was mind-blowing.

I was planning on participating in the fast music compo (1.5h time limit) but unfortunately my plane from IMC arrived after the deadline. I've already started working on two entries for next year: something for extreme music and something that I'll keep secret for some time longer.

PS. Alternative party looks interesting, especially with the discount.

Update 2008-08-05: Yeah, I'll be there. Hopefully I'll get something together for the one-track music compo :). Also, fixed links.

Tags: culture.

Finally switched from ion to xmonad. I still haven't fully adapted my workflow to the new window manager or vice versa, but I'm getting there.

ido for emacs is a great incremental tab-completing buffer switcher and file selector. Think iswitchb-mode and then some more. Another nice find are the up-line-or-search and down-line-or-search actions in zsh. They enable you to type for example sudo emacs and then browse through commands starting thus.

On a more personal note, I had my hair cut and have started packing for my impending move to Pasila. I've also been offered a chance to work at zendroid, the hottest startup in town. I'll probably have to decide between them and continuing at HIIT in a few weeks.

A couple I knew just broke up. Some of my friends are depressed. My girlfriend thinks we've wasted the summer. I myself feel as though I were slowly awakening from a very long sleep.

Additionally, you can start expecting part two in my attribute grammars and compilers series, it's well under way.

The semester is starting in a few weeks. I'm aiming at completing my candidate (bachelor for you foreigners) degree for christmas. Sadly there aren't that many interesting courses this fall, but I guess that's just good if I'm to be working part-time.

Tags: conf, life.
2008-08-24 23:30

Sorry, somehow managed to forget about writing part 2 for multiple weeks

Okay, I'll pick up where part one ended. I've added booleans and declarations in order to make type checking non-trivial ;)

> {-# LANGUAGE KindSignatures, EmptyDataDecls, MultiParamTypeClasses,
>              FlexibleInstances, GADTs #-}
> import Control.Monad
> import Control.Monad.Error
> import Control.Monad.RWS
> import Control.Monad.Reader
> data Expr
> data Stmt
> data Location
> data Decl
> type Identifier = String
> type Op = String
> type Symbol = String
> data Type = BoolType | IntegerType
> -- the empty annotation
> data NoAnn a = NoAnn
> data AST (ann :: * -> *) t where
>     If      :: ann Stmt -> AST ann Expr -> AST ann Stmt -> AST ann Stmt
>     -- note the added declaration list
>     Block   :: ann Stmt -> [AST ann Decl] -> [AST ann Stmt] -> AST ann Stmt
>     Assign  :: ann Stmt -> AST ann Location -> AST ann Expr -> AST ann Stmt
>     Var     :: ann Location -> Identifier -> AST ann Location
>     Ref     :: ann Expr -> AST ann Location -> AST ann Expr
>     Binary  :: ann Expr -> Op -> AST ann Expr -> AST ann Expr -> AST ann Expr
>     NumLit  :: ann Expr -> Integer -> AST ann Expr
>     -- these are new
>     BoolLit :: ann Expr -> Bool -> AST ann Expr
>     Decl    :: Identifier -> Type -> AST ann Decl

Descending from the Tower o' Ivory

I decided to partly break the attribute grammar abstraction by performing different phases inside different suitable monads. This increased coding pleasure and clarity in comparison to the generalized versions presented in the previous post.

> type M = Either String    -- aka Error, used for inter-phase communication
> type TypeM = ReaderT TEnv (Either String)   -- typecheck monad
> type CodeM = RWST SEnv () SState (Either String) -- codegen monad

The Reader monad is used for passing down symbol tables, and, in the case of code generation, the label of the current loop for use in breaking. These are the inherited attributes of the respective attribute grammars.

> data SEnv = SEnv { symbols :: [Symbol], loopend :: Maybe String}
> data TEnv = TEnv { decls :: [AST NoAnn Decl]}

Additionally code generation needs to keep counters for disambiguating variables and scopes (labels). The State monad corresponds to a top-down left-to-right flowing attribute.

> data SState = SState { var :: Integer, scope :: Integer }

Synthetic attributes are embedded in the form of the recursive traversal, no fancy tricks are needed to represent them.

As another step down the abstraction ladder I differentiated the type signatures of different phases to enforce and clarify the flow of information between the phases.

Typechecking generates an annotated AST from an unannotated one:

> data Attr a where
>     EAttr {etyp :: AST Attr Type} :: Attr Expr
>     LAttr {ltyp :: AST Attr Type} :: Attr Location
>     Empty :: Attr a
> class Typecheck a where
>    typecheck :: AST NoAnn a -> TypeM (AST Attr a)
> do_typecheck :: AST NoAnn Stmt -> M (AST Attr Stmt)
> do_typecheck ast = runReaderT (typecheck ast) (TEnv [])

Code generation takes an annotated AST and transforms it into code:

> data Code a where 
>     -- code is the body, out is the register the result is in
>     ECode {code :: String, out :: String} :: Code Expr
>     -- code fetches the reference, which is then available in ptr
>     LCode {lcode :: String, ptr :: String} :: Code Location
>     -- statement code is just a body
>     SCode :: String -> Code Stmt
> class Codegen a where
>    codegen :: AST Attr a -> CodeM (Code a)
> do_codegen :: AST Attr Stmt -> Either String String
> do_codegen ast = do 
>   (SCode code,_) <- evalRWST (codegen ast) (SEnv [] Nothing) (SState 0 0)
>   return code

Now our glorious two phase compiler (still missing the instances ;) could be written as \s -> parser s >>= do_typecheck >>= do_codegen. The do_ functions are restricted to statements on purpose: we know that the root node of the AST will be a statement.

Notice how the Code and Attr types are parametrized with the same phantom types as nodes in the AST. This is what we had in mind when designing the GADT.

Now we have managed to present different phases modularily while not straying too much from the original attribute grammar approach.

Okay, this has been sitting in my draft directory for long enough, better "realease early, release often"

Coming next: the implementation.

Update 23:35

Update 2008-08-25: The do_ functions

2008-08-26 17:25

The last two final courses for a candidate degree here at Univ Helsinki CS are Ohjelmistotuotantoprojekti (Software Engineering Project) and Tieteellinen kirjoittaminen (Scientific Writing). The former is a programming project for groups of about eight with make-believe real software engineering processes. The projects also have proper clients, though these tend to be other departments or research projects.

Like most universities nowadays, Helsinki is a Java school. You can probably feel the dread I had for executing a largeish project in Java with a bunch of Java programmers. Thus my exuberance on finding out that one of this year's projects would be extending a research project coded in LISP. Earlier this day our group tutor mailed us a link to Practical Common Lisp. Things are looking up :)

In other news, the move to Pasila went ok. The interview with zendroid is coming up.

Tags: life, programming.
2008-08-28 15:37

The interview at Zendroid on tuesday went smoothly. I saw some interesting demos and enjoyed talking to the guys. If you're still wondering, the company wants to implement cool robotics-mixed-with-machine-learning stuff that's feasible right now. Needless to say I can't tell much (NDA), but Zendroid is very much the sort of environment I want to work in. Also, they are using extensive unit-testing and git, i.e. doing things properly.

A few hours ago, I got an email telling me I was accepted. I'll be starting some time next month. It'll be interesting to see what working at a startup is like, especially after all the propaganda by Paul Graham and others.

Tangentially, I've recently been making mixtapes and brushing up on my DJ skills. I was also asked to play at a student party next month. Things are progressing very nicely on the music front, and I hope to have a proper mix on-line soon.

Tags: life, work.

RSS Feed