|Kl and the Development of Qi : Richard Gabriel's Unfinished Revolution|
|For those new to this topic, the
roots of this project go back to an address
delivered to European Lisp Symposium in May 2009 in which
I was addressing the problems of Lisp and how to meet
them.. In it I said.
I called this prototype language Shen.
In November 2009 Carl Shapiro wrote to me about moving Qi to run on mobile devices and I have agreed to help him.
This Lisp code is, in fact, a very restricted subset of Lisp, close to the heart of Kl. Hence Carl's project for running Qi on mobile devices brought me out of retirement in the mountains of India and back into the world of the twenty first century.
Completing Gabrial's Vision
Shen is virtually the same as Qi. It is Qi conceptually seperated and liberated from the bonds of running only in Common Lisp. For this reason (and to avoid renaming the news group) I've stuck to the same name. However that seperation does have some significant consequences. Let's go through them.
The first is that without CL as a platform, we cannot assume that certain bread-and-butter functions will exist in the platform as they do in CL. For example, if somebody wants to read from a stream, Functional Programming in Qi (the standard language guide) does not tell them how to do it. For that they have to dive into CL and read the CL language guide. But if the platform is not CL then the answer may not be so well defined. Generally this is not a good thing. We want differences in the underlying platform to be invisible with respect to commonly required tasks. People should not have to fumble around in unfamiliar languages to do that or find that they have to rewrite code in order to move it to their favourite platform. So this means filling in the spaces that Functional Programming in Qi left blank - how to create and call streams, how to query the OS and so on. In the long term it means seriously thinking about what 'computational adequacy' really means in the C21; what functions are really needed.
The second aspect has to do with the primitives in Kl. We want to aim for a small instruction set. Kl should be as compact as possible so that Carl and people like him can write compilers for Kl without having to build a cathedral. The huge specification of CL proved a hindrance to implementors. I'm fairly certain the vast CL spec is the reason why the ABCL project has taken up so much time and is still incomplete - too many things to get right (or wrong). Hence we should aim at simplicity, even starkness in the primitive instruction set, and move as much of the action into an open source standard library as possible.
When I gave my ELS 2009 address I did not mention Richard Gabriel's famous 'Worse is Better' essay. I read it a long time ago and had partly forgotten his brilliant analysis of what direction Lisp should take and just remembered the 'worse is better' angle. But on rereading the essay recently, I stumbled on the section 'The Next Lisp' which fits so well with my analysis and the direction I am taking that I can only conclude it must have lodged in my hind brain all these years. Hence I call this page 'Richard Gabriel's Unfinished Revolution', because we aim to finish it.
So how do we proceed?
Qi III Becomes Self Compiling
The first step is to make Qi self-compiling; that means Qi becomes 100% written in itself. That's not too hard because 90% of Qi is written in itself. So that's a task for me and it shouldn't take that long.
The second step is to make Qi generate Kl and that is easy because Kl is really defined as what Qi generates. In the internals of the Qi compiler, Kl is already generated and it is mapped to CL with the additions of quotes and so on. So by simply omitting the Lisp back end, we get Kl. By running Qi-in-Qi through Qi (slightly boggling to write), we get Qi in Kl. By mapping Kl to Blub we get Qi running under Blub (and for Blub read Clojure, Python, CL, DVM etc).
The third task can be done in parallel to the first two and that will be the specification of the primitives of Kl. We can predict just from the language specification for Qi that certain functions will be needed (e.g I/O), so we can usefully discuss in public forum what these should be keeping in mind that parsimony is a virtue and that stlib can contain the standard utility functions.
One thing that is clear right now is that defining these utility functions will make heavy use of recursion and that, in some cases, these will not execute properly in a language lacking tail recursion optimisation. Python lacks this feature but I'll come back to this later.
Expansion Slots in Qi III
One thing is clear already about Qi and that is that people enjoy experimental programming in it. Trying out new language features and customising your programming environment is healthy and natural. But we want people to be able to do this without having to dig up working source code and, in hacking it, introduce errors into a working system.
To give an analogy, when you buy a laptop, you have expansion slots for more memory. If you need more memory, you don't whip out a soldering gun and a pair of cutters, you buy a chunk of silicon and plug it into the expansion slot. The problems of the soldering-gun-and-pliars approach is that you run the serious risk of screwing up the machine and it takes a lot more work.
Ditto, digging up working code in Qi and hacking it to add a feature generates more opportunity for error. Another argument against it is that it creates non-portable solutions. People running Qi cannot just load your ideas and play with them like any other program. We want to be able to experiment and share ideas without creating zombie versions of Qi. We want a common core, like a strong rhythm section, around which people can play fantastic software riffs.
Now Qi already contains expansion slots in the form of provision for experimenting with new syntax via input sugar functions and changing the printed appearance through output sugar functions. To this we should add programmable pattern matching within type secure limits.
and most significantly a programmable back end that will map Kl to Blub.
Within the back end will occur many of the optimisations currently performed within Qi itself. For example, using EQ to compare symbols. This sort of thing really belongs to the back end where knowledge of the platform is at a premium. Within the back end will take place decisions of how to use the type annotations that Qi can insert into Kl code. I should also say that factorisation of overlapping patterns to eliminate redundant testing will also go into the back end. The reason for this is that factorisation depends on something like a GOTO with the object code and we cannot safely assume that every platform will have it. So into the back end goes just about all of the optimisation because it is mainly platform dependent.
For Qi III I'm moving the license from the book and making it universal to all. This is not because of some road-to-Damascus conversion to the open source/GPL lobby. I still think, as I have done, that they have serious holes in their case which have not been addressed. My reasons are pragmatic and not philosophical; it works in this case.
There is not much daylight between having the commercial licence in the book and having it in the code - actually £24.50. And people wanting to use the language for commerce will surely need the book anyway and in buying the book they got these rights. But people were wary that the book might go out of print leaving users stranded. Making the book license universal takes away that fear.
More significantly perhaps, I wish to avoid people 'liberating' the code by producing poor copies in the name of open source. If we have a single song sheet from which to sing, even if we sing off key, the sound should not be that bad! So the license gives universal commercial rights and forms the departure point for future work.
It takes time to develop open standards so the time frame for some of these developments will be slow, but some of the work will be fast. Qi I began in 1989 and was issued in April 2005 - 16 years. Qi II was issued in November 2008 - 3 years and six months. Following the progression we can expect Qi III to appear within 2010 and I would predict that self-compilation will be complete before the end of February 2010.
At the point that self compilation is complete we will have a small Kl - KKl if you like, which is likely to remain fixed. We will make this an open standard for people. At that point, when KKl is generated and defined, we will publish an open standard and easy instructions for anybody wanting to port Qi III to their target platform by mapping KKl. People can then freely build their own back ends. I think this open model is more logical than weighing any one person down with the responsibility of porting to language X and I cannot do all the work myself! I'll post to the relevant news groups when this standard is complete. This should appear very soon.
When that is done my main part in coding will be done. But that is not the end of my work because Functional Programming in Qi needs to be rewritten to meet any changes in the language standard and that will come out as a third edition.
However even then the work as a whole will not be done, because KKl is really only a subset of Kl. And the rest of Kl, which Gabriel talks about, and which must be what I called computationally adequate, needs to be thrashed out piece by piece in open forum. This will take time. So I will be around to mentor these discussions, in hopefully a light touch, because there are people who know more than I about odd corners of FPLs concerning streams etc. who should be able to make a contribution. So for people from comp.lang.lisp, clojure, python etc, this is the chance to show what you know and shape our development.
The other part of my work is to encourage the formation of libraries which should, as far as possible, run under KKl (or equivalently Qi III). In that way they will be guaranteed to run under every platform (Python, Clojure, CL) that the backenders can assimilate. I'm quite happy to put up people's code on Lambda Associates and, to guarantee the site stays open, Carl is arranging a mirror at Google.
Hence for Qilangers, 2010 should be a very exciting year. Hang onto your hats; we are going to hit the accelerator.
Copyright (c) 2010, Mark Tarver