Sunday, July 27, 2008

Mousetrap in C language

Just for fun, and performances are horribles as well in new C version, performances are great until 5000 cards, so I need to remove some dust from my good old ANSI C book :D

New version, compatible with gcc compiler.
To create and use the executable, gcc Mousetrap.c

Then call the file Mousetrap 5, for example, to obtain 1,3,2,5,4
Works quickly until 5000 results, requires a monster PC for 1000000 Google limit (algo is still not perfect, but this can generate an entire deck, instead of getting only that index, for each index)

#include <stdlib.h>

int *perfectDeck(int cards);

int main(int argc, char **argv){
if(--argc){
*argv++;
int i = 0,
cards = atoi(*argv);
if(cards > 0){
int *result = perfectDeck(cards);
printf("%i", result[i++]);
while(i < cards)
printf(" %i", result[i++]);
free(result);
}
}
return 0;
}

int *perfectDeck(int cards){
int card = cards,
move = 0,
i = 0;
int *deck = (int *)malloc(cards * sizeof(int)),
*result = (int *)malloc(cards * sizeof(int));
while(card--)
deck[card] = card;
while(cards){
move = (card++ % cards--) + 1;
while(move--){
i = deck[0];
memmove(deck, deck + 1, cards * sizeof(int));
deck[cards] = i;
}
result[deck[0]] = card + 1;
deck++;
}
free(deck);
return result;
}



This is the old version, bad practices everywherem and no movements optimizations (ok, ok, I wrote it too fast)

#include <stdlib.h>

typedef struct {
int length;
int *index;
} Array;

Array new_Array(int length);
Array shift(Array deck);
Array perfectDeck(int cards);
void move(Array deck);

Array new_Array(int length){
Array result;
int i = 0,
*stack = malloc(length * sizeof(int));
while(i < length)
stack[i] = i++;
result.length = length;
result.index = stack;
return result;
}

Array shift(Array deck){
Array result = new_Array(deck.length - 1);
int i = 0,
length = result.length,
*dindex = deck.index,
*rindex = result.index;
while(i < length)
rindex[i] = dindex[++i];
free(deck.index);
return result;
}

Array perfectDeck(int cards){
Array deck = new_Array(cards),
result = new_Array(cards);
int i = 0,
count = 0;
while(i < cards){
while(count++ != i)
move(deck);
result.index[deck.index[0]] = count;
deck = shift(deck);
count = 0;
++i;
}
free(deck.index);
return result;
}

void move(Array deck){
int *index = deck.index,
last = index[0],
i = 1,
length = deck.length;
while (i < length)
index[i - 1] = index[i++];
index[i - 1] = last;
}

/*
int main(){
Array result = perfectDeck(5);
printf("%i %i %i %i %i", result.index[0], result.index[1], result.index[2], result.index[3], result.index[4]);
scanf("%s");
free(result.index);
return 0;
}
*/

Google Code Jam: Mousetrap in 4 languages - GAME OVER

First of all, I would like to thank the Google team for Code Jam opportunity, and its organization: AMAZING!

Yesterday I have lost my Round without a single commit.
This time I have not excuses, it was simply my fault.
I did not understand properly first two problems, or better, expected results, but I was sure the reason was my poor English knowledge, and I wouldn't be silly, asking silly questions (some question was silly enough, so, next time, I'll be less shy than this time).

Accordingly, since Code Jam is a challenge, I chose to solve the most difficult problem, the Mousetrap. First of all, because the problem, and the expected result, was so simple to understand, secondly, because it was the best one for points :geek:

Problem Analysis


Ok, we had 2 hours to analyse the problem, to find the best solution, and to commit results, and this time I did not even download the test, because I would like to be sure that my solution was good enough to solve the problem.

Count positions ... no, don't do it, count movements, no, do not count at all!


My first 3 versions of Mousetrap were so tricky, that no one worked as expected :D
After about one hour trying to find the perfect algorithm to know where each card has to be during the game, I realized that I was trying to solve them in a complex way (a sort of home made equation), and without results, instead of simply think exactly what was going on in the deck during the game.
Anyway, I wasn't able to finish the code, specially because my "perfect solution" was trying to destroy my CPU! So, honestly, for my brain and my knowledge, time was not enough to complete that task.

Brainstorming


