Closure II and some future thought

My last post about closure in my blog and my query in the comp.lang.lisp have created some interesting debate among lispers and my friends. They have sugested their views about my posts. Some of them said that it was required and some said “I do not care about closure”. All in all I felt good about it. At least some people took a notice about closure and what it means.



To begin the post I must correct one program from my privious post:

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

I was really busy with my work of late and could not find any time (or topic) to write. I am busy with javascript and I am very happy with that. So I feel that in next couple of blogs I will write about some of JavaScript. For this I will go back to my school days and write programs which are like stack, queue and linked list. So that I can keep up with my old habits; what is it?


Programming.

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.

On Parentheses

People think about lisp parentheses as most hard thing in the world. When I started learning lisp it was a bottleneck for me too. I used to think what you do with these parentheses? Why it is like this. But now when I have started feeling a bit confident about lisp parentheses I felt I should put a note for absolute beginners of the language.

Parentheses while coding lisp

While you are coding always use a lisp editor for your parentheses handling. Best option is Emacs or XEmacs. If you are using it in windows please install and configure your Emacs in Windows (for some idea you can see here). Understand that good editor (like Emacs) will not only help you in coding in lisp but will increase your speed of translating your idea into code.

Use good key combinations to move around the parentheses as s-expression. Do not waste your time with bad editors which does not support any lisp mode; the faster you unlearn (thoes editors) the better you will be in coding lisp.

Parenthesis while reading lisp codes

There is no parentheses in the lisp code when you are reading a code. Yes, it may sound crazy for anyone starting out in lisp but it is true. Here is an example showing the concept:

(defun show-file(filename)
    (let ((in (open filename :if-does-not-exist nil)))
     (when in
      (format t "~a~%" (read-line in))
     (close in)))

Here is what you get when you removed all the parentheses:

defun show-file filename
let in open filename :if-does-not-exist nil
when in
format t “~a~%” read-line in
close in

It reads like:

Define function show-file which will take filename as argument
Let in be the file handler with filename; if the file does not exist do nothing
When there is a file handler in “in”
Format output as each line in the file comes
And yes close the file “in” before quitting.

That’s all! I hope this will help.

A Small Mathematical Project

Some times back I received an invitation to join an online community on Diophantine equations and related mathematical group in my Orkut account. I did not join the group for quite some time as I am very irregular in Orkut. But at last I when I wanted to join the group it is no longer there, this group’s moderator, a student of Indian Institute of Technology, wanted to run the community as complete mathematical community, unfortunately he decided to close the group.

When I learned about Diophantine equations in little details, I felt that how about writing a small common lisp utility to get going in this field. There were challenges to do that and more for a person like me who likes to work on his own code rather than using library in hobby projects. This post is all about what I felt during that development. I made a point of writing some lines while coding. Not as a comment but as a thought process.

How can I create a set (list) of values starting from one number and ending at another number? This question came to my mind first and the solution is writing a function which will give me a list like that on demand. It is intuitive that the arguments in this function would be a starting number, an end number and an incremental element which will increment the starting number till the end number or less. Moreover Diophantine equation demands that variables needs to integers.

(defun diophantine-create-set(start end)
(loop for n from start to end
while(<= n end) collect n))

Once I got that I have to think how I can represent a Diophantine equation in common lisp. The first thing that I felt is this has to be small so it will be a two unknown argument equation not an n-unknown Diophantine. At this point my imaginary linear Diophantine looked something like: Ax + By = K

Here I have to get the constant values from the user. That is good enough but another step needs to be done in this, which re-writing the equation,

y = (K – Ax) / B

Once I got this form of the equation I can write something like:

(lambda (x)
(/ (- k (* a x)) b))

So now how do I do this? I have come with this macro:

(defmacro diophantine-equation (a b k s e)
`(mapcar #'(lambda(x) (/ (- ,k (* ,a x)) ,b)) (diophantine-create-set ,s ,e)))

Following are some evaluation of this macro:

CL-USER> (diophantine-equation 1 1 10 1 100)
(9 8 7 6 5 4 3 2 1 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 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
-37 -38 -39 -40 -41 -42 -43 -44 -45 -46 -47 -48 -49 -50 -51 -52 -53 -54 -55
-56 -57 -58 -59 -60 -61 -62 -63 -64 -65 -66 -67 -68 -69 -70 -71 -72 -73 -74
-75 -76 -77 -78 -79 -80 -81 -82 -83 -84 -85 -86 -87 -88 -89 -90)

CL-USER> (diophantine-equation 2 1 10 1 100)
(8 6 4 2 0 -2 -4 -6 -8 -10 -12 -14 -16 -18 -20 -22 -24 -26 -28 -30 -32 -34 -36
-38 -40 -42 -44 -46 -48 -50 -52 -54 -56 -58 -60 -62 -64 -66 -68 -70 -72 -74
-76 -78 -80 -82 -84 -86 -88 -90 -92 -94 -96 -98 -100 -102 -104 -106 -108 -110
-112 -114 -116 -118 -120 -122 -124 -126 -128 -130 -132 -134 -136 -138 -140
-142 -144 -146 -148 -150 -152 -154 -156 -158 -160 -162 -164 -166 -168 -170
-172 -174 -176 -178 -180 -182 -184 -186 -188 -190)

Looks fine till now but see what you get from the following evaluation:

CL-USER> (diophantine-equation 2 5 10 1 100)
(8/5 6/5 4/5 2/5 0 -2/5 -4/5 -6/5 -8/5 -2 -12/5 -14/5 -16/5 -18/5 -4 -22/5
-24/5 -26/5 -28/5 -6 -32/5 -34/5 -36/5 -38/5 -8 -42/5 -44/5 -46/5 -48/5 -10
-52/5 -54/5 -56/5 -58/5 -12 -62/5 -64/5 -66/5 -68/5 -14 -72/5 -74/5 -76/5
-78/5 -16 -82/5 -84/5 -86/5 -88/5 -18 -92/5 -94/5 -96/5 -98/5 -20 -102/5
-104/5 -106/5 -108/5 -22 -112/5 -114/5 -116/5 -118/5 -24 -122/5 -124/5 -126/5
-128/5 -26 -132/5 -134/5 -136/5 -138/5 -28 -142/5 -144/5 -146/5 -148/5 -30
-152/5 -154/5 -156/5 -158/5 -32 -162/5 -164/5 -166/5 -168/5 -34 -172/5 -174/5
-176/5 -178/5 -36 -182/5 -184/5 -186/5 -188/5 -38)

Now the main aim of diophantine equations is failing, as only the integer solutions are accepted as per Diophantine analysis. In the last evaluation we have some integer solution but this list has both integers as well as fractions. This to me is simply “Not acceptable!” Moreover I can bet that it will not be acceptable in mathematics community.

At this point of development I had to put some more code in my diophantine-equation macro, it has to check whether a solution is integer or not. I will map the list and create a list of solutions with integers if it exists. To achieve this I introduced another macro because I wanted to keep diophantine-equation macro as it is. Here is the macro:

(defmacro diophantine-solutions(a b k s e)
`(remove nil (mapcar #'(lambda(x)
(when (integerp x)
x))
(diophantine-equation ,a ,b ,k ,s ,e))))

