Blog.from.bz

jLambda: A jQuery plugin for succinct anonymous functions

Tue, 27 Oct 2009 00:00:00 -0400

Download
Production (YUI compressed, 448 bytes)
Development (1.3kb)

Motivation
jQuery has an elegant chaining syntax that allows much of its API to be expressed in a clear, succinct way. For example, the following code from the jQuery homepage code finds all <p> elements with the class neat. The class "ohmy" is added to each matching element and then show() is called, which causes each element to be displayed.

$("p.neat").addClass("ohmy").show("slow");

Many jQuery functions accept a function as a argument which is called after some action is performed. For example, the following code finds all elements with the class "foo" and tells jQuery to call the function 'clkCallback' each time such an element is clicked.


function clkCallback() {
    $(this).hide();
}

$('.foo').click(clkCallback);

These functions are often written anonymously:

$('.foo').click(
            function() {
                $(this).hide();
            });

Often one wants to register a callback function that calls another jQuery function (like in the above, where the goal is to call hide() on the clicked element). Javascript's verbose anonymous function syntax makes this difficult to do succinctly. Can we do better?

The Plugin: jquery.lambda.js

I've written a jQuery plugin which adds the succinctness of jQuery chaining to callback functions. Generally, the plugin adds the global function $l (lowercase L, for "lambda"), which "wraps up" a jQuery expression into a function that can be executed later. For example, instead of writing:

function() {
    $(this).hide().addClass('foo').css('color', '#fff')..;
}

The plugin allows you to write:

$l.hide().addClass('foo').css('color', '#fff')..;

This allows succinct expression of callback functions.

// Without plugin:
$('.foo').click(
            function() {
                $(this).hide();
            });

// With plugin:
$('.foo').click($l.hide());

Usage

By default, any expressions following $l are called with $(this) as the argument. The plugin also makes the jQuery $() function available. For example:


// Without plugin:
$('.foo').click(
            function() {
                $(this).hide();
                $('p').show();
                $('a').width(20);
            });

// With plugin:
$('.foo').click($l.hide().$('p').show().$('a').width(20));

More generally, calling:

$l.a().b().$('x').c().$('y').d().$('z').e().f().g();

is functionally equivalent to:

function() {
    $(this).a().b();
    $('x').c();
    $('y').d();
    $('z').e().f().g();
}

Supported Methods

All properties of jQuery.fn are available, as are some additional ajax methods (ajax, get, getJSON, getScript, and post). These ajax methods can be called with, i.e., $l.$.ajax().

The plugin also supports a special function called ret(), which controls the value returned from the generated function.

// returns 5 when called.
$l.addClass('x').ret(3).css('color', '#f00').ret(5).show();

Performance

From a size/download perspective, the plugin is only 448 bytes (when compressed with the YUI Compressor).

From a performance perspective, the cost of using jLambda will be proportional to the number of chained calls made to $l (but not the size of the document or the DOM tree). Since Javascript doesn't support dynamic getters (see PHP's __get or Python's __getattr__), the values from the jQuery.fn need to copied after each called to a "placeholder" function, to allow that function to at as a dictionary to be called.

Compatibility

jLambda has been tested with Firefox 3.0.14, Firefox 3.5.3, Google Chrome 3.0.195.27, Safari 4.0.3 (5531.9), IE 8.0.7600.16385

Announcing XMLegant for Python

Sat, 28 Mar 2009 12:10:48 -0400

I've written a Python version of XMLegant, which I released earlier this morning for PHP. The Python version was designed to be as compatible as possible with the PHP version, without unnecessarily abusing the language.

XMLegant (github, download latest as zip) is a tool designed to allow easy generation of XML.

To see how XMLegant works, let's take a simple example. Suppose we want to generate the following document:

<books>
    <book>
        <title>Title 1</title>
        <author>Author 1</author>
        <isbn>isbn 1</isbn>
    </book>
    <book>
        <title>Title 2</title>
        <author>Author 2</author>
        <isbn>isbn 2</isbn>
    </book>
    <book>
        <title>Title 3</title>
        <author>Author 3</author>
        <isbn>isbn 3</isbn>
    </book>
</books>

We can use the following code:

x = XMLegant()

for i in xrange(5):
    x.books.book().title("Title %d" % i) \
                     .author("Author %d" % i) \
                     .isbn("isbn %d" % i)

And to generate this document:

<a>
    <b>c</b>
    <b>d</b>
    <e>f</e>
    <b>g</b>
    <h>
        <i j="k"/>
        <l>
            <m/>
        </l>
        <n>o</n>
    </h>
<a>

We can use either:

x = XMLegant()

x.a.b('c')
x.a.b('d')
x.a.e('f')
x.a.b('g')
x.a.h.i['j'] = 'k'
x.a.h.l.m
x.a.h.n = 'o'

