Imperative Programming:What is *Wrong*?

What is *wrong* with the imperative programming? That’s the question that came up in a discussion where I was part; the dicussion group comprised of people from diverse software background and most of them has their lineage to C or C++. The points that came up during that discussion were well spread over the day to day activities of the programmers working in various types of projects.

Actually if you see from a distance it is absolutely ok to write a piece of code in your favorite imperative language, but if you take some time and code the software in your favorite functional programming language it feels and looks better; of course your choice of functional programming language has to be good.

Side Effects

Side effects make lot of problems while coding in imperative languages. Say you have a program that runs into several functions and as imperative language like C does not support higher order functions (in true sense) your functions are dependent on what we know as *GLOBAL VARIABLES*(to preserve the global state). Lets assume that you set an error flag if something has gone wrong in some function. As each function is interlinked in producer-consumer relationship with each other, once a function has done its job you have to see whether there is any error set or not. So your code will be sprinkled with codes like this:

i = fn1();

if( !errorset())

fn2();

This is not only bad while typing but also an example how a programmer loose his ability to think. How? As our example goes if you do it in several files and several functions; one fine morning loose the intent to think what may go wrong in simple function which is just checking whether a file exists or not! And I can tell you this happens because this happened with me.

Other than this, think about the time that I spent error handling. People might say that this is because you are using a programming language which does not support better error handling mechanisms to help the programmer. I agree, but as we know the imperative programming languages will always depend on Hoare Logic, i.e. it will have the notion of pre and post conditions. If we see both the paradigms of programming (lambda calculi and Turing machines) depends on those conditions but pure functional programming does not have side effects as it does not change (although lisp programs can do that) the values of its parameter.

But when I code in lisp I know that if I need an output from one function to another I will using the first one as a higher order function to the later. Then the second function only need to know what it expected out of the calling function if something goes wrong in the higher function it can handle it then and there and end the execution flow gracefully. This brings me to next topic execution flow.

Execution flow: Where am I?

Yup! This is a nightmare for any programmer in the imperative programming world; a bunch of programmer I knew once wrote a simulation program for Intel 8085 microprocessor but after each cycle of execution they didn’t know from where the program exited. It used to exit with unhandled error each time in Windows. If you think who they were I can tell you I was in that group. It took us some effort to fill that gap.

Now you might say that boy that doesn’t happen in real world! Oh yes that does not happen but we always have way to complete the process and most of the time the process is return-return-return till you come to main and then do simple check up and clean up of your mess with memory and then die by returning 0. No problems with that but think that if an execution starts and you know from the first command line checking itself that the user has made a mistake but you still follow your way of closing after eating some good processor time.

But in lisp you can’t loose your track! Even if you want you can’t, simple. How? If you are creating a properly designed lisp code with functional style you will be calling functions on top of one another so it will go on till the boundary of your hardware! It may fail some times but you will not be loosing your track. Even in error without any extra effort from your side you will be getting messages like: “Debugger invoked on ….”! I say, it’s just cool.

LOC – Yeah the greatest enemy of code!

I think Steve has given enough reason in his post so I need not prove this. But yes if I look at my C code some times I cry! How much I have typed for so little. Take the famous, old and boring “Hello World” program. In C you have to type at least 5 lines. In lisp REPL it’s only “Hello World”. Even a fancy function will be 2 lines. So you save 60% of typing effort while working with “Hello world” program.

And as the saying goes with lazy programmer I feel good while I use my “TAB” key for auto complete in XEmacs.

It happens especially if you need to work with raw data. By the time I finish structure filling code in C, I bet will be able to complete a subset of other tasks like some parsing also.

The crux of the matter is doing more out of less. If this is not good enough for you rethink about becoming a programmer.

Macros

My first impression about C macros was, “Here is subject which I need to learn because I really do not know what is wrong with my code when I use them.” The best macro I have used in my C code:

# define PRINTLN printf(“\n”);

And believe me it worked wonderfully for me. People in that discussion never understood what I was talking about when I said “function returning macro” or “code writing macros”. Because they do not know what a power a macro can have if you are programming lisp.

(I can go on talking about macros but I should refrain as this is not a sub-topic but requires major effort and can span several posts.)

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.

Emacs Lisp: A Note of a Newbie