My approach was simple: create the perfect deck!
Once we have a perfect deck, find positions is something extremely simple, since each number is, at the begin, a deck index itself minus 1 (i.e. 1,2,3,4,5 as indexes: 0,1,2,3,4), so once you have moved each card over indexes, you can find card positions simply using created array.

card = "5"
result[(int)card - 1] = ... moved card.

At this point, we need to create the deck, and nothing else.
The first version was based on movements, and removed cards, to know the position of each card in that index. A sort of tracing, using a simple function like this one:

function movements(card){
return 0 < card ? card + movements(card - 1) : 0;
}

In this way we can know that when we are looking for card N, we have removed N-1 cards beforfe, and moved movments(N-1) time other cards.
This was probably the right direction, but it was exponential, and results completely wrong ... and snce we had 2 hours, I though to change strategy.

The most simple, logical, and expensive solution at all


Try to imagine we have 5 cards, so the deck will be: 1,2,3,4,5
The sequence, during the game, will be this one:

12345 [card = 1, pos 1]
2345 // remove one, and count fr next card
3452 [card = 2, pos 3]
452 // remove one, and count for next card
524 // counting ...
245 [card = 3, pos 2]
45 // remove one ...
54 // counting ...
45 // counting ...
54 [card = 4, pos 5]
4 // counting ...
4 // counting ...
4 // counting ...
4 // counting ...
4 [card = 5, pos 4]

Above operation is exponential as well, but in my mind it was the best one ever to be sure about the result. That is why I started to play the game!

Mousetrap with JavaScript


When I realized that in that simple way the code was truly slim, I though about 2 possibilities: 1 - I am a f#*@in genius, 2 - There is something wrong, it cannot be that simple, I am an idiot!
Once I have created the code:

// JavaScript
function perfectDeck(cards){
for(var
deck = range(cards),
result = range(cards),
count = 0,
i = 0;
i < cards; i++
){
while(count++ !== i)
deck.push(deck.shift()); // move cards
result[deck.shift()] = count;// remove one
count = 0; // start counter again
};
return result;
};

// JavaScript Extra
function range(length){ // return an array with 1:1 index/value integers
for(var i = 0, result = new Array(length); i < length; i++)
result[i] = i;
return result;
};

// example
alert(perfectDeck(5))
// 1,3,2,5,4

I did some test, and I checked results in my minds, and those were expected. Well done?

Mousetrap, PHP implementation


At this point, I need to parse the input file, and to produce an output file.
Since the code was extremely simple, I have though about PHP, to be able to read the input, and produce the output to upload.

function perfectDeck($cards){
for(
$deck = range(0, $cards - 1),
$result = range(0, $cards - 1),
$count = 0,
$i = 0;
$i < $cards; $i++
){
while($count++ !== $i)
array_push($deck, array_shift($deck));
$result[array_shift($deck)] = $count;
$count = 0;
}
return $result;
}

Damn it, literally 1 minute to create my PHP perfectDeck version.
Now, lets do some test to be sure everything is correct ... ok, that's correct.
At this time, I read the problem again, and I realized that I was debugging with 3, 4, 5 or 7 cards, thinking that a deck could not have more than 15 cards (poker addicted!) ... well, things are a bit different, since limits are clear, and we are talking about a maximum of 5000 cards, and for the small input!!! :o

Python version


Since trying to generate the perfect deck with PHP, and 2500 cards, was extremely slow, I though that I could try to use another language, maybe faster, thanks to Psyco module.

from psyco import full
full()

// Python
def perfectDeck(cards):
deck = range(cards)
result = range(cards)
count = 0
i = 0
while i < cards:
while count != i:
deck.append(deck[0])
deck = deck[1:]
count = count + 1
result[deck[0]] = count + 1
deck = deck[1:]
count = 0
i = i + 1
return result

Of course, in this case Psyco cannot help that much, since the most expensive operation is with the deck, and not with math.

Need for speed, C# Mousetrap


As last chance, and since the code was producing expected results, I though about fixed Arrays, without a single scriptish operation.
Instinctively, I opened my visual C# Express Edition, instead of Dev C++ to create a C version ... maybe because it's long time I am not using them, but anyway, I know that using fixed length arrays I should not have speed problems at all.

// C# with fixed lengths
static int[] perfectDeck(int cards){
int[] deck = range(cards),
result = range(cards);
for(int i = 0, count = 0; i < cards; i++){
while (count++ != i)
move(ref deck);
result[deck[0]] = count;
deck = shift(deck);
count = 0;
}
return result;
}