or:

x = XMLegant()

x.a() \
    .b('c') \
    .b('d') \
    .e('f') \
    .b('g') \
    .h() \
      .i('j', 'k') \
      .l() \
        .m('') \
        .getParent() \
      .n('o')

A walkthrough of a short example is available in the XMLegant for PHP post. Many more examples are available in demo.py. Also, XMLegant_Tests.py consists of a number of unit tests that may be useful as a guide.

Announcing XMLegant for PHP

Sat, 28 Mar 2009 00:18:00 -0400

Update: I've also written a Python version of XMLegant

While SimpleXML has made reading XML relatively painless, no analogous tool exists for generating XML from scratch. To fill this need, I've created XMLegant (github, download latest as zip).

To see how XMLegant works, let's take a simple example. Suppose we want to generate the following document:

<books>
    <book>
        <title>Title 1</title>
        <author>Author 1</author>
        <isbn>isbn 1</isbn>
    </book>
    <book>
        <title>Title 2</title>
        <author>Author 2</author>
        <isbn>isbn 2</isbn>
    </book>
    <book>
        <title>Title 3</title>
        <author>Author 3</author>
        <isbn>isbn 3</isbn>
    </book>
</books>

We can use the following code:

$x = new XMLegant();

for($i=0;$i<5;$i++)
    $x->books->book()->title("Title $i")
                     ->author("Author $i")
                     ->isbn("isbn $i");

echo $x->toXML();

And to generate this document:

<a>
    <b>c</b>
    <b>d</b>
    <e>f</e>
    <b>g</b>
    <h>
        <i j="k"/>
        <l>
            <m/>
        </l>
        <n>o</n>
    </h>
<a>

We can use either:

$x = new XMLegant();

$x->a->b = 'c';
$x->a->b[] = 'd';
$x->a->e = 'f';
$x->a->b[] = 'g';
$x->a->h->i['j'] = 'k';
$x->a->h->l->m;
$x->a->h->n = 'o';

or:

$x = new XMLegant();

$x->a()
    ->b('c')
    ->b('d')
    ->e('f')
    ->b('g')
    ->h()
      ->i('j', 'k')
      ->l()
        ->m('')
        ->getParent()
      ->n('o');

How does this work?

XMLegant uses PHP's overloading and the SPL ArrayAccess interface. This allows interception of calls to unnamed functions or member variables as well as subscript access to the object. Using this, we can construct an XML access through manipulation of these anonymous calls.

Take this code:

$x = new XMLegant();
$x->a->b->c->d = 'e';
$x->a->b['f'] = 'g';
$x->toXML();

Which produces this:

<a>
    <b f="g">
        <c>
            <d>e</d>
        </c>
    </b>
</a>

This code first starts with the root object $x.

$x->a is called, which looks for the most recently created a child. Since none exists, an a element is created and added as a child of $x.
->b is called, which looks for the most recently created b child of a. Since none exists, a b element is created and added as a child of a.
->c is called, which looks for the most recently created c child of b. Since none exists, a c element is created and added as a child of b.
->d is called, which looks for the most recently created d child of c. Since none exists, a d element is created and added as a child of c.
d = 'e' is called, which assigns 'e' as a text node of d.

The second line finds the already created a element, finds the already created b child of a, and then sets the attribute f of b to 'g'.

Many more examples are available in demo.php. Also, XMLegant_Tests.php consists of a number of unit tests that may be useful as a guide.

Sudo make me a sandwich stub code

Sun, 01 Mar 2009 12:14:30 -0500

On linux-based machines, save this as the file Makefile

.SILENT: 

me:

a:

sandwich:
ifeq ($(shell id -u), 0)
	echo "Okay"
	# Ordering code goes here
else
	echo "What? Make it yourself."
endif

From the directory in which that file exists, you can now type

make me a sandwich

(which does not work) and

sudo make me a sandwich

(which does). Actually making the sandwich is an exercise left to the reader (although Dominos now makes sandwiches).

Using Python and CSPs to Solve Sudoku

Sun, 15 Feb 2009 12:21:17 -0500

This post introduces Constraint Satisfaction Problems (CSPs) and shows how to use a CSP solver to easily solve instances of Sudoku problems. It assumes familiarity with Sudoku and Python.

Constraint Satisfaction Problems (or CSPs) are problems that involve a set of variables that can each take on some number of values. The possible values of each variable may depend on other variables in the set. A well-written overview of CSPs is available here.

A CSP can be represented as:

A set of variables
For each variable, a set of possible values that the variable can taken on (also called the domain)
A set of constraints. Each constraints limits the values some subset of the variables can taken on.

A CSP solver searches over the variables' possible values and produces a mapping from variables to values that satisfy the constraints of the problem.

