Elastic Tabs

I was just reading Joel Spolsky's column and today he gave this link. It's a nice idea for IDE's. Instead of tabs or spaces just use elastic tabs. Go check it out.

Mihai

GWT from Intellij IDEA

This is nice. I don't know if a month has passed yet since Google gave the world the GWT (Google Web Toolkit) and already there is already a plugin allowing you to use it from inside Intellij IDEA. And to make things more interesting it looks like the plugin is written by their marketing guy (Alex Tkachman .. see the blog entry here). I watched the demo and it looks like a very good integration. I can't hardly wait to play with it in the next EAP.

And people are curious of why I like this product :-).

Mihai.

Semantics

Usually when defining a new programming language one will have to provide two items:
the syntax of the language and the semantics of the language. Now you might ask why do you need both things ? Isn't the syntax enough ?

Think about this: if I came to you and I give you a paper written in Klingon would you be able to read it ? (Star Trek hardcore fans would probably get a paper written in rural romanian :-)). In general the answer would be no. In order to read it you would need to know how to transform the Klingon phrases in English phrases (a language that you already know). You would need at least a Klingon/english dictionary. In order to do it properly you would also need to know the grammer rules of the Klingon language. The dictionay and the grammar rules are in fact a semantic of the klingon language with the english language as a target (one that the recipient knows!). In effect the semantic of a language will define the meaning of phrases written in that language. This is another reason why crypto works :-). When you get an encrypted message you really have no clue what is the meaning associated with that text you got. And you can deduce virtually zero information about the semantics starting from the text you have. The stupid cyphers usually have semantics embedded into the syntax or are too close to the actual target language (the one which is encrypted) and slip that info on carefull analysis.

You can define the semantics in more than one way (see here for a more detalied presentation of the formal semantics of programming languages). To put it short there are three big ways: translation, interpretation and using logical axioms. When you give a semantics using the translation method you actually writing the translation rules from the source langauge into a known target language (usually compiling C to ASM is doing something like this). When using the interpretation method you are effectively describing what it will happen for every source phrase with a target known system (usually assembler can be described like that). I really don't have a good idea of an example using the third approach so i will leave like that. But basically what it is happennig with the third approach is this: you can define axioms for every building block of the language and inference rules for every combinatorial building block of the language. The meaning of a phrase in the languages is the resulting meaning in the defined logic (probably XSLT is/can be defined using something similar).

That's it for today :-). See you next time.

Mihai

Problem: Detecting duplicated items in an array

And another problem :-).

Someone asked me to give him problems so that he can train for an interview. I gave him the problems from google posted here and in turn he gave me another one: You have an array of length n. It is filled with n random numbers between 0 and n-1. The task it to find out if any of them are repeated.

The trivial solution would be to sort the array and detect any repeated number in the sorted array. This one has O(n * log(n)) time complexity. We should be able to do better. Here is what i came out with after a little thinking.

• start with the first element of the array which has a value different from the index at which it is located. For int[] arr = {0, 1, 2, 3, 5, 4} i would start with the position 4 because the value of 5 is different than its index.
• take the value and go in the array at the position represented by that index. Look at the value from there. If the value is the same as that index we just found our duplicate. If not then remember the new value, put the old value in there and do the same.
• if the next value is the original starting position you have just arranged a subset of the original array in the proper place. select the next number matching the condition at step 1 if possible. If not then you are done, you have the array sorted and you also know that there are no repeted numbers in it.

The worst case complexity is lower than O(2 * n). In the best case and medium case probably you will find in less than n/2 operations but this is just a guess. You would have to apply some statistics :-) to find out exactly what is this in the medium case.

Mihai.

Velocity compiler again

I postes a while ago about my Velocity "compiler". There is another interesting problem in it: How do you handle internal macros?. In Velocity you can define macros which are pieces of reusable code. The problem is how do you translate that into a java class ? The solution would be something like a method call obviously (this is what I use right but it might be something totally different). But with a method call you have the typing problem :-).

You start from this:

#macro( macroName $macroParam1 $macroParam1);
## macro code here
#end

## and a macro call here
#macroName( $actualParam1, $actualParam2 );

and you should end up with something like:

protected void macroName(Type1 macroParam1, Type2 macroParam2) {
// function code translated from macro here.
}

// and a call here
macroName(actualParam1, actualParam2);

The problem is: how do you find out the Type1, Type2 parameter types?. It turns out that there are two approaces. Infer the type from actual calls and infer the type from the actual macro code. I haven't really thought about the latter so I will talk mostly about the first one.

I used this because i already had some code helping me do it. I used it to infer the type of an expression in a #set( $var = $value); statement in order to properly convert it InferredType var = value; statement. So what i ended up doing is this:
- visit the AST tree of the velocity macro
- do the translation for all the nodes which are not ASTDirective with the name of macro (this is how an internal macro is presented in a velocity macro).
- for every node not translated i'm putting in a queue and remember it for later.
- while processing the other nodes i look for callers of macros.
  - I infer the types for any parameters passed to the macro and keep them in a map in the generator.
- after the processing is completed I iterate the macros and build them as functions using the parameters types inferred earlier.

This one works reasonably well in most of the cases however there are cases in which it fails :-). It should be visible from the algorithm description and the solution to this problem too ..

Mihai.

Goooogle interview questions II

This is the follow-up I promised some posts ago for the search problem.

Last time I was hinting at a totally different algorithm which might solve the problem. It's quite interesting and fun but .. it doesn't work :-). It will not find the shortest fragment but a short fragment. I'll give the code later. For now here is a variation of the alg I posted which has the same complexity but it's different :-).

Remember that with the algorithm posted you would merge the index arrays while keeping score of the term each index belonged (coloring them as I said). After that you would start with the minimal valid sequence from either end and walk toward the middle of the complete array (by breaking the longest sequence and then rebuilding again with new data) until you would have the same sequence in either end. This will require you to have the original index sets in memory before starting the work. This might be ok in some cases but if the index arrays are big you might get them from a database or web service or something else as a stream. In this case you would start only from one end and do the same (find a valid seq, break it, find another valid seq .. etc) while keeping score of the shortest one so far. This can enable you to actually apply the alg while reading the index sets (if they are too big).

The other interesting solution is this:

• sort the shortest index array.
  
• for each index in this index array you would find the nearest index in the second array.
• with those two numbers you would compute the mean find in the third array the closest number to the mean. - now you will have a couple of candidates (the same amount as the number of items in the shortest index array). You need choose the shortest one.
  

It's a nice algorithm but it doesn't work completely. The counter example is real nice :-). However it is faster because the complexity is something like O(card(S1)) * (1 + O(log(card(S2)) + log(card(S3))) compared with O(card(S1) + card(S2) + card(S3))
as in the first algorithm. In some cases you might be content with the size of the solution it would find. I think is not that far off the real solution. In the case of 3 search terms they are even related :-).

Mihai.

Spellchecking :-((

I really need to learn how to use a spellchecker or at least read the post again before posting.

The trouble is .. In general I really don't have something worth of telling to other people and when i do i usually rush to tell them and i forget to follow the proper practices. The good news is i know about the issue and i'm trying to change the habit. In the meantime I'll ask the reader to bear with me and/or report the mistakes find if you think are bad :-).

Mihai