Category Archives: programming

The joy of Elm

Elm is a purely functional programming language for creating web frontend. It is strongly typed, largely influenced by Haskell – without some of the things that make Haskell difficult for newcomers, and with much better error messages.

I’ve recently written two small (~2k lines total) side projects in Elm. Writing code in Elm is an absolute joy:

  • It’s easy to get started and Elm is a simple language.
  • Very strong typing – seems somewhat stronger than in Haskell. Eg List.head is of type List a -> Maybe a and won’t crash on you in runtime – if the list is empty you get Nothing. If it compiles it usually works.
  • Elm has amazing error messages. They don’t just tell you what’s wrong, they try to explain why that could be and suggest how you could try to fix the error. I have never before encountered errors this helpful.
  • There’s Ellie – a wonderful online environment to play around and share snippets.
  • The Elm Slack is the most helpful and responsive community I’ve ever participated in.
  • Refactoring is a breeze – it compiles it works. I’ve never had a refactoring mess up things that worked before.
  • Yes Elm compiles to JavaScript, and I’ve never had to dive into the generated code.

That said, there are some potential drawbacks:

  • No higher kinded polymorphism: to map over a List, you need to use List.map, to map over Set, use Set.map. This is slightly verbose and sucks for the library developers, but isn’t a big problem for the end user.
  • Elm-land is an autocracy. Evan has been a very enlightened ruler, so this could also be seen as a benefit.
  • The development of Elm itself is intentionally slow: they try to get it right rather than get it out quick. Some things one would like in the standard library are external libraries. The repository of Elm packages is rather comprehensive.

One year with Scala

This is gonna be rambling personal experience. You have been warned.

A year ago I took a break from my work at Inviqa to learn Scala and functional programming. This has been a great decision, a most successful endeavour, and an amazing learning experience.

I’ve been stuck with PHP for a long time. Mind, at Inviqa we were doing as good PHP as one can. I learned lots about software engineering from a multitude of conference speakers and industry leaders. This was further helped by a very active learning & development department and a generous conference/learning budget. Still, it was PHP. The language sucks.

Learning Scala as a “better Java” kind of language was easy. Case classes, options, lots of easy wins. Learning functional programming… well, I’ve been reading the awesome Functional Programming in Scala book, and I’m still reading it one year later. Despite its hands-on approach and lots of hand-holding, it’s not easy for me to digest. Functional programming is hard.

I used to really like Python. I wrote about 50 lines of Python recently, and just couldn’t believe how difficult it was. One needs to explicitly write return to return values. When just trying things out, you don’t get quick feedback from the compiler. Either write tests or run your code – the former seemed like overdoing it for such a short program, the latter was tedious. Working with the collections was a pain.

Let’s have a look at an example. What we want to do: split a string on commas, then strip whitespace from each element.

In Python:
map(lambda i: i.strip(), re.split(',', string))

In Scala:
string.split(",").map(_.trim)

The relative conciseness of Scala is nice, sure, but the Scala code basically follows the instructions: take a string, split on a comma, trim whitespace. Python is completely cryptic in comparison.

The main drawback of Scala is not the language but the ecosystem. SBT (Scala Build Tool) is powerful but often times incomprehensible. The compilation can be slow at times. Scala’s Play Framework is not nearly as polished as PHP’s Symfony. Replacing any piece of Symfony is just a dependency injection away. Replacing a component of Play is bordering on impossible, everything depends on everything and is mostly hardcoded. I wanted to do a really simple one-line change in Play Framework routing but had to give up.

Inviqa didn’t have as much interest in Scala as I hoped, so regrettably, I stopped working for them. Now I’m part of KwiqJobs (soon to be Swarms Technologies), an amazing startup. We turn people’s waiting time into a new resource for companies. Our tech team works remotely and we meet about once a month for a week. It’s lots of fun! Also we’re hiring! :)

ListMap in Scala

You probably don’t want to use a ListMap. It has an interface of a Map, but is “powered” (that’s too good a word) by a List. Thus pretty much any Map operations you call on it will take ages. Consider using a LinkedHashMap instead – it will preserve both the element order and your sanity.

