Embedding Scheme On Palm

From LispSchemeDifferences:

There are several existing scheme and lisp implementations that are designed to be embedded into an application -- Guile, Librep, DrScheme, MzScheme, etc.

I want to embed it on a PalmPilot. Not quite the same thing. ;) I think I just figured out how to resolve the scopes lexically at parse time without causing a lot of fuss. When I encounter a </script>, I should evaluate it then, not at <script> like I thought I had to. This is a major "duh" moment for me, so please don't laugh. -- SunirShah

Have you looked at LispMe? http://www.lispme.de/lispme/ Source is available but I can't check exactly what licencing terms it's under. --DanBarlow

It's GPLed, and therefore tainted. I cannot look at its source, so that doesn't help me. Bummer. I did notice this:

: a typical garbage collection of 16k heap takes about 0.2 seconds.

groan. I didn't think it was that bad. Maybe it's just his implementation convoluted for the completeness of his implementation. Our goal is to run the script as part of the draw/animation loop for http://research.bitflash.com/sdvg. 0.2 seconds is a lot of time--i.e., it's perceptible.

I'm aiming to implement the whole thing in less than 4kb of compiled 68k instructions. The best Scheme version we saw was 22kb. So, if I implement a Scheme, this may involve throwing out support for such things as call/cc, which is fine with me because I still don't understand it well enough to implement it. My target market is graphic artists, so Scheme may be pushing sanity as it stands. (The other major alternative was Forth, but that is insane.)

I probably also have to implement it heap-efficiently as the RIM Blackberry's performance degrades as the heap fragments.

I think I'll have to implement it to see what's possible and not possible instead of just doing BigDesignUpFront (more like Big Procrastinating Up Front) like I am now. --SunirShah

I think that LispMe's GC is really optimised for space efficieny, not for fast GC. LispMe uses a simple mark-and-sweep GC; a generational GC which uses copying for "eden" would probably result in unnoticable GC delays. But such things are not trivial to write, and might not fit in 4kb.

You could consider using ForthLanguage instead. It's easier to implement than Scheme, and works well in small footprint environments. It doesn't have GC. But it is a weird language and I still don't fully grok it.

What about a (subset of) Postscript? Some of your intended audience (graphics artists) might even be acquinted with it. -- StephanHouben

I'm surprised mark and sweep isn't fast enough. As the LispMe website points out, any copying GC won't work due to memory constraints. It will also fragment the heap faster, which is brutal on the RIM. But then again, I might just have to do the memory management myself.

PostScript would certainly make our main competitor happy. (Adobe) ;) I'll look into it, though. Excellent suggestion. -- SunirShah

Coincidentally, a friend and I are discussing a Scheme implementation for the LegoMindstorms, which has largely the same constraints as your system. One research avenue that appears promising is region based memory management, as featured in MlKit. They achieve significantly lower memory usage than garbage collector based implementations and avoid GC pauses. I don't yet know enought about RegionBasedMemoryManagement? to say if it is possible in Scheme or appropriate for embedded devices, but it should be worth a look. --NoelWelsh

Maybe one can put each environment frame into its own region, and then scavenge the whole frame all at once?? For most functional programs, and probably most in our circumstances, this might be a valid strategy. Obviously the real problem with any language like this is that they aren't stack-based, but graph-based. Hmmm...

Maybe we should work on this together. http://research.bitflash.com/sunir/LICENSE acceptable? -- SunirShah

According to the MlKit pages, "The fact that ML is typed is essential" for RegionBasedMemoryManagement? to work. Another idea is to use reference counting. It is possible to design the language so that cycles are infrequent or even impossible. Then you can use refcounting without problem. Otherwise, you could have a not-necessarily-efficient GC as a back-up. -- StephanHouben

I'm looking into Smalltalk right now, as all the interesting VM papers seem to be on Smalltalk VMs, and I was thinking that every method and block context can be allocated on the stack instead of on the heap. All you need are two stacks--one data, one call--ala Forth. If you also had a data flow algorithm to determine lifetimes of method temporaries, you might also be able to move many objects onto the stack from the heap, but I'm not as sure of that one. -- SunirShah

A couple months later, I'm studying scripting for embedded systems for my honour's project. I'm currently focusing primarily on PocketSmalltalk. I have a metric ton of PDFs on my hard drive on Smalltalk optimization. However, I would also like to investigate LispMe and (shudder) Java [Waba, Kaffe]. I'll keep y'all posted. I might just implement something at the end of this, but I'm not sure yet. -- SunirShah

Why did you dismiss Forth as "insane"? It can have a more English-like syntax than Scheme or Smalltalk, and therefore could be better for users who are graphic artists (I'm assuming these graphic artists have never used a programming language before). QuartusForth can be used to create compiled native M68K applications as small as 2kb.

Not to mention that Adobe Illustrator®, Adobe PageMaker®, and some other popular tools used by graphic artists use PostScript®, which is a language very similar to ForthLanguage.

CategoryScheme CategoryHandheld