LISP on the Propeller?
rwgast_logicdesign
Posts: 1,464
I have been reading about LISP a lot lately and it seems like a very intresting language well suited to some of my needs, more so in the embedded world than on the desktop though. I know GCC supports many languages and if I am not mistaken LISP is one of them (I don't see why Stallman's favorite language would not be part of his most famous contribution to computing), anyways I was wondering exactly how feasible is it to compile other languages than C using Prop GCC?
Comments
Actually I don't think there is a LISP front-end for GCC. There are Fortran, Pascal, Go, Ada, Java, and of course the C family (C, C++, Objective-C) front ends. I'm sure the GNU project has a LISP compiler, but it doesn't seem to be integrated with GCC.
The hard part of getting any of these to work on the Propeller is the language specific library. I've made the Fortran compiler itself work for the Propeller with little effort (just some config file changes), but the GNU fortran library that was linked with it caused the program to be far too big to be practical on the Propeller -- a simple "hello world" program was several hundreds of kilobytes, if I recall correctly.
Eric
I think the thing is that GCC is based on the idea of compiling source code down to natively executable binaries. As such it does a great job of compiling the languages Eric mentioned and can produce executables for many different processors. Quite amazing really.
But then we have languages like Lisp, Scheme, JavaScript etc that are traditionally interpretted or perhaps compiled to byte codes or compiled on the fly as they run. Just In Time (JIT).
GCC is not a good fit for those as they need a big run time engine where most of the real work is done. Seems to me the very semantics of the languages mitigates against compiling to native in the GCC way. For example in those languages you can create functions on the fly (Lamda's) which you can the pass around to other functions. How is a regular one time source to executable compiler supposed to do that? No it needs to be done at execution time.
Then we have things like closures in Lisp, Scheme, JavaScript etc that determine a functions environment (The variables it has access to) dynamically at run tim.
One biggie is that compiled languages are generally statically typed. You declare a variable as an integer and it is always an integer. A compiler like GCC can track that in your program and ensure you use the variable correctly and it can generate optimized code to operate on your variable. Where as these other languages have dynamic type, a variable can change from number to string to object reference to undefined many times throughout a programs running time. A compiler like GCC cannot deal with that. You need a sophisticated run time engine, interpretter to do it.
Stallman did get his Lisp. First he wrote the GCC compiler with which he could compile his Lisp run time, the Emacs editor. (Or did he write the editor first?).
Back to the question. Can we use Lisp on the Propeller?
Firstly I would not go for Lisp. I would go for Scheme which is a modern dialect of Lisp. Scheme is quite well supported now a days and is still used as a teaching language in places like Berekey. Scheme does everything Lisp does but in a nicer way.
I don't know of any compilers for Scheme (or Lisp) to native probably for the reasons I mentioned above. But there is at least is a Scheme compiler that compiles to C which can then be compiled with GCC. Potentially that is a way to get Scheme running on the Prop.
However it will be:
a) Slow as hell.
b) Require huge amounts of memory to run.
Here is Chicken scheme.
http://call-cc.org/
Here is it's C API:
http://wiki.call-cc.org/man/4/Embedding
All of which looks interesting, I might have to try it out myself.
Gambit: http://dynamo.iro.umontreal.ca/wiki/index.php/Main_Page
And here is an oldie:
scheme2c: http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/impl/scheme2c/0.html
with recent updates and a Debian version here:
https://github.com/barak/scheme2c
a) The run times are big. They are interpretted languages that rely on a heap and garbage collection.
b) Being interpreted they are slow.
c) Being garbage collected timing determinism is tricky.
d) Not many small programs in such systems need closures, or lambdas or recursion. Most embedded programmers don't even know what these things are or why they might need them.
e) A lot of programmers rebel at the syntax with its mass over brackets. Especially lisp.
I think that from a purist computer science perspective they are wonderfull. Especially Scheme.
I'm kind of tempted to play allong with your idea of trying out Scheme on the Raspberry Pi, Perhaps see what can be done with Chicken Scheme.
Of course many of the Scheme like features, first class functions, closures etc are to be found in JavaScript which runs very well on the Pi with great performanc due to Node.js and it's Google V8 JavaScript engine. Hard to beat and what I am using on ARM boards in comercial developments.
http://tinyscheme.sourceforge.net/home.html
-Phil
http://armpit.sourceforge.net/
Armpit Scheme
or PICBIT Scheme
http://lambda-the-ultimate.org/node/3694
references a nice article which shows how it is implemented on the micro
True none of them is for the Propeller, but both are implemented bare on the metal and can deal as a template to learn from when someone really wants to implement something similar on a prop.
Seems you are right. Sniffing around the net one can dig up projects that have implemented Scheme like systems on PIC, AVRs ARMs, Lego MindStorms.
Actornet is another example:
http://osl.cs.illinois.edu/actornet/
All kinds of things out there. Amazing.
Of course all of this is impossible on the Propeller:)
If you are into such things there is a great course in Scheme and introductory computer science on YouTube by Brian Harvey at Berkeley. It's the Berkeley CS 61A course.
http://www.youtube.com/watch?v=jgEjm-eOWaw&playnext=1&list=PL3E8F114DBE59CF1D&feature=results_main
Note: That play list has some lectures in the wrong order and a couple missing. I think you can find the missing ones though.
I could listen to Brian Harvey all day.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/
also the book is available for free (myself I have a dead tree version)
http://mitpress.mit.edu/sicp/
http://dspace.mit.edu/handle/1721.1/6334
I think what they are really referring to is that LISP has an "eval" function that can execute LISP expressions.
This allows writing LISP code that is self-modifying.
So it may be better to say that a full version of LISP that includes the eval function may be very large and not well suited for a MCU environment.
C.W.
That would be me.
I sort of stand by what I said. Historically microcontrollers were 8 bit and had a few K bytes of memory. Many of them still are. Now Bill Gates showed with his 4K BASIC that you could indeed have an interpreter on such a system but what you end up with is very slow and leaves not much room for you application code. Why waste your resources when you can code your app in assembler or some HLL like C (or PL/M back in the day)?.
The Propeller is a whole other ball game. It's huge by comparison. Eight processors, 32 bits. 32K HUB wow. On the Prop you have the luxury of being able to have "slow" interpretted code running in a COG or two and another bunch of COGs available for the high speed work in PASM. Not to mention getting rid of all the pain of interrupts.
It's a different world and I think Spin fits there very well.
I do think LISP on a propeller would be more than possible, Im not sure what kind of hardware went in to the original M.I,T LISP machines, but assuming they were mini computers comparable to old PDP systems a propeller has much more power! If one were able to interpret LISP speedily and allow code execution from RAM in the way some of the GCC models do, a decent LISP interpreter should be a reasonable thing for anyone with compiler experience to build.
I had actually thought a decent way to work with LISP in an embedded setting may be to just use a 68k cpu with some RAM, maybe even a pre-built M.I,T handy board, I know there is a pocket LISP for the TI89 and old Palm Pilots which use 68k cpu's. Maybe a pretty cool system would be a propeller a long with a 68k and some ram. Basically set up like the 6502 laptop or the Briel Apple 1 clone, only with a 68000 instead of a 6502.
Just been kicking around different idea's on the best way to make this work. I don't expect anyone to actually write a full featured LISP interpreter/compiler that is propeller compatible as David says there probably is no audience for this, I am some what surprised Fourth has one. Like I said I think learning LISP from SICP is a great idea for anyone who wants to sharpen there skills, but I do not see myself using LISP for much on a desktop. I do however see LISP skills carrying over to the robotics world and AI, I guess this is why I am surprised there aren't many embedded LISP computers with robotics and AI being so popular. Im sure C/ASM is a much better choice for writing drivers, reading sensors, controlling motors, etc, but in some "Intelligent" type hardware products LISP may be the better choice for the LOGIC that calls all those drivers.
Now I just heard of and started using Parallax products a bit over a year ago. Before that I had NOOOO idea what a micro controller even was! Unfortunately by the time I started buying and learning parallax products the Javelin was discontinued and marked down so they could sell off there remaining stock. From what I understand the Javelin was an SX chip running a boot loader that had a Java interpreter, or it used pre-compiled Java? At the time I was interested because it looked like a fun way to learn Java, but I never bought one due to the fact the product was being discontinued and there did not seem to be a lot of educational material for it.
So this LISP conversation got me thinking, about micros and there limitations. I remember reading a a question in the general forum by a guy who wanted to know if he could program the Prop with Java. The answer given was much like the one I have received about LISP. The consensus was that Java and it's library's are two big, simple programs would be huge, the language has to much overhead an example being garbage collection (a lot of the same problems as LISP). Python is another language I have wanted to see on a micro, and I found a version that works with AVRs if I remember right, but it is soooo limited to keep size and overhead down that it almost seems pointless!
So how is it that the Javelin on a single core SX was able to run some type of Java, but most would agree Java on a propeller is impractical AT BEST, and impossible at worst? I would think getting languages like Python and LISP to run on a micro, even an 8mhz AVR/PIC wouldn't be such a big issues as long as the language was stripped to it's core commands and the library's were re-written from the ground up to be smaller, and more relevant to the micro controller. Or what about even writing a PC based compiler that would allow one to write a program in a mostly interpreted language like Python or Perl and then compile it down to compatible machine code? I have never written a compiler, or anything that interprets bytecode but are the things I am asking about actually impractical to impossible or are they just such a programming fight that most people don't want to bother?
In most of the object oriented languages, the use of the heap for object creation mandates garbage collection which as Phil mentioned earlier is a cause for non-deterministic operation unless you dedicated a core to garbage collection. There are also often very large stack demands as procedures are called and the stack frame is called on to support the creation of variable space in the new scope. This is all expensive to the processor and can bring large servers to their knees if poorly used....think of the mpact on a micro...and again to what end.
If you want to experiment with languages (and I do love to play with languages just for the sake of trying new languages), load up Linux on an older laptop or grab a Raspberry Pi. If the language does not bring a benefit to the micro, unless it's just an exercise in FUN, stick to efficient micro languages that let you leverage the hardware for an embedded application.