// C# with fixed lengths - Extra
static int[] range(int Length){
int[] result = new int[Length];
for (int i = 0; i < Length; i++)
result[i] = i;
return result;
}

static int[] shift(int[] deck){
int i = 0,
Length = deck.Length - 1;
int[] result = new int[Length];
for (; i < Length; i++)
result[i] = deck[i + 1];
return result;
}

static void move(ref int[] deck){
int last = deck[0],
i = 1,
Length = deck.Length;
while (i < Length)
deck[i - 1] = deck[i++];
deck[i - 1] = last;
}


Good enough? NO WAY, speed is more close to Python than C, so I promised myself that next version of perfectDeck function will be written in C.
At the same time, it will never be enough fast, because big input as these limits:
T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K

This means that my code will perform a factorial 1000000 changes, so honestly, the next step, will be to download some code from the competition, and learn which algorithm is the most clever and simple, to perform this task, in my mind, and in my implementation, completely mechanical.

Conclusion


I like challenges, and this one was amazing. I have learned at least these things yesterday, and I hope next year, I'll be more prepared:

  • Code Jam is fantastic!

  • Do not choose the most difficult task only to be in the top 100, but read in every case all of them before you start to write a single line of code

  • Do not use mechanical procedures, but think about efficient algorithms

  • Do not focus in a code, that for more than 2 times produced wrong results, or simply it is too slow, because it means there is something wrong in the logic, or in the algorithm

  • Go back to school, because even if you are a senior programmer, you do not work for the N.A.S.A. and you do not deal, daily, with algebra, math, geometry, and related stuff



If you are still reading, thank you too, I only would like to share my Google Code Experience, and my perfect costly nightmare Mousetrap solution.

Kind Regards

Saturday, July 26, 2008

JXON - A little update loads of documentation

I have updated my lightweight JXON library right now, lightly improving them, and adding a consistent documentation for each method as well.

At this point, the last thing I could do about JXON, is to talk about what exactly is, and what is not at all.


JXON IS


  • An intermediate, well defined, layer between native JavaScript variables, and a generic page content (their representation inside the layout)

  • A fast and cross-browser JS to XML, and vice-versa, parser

  • A human comprehensive way to represent JavaScript Object Notation via XML using a natural, lightweight, and unambiguous, schema, that will make XSL files creation, manipulation, and maintenance, more clear and natural than ever, working over both XPath, and semantic data types nodes with optional keys for object members

  • A simple and crossbrowser global object, with few methods to transform JavaScript raw data into a valid (x)HTML layout page, or portion

  • An advanced, XSLT based, enterprise ready way to represent data in a generic browser, with possibility to re-use thousands of time the same XSL file, or choose which one should be loaded for that browser (device browser indipendent)





JXON is NOT


  • A JSON parser

  • An Ajax library

  • A template Engine


Indeed, JXON aim is to be easily integrated inside your library, or your own code.
You do not necessary need a JSON parser, but every famous client library has one, so you can still perform client / server interactions using that parser, if necessary, and putting JXON between the evaluated result, and the layout.
The load method principal aim is to assign the public xml property that will be the JXON XML node you need to transform. This means that you have no options to change both its syncronous nature, or to use them to send POST parameters, it is NOT Ajax, but you can use every kind of library or code to perform these tasks putting JXON, again, between these interactions and your automatically updated layout portion.
Finally, thanks to JXON, you could focus entirely about data, instead of data plus its layout representation, delegating latter task to one of the most related languages to do that: XSL, a dedicated markup template engine transformer.

JXON - In line JavaScript to XSLT Example Page

P.S. Above link uses an object instead of a regular layout, and of course, even if when you look at that extremely light page (1.24 kB without gzip), Google and generally every kind of search engine, is able to read those information.

Thursday, July 24, 2008

JXON - Lossless JavaScript to XML Object Notation convertion

It seems to be the time to talk about JavaScript template engines, and DocumentFragments, so here I am with my last idea: a JavaScript XML Object Notation transformer.

Introduction


