Sergi Mansilla

Yahoo came up with YQL a few weeks ago, and I think it is a very interesting idea. It is basically a SQL-like language that allows developers to retrieve structured data from multiple Yahoo web services without having to deal with each service’s API particularities; the developer can query any service in a generic way, just like he would do retrieving rows and columns from a SQL database.

An example of YQL query to retrieve the 5 first results returned by the search engine with the keyword “pizza” would be:

SELECT title, abstract FROM search.web WHERE query="pizza"

which returns a response in the format that you specify (either XML or JSON) that includes some metadata about the query itself and the actual requested results in a format like this (JSON):

"results": {
    "result": [
    {
     "abstract": "Official site for the international <strong>pizza</strong> chain, with online ordering, etc.",
     "title": "<strong>Pizza</strong> Hut"
    },
    {
     "abstract": "<strong>...</strong> site for the delivery chain offering thin crust, deep dish, etc.",
     "title": "Domino's <strong>Pizza</strong>"
    },
    ...
    ]
}

As you can see it is a very intuitive way to interact with web services (if only they were not all from Yahoo) for everybody that knows a bit of SQL.

If you want to try other queries or see examples of its use with other services you can use the YQL Console.

Querying YQL with Google Web Toolkit

So how would we query YQL with GWT? As it turns out, very easily. I am going to create a GWT component that queries flickr through YQL and retrieves the first 9 occurrences related to the keyword entered in a textbox and presents them in a Grid, like the one on the left.

Authentication

YQL uses 2-legged OAuth authentication like most OpenSocial containers, so we will have to have this into account when making the request. Fortunately there are good OAuth libraries available for every language. In my example I will use the ones made by Google, available at http://oauth.googlecode.com. I copied them to the /public folder and I referenced them from the module xml file instead of loading them directly in the html, which is more GWT-ish.

When I browsed the web for OAuth libraries I stumbled upon Paul Donnelly’s blog, who made a simple Javascript function for processing the parameters returned by OAUth libraries in the fashion that YQL wants, so instead of doing it with pure Java I took advantage of the toolkit’s JSNI classes and I just made a dumb OAuth class with a single static container method makeSignedRequest that wraps Paul’s very slightly modified function so that it references the OAuth object properly.

Calling back

Note: This section is explained in much more detail at Dan Morrill’s JSON tutorial.

Now that we have an OAuth class that will deal with the authentication, we only have to worry about the actual communication. Before getting our hands dirty with it, I will explain a bit some particularities of YQL and GWT that are necessary to get the mashup working properly.

GWT doesn’t directly allow fetching JSON data from an external domain for security reasons (any JSON data is a Javascript object after all, and although it should be used only for data transport, it can contain executable code as well), so I will use a bridge method setup to fetch it from Yahoo’s domain.

When we send a request to YQL through OAuth, we send some important parameters with it: our personal YQL key and YQL secret (generated when we request a new application account), and the URL in which we specify the encoded query, the response format we want and the callback function name that YQL will use in its response. The request method looks like this:

public void executeQuery(String keyword)
{
    String callback = this.reserveCallback();
 
    // Generate a function in the page with the known name we just created
    flyqlr.setup(this, callback);
 
    // Encode the URL using GWT's |URL.encode| and replace remaining unencoded characters
    String query = URL.encode("select * from flickr.photos.search where text = '" + keyword + "' limit 9")
			      .replaceAll("'", "%22").replaceAll("=", "%3D");
 
    // Makes the request using OAuth, which calls our just created callback
    // and adds the response as a script to the page
    this.addScript(OAuth.makeSignedRequest(
    	flyqlr.Y_KEY, flyqlr.Y_SECRET, flyqlr.YQL_URL + "q=" + query + "&format=json" + "&callback=" + callback));
}

The first thing that the method does is to generate a unique name for our future function and pass it as a parameter to the setup static method, which is the JSNI “bridge” method mentioned above, and that looks like this:

public native static void setup(flyqlr f, String callback) /*-{
  $wnd[callback] = function(data) {
    f.@com.sergi.client.flyqlr::process(Lcom/google/gwt/core/client/JavaScriptObject;)(data);
  }
}-*/;

This method creates a new function inside the window object ($wnd in JSNI slang) named after the callback parameter. This function calls the Java method process with a parameter data which contains the JSON string returned by YQL. When we know that our callback exists in the window we can safely compose the query and make the OAuth request. Notice that the latest parameter of the request string is callback, which tells YQL services our callback function’s name.

