foldl.com - foldr.com
:-)
George Orwell and Others Online
Under Australian copyright laws, copyright in literary works of authors, who died before 1955, has expired. These works are now within the ‘public domain’ in Australia and this is why the University of Adelaide is able to reproduce such works on the world wide web. Here go some of my favourites:
Complexity of Type Reconstruction
Again I would like to draw an interesting example from Benjamin Pierce’s book Types and Programming Languages that is originally due to Kfoury, Tiuryn, and Urzyczyn. The following Haskell program is well typed but takes a very long time to typecheck:
module Main (main) where
main =
let f0 = \x -> (x,x)
f1 = \y -> f0 (f0 y)
f2 = \y -> f1 (f1 y)
f3 = \y -> f2 (f2 y)
f4 = \y -> f3 (f3 y)
f5 = \y -> f4 (f4 y)
in
f5 (\z -> z)
It has long been believed that type-checking programs in languages that allow for let-polymorphism appears to be “essentially linear” in the size of the input program. It therefore came as a surprise that its worst-case complexity is still exponential as the above example demonstrates ;-)
Crazy Patent Claims
My dad discovered the following patent claim. Compare this with my diploma thesis. Does that ring a bell ;-)
HBURG Version 1.0 Released
HBURG (Haskell Bottom Up Rewrite Generator) version 1.0 is available as of today! As always there is still work to do, but it is finally the time to release a first version. A very simple example compiler showing how to use HBURG in the compiler design and development process is provided as well.
- Please visit the HBURG project website for more information.
Dachstein Hiking Trip
We have made it to the top of the Dachstein glacier last weekend. The Dachstein is 3004m high and one of the tallest mountains in the Salzkammergut Region. We were very fortunate since the weather was wonderful and could not have been better for our task. Take a look at the gallery for some nice pictures...
One Concept - Many Names
Imagine an Abstract Datatype which consists of a collection of keys and a collection of values, and where each key is associated with one value. This description or concept I have just given is quite trivial to understand, at least that’s what one might think. What is interesting though is the fact that there are so many names for the same thing:
There are some other prime examples in computer science where this is the case, if you find other interesting examples please feel free to send me an email.
Heap Datastructure vs. Heap Dictionary Definition
In computer science, a heap is a specialized tree-based data structure. The nice thing about it is that it satisfies a very simple law, namely:
- If B is a child node of A, then key(A) ≥ key(b)
This simple law implies that the element with the greatest key is always in the root node.
There is a sort algorithm, namely Heap Sort, which utilizes this datastructure in order to achieve a worst case runtime of O(n log n), which is better than Quicksort for example.
Since the heap datastructure has such a nice property which makes it so useful, I looked the word up in the dictionary and what I found was quite amusing:
- heap: a collection of things in an untidy pile or mass…
Now I can understand the pile or mass part, since a tree can also somehow be seen as a pile, but untidy? That is a bit awkward and funny if you consider it from a computer science perspective.
I guess there is no Algorithms and Datastructures class out there where the Lecturer would call a binary heap untidy ;-)
Sources:
Hiking Trips
Finally I managed to partly migrate most of my photos to the new servers. So the all new shiny gallery is available over here. Right there you can also find the latest pictures from our last two hiking trips to Hallstadt, and to the Schoberstein.
Switzerland Trip
Last week I went to visit my friend Christian in Zürich, Switzerland. It was 3 days of fun, hanging out, eating loads of food and getting into trouble. This time we were doing stuff in Zürich like going to the Zoo which is one of the coolest Zoo’s I have been at.
There were also daily cook-outs and there are also some pictures of them – the most funny pics were taken with my iSight camera though!
We have also made some videos but I have to find some time to edit them first before uploading them. They are really funny, especially the one were the Swiss cops get on to us because they thaught we were smoking weed in the park with Christians waterpipe hehehe – and we have it all on tape! Of course we were NOT smoking weed but apple scented Shisha tobacco which doesn’t even include nicotine – but nevertheless we were falsely accused of being teenies trying to get high ;-)