(Please Note that all the codes/commands are tried in x86 based system running in Windows XP and XEmacs 21.4.20)

I have been learning elisp for couple of weeks just before Steve Yegge came up with his blog on Emergency Elisp. It is a good introduction to a programming language which is bound to an editor (or the other way around?). His blog talks about the basics of elisp in a nut shell, although lot of people have pointed out mistakes in it, but I feel it must have helped people like me who are learning elisp or will do so in the future. Also if you have looked for elisp tutorials in Google you must have bumped on to “An Introduction to Programming in Emacs Lisp” or “Emacs lisp Tutorial” . The elisp manual is good for people who have played with the language for some time; but for people who want to start learning elisp it is may not be a good place to be.

So why am I writing this blog? I found no mention of buffers and windows related stuffs in Steve’s post; as a programmer I felt I should keep notes of my work (as I do in some of my blogs).

When we configure SLIME and Emacs we add some lines to our init.el file which reads some thing like:

(add-to-list ‘load-path ….)

So the first thing is how to inspect a variable in Emacs, C-h v will prompt for the name of the variable you want to check and as soon as you enter the name of the variable it shows you the content of it. Like if I have a variable foo and want to see what the value of foo is.

Similarly if we want to see the documentation of any function we can use C-h f and enter the name of the function to see its documentation.

But don’t be fooled by these “control h” stuffs as they are nothing but either elisp functions or commands which are bound to some key combinations and keymaps. One can make a function interactive with the user by a using a built in function called (interactive).

Buffers and Windows

Buffers are lisp objects which hold texts for future editing. So as soon as you start Emacs it starts in a buffer. The most famous buffer is *scratch* buffer. If you do not have any customizations or filename mentioned while opening Emacs, it opens in this buffer by default. Let’s check some buffer related functions.

Let’s try out a mini project, suppose I have to create a function which will create documents in a predefined manner. How do I do that? The format is as follows:

Author:

Author Email:

Company:

Abstract:

From there on the author will create the rest of the document.

(Note here that I am not going into a lot of details in this and please do take care of the details required before creating a real project.)

Here is a way how we can do it elisp (please feel free to comment if you have any other idea i.e. more lispy way of doing this).

Programmer, who has his lineage from C or Java or JavaScript, knows that if he has to output some string with values extracted from a variable he has to write something like:-

C: printf(“Author:%s”, auth);

Java: System.out.println(“Author:” + auth);

JavaScript: alert(“Author:”+auth);

Common Lisp: (format t “Author:~a~%” auth)

Same applies here also but we do the formatting as following:

(format "Author:%s " auth)

I will just quickly note what all the in build functions does and how I have used them.

1. insert: This function inserts a formatted string in to the current buffer.
2. newline: As the name suggest it appends a new line.
3. switch-to-buffer: This function switches to a buffer and displays the buffer.
4. create-file-buffer: This will create a buffer with the filename (if the buffer exists it appends some extras apropos) and returns that buffer.
5. save-buffer: This function will prompt the user to save the buffer.

(Refer to elisp manual for details of these function)

Here is the code:

(defun create-the-doc-template (auth &optional email company)

(insert (format "Author:%s " auth))

(newline)

(if (eq email nil)

(insert "Author Email:")

(insert (format "Author Email:%s " email)))

(newline)

(if (eq company nil)

(insert "Company:")

(insert (format "Company:%s " email)))

(newline)

(insert "Abstract:"))

(defun create-file-as-doc(filename Author &optional Auth-Email Comp)

(switch-to-buffer (create-file-buffer filename))

(create-the-doc-template Author Auth-Email Comp)

(save-buffer))

(create-file-as-doc "hello-emacs.txt" "samik" "samikc@gmail.com" "ABC")

(create-file-as-doc "hello-emacs.txt" “samik”)

Now once you execute the first call it should look like the following:

Keyboard Macro

The best thing about elisp is that it allows you to hack Emacs completely and you can record a keyboard macro and use it by using a set functions and variables.

The variable last-kbd-board macro holds the last macro that you have defined and execute-kbd-macro does repeat the last macro defined by you in the current line. This can help you build a function that will repeat the macro in vary large file.

(defun do-macro()

(interactive)

(execute-kbd-macro last-kbd-macro))

So that’s all for now…

Thanks for reading.