Let’s see what kind of output I have from this macro:

CL-USER> (diophantine-solutions 2 5 10 1 100)
(0 -2 -4 -6 -8 -10 -12 -14 -16 -18 -20 -22 -24 -26 -28 -30 -32 -34 -36 -38)

Now as we have built this basic framework for Diophantine analysis, let’s put this to some test. I know that I may not be able to answer a lot of questions asked in Diophantine analysis. But this small framework can answer a basic question right now. The first question that is asked in Diophantine analysis is, “Are there any solutions?” of course I have to reframe the question as per my framework as “Are there any solution between the range that I have mentioned?” it looks something like this in the REPL.

CL-USER> (if (eq nil (diophantine-solutions 2 5 10 1 100))
nil
t)
T
CL-USER> (if (eq nil (diophantine-solutions 2 5 10 1 4))
nil
t)
NIL
CL-USER> (if (eq nil (diophantine-solutions 2 5 10 1 1))
nil
t)
NIL
CL-USER> (if (eq nil (diophantine-solutions 2 5 10 1 10))
nil
t)
T

This utility has only one function and two macros.

I hope you like this blog; however if you think that there is a better way (which I am sure would be) of doing some things that I have done here or if you find any bug please feel free comment on it.

Thanks for reading.

Disclaimer: This is a hobby project not for any production use.

Lambda Calculus and Common Lisp

Warning: If you do not like mathematics this post may not be interesting to you.

When we talk about lisp or any dialect of it we come across the term functional programming. So what is functional programming any way and where it all started? If you ever have thought about such things here is my small attempt to answer some very fundamental questions in functional programming.

So what are the functions? Here are some basics.

In mathematics functions is some kind of relation between two things. But wait a minute isn’t functions are some code snippet that does some tasks? After all we programmers know functions that way. Yeah, both are correct and they do not have any difference. Like a function, which increments a variable by one, can be represented in following way:

f(x) = x + 1

