Thursday, August 22, 2013

LaTeX tricks

In this post I will gather different LaTeX tricks that I want to remember.

Changing the space between paragraphs

Command to change the space between paragraphs globally.

\setlength{\parskip}{desired space}

I think the default value is \baselineskip.

Friday, August 16, 2013

Processing: Optimizations and FireFox

I have done a lot of commits to the processing GitHub repo since the last Hackage release. I have discovered dozens of bugs that are now fixed. I have also implemented some new nice features, like conditionals with custom values or arrays. However, the nicest change has been done in the Substitution Optimization Algorithm. At least, this is the one I am more enthusiast about! It took me a while to get arrays working correctly, but it wasn't so exciting. Well, maybe arrays with custom values are a bit magical! They handle a set a of arrays of potentially different types under the hood, so you think that you are dealing with a single array.

In any case, the optimization process has been improved greatly. Now it looks for common sub-expressions inside a set of optimizable values, which are instances of a class. Instances of this class are automatically generated using Template Haskell. The nice thing is that, an expression of type Float can be inside an expression of type Integer (for example, in round pi), however, the optimizer will find expressions that are nested even in expressions of other types. Furthermore, the optimizer is now able to take greater pieces of code to work with, since it is now able to detect which variables are mutated. Therefore, it is able to stick to the biggest piece of code where variables can be treated as constants. Neat.

Of course, since I am the developer of the library, I find all these words easy to understand, but for the reader they may be quite opaque. In the section below I will try to explain the Optimization by Substitution Algorithm which is fully implemented in the processing package.

Optimization by Substitution Algorithm

A problem that arises when you are automatically generating code for a language you cannot evaluate is that the output code is usually slow and repetitive. Consider the following code example in Haskell:

foo :: Int -> Int
foo x = 2*x + 2*x + 2*x

Apparently (perhaps some cool GHC optimization you should no rely on is avoiding it) we are computing 2*x three times. To avoid it, the general technique is to create a let or where clause and include the repeated computation in it.

foo :: Int -> Int
foo x = let y = 2*x
        in  y + y + y

Now it seems clear that 2*x is computed only once. What we have done is to observe a repeated pattern/computation and gave it a name for its result. We then have substituted all the appearances of the repeated computation with that name. This is an intuitive way to avoid repeat computations, and this is exactly the idea behind the Optimization by Substitution Algorithm. I am pretty sure that this has been done before, but I give it here my own perspective, applied to my library.

In processing.js (JavaScript), we can apply a similar technique to that we applied to Haskell. Consider the following assignment.

v = 2*x + 2*x + 2*x ;

We can create an auxiliar variable, store the result of 2*x in this variable, and then use it to calculate the value of v.

y = 2*x ;
v = y + y + y ;

And this is how we adapt the above technique to JavaScript code.

Unlike Haskell, processing.js variables are mutable. The same variable x may have different values, depending on the last assignment done to that variable. Each time an assignment is done, the value of the variable may change, and we can't know if the new value is going to be the same or not (probably not). For example, consider the following code.

v = 2 ;
v = 2*v ;
v = 2*v + 2*v ;

At first sight, it seems that we are doing the same operation three times. However, the value of v has changed over time. If we replace all the appearances of 2*v we alter the result of the program.

v = 2 ;
y = 2*v ;
v = y ;
v = y + y ;

In the first program, the final value of v is 16. In the second program is 8. We cannot make substitutions freely in this situation. The solution I came out is to keep track of every mutated variable. When we reach an expression that uses one of the mutated variables, we apply substitutions over the code we have traversed so far, without including the expression that uses the mutated variable. Once we are done with the substitutions in that fragment of code, we repeat the process starting from the expression containing the mutated variable. This way, each piece of code where we are applying the Optimization by Substitution is safe.

Is this enough?

After my testings I am very happy with the results. However, in some browsers, like FireFox, it seems that my current test example is not running smoothly. I have made a Pac-Man game (a slightly simplification of the original) and looks like FireFox is not able to run the script smoothly. Either we need further optimizations or FireFox is just not good with processing.js. Perhaps the problem comes from processing.js, which may be not efficient enough. In any case, the game runs perfectly in Chrome/Chromium. I haven't tested with other browsers yet. Try it yourself here.

In the near future

The development of the Haskell processing library is not going to stop yet! More features are to come, and more bugs are to be found (and fixed!). Please, do not hesitate in try it yourself and report any annoyances in the issue tracker.