There are a lot of ways to interact between the client, and the server, in a W3 friendly way, such Ajax, the classic remote scripting, Comet, and last, but not least, and probably first of all, XML. The latter "protocol" is one of the most flexible, compatible, and cross platform one you can find in the IT sector, in a word: universal.
Over XML we are loaded of different standards to transport every kind of data, which one should be compatible with browsers, parsers, and preferably with JavaScript DOM implementation as well.
One of the main limitations I have spotted about XML to JavaScript and vice-versa conversion, is the data type, usually lost, and the prolixity of JavaScript data representation.

JSON is great, but whtat's up if we destroy its nature?


The JavaScript Object Notation model, aka JSON, has been one of the most revolutionary protocol between the browser and server, thanks to its thin nature: completely non-redundant against the open and close XML tag style, that is able to make client server interactions faster than ever.
At the same time, JSON is not only about data transportation, it is about data, and data type transportation, so every server side language can receive an object, an array, and every string, number, date, or null, nested information, and this is great!
Some project aim, is to use JSON notation to transform common (x)HTML data into a JSON string, making things almost useless for daily applications.
As example, JSONML goal is to transport HTML over JSON, loosing a consistent portion of this protocol nature because of redundant informations between the client and the server (JSON aim is to transport data, and not its representation in the generic document).
Other libraries try to convert XML or (x)HTML to JSON, and vice-versa, using attributes like "@class", that make client side code usability close to zero

var info = eval('({"@class":"my-class-name"})');
info.@class // error!!!
info["@class"] ...

As I said, JSON is great, robably the best one, to transport data, not its representation, so, the point is: do we really need to put all those information inside a protocol born to be light and essential?

To loose, or not to loose


A common problem in daily XML to JSON and vice-versa transformation, is the data type. A number, is a number, as an array is an array, but XML data is inevitably stored as a string, so the final result, is that almost every XML to JSON parser maintain XML data representation, but looses original JavaScript object notation. The main purpose of JXON, is to maintain original JavaScript data type, using XML to represent them:

<element>
Boolean = <boolean>true|false</boolean>
Date = <date>YYYY-MM-DDTHH:II:SS</date>
Null = <null/>
Number = <number>N|Z</number>
String = <string>string content</string>
Array = <array><element-list/></array>
Object = <object><element-list key="element-key"/></object>

<element-list> = a list of precedent element

For a better explanation about what I am talking about, next example is a full JXON compatible XML node:

<jxon>
<array>
<object>
<string key="developer">Andrea</string>
<number key="age">30</number>
<array key="sites">
<string>webreflection.blogspot.com</string>
<string>www.devpro.it</string>
</array>
</object>
<object>
<string key="developer">Cristian</string>
<number key="age">24</number>
<array key="sites">
<string>mykenta.blogspot.com</string>
</array>
</object>
</array>
</jxon>

Where everything, could be represented in JavaScript, as a developer list, in this way:
[
{
developer:"Andrea",
age:30,
sites:[
"webreflection.blogspot.com",
"www.devpro.it"
]
},{
developer:"Cristian",
age:24,
sites:[
"mykenta.blogspot.com"
]
}
]

And converted to XML, and vice-versa, with a truly simple, and fast, parser.

JXON transformation? XSLT, of course!


The XSLT language, is (x)HTML dedicated, standard, and supported by a wide range of browsers. XSLT could be based on components, matches and templates for every kind of structure, or could be simply dedicated for a single piece of code.
The main advantage of XSLT, is that an XSL file could be easily cached via browser, or server, but it could be always used in the future, while the only thing that will change will be the data, and not its entire structure representation.
What I mean, if you still wondering them, is that we do not need layout informations inside JSON strings at all, since the only thing that we need, and that could change, is the raw data itself, and nothing else.
JXON goal is to completely separate useful JSON informations, from useless, redundant, pointless, layout informations inside JSON protocol itself, making interactions exremely fast, and XSL files re-usability similar to the same we use daily with CSS, to transport only what we need, and to transform them quickly, and in a W3 recommended way as well.

Not clear enough, yet?


So, as last example, I can directly show you what could be possible to do with JXON, and its cross browser implementation, having a look into this unofficial JXON Example page, where you can directly spot the idea, its implementation, and finally its page source code :geek:

Thursday, July 17, 2008

Google Code Jam, or better, how to feel a 100% idiot !

Update 2


Congratulations! The results of the Google Code Jam 2008 Qualification Round are now official, and we're happy to announce that you have advanced to Round 1

Cheers :D
-----------------------------------------

