Why not port Linux kernel to Common Lisp?

Question

Conventional wisdom states that OS kernels must be written in C in order to achieve the necessary levels of performance. This has been the justification for not using more expressive high level languages.

However, for a few years now implementations of Common Lisp such as SBCL have proven to be just as performant as C. What then are the arguments against redoing the kernel in a powerfully expressive language, namely Common Lisp?

I don't think anyone (at least anyone who knows what they are talking about) could argue against the fact that the benefits in transparency and readability would be tremendous, not to mention all the things that can't be done in C that can be done in Lisp, but there may be implementation details that would make this a bad idea.

Answer 1

But you see, someone's already written the Linux kernel in C. Around 11 million lines of C. Porting it to Lisp would be far too much work for far too little gain.

Answer 2

Are you sure you don't mean "all the things that can't be done in Lisp can be done in Assembly"?

The reason that the linux kernel was written in C in the first place was because C is a systems programming language. It is basically the equivalent of machine independent assembly code.

Porting the entire linux kernel to Lisp would be quite the undertaking.. I'll see you in about 5 years or more..

You can write a kernel in almost any language, but you must remember that some are more suited than others. C was designed just about for writing kernels. Lisp wasn't. Sure, it's possible, but it will be harder, no matter how much cleaner you consider the syntax. And you will still have to have assembly bits here and there for doing machine specific stuff(loading GDT, IDT, inport, outport, Interrupt stubs)

I assume that Common Lisp can be compiled. It would be much harder if it was interpreter only, as you would first have to port a Lisp interpreter(written in C or Assembly or some other "native" language) to bare-metal, which is basically like writing a kernel to load your kernel.

Answer 3

It is a complex piece of code that already exists. Change is risk, so generally requires a good reason in order to happen.

Is there a good enough reason here to scrap and rewrite what there is? What do you hope to gain by doing so that would begin to be worth the cost of rewriting and testing and the risk of replacing a mature codebase with a completely new one?

No-one's stopping you, mind ;)

Answer 4

I don't know much about Lisp, but doesn't it need runtime environment? If yes this is the answer why we cant do it.

I'm also not sure how would it affect on system api. We probably would have to rewrite user space apps

Answer 5

There are projects that aim to implement "Lisp on the bare metal", e.g. Movitz (there were also the famous Lisp machines). Having Lisp in such a central role would also mean significant changes to how the system is designed, e.g. having a garbage collecting memory system, different library interaction etc..

So, you wouldn't port any OS to Lisp, you would write a new Lisp OS. I would be very excited if that becomes usable.

Answer 6

I don't know that it could be ported. The language paradigms themselves are quite different. I would say that having a Linux-compatible clone that maintained interface/binary compatibility for drivers and applications is doable.

Why is Linux in C? Because C compilers exist for pretty much every architecture under the sun. Further, the writer of Linux famously prefers C.

Answer 7

I strongly suspect you are a troll for using such inflamatory wording, but I'll answer nonetheless.

There are several things wrong with your premise:

1. You claim SBCL is as performant as C. What does "as performant" mean? In the kernel world even a 1% or 2% performance regression is a major problem.
2. Lisp's readability is one of those things that is highly trumpted in lisp circles and otherwise disbelieved. I have a Computer Engineering degree and studied Lisp and C in school and can honestly tell you that I find Lisp harder to use. I'm sure millions of programmers agree with me. C is not the best language ever but neither is Lisp.
3. There is nothing that can't be done in C which can be done in Lisp. Some things may be easier to do in Lisp, but since you can write a Lisp engine in C then C can do anything Lisp can (and more).
4. Garbage Collection: GC is great but not well suited to applications which require specific deterministic performance. The Kernel falls into this category.
5. Rewriting code is hard and porting is harder. Changing code for the fun of it introduces bugs (this is a guarantee) and reduces features.
6. C lets the developer tweak even the tiniest detail. This is critical when you need to do things like ensure that a data-structure fits in a cache entry for your target processor. How do you do that in Lisp? Is it even possible? These are details that kernel developers have to deal with all the time. Kernel developers are still counting bytes.