That’s me trying to blog more.

Explorations in AI – solving RoboZZle

RoboZZle is a robot programming game. You can play it in your web browser (even without Silverlight), on Android, or iPhone/Pad/Pod. Go and try it, otherwise the rest of this entry won’t make much sense.

After a while of playing the game myself, I started getting interested in creating a program to find puzzle solutions. Having completed Intro to AI by Sebastian Thrun and Peter Norvig in 2011 and never using the techniques since, this seemed like a good opportunity to explore them further. As things go, none of these techniques appear directly applicable and a simple evolutionary search seems best.

Approach

I started by writing a solution runner, the main output of which is determining whether a given RoboZZle program solves a puzzle. Next were a robozzle.com client, utilizing the awesome Python requests library, and finally solver randomly generating programs to be tested by the runner. You can browse the source code of Zlej Rob at github.

Some facts about the solver:

  1. Start with an empty program.
  2. In each generation, each of the surviving programs will have ~100 randomly generated offsprings.
  3. A program is mutated by overriding (or removing) 1 to ~3 instructions of its parent.
  4. Programs are scored: positive points for reaching a square, extra points for collecting stars, and a negative point for each program instruction.
  5. If an offspring achieved higher score than its parent, it’s added to the current program population.
  6. Program population is kept to ~100 programs with highest score.

I decided not to cross-breed programs at all, as it doesn’t feel like it would be helpful.

Surprisingly, keeping a set of all evaluated programs doesn’t eat all the memory (and prevents recalculating the same thing over and over, speeding up execution by an order of magnitude). Yay for sets of tuples!

Results

Zlej Rob has solved over a 1000 puzzles in a couple of weeks of running on my $5/mo DigitalOcean (that’s a referral link – sign up and I’ll get rich) droplet alongside this blog and a couple other things.

Zlej Rob’s good at solving one-way street puzzles with one function, bad at anything involving multiple functions, mediocre at multiple-possibilities puzzles, and passable at random walks.

Zlej Rob discovered the shortest solution for Twins 2 (which I improved by removing a redundant function call). I think that’s pretty impressive. The solution includes a lot of recursive calls, and the replay takes ages – the robot loops and loops, seemingly never getting very far.

Ideas for improvement

  1. Visualisation. Would help identifying why certain things work and others don’t. I’ve almost started writing an Angular app to do that.
  2. Smarter mutations. Mutations should include abstracting random instruction subchains into other functions (this could be very useful for multifunction problems where Zlej Rob usually fails terribly because it can’t connect the dots). It might also be better to insert instructions instead of replacing them.
  3. Program diversity (“similarity penalty”). Surviving population for each generation is around 100 programs (toyed with higher values with no positive results – if anything, having 1000 programs is terribly slow), and they can all easily end up being very similar, getting stuck in local minima.
  4. Higher score programs should have more offsprings. Could speed up certain puzzles but perhaps make less obvious solutions unatainable. Would need to ensure program diversity first.
  5. Hints. For puzzles with an “obvious” order in which squares must be visited (such as binary counting or limit your stack), mandate this order. Currently, Zlej Rob finds random solutions that sweep vast majority of the board in a haphazard manner. Forcing the order in which squares must be visited would be extremely helpful, but likely requires human participation. Perhaps that’d be cheating?

Where do we go from here?

Zlej Rob’s results have surpassed my expectations, especially considering I haven’t spent that much time on it. Getting Zlej Rob into top 10 of RoboZZle players seems possible but would likely require an order of magnitude more effort than I spent so far. Not sure if worth it?

Dotrc aka ~/.*rc

If you don’t understand the title, you might just as well leave — this post is going to contain close to no useful information for you.

I’ve been spending a lot of my time in the shell recently. Mostly splitting my time between bash and vim, usually in screen.

I’ve always had a reasonable .bashrc, and my .vimrc used to be above average as well. But I invested some extra time to research more possibilities the dotfiles offer. You can preview and download my dotrc at github.