Update


Guys, I do not know what Google judges will think about him/her, but in my mind, the qualification winner, for Python language, is the user camrdale, currently in position 40 of global score grid.

That code is extremely clear (come on, that is Python, how can be different!), essential, and the logic is probably not the perfect one, but is so linear that you can understand the problem even without reading them.

Well done camrdale, and good luck for the contest :geek:
-----------------------------------------

Guys, honestly, I did not think about that kind of selection only to participate, bloody hell!

First of All, the selection started at 11pm, and since I am an employee, and an hard worker as well, I though: who care? I have 24 hours to partecipate.

This is not true at all, I have discovered only after an entire day of work, programming in front at two monitors, drinking 3 red stuff and having 2 coffee, that the classification, or the total score, is based on both results, and when you commit your result.

But who had time to read the task before? Not me, honestly!

This simply means that USA, and vampires a part, nobody could stay in the top of that list.

I was so newbye in this contest, that the instant I went in the page, after login, I started to read the task, downloading automatically the first example file. no way, bad choice as first step, so first task failed because of time, well done!

After that, I chose the second task.
I truly feel like an idiot because I still have not understand at all what the hell is the correct check to avoid trains conflicts. But I hope i will discover soon them, because I am sure somebody more fresh than me understand perfectly the task, and properly solved them.

The last one is probably the most simple one, logically speaking, but at 10:30PM and after 14 hours spent in front of my PC, I really do not know who I am, how can I remember correct geometry permutations?

One think in my mind: I am an idiot!

So thank you for the opportunity Google team, I am sure next year I will ask a week of holidays to participate in another contest like that.

Kind Regards

Wednesday, July 16, 2008

JavaScript Relator Object, aka unobtrusive informations

Have you never though about add, modify, or remove a generic information from a variable, and without changing variable itself?
This is all about what my last simple creation does.



Relator Object Concept


The main purpose for this object is to associate every kind of information, value, or function, into a generic variable, whatever it is, and without modifying its native state.
To obtain this result, I have used a 1:1 relationship between a stack that will contain every stored variable, and another one that will contain related objects.

Stack = [1, 2, 3];
RelatedObject = [{}, {}, {}];

// add a property
RelatedObject[Stack.indexOf(2)].description = "Number 2";

// remove a property
Stack.splice(0, 1);
RelatedObject.splice(0, 1);

// situation
Stack = [2, 3];
RelatedObject = [{description:"Number 2"}, {}];

Using above strategy we obtain 2 benefits:

  1. The Stack does not cause memory leaks

  2. both Stack and RelatedObject are alway as small, and fast, as possible





Related Object Code



var Relator = function(Array, Object){
// (c) Andrea Giammarchi - Mit Style License
if(!Array.indexOf)
Array.indexOf = function(value){
for(var i = 0, length = Array.length; i < length; i++)
if(Array[i] === value)
return i;
return -1
};
return {
get:function(value){
return Object[Array.indexOf(value)]
},
set:function(value){
var i = Array.indexOf(value);
return ~i ? Object[i] : Object[Array.push(value) - 1] = {}
},
del:function(value){
var i = Array.indexOf(value);
if(~i){
Array.splice(i, 1);
Object.splice(i, 1);
};
return this
}
}
}([], []);

I hope, and I suppose, the 3 methods API talks by itself.
set is used to create a relation, if this does not exists, returning associated object.
get is used only to get a relation or undefined, if this does not exist.
Finally, del, is used to delete the relation, reducing the Array size, and deleting related Object.



Some Example


Try to imagine that we are using a library, but we would be able to add any sort of info about them, or implement something for our purpose.

var jQueryMore = Relator.set(jQuery);
jQueryMore.details = "jQuery library";
jQueryMore.isCompatible = function(){
return window.$ === jQuery;
};

// in every other piece of code ...
if(Relator.get(jQuery).isCompatible())
alert("I am using the " + Relator.get(jQuery).details);
// I am using the jQuery library




Relator Performances


IE a part, since it still does not implement natively the old indexOf Array method, performance to set, access, modify, or delete related informations, are probably the best possible, closes to zero value.
We can test by ourself using 10000 stored relations, and accessing to the last one.

for(var i = 0; i < 10000; i++)
Relator.set("number " + i).description = "The " + i + " number";

time = new Date;
description = Relator.get("number " + 9999).description;
time = new Date - time;
alert([description, time]);




