Tuesday, December 20, 2005

Lisp from the ground up

I sometimes try to think of how a Lisp system built from the ground up might look. It's a interesting exercise, because it mostly is a matter of scope. Plus, when you compare it to "modern" computer systems, there's a big leap between low-level systems and the high level we interact with. People expect graphical user interfaces, soundcards that work, mice, hard disk interactions, etc.


We could start at the lowest possible level: chip architecture. Can a chip be designed so that it's optimized for Lisp from the get-go? Would it look any different than the chips we have now? I'm talking about things below assembly language here--logic gates put into order to build an arithmetic logic unit (ALU) are one of the basic components of a processor. Can we/have we built similar modules that are meant for basic Lisp operations, like consing? We could have new instructions that don't make much sense for someone writing a C compiler, but would be heavily used for a Lisp compiler. C compilers were (presumably) designed around available assembly capabilities, which was in turn designed around machine language features and/or processor instruction sets. But what were processor instruction sets based on? Perhaps basic operations we were familiar with, like adding and subtracting. Perhaps also features requested from higher level languages, like C. Something akin to "It'd be great if we could have an instruction that did X". I'd suppose that majority of instructions nowadays are of the latter type.

But what if Lisp were the primary language, and chip designers heard "It'd be great if we could have something that consed for us." Would we have different instructions sets? My intuition tells me yes.

Now, the chip would probably still interact with peripheral chips (in hard drives, video cards, etc.) that are customized for that purpose, and which may be programmed in C or assembly, but because all their interactions are (usually) on a low level (bits and flags), there should be no issue with those interactions.

To do something like this would probably require starting with FPGAs and some Verilog/VHDL, and result in a custom-designed chip.

Next, we could define the ground as "any existing processor". That's fine and dandy, except there's a large number of processors and they all do things differently, optimize differently, and have unique instruction sets. The fastest way to do task X on a MIPS instruction set would be different from the fastest way to do it for an x86-based set. So, a Lisp compiler, to be truly effective, would need to be customized for each processor--indeed Intel releases their C compilers which happen to produce the most optimized code for an Intel chip. Try it on a different chip or use a different compiler and it's not so fast or compact. That sounds like a lot of work to maintain; however, it is do-able. Note that Movitz plans to do exactly this, but only for an x86 architecture.

Something I imagine trying for fun would be to make a Lisp system that runs on a smaller chip, like a PIC microcontroller, or an ARM-based chip. PIC would be nice for hobbyists and electronics programmers, but ARM would be nice for PDAs. Maybe it'd be best to identify their common instructions and hit them both. I, for one, would love to convert my Zaurus to a Lisp-based OS

After this, it gets fuzzy for me...I imagine a Lisp kernel, a Lisp OS, with a Lisp compiler and Lisp applications. But somewhere in there, we put in a GUI, making the leap to user-friendliness. How to do that while still maintaining Lisp-ishness, I'm still figuring it out. Maybe something akin to the way GNU/Linux distributions have a GUI yet you can still access the terminal (which I would equate to the Lisp toplevel). We'd also have many standard protocols in there, like USB and TCP/IP, communicating just as effectively as they do now with their C implementations.

I'm also still thinking about the namespaces and toplevel issues. As I'm still learning Lisp, I may not know about it, but there would need to be some way to keep everything from being exposed at the toplevel. Maybe something akin to a directory structure (or nested namespaces), much like how in the terminal, you have to be in a particular directory to run a program. Without this, the function and variable names would become unnecessarily long.

More thinking to go, feel free to add comments if you have thoughts of your own...

2 Comments:

Blogger Kris_Tuttle said...

Well we already had the Lisp Machine which was made in the 1980's I believe. There was also a Pascal Machine around 1979/80. As I recall they went nowhere because they were specialized and while they were neat for a few months soon general purpose machines outdid them at their specific tasks and of course were good for everything else too!

5/01/2006 3:55 AM  Edit
Anonymous Anonymous said...

The Lisp Machines were quite successful, I'd say. But the AI winter struck them hard, as well as the rise of Unix workstations did... But they survived as internal boards for other computers for several nex years, just because the SW was so unique...

Jakub Hegenbart

5/05/2006 6:27 AM  Edit

Post a Comment

<< Home