In short, porting the kernel to Lisp would bring: reduction in readibility, performance loss, reduction in available programming talent, fewer features, and more bugs. That's why nobody will do it.

Answer 8

There are the basic arguments against porting any very large project to a very different implementation.

Right now, we've got a whole lot of C code that is extensively used and battle-tested. Rewriting that in any different language is going to introduce bugs. Lots of them. It would be years before the rewritten kernel would be anywhere near as good as the original.

Moreover, in order to get any benefit from it, it would be necessary to simply rewrite large portions of it to take advantage of Lisp's greater expressiveness. That increases the amount of effort and the number and severity of bugs introduced.

At the end, we'd have a Linux kernel designed in C and written in Lisp. I just don't see a great benefit here.

Moreover, the people most familiar with the kernel are experts in C, and there are a whole lot more C developers than Lisp developers, so you'd be changing the people working on it to a much smaller and less experienced group.

The right way to do something like this is to forget about rewriting, and simply write a new Linux-compatible kernel in SBCL. Look at the complete ABI for the Linux kernel at some version, determine what it needs to do, and treat those as specs for the SBCL kernel. It will wind up well behind the Linux kernels available when the project's finished, but if writing the kernel in SBCL does work as you hope it should be possible to catch up. The proof of whether this is worthwhile or not will be any acceptance of the new kernel.

Answer 9

It would be pointless. This isn't because Lisp can't be used to write an OS (there are existing examples of OSes written in Lisp!) but because rewriting big, complicated pieces of software just because you like some other language better is an extremely good way to waste money, effort and time.

Answer 10

The short answer is that the reason it hasn't been done is that nobody has done it. If somebody (e.g., you) wants to do it badly enough, there's nothing to stop them/you from doing so. You never know: the project might be a wild success, and someday I'll be able to say: "I was the one who really got him to do it..."

At the same time, I feel obliged to point out that most attempts at starting open source projects seem to fail, and at least to me this one seems more like to fail than most others. The single biggest shortage (in most cases) is people to sit down and just hack out large quantities of code, most of which is ultimately pretty boring, but still has to be written (and written quite well at that) before you get a working system. The relatively small number of competent Lisp hackers leads to a bit of a problem right away. Unfortunately, an OS can't avoid a fair amount of code that has to work close to the "metal", and it's often (usually?) difficult to use a lot of higher level features to keep such code as compact and elegant as you might otherwise do. In other words, for things like device drivers, you're probably not going to gain as much from using Lisp as you'd expect from writing other kinds of code.

Then you have to find a development system (or more than one) that's suitable for the task. Something that lets you generate output that can run without any assistance from anything else at all. While there's no question that such a Lisp development system could be written, I'm not at all sure that there is such a thing (especially one that's freely available) today.

Third, you have to deal with the fact that many Lisp hackers have a relatively narrow view of the world. Many of them tend to latch onto very specific problems, and want to solve those problems as close to perfectly as humanly possible. Especially in the early development of something like an OS kernel, nearly the opposite is needed: write something that's barely usable as quickly as possible, so you can work on the other 10 zillion things that need to get done, and have something that's finished and working before it's obsolete.

Answer 11

There are possible variants of this question. Let's first ask what is the 'Linux' kernel. Linux is basically some variation on Unix. The Linux kernel provides services as memory management, ...:

The kernel parts and the interfaces all assume some C compiler and C language conventions are used. A C compiler can generate a compact executable.

Now things get difficult in Lisp. It shows in SBCL. Fixnums in SBCL are 61bit and not 64bit. Some bits in data are used for tags (and possibly other things). SBCL programs start at multi-megabyte size. Characters are not bytes, but again tagged data. Most Lisp implementations use tagged data, because the data needs to be identifyable at runtime - in Lisp.

C has very different data structures, etc from Lisp. If you write something in Lisp it would by default look very different from C code. Wouldn't a scheduler be best a CLOS object? Tasks? Timers? But the interfaces of the Linux kernel look very different. You would program very primitive data structures in a language that has higher-level data types (like CLOS). That's not a very good fit.

