views:

2606

answers:

17

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.

+35  A: 

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.

Nick Lewis
I disagree, that the gains would be little. The gains in clarity and maintainability would be enormous (and I bet it would come down to a lot less than 11 million lines eventually), and the work would not be done by the same people who currently hack the Linux kernel, but by people who would otherwise not have been as interested in it.
rplevy
The people who would be doing the port, and who are not interested in systems programming, are likely much less knowledgeable about systems than the people who currently hack the Linux kernel. Also, what is unclear about C? Even disregarding the massive effort to rewrite the code, it would be an even more colossal task to test all of that code again.
Nick Lewis
rplevy is right; a rewrite in Lisp would almost certainly drop the LOC count due to the Lisp higher-level features.
Paul Nathan
Sure, it would drop the LOC count. It would also limit the number of people interested in working on it (since there are far fewer Lisp hackers than C hackers), and drive away lots of people.
David Thornley
I would say that you are not looking to "port" Linux to Lisp, but rather to write a kernel that would be compatible with Linux from the API point of view. Which may actually be possible, but still take years of effort and the kernel ABI isn't stable, so that'll be fun to try to keep up with each new version.
Earlz
+6  A: 

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.

Earlz
Sbcl is bootstrapped, compiled purely in sbcl, so that part is already done.
rplevy
To be specific, C was written to write the UNIX kernel in (replacing B).
R. Bemrose
Although, as Jerry Coffin pointed out when I accidently hit Add Answer insted of Add Comment, "B was never used to write a UNIX kernel. B was only ever put to minimal use, and only for some small utilities."
R. Bemrose
@rplevy, Thats quite interesting.. it means to compile your kernel inside your kernel, you'd have to have a Lisp compiler.. but thats the same as with C and gcc and yes, B was used quite briefly, but it was still used(I believe the first versions of cp, ls, ed, and other common utilities were written in it)
Earlz
Most good Common Lisp implementations have compilers. Some don't even have interpreters, and simulate it by JIT compiling. Replacing C with Lisp wouldn't be for the syntax, but for more general advantages. In general, Lisp is a much more expressive language than C, and would likely result in a much smaller kernel by LOC. Whether the general advantages of Lisp would compensate for C's closeness to the metal, in performance and in expressing all the stuff you need in the kernel, is a very large question.
David Thornley
+12  A: 

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 ;)

moonshadow
A: 

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

Maciek Sawicki
Actually, C needs a runtime environment, too. It is just already provided by the C-based operating systems.
Svante
@Savante: That statement makes no sense. We are talking about writing the kernel in C (or Lisp). The kernel does not have a runtime environment, it runs directly on the CPU.
Mr. Shiny and New
Mr. Sahiny and New: which means that it brings its own runtime environment. Take a look at the Lisp machines.
Svante
Lisp also runs directly on the CPU.
Rainer Joswig
@Svante: I guess I'm confused by your use of the word "run time environment". What is the runtime used for the Linux kernel?
Mr. Shiny and New
The Linux kernel is its own runtime. Code that is part of the kernel (or loaded into the kernel) are using those routines. A Lisp system can also provide its own runtime (memory management, interrupt handling, ...) as part of the Lisp system and use it.
Rainer Joswig
+11  A: 

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.

Svante
The Lisp machines failed largely because it was impossible to keep up with Intel and Motorola CPUs in performance. Running MCL on the Mac or Franz Lisp on Windows gave better performance and was cheaper (even for Franz). Implementing on the bare metal is probably impractical.
David Thornley
The problem was not the performance (that could have been fixed and was about to be fixed), but the cost. The question was not about the hardware, but the OS. The OS has been ported to emulators and today runs on non-Lisp hardware. The OS has not been ported to a native machine - that would be possible - but there is no funding for that, and the interesting sources are not 'open source'.
Rainer Joswig
+1  A: 

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.

Paul Nathan
+11  A: 

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.

