quasiTech

experiments

Starting With Common Lisp

Learning a new programming language requires you to interact with its runtime. But the bare bones runtime is usually just that – bare. It generally is an unpleasant task to interact with directly. This is nowhere more true then when learning to program in Lisp. But the good news is that the tools of the Lisp environment are evolved and provide a lot of support to make interaction less unpleasent. It is therefore imperative that we use these tools and setup an ideal environment before we start with the lessons.

Today we will setup, from scratch, a Common Lisp development environment. This will include an editor, an interactive development environment, a structured editing mode and an implementation of Common Lisp.

Note : please change the paths in the examples to reflect your system

Common Lisp

We will need an implemntation of Common Lisp. There are several free and commercial ones available. We will use the excellent public domain Steel Bank Common Lisp (SBCL) for this tutorial.

Steel Bank Common Lisp (SBCL) is a high performance Common Lisp compiler. It is open source / free software, with a permissive license. In addition to the compiler and runtime system for ANSI Common Lisp, it provides an interactive environment including a debugger, a statistical profiler, a code coverage tool, and many other extensions.

Let us select the Darwin (Mac OS X) AMD64 port from the downloads section and download (< 10 Mb).

1
wget http://prdownloads.sourceforge.net/sbcl/sbcl-1.1.8-x86-64-darwin-binary.tar.bz2

Extract the archive

1
tar xjvf sbcl-1.1.8-x86-64-darwin-binary.tar.bz2

Change to the extracted folder

1
cd sbcl-1.1.8-x86-64-darwin

The INSTALL file details the installation instructions. I prefer to install in my home folder. Create a folder to contain all the SBCL files. Run the install script specifying the installation folder of our choice.

1
2
3
mkdir /Users/me/sbcl

INSTALL_ROOT=/Users/me/sbcl sh install.sh

This will install all the files into /Users/me/sbcl. SBCL contains an executable and a core file. The executable – usually named sbcl – looks for an environment variable SBCL_HOME to locate the core file. We also need to set the locale. I have a shell script in my local bin which does all this.

Create a file ~/bin/sbcl and add following to it :

1
2
3
4
5
6
#!/bin/sh
LC_CTYPE=en_US.UTF-8
export LC_CTYPE
export SBCL_HOME=/Users/me/sbcl/lib/sbcl/

/Users/me/sbcl/bin/sbcl $*

Make this file executable

1
chmod +x ~/bin/sbcl

now typing sbcl into your shell prompt should start up SBCL and show something like below

1
2
3
4
5
6
7
8
This is SBCL 1.1.10, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
*

You can type s-expressions at the * prompt and the lisp will evaluate and return you an answer. For example.

1
2
3
4
* (+ 2 3)

5
*

Congrats !! We have an installed and running Common Lisp ! Now let’s move forward.

Quicklisp !

http://www.quicklisp.org/beta/ by Zach Beane

Quicklisp is a library manager for Common Lisp. It works with your existing Common Lisp implementation to download, install, and load any of over 900 libraries with a few simple commands.

Read through the installation instructions from that site. In short we will have to :

1
$ curl -O http://beta.quicklisp.org/quicklisp.lisp

Start SBCL with this file :

1
sbcl --load quicklisp.lisp

At the prompt follow the instructions – type following :

1
* (quicklisp-quickstart:install)

This will download and install the latest quicklisp software. To add the quicklisp to the SBCL startup file :

1
(ql:add-to-init-file)

Now everytime you start SBCL it will load quicklisp automatically. yey!

To install a library you simply have to :

1
* (ql:quickload "libraryname")

Now the we need to install a very important package called SLIME. This is the software which gives us our interactive development environment (like no other) !

1
(ql:quickload "quicklisp-slime-helper")

Note the instructions which follow this – you will need to use them for your editor configuration. Next topic.

Editor

GNU Emacs is an extensible, customizable text editor—and more. At its core is an interpreter for Emacs Lisp, a dialect of the Lisp programming language with extensions to support text editing.

Emacs is the editor of choice for Lisp programmers. It provides fantastic support for programming in various lisps. There are a lot of flavours available for a lot of different systems. On GNU/Linux systems, the latest emacs can be installed using the system package manager. I use Aquamacs on Mac OS X. Please install your Emacs before moving to the next step.

Configuring Emacs

