Building Shindig 101

"Proxy" problem:


While most of the world in enjoying the freedom of non-proxy Internet some people (like me) are behind a proxy server. Whatever, to get Maven working behind a proxy you need to go to your Maven installation folder and edit the file settings.xml in conf folder. What do you put in there?

<settings>
.
<proxies>
 <proxy>
    <active>true</active>
    <protocol>http</protocol>
    <host>proxy.somewhere.com</host>
    <port>8080</port>
    <username>proxyuser</username>
    <password>somepassword</password>
    <nonProxyHosts>proxyhost.somewhere.com</nonProxyHosts>
  </proxy>
</proxies>
.
</settings>

Building Shindig - The canonical way:

Building shindig (I assume that you know how to get the code using Subversion) the canonical way is simple:

cd ~/src/shindig/
mvn

This should be enough for most of you but if you are unlucky like me. You may get variety of errors:

1. Too many unapproved licenses: 12


Some people get a different number (even 0 - see this mail trail: http://www.mail-archive.com/shindig-dev@incubator.apache.org/msg07718.html)


2. Test failure :

May be one of the most frustrating thing is the test failures. They are hard to find and resolve sometimes.


So the question is; what are the options that you can try while building Shindig (and if *something* goes wrong - the list is in no particular order):

1. Delete your .m2/repository folder and retry - This will download all the required jar files once more. If you have missed something in the previous go you may get it (due to downtime to some download location). This is important if you get "Missing Artifacts" kind of an error.

2. Try : mvn clean install [ This cleans old bad builds and gives you kind of a fresh start]

3. Checkout or update the code from the Shindig repo once more.

4. Update the code once more if the build fails badly as this can happen due to unintentional commit mishaps.

5. If only the test fails and you are not patient enough to debug, use the following to suppress the error:

 mvn -Dmaven.test.failure.ignore=true

6. If you are too brave you can even try:

 mvn -Dmaven.test.failure.ignore=true -fn

[This worked for me when I got *too many unapproved licenses : 12*]


all the failures are suppressed by this -fn it will *NEVER* fail the build.



So that's about it while building Shindig. Hope this helps - if you have any other way of doing this let me know.

Code and Data Equivalence

That code and data are equivalent is a common idea in common lisp. However any programmer who has started his programming in any language other than lisp may find this idea alien to him. This happened to me, and it took me some time to understand the concept. This post is all about my understanding about “code data equivalence” in lisp.

First of all what is code? Code is anything that can be executed in a computer. In other words code is what we write in a programming language. Code is as the text books suggest is a human readable representation of what computers going to execute. Like the famous hello world program that all of us has written at some point of our life.

Data on the other hand is something which will be processed by the code. So the code will execute on a data and data change from one execution cycle to another. Data can be given to a code from various sources, like input from a user, file or even a program or code. So in our mind there is a difference. For example take the example of a function which will add two numbers passed to it.

int add(int a, int b)

{

return a+b;

}

In mathematics we know that the operation summation will do *something* with two (or more) numbers and will return a result. This result also will be a number. So the operation of addition is important than that of the data that it operates on. This creates a difference of treating data and code. This difference is the underpinning of treating data and code as separate entities which is true for most of the programming languages.

But in case of lisp this is not true.

In lisp anything that comes to the REPL is s-expression. What is s-expression? Sexp or s-expression is defined in lisp as an atom or list. Atoms are number, string, character etc. So when a input or data come to REPL it evaluates that as any one these alternatives.

The code that we write in lisp is also s-expression. Now as in mathematics we know that:

If A = B and C = B so A = C.

For lisp:

CODE = SEXP and DATA = SEXP so CODE = DATA

QED.

Why lisp is *Unpopular*

Lisp is a great programming language which has lot of power; however it is far from being most popular programming language. If you see lisp from a distance you will find:

1. Orthogonal syntax

2. Very quick to learn the basics

3. Very power full when it is used in high level project

4. You write less code as it has most powerful macro system

But still lisp is not the language of choice. It is a fallacy of programming world. Why? This question has stumped me number of times.

This post is my attempt to understand why it is so.

Prefix notation

Lisp is a programming language where prefix notations are used extensively. Prefix notations are good for computer but not for human being. From very old age human civilization and its mathematics is built on top of infix notation. We comprehend mathematical expressions in infix. You can argue with educational system but you cannot ask to change the year old mathematical notation to help a programming language to be understandable. That is simply not possible. This seems to me a perfect road block for lisp and it has to survive with that.

It will not be out of the turn to tell you a story about my friend. She was looking at Practical Common Lisp, and told, “How do you write 4*3+6 in common lisp?”

I replied (in writing), “(+ (* 4 3) 6)”.

She looked at it and closed the browser which was rendering “Practical Common Lisp”.

Mathematics behind lisp

Believe it or not all programmers do not like mathematics. They lie in the pantry, in conferences, in blogs. But the truth is a handful among us really like mathematics and care about it. Moreover it is not necessary to have deep understanding of mathematics to develop programs, or to be a programmer for that matter.

But lisp is an exception to this idea. To have a fair idea about lisp you have to understand some mathematics, like higher order functions. To understand functional programming paradigm one have to devote some weeks to lambda calculus. If one does not understand this he can write programs in lisp but it will be distant from the lisp style. The very idea of Turing machine and lambda calculus is fundamental to computer science but at the real world of software development those ideas do not cross our mind. To be honest with everyone I learnt C programming language without any knowledge of both Turing machine or lambda calculus.

There are self educated programmers who are very good in their trade and they care a damn about those theoretical computer science topics.

So lisp (and proper lisp style) is beyond many programmers and the target audience is less.

Programming language politics

Politics is pervasive; programming languages are not an exception to it. Big corporation look for development environments which are well supported, backward compatible, developers are available, etc. This is true in all large organizations or profit making corporations. When you decide about writing software you try to find out a middle ground. Lisp is powerful, 100 java average programmers = 10 or 2 great lisp hackers, you write less code to get more out programming language – all of them so very true. But when I was asked, “Show me one problem that I cannot solve with Java/Ruby/C++/Python?” I knew as all of them are Turing complete, so there is no problem that cannot be solved by Java/Ruby/C++/Python.

Although you have to learn more lexical separator in those programming languages than lisp still lisp looses. This is *PLP* - Programming Language Politics, we have to live with it. People will reject our ideas of development in lisp and the reason will never be purely technical; rather techno-political.

Code – data Equivalence – Hard to understand

I said, “In lisp code is data and data is code”.

Ron said,”What?”

People do not understand code data equivalence, because they are tuned by other programming languages. Those programming languages are their bread and butter so the immortal suggestion of “Unlearn “is “Unreal”. This is the bottom line of any lisper. This is *THE BASIS* of lisp macros. And it is so away from all other brick-mortar programming languages that no one understands its power without coding for many months and many macros. I got the feel of the matter when I read first ten chapters of Paul Graham’s “On Lisp”. This adds to another stiff cliff in any newbie’s learning curve.

Macros

Lisp macros are different beast, a beast when under you command do wonderful job for you. As any other programmer, especially *I know all* programmer like me, need some time to understand that lisp macros are really different.

It took me couple of week to realize that, when I realized it I felt like a stupid school kid with all red score card who has been slapped by his father for his exceptional result. Then I understood,”Oh! Yeah lisp macros are different.”

It opened my mind about programming as whole. Like when I learnt lisp – I learnt map, list, mapcar and all other cool lisp techniques. Before my lisp journey I was struggling with C++ STL concepts, after I learnt lisp all the things fell into place.

But the point here is that lisp macros are the last challenge that one has to understand (if not master).

Run-of-the-mill programmers

In many places it has been mentioned that lispers are not *Run-of-the-mill* programmer. They are different (in some cases arrogant), may be programmer elite. But popularity of a programming language depends on the acceptability of the language not on its power. Natural languages evolve out of existing languages to a simpler but verbose form. The same is not true for programming languages. There is no programming linguistic tree which has a common root node for syntax or semantic or paradigm. Lisp’s elite status may be the singular disadvantage to the general programming cloud.

We all play the role of *run-of-the-mill* programmer in any given project while it comes to coding and debugging. So *run-of-the-mill* programmers are necessary for any project to succeed and sustain. If your target is not *run-of-the-mill* guys you are bound to lose one day or the other.

Undermining Microsoft Windows

Not many lisp software works properly in Microsoft windows. The lion share of desktop application runs on windows box, but many lisp apps do not work.

Lisper world over has to take up the challenge to support Microsoft version of all the application that they are going to release. The word support can be even this one liner: “I do not care about windows. If it works fine else just do not disturb me.” At least some who cares about Microsoft compatibility will not use your stuff in his software.

Undermining Microsoft is bad, because Microsoft to computers is like photosynthesis to trees – it is a necessary evil.

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.

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.

Arc in Windows

Arc was released on 29^th January; just one day back; I started working with it in Windows. How to use our Arc in Windows; here is a quick way to start.

First thing first go to http://arclanguage.org/install and read the notes there carefully. It is a very small and well written guide how to get started in Arc. However for windows the first thing you have to do is to download and install MzScheme first. So here is the step by step guide to your Arc setup in Windows:

1. Download Arc.
2. Unzip Arc in a directory I use c:\Arc0.
3. Download MzScheme version 352(for Windows) from http://download.plt-scheme.org/mzscheme/ . You will land to the latest release download page which version 372. Click on the other version link and select V352 (as arclanguage.org suggests the use of v352; so please follow the canonical way.)
4. Once you have MzScheme installer run it. I have used C:\Program Files\MzScheme as installation directory you can use your own directory.
5. Go to your MzScheme directory and run the command Setup PLT.exe from the command prompt. Watch out for the line which says something like this:

setup-plt: Collection search path is

setup-plt: C:\[some-directories]\Application Data\PLT Scheme\352\collects

6. Go to this directory and check whether the path exits or not and properly populated. If not then create the required directories and sub directories and copy the collects folder from your MzScheme folder.
7. Everything should be ready by now do a cd to your Arc folder and run the following command:

mzscheme –m –f as.scm

That’s it start hacking Arc. If you have any problem feel free to post a comment will try to answer as fast as possible.

Logical Nirvana – How Programming Languages and Our Thoughts Are Linked

A programming language can change the way you think about programming; this is true but not the whole truth. Most of us when we code we try to think about a problem and we try to figure out how to solve the problem in a programming language. I do not want reiterate the same example of how BASIC does not allow you to think about recursion blah, blah, blah; but what I want to point out here is that at the time of solving a problem we actually solve the problem in our mind first and then we start coding. At the time of coding we start thinking in a programming language not before that. If some problem can be solved by a human being it can be solved by a computer. It may be tedious to put the logic but it can be done. Like as we have programs which can play chess better than most of us. So this simply means we just map our logic, which we develop in our mind, to a programming language.

Now this mapping requires us to translate the problem in a computer language. Now for example if we need to do an operation which is very low level we can do it very easily. But if the operation is complex we need to do a lot of sub operations, so at the time of translating the logic to a computer action we need to give bridging of more fundamental statements.

Now how a programming language can help you in doing this mapping? Simple it will provide you operations which are close to your logical system. It might not match the exact logical unit that you have in your mind but it can significantly reduce the number of statements that you write in that programming language. So if a programming language allows you to do some job in 10 statements and another programming language allows you to do the same job in 3 statements then it is better to use the second programming language. Plain and simple! But this is not so simple in this world and that’s why we have programming languages which require at least 4 lines to print “Hello World!!!”, moreover those programming languages are so called *MARKET LEADERS*.

Now let us return to our discussion on programming language and thinking process. The problem of mapping get worse if you are working in a programming language which is vary far from your solution in your brain; then you have to start from your end (Top-down approach) or from the programming language end(bottom up) and bring these two things to a single point and then it should work. What we are trying here is building of higher order logic from existing logical system in the programming language. So end of the day we are doing nothing but mapping of two logical systems.

Here I feel that the greatest realization of every programmer is what we are trying, while programming is not only solving a problem but also understanding our logic; the logic which lies beneath our mind. So the question is if a programming language does not allow us to think beyond certain point should we continue with that or let our thought go to wildest of imaginations where the boundaries are endless with a programming language that has no limitations.

So let’s reach out for that logical nirvana.

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.

Evolution of Programming

The RISC architecture is good, as they say anything small and working is good! This is my fellow programmers is a philosophy of *nix*; how many years has gone by? Stupid thirty years and do not question it; because that’s the best idea we have got and we are following it. Doing great stuff, building systems on top of it, I agree. But has it ever came to your mind that why this is like THIS? Why we have to use the same old RISC for our computing? The answer is we have stopped innovating in the real sense. We now know that we need more data types, arithmetic operations and better instruction set to carry out an operation. But at the end of the day all we have is a *MOVE* or *STORE* or *LOAD* and we say that Lisp, Java or Ruby runs slowly. These programming languages are not close to low level and thus will take some time to actually execute it in our cute processors.

Tomorrow if we try to develop a programming language which is more higher level we will not be able to convince our bosses that this is the right way of doing things. Because they will tell us, “look at the performance man!” And an innovation will die. Once upon a time C was considered higher level language than machine language, yes true but you need to write a 20 lines of code to reverse a link list or worse link list is not a basic data types.

I do not blame any one but tell me is it fair to ask a student of computer science to write a link list reversal program in Java. I don’t think so. If you can declare link list as a data type and you have a method to reverse it please reverse it using that; and if your computer is taking more time to do that for link list of 10000 elements blame it on the computer not the programming language even if the C/C++ implementation is taking less time. This is because of the abstraction that this high level programming language is providing. C/C++ on the other hand is good because there is very low level abstraction in it and you have to build rest of the thing.

In programming world this is like saying to the programmer it’s my way or highway. So if the instructions set are evolved up to the level of say C then what happens? The magic starts then you can still program in C as now you still have a choice program in assembly language; but it will be better to choose a higher level language.

We have come from binaries to pneumonic to assembly, but we are long due for the next higher level let us just take the next step, and which programming language we should choose is up for debate…..or is it not clear?