Sunday, November 08, 2009

Going lambda/functional with m4

m4 is the GNU version of traditional macro processor. Even though it is a single pass macro processor, unlike cpp, it can also process the substitutions of a macro, we can define a macro to define another macro, and use the newly created macro, and so on. Thus, we can, in some sense, use m4 as a functional programming language.

Recursive version of factorial program is straightforward in m4:

define(`rec_fact', `ifelse($1,0,1,`eval'($1 * `rec_fact'(`eval'($1 - 1))))')
rec_fact(15)


We can also create non-recursive version in m4. Since lambda terms are essentially anonymous functions, we write m4 macros to create and destroy new pseudo-anonymous macro definitions. Following macro defines the Y combinator equivalent in m4.

dnl Thanks to Toby White (http://uszla.me.uk/space/essays/m4Y)

define(define(`Y_COMB', `dnl
pushdef(`recur',dnl
`pushdef(`y_anon',dnl
`$1''changequote([,])(['changequote([,])`changequote`]`$[]1'(``$[]1'')dnl
['changequote([,])'changequote`])changequote`dnl
(changequote([,])`$[]1'changequote)dnl
`popdef(`y_anon')')'dnl
`y_anon')dnl
pushdef(`y_anon',`dnl
recur(`recur')'changequote([,])(`$[]1')changequote`dnl
popdef(`recur')`'popdef(`y_anon')')`'dnl
'`y_anon')`'dnl


This essentially is a version of fixed point combinator given by Haskell Curry and is defined as Y = \lambda f.(\lambda x.f (x x)) (\lambda x.f (x x)). This is similar to recur(recur). \lambda x.f (x x) is implemented as $1(`$1') in y_anon.

The non-recursive version of factorial can be written as :
define(`ARG1', `changequote([,])`$[]1'changequote')dnl
define(`F_fact',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, dnl
``eval''(ARG1 * ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl


And now all we need to do to call this non-recursive factorial functions is:
Y_COMB(`F_fact')(5)


We can also define a sugar function named fact that expands to Y_COMB(`F_fact').

Not just tail recursion but we can also run any kind of general recursive program in non-recursive fashion:

define(`F_fib',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, ARG1,2,1, dnl
``eval''(``$1''(`eval'(ARG1 - 2)) + ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl
Y_COMB(`F_fib')(11)


Run the above with m4 -dV to get sequence of reductions, it helps a lot with debugging.

Note that data constructors are also actual functions in m4, and there is no built-in support for say tuples or lists. It is more lambda-ish than say Haskell-ish. We have to build all such structures ourselves. The evaluation scheme is not full-lazy.

Saturday, November 07, 2009

Pidgin : Log in invisible for Google Talk (XMPP/Jabber)

I am a big fan of pidgin, primarily due to it's configurability and plugin support. One of major turn-off people report around me is that pidgin does not support logging in as invisible with gtalk account. Not that I am a big fan of invisibility, I built a plugin that lets you do just that.

Not supporting neat 'sign on as invisible' for gtalk is basically due to lack of time and willingness on Pidgin developers' part. Not that they can't, they just don't want to at the moment due to some extra stuff gtalk uses/needs.

Installation instructions:

It is written in Perl, which means you need perl 5+, pidgin-perl and libpurple-perl packages.


On apt based systems (like Ubuntu), do (as root)
apt-get install pidgin-perl

looks like Ubuntu 9.10 has this built in.

on fedora and alike

yum install pidgin-perl

That should install all required packages, with dependencies.

Download and extract the plugin perl script.
Save it to your ~/.purple/plugins/ directory. That is, /home/{username}/.purple/plugins/.
If you find that hard, there is an install script included.

Usage:
Go to Tools->Plugins. Find 'Google Talk Invisible Plugin' and enable it.
Now, when you set your status as "Extended Away", you become invisible. Simple!

This is the pre-pre-pre-...-alpha release, which means I did not go through the trouble of activating the INVISIBLE status for gtalk accounts, and hijacked xa instead. I hope it is not a big mistake.

Update : there is a serious bug in this plugin. After you become invisible, you can not get updates to your contact list, and hence if you start pidgin with the plugin enabled in extended away mode, you may not see any online friends at all. I am working on it.