The addScript method just creates a script tag and injects its argument as its content and appends the tag to the page which executes its contents straight away, thus executing our callback.

Processing the response

At this point we have the JSON data returned by the YQL server, passed as a parameter to our process method, which looks like the following:

public void process(JavaScriptObject jso)
{
    JSONObject json = new JSONObject(jso);
    JSONArray ary = json.get("query").isObject().get("results").isObject().get("photo").isArray();
 
    this.updateGrid(ary);
}

This method is pretty straightforward, it simply converts the JavaScriptObject to a JSON one so we can extract from it the specific information that we want in form of JSONArray and pass it to updateGrid, which renders the retrieved photos:

public void updateGrid(JSONArray ary)
{
    for (int i = 0; i < ary.size(); ++i)
    {
	JSONObject photo = ary.get(i).isObject();
 
	Image img = new Image
	    (   // Constructs the flickr image URL from JSON data
		"http://farm"+photo.get("farm").isString().stringValue() + ".static.flickr.com" +
		"/" + photo.get("server").isString().stringValue() +
		"/" + photo.get("id").isString().stringValue() +
		"_" + photo.get("secret").isString().stringValue() +
		"_s.jpg"
	    );
	img.setWidth("75");
	this.theGrid.setWidget((int)Math.ceil(i/3), ((i+1) % 3), img);
    }
}

updateGrid constructs the 9 element grid and composes the flickr pictures URLs out of the data that we extracted from YQL. We are done!!

Although I am not sure about using GWT to build a complete website, I love its potential for building independent small components that hook on any web page. Even with an example like the one above in which the request is not a direct RPC call from Java, AJAX is ridiculously easy to use from GWT, and it provides a whole set of widgets ready to use. Besides, there are very interesting and impressive addons to GWT like GWT-Ext which boosts its possibilities on the UI side. This, and the goodness of developing the whole thing in one single robust language (most of the time) makes it a very attractive option for building web front-ends.

flyqlr.java
OAuth.java
Download the whole example

I first read about the Solitaire algorithm in the novel Cryptonomicon, by Neal Stephenson. Being a geeky kid fascinated by computers I thought that it was a brilliant idea, but my curiosity didn’t go so far as to make me write an implementation of it (you can find a perl version in the book, which by the way I consider to be another great way to encrypt information).

Solitaire is a stream cipher created by Bruce Schneier and designed to be used with only a deck of cards. No electronic devices are needed and its security is intended to be military-strength; that means that even if the way to generate/decipher messages is manual and might look a bit rudimentary, ideally not even the most powerful government could ever decipher a message generated with Solitaire (although some potential flaws have been reported).

So after playing with F# lately, I decided to write some non-trivial code in order to see how it suits my coding style and habits, and yet another naive implementation of this curious crypto-algorithm was born.

Notes about the implementation

After the initial struggle learning the particularities of F# (which are basically the same as ocaml) I quickly felt comfortable with it. It’s a very versatile language, given that it allows the programmer to use functional and imperative programming at his own will, so the learning curve is not very steep. And although the functional approach should be used most of the time, sometimes imperative code is more convenient and can make some programmers with a C or Java background feel more in control. For an example, consider this snippet of code:

member s.KeyStream (c: char list) f =
    match c with
    |x :: xs  -> let mutable o = s.getOutput
                 while o = jokerA or o = jokerB do o <- s.getOutput;
                 (Convert.ToChar (((f x o) % 26) + 65) :: s.KeyStream xs f)
    |[] ->  [];

Here I am using a functional approach to go through a list of characters and apply a given function and some calculations to each one of them. The whole transformation is based on the value of the variable o, but I only want to use o if it is not equal to a joker value (you can read about the algorithm internals on the author’s page or in its wikipedia article), so I use a very convenient while block that does the job. Sure, it can be done with recursivity as well, but F# lets you choose what suits you better.
In this snippet I am also using one of the most powerful ideas of the functional world: pattern matching. As the name says, a pattern match takes an expression between the match ... with block and compares it against a set of rules which test the expression given and returns a result. The concept is close to the good old switch/case statement, but much more powerful, because it allows the programmer to use conditions, name binding and object decomposing in the rules. The net is full of examples and articles about it where you can learn how to use them effectively.

