ML without GC

I'm in the mood to develop an ML like language for small microcontrollers :-)

I tried to find out which subset of an ML like language do not need a garbage collector (without much success).
Do you have some ideas or some pointers to papers?

Thanks in advance!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

No longer ML

You probably had to throw out closures, tuples, datatypes. Not much left of ML then.

Excuse my ignorance, but why couldn't have GC on a microcontroller? A simple GC is really tiny, and since you probably control all the memory on a microcontroller anyway, it should be no problem to integrate one.

You can't get...

...a ML compiler for simple hardware without building a decent optimising compiler.

That's my thought.

For example, you'll need to be able to perform certain analysis (what is plural, btw) on the program to tell that some values are linear (as in linear logic - google for it) and could be kept on stack or malloc'ed. Or perform fully fledged region inference (and refuse to compile programs that cannot infere finitie regions).

Just want to understand where dynamic allocation is needed..

I plan to implement an GC (to get a real ML)
but I want to understand what is posible without
it because some functions (interupt-handler for example;
the GC itself...)
should not dynamicaly allocate memory.


linear values... I'll google for it.


The target of my language will be an stack-based vm,
a mixture of (static)forth/ocamlrun/tiny-smalltalk(perhaps).


Throwing out closures especially currying will help,
I hope to pass tuples on the stack...

GC all the way around

For myself, I tend to view interrupts as sort of a continuation of sorts (setjmp and lngjmp can be useful in C for such purposes). Perhaps we don't want the garbage to be deallocated during the interrupt service, but I guess I don't see why an ISR can't generate garbage like any other event driven code. And as long as a GC rememebers to collect its own generated garbage, it should also be able to rely on GC as much as any user code.

You are right..

... I'm just afraid of creating to much non-garbage dynamicaly and have no idea how to avoid this or warn my users...

malloc in C is quite obvious, bit in an ML-Like language
allocation is transparent...

Don't bother, it's been done before.

Supposedly: http://www.it-c.dk/research/mlkit/

Never used it personally, though.

Looks Great

Thanks for the link!

maybe

you could do something like jhc?

PreScheme

Take a look at Pre-Scheme.

"Pre-Scheme: A Scheme Dialect for Systems Programming"

by Richard A. Kelsey.

http://citeseer.ist.psu.edu/kelsey97prescheme.html

Abstract: Pre-Scheme is a statically typed dialect of Scheme that gives the programmer the efficiency and lowlevel machine access of C while retaining many of the desirable features of Scheme. The PreScheme compiler makes use of type inference, partial evaluation and Scheme and Lisp compiler technology to compile the problematic features of Scheme, such as closures, into C code without significant run-time overhead. Use of such features in Pre-Scheme programs is restricted to those cases that can be compiled into efficient code. Type reconstruction is done using a modified Hindley/Milner algorithm that allows overloaded user-defined functions. All top-level forms in Pre-Scheme programs are evaluated at compile time, which gives the user additional control over the compiler's partial evaluation of the program. Pre-Scheme has been implemented and used to write a byte-code interpreter and associated support code for a complete Scheme implementation.

/Jens Axel Søgaard

check out regions

Its mentioned in regards to MLKit, but still worth mentioning on its own. Regions are a way of statically (and typefully) allowing the programmer to explicitly do dynamic memory allocation in a safe manner. I'd suggest checking out the various papers by folks such as Talpin, Morrisett, and several others. There is also a chapter in ATAPL on the subject.

Hope that helps