So we can write a lot of functions like this in mathematic and solve them for a value. However there was no such concept as function in the begging of computer science instead there were just Turing machines which used to change state to provide result and solve problems by means of its states; this is such a great system that it can solve all computational problems.

Then Alonzo Church came up with lambda calculus and revolutionizes the whole concept of representing and solving problems. He wanted to solve some mathematical paradox (if you want to know about them see here and here); unfortunately that was not solved but we got our base for functional programming.

I think its enough of history; let’s start what this post is all about.

Basic Notations

Here is how you can represent the previous function in λ calculus:

λx.x+1

And if we want to evaluate for x = 2 we write it as:

(λx.x+1)2

Now we can write the same in common lisp as:

((lambda(x)
(+ x 1)) 2)

Now functional calculus we have learnt another thing which is higher order functions. Higher order functions are nothing but functions whose arguments are also functions (I will not get into the evaluation debate here).

Like this:

Suppose we have a function f(x) = x + 1 and g(x) = x + 2 and we are calling f(x) as f(g(x)).

How is it going to be evaluated?

f(g(x)) = g(x) + 1 = x + 2 + 1 = x + 3

So how do we represent it lambda calculus?

(λx.x+1)(λx.x+2)

Now if we want to evaluate this for x = 2 we write it as

(λx.x+1)(λx.x+2)2

In common lisp we write:

((lambda(x)(+ x 1))

((lambda(x)

(+ x 2))2))

Free or Unbound Variable

“The variable X is unbound.”

How many times you have got this message in your REPL? This comes directly from lambda calculus; here is how.

Any variable that is not a member of any lambda expression is called a free variable and it does not have any effect on the evaluation of that expression. However in programs we cannot use such variable for evaluation. If we do so we get this error message.

In lambda calculus a variable in cases like this:

λx.(x * y)

Here the variable y is free. The same happens in common lisp.

((lambda(x)

(* x y))1)

Logical Stuffs

In programming we use logical operators every day, the two mostly(or *ONLY*) used of them are *AND* and *OR*. How lambda calculus does it?

Before I start I want to give the meaning of the following lambda expression:

λxy.xxy => λxy. if x then x or y.

And this expression is the *OR* function in lambda calculus. So we can write it in common lisp as:

(lambda(x y) (if x x y))

The *AND* function also look quite similar

Lambda Calculus: λxy.xyx

Common Lisp: (lambda(x y) (if x y x))

So that’s all about very ugly comparison of lambda calculus and common lisp. I know that I missed lot of things which include reductions and reduction strategies. But one can read about lambda calculus tutorials to get fair idea on this; here is my choice:

www.cs.chalmers.se/Cs/Research/Logic/TypesSS05/Extra/geuvers.pdf

www.utdallas.edu/~gupta/courses/apl/lambda.pdf

Thanks for reading.

A Tale of Two Loosely Typed Languages

---

Disclaimer: I love JavaScript and this blog is not a defaming blog for JavaScript.

---

We all know that JavaScript is a loosely typed language; there are advantages of being loosely typed. You need not to think about what will be the data types of a particular variable and work with that variable. But a newbie to a loosely typed language will miss a lot of details which is required to code in such a language. (As I am writing this I consider me as newbie in most of the cases in programming). But still this blog is all about the mistakes that we all make and learn from them.

If you are reading this blog I can safely assume that you have some interest in programming in languages like JavaScript, Lisp or Scheme which are strictly speaking examples of great loosely typed language. Albeit I have doubts in my mind about ECMAScript that it might not remain as loosely typed as now with its reserve words containing char, int, long, float etc. But nevertheless I will take presently implemented format of well good JavaScript which still allows me and other programmers to write code free from types.

The most important concept while programming in any loosely typed programming language is the understanding of how my function is going to behave on certain inputs. If the function is a pure function you need not to worry, however in WWW we do not write much of a code like pure functions. But even pure functions can behave absolutely insane if you allow them to do so. How? Here is a code for a function in JavaScript which takes two numbers as its arguments and adds them (If you do not know JavaScript you can click here for a tutorial).

function add(x,y) { alert(x+y); }

I call this function as add(4,5) and as expected it pops 9. Good now if I try to call this function like this add(“hello”,5) what am I suppose to get?

Let us now stop this for a moment and try the same function in Lisp, the function in Lisp should look like:

(defun add(x y) (+ x y))

Now if I call the function in Lisp like (add 4 5) it will evaluate to 9 but if I try to call this add function with “hello” and 5, we will be in the debugger saying something like ‘Argument X is not a NUMBER: “hello”’ (my Lisp is SBCL).

