ByteLabs

Well, as I thought I should probably keep you up to date about what I am doing and up to… After last week, my quite “crazy” Exam-Week I’m done will all of my exams. It’s awesome to be “free” again, although I should start doing my projects. Or let’s better say, I should finish them!

The Wire Tree My Visual Art project… it is going to be a sculpture, a tree out of wire. It is supposed to reflect the impact we have on the environment and all the issues through global warning and the questions and so on… I am going to put Coke Cans onto the tree, instead of real fruit. Wonder how it is going to turn out when it is all done, finished the stump today.. =D

Packaged Personality This project is for Visual Design… We have to create a package or bag or whatever that is reflecting our personality and of course I’m making a handbag. Let’s say I already made it – out of a T-Shirt. I am damn proud of it. It’s gorgeous! gg Just can’t help it… Now I just have to put stuff in there that reflects my character as well… let’s see how far I get. Wish me luck! =}

Well, I’ll try to keep you up to date. As I said. I will try. Not so much in the coming weeks, am not really going to be at home… Monday – Wednesday: Crossroads (it’s a school camp just for Year 11 – it’s gonna be awesome!) Friday – Monday: Camping with my friend Shanade =D Tuesday – Wednesday: Canberra and I can not wait! There’s this flower festival on and it’s going to be just BEAUTIFUL! Sunday – Sunday: Art School =D (am not sure about the date, I keep forgetting it…)

And would be nice if you drop by at cherryTREE my portfolio. thx already.

Ines <3

HBURG is now also available via the Haskell HackageDB if you follow this link.

If you have written lots of Haskell code and used tabs for indentation because you have not yet read Good Haskell Style by Ian Lynagh, then the following little Perl snippet may help you to easily convert your Haskell code:

• perl -e '($_ = join "",<>) =~ s/(\t)/ /g; print;'

If you are using TextMate you can easily use this snippet as a Filter Through Command…

Sources:

• Ian Lynagh post to the Haskell Libraries list.
• Good Haskell Style

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.

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...

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:

• Map
• Dictionary
• Lookup Table
• Associative Array

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.

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:

• Heap Datastructure
• Binary Heap
• Heapsort
• Heap – Chambers Dictionary Definition

The term “Hindley-Milner type system” is one I have read quite often only having had an intuitive understanding of what it means. Since every paper about Type Systems or some Functional Programming papers often use the term in such a way that one might get the impression that it is universally understood by everyone, I was firstly reluctant to ask the simple question:

• What is a Hindley-Milner type system?

But the simple questions are usually the interesting ones! When you write a program in an imperative programming language like Java, C, etc. the compiler depends on explicit type annotations in order to do its type checking. This may not sound particularily disturbing since a good programmer should always know the types of function arguments, return types, etc. Type ascriptions also serve as documentation. So what’s wrong with explicit type annotation?

1. It is tedious!
2. You do not always get it right!
3. It is tedious!
4. You do not always get it right!
5. ...

But what about languages like Ruby, Perl, PHP etc. where there is no need – or almost no need – for explicit type annotations? How do those languages infer the types of expressions, function parameters, variables etc. (e.g. Perl example ‘sub foo($) { my $arg = shift; }‘) In order to answer this question it necessary to distinguish between the following type checking strategies:

• Statically checked: Static type checking happens during compile time. It can be seen as a static approximation to the run-time behaviors of terms in a program.

• Dynamically checked: Dynamic or latent type checking occurs during run-time, where run-time type tags are used to distinguish different kinds of structures in the heap.

• Hybrid – statically & dynamically checked: Many languages like Java do extensive static type checking as well as some dynamic type checking during run-time (e.g. to support down casts (a.k.a. widening))

Thus ‘type inference’ and ‘type checking’ in languages such as Ruby, Perl, PHP etc. happens at run-time when all the expressions are evaluated. Even some language constructs in Java require run-time ‘type checking’. A language like Haskell infers and checks types statically – so you do not have to run a program to find out about possible type errors.

There is a lot of debate on what strategy is ‘better’ or ‘worse’, but hey, what about Hindley-Milner? So let others do the debating about the merits of language XYZ and its type checking strategy and let’s concentrate on the original problem.

Type Inference

Type inference is the ability to deduce the type of a value derived from the eventual evaluation of an expression. So we do not actually evaluate an expression to ‘infer’ its type (dynamic typing), but rather infer the type of a value before the expression which produces it is evaluated (static typing). How can this work? Well, if the compiler is able to recognize the eventual reduction of an expression to implicitly typed atomic values (e.g. 1, “string”, 1.3, False), it is able to type check and compile a program completely without type annotations. Now there are limits to this, but delving into those would be a bit too much for now.

• So what does Hindley-Milner stand for ?!

Finally we can answer this question! The common algorithm used to perform type inference is referred to as Hindley-Milner or Damas-Milner algorithm. So if you have a language with a Hindley-Milner type system, it basically means that the language can infer almost all types and you do not have to explicitly write type ascriptions. Of course you can still make type annotations where it makes sense for better readabilty. Hindley-Milner type inference will check if your ascriptions are correct and ensure that there are no type errors before you execute the program. In case of type errors it is even able to tell you what type it would have expected at the erroneous position. That’s pretty cool and very powerful indeed!

Sources:

• http://en.wikipedia.org/wiki/Type_inference
• Pierce, Benjamin C.. Types and Programming Languages (Chapters 1, 23)

It takes quite some time to acquire good programming skills! Just as no good craftsmen suddenly fall from heaven, no one turns into a good programmer over night.

There is a nice essay about this topic by Peter Norvig called Teach yourself programming in 10 years. Especially the part where Norvig says ”...Learn at least a half dozen programming languages. ...” is very true.

So don’t be a language fundametalist by sticking to the one and only programming language and paradigm you know – learn more languages, learn about other programming paradigms (e.g. declarative vs. imperative)! This will improve the way you code, design, reason, and understand programs.

While I am writing this, I really hope that the informatics curriculum at Informatics@JKU will change at least a little bit in order to accommodate more and better courses on programming languages and different programming language paradigms in general. By the way they also should improve their home page as well. It is in a very sad state and makes the uni look quite bad!

Sources:

• Teach yourself programming in 10 years [by Peter Norvig]

In order to find out about shared library dependencies the command ldd is used. Well, at least on every UNIX system I worked at, except on Mac OS X. There the command:

• otool -L

lists all shared library dependencies.