A detailed view of the lisp interpreter (contd...)

In the previous post, I had explained some part of the code for the interpreter. In this post I will first give an explanation for the lambda and label forms and then I will complete the explanation of the interpreter.

The lambda form

The anonymous lambda function has the form,

(lambda (x1 ... xn) expr)

All the xi's represent variables that may be used in the expression expr.

As such, the lambda function as given above is just an abstraction of a function. In order to do something useful with it, you have to execute it by providing it with arguments as,

    ((lambda (x1 ... xn) expr) a1 ... an)

The manner in which the lambda function is evaluated in lisp is by first evaluating all its arguments, i.e., all the ai's. Once all the arguments have been evaluated, the values returned are then bound to the xi's which are used as variables in the expression 'expr'.

An example of the lambda form evaluated in emacs,

    ((lambda (x y) (cons x (cdr y)))
             'a
             '(b c d))    ==> (a c d)

The label form

The label form is a special type of lambda form. While the lambda form is an anonymous function call, the label form allows one to name the expression and then use the name within the expression itself. This feature enables one to define recursive expressions.

The label expression is (label f (lambda (p1 ... pn) e)). It denotes a function that behaves like (lambda (p1 ... pn) e) with the additional property that an occurrence of f within e will evaluate to the label expression as if f were a parameter of the function. Here is an example.

    (label subst (lambda (x y z)
            (cond ((atom z) (cond ((eq z y) x) ('t z))
                   ('t (cons (subst x y (car z))
                             (subst x y (cdr z))))))))

The abbreviation for

 f = (label f (lambda (p1 ... pn) e))

is

 (defun f (p1 ... pn) e) 

Thus, we have,

    (defun subst (x y z)
        (cond ((atom z)  (cond ((eq z y) x) ('t z))
               ('t (cons (subst x y (car z))
                         (subst x y (cdr z))))))))

I have described what the subst function does and how it does it here.

Once again, the interpreter

The lines that are in bold represent the part of the code that I did not explain in the previous post.

    (defun eval. (e a)
      (cond
        ((atom e) (assoc. e a))
        ((atom (car e))
             (cond
                 ((eq (car e) 'quote)  (cadr e))
                 ((eq (car e) 'atom)   (atom (eval. (cadr e) a)))
                 ((eq (car e) 'eq)     (eq   (eval. (cadr e) a) (eval. (caddr e) a)))
                 ((eq (car e) 'car)    (car  (eval. (cadr e) a)))
                 ((eq (car e) 'cdr)    (cdr  (eval. (cadr e) a)))
                 ((eq (car e) 'cons)   (cons (eval. (cadr e) a) (eval. (caddr e) a)))
                 ((eq (car e) 'cond)   (evcon. (cdr e) a))
                 ('t  (eval. (cons (assoc. (car e) a) (cdr e)) a))))
        ((eq (caar e) 'label)
             (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a)))
        ((eq (caar e) 'lambda)
             (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a)))))

The lines in bold above represent three cases :

1. (car e) is an atom but is not any of the primitive functions
2. (car e) is a list and (caar e) is 'label
3. (car e) is a list and (caar e) is 'lambda

Let's see how the interpreter handles these cases.

1. (car e) is an atom but is not any of the primitive functions

   The code for this case is given below.

       (eval. (cons (assoc. (car e) a) (cdr e)) a)
   

   In this particular case, the function is a lambda form that is defined in the environment. So, we just obtain the value of the function and evaluate it on its arguments.
   
   An example:

   
       
       (setq e '(f '(b c)))
       (setq a '((f (lambda (x) (cons 'a x)))))
       (eval. e a)        ==>  (a b c)
   
       (assoc. (car e) a) ==>  (lambda (x) (cons (quote a) x))
   
   
   

2. (car e) is a list and (caar e) is 'label

   The code for the label form:

       (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a))
   

   The label form is transformed into a call to a lambda form since a label is really a lambda form. An example will help you understand,

   
   
       (setq e '((label firstatom 
                   (lambda (x)
                        (cond ((atom x) x)
                        ('t (firstatom (car x))))))
                   y))
   
       (setq a '((y ((z b) (c d)))))
       
       (car e)    ==> (label firstatom (lambda (x) 
                                 (cond ((atom x) x) ((quote t) (firstatom (car x))))))
   
       (caddar e) ==> (lambda (x) (cond ((atom x) x) ((quote t) (firstatom (car x)))))        
   
       ;;The modified environment
       (cons (list (cadar e) (car e)) a)
       ==> ((firstatom 
                (label firstatom (lambda (x) (cond ((atom x) x) ((quote t) (firstatom (car x))))))) 
            (y ((z b) (c d))))
       
       (eval. e a)
   
   

3. (car e) is a list and (caar e) is 'lambda

   The code for lambda form

       (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))
   

   The expression for a lambda form is transformed into another eval. call where the expression is (caddar e) and the environment is (append. (pair. (cadar e) (evlis. (cdr e) a)) a). Let's first have a look at the evlis. function

   
       (defun evlis. (m a)
         (cond ((null. m) '())
               ('t (cons (eval.  (car m) a)
                         (evlis. (cdr m) a)))))
   
   

   The evlis. function is used in the code for the lambda form. This function is given a list of expressions, 'm', as input and it returns a list of the results of evaluating each expression in the list.
   
   

   
       (eval. '((lambda (x y) (cons x (cdr y)))
                 'a
                 '(b c d))
              '())                           ==>     (a c d)
   
   
       (setq e '((lambda (x y) (cons x (cdr y)))  'a  '(b c d)))
   
       (setq a '())
   
       (car e)     ==>  (lambda (x y) (cons x (cdr y)))
   
       (cdar e)    ==>  ((x y) (cons x (cdr y)))
   
       (cddar e)   ==>  ((cons x (cdr y)))
   
       (caddar e)  ==>  (cons x (cdr y)) 
   
       (evlis. (cdr e) a)     ==>  (a (b c d))
   
       (pair. (cadar e) (evlis. (cdr e) a))     ==> ((x a) (y (b c d)))
   
       ;; Thus the environment has been modified
       (setq a  (append. (pair. (cadar e) (evlis. (cdr e) a)) a))     ==> ((x a) (y (b c d)))
       a     ==> ((x a) (y (b c d)))
   
       (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))     ==> (a c d)
   
   
   

References and Further reading

1. Paul Graham
2. About Lisp
3. John McCarthy's original paper on Lisp
4. Lisp history from the inventor/discoverer

A detailed view of the lisp interpreter

Ok, so here's the deal !!! Given seven primitive functions implemented in a way that can be called/evaluated in the standard lisp format (which I explain in the next paragraph), we can create an interpreter that is capable of understanding and running a few instructions which is equivalent in power to any other program that you can possibly write. When I say equivalent in power I mean that any program written in any other programming language can be re-written in this language, easily, with fewer bugs and more elegantly. The even more amazing thing about this is that the interpreter is itself written in the language which it recognizes.

The 7 primitive operators required are quote, atom, eq, car, cdr, cons and cond. You can look up their definitions in Paul Graham's complete article. The standard format of writing these functions in lisp is as follows,

1. (quote a1)
2. (atom a1)
3. (eq a1 a2)
4. (car a1)
5. (cdr a1)
6. (cons a1 a2)
7. (cond (p1 e1) (p2 e2) ... (pn en))

The above functions may be implemented in any language, C or assembly or binary. It just does not matter. What does matter is that they should be callable in the above format.

Auxilliary Functions

The auxillary functions given below are used by our lisp interpreter. Notice that they require only the seven functions mentioned above. However, we have this problem of the "chicken and the egg" when defining new functions. In order to define new functions you need to have an interpreter. But, in order to create the interpreter we need to define some functions. I do not intend to discuss how to resolve this problem right now but if you are impatient please have a look at an excellent discussion on this topic at comp.lang.lisp and this discussion.

I have shown how the functions cxxxr may be implemented in addition to the other functions described in "The roots of lisp".

    (defun caaar (a) (car (caar a)))
    (defun caadr (a) (car (cadr a)))
    (defun cadar (a) (car (cdar a)))
    (defun caddr (a) (car (cddr a)))
    (defun cdaar (a) (cdr (caar a)))
    (defun cdadr (a) (cdr (cadr a)))
    (defun cddar (a) (cdr (cdar a)))
    (defun cdddr (a) (cdr (cddr a)))

    (defun caddar (a) (car (cddar a)))

    (defun null. (x)
        (eq x '()))

    (defun and. (x y)
      (cond (x (cond (y 't) ('t '())))
            ('t '())))

    (defun not. (x)
      (cond (x '())
            ('t 't)))

     (defun append. (x y)
      (cond ((null. x) y)
            ('t (cons (car x) (append. (cdr x) y)))))

    (defun pair. (x y)
      (cond ((and. (null. x) (null. y)) '())
            ((and. (not. (atom x)) (not. (atom y)))
                   (cons (list (car x) (car y))
                         (pair. (cdr x) (cdr y))))))

    (defun assoc. (x y)
      (cond ((eq (caar y) x) (cadar y))
            ('t  (assoc. x (cdr y)))))

    (defun evcon. (c a)
      (cond ((eval. (caar c)  a)
             (eval. (cadar c) a))
            ('t (evcon. (cdr c) a))))

    (defun evlis. (m a)
      (cond ((null. m) '())
            ('t (cons (eval.  (car m) a)
                      (evlis. (cdr m) a)))))

Finally, the interpreter

In order to explain its workings clearly I will be splitting the explanation into two posts. In this post, I discuss how the seven primitive functions are evaluated. In the next post, I will describe the syntax and semantics of the label and lambda functions. I also intend to explain and illustrate how the interpreter handles the label form, the lambda form as well as user-defined functions in the next post.

The complete code for the interpreter is as given below.

    (defun eval. (e a)
      (cond
        ((atom e) (assoc. e a))
        ((atom (car e))
             (cond
                 ((eq (car e) 'quote)  (cadr e))
                 ((eq (car e) 'atom)   (atom (eval. (cadr e) a)))
                 ((eq (car e) 'eq)     (eq   (eval. (cadr e) a) (eval. (caddr e) a)))
                 ((eq (car e) 'car)    (car  (eval. (cadr e) a)))
                 ((eq (car e) 'cdr)    (cdr  (eval. (cadr e) a)))
                 ((eq (car e) 'cons)   (cons (eval. (cadr e) a) (eval. (caddr e) a)))
                 ((eq (car e) 'cond)   (evcon. (cdr e) a))
                 ('t  (eval. (cons (assoc. (car e) a) (cdr e)) a))))
        ((eq (caar e) 'label)
             (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a)))
        ((eq (caar e) 'lambda)
             (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a)))))

Note:- The eval. function takes as input two arguments 'e' and 'a'. The first argument is the expression to be evaluated while the second argument is the environment in which it is to be evaluated. To be more precise, the second argument is really an association list consisting of pairs of variables and their values.

Thus, the outermost skeletal structure of the interpreter is as follows,

    (defun eval. (e a)
      (cond
        ((atom e) (assoc. e a))
        ((atom (car e)) (expr-atom))
        ((eq (caar e) 'label)  (expr-label))   ;; For the label special form.
        ((eq (caar e) 'lambda) (expr-lmbda))   ;; For lambda special forms 
      )                                        ;; End of the outer cond form.
    )                                          ;; End of function definition.     

As you can see the outermost structure of eval. consists of a single cond form containing four conditions. In this post I describe and explian only the first two conditions. The other two will be explained in a later post.

• The first condition checks if the expression is an atom. If it is, then the expression is just a variable and thus eval. simply returns the value bound to the variable in the environment/association list 'a' using the assoc. function.
• If the expression 'e' is not an atom, then, it checks if the 'car' of expression is an atom. The car(first element) of an expression is an atom precisely when it is either a primitive function or any other user-defined function. If this condition is true then the interpreter evaluates "expr-atom" that has been represented in italics in the code above. It is a placeholder for the actual code.
• The third condition checks if the expression 'e' is a label form.
• The final condition check is for the lambda form.

Now, let me give you a small example to familiarize you with the way in which the interpreter works. Please note that all the functions are being evaluated inside emacs.

    (eval. 'x '((x  "Hello World!")))   ==> "Hello World!"


;; or another way to obtain same results

    (setq  e  'x)
    (setq  a  '((x "Hello World!")))
    (eval. e   a)    ==>    "Hello World!"
 

In the above code the expression was set to 'x and the environment of the expression was set to the association list '((x "Hello World")). In the first piece of code it was set implicitly. However, in the last three lines the settings were provided explicitly and the function call was made as (eval. e a) . The reason for providing settings explicitly is that it really helps in breaking up the code to get a clearer insight into how the code really works.

    (setq  e  'x)
    (setq  a  '((x "Hello World!")))

    (atom e)      ==>  t        
    (assoc. e a)  ==>  "Hello World!"
 

Thus we can clearly observe that the assoc. function is used in eval. to look up the values of the variables.

Now, let's have a look at the code for expr-atom when the first element of the expression is an atom.

    (defun eval. (e a)
      (cond
        ((atom e) (assoc. e a))
        ((atom (car e))
                 (cond
                     ((eq (car e) 'quote)  (cadr e))
                     ((eq (car e) 'atom)   (atom (eval. (cadr e) a)))
                     ((eq (car e) 'eq)     (eq   (eval. (cadr e) a) (eval. (caddr e) a)))
                     ((eq (car e) 'car)    (car  (eval. (cadr e) a)))
                     ((eq (car e) 'cdr)    (cdr  (eval. (cadr e) a)))
                     ((eq (car e) 'cons)   (cons (eval. (cadr e) a) (eval. (caddr e) a)))
                     ((eq (car e) 'cond)   (evcon. (cdr e) a))
                     ('t  (eval. (cons (assoc. (car e) a) (cdr e)) a))
                 )       ;; End of inner cond form and expr-atom
         )               ;; End of the second check of outer cond 
        (third-condition)       ;; The label check 
        (fourth-condition)      ;; The check for the lambda form 
       )
    )
    

Now, for the remainder of this post I will be talking about expressions of the form

 e = (a1 a2 ... an)

where the first argument of the expression, a1 = (car e), is an atom. Let's see each case one by one, with examples.

1. quote

       (setq e '(quote Works!!!)) 
       (setq a '())    ;;We don't need an environment for quote 
       (eval. e a)     ==> Works!!!
       
        ;; Works!!! But, how?    
       (atom e)        ==> nil   ;;The first condition (in outermost cond) fails 
       (atom (car e))  ==> t     ;;The second condition (in outermost cond) succeeds 
       
       (car e)                ==> quote
       (eq (car e) 'quote)    ==> t
       (cadr e)               ==> Works!!! ;;The value of the expression (cadr e) is returned 
   

2. atom

       (setq e  '(atom x))
       (setq a '((x 1)))
       (atom (car e))     ==> t    ;; Is atom an atom? Yes, it is !
       (eval. e a)        ==> t    ;; And x is an atom too
   
       ;; How?
       ;;Since expression for atom is (atom (eval. (cadr e) a))
       (cadr e)                   ==> x
       (eval. (cadr e) a)         ==> 1
       (atom (eval. (cadr e) a))  ==> (atom 1)    ==> t
   

3. eq

       (setq e '(eq x y))
       (eval. e '((x 1) (y 1)))   ==> t
       (eval. e '((x 1) (y 2)))   ==> nil
   
       ;; Expression for eq is (eq   (eval. (cadr e) a) (eval. (caddr e) a))
       (cadr e)      ==> x
       (caddr e)     ==> y
       (setq expr1 (eval. (cadr e) '((x 1) (y 1))))  ==> 1
       (setq expr2 (eval. (caddr e) '((x 1) (y 1)))) ==> 1 
   
       ;;Thus,
       (eq  expr1 expr2)  ==> t
   
       ;;While,
       (setq expr3 (eval. (cadr e) '((x 1) (y 2))))  ==> 1
       (setq expr4 (eval. (caddr e) '((x 1) (y 2)))) ==> 2
   
       ;;And hence,
       (eq  expr3 expr4)  ==> nil
   
   

4. car
   
   Notice the recursive call to eval. where the remainder of the expression is evaluated in the environment 'a' and the car of the resulting list is returned.

       (car  (eval. (cadr e) a))
   

5. cdr
   
   Similar to car but the value returned is the rest of the list excluding the first element.

       (cdr  (eval. (cadr e) a))
   

6. cons
   
   The first input to cons is evaluated followed by the evaluation of the second input and then both are consed together.

       (cons (eval. (cadr e) a) (eval. (caddr e) a))
   

7. cond
   
   Let's start with an example,

       (setq e '(cond ((atom x) (quote x-is-an-atom))
                      ((atom y) (quote y-is-an-atom))))
       (setq a '((x (1 2 3))
                 (y 1)))
   
       (eval. e a)     ==> y-is-an-atom
   

   
   Looking at the code for eval. , the result returned by a cond form is the result of evaluating

   (evcon. (cdr e) a)
   
   ;; The input for evcon. is (cdr e) and the environment 'a'
   (cdr e) ==> (((atom x) (quote x-is-an-atom)) ((atom y) (quote y-is-an-atom)))
   
   ;; Thus for the cond form, (cdr e) is the association list ((p1 e1 ) (p2 e2) ... (pn en))
   

   
   Thus the evcon. function takes as input (cdr e) which is an association list of the form, ((p1 e1 ) (p2 e2) ... (pn en)), where each of the pi's denote a condition or predicate and for any i, the expression ei, is the expression whose result is to be returned when the corresponding pi evaluates to true.
   
   Let's have a closer look at evcon. ,

       (defun evcon. (c a)
         (cond ((eval. (caar c)  a) (eval. (cadar c) a))
               ('t (evcon. (cdr c) a))))
   

   
   All the evcon. function does is evaluate the first element in the head of the list namely the first condition and if it happens to evaluate to true then it evaluates the expression associated with that condition. If, however the conditions returns nil then the function recursively calls evcon. this time with the cdr of the current cond list.

This completes the explanation of the first half of the interpreter in which I explained how the interpreter handles the seven functions that were assumed as primitive for the functioning of the interpreter itself.

Searching an Association List

In my previous post I described an association list as a list of two element lists as ((x1 y1) (x2 y2) ... (xn yn)). However, the real purpose of an association list, as the name suggests is to associate one element with another. Thus, an association list denotes a list of key value pairs as ((k1 v1) (k2 v2) ... (kn vn)) where all the ki's refer to the value of the key while the vi's denote the value associated with ki. The keys must be distinct as the presence of duplicate keys would either mean that a key-value pair has been repeated or a key is associated with multiple values which defeats the purpose of an association list.

In this post, I review the assoc. function that takes as input a key x and an association list, y, and returns the value associated with the key. The function actually returns the second element of the first two element list in y whose first element is x.

The code for the assoc. function :

    (defun assoc. (x y)
        (cond ((eq (caar y) x) (cadar y))
               ('t  (assoc. x (cdr y)))))

As you can see the function is pretty short and simple. The element x is the key that has to be searched for in the association list y. Once again, we have the cond form. And once again, as found in the functions subst1,append. and pair. the cond form contains two parts. The simple base case and the second inductive case.

Consider the following examples where the first part of the cond form, the simple base case, is satisfied,

    (setq alphabets   '((1 a) (2 b) (3 c)))
    (setq companies   '((search google) (lisp ITA) (databases oracle)))   
    (setq favourites  '((sport cricket) (distro ubuntu) (editor emacs)))

    (assoc. '1 alphabets)          ==> a
    (assoc. 'search companies)     ==> google
    (assoc. 'sport  favourites)    ==> cricket

In all three examples above, the key was found to be equal to the first element of the very first two element list. For instance if you consider the first example,

    (car alphabets)           ==> (1 a)

And hence

    (eq (caar alphabets) '1)  ==> t

    ;; The returned value was 
    (cadar alphabets)    ==> a

The inductive step for the assoc. function is the simplest of inductive cases seen so far. If the first element of the first list is not equal to the key value, then, we repeat the search on the rest of the association list using (cdr y).

Let's trace the execution of the program on the example below,

    (assoc. 'editor favourites)

                            (assoc. 'editor favourites)

                                         ||
                                         ||
                                         \/


                (assoc. 'editor '((sport cricket) (distro ubuntu) (editor emacs)))

                                         ||
                                         ||
                                         \/

                (assoc. 'editor (cdr '((sport cricket) (distro ubuntu) (editor emacs))))

                                         ||
                                         ||
                                         \/

                       (assoc. 'editor '((distro ubuntu) (editor emacs)))

                                         ||
                                         ||
                                         \/
                
                       (assoc. 'editor (cdr '((distro ubuntu) (editor emacs))))

                                         ||
                                         ||
                                         \/
                
                          (assoc. 'editor '((editor emacs)))

                                         ||
                                         ||
                                         \/
                
                              (cadar '((editor emacs)))        

                                         ||
                                         ||
                                         \/
                
                                       emacs

However, there is a problem with the function assoc. as described above. The bug appears when you try to search the association list for a key that is not present in the list. Ideally, the assoc. function must return nil. However, it does not.

    (assoc. 'os favourites)

Can you modify the assoc. function to avoid the above error and make the assoc. function return nil?

Association Lists

An association list is a list of cons elements or a list of two element lists.
In this post the association lists I am describing are of the latter type viz., a list of two element lists.
A two element list is of the form (x1 y1) and thus the association list is of the form ((x1 y1) (x2 y2) ... (xn yn)).

The pair. function

The pair. function takes in two lists, x and y as arguments and returns an association list.

Ideally, the two lists x and y must be of the same length. Thus, (pair. '(x1 x2 ... xn) '(y1 y2 ... yn)) will return the association list ((x1 y1) (x2 y2) ... (xn yn)).

The code for the pair. function and other functions used in pair. are given below :

    (defun pair. (x y)
      (cond ((and. (null. x) (null. y)) '())
            ((and. (not. (atom x)) (not. (atom y)))
                   (cons (list (car x) (car y))
                         (pair. (cdr x) (cdr y))))))

    (defun and. (x y)
      (cond (x (cond (y 't) ('t '())))
            ('t '())))

    (defun null. (x)
        (eq x '()))

    (defun not. (x)
      (cond (x '())
            ('t 't)))

A skeletal overview

    (defun pair. (x y)
      (cond ((and. (null. x) (null. y)) '())
            (p2 e2)))

As can be seen from the above code, the pair. function consists of two condition checks. It first checks if both x and y are nil. If that is the case, then, it returns nil as it should. Try,

    ;; The base case when both x and y are nil.
    (pair. '() '())

If the first condition check fails, then it proceeds to the next condition check, p2, which is

    (and. (not. (atom x)) (not. (atom y)))

The above check ensures that both x and y are not atoms. Note that nil is an atom. Thus if even one input x or y is an atom then the second check fails.

In a cond form, every condition is checked one after another. If the last one fails, then the cond form returns nil. Thus, in our pair. function if the second condition check, p2, fails, then the function returns nil, as p2 is the last condition in the cond form.

However, if p2 returns t then the expression e2 as given below is evaluated. As can be guessed, e2 is where the major work is done. Like the functions subst1 and append., the function pair. also contains a recursive call to itself.

    (cons (list (car x) (car y))
          (pair. (cdr x) (cdr y)))

    ;; The function "list" takes in arbitrary elements as input 
    ;; and creates a list of those elements
    (list)                    ==> ()
    (list '1)                 ==> (1)
    (list '1 '2)              ==> (1 2)
    (list '1 '2 '3 '4 '5 '6)  ==> (1 2 3 4 5 6)
    (list '(1 2) '(3 4))      ==> ((1 2) (3 4))

Thus, what the expression e2 really does is it creates a list of the first element of x and the first element of y and then it conses this two element list onto the recursively created association list
pair. (cdr x) (cdr y)) .

Now to summarize the way in which pair. works. First, let's look at the code again

    (defun pair. (x y)
      (cond ((and. (null. x) (null. y)) '())
            ((and. (not. (atom x)) (not. (atom y)))
                   (cons (list (car x) (car y))
                         (pair. (cdr x) (cdr y))))))

It first checks if both x and y are nil. If that is the case it returns nil. If the first check fails, then, it checks if both x and y are not atoms in which case most probably they are lists. If this is true then, we create a list consisting of the first element of x and the first element of y. This list is then attached to the front of the recursive call to
(pair. (cdr x) (cdr y)) .
If the second check too fails, however, then the cond form returns nil. Thus this results in an association list whose length is equal to the number of elements in the shortest list if the lengths of the two lists are unequal.

Now, for a few examples.

    ;;Boundary examples where the length of one of the lists is smaller
    (pair. '(1) '())           ==> ()
    (pair. '(1) '(a b))        ==> ((1 a))

Now for a proper example, where the lengths of both lists are equal.

  (pair. '(1 2 3) '(a b c)) 

            
a)                             (pair. '(1 2 3) '(a b c))
                                         |
                                         |
                        _______________cons____________
                       /                               \ 
                      /                                 \
 (list (car '(1 2 3)) (car '(a b c)))            (pair. (cdr '(1 2 3)) (cdr '(a b c)))
    
    

                                         ||
                                         ||
                                         \/



b)                              (pair. '(1 2 3) '(a b c))
                                         |
                                         |
                        _______________cons____________
                       /                               \ 
                      /                                 \
                 (list '1 'a)                    (pair. '(2 3) '(b c))



                                         ||
                                         ||
                                         \/



c)                              (pair. '(1 2 3) '(a b c))
                                         |
                                         |
                        _______________cons____________
                       /                               \ 
                      /                                 \
                   '(1 a)                    (pair. '(2 3) '(b c))
                                                          |
                                                          |
                                          _______________cons____________
                                         /                               \ 
                                        /                                 \
                                   (list '2 'b)                  (pair. '(3) '(c))



                                         ||
                                         ||
                                         \/



d)                              (pair. '(1 2 3) '(a b c))
                                         |
                                         |
                        _______________cons____________
                       /                               \ 
                      /                                 \
                   '(1 a)                    (pair. '(2 3) '(b c))
                                                          |
                                                          |
                                          _______________cons____________
                                         /                               \ 
                                        /                                 \
                                     '(2 b)                      (pair. '(3) '(c))
                                                                           |
                                                                           |
                                                                     ____cons____
                                                                    /            \
                                                                   /              \
                                                                '(3 c)       (pair '() '())
                                                                                   |
                                                                                   |
                                                                                  '()


                                         ||
                                         ||
                                         \/


e)                              (pair. '(1 2 3) '(a b c))
                                         |
                                         |
                        _______________cons____________
                       /                               \ 
                      /                                 \
                   '(1 a)               _______________cons____________
                                       /                               \ 
                                      /                                 \
                                   '(2 b)                          ____cons____
                                                                  /            \
                                                                 /              \
                                                              '(3 c)            ()


                                         ||
                                         ||
                                         \/


f) (cons '(1 a) (cons '(2 b) (cons '(3 c) ())))   ==>   ((1 a) (2 b) (3 c))

Thus,

       (pair. '(1 2 3) '(a b c))  ==>  ((1 a) (2 b) (3 c))

Now, let's have a look at what happens when one of the lists is bigger than the other. Take a modification of the previous example,

       (pair. '(1 2 3) '(a b c d e))

In the above example the length of the second element is larger than the first. The intermediate stages that the above example passes through is the same as the previous example from a) to c) except for a few minor differences. At step d) however, this is what happens,

d)                                  (pair. '(1 2 3) '(a b c d e))
                                             |
                                             |
                            _______________cons____________
                           /                               \ 
                          /                                 \
                       '(1 a)                    (pair. '(2 3) '(b c d e))
                                                              |
                                                              |
                                              _______________cons____________
                                             /                               \ 
                                            /                                 \
                                         '(2 b)                      (pair. '(3) '(c d e))
                                                                               |
                                                                               |
                                                                         ____cons____
                                                                        /            \
                                                                       /              \
                                                                    '(3 c)       (pair '() '(d e))
                                                                                       |
                                                                                       |
                                                                                      '()

After that the steps are the same as in the previous example (from e) to f)).

Thus once again, we have

       (pair. '(1 2 3) '(a b c d e)) ==>  ((1 a) (2 b) (3 c))

Similarly,

       (pair. '(1 2 3 4 5) '(a b c)) ==>  ((1 a) (2 b) (3 c))

The append function

I had explained my method to understand lisp code and the subst1 function in my previous post. In the following posts I explain three functions, append., pair. and assoc. This post will explain the append. function.

Once again, the steps I use to understand lisp code :

1. Construct a mental model by abstracting away all the details and consider the outermost structure.
2. Expand the next function in the program and create simple examples along the way.
3. See what actually happens to the simple examples created in the previous step by manually/mentally parsing the input.
4. Repeat steps 2) & 3).

The append. function

(append. x y) takes two lists and returns the result of concatenating x with y

    (defun append. (x y)
        (cond ((null. x) y)
              ('t (cons (car x) (append. (cdr x) y)))))

     ;; Definition of null.
    (defun null. (x)
        (eq x '()))

Skeletal code

    (defun append. (x y)
        (cond ((null. x) y)  ;; If x is nil return y
              ('t   (e2))))  ;; else return the value of e2
                  ;;  where e2 = (cons (car x) (append. (cdr x) y))

The base case is if x is nil then y is returned as it is without modification. For example,

    (append. () '(1 2 3))

Now, for the expression which is executed if x is not null.

    (cons (car x) (append. (cdr x) y))

As seen in the subst1 function in the previous post, append. too contains a recursive call to itself. It first strips off the first element of the list x. Since x is not null there will be such an element and the expression
(cdr x)
will return either the rest of the array or it will return the empty list.

The complete code for append. and a few examples

    (defun append. (x y)
        (cond ((null. x) y)
              ('t (cons (car x) (append. (cdr x) y)))))

    (defun null. (x)
        (eq x '()))

    ;; Examples

    (append. () '(1 (2 3) 4 5)) ;; the first list x is null

    (append. '(1) '(2 3))       ;; the first list, x, contains a single element

    (append. '(1 2) '(3 4 5))   ;; the first list, x, contains two elements

    (append. '(1 (2 3)) '(4 5)) ;; Again the first list, x, contains only two elements

One important thing to note is the manner in which a list is built up. For instance, let's have a look at what the list
'(1 2) consists of. It can be viewed as a series of cons as given below

(cons '1 (cons '2 ()))
    ==> (1 2)

;; Similarly,
(cons '3 (cons '1 (cons '2 ())))
    ==> (3 1 2)

;; And so forth ...

Now, let's run a few examples on the code and see how it is evaluated,

(append. '(1) '(2 3 4 5))

  (append. '(1) '(2 3 4 5))                     (append. '(1) '(2 3 4 5))
             |                                             |
             |                                             |
            cons                          ==>             cons              ==>  (cons '1 '(2 3)) 
           /    \                                        /    \
          /      \                                      /      \
   (car '(1))  (append. (cdr '(1)) '(2 3))             '1    (append. () '(2 3))

The pattern to be noticed is that the first list keeps getting shorter till it eventually becomes empty. Another example,

(append. '(2 1) '(3 4 5))

                    (append. '(2 1) '(3 4 5))  
                             |                   
                             |                   
                            cons                 
                           /    \                
                          /      \               
                   (car '(2 1))  (append. (cdr '(2 1)) '(2 3))   
                                            |
                                            |
                                 (append. '(1) '(2 3))

       But, we know what (append. '(1) '(2 3)) returns from the previous example.
       Thus,


                    (append. '(2 1) '(3 4 5))  
                             |                   
                             |                   
                            cons                 
                           /    \                
                          /      \               
                         '2    '(1 2 3)

      Which is (cons '2 '(1 2 3))   ==>   (2 1 2 3)

A method to understand lisp code

In the next few posts, I intend to go over the code given by Paul graham in his article "The roots of lisp" in detail. I had simply illustrated the code in my previous post but, here, I will be breaking the code down and explaining it with examples. The reason I want to do this is twofold. Firstly, to explain the way the code works. Secondly, it helps me to recall whatever I learnt and the methods and techniques that helped me to best understand it.

The method I use to understand lisp code is as follows :

1. Construct a mental model by abstracting away all the details and consider the outermost structure.
2. Refine the structure by expanding the next function in the program and create simple examples along the way.
3. Evaluate the simple examples created in the previous step by manually/mentally running the input through the code.
4. Repeat steps 2) & 3).

The subst1 function is given below, the first non-trivial function in "The roots of lisp" article.

(defun subst1 (x y z)
     (cond ((atom z)
            (cond ((eq z y) x)
                  ('t z)))
            ('t (cons (subst1 x y (car z))
                      (subst1 x y (cdr z))))))
     

subst1 takes in three arguments. The first argument x can be any expression while y is an atom and z may be a list or an atom. The subst1 function then replaces every occurence of y in z by x.

This is how my method for understanding subst1 would look like

Step 1) The outermost skeletal structure of subst1

 (defun subst1( x y z)
       (cond (p1 e1)
             (p2 e2)))
     

Step 2) Expanding p1 and e1

Now, p1 is (atom z) and e1 is another cond of the form

     (cond ((eq z y) x)
           ('t z))
    

It is pretty easy to see what the e1 form does so I did not abstract the details out. What it does is if z == y it returns x otherwise it returns z. Now that we know what (p1 e1) does we can expand the subst1 function and have a look inside

    (defun subst1( x y z)
       (cond ((atom z)
              (cond ((eq z y) x)
                  ('t z)))
              (p2 e2)))

    ;Some examples where z is an atom

    (subst1 'a '() '())      ;z = '() is an atom
    (subst1 'a 'b 'b)        ;z = 'b is an atom
    (subst1 'a 'b 'c)        ;z = 'c is an atom
    (subst1 '(+ 1 2) 'b 'b)  ;z = 'b is an atom

Step 3) Running the example through the code

(subst1 'a '() '())
        ==> (cond ((atom '())
                    (cond ((eq '() '()) 'a)
                           ('t '())))
                  (p2 e2))
        ==> (cond ((eq '() '()) 'a)
                   ('t '()))
        ==> a

    (subst1 'a 'b 'c)
        ==> (cond ((atom 'c)
                   (cond ((eq 'c 'b) 'a)
                           ('t 'c)))
                  (p2 e2))
        ==> (cond ((eq 'c 'b) 'a)
                   ('t 'c))
        ==> c

N.B.:- The above process may become cumbersome if you attain a certain level of proficiency. At that time, it is to be discarded and to be used sparringly only for code that becomes really complex.

Step 2) Expanding (p2 e2)

The predicate, p2 is 't which means that if p1 fails then e2 is definitely executed. In other words, if z is not an atom, e2 is executed and the program returns the result of evaluating e2 which is

   (cons (subst1 x y (car z))
               (subst1 x y (cdr z)))

The above code is at the heart of the subst1 function and it consists of two recursive calls to itself. First, as you can see the cons function is being used here. So you must know what the cons function does. You can read it up here or in info.

Thus,

   (cons '5 '(4 3 2 1))
        ==> (5 4 3 2 1)

Now what the e2 form does is, it takes the first element (or car or head) of the list z and calls

    (subst1 x y (car z))

Then it evaluates subst1 on the tail (or cdr) of z.

    (subst1 x y (cdr z))

Finally, it calls a cons to recreate the list z with elements of y replaced by x. Note that the structure of the list remains unchanged, only the elements change.

Let's create a few examples for this,

    (subst1 '5 'x '(+ x 1))
    (subst1 '5 'x '(+ (- x 2) 1 x)) 
    (subst1 'm 'b '(a b (a b c) d))

Step 3) Running the examples through the code

Now, that we have expanded (p2 e2) we can view the entire code of subst1 and run our examples through the entire code,

(defun subst1 (x y z)
     (cond ((atom z)
            (cond ((eq z y) x)
                  ('t z)))
            ('t (cons (subst1 x y (car z))
                      (subst1 x y (cdr z))))))

Let's run the example given below

    (subst1 '5 'x '(+ x 1))

The function calls that will be made can be viewed as a tree as follows,

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
    (subst1 '5 'x (car'(+ x 1)))   (subst1 '5 'x (cdr '(+ x 1)))      
                |                              |
                |                              |
      (subst1 '5 'x '+)              (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                   (subst1 '5 'x (car '(x 1)))    (subst1 '5 'x (cdr '(x 1)))     
                                |                              | 
                                |                              | 
                      (subst1 '5 'x 'x)             (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                    (subst1 '5 'x (car '(1)))    (subst1 '5 'x (cdr '(1)))  
                                                |                            |
                                                |                            |
                                      (subst1 '5 'x '1)            (subst1 '5 'x '())

The above tree is the complete expanded expression tree. The manner in which the whole thing is evaluated will differ depending on the intepreter used. If the interpreter evaluates in a depth first manner, which I think is the standard way in which lisp does it, we will get the answer in the following manner

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
    (subst1 '5 'x (car'(+ x 1)))   (subst1 '5 'x (cdr '(+ x 1)))      
                |                    
                |                    
      (subst1 '5 'x '+)

which in turn evaluates to

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                            '+    (subst1 '5 'x (cdr '(+ x 1)))

To convince yourself, see the answer of the expressions given below

  (cons '+ (subst1 '5 'x (cdr '(+ x 1))))
  (subst1 '5 'x '(+ x 1))

Expanding the tree further,

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                   (subst1 '5 'x (car '(x 1)))    (subst1 '5 'x (cdr '(x 1)))      
                                |                             
                                |                             
                      (subst1 '5 'x 'x)             

                                 ||
                                 ||
                                 \/

                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                                           '5     (subst1 '5 'x (cdr '(x 1)))     
                                                               |
                                                               |
                                                    (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                     (subst1 '5 'x (car '(1)))    (subst1 '5 'x (cdr '(1)))   
                                                 |                            |
                                                 |                            |
                                     (subst1 '5 'x '1)                (subst1 '5 'x '())



                                 ||
                                 ||
                                 \/


                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                                           '5     (subst1 '5 'x (cdr '(x 1)))     
                                                               |
                                                               |
                                                    (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                                           '1      '()


                                 ||
                                 ||
                                 \/


                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      cons
                                  /    \
                                 /      \
                                '5     cons
                                      /    \
                                     /      \
                                    '1      '()


                                 ||
                                 ||
                                 \/


                               (+ 5 1)

Thus, the above method works well for me. I have not explained the complete process exactly but, the basic idea is to abstract away and then make things concrete one by one. Also I do not always go in detail when I get a good understanding or a strong intuitive feeling as to how it works. Activities such as drawing the expression trees is extremely good if you want to be more formal and more correct.

If you liked this, do drop in your comments and let me know what you think. If you have any issues, again, your comments will really helpful.

A lisp interpreter

The article " The roots of lisp", written by Paul Graham was a major motivation for me to learn lisp. In that article, he actually converts the original paper by John McCarthy(inventor of lisp) into running code in common lisp. I have not (yet) read the original (completely) but I found the commentary by Paul Graham to be relatively simple, but highly effective.

In this post, all I want to do is illustrate all the code found in the article "The roots of lisp" without any explanations whatsoever. I will post in more detail about the various functions later, but for now, please refer to the complete article for any explanations. The code was originally written for commonlisp but it works in emacs lisp too since the seven primitive operators are a part of emacs lisp.

I faced a few minor glitches while executing the code, and thanks to the people at comp.lang.lisp for clearing them. The glitches were due to the fact that the lambda form and the label notation are a bit modified in the more recent versions of common lisp.

The Seven Primitive Operators

;From Paul Graham's site
    ;see http://www.paulgraham.com/rootsoflisp.html

;P.S:- Any line beginning with a ';' is a comment and not to be executed
      ;Like this line for instance. Do not evaluate such lines.


;1)The Seven primitive operators

    ;a)quote

        (quote a)

        'a

        (quote (a b c))


   ;b)atom

        (atom 'a)

        (atom '(a b c))

        (atom '())

        (atom '(atom 'a))


   ;c)eq

        (eq 'a 'a)

        (eq 'a 'b)

        (eq '() '())


   ;d)car

       (car '(a b c))


   ;e)cdr

        (cdr '(a b c))


   ;f)cons

        (cons 'a (cons 'b (cons 'c '())))

        (car (cons 'a '(b c)))

        (cdr (cons 'a '(b c)))


   ;g)(cond (p1 e1) (p2 e2)  ... (pn en))

        (cond ((eq 'a 'b) 'first)
              ((atom 'a) 'second))

Denoting functions

;2) lambda -- ((lambda (p1 p2 ... pn) e) a1 ... an)

    ((lambda (x) (cons x '(b))) 'a)

    ((lambda (x y) (cons x (cdr y)))
      'z
      '(a b c))


    ;((lambda (f) (f '(b c)))
      ;(lambda (x) (cons 'a x)))

   ;Though the above function is theoretically correct,
    ;it is not working in any of the more recent versions of the lisp dialects

   ;The right way to do it in the more recent versions of lisp is as given below
      ;It works in clisp as well as emacslisp
    ((lambda (f) (funcall f '(b c)))
        (lambda (x) (cons 'a x)))
   
;The label function is obsolete

;(label subst1 (lambda (x y z)
           ;(cond ((atom z)(cond ((eq z y) x)
                                ;('t z)))
                 ;('t (cons (subst1 x y (car z))
                           ;(subst1 x y (cdr z)))))))

   ;The reason for using subst1 (instead of subst) is 
        ;because there is an in-built function
        ;(in common lisp as well as emacslisp) called subst with the same functionality

   ;(defun f (p1 ... pn) e) is equivalent to f=(label f (lambda (p1 ... pn) e))
    (defun subst1 (x y z)
     (cond ((atom z)
            (cond ((eq z y) x)
                  ('t z)))
            ('t (cons (subst1 x y (car z))
                      (subst1 x y (cdr z))))))

    (subst1 'm 'b '(a b (a b c) d))

    ;(cond (x y) ('t z)) is equivalent to
           ;if (x) then y else z (in languages like C, python, java ...)
    (cond (nil  0)
          ('t   1))

A few functions

;3) Some Functions

    ;Abbreviations

        (cadr '((a b) (c d) e))

        (caddr '((a b) (c d) e))

        (cdar  '((a b) (c d) e))

        (cons 'a (cons 'b (cons 'c '())))

        (list 'a 'b 'c)

    ;The periods after each of the functions is
       ;a)to  *distinguish* them from the primitive operators,
       ;b)to identify them as being built using the primitive functions
       ;c)to avoid clashes with existing functions

    ;a) (null. 'a) -- tests whether its argument is the empty list

        (defun null. (x)
            (eq x '()))

        (null. 'a)

        (null. '())

    ;b) (and. x y) -- return t if both its arguments do and returns () otherwise

        (defun and. (x y)
          (cond (x (cond (y 't) ('t '())))
                ('t '())))

        (and. (atom 'a) (eq 'a 'a))

        (and. (atom 'a) (eq 'a 'b))

    ;c) (not. x) return t if its argument returns (), and () if its arg returns t

        (defun not. (x)
          (cond (x '())
                ('t 't)))

        (not. (eq 'a 'a))

        (not. (eq 'a 'b))

    ;d) (append. x y) takes two lists and returns their concatenation

        (defun append. (x y)
          (cond ((null. x) y)
                ('t (cons (car x) (append. (cdr x) y)))))

        (append. '(a b) '(c d))

        (append. '()    '(c d))

    ;e) (pair. x y) takes two lists of the same length and return a list of
      ;two-element lists containing successive pairs of an element from each.

        (defun pair. (x y)
          (cond ((and. (null. x) (null. y)) '())
                ((and. (not. (atom x)) (not. (atom y)))
                       (cons (list (car x) (car y))
                             (pair. (cdr x) (cdr y))))))

         (pair. '(x y z) '(a b c))


    ;f) (assoc. x y) takes an atom x and a list y of the form created by pair. , 
;and returns the second element of the first list in y whose first element is x

        (defun assoc. (x y)
          (cond ((eq (caar y) x) (cadar y))
                ('t  (assoc. x (cdr y)))))

        (assoc. 'x '((x a) (y b)))

        (assoc. 'x '((x new) (x a) (y b)))

Finally, the interpreter

;4) The interpreter for our lisp

        (defun eval. (e a)
          (cond
            ((atom e) (assoc. e a))
            ((atom (car e))
             (cond
               ((eq (car e) 'quote) (cadr e))
               ((eq (car e) 'atom)  (atom (eval. (cadr e) a)))
               ((eq (car e) 'eq)    (eq   (eval. (cadr e) a)
                                          (eval. (caddr e) a)))
               ((eq (car e) 'car)   (car  (eval. (cadr e) a)))
               ((eq (car e) 'cdr)   (cdr  (eval. (cadr e) a)))
               ((eq (car e) 'cons)  (cons (eval. (cadr e) a)
                                          (eval. (caddr e) a)))
               ((eq (car e) 'cond)  (evcon. (cdr e) a))
               ('t (eval. (cons (assoc. (car e) a)
                                (cdr e))
                           a))))
            ((eq (caar e) 'label)
             (eval. (cons (caddar e) (cdr e))
                    (cons (list (cadar e) (car e)) a)))
            ((eq (caar e) 'lambda)
             (eval. (caddar e)
                    (append. (pair. (cadar e) (evlis. (cdr e) a))
                              a)))))

        (defun evcon. (c a)
          (cond ((eval. (caar c)  a)
                 (eval. (cadar c) a))
                ('t (evcon. (cdr c) a))))

        (defun evlis. (m a)
          (cond ((null. m) '())
                ('t (cons (eval.  (car m) a)
                          (evlis. (cdr m) a)))))

;Examples of our eval. function in action

        (eval. 'x '((x a) (y b)))

        (eval. '(eq 'a 'a) '())

        (eval. '(cons x '(b c))
               '((x a) (y b)))

        (eval. '(cond ((atom x) 'atom)
                      ('t 'list))
               '((x '(a b))))

        (eval. '(f '(b c))
               '((f (lambda (x) (cons 'a x)))))


        (eval. '((label firstatom (lambda (x)
                                    (cond ((atom x) x)
                                          ('t (firstatom (car x))))))
                  y)
                '((y ((a b) (c d)))))


        (eval. '((lambda (x y) (cons x (cdr y)))
                  'a
                  '(b c d))
               '())

        (eval. '(quote a) '())

What is Lisp ?

<<About linuxandlisp>> For the uninitiated, Lisp is the programming language invented by Professor John McCarthy in 1958 while he was a professor at The Massachusetts Institute of Technology (MIT).This makes lisp the most ancient programming language still in existence. Remarkably it is also the best. All other programming languages have since then been a degeneration in quality. The beauty of lisp can be described by the manner in which programmers especially expert hackers of languages like C and java have responded once they learnt lisp. One such example is that of Peter Siebel who was a java programmer before he learnt lisp. He then actually left his job to start learning lisp and even wrote a book on lisp to help the people who had no idea what lisp was all about. To learn about the essence lisp you can visit paul graham's web site where he discusses the roots of lisp. Also the official history of lisp by John McCarthy himself is available here

Welcome to Linux and Lisp blog

Linux and Lisp blog was created in order to keep a journal of the most interesting stuff that i am learning in Linux as well as lisp. Linux and lisp are two of the most beautiful pieces of technology that computer science has seen in the last 50 years or so. Linux has been around for about 40 years while lisp has been around for about 50 years. As far as my skills and knowledge in linux and lisp are concerned, I am at an intermediate level right now. I am neither an expert neither am I a complete beginner. Hence I will be posting articles from which a novice will learn, an intermediate person will find interesting and an expert will comment on. I will try my best to make this blog lively, entertaining and useful. Though this blog is mainly dedicated for linux and lisp I will also post other content that I find interesting. So do bookmark my page and tune in as frequently as possible.