Certain programming languages, like Prolog, naturally lend themselves to solving CSPs (here's an example of a Prolog program that solves the N-Queens problem). We could use Prolog to solve CSPs, but that would require learning Prolog (which can be difficult for those not familiar with declarative langauges) and would possibly make other integration difficult (for example, a Sudoku solver may be part of a larger web site, not written in Prolog).

Solving Sudoku (and other CSPs) with Python

To solve Sudoku we're going to use the python-constraint library. (Note for Debian/Ubuntu users: This is not the library installed when typing apt-get install python-constraint. You will need to download and install this package manually.)

We will be creating a function called SolveSudoku. It will be called as follows:

m = [
[0,2,0,0,3,0,9,0,7],
[0,1,0,0,0,0,0,0,0],
[4,0,7,0,0,0,2,0,8],
[0,0,5,2,0,0,0,9,0],
[0,0,0,1,8,0,7,0,0],
[0,4,0,0,0,3,0,0,0],
[0,0,0,0,6,0,0,7,1],
[0,7,0,0,0,0,0,0,0],
[9,0,3,0,2,0,6,0,5],
]

print SolveSudoku(m)

...which represents the puzzle:

Step 1

Let's define the function:

def SolveSudoku(m, N = 9):
    p = Problem()
    ...
    # TODO: setup variables and constraints
    ...
    solution = p.getSolution()
    ...
    # TODO: format and return solution

Problem() defines a new constraint problem. p.getSolution() searches for a solution. Since we haven't added any variables yet, it returns None.

Step 2

Now we need to define the CSP variables. I've decided to name the variables 0 through 81, where the top-left box is 0 and the bottom right box is 1. The first row consists of the variables [0,1,2,3,4,5,6,7,8], etc. To help with manipulation, we "flatten" the Sudoku board m.

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)
   ...
    # TODO: setup variables and constraints
    ...
    solution = p.getSolution()
    ...
    # TODO: format and return solution

Given the above example problem, mList becomes:

[0, 2, 0, 0, 3, 0, 9, 0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 7, 0, 0, 0, 2, 0, 8, 0, 0, 5, 2, 0, 0, 0, 9, 0, 0, 0, 0, 1, 8, 0, 7, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 7, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 9, 0, 3, 0, 2, 0, 6, 0, 5]

Step 3

To setup the variables, we loop over each item in mList. If the value is 0 (our placeholder for an unknown value), we call p.addVariable(i, range(1, N+1)), which says "The variable i can be any value from 1 through 10". If the value isn't 0, we add a variable whose only value can be the value specified.

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)

    # add variables
    for i in xrange(N*N):
        if mList[i] == 0:
            p.addVariable(i, range(1, N+1))
        else:
            p.addVariable(i, [mList[i]])

    # TODO: setup  constraints
    ...
    solution = p.getSolution()
    ...
    # TODO: format and return solution

Step 4

To add the row constraints, we can loop over each row and for each row, generate a list of numbers representing the variables in that row and then add the constraint to that list of variables. To add a constraint, we call p.addConstraint(constraint, variableList), where constraint is the constraint placed on the list of variables variableList. Conveniently, python-constraint provides the constraint AllDifferentConstraint for us, which simply says that every value in the list variables we provide must be different.

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)

    # add variables
    for i in xrange(N*N):
        if mList[i] == 0:
            p.addVariable(i, range(1, N+1))
        else:
            p.addVariable(i, [mList[i]])

    # row constraints
    for r in xrange(N):
        l = list(xrange(r*N,(r+1)*N))
        p.addConstraint(AllDifferentConstraint(),l)

    # TODO: setup  constraints
    ...
    solution = p.getSolution()
    ...
    # TODO: format and return solution

At each iteration of the loop, l is:

[0, 1, 2, 3, 4, 5, 6, 7, 8]
[9, 10, 11, 12, 13, 14, 15, 16, 17]
[18, 19, 20, 21, 22, 23, 24, 25, 26]
...

Running this code will produce a solution that has our initial values and unique values for each row. All that's left is adding the column constraints.

Step 5

Similarly, we add column constraints by generating a list of numbers representing each column:

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)

    # add variables
    for i in xrange(N*N):
        if mList[i] == 0:
            p.addVariable(i, range(1, N+1))
        else:
            p.addVariable(i, [mList[i]])

    # row constraints
    for r in xrange(N):
        l = list(xrange(r*N,(r+1)*N))
        p.addConstraint(AllDifferentConstraint(),l)

    # column constraints
    for c in xrange(N):
        l = list(xrange(c,N*N, N))
        p.addConstraint(AllDifferentConstraint(), l)

    # TODO: setup  constraints
    ...
    solution = p.getSolution()
    ...
    # TODO: format and return solution

Step 6