Thursday, August 8, 2013

Getting started with GHC hacking

After reading this blog post by Jason Dagit with the same title as the one you are reading now, I opened a new terminal session and cloned the GHC repo to my computer. Then, I successfully built GHC. Easy and faster than I thought. Online docs talk about hours of compiling process, when for me it only took some minutes (about 20-30 minutes). But, yeah, I provided the -j3 parameter to compile it in parallel. It works like a charm.

After having GHC built from the source for my first time, I decided to make a modified version of GHC. This version is aimed to really professional Haskell hackers who don't need any help from any source to know which commands are available in GHCi.

This is just my first step to get involved in GHC coding. :)

Monday, August 5, 2013

Processing: Key events

After being thinking and then hacking on processing yesterday, now key events are alive. After implement the feature, and add access to it from the interactiveFigure function, I wrote a code example to see it working. It was really helpful since it showed up some bugs I was not aware of. For example, variable numbers contained in conditionals were wrong. I have uploaded to Hackage a new version fixing this bug (and some other) and with the new feature of key events. Probably, we will find more bugs in the feature. In the meanwhile, please, update to the new version.

I post here the output of the key events demo (code here). Click over the canvas to make it work. Press W to move the black square up, A for left, S for down and D for right.

To interact with keys using the simple interface, use the interactiveFigure function. There is an argument of type [(Key, w -> w)] to handle key events. Each pair included in the list will specify a key, and the transformation over the current state that particular key does. As simple as that.

Saturday, August 3, 2013

From Haskell to Processing

I am happy about my last Haskell project. Its name is processing, and it is a library aimed to generate processing.js code. Actually, the purpose is to create interactive web animations, and processing.js is just the selected backend.

inCircles n =
  let t = intToFloat n * 0.03
      r = 100
  in  Circle (r * sin t, r * cos t) 20

I found the process of creating the library both funny and exciting. Phantom types, Template Haskell, Monads, ... I have used all the Haskell artillery to make the library nicer for the user, with some extra work from the developer (me). A lot of work still needs to be done. However, I am going to make it public right now, since it is already capable of working reasonably well.

Some days ago I published one of the output scripts in reddit to make sure that these animations are compatible with different browsers and settings. And it seems that it worked for everyone. Here is the animation I posted (try to move your mouse inside).

The reason I started working on this library is that I was looking for a library to write web animation scripts, without the need of running a server for them. Mainly, because I do not own a web server (I only have a web hosting, where I can upload these scripts). I looked through several choices, and processing.js suited my purpose very nicely.

Levels of abstraction

The library is built by levels of abstraction, and I have allowed the user to use any of the levels, hiding selected entities to make sure the user builds correct processing code. For example, you won't be able to use a variable before it is defined, create a variable twice, or calling a function where it does not make much sense. The compiler will stop you. The library levels are classified in the following form. Each one is built on top of the previous one.

  • Primal. This level is actually hidden in an internal module. It defines the abstract syntax tree of a processing script, how to print it, and other pretty basic stuff. However, it is one of the largest modules. It is the core of the library.

  • Basic. This level exports a writer monad which produces processing code. Imperative feeling. It is not really convenient, but it served me as starting point to work in the next level of abstraction. I exported it since it does not do any damage, and also because it has the property that the generated processing code is predictable.

  • Mid. Full-featured like the basic level, but more convenient. Still imperative feeling, but it makes sense given the nature of processing. It works using events, with things like

    on Draw $ do
    on MouseClicked do $

    The output processing code produced by this level is optimized using a common-subexpression recognition. It searches for commonly done operations, and create variables for them where they are only done once.

  • Simple. The most convenient level. Haskell-ish feeling. Create values of the Figure datatype (defined in the same module) and let the library decide how to write the processing code for you. It includes several options, like static image displaying, time-dependent animations or even interactive animations (very experimental yet). It is inspired by the gloss library, which I think is the perfect example of easy-to-use animation library.

Using the Simple interface I have created this recursive animation.

You can see the complete code here. More examples are to be added in the future.

Future plans

In the near future some of my planned additions are: arrays, conditional values, pre-made figures, images (the type is there but there is no function to create them) and more examples. I also have to do more testing and check if the library documentation is clear enough for a new user. Any contribution in this regard would be really appreciated. The library code lives in GitHub.

Thanks for reading,
Daniel Díaz.