Lisp for the 21st Century

Lisp is the grandaddy of functional programming languages both in terms of size and age. Next year (2009) will see a special celebration of Lisp's 50th birthday and a special session in ILC in Massachussetts. It is also nearly a quarter of a century since Lisp was formalised into what has become the most definitive dialect of that language - Common Lisp. Lisp is also enjoying something of a revival as younger programmers find that gramps can outjive a lot of younger languages like Java.

The definitive text on that agreement - Common Lisp: the Language - is sitting on my desk. It's an impressive tribute to the ability of people to work together as a team. But it suffers from a significant degree of bloat because when you get a number of experts sitting round a table arguing whether feature Y should be in the language, the yea sayers tend to win on the nay sayers. It's easier to make a case for including something than saying it should not be there. In fact the easiest way to make a standard language consistent with all of its various dialects is to union the existing features of all the dialects together. The result is that programs can gravitate to your standard with no problem and you establish your pre-eminence. The disadvantage is that the resulting standard is very large and implementors have a hard time implementing your standard. Newcomers are faced with an intimidating pile of documentation when what they want is something they can pick up and use.

Shortly after CLTL was formalised, in the 1990 EUROPAL conference, Richard Gabriel voiced the feeling that CLTL was too large. I think a lot of people would agree with that. Almost everybody could pick out some feature of CLTL which they feel could be dispensed with. The problem is that although most people think CLTL is too large in some ways, the intersection of the elements that they would leave out amounts to the empty set. The disagreement about what we really can do without was the reason that CLTL got so large in the first place and these disagreements are still there.

If CLTL can be criticised as too large, it can be also said to be not large enough. A lot has moved on in the software world since Common Lisp received its baptism in 1984. Graphical interfaces, scripting languages, multiuser databases, event driven programming, sound files, the Internet and virtual conferencing have all sprung up in the last twenty years. CL has been losing out recently because languages like Python aim to offer shrink-wrapped solutions to many of these requirements. In CL, solutions do exist, but you have to shop around to find them and cope with documentation of uncertain quality. Noobs don't want to do that and who can blame them? If you can get a standard solution, used by many, described by a professional author in a book you can buy in Borders, why trudge through somebody's home brew?

This fact underlines the distinction between Turing-equivalence and computational adequacy. Everybody who does CS knows about the former and in Lisp you can achieve Turing equivalence with less than 10 system functions. In fact I taught an introductory course on computing just that way. Computational adequacy is a different concept. It means that the language is computationally adequate for the tasks it is supposed to perform. In that sense Common Lisp as defined in CLTL is not computationally adequate for the C21. There's just too many things noobs want to do that are not part of the language standard. Things that did not exist 25 years ago.

CL implementors have responded bravely to this. They sneak in these functions in things called external packages which are not part of the official standard and allow you to do things like talk to the operating system. Cool. Except these functions are platform-specific, are called differently by different implementations and so the noob is not really happy. And there's still lots of stuff that many platforms do not inherently support.

Novices like instant gratification. If you're a novice and you want to write a script then a language you can pick up in 15 minutes and write HELLO WORLD in yellow letters across your web page is a turn on. It gets you interested and you learn more. In this way some truly awful languages (like Perl) can get a grip because by the time the novice has realised that his favourite language MacHack is really only good for writing HELLO WORLD in yellow letters, he's hooked. He's invested so much time in learning MacHack that he won't give it up.

A really neat engineering solution would combine the glamour of MacHack with the power of Lisp.

If Lisp is not getting the attention from programmers that it deserves, then its also getting cold-shouldered by the academics. In many universities Lisp is not thought of as an adequate functional programming language. Criticisms? Full of procedural constructions, missing pattern-matching, lambda calculus consistency, formal semantics and strong typing. Actually there are arguments for saying that the last feature is not always a boon, but the fact is that many of the mainstream developments in functional programming (especially in the UK) have passed by Lisp. ML, OCAML, Haskell and F# all have features missing from Lisp.

Qi is really about equipping Lisp for the C21 so that it can carry on for another 50 years. It means tackling the problems outlined above. Essentially Qi is more than a language - its a project. How does this project work? We can put the central ideas in numbered form in terms of the <Good Solution>.

