Tuesday, April 22, 2008

Closure

A closure can be a very deceptive concept that comes with programming languages like lisp, JavaScript etc. So what is a closure? Definition of closure from Wikipedia is like this:

“a closure is a function that is evaluated in an environment containing one or more bound variables.”

In closure we get an environment and a function in that environment. When the function gets evaluated it has the opportunity to play with the environment. In common practice we think that an environment is nothing but the state of execution of a program. Programs, as pointed out in the classic book “How to design Programs”, is variables plus functions. So we can say, in general, environment is nothing but current state of the variables.

How we create closures? Here is an example:

[1]> (let ((x 1))
(defun foo(n)
(+ n x)))
FOO

Here x is the bound variable which has a value 1 and this makes the environment for function FOO. FOO will always get x as 1 in its execution. When we call FOO we get:

[2]> (foo 3)
4

With this as our base let’s explore a classic example of closure. Yeah! The same old make-adder example, what I am talking about.

Here is the code for that:

[4]> (defun make-adder(n)
#'(lambda(x)(+ x n)))
MAKE-ADDER

[5]> (setf add1 (make-adder 1))
#

[6]> (funcall add1 2)
3

When we defined make-adder we created a closure with variable n in lambda function with its own variable x. As we call make-adder and store the resultant function in variable add1 we created a closure where we will add 1 to the passed argument. Now that’s OK but how can I use it? This question I faced from many. Here is my use case.

MOVE

I (with my friends) developed a simulator for Intel 8085 microprocessor in C. later I tried to redo the code in lisp and found a very interesting application of make-adder closure. By this time I got familiar with IA-32 and Intel family of 80x86 processors where the logic MOVE have not changed but the number of bits (or bytes) to move has changed to match processor register size and architecture. That’s the “Aha!” moment for me. I wrote a function that will create a move as per the bytes to move. Here is the code for that (I have a move function which takes from-reg, to-reg for register purpose and number of bytes to move):

(defun make-mover(n)
#'(move from-reg to-reg n))

This solved (I hope) my problem for backward (or forward) compatibility issues as long as Intel does not change its MOVE.

So now I can get MOVE8, MOVE16 and MOVE32 very easily. I should re-write the whole program like that starting from register class definition.

STATE MACHINE

In the beginning we found that closure has close relation with function and its environment. This fact intuitively gives us a ready made case for state machine implementations in closure.

Consider the following state machine; it has two states S0 (represented as 0) and S1 (represented as 1). Here is the logic that it performs, if the current state of the machine is S0 and input is 0 it remains in S0 else machine goes to state S1. If the current state of the machine is S1 and input is 0 it changes the state to S0 else it remains in state S1. This machine accepts 1 and 0 as input. Also note that this machine initializes at state S0.

Here is the code:

(let ((s0 0) (s1 1) (state 0))
(defun input-action(in)
(if (eq state in)
state
(if (eq state s0)
s1
s0))))

And here is two sample runs:
[19]> (list (input-action 0) (input-action 1) (input-action 0))
(0 1 0)
[20]> (list (input-action 0) (input-action 1) (input-action 0) (input-action 1) (input-action 1))
(0 1 0 1 1)

That’s all I have understood about closures. Let me know if something wrong or you have better idea of closure and its uses.

Thanks for reading.