The ML Kit with Regions
Version 2 is not the most recent version; please consult the
ML Kit Home Page.
from http://www.itu.dk/research/mlkit/kit2
What is the ML Kit with Regions?
The ML Kit with Regions is a compiler for Standard ML, a strict functional
programming language which is widely used for teaching and research. The ML Kit with Regions is intended
for the development of stand-alone applications which must be reliable,
fast and space efficient.
The main feature of the ML Kit with Regions is that it uses a
stack of regions for memory management rather than traditional
garbage collection techniques; this has several important
consequences:
- Compile-Time Garbage Collection: All memory allocation directives (both allocation and
de-allocation) are inferred by the compiler, which uses a number of
novel program analyses concerning lifetimes and storage layout.
There is no pointer-tracing garbage collection
at runtime;
- Memory Safety: Safety of de-allocation of memory is ensured by the compiler;
- Static detection of space leaks;
- Region Resetting: It is possible to give explicit directives about resetting of
regions in cases where the static analyses are too conservative;
such directives are checked by the compiler;
- Region Profiling: The system includes a graphical region profiler, which helps gain
detailed control over memory use;
- Soft Real-Time: Programmers
who are interested in real-time programming
can exploit the absence of garbage collection:
there are no interruptions of unbounded duration at runtime;
- Interface to the C language: ML Kit applications can call C functions using standard C
calling conventions; the region scheme can even take care of
allocating and de-allocating regions used by C functions thus
invoked.
The overall goal with developing the ML Kit with Regions has been to
combine the advantages of a high-level, type-safe language
(Standard ML),
with the advantages of low-level languages, namely
detailed control over space and time. Indeed, it turns out
that the regularity provided by the ML type system makes is possible
to infer much more useful information about ML programs than one can reasonably hope for
in languages with more liberal type systems. Naturally, the hope is that
this technology will promote the use of Standard ML in situations
where safety and detailed control of machine resources are
important, as indeed is often the case.
Since we are using Standard ML as our source language,
one can use the ML Kit in conjunction with other Standard ML systems;
for example,
one can port programs that previously ran on a garbage collection based
Standard ML system to run on the Kit; or one may use the Kit simply to gain insight
into how a program intended for another system uses memory; or one can
develop Standard ML programs directly in the Kit. We have tried all three with
good results.
Learning how to program with regions
The user we have in mind is an experienced programmer
who is concerned with developing small, but reliable and
efficient programs.
To use the Kit effectively, you need to learn how to program with regions -
this applies even if you already know Standard ML.
To this end, we have written a technical report:
Programming
with Regions in the ML Kit
To get it, click A4 paper (non-US)
or letter-size paper. (Hard copies are now available,
free of charge. Send an email with your postal address
to Jeanette Kværndrup (jeanette@diku.dk) reqesting a copy of DIKU-report
97/12.)
The report gives a systematic account of programming with regions,
without getting into the theory of regions. It
provides many examples of what to
do and what not to do when programming with regions.
Another group of users we have in
mind are those for whom Version 1 of the ML Kit was developed, namely
the programming languages research community. As with Version 1, the
present version includes the ML sources of the system. There is no
separate guide for Kit system programmers this time, but
the code contains many comments. (Comments account for 38% of the 2,5Mb of source
code, at the last count.)
What is provided?
Apart from documentation, you can download the Kit compiler,
the Kit runtime system and the region profiler. The Kit compiler has
a separate compilation system, which takes great care to avoid
unnecessary re-compilation.
The Kit has two code generators, one that produces ANSI C code and
one that produces HP PA-RISC code.
The compiler is a batch compiler with a text-based menu system
of the kind which was quite popular amongst computer hobbyists twenty
years ago. The Kit does not yet support compilation of Modules,
although it will in a future release.
Standard ML: Revised Definition and Basis Library
This release coincides with a revision of the Definition of
Standard ML(1997 Definition) and the
approaching completion of the Standard ML Basis Library. See
pending list for the changes that are yet to
be made to the Kit as a result.
Degree of completion
For the past year, systematic testing has been an integral part of the
development. Also, we have spent considerable
time on error messages and warnings and on general tuning of the
system. At the
time of writing, we are not aware of bugs in the system, although we
cannot promise that none are left.
Performance
Compilation is slower than on most other ML compilers and it may
require tens of megabytes of memory. However, judging from our own
experience, the system is fine for developing programs up to a couple
of thousand lines of Standard ML. On the HP and for the benchmarks
we have tried, the generated target programs run
between three times slower to ten times faster under the ML Kit
than under SML/NJ v93 on the same machine.
For users that do not have an HP machine, the Kit can
compile to ANSI C instead. On the HP, target programs produced via C typically
run 6 to 10 times slower than the corresponding programs produced
directly by the Kit HP backend.
For an automatically generated test report with current
performance figures, click test.ps.
Support
We hope that you will enjoy using the ML Kit with Regions as much
as we have enjoyed developing it. If you have comments or
suggestions, whether positive or critical, feel free to write us.
If you find a bug, please do write us, so we can correct it.
The ML Kit with Regions is a software deliverable of the DART
research project, which is sponsored by the Danish Research Council
for Natural Sciences.
Summer School
A Summer School on the theory and
practice of region-based memory management took place
August 18-22, 1997, in Copenhagen.
Links
Applet
Below is an applet. If you click on it, you will see a randomised
execution of a region-based program. The region stack grows to the
right. The red line is the largest region. The blue line marks the
stack top.
April, 1997
Mads Tofte, Lars Birkedal, Martin Elsman, Niels
Hallenberg, Tommy Højfeld Olesen, (DIKU)
Peter Sestoft, Peter Bertelsen (KVL)
tofte@diku.dk, birkedal@cs.cmu.edu, mael@diku.dk, faxe@diku.dk, hojfeld@diku.dk, sestoft@dina.kvl.dk, pmb@dina.kvl.dk
Maintained by tofte@itu.dk /
April 17, 1997. Revised Jan 4th, 1998.