1. The <Good Solution> does not abandon Common Lisp. Common Lisp took a lot of effort to become established and the <Good Solution> sticks to it. So the <Good Solution> runs under Common Lisp because who wants to implement garbage collectors, and pointers and compilers and all that stuff? Its old and it works so lets use it.
2. The <Good Solution> is open source. Anybody can port the <Good Solution> onto their favourite Lisp and OS.
3. The <Good Solution> aims to eliminate platform differences. There is one function for calling the OS irrespective of which Lisp platform you use, so that you can forget about whether its CLisp, CMU, Steel Bank, Allegro, Lispworks, Power Lisp, or MCL. It all works the same. And it runs under any version of Common Lisp and any OS.
4. The <Good Solution> keeps the good things of Lisp. You can write functions in S-expression syntax and you have full communication with the underlying Lisp.
5. The <Good Solution> has the features of a modern functional language. Pattern-matching, lambda calculus consistency, formal semantics and (optional) strong typing.
6. The <Good Solution> is as small as possible. The <Good Solution> imports from Lisp only those functions which are really needed. The idea is that the set of system functions should be the minimal set needed to provide computational adequacy. This is the way mathematicians work when they formalise any discipline - they adopt the minimum set of postulates needed to get the system off the ground.
   
   All the other stuff is hived off into libraries. This is nice for noobs. They feel that they don't have much to learn.
7. The <Good Solution> is computationally adequate. This means you can talk to the OS, write scripts, multithread and all the other stuff.
8. The <Good solution> is configurable to personal requirements. This is a strength of Lisp.
9. The <Good Solution> is well documented, clear and reliable

The Qi manifesto is really about making this equation true.

The <Good Solution> = Qi

In what ways does Qi meet the constraints of the <Good Solution>? We can see the Qi project as delivering the <Good Solution> using a structured time table composed of project phases. Let's see what has been achieved so far.

Phase I

Phase I began in April 2005 when Qi 6.1 was made publicly available over the Internet. It immediately generated a lot of interest. As a start it was a strong beginning on the good solution.

1. Qi 6.1 did not abandon Common Lisp.
2. Qi 6.1 was open source.
3. Qi 6.1 kept the good things of Lisp. It allowed free and easy communication with the underlying Lisp and you could load Lisp files into a running Qii image (modulo case). Qi 6.1 has an S-expression syntax (see chapter 8 of the online book for how to use it) as well as a higher-level pattern-matching syntax.
4. Qi 6.1 had the features of a modern functional language. Pattern-matching, lambda calculus consistency, formal semantics and (optional) strong typing are all in there. Actually the type system is way more powerful than ML or Haskell.
5. Qi 6.1 was as small as possible. The glossary of functions is small and so is the code size (6,700 lines of Lisp).
6. Qi 6.1 was configurable to personal requirements. You can extend the type system of Qi 6.1, import chunks from Lisp and even change the syntax if you don't like it.
7. Qi 6.1 was well documented, clear and reliable. The implementation had a text of over 350 pages with many examples, formal correctness proofs, BNF, semantics. Qi 6.1 was fast and strong enough to be implemented in itself.

Phase II

Phase II began about 18 months after phase I. People liked the work but the complaint was 'Why does it only run under Windows and CLisp?'. So phase II is about platform differences. The third constraint of the <Good solution> is

The <Good Solution> aims to eliminate platform differences.

Phase II has seen Qi 7.2 ported over Linux versions of CLisp and CMU 19c in January 2007. In April 2007, Qi was ported to Allegro Common Lisp and this became version 7.3. That same month Yaroslav Kavenchuk ported Qi to SBCL and joining his port features to the Allegro ones gave Qi 7.4. We now have a single release that runs over four CL platforms.

Phase III

Phase III is about computational adequacy. It means supplying Qi with what is missing from CLTL. The two target areas are

1. Graphics
2. Web Programming

Graphics is the target of phase III. By the later part of 2007, we should have a type secure connection to TCL/tk creating a new language standard Qi/tk with > 100 pages of documentation. In 2008 we tackle the question of web programming.

Beyond that is the clear blue water of the future.

Copyright (c) 2007, Mark Tarver
dr.mtarver@ukonline.co.uk