Adding constraints for the 3x3 grids is slightly more complicated, but still involves generating 9 lists representing the variables in each grid:

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)

    # add variables
    for i in xrange(N*N):
        if mList[i] == 0:
            p.addVariable(i, range(1, N+1))
        else:
            p.addVariable(i, [mList[i]])

    # row constraints
    for r in xrange(N):
        l = list(xrange(r*N,(r+1)*N))
        p.addConstraint(AllDifferentConstraint(),l)

    # column constraints
    for c in xrange(N):
        l = list(xrange(c,N*N, N))
        p.addConstraint(AllDifferentConstraint(), l)

    # grid constraints
    for i in xrange(9):
        grid = []
        startingRow = (i%3)*3
        startingCol = i/3*3
        for r in xrange(3):
            for c in xrange(3):
                grid.append((startingRow+r)*N+startingCol+c)
        p.addConstraint(AllDifferentConstraint(),grid)

    solution = p.getSolution()
    ...
    # TODO: format and return solution

Step 7

And finally, we can format the solution nicely by putting each row on its own line:

from constraint import *

def SolveSudoku(m, N = 9):
    p = Problem()

    # flatten list
    mList = []
    for r in m:
        for c in r:
            mList.append(c)

    # add variables
    for i in xrange(N*N):
        if mList[i] == 0:
            p.addVariable(i, range(1, N+1))
        else:
            p.addVariable(i, [mList[i]])

    # row constraints
    for r in xrange(N):
        l = list(xrange(r*N,(r+1)*N))
        p.addConstraint(AllDifferentConstraint(),l)

    # column constraints
    for c in xrange(N):
        l = list(xrange(c,N*N, N))
        p.addConstraint(AllDifferentConstraint(), l)

    # grid constraints
    for i in xrange(9):
        grid = []
        startingRow = (i%3)*3
        startingCol = i/3*3
        for r in xrange(3):
            for c in xrange(3):
                grid.append((startingRow+r)*N+startingCol+c)
        p.addConstraint(AllDifferentConstraint(),grid)

    solution = p.getSolution()

    if solution is not None:
        m = []
        i = 0
        for r in xrange(N):
            row = []
            for c in xrange(N):
                row.append(str(solution[i]))
                i+=1
            rowStr = ' '.join(row)
            m.append(rowStr)

        return '\n'.join(m)

    else:
        return None

And we have a Sudoku solver! The example program outputs:

6 2 8 5 3 4 9 1 7
5 1 9 8 7 2 4 3 6
4 3 7 9 1 6 2 5 8
8 6 5 2 4 7 1 9 3
3 9 2 1 8 5 7 6 4
7 4 1 6 9 3 5 8 2
2 5 4 3 6 9 8 7 1
1 7 6 4 5 8 3 2 9
9 8 3 7 2 1 6 4 5

Making it Succinct

We can make this program shorter by abusing both Python's syntax and readability:

from constraint import *
def SolveSudoku(m, N = 9):
    p = Problem()
    l = sum(m,[]) # flatten list
    [p.addVariable(i, [l[i]] if l[i] > 0 else range(1,N+1)) for i in xrange(N*N)] # load variables
    [p.addConstraint(AllDifferentConstraint(),list(xrange(r*N,(r+1)*N))) for r in xrange(N)] # row constraints
    [p.addConstraint(AllDifferentConstraint(),list(xrange(c,N*N, N))) for c in xrange(N)] # column constraints
    [p.addConstraint(AllDifferentConstraint(),filter(lambda x: (i%3)*3 <= x/N < (i%3+1)*3 and (i/3)*3 <= x%N < (i/3+1)*3, xrange(N*N))) for i in xrange(N)] # grid constraints
    s = p.getSolution()
    return '\n'.join([' '.join([str(s[j]) for j in list(xrange(i*N,i*N+N))]) for i in xrange(N)]) if s is not None else None

Conclusion

While we could have solved Sudoku directly, transforming Sudoku into a CSP allowed us to use an existing CSP solver to do the difficult work for us. If you come across problems in your work that appear to be CSPs, give a CSP solver a chance before reinventing the wheel.

Coming Soon: Sudoku's constraints can all be described using the built in AllDifferentConstraint(). A future post will describe how to define your own constraint classes in order to solve the logic puzzle KenKen.

Run command when saving file on Linux

Wed, 05 Sep 2007 14:25:50 -0400

I'm working on a LaTeX project and like to continually monitor the PDF output. Normally this requires saving the .tex file, typing "make" in the terminal and refreshing the PDF viewer. The "dnotify" command allows you to specify an action to perform when a directory changes. I'm using this to run "make" whenever I save the my .tex file.

dnotify /directory/to/monitor -e make -C /directory/in/which/to/run/make

It appears that the directory to monitor can be the same as the directory that make modifies (I had assumed if make modified the directory monitored by dnotify, dnotify would be called again, which would call make, which would activate dnotify, etc).