Here are some of the highlights, whatever I consider the “best of”.

My .bashrc is unremarkable, I just have a lot of shortcuts for the common everyday stuff. Perhaps the only thing worth noting is title setting for screen:
PROMPT_COMMAND='echo -ne "\033k`echo $PWD | sed "s:.*/\(.*/.*/.*\):\1:g"`\033\\"'
I actually wrote that myself, it shows the innermost three directories that you’re in. Showing running command in title is useless, as that’s in most cases either bash or vim (rarely also mysql). Showing the full path is useless, because long titles get cut off. Showing only the current directory name is not so great either, as it leaves you without context. I’ve settled for last three so far, but two might also be useful in certain situations.

Perhaps the best tip of all, reduce amount of tab hitting for completion by 50%. Put following to your .inputrc:
set show-all-if-ambiguous on

Next in line is my .vimrc (sorry, no .emacsrc, emacs sucks). Except for the usual stuff (nocompatible, colours, incsearch, etc.), I use few very useful and not very well known tricks.

set so=10 " show 10 lines of context (above and below)

“so” is short for “scrolloff”, which makes sure you have some space to breathe.

Last but not least, the Esc key is real far, hence:
set tm=400 " timeout for shortcuts

inoremap jk "pressing j and k together escapes
inoremap kj

Have I missed any useful tips & tricks?

Gödel, Escher, Bach

I just finished reading Gödel, Escher, Bach by Douglas R. Hofstadter. I’ll wait for you to at least read the wikipedia description of the book.

Done? Ok… The main surprise for me was how many seemingly unrelated topics the book touches. Logic (Gödel), graphic art (Escher), music (Bach) to start with. But also mathematics, molecular biology, genetics, philosophy, zen buddhism, formal systems, artificial intelligence, programming, recursion and self-reference, various paradoxes, and much much more.

It is easily the best book I’ve ever read, although I can’t claim to have understood everything. If you want to borrow my copy, I’d be glad to help (the book is sort of expensive and really hard to get in Czechia).

New look again

I was thoroughly bored with the previous theme, and although I tried to revive it with the new header image, it was still bugging me. So I created a new one.

I had a draft of a new theme lying around for quite a long time, so I made few adjustments to it: made the code much longer and much less clean. But it seems to work.

Features of the new design include, but are not limited to:

  • big letters in headings (big letters rock)
  • even less images (none, except the two links to flickriver, smilies and images in posts)
  • half-fixed-width half-fluid design (the design is fixed width, but the sidebar is fluid — works well for many different widths of browser (800px — the sidebar isn’t displayed, it’s accessible through scrolling; 1024px — sidebar in one column, 1280px — two columns, more px — more columns (it is capped at three columns)))
  • emphasis on typography (lists, blockquotes, etc. are styled properly)
  • lines vertically in synch (left column, middle column and sidebar)
  • the old color scheme, I mostly like it and more importantly — couldn’t find a better one at the moment :)
  • justified text (I’m still very unsure here — justified looks way better, but left-aligned is more readable)

Bugs of the new design include, but are not limited to:

  • IE6 sometimes messes up the sidebar, not quite sure why
  • Opera doesn’t keep lines in synch when there are smileys (and I thought I had the solution, sigh…)
  • IE doesn’t align the comment date in the comment list (will look into that later)

Also, I spent ages dealing with various bugs in IE that caused things to disappear.
One such bug caused the sidebar not to appear (it was an absolutely positioned element next to a floated element — don’t ever do that), another sometimes caused titles to disappear (they were relatively positioned, now that they are static it seems ok, but I have no idea why). When repairing the sidebar, I had to move it in front of the actual content in the markup, which is wrong and I know it. I am sorry to all lynx/links users out there.

Bug reports, remarks and suggestions are welcome! ;-)

Nothing is random, everything has a meaning.

Nothing is random.

Everything has a meaning.

The scene fits in under 100 lines of code (with comments! :)), so I decided to publish it here.