Mr. Shiny and New
I'd say enthusiast, not troll. 1. This can be tested. 2. Millions of programmers have never given Lisp a fair shot. 3. There's nothing you can do in C that you can't do on a Turing machine simulator. This argument is a non-starter. 4. Lisp normally uses garbage collection, but can handle its own memory. 5. This is the good reason. 6. Since you don't know Lisp well, or SBCL in detail, you're hardly in a position to criticize it for missing features.
David Thornley
@David Thornley: 1. It's not up to the Linux devs to prove that Lisp isn't as fast as C, it's up to the Lisp folks to prove that it IS as fast. 2. Maybe true, but not that relevant; the more obscure the language the harder to get programmers. That's pragmatism. 3. The question claimed that Lisp could do things C cannot. False. 4. Fine, but then isn't one of Lisp's advantages lost? 5. Glad we agree on one thing :) 6. I'd love to be educated on how to control the precise size of data structures in memory in Lisp. This is one thing I know the kernel devs actually do frequently. A link would do.
Mr. Shiny and New
A typical Lisp system provides a Foreign Function Interface (FFI). It usually has constructs to define data types. Like this: http://common-lisp.net/project/cffi/manual/html_node/defcstruct.html#defcstruct In a Lisp OS there are similar constructs to define such types (to interface to hardware or network services). But other types defined by the OS for itself just uses Lisp objects (CLOS, Flavors, Structures, ...).
Rainer Joswig
+7  A: 

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.

David Thornley
+3  A: 

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.

Pillsy
+3  A: 

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.

Jerry Coffin
+39  A: 

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, ...: alt text

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.

Rainer Joswig
Paul Nathan
Paul, it simply does not fit. You could pound a square peg into a round hole with lots of force. But the result would not be pretty. Huge amount of work, alone providing the interface would be a lot of work with lots of internal bit fiddling.
Rainer Joswig
The problem with real array bounds checking is that it takes code and execution time at runtime. For most purposes, this is just fine, but there's stuff in the kernel that really needs to run as fast as possible, and so the correct approach is to set things up so the index will not be out of bounds and prove that that works. C is at least close to a sweet spot for kernel hacking: it's darn close to being a multi-CPU assembly language.
David Thornley
We have to pay for the lack of bounds checking every day. People run slow stuff like Ruby on top of a fast unsecure kernel. A bad match. I don't even have the choice - all typical Unix OS variants are compiled without bounds checking. I would use that - even if it is a few percent slower.
Rainer Joswig
Bounds checking alone will not save an OS or make it secure.. it only takes some of the load off the programmer.
Earlz
That would be a start.
Rainer Joswig
As I understand it, typical Lisp systems were circa 1978-1990. So a real modern Lisp OS will look different both from the historical lisp OS and from the Linux...
Paul Nathan
Could be. If you could find funding and people for that? Currently it is not even possible to get the existing stuff improved or copied.
Rainer Joswig
@Rainer - You're completely wrong. Kernels need to be fast. If they took the time for bounds checking, they would be unbearably slow. Saying "performance doesn't matter" won't convince your customers who are waiting for their program to finish (or web page to load) because your kernel is more "secure" because of it's bounds checking. The frequency at which kernel code must be used, combined with the overhead of bounds checking, means that, in certain areas, we have to go with something that is either a) provably correct, or b) works as far as we (the users) can tell.
Chris Lutz
Chris: @You are completely wrong. Not everyone needs the fastest kernel. There are tradeoffs. If your financial data server gets hacked, 'fast' has not helped. Last years our computers were half as fast. They worked, too. What have we used the speed increase for? Some wished it would have been used for a safer infrastructure. Instead it is wasted in slow scripting language driving the web sites. If speed really mattered, Ruby, Python, Abap, and all this stuff would not be there.
Rainer Joswig
Runtime bound checking is retarded. You need it only for code that is buggy in the first place. I manage a multi million LOC project in C and not once in the 8 years I worked for that project would a bound checking have helped to find a bug. Are there array bound overflows in our code? May be, probably not much. Would it matter, not in the least, would the wasted time matter, yes a lot. If bound checking matters to you, go on,play with Java, Pascal and others, but let us our C which allows us to get as near as bare metal as it gets.
tristopia
@tristopia : the damages done by security leaks in C speak another language. Every day hackers find the most primitive bugs in widely used software written in C. It is already kind of a sport. Many of these problems come from buffer overflows. That's a fact. That you think your software doesn't have this problem doesn't matter. The problem reports for many popular C-based software shows the huge scale of the problem. People like you should be kept far away from any security relevant software.
Rainer Joswig
People that write _bad_ C should be kept far away from any security relevant software. LISP is not better than C. It is different. Some people prefer C, some prefer LISP. Get over it.
mathepic
Thanks for the picture!
Liran Orevi
+3  A: 

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.)

L33tminion
+1  A: 

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?

wgl
+1  A: 

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

lnostdal
+3  A: 

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

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

I kid, I kid.

Chad
Hahaha, you earned my +1 for that. Thank goodness emacs was around in my undergraduate days.
ChrisInEdmonton
A: 

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.

Silvanus
A: 

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.

jrernst