The code also makes a basic use of some of the different paradigms that F# allows. For example, it uses OO for the Solitaire class to take advantage of mutable variables (a clear deviation from functional pureness and as I said, one of the strong points of the language) so the same variable can be used when keying the deck and by the encryption/decryption methods, but I use global functions for card manipulation operations. Sure, there could be a Deck class that includes card manipulation methods, but as I said before, this code is just for my own experimentation purposes.

I borrowed some utility functions from Haskell Prelude (span, splitAt) to help me with string manipulation, although I am sure that there are dozens of Ocaml libraries that already have a version of them. I am lazy and I just implemented the ones I needed and knew from Haskell.

This implementation is not intended to be efficient and of course there might be better ways to write it, this code was only written for fun and to teach myself some F# discipline, so it is not written in the most optimal way, but in the clearest one. I would gladly accept suggestions of how to improve it. I feel like I just started scratching the surface of what can be done with F# and I can’t wait to unleash its real potential.

The code below is the working algorithm, and you can find the complete source code including tests here.


#light
#r "FSharp.PowerPack.dll"
 
open System
 
(* Utility functions *)
 
let getCharValue c =
    let alphabet = Seq.to_list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    (List.find_index (fun x -> c = x) alphabet)
 
(* Adds 'X' characters until the list has a length multiple of 5, as stated in
   Schneier's page *)
let rec mod5 (msg: char list) =
    if (List.length msg) % 5 <> 0 then mod5 (msg @ ['X']) else msg
 
let sanitize _string =
    _string
    |> Seq.to_list
    |> List.filter (fun c -> Char.IsLetter c)
    |> List.map Char.ToUpper
 
(* Functions borrowed from Haskell *)
let span p xs = (Seq.to_list (Seq.take_while p xs), Seq.to_list (Seq.skip_while p xs))
 
(* Splits a list into two lists at the position corresponding to the given
   integer *)
let rec splitAt n xs =
    match (n, xs) with
    |(0, xs) -> ([], xs)
    |(_, []) -> ([], [])
    |(n, x :: xs) ->  let t = splitAt (n-1) xs;
                      (x :: fst t, snd t)
 
(* Deck Manipulation functions *)
let jokerA = 53
let jokerB = 54
 
(* Moves down a card in the deck *)
let md (c:int) (d) =
    match span (fun x -> x <> c) d with
    | (y :: ys, [x])     -> y :: x :: ys
    | (ys, x :: z :: zs) -> ys @ [z;x] @ zs
    | (_,_) -> []
 
let md2 c d = md c (md c d)
 
let tripleCut deck =
    let tripleCut2 c acc =
        match acc with
        | []      -> [c] :: acc
        | h :: t  -> if c = jokerA or c = jokerB then [] :: [c] :: acc
                     else (c :: h) :: t
    let s = List.fold_right tripleCut2 deck [ [] ]
    [s.[4]; s.[1]; s.[2]; s.[3]; s.[0]] |> List.concat
 
let countCut index deck =
    match splitAt index deck with
    | (xs, [x]) ->  deck
    | (xs, ys)  ->  let split = splitAt (ys.Length-1) ys;
                    fst split @ xs @ snd split
 
type Solitaire() =
    let mutable Cards = [1 .. jokerB]
    member s.Deck with get() = Cards
 
    member s.getOutput =
        Cards <- Cards |> md jokerA |> md2 jokerB |> tripleCut
        Cards <- countCut (if Cards.[jokerA] = jokerB
                           then jokerA
                           else Cards.[jokerA]) Cards
 
        if Cards.Head = jokerB then Cards.[jokerA] else Cards.[Cards.Head]
 
    member s.keyDeck keys =
        Cards <- [1 .. jokerB]
        let keyArray = keys |> sanitize |> Seq.to_list
        List.iter (fun (c:char) -> s.getOutput |> ignore;
                                   Cards <- countCut (Convert.ToInt32 c - 64) Cards) keyArray
 
    member s.KeyStream (c: char list) f =
        match c with
        |x :: xs  -> let mutable o = s.getOutput
                     while o = jokerA or o = jokerB do o <- s.getOutput;
                     (Convert.ToChar (((f x o) % 26) + 65) :: s.KeyStream xs f)
        |[] ->  [];
 
    member s.Encrypt msg = s.KeyStream (msg |> sanitize |> mod5)
                                       (fun x o -> (getCharValue x) + (o % 26))
 
    member s.Decrypt msg = s.KeyStream (msg |> sanitize |> mod5)
                                       (fun x o -> let k = (getCharValue x) - (o % 26)
                                                   if k < 65 then k + 26 else k)
(* Unit testing *)
let vectors =
   [["AAAAAAAAAAAAAAA";"";"EXKYIZSGEHUNTIQ"];
    ["AAAAAAAAAAAAAAA";"f";"XYIUQBMHKKJBEGY"];
    ["AAAAAAAAAAAAAAA";"fo";"TUJYMBERLGXNDIW"];
    ["AAAAAAAAAAAAAAA";"foo";"ITHZUJIWGRFARMW"];
    ["AAAAAAAAAAAAAAA";"aa";"OHGWMXXCAIMCIQP"];
    ["AAAAAAAAAAAAAAA";"aaa";"DCSQYHBQZNGDRUT"];
    ["AAAAAAAAAAAAAAA";"b";"XQEEMOITLZVDSQS"];
    ["AAAAAAAAAAAAAAA";"bc";"QNGRKQIHCLGWSCE"];
    ["AAAAAAAAAAAAAAA";"bcd";"FMUBYBMAXHNQXCJ"];
    ["AAAAAAAAAAAAAAAAAAAAAAAAA";"cryptonomicon";"SUGSRSXSWQRMXOHIPBFPXARYQ"];
    ["SOLITAIRE";"cryptonomicon";"KIRAKSFJAN"]]
 
let rec test (arr:string list list) =
    match arr with
    |x::xs    ->    let key = x.Tail.Head
                    let correct_enc = List.hd (List.tl x.Tail)
                    print_endline("Testing vector: " ^ x.Head ^
                                      "\nwith key: " ^ key ^
                                      "\nshould output:\t" ^ correct_enc)
 
                    let cipher = new Solitaire()
                    cipher.keyDeck key
                    let enc = new String (List.to_array (cipher.Encrypt x.Head))
                    cipher.keyDeck key
                    let dec = String.sub (new String (List.to_array (cipher.Decrypt enc))) 0 x.Head.Length
                    print_endline
                        ("and it outputs:\t" ^ enc ^ "\ndecryption:\t" ^ dec ^
                        "\n[Encryption test: " ^
                            if enc = correct_enc then "CORRECT!]" else "FAIL!]")
                    print_endline
                        ("[Decryption test: " ^
                            if dec = x.Head then "CORRECT!]\n\n" else "FAIL!]\n\n\n")
                    test xs
    |[]       ->    print_endline "All tests Finished."
 
(* Command line parser *)
 
let _ = match Sys.argv with
        |[|_;"-test"|]      ->  test vectors
        |[|_;"-enc";_;_|]   ->  let cipher = new Solitaire()
                                cipher.keyDeck (Sys.argv.[3])
                                print_endline
                                    (new String (List.to_array
                                        (cipher.Encrypt (Sys.argv.[2]))))
        |[|_;"-dec";_;_|]   ->  let cipher = new Solitaire()
                                cipher.keyDeck (Sys.argv.[3])
                                print_endline
                                    (new String (List.to_array
                                        (cipher.Decrypt (Sys.argv.[2]))))
        |_  ->  print_endline("Usage:\tSolitaire -test\n\t" ^
                                  "Solitaire -enc text key\n\t" ^
                                  "Solitaire -dec ciphertext key\n\n")
                print_endline("Example: Solitaire -enc SECRETMESSAGE foo")

The great thing about F# is that is a member of the .NET family of languages, so it can interact with the .NET framework just as C# would. In the code above I am not using much of explicit .NET related code, but I definitely want to explore it…just imagine the potential uses of combining ideas like pattern matching with existing .NET objects. Cool.

Yes, I am blogging again. But this time I have a plan.

My last blog tried to cover too many things, from my life abroad, to ramblings on software engineering and even some poor attempts to deep thinking every other post. Well, you really can’t bite off more than you can chew, and that was too broad and disorganized to maintain it properly, so this time the theme of this blog will be quite specific: programming and sotware engineering (mainly), focusing on languages, techniques and my day-to-day development.

I already have some few articles prepared, and many ideas for future ones. Stay tuned!