/**
* Simple POV-Ray scene with reflective pillars
*
* @author Vit 'tasuki' Brunner
* @license GNU GPL, http://www.gnu.org/copyleft/gpl.html
* @version 2.7, 2008-11-05
*/

// dark and reflective texture
#declare ShinyDark =
texture {
pigment { rgb 0 }
finish {
ambient 0
// reflection .3 // dark version
reflection .6 // light version
specular 3
}
}

// create a pillar of specified height
// kind of hackish, but I can't find a better way
#macro pillar(xx, yy, height)
#declare counter = height * 2;

#while (counter > -1)
superellipsoid {
<.3, .3>
texture { ShinyDark }
translate y * counter * .5
translate x * xx * 2.2
translate z * yy * 2.2
}

#declare counter = counter - 1;
#end
#end

// just some random (random, really?) pillars
pillar(-3, 3, 2)
pillar(-1, 3, 4)
pillar( 0, 3, 3)
pillar( 2, 3, 0)
pillar( 3, 3, 2)
pillar( 0, 2, 2)
pillar( 1, 2, 1)
pillar(-1, 1, 3)
pillar(-1, 0, 2)
pillar( 0, 0, 1)
pillar( 2, 0, 3)
pillar(-2,-1, 2)
pillar(-1,-1, 3)
pillar( 1,-1, 0)
pillar( 3,-1, 2)
pillar(-1,-2, 1)
pillar( 0,-2, 2)
pillar( 2,-2, 1)
pillar( 3,-2, 0)
// there's no such thing as random...

// the sphere everything is wrapped in
sphere {
<0, 100, 0>, 100
hollow
pigment { rgb 1 }
finish {
ambient .6
reflection .05
}
}

// get light quality from clock (+K in params)
#declare qualight = clock;

// back right less bright white light
light_source {
<30, 25, 40> rgb .5
area_light <0, 10, 0>, <0, 0, 10>, qualight, qualight
adaptive 1 jitter circular orient
}

// front right white light
light_source {
<30, 20, -30> rgb .7
area_light <0, 10, 0>, <0, 0, 10>, qualight, qualight
adaptive 1 jitter circular orient
}

// front left blue light
light_source {
<-15, 25, -15> rgb <.3, .7, .9>
area_light <0, 20, 0>, <0, 0, 20>, qualight, qualight
adaptive 1 jitter circular orient
}

camera {
location <7, 9, -14>
look_at <2, 1, 0>
}

To render the picture, you should run something like:


povray +Ifilename.pov +FN +W1024 +H768 +Q9 +QR +A0.5 +AM2 +K11

Well, that’s it. Hope you enjoyed ^^

Oh, you actually want to see the picture? Please check it out on deviantart.

And remember: Nothing is random, everything has a meaning…

.htaccess, document root and Zend Framework

It’s funny but I couldn’t find anyone having this issue. It certainly isn’t limited to Zend Framework, it affects everyone who doesn’t have access to apache configuration and wants to have document root in a deeper directory. Maybe I just can’t google very well.

Imagine a shared host. You can’t choose your document root, it’s firmly set to one particular directory. Now you want to install Zend Framework. Imagine you’d like to follow the standard directory structure (that means you more or less have these directories in your project: application (the application), library (zend and other libraries) and public (stuff accessible from the outside, images, css etc.)). Normally, you’d want to point your document root to the public directory, but when you can’t do that you can use .htaccess in the project directory to redirect everything to public.

RewriteEngine On
RewriteRule !\.(js|gif|jpg|png|css|txt)$ public/index.php [L]
RewriteRule ^(.*)$ public/$1 [L]

This was the first thing I wrote, and it works on certain servers. Other servers will kindly remind you that “Request exceeded the limit of 10 internal redirects due to probable configuration error.” Which kind of makes sense when you think about it. Makes me wonder how comes the above code actually worked on two different configurations.

Now here’s the code that works (and in my humble opinion it also should work, as opposed to the one above):

RewriteEngine On
RewriteRule !\.(js|gif|jpg|png|css|txt)$ public/index.php [L]
RewriteCond %{REQUEST_URI} !^/public/
RewriteRule ^(.*)$ public/$1 [L]