Conclusion


The Relator object is based on our own variables, and it is not a container, a register, or a IOC emulator, at all.
At the same time, to be able to relate an object with a generic variable (undefined included, as example), it needs to store them in the Stack.
This could be a problem for memory leaks, but only if we forget to use the del method, to remove the assigned, and protected, relation between our global scope whatever, and the internal object dedicated relation.
Applications? In my mind, this object could make a lot of stuff simpler than ever, specially in those case where we would like, for example, monitor variables, singleton or global instances, during our script life :)

Saturday, July 12, 2008

An alternative JavaScript development pattern

A common pattern to develop JavaScript libraries is to use different behaviours inside methods, and based on browser, or browser plus its version.
For about 80% of cases, these behaviours are Internet Explorer dedicated.
This approach is good enough, otherwise we could not have a wide variety of libraries to choose, but is this way to develop libraries the best one?

These are some pro concepts:

  • libraries could be usually merged into a single file, so we can add only one script tag, and for every browser

  • libraries maintenance or improvements are focused into one, or more, constructor, function, or method



The expected result is, usually, a method that is capable to understand which browser is running them, and what to do for that specific case.

// common libraries development pattern
function myGorgeusLib(){};
myGorgeusLib.prototype.sayHello = function(){
if(self.attachEvent)
attachEvent("onload", function(){alert("Hello")});
else if(self.addEventListener)
addEventListener("load", function(e){alert("Hello")}, false);
else
onload = function(onload){return onload ?
function(){onload();alert("Hello")} :
function(){alert("Hello")}
}(self.onload);
};

new myGorgeusLib().sayHello();

Is above code clear enough? If a browser implements attachEvent, use them, otherwise if it implements addEventListener, use them, otherwise use manual onload implementation.

If we would like to modify, for some reason, that method, there is only one "place" to do it, the method itself.
At the same time, every time we would like to use that method, the browser has to check 1 or 2 times which case is suited for its engine.

This concept introduces these side effects:

  • every method size is generally increased for every browser, and often only to make some task IE compatible

  • every method speed execution, is generally increased, because of useless, or necessary, checks to perform each time the method is called

  • every change inside every method, could cause side effects for other browsers, so we have to fix 3 to 4 times instead of once, because of possible problems

  • every changed method should be tested into every library supported browser, even if it worked perfectly with every one, IE a part



Lazy, or direct, method assignment


Some library implements lazy prototype assignment, so that method will be the best one, only after the first time we will use them.

// lazy method assignment
function myGorgeusLib(){};
myGorgeusLib.prototype.sayHello = function(){
myGorgeusLib.prototype.sayHello =
self.attachEvent ? function(){
attachEvent("onload", function(){alert("Hello")});
}:(
self.addEventListener ? function(){
addEventListener("load", function(e){alert("Hello")}, false);
}:
function(){
onload = function(onload){return onload ?
function(){onload();alert("Hello")} :
function(){alert("Hello")}
}(self.onload);
}
);
this.sayHello();
};

new myGorgeusLib().sayHello();

Since we could perform that kind of check directly during prototype assignment, in this case, above pattern, is completely useless.
On the other hand, doing lazy or direct dedicated assignment, we are using a better approach because:

  • method is specific for this, or that, browser, so its execution speed will be the fastest possible

  • if we need to fix that method, we can focus only into specific browser version. Accordingly, we do not need to test with every supported browser, every change we made, but only with one, or more, specific version


Code minifier maniacs, could think that in this way, and for each method that requires that strategy, the final size of the library could increase about 30%, and this is, basically, true.
So, at this point, we have the best method ever to perform that specific task, but not the best size. How could we solve this last problem?

An alternative library development pattern


Before I will talk about my proposal, we should focus on a simple, as useful, thing about libraries: modularity
What we do like about this, or that, library, is the possibility to include only what we need, to obtain the final result with smallest possible footprint.
In other words, we chose exactly what we need, and we load or use only them, without useless piece of code that could only increase our page size, with or without cache help.
A lot of libraries use this concept runtime, like Dojo, or directly during library generation, like MooTools.
This way to develop, mantain, and use libraries, is loads of benefits for both developers, and users.
At the same time, and as far as I know, nobody though to port this development pattern, to create each library "portion" a part.
This is an example of what I am talking about:

// alternative library development pattern
function myGorgeusLib(){};
myGorgeusLib.prototype.sayHello = function(){
addEventListener("load", function(e){alert("Hello")}, false);
};

// IE dedicated changes, separated file
myGorgeusLib.prototype.sayHello = function(){
attachEvent("onload", function(){alert("Hello")});
};

// if we would like to support really old browsers too, in a separated file
myGorgeusLib.prototype.sayHello = function(){
onload = function(onload){return onload ?
function(){onload();alert("Hello")} :
function(){alert("Hello")}
}(self.onload);
};


This is a benefits summary, about this proposal:

  • smallest library size ever, thanks to common standard methods used by the library itself (a sort of FireFox, Opera, and Safari dedicated version)

  • modular methods development, with separed files dedicated for one, or more, browser version (IE6, IE7, IE8), thanks to conditional IE standard HTML comments: <!--[if IE 7]><script type="text/javascript" src="library.IE7.js"></script><![endif]-->

  • "future proof", when IE will implement standard DOM or Events methods, and behaviours, we can reduce IE dedicated file size

  • single debug, modular updates. We changes only one, or more, file, instead of recompile, regenerate, redistribute, the entire library file

  • intranet friendly, update only library version for dedicated environment, if it uses only a specific browser


So why shoulld we use JavaScript to define library behaviour, instead of browser itself?
Anyway, this pattern completely brakes practices about script tags in a generic (x)?HTML page. But, at the same time, could be the key to solve a wide number of problems, starting from modern devices with possible memory limits for JavaScript files, up to library execution speed, the best possible, and maintenance, focused in a single browser, or a single browser version.
The best implementation could be a Dojo "progressive library load" style, where the core automatically knows which file should be loaded, depending on browser, or its version.
Finally, these are side effects about this pattern:

  • final and complete library size will be the biggest possible one, but there shouldn't be a case where a browser download every file, redefining N times one or more methods

  • more effort to develop an entire library using this way, if there are a lot of methods that are not compatible with every browser

  • probably something else, that I am not thinking about



Now, after this explanation, would you like to write your impressions? Cheers :)

Thursday, July 10, 2008

He wrote: I'd like to know your opinion about JS2 ...

... and here I am.

My opinion about ECMAScript 4 is not that simple to explain.

I would like to have a language, whatever it is, that is powerful, truly natively cross browser, and widely adopted from every kind of device.

It seems I am talking about ActionScript, since Flash Player respects, aproximatly 90%, my desires, but I am not.

I "come" from Macromedia world, as a Certified ActionScript 2.0 Developer (no design guys, only pure AS2 OOP), and I have used, for years, Flash as production environment.

Looking at the little "JS2 monster" they are creating, I could smile, thinking about problems I had for those years with an environment that would like to be compatible with both old and new code, loads of unresolved bugs, and never perfectly cross browser ... we just have them, it is JavaScript, with its numerous implementations.