Create a .emacs file in your home. This file is the Emacs startup file and can contain any valid elisp. All options can be configured here. By convention a folder ~/.emacs.d is usually used for any misc elisp files, packages etc. which we may need to install manually.

Emacs comes with a package manager. This can automagically install packages and their dependencies. I like all the installed packages to reside inside a folder .emacs.d/elpa. Create this folder. To set it up, add the following to your .emacs. (note : ; start a comment in lisp source files)

1
2
3
4
5
(require 'package)
(add-to-list 'package-archives
             '("melpa" . "http://melpa.milkbox.net/packages/") t)
(setq package-user-dir "/Users/me/.emacs.d/elpa/") ;; change the path.
(package-initialize)

Now M-x package-install <package-name> will download and install the package.

SLIME

SLIME is a Emacs mode for Common Lisp development.

Configuring SLIME : Add the following to your .emacs

1
2
3
4
5
6
7
8
(setq inferior-lisp-program "~/bin/sbcl")
(load (expand-file-name "~/quicklisp/slime-helper.el"))

(setq slime-lisp-implementations
           '((sbcl ("~/bin/sbcl") :coding-system utf-8-unix)))

(set-language-environment "UTF-8")
(setq slime-net-coding-system 'utf-8-unix)

This basically tells Emacs where to find the lisp (called inferior-lisp) program. Then we load the slime-helper which quicklisp provides.

M-x eval-buffer will read your new changes. M-x slime should start SLIME and present you with a nice REPL. At the REPL ,q will quit SLIME.

PAREDIT

ParEdit (paredit.el) is a minor mode for performing structured editing of S-expression data.

M-x package-install paredit should download and install it.

To setup paredit and to get it to work with SLIME, add following to .emacs.

1
2
3
4
5
6
7
;; Paredit customizations
(autoload 'paredit-mode "paredit"
  "Minor mode for pseudo-structurally editing Lisp code."
  t)
(add-hook 'slime-mode-hook (lambda () (paredit-mode +1)))
(add-hook 'slime-repl-mode-hook (lambda () (paredit-mode +1)))
(require 'paredit)

Almost there

At this point of time we have an installed and running Common Lisp implementation, an advanced editor, an interactive development environment & a structured editing extention for the editor. This is the place to spend some time to see how all of these work.

  • Inside Emacs C-h t starts the inbuilt interactive tutorial
  • Emacs introductory videos http://emacsrocks.com/
  • SLIME video – This is an excellent and instructional watch. Marco Baringer shows how it is done. Consider this also as informal introduction to SLIME
  • SLIME manual
  • Paredit Author’s page
  • Paredit Emacs Wiki page

Epilogue : Learning Common Lisp

Now that we have got all the boring setup stuff out of the way, let us start with Common Lisp !! Practical Common Lisp is an excellent modern introduction and you can start here.

I am assuming that as you have come this far, you are interested in learning. I would suggest that you do exactly so – learn. Give it some time and thought before you come to any conclusions. This is very important for people who are coming from a non-lisp programming background. The lisp way is different. It may take time for you to get it. Concentrate on the simpler language aspects and try to solve challenging programming problems. Stay away from the temptation of exploring libraries and doing some ‘real’ work at this point. You will only get distracted with unnecessary detail.

Best Luck on your journey – You will not regret it.

May the force be with you.

How I Came to Lisp

People have asked me why I chose to program in Lisp.

Early days

Long back (1995-6) when I was still a college student (studying Math) I first saw Prolog. Chirs Martis, then boyfriend (now husband) of my friend Medha Patkar used to work for some company in SEEPZ and he was working on a project for some Japanese company. They had to migrate an older code base to a newer stack. I disremember the details (I dont think I knew much anyway) but he was learning Prolog as they were using a translater written in Prolog to help in the translation of the older codebase. I was a curious cuss then, and kept pestering him with questions. I was interested and wanted to learn Prolog. This was before we had access to the Internet. So my friend Anuprita took me to the British Council Library where she was a member. I saw a couple of Prolog books – pretty hard for me to understand as I had scant background in Programming (I did not even own a computer at that time). But I also saw a tiny booklet about another language called Lisp written by some Indian author. What intrigued me was the factorial program on the last page – this did not look like any program I had ever seen. I was more interested.

Fast forward to 1998. I tried using CMUCL on my AMD 386DX with 8 MB of RAM. It was very hard to understand what to do at the REPL. Hardly any documentation. Fast forward somewhere 2001 and Internet world. I landed up on comp.lang.lisp and asked a few silly questions. Got my head bitten off seriously – especially by Naggum. But Erik Naggum, and Erann Gatt (Ron Garret) were the reason I persisted. Erann(Ron) by his Nasa stories really awed me. By this time I had also come across Greenspun’s tenth rule of programming…

RMS and me

By this time I was a super fan of RMS. He wrote Emacs. In lisp. WOW.

Soon, 2003, I wrote a software for a cable ISP service provider in Bandra East. I tried CMUCL again. This time with Emacs. I had an upgraded machine – Pentium MMX 200MHz with 32 MB or RAM. Those were the days when internet was provided by small players who provided Cable TV. This software did everything from user management to enabling / disabling users to keeping track of their usage. I used the GNU/Linux ‘tc’ tool to do the traffic shaping. I wrote everything including a jazzy web-frontend in CMUCL. It ran very stably.

All this time I was a Common Lisp noob. But still I loved the simplicity of the syntax and the expressibility. There was also a sense that I was just touching the surface and I needed to find the horizon. From 1995 to this time I had learned programming in C and had done some low level stuff in Dos 6.22 and GNU/Linux. I had finished my Post Graduate Diploma in Networking from the National Center of Software Technology. I had done a bit of network programming. I loved to program in C. But I loved CL too.

So the reasons I persisted and learned programming in Common Lisp are many, mostly incidental. But there was also a sense that this was something beyond the ordinary – it was elegant. There was also some kind of respect for it as few of the greatest minds of this field had used it and respected it.

I had to explore. I had to learn.

next post – how I used Common Lisp at Cleartrip

Emacs and JS: Finding Function Definitions

I started doing Javascript recently. The js2-mode is excellent. But I am spoilt by SLIME :). One of the things I most missed from there was to be able to lookup function definitions with M-. and to get back with M-,. I had been pair programming with a team-mate and editing a 1000 line file and in his vanilla ‘Sublime’ editor and it was a royal pain scrolling all over the place looking for function definitions. So I decided to try my hand at some elisp. This was the first time but I really felt the need.

This is pretty simple really :

  • Get the word at point
  • Prepend “function ” to it
  • Save current location on a stack to getting back
  • Go to top of buffer
  • Do a forward search with our search string
  • If successful center line
  • Else do nothing and show message.

Another function, bound to M-, pops a position off the stack and goes to it.

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
;;; Find JS function definition in your current buffer (and go back).

(defvar *quasi-js-current-pos* nil)

(defun quasi-js-function-search ()
  "Search for JS function definations. In a rather dumb way, but works, albeit
only for current buffer. Works recurcively too :)"
  (interactive)
  (let ((text (thing-at-point 'word)))
    (push (point) *quasi-js-current-pos*)
    (goto-char (point-min))
    (if (search-forward (concat "function " text) nil t)
        (recenter)
      (progn
        (goto-char (pop *quasi-js-current-pos*))
        (message "Could not find definition for %s" text)))))

(defun quasi-js-function-go-back ()
  "Go back to where you initiated search from"
  (interactive)
  (if *quasi-js-current-pos*
      (goto-char (pop *quasi-js-current-pos*))
    (message "Nowhere to jump!")))

;; Add hooks to js2-mode. It will cobbler the default tag-search bindings. Beware.
(add-hook 'js2-mode-hook
          (lambda ()
            (local-set-key (kbd "M-.") #'quasi-js-function-search)
            (local-set-key (kbd "M-,") #'quasi-js-function-go-back)))

It really felt good to have written my first useful elisp code.

Pooler

A simple, fast & thread-safe generic pooling library.

Homepage http://quasilabs.com/pooler/

We need pools for items which have heavy cost of creation and which we can reuse. A typical use case is connection pools.

Pool item creation (as required) is automatic on fetch-from pool. Pool-item’s are created and destroyed using user supplied funcitons. The pool has a idle timeout after which all the existing pool-item’s are destroyed and new ones created (pool-init). The pool has a threshold number of items which it tries to maintain.

Licence : MIT

An Example :

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
CL-USER> (pooler:make-pool :item-maker
                           #'(lambda () (clsql:connect '("127.0.0.1" "quasidb" "quasi" "*****")
                                                       :database-type :mysql
                                                       :if-exists :new))
                           :item-destroyer
                           #'(lambda (item) (clsql:disconnect :database item)))
#S(POOLER::POOL
  :NAME "Default Pool"
  :QUEUE #S(SB-CONCURRENCY:QUEUE
  :HEAD (SB-CONCURRENCY::.DUMMY.)
  :TAIL (SB-CONCURRENCY::.DUMMY.)
  :NAME NIL)
  :LOCK #<SB-THREAD:MUTEX "Pool Lock" (free)>
  :ITEM-MAKER #<FUNCTION (LAMBDA #) {1005C9BFAB}>
  :ITEM-DESTROYER #<FUNCTION (LAMBDA #) {1005CCAAAB}>
  :CAPACITY 40
  :THRESHOLD 2
  :TIMEOUT 300
  :LAST-ACCESS 0
  :CURRENT-SIZE 0
  :TOTAL-USES 0
  :TOTAL-CREATED 0
  :TOTAL-POOL-INITS 0)
CL-USER> (defvar *mysql-pool* *)
CL-USER> (pooler:fetch-from *mysql-pool*)
#<CLSQL-MYSQL:MYSQL-DATABASE 127.0.0.1/quasidb/quasi OPEN {1007571373}>
CL-USER> (pooler:return-to *mysql-pool* *)
2
CL-USER> (pooler:with-pool (db *mysql-pool*) (clsql:query "show tables;" :database db))
(("LOGIN_DATA"))
("Tables_in_quasidb")

Has been tested with SBCL, CCL & CMUCL on OSX. Should work on GNU/Linux.

Nostalgia

Long ago I used to program C. I loved it. In those days, access to the net was restricted to a 30 minute session once a week. There used to be a ‘superfast’ 14400 baud US Robotics modem connected to a DOS PC in our collage library. We had to pay for the access. I used to spend those 30 minutes downloading stuff at optimal speeds for later consumption. Either I used to download code snippets from ftp servers and boards or some random Anarchist documents or I used to be downloading images of angels compressed in this magical format called JPEG. These were so much better and smaller than the prevalent GIF files at that time. 16 million colours as opposed to 256 and that too at 1/5 the size !!

I taught myself ‘C’ programing using ‘Let us C’ by Yeshvant Kanhetkar. I also loved the book ‘Programing in ANSI C’ by Ram Kumar and Rakesh Agarwal. DOS 6.2 was an awesome OS to play with. You could do anything you wanted. :) I wrote a couple of interesting TSR’s and a system information utility which gave complete information about your hardware. I also wrote a graphical copy program. The inspiration was the hours we spent transferring bootleg material around on floppy disks and waiting for them to get copied not knowing how much % was remaining or which files were written on bad sectors. We could skip files which gave the dreaded Abort, Retry, Fail? error.

One of the most amazing and inspirational C programs I came across was from the The International Obfuscated C Code Contest (IOCCC). The program calculated a factorial of any large number. I have let it run for about 30 minutes on my AMD 386 DX 40MHz machine, watching the endless stream of numbers. It is written by one Michael Savastio and the source code is beautiful and can be found here (savastio.c).

‘Nuff of the nostalgia :)

How to Solve It

One of the books, which Alok Tiwari, a friend of mine from the old time, had suggested I read was ‘How to Solve it’ by G Polya. I remember being enthralled reading it. It, with Euclid’s ‘Elements’, are the two books which have had the most impact on my method of thought.

I made a quick set of slides for sharing the salient points of that book with a few friends. The book itself is written in 1945 but still is a very inspiring read.

Wikipedia article about him says that he was born in Budapest, Hungary and that he was a professor of mathematics from 1914 to 1940 at ETH Zürich in Switzerland and from 1940 to 1953 at Stanford University carrying on as Stanford Professor Emeritus the rest of his life and career. He wrote four books on the subject: How to Solve It, Mathematical Discovery: On Understanding, Learning, and Teaching Problem Solving; Mathematics and Plausible Reasoning Volume I: Induction and Analogy in Mathematics, and Mathematics and Plausible Reasoning Volume II: Patterns of Plausible Reasoning.

Some of his quotes are :

“To be a good mathematician, or a good gambler, or good at anything, you must be a good guesser.”

“A Great discovery solves a great problem but there is a grain of discovery in the solution of any problem. Your problem may be modest; but if it challenges your curiosity and brings into play your inventive faculties, and if you solve it by your own means, you may experience the tension and enjoy the triumph of discovery”

“To conjecture and not to test is the mark of a savage”

About Paradigms

A multi-paradigm programming language is a programming language that supports more than one programming paradigm. As Leda designer Tim Budd holds it: The idea of a multiparadigm language is to provide a framework in which programmers can work in a variety of styles, freely intermixing constructs from different paradigms. The design goal of such languages is to allow programmers to use the best tool for a job, admitting that no one paradigm solves all problems in the easiest or most efficient way.

I was just reading this blog post by my friend Sandeep Procedural Programming is NOT a Bad Thing! and just thought I had to add some of my own blab …

I think rather than what features a language or paradigm provides, it is more important to ask oneself how many of these problem solving tricks/ techniques / methods one really knows and can call to aid. Understanding a certain paradigms enough to start fashioning solutions around it is non trivial. Knowing several paradigms should help open a world of different techniques of problem conquest. Any reasonably sized software would have you contemplate deep and hard on the problem space and probable techniques. Most likely, new techniques and paradigms will have to be acquired.

The tools we know of mould the way in which we approach problems. As a C programmer, say, what I can think of are data, locations of data, manipulation of this data in some conditional or iterative way. I would see clear steps and their impact on performance. As a schemer perhaps, I could see abstractions which might help me solve larger problems with less effort at the cost of seeing immediate impact on performance. For example quoting from SICP where the author is explaining about ‘concepts’ and ‘abstractions’ – “Similarly, as program designers, we would like our language to be powerful enough so that we can write a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums.”

The key to program design and problem solutions is our ability to see these ‘abstractions’ and hence reduce problem space and complexity repeatedly till we have managed to ‘solve’ it sufficiently.

Certain vagueness or misdirections occurs when people give (or understand) only part of the reasons why they propound a particular paradigm strongly. For example, the Java people build a engineering platform which could scale to handle large complexity and resources and also help management of the whole thing. Large companies with extremely large code bases and with large programmer base have, as an element of the problem space, issues regarding code integrity, collaborative maximal exclusion coding. The issues and hence the design patterns which addresses these issues are specific to such systems. A Linus working on GIT is a different proposition. So Java is not necessarily a very elegant medium of expression of ideas but it is an excellent platform for the management of larger code bases and systems.

One has to choose a platform which will give him access to all the paradigms which his problem space may need to reach a good solution. So the key to a good platform for the creative types and people not encumbered with people problems, turns out to be the flexibility of the platform in providing the programmer a free space where a solution could be designed which merits the problem without being restrained or constrained by any particular paradigm or method of work. Ruby and Python are becoming more popular due to the flexibility and the expressiveness they provide, which I will call the elegance factor, which earlier was underrated.

Me, I program in Common Lisp. It is Nirvana for the programmer. The path to Niravana is always tough. But what you can do with such tools is what makes work pleasure.

Some Hash Functions

Here are some common hash functions in C I found online here and here. I have done the menial task of translating them to Common Lisp.

1
2
3
4
5
6
7
8
9
10
11
12
13
;;; Hash Function by Dan Bernstein
(defun hash-DJB (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381))
    (loop for x across str
     do (setf hash (ldb (byte 32 0)
                        (+ (ldb (byte 32 0)
                                (+ (ldb (byte 32 0)
                                        (ash hash 5)) hash))
                           (char-int x))))
     finally (return hash))))
1
2
3
4
5
6
7
8
9
10
;;; Hash Function by Dan Bernstein
(defun hash-DJB2 (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (logxor (char-int x) (* hash 33))))
       finally (return hash))))
1
2
3
4
5
6
7
8
9
10
11
12
13
;;; Hash Function from GAWK, a variation from the verwion from SDBM
(defun hash-SDBM (str)
  (declare (type simple-string str)
           (type (unsigned-byte 32) hash)
           (optimize speed (debug 0)))
  (let ((hash 0))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (+ (char-int x)
                             (ldb (byte 32 0) (ash hash 6))
                             (ldb (byte 32 0) (ash hash 16))
                             (- hash))))
       finally (return hash))))
1
2
3
4
5
6
7
8
9
10
11
12
;;; An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3
(defun hash-DEK (str)
  (declare (type simple-string str)
     (type (unsigned-byte 32) hash)
     (optimize speed (debug 0)))
  (let ((hash (length str)))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (logxor (char-int x)
                                  (logxor (ldb (byte 32 0) (ash hash 5))
                                          (ash hash -27)))))
       finally (return hash))))