Now what happens in JavaScript it will pop you a message box saying “Hello5”. That’s right, the + operator in JavaScript does two things it adds in case of a number and it also concatenates strings and moreover when it finds a string in any side of it, it forgets the other job that it can perform and it just concatenates. That is ok for me a language can do that like Java does the exact same thing. So to be sure about what you want from your function you need to check your input for certain type before you do this addition operation.

In JavaScript I as a programmer has to make sure that all the arguments to the function are as I was expecting before I pass them to an operation. In our case it is addition. In Lisp we can we will use restarts using condition handlers. We need to understand here that first way is static checking and the second one is dynamic checking at the run-time. The importance of conditional restarts are more felt where we have to take care of more complex functions.

SLIME - How to Profile in Lisp

If you have worked on a fairly *BIG* project you must have heard people saying, "Let's profile it first." When I started lisp programming I was clueless about profiling a lisp code. This was fairly easy in other programming languages by the tools they provide; I knew how to profile C/C++ code with GCC compiler options but not for lisp.
Here I am going to explain how to profile lisp codes using SLIME.
Suppose you have a function:

(defun foo()
(format t "Hello foo"))

and you call it like:

(loop for n
from 1 to 1000
do(progn
(print n)
(foo)))

Now you have to find how much time foo has taken. Below are the steps for that:

• Run the command: M-x slime-toggle-profile-fdefinition and hit enter. It will ask you the function name you want to profile. Enter the function name (foo in our case) you want to profile.
• Now run the function; as in our example we will run the loop for getting more data.

• To see the profile data use command M-x slime-profile-report. This will show the profiled data in the format below:

seconds consed calls sec/call name
-----------------------------------------------------
0.015 587,712 1,000 0.000015 FOO
-----------------------------------------------------
0.015 587,712 1,000 Total

estimated total profiling overhead: .002 seconds
overhead estimation parameters:
0.0s/call, 2.03e-6s total profiling, 9.36e-7s internal profiling

There is profiling options for packages. For more details you can refer to SLIME Manual.

SLIME Setup for Windows

If you are trying to setup SLIME in Windows it is fairly a simple job now.

I have used SBCL version 1.0.6 and XEmacs 21.4.20 in this example.

Following are the steps that you need to perform for a minimal setup of SLIME:

1. Download and install XEmacs.

2. Download and install SBCL in a directory, say C:\SBCL.

3. Download and unzip SLIME in a directory, say C:\SLIME. Make sure you have the directory names noted correctly.

4. Edit your init.el file and put the following lisp codes there:

(setq inferior-lisp-program "c:/sbcl/sbcl.exe")
(add-to-list 'load-path "c:/home/site/slime-2.0/")
(require 'slime)
(slime-setup)

This is it you sould have the SLIME working for you. :-)

Defvar and Defparameter

Defvar and defparameter does the same thing as defining a variable but the difference is that in case of defparameter you have to initialize the variable with a value but in case of defvar you can define the variable but you can initialize it later. There is a catch here if you try to use a variable by defining it using defvar without initializing it, it will evaluate to unbound variable, and the unbound-variable slot for that variable will be set.

Recursion and Bottom up design

In Lisp you can go from simple to very complex solutions. This is possible because of REPL. If you start with something simple and add on top of that simple design you will end up in a better program.



Recursion is a phenomenon in Lisp as it can be used extensively (but should be used judiciously). I was just developing something which required a permutation calculation. Now we know that basic permutation is defined in mathematics as:

P(n) = n! ..... (1)

And permutation of r things from a set of n things is defined as:

P(n)(r) = n! / (n – r)! ..... (2)



And we can expand (1) as:



P(n) = n.(n – 1).(n – 2) …2.1

= n. P( n – 1)



So the following function can be used in Lisp:



(defun permut (x)

( if ( not( eq x 0))

( * x ( permut ( - x 1)))

( block nil ( return 1))))



And from equation (2):



P(n)(r) = P(n)/P( n – r)



We can write this general function as:



(defun permut-n-r(n r)

(/ (permut n) (permut (- n r))))



Here we have used the bottom up approach by defining the easier “permut” function first then moving to the “permut-n-r”.

A useful macro

When you return a (multiple) value(s) from a Lisp function you use either use return-from or return macro. Now how about this, if you have a macro which will look like:



(defun foo()

(return “foo”))



This can be useful as we can do away with all the “block” statements. The macro that I use for this purpose is fairly simple:



(defmacro xreturn(x)

(block nil (return x)))

I know that it has one limitation that it does not return multiple values but that's fairly easy for any lisper to figure out right. ;-)

Please do not ask me about the naming convention I followed. Any feedback in this will be more than welcomed.