At the same time, I would love to see JavaScript 2 power, in a bytecode based VM, but what I do not want, is a partial implementation of this new language, as I do not hope in a JS3 project at all ( Macromedia style, every maximum 1 or 2 years a new language, so that nobody was really skilled and nobody knew perfectly the environment and language features itself ... welcome Adobe, and its hybrid Flash player that could do more, but only with Flex ... but it is only about marketing, isn't it? )

After 10 years or more, we are still "discovering" patterns and practices for a language born so far ( today, as example, another post about prototypal inheritance, using bad practices to perform simple, and logical, tasks - this is the state of general JS knowledge, 2008 )

Furthermore, as far as I know, Microsoft invested a lot of effort for its SilverLight pearl, a technology that, after years, is not that far from what Adobe, and Macromedia before, has done during these web evolution days and for long time.

I think, and it is only my humble opinion, that MS will never implement natively in its browser an open source VM, which purpose is to make Web more standard, at least for development, and more powerful for everyone:

You want more for your browser? You want SilverLight!


We would like to have canvas ( fast graphic? SilverLight ), standard behaviors, libraries which size could be 1/3, removing every single line IE dedicated ( fast and easy development? SilverLight ) ... but we still have attachEvent, old Array methods, and we know what else.

So, definitively, if JS2 will be the key to write once and run everywhere, without 3rd parts plug ins, without strict usage licenses, with more speed, more power, and capable to run in every device, I cannot wait that day ... but I am pretty much sure, that it is not close as I hope.

What about solving problems with ECMAScript 3rd edition, fixing everything, and in every browser? A dream, or better, an utopia!

So let's start to learn, to develop, and to fix, a new language :geek:

Thursday, July 3, 2008

scary eval to create the most safe environment ever

Are you worried about Array redefinition?
Are you worried about eval function redefinition?
Are you worried about whatever you want redefinition?
STOP
With the incredible eval feature "discovered" few days ago, it possible to create the most safe environment ever for every kind of purpose, starting from JSON evaluation, arriving to total protected native constructors.


const safeEnvironment = function(A, B, D, F, N, O, R, S){
const Array = A,
Boolean = B,
Date = D,
Function= F,
Number = N,
Object = O,
RegExp = R,
String = S,
eval = function(String){
return self.eval("(" + String + ")");
};
return new function(){};
}(
Array,
Boolean,
Date,
Function,
Number,
Object,
RegExp,
String
);


With above piece of code you can evaluate every kind of script without to be worried about common XSS or evaluation problems.


eval("Array=function(){}; alert(Array);", safeEnvironment);
/*
function Array(){
[native code]
}
*/


Seems to be hilarious, isn't it? The most scary Gecko function let us redefine entirely an environment, using constants to create immutable values that will be present in the virtual sandboxed scope.

So, the paradox, is that with Gecko eval, we could create the perfect safe environment, that could be used for every purpose, starting from the NoScript stuff.

Please, help me to convince Mozilla staff that second argument is not dangerous and could make our code execution safer than ever, thank you!

Wednesday, July 2, 2008

SCARY EVAL ... and the "futuristic" solution

Planet Earth, Year 2000

eval("document." + myformName + "." + myInputName + ".value");



Satellite Moon, Year 2004

eval is evil, nobody should use them, "except for json evaluation"



Planet Earth 2.0, Year 2008
OMG somebody could penetrate my closures!!!


Web Reflection, few days later
First of all, it was in the MDC, so if everbody is surprised, it is because we did not read that page, or simply we did not try that code (please correct that page, the second argument is everything but not the same of with statement).

Secondly, please, DO NOT CHANGE THAT FEATURE!!!
What I mean is that JavaScript is an amazing language, where everything could be changed, thanks to its intrinsically dynamic nature.

If we are worried about this fake news:

  • we should worry, before, about XSS in our site (after SQL injections)

  • if we are sure about missed XSS possibility, we should be worried about external libraries

  • if we are sure about third parts libraries, we should be worried about JSON

  • if we are sure about external libraries and JSON interactions ... why on heart should we be worried about this historic feature?



The feature is present in Gecko, but hey, Gecko implements constants!!!
Another thing I could not understand, is why somebody opened a bug for a feature that could be AMAZING if used for our own purpose.

Code and closure introspections, protected method implementation, whatever I cannot imagine right now.

On the other hand, it is extremely simple to solve the problem using a basic constant declaration

// webreflection "from the space"
try{eval("const $eval=function(eval){return function($eval){return eval($eval)}}(eval)")}catch($){$eval=eval};


Now try to delete the constant, try to do whatever you want in FireFox, and if it will be possible to change that $eval behaviour with Gecko browser, that will be the only bug you should really fix.

With Best Regards,
your bloody evil propagator ( booh! )



Update
Since I am writing in the bug page, I think my example could be interesting to understand what we are going to loose when this feature will disappear:

// sandbox: redefined environment
var myEnvironMent = {
eval:function(script){
return eval(script);
},
alert:function(String){
(document.body || document.documentElement)
.appendChild(document.createTextNode(String));
}
};

// evaluate a script from a string or a textarea
eval("alert('Hello World')", myEnvironMent);

/* you cannot do this with a with statement
with(myEnvironMent)
eval("alert('Hello World')");
*/



// privileged protected methods in prototype
Protected = function(){
function _showMessage(message){
alert(this.name.concat(" say ", message));
}
return function(name){
this.name = name;
};
}();
Protected.prototype._ = function(method){
return eval("_" + method, this)
.apply(this, Array.prototype.slice.call(arguments, 1));
};

var p = new Protected("Andrea");
p._("showMessage", "Hello World");

These are only two quick examples, and I wrote them in 1 minute.
Now try to imagine what could be possible to do having such control over closures!