Development diary

Last modified:

2003-04-02 - 04-28

  • Lots of cunning rewrites and coding misery. Finally has something that works and does a few fancy things. It's not bulletproof in any way, but the rest of the work will have to wait until later.

2003-03-19 - 04-02 ~6 hrs/day

  • Finished backend for points. (does not take pointsize into account, yet.
  • Changed primitive commands to take functions from time to (pos,col,etc..) tuple, because we need to be able to differ between time for emitter and time for variables, thus we need to generate time-variables in the compiler
  • Completed global optimization. This works well but, is a bit slow and needs a few passes to find all expressions within expressions.
  • Let-floating seems to have quadratic or worse behaviour on the number of let's. It is the most time consuming pass and since it runs twice (before and after global opt), it probably needs some work.
  • Snapshots/state and rand-exprs get copied when creating the system. This will then result in several alpha-equivalent expressions (same math, different variables). Either take care of this with Ref:s, detecting where they are the same, or implement some sort of alpha-equivalence test in the CSE-algorithm. Clearly, compiler speed benefits from the former, as all subsequent passes get a smaller expression to work with.

2003-03-18 8 hrs

  • More work on report and backend.

2003-03-17 - 9 hrs

  • Started updating the backend.
  • Begun adding more material to the report and fixing errors in first draft.

2003-01-23 - 30 10 hrs

  • Fixed remaining bugs in first phases.
  • Browsing the CVS now works again.

2003-01-22 5 hrs

  • Now passes through all implemented phases, except cpp-gen, but still with a few quirks.

2003-01-21 5 hrs

  • More work on propagating changes.
  • Another attempt at tuple-stuff. No luck.

2003-01-20 5 hrs

  • Made an attempt at unifying tuples and vectors but got only to the point where a tuple written entirely with literals can be treated as a vector (or a tuple entierly with scalar exprs). No luck in mixing them properly though.

2003-01-19 11 hrs

  • Have integrated refs and reworked things to the point that expressions can be built and viewed by the pretty printer. Some internal compiler stuff is also updated, but local optimization and the cpp-generator is left.

2003-01-17 7 hrs

  • Started integrating ref-test framework into main codebase and redesigning a few things as well.

2003-01-16 8 hrs

  • More on cyclic lets. Rewrote some parts to make things clearer. Decided to introduce explicit LetRec:s where such sharing is used (this is detectable by using Ref). A separate function will then try to resolve them, if possible.
  • Untying the cycle works now!
  • State calculations can be split up into intialization, calculation of result and update of new state. Makes observing letrec/state combinations much easier.
  • Updated semantics document with info on let/letrec.

2003-01-15 3 hrs

  • Working on resolving cylic simultaneous let-exprs.

2003-01-14 8 hrs

  • Website polishing. The todo-list now holds a list that should be complete.
  • The feature-list on the main page has been updated. Removed data-structure selection as the current dynamic array + dead list is efficient for both linear and random death-patterns.
  • Updated the presentation

2003-01-12 - 2003-01-13 16 hrs (yes.. sixteen hours.. straight.. *yawn*)

  • Finalized first draft of semantics. See main page for link to the document. Of course, there are parts that need a bit more work.
  • Todo-list cleanup and addition.
  • Rewrote the code-example with better and more updated examples on how both the embedded language and the output should be. Also figured out a nice way to communicate with an external scene-graph graphic engine and how to write a moonlander game.

2003-01-10 3 hrs

  • Cleaned up some semantic defintions and started moving everything to LaTeX.

2003-01-09 7 hrs

  • Now identifies all loops in expressions, but simultaneous lets aren't handled correctly, yet. 
    let x = 2 + y
    y = 2 + x
in x+y
    should be transformed to the equivalent 
    let (x,y) = (2+y,2+x) 
in x+y
    Currently, we get something like 
    let x = 2 + (let y = 2+x) 
in x+y
    which is not quite right.
  • Also made it possible to transform expressions into (x_0 = const, x_n = f x_(n-1)). This is possible whenever any recursion happens through a state expression, f.ex. numeric intergration. State expressions are built thusly: 
    -- first element in tuple is the result, the other is the new state
-- the second argument is the initial state
state :: (Exp a -> (Exp b,Exp a)) -> Exp a -> Exp b
time, dt :: Exp Float
prev, derivate, integrate :: Exp a -> Exp a

time        = ...
prev e      = state (\x -> (x,e)) e
dt          = time - prev time
derivate e  = (e - prev e) / dt
integrate e = state (\x -> let i = x+e*dt in (i,i)) 0
    Of course, derivation and integration should be symbolic, with a fallback to an iterative solution for difficult expressions.
  • Future work is integrating these, so that cyclic expressions where the recursion goes through state can be calculated using iteration.

2003-01-08 7 hrs

  • Continued writing a testing module to try out ideas on how to solve recursive lets (i.e. detect them and make them explicit, then transform them so that they can be computed in the target language).
  • Successfully detects simple recursions such as let x = 2 + x in x. Now working on more complex patterns containing state.

2003-01-07 9 hrs

  • Working on how to resolve recursive let-expressions at initialization, so that a starting point for the iteration (simulation) is available.
  • Started some implementation tests on observable sharing.

2003-01-06 5 hrs

  • More semantics. The event/emit/display computational model is coming together,

2003-01-03 9 hrs

  • More semantics. Managed to complete a draft of semantics for expressions (Behaviours) but need to rethink how to handle events, emits and graphic entities.

  • Reworked the website, improved the layout and rewrote of incorrect/obsolete text.

2003-01-02 6 hrs

  • Studied Fran's semantics and begun writing formal semantics for HSpark's different constructs.

2002-12-01 7 hrs

  • Fixed a few bugs that crawled up during last session. Wrote a small example where particles collide with the ground (y-plane). Need to build/get a good linear algebra/geometry package for vector/plane manipulation.

2002-11-26 5 hrs

  • Removed Div/Sub/Neg from DExp and replaced these with functionally equivalent Sum/Product/Rcp stuff.

  • Has run in to a stupid bug where I get (mul (mul [x],mul [])) after optimization. I now see the benefit of having smart constructors, which ensure that these things just cannot happen. Then again, getting (mul []) shouldn't happen either.

  • CVS-tree is now browsable via web page. :)