So, can you define a Lisp that is nearer to C in its capabilities? That's possible. There are some examples.

Also, can you write an OS that would not look like Linux, but is written in Lisp and is more idiomatic? That's also possible and has been done before.

The typical Unix (and Linux) OS 'kernel' does a few things that were not done in the typical (existing) Lisp OS: different applications with their own memory space, multi-user capabilities, ... that would be new ground for a Lisp-based OS and had to be invented first: how to provide multiple independent Lisp applications on top of a Lisp OS and not lose the advantages of a typical Lisp system.

Probably it would be better to not write an OS in C (for example one might want a language and implementation with real array bounds checking) - but the language better be near the C model - otherwise lots of knowhow is not transferrable. Lisp solutions usually look very different.

A real Lisp OS looks very different.

Answer 12

Other posters have enumerated the problems with designing a kernel in Common Lisp (or SBCL specifically). And there are many good reasons why porting the Linux kernel to another language is almost certainly a bad idea.

That said, if you were picking a language in which to write a new kernel, Lisp has something very strong going for it: A Lisp-style macro system is incredibly useful in large-scale software systems. I've found that the resulting code can be much shorter, clearer, and easier to optimize.

If I were implementing a kernel, though, Common Lisp still wouldn't be a first choice. For one thing, I'd also like a strong type system, and if the language in question had garbage collection, I'd want that to be more efficient and predictable than the garbage collection in SBCL evidently is.

(Note: I use Common Lisp for hacking on a large-scale project at my job, but I know little about the Linux kernel or the internals of SBCL, so my knowledge about the flaws of SBCL garbage-collection is second-hand.)

Answer 13

Certainly an OS can be written in Lisp. It is not clear what the point of rewriting Linux in Lisp would be, however. There are certainly enough competent resources dedicated to making Linux highly useable, effective, and popular.

The suggested benefit of being transparent is likely a non-issue, as you can see all the source code, read it, ask questions about it. If it appears to be not "transparent", it is likely that is because it is a very ambitious project that accomplishes a tremendous amount. So the problem of transparency is really one of familiarity. Read the code until you understand it. Even if you get an 8-fold reduction in LOC (a sheer guess) then it will still be a significant task to wrap your head around.

Regarding Lisp being as performant as C, this may not be as true as that statement implies. Certainly we can look at the microbenchmarks to see how they compare on small problems, but the real traction of improved performance would be found in really large engineering efforts where strengths of Lisp make a bigger difference.

Perhaps Linux focuses too much on the 1% performance differences. There have been good suggestions made about how to improve the reliability of the kernel and reducing its monolithic nature (cf Tannenbaum), and these are met with rigid resistance.

I think a more interesting question would be to approach the idea of an OS fresh and ask what we want it to do. Is there something more interesting we can do with a Lisp-based OS that Linux is not doing? If so, what about all the programs that you would want to run that require Linux or Unix ABI?

Answer 14

It would be much more worthwhile working towards making Linux & SBCL (or some other Lisp if you want) communicate better with each other.

Answer 15

Because Linux is open source, and no one wants to read source code when the last page of it is:

)))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))

I kid, I kid.

Answer 16

Wouldn't it be much more feasible to write lisp macros for generating C code for the Linux kernel, and slowly replacing original C source files?

... Hmm, I might just try that out and see if there are great advantages (I'm not the most experienced lithper T_T). Would there be any great licensing problems in committing generated C code? What if I tweaked it? Not so much that I'd be unhappy to release it, just.. I'm not sure there are any kernel developers who'd enjoy building my lisp code.

Answer 17

I strongly disagree. It is possible to use Lisp to write a linux kernel. The key is not to run it in Lisp. Imagine the kernel written in Lisp. Then transform this code to C with a mapping function. Then compile C and that's it. You gain: verification of the kernel in Lisp. No errors in C because C code is generated. You only have to prove that your mapping is correct.