And finally a disclaimer: I am not sure about the security implications. If someone knows more about possible security issues with this, please do leave a comment.

Tone Mapping with GIMP

“Tone mapping reduces global contrast in images while increasing local contrast and shadow/highlight detail.” or so Gimp Addict’s Tone Mapper tutorial says. Go and read his tutorial, I will add few comments to it:
4) “radius of 100-500 is good” — yes, it usually is, but since we don’t know the size of the image, I’d rather say that 10% of image size (that is (width+height)/2) is a good starting point.
5) 75% is again a good starting point, but you might want to play around with the value.
7) It depends… if you want to increase the tonemapping effect, duplicating the “soft light” layer is the way to go (I’ve tried changing the layer mode and nothing else really worked at all).

So I wanted to create a script that would do this. After searching the GIMP Plugin Registry, I found Tone mapping script, which basically follows Gimp Addict’s guide. However, it only has two options – the amount of blur and the amount of layer transparency. That certainly isn’t enough for me. Luckily, the plugin is GPL…

(((GIMP’s Script-Fu) uses Scheme) (which is (a dialect) (of the (Lisp (programming language)))) ((Lisp is a (programming language)) (for people) (who (really (really (like parentheses))))))

And because I like parentheses almost half as much as an average Lisp programmer, I rewrote the Tone mapping script and created Advanced Tone Mapping script. Feel free to put it in your GIMP’s script directory (~/.gimp-2.4/scripts/ in my case).

There are four parameters for Advanced Tone Mapping script:

  • Gauss. Blur (% of img size) — is the amount saying how much the blurring should be used for the tone mapping. It is in percents of image size (where image size = (width+height)/2). Ten is a good default, but different values might be interesting too.
  • Opacity of blurred layer — this is the 75 default, which can be changed if you want stronger or weaker effect.
  • Opacity of merged layer — the default is 90. If 100 is not enough, consider increasing number of “copies of merged layer”.
  • Copies of merged layer — when one, it’s barely noticeable, you can deny any accusations of postprocessing easily. :) Three has a lot of “halo effect” and anything above five will completely mess all colours up.

The first set of pictures is simply a preview. The image on the left is the original image, and the image on the right is processed by Advanced Tone Mapping with Gaussian-blur set to 10, opacity of blurred layer equal 75, opacity of merged layer full 100, and finally three copies of the merged layer (note the way I use to show those values — it is also used for naming the layers, which can be handy if you later forget which layer is which or what you have done). The image on the right might be a bit over the top, but it shows nicely what can be done with Advanced Tone Mapping script:

Tone mapping

The next example shows some pretty conservative tone mapping. The one on the left was created with almost none blur, while the one on the right has 10% blur. Note the difference: the one on the left has no halo but appears a bit flat, while the one on the right has a slight halo but also has higher level of detail.

careful Tone mapping

Oh my… the following example shows what can go wrong with tone mapping (I’m sorry for all the people who already gouged their eyes out). The reason why image on the left appears so flat and awful is that almost no blur was applied. The image on the right is a comparison with healthy blur applied. Five copies is still a bit too much, but hey, at least it has kind of action-like look.

Tone mapping gone wrong

The last image shows the difference between the default blur and maximum blur available. As you can see in the right side picture, the halo is so huge it’s almost impossible to see. The bad news is that with maximum blur we lose a lot of detail near the borders of light/dark areas.

Tone mapping different halo

Ok, that’s it — now go and experiment with my script on your own photos. 8-)

PS: Underexpose your images — the dark areas can still be lightened, while the burned out areas are usually completely white and can’t be darkened.

PPS: The more contrast there is, the more layers you apply, the more blur you will usually need.

PPPS: Any kind of noise in your picture will be greatly amplified.

PPPPS: No, this is not HDR, this is just tone mapping of a single image (just jpeg, in my case). Tone mapping is a part of HDR, but HDR is not a part of tone mapping. ;)