2002-11-?? 15 hrs

  • Misc hacking on various parts. Trying out different features.

  • Looked at Vertigo, Conal Elliot's latest work which is a vertex-program compiler for DirectX 9. Took some time to get it working for the latests DX9 SDK Release (RC0 vs. beta 2), but I did get most of the examples running. Looked at a few implementation details, and the overall structure is similar but clearer than that of Pan. Normal form is used exclusively and the expression type is quite specialised for GPU instructions. It may be possible to use the Exp -> GPU-asm compiler which would make the HSpark compiler independent of other compilers (such as Cg or the D3DX HLSL compiler).

2002-11-06 3 hrs

  • Rewrote indexing so that it works properly with random expressions, variable analysis (indexing of a vector is now explicit in the expression tree and there is no manipulation of variable names) and a few other parts of hpark. This also means that it is possible to use a expression to index a vector, but this is not exposed to the user (yet).

2002-10-28 6 hrs

  • Made a workable executable file (!) and found lots of stupid bugs and a few bigger issues (randomized expressions don't mix well as arguments to other operations and indexing is a bit broken). Anyway, this zip-file contains source code and a windows executable that will show the following effect:

    This output was produced by this specification.

2002-10-24 12 hrs

  • More work on the C++ backend. implemented a simple emitter, spherical bounding volume calculation and particle creation/kill code. Need to work the compiler a bit more to handle integration expressions. Also battled with the pretty printer so that the C++ output now looks quite nice. The following specification is transformed into these c++ files. (Note that integrate_t is just a temporary placeholder)

  • These files actually compile properly with gcc. Yay! :)

2002-10-23 8 hrs

  • Completed working user-interface that allows the user to build a particle system. A system definition now looks like this: 

    posV = local3 "position"
colV = local4 "color"

initPos = vec3 (0,0,0)
pos = atRate vel
 where vel = rand (\v::Float3E -> v - atRate acc)
       acc = vec3 (0,-9.82,0)

red = vec4 (1,0,0,1)
color = atRate $ vec4 (0,0,0,-0.1)

initv = [posV <== initPos,
         colV <== red]

mySys = UserSystem {
   emitters = [emitInterval 100 (ifE (systemAge ==* 0) 100 0) initv,
               emitCont 20 initv],
   simulation = [posV <== pos, colV <== color],
   killwhen = kill $ age >* 10,
   visualizer = pointVis posV 1 red,
   boundingvolume = nobv
}

    There are of course a few issues to work out, but this will do for the time being. Need to develop things further and experiment a bit in order to decide on a proper way to build systems, emitters and allow easy extensions of previously declared systems. (The killwhen/kill stuff is a wart, will fix soon)

  • Made a compiler that takes a user-defined system and compiles/optimizes it to produce information that is suitable for backends. Does not have CSE or a complete type checking system. (Should be safe since we only let the user use type safe building blocks, but some internal error checking is always nice.)

  • Started reworking the half-finished C++ backend to fit the new frontend interface.

2002-10-?? 3 hrs

  • Worked on the C++ backend...

2002-10-14 6 hrs

  • Started on a C++ backend. Actually making progress after a two months of idleness and futile attempts.

  • Spent some time thinking about the CSE-algorithm, corrected it.

  • Rewrote Vec [DExp] as O Vec [DExp].. i.e. only one recursive case for the DExp datatype, which simplifies many operations.

  • Will keep all ideas in quarantine for a week or two. Of course I need to separate initial values from the simulation as such. Will try harder to stay focused with the current system and not change basic stuff all the time.

2002-10-11 2 hrs

  • Meeting with Koen. Worked out a CSE algorithm.

2002-09-12 3 hrs

  • More context wrapper/glue code.

2002-08-16 3 hrs

  • Begun writing a context wrapper for expressions in order to produce code that works. Decided that there's no need for separate intial values and simulation details. Each emitter can have particles that behave differently, but are still visualised in the same way. This at least reduces state changes in the rasteriser (and if we do software processing, we can just run different loops and then submit _all_ particles in one go to the renderer.). Splitting an expression into time-dependant and constant parts shouldn't be that hard.

  • nVidia's CineFX architecture allows for render-to-vertex array (numerical solving of diff-eqs) and conditional branching (complex if else and loops possible). I.E. everything can be computed on the GPU. Yay. Still need a card for that though. Definitely a possible future backend for HSpark.

2002-08-?? 20 hrs

  • A few more failed attempts on proper CSE. Can't figure out how to implement a proper mutable graph in Haskell. Have tried other approaches instead, but these generate too much garbage in the expression, and I dislike generate-cleanup cycles in the transformation (floatLet currently does this though).

  • Borrowed two books, The Dragon book and "modern compiler implementation in ml", and tried to find a good solution to the above problem. These books focus more on imperative dataflow stuff than an easy solution to the above (and the solution consists of repeated modifications to the expression tree). Will look at this later

  • Rewrote Let-optimization/lifting/cleanup. Better separation of lifting/cleanup and optimization.

2002-08-04 6 hrs

  • More CSE.

2002-08-04 3 hrs

  • Continued on CSE.

2002-08-04 5 hrs

  • Built together a small (40 lines) CSE-system which works, but is incomplete. CS within CS, and Ifs aren't handled correctly. Also, partial sums aren't extracted either. This is a non-trivial problem.

  • Defined an ordering for DExps and wrote sortExp which sorts commutative operator arguments (2*3 == 3*2). Need that to use FiniteMap.

  • Implemented constant folding for expressions partly made up of literals. (Previously only possible for exprs with nothing but literals.)

2002-08-02 4 hrs

  • Stomped out most bugs, so now we can go from haskell through local optimization and get a string representation of an expression. The string representation is a mixture between haskell and C, which works as a nicely formatted show instance for now.

  • Added Let-floating. Let's float up a high as possible (up close to If's, or beyond them if the same Let exists in both branches), so that no necessary computation is made, but we do not have Let's within mathematical expressions. This should satisfy the C-requirement that declaration of variables must be at the beginning of a block, and makes the expressions a bit more organised.

  • A (bad) example of the current state:

    pos = vec3 (10,10,10) + atRate vel
vel = rand $ \v::Float3E -> v + atRate acc
acc = vec3 (0,ifE (size <* 2) (gravity/2) gravity,0)
size = localF "size"
gravity = -9.82

    Get's transformed into the following pseudo code:

    ** X **
let rand_0 = rand()
in 10.0f + integrate_t ((rand_0))

** Y **
let rand_1 = rand()
in if (part->size < 2.0f) {
     10.0f + integrate_t ((rand_1 + integrate_t (-4.91f)))
   } else {
     10.0f + integrate_t ((rand_1 + integrate_t (-9.82f)))
   }

** Z **
let rand_2 = rand()
in 10.0f + integrate_t ((rand_2))

    Of course, an initial random velocity needs to be taken care of better. (The parenthesis are a bit of a mess too. :)

2002-08-01 7 hrs

  • More work on making sure previous changes work througout system.

2002-07-31 4 hrs

  • Added randomization fix, plus Random class and code to evaluate these.

  • NewVar (DExp -> DExp) prevents deriving of Show and Eq, so had to implement these manually.

2002-07-30 5 hrs

  • Continued modifications.

2002-07-25 5 hrs

  • Made &&,||,min,max multiple-arity ops like sum and product.

  • Begun with the vector operations and unification of all variables (temp,local,global).

2002-07-24 2 hrs

  • Decided on work schedule for coming month. Will produce a complete implementation from beginning to the end (i.e. produce working c++-code) albeit with some features missing. Everything major should be in though.

2002-07-22 3 hrs

  • Wrote a few more examples / development goals.

  • Meeting with Koen. Decided to do derivatives as in Fran (using atRate). This will probably work nicely to resolve cyclic expressions, and also to aid in any future work of actually solving these differential equations.

2002-07-16 5 hrs

  • Wrote an example on the user-interface of HSpark and came up with a number of issues.

2002-07-15 4 hrs

  • Read some more about Cg.

  • More documentation. Produces first draft of a slideshow outlining front-end of HSpark.

  • Battled with the NVIDIA SDK.

2002-07-14 3 hrs 

  • Lost 3 hrs of documentation due to buggy computer. AutoRecover didn't work. ARGH!

  • Cleaned up solution of random variable issue.

  • Still documenting and defining interfaces. Lots of thinking involved. :)

  • Updated the todo-list with issues on deriving particle properties from expressions and system termination.

2002-07-12 5 hrs

  • Meeting with Koen. Got a good solution on the problem of sharing and subtrees with random variables. 

  • Read papers on Fran implementation (functional -> stateful description) and QuickCheck (verification toolkit for Haskell programs).

2002-07-11 6 hrs

  • Continued documentation.

  • Read some interesting papers (Lava, etc.).

  • The graphics card has arrived (NVIDIA GeForce 4). Installed it and ran some tests on vertex programmability. Seems ok.

  • Solved typing problem in theory (haven't implemented it fully  yet, but it looks very promising). See task-list.

2002-07-09 3 hrs

  • HSpark website cleanup.

  • Begun writing documentation on system architecture.

2002-07-08 4 hrs

  • Tried different approcaches to solving the problem from yesterday. Read some language specs, ghc docs.

  • The problem is that Haskell lacks overloading on argument types (C++ supports this).

2002-07-07 3 hrs

  • Completed static layer (i.e. all parts are there. Needs some tweaking though).

  • Still needs work as it is too strict currently, automatic scalar->vec expansion does not work except for literals (which are converted to Exp *Vec* by using fromRational which is defined for that class. This creates something like E (LitF X) with the type Exp Float3/4, which is then expanded to a Vec-expr by the operators in DExp.) Would like to have a fromFloatE or similar.

2002-07-05 5 hrs

  • Meeting with Koen. Discussed different hashing approaches, memoization, etc.

  • Updated the web with more info, previous versions, etc

  • Begun writing statically typed layer. Works for scalar expressions / booleans.

  • Removed much error checking from DExp (did this a few hours after writing note on error-checker.)

2002-07-04 5 hrs

  • Finished local optimization.

  • Also updated if-floating code (which became suprisingly neat and now handles any-arity operators correctly)

  • (Am still amazed by the clarity by using Normal Form.)

2002-07-01 4 hrs

  • Continued rewriting local optimization code.

2002-06-25 8 hrs

  • Begun updating local optimization code.

  • The code gets a LOT cleaner with normal form.

2002-06-19 4 hrs

  • Printing of expression now works with new type.

2002-06-12 4 hrs

  • Finished rewrite.

  • Moved vector ops (dot-product etc) to separate file (ExpMath.hs)

2002-06-11 5 hrs

  • Begun rewrite of the basic data type into being in Normal Form