I would like to learn to use ATS and also get some help using it
for some things.
- Can ATS be used to produce a stand alone C library?
This means: I will specify the functions which must be provided.
They will have extern “C” linkage.
I am thinking of Judy. Judy provides a cache tuned digital trie.
It is the fasted mutable associative store in existence which
provides both random and sequential access. There are 3 primary
data types: word -> bit, word -> word, and NTBS -> word.
[NTBS: null terminated string]
It also scales to terrabyte store without any issues.
All core operations on Judy are O(1) (O(N) for NTBS where
N is the string length).
Judy is slower at some sizes for random access compared
to hash tables (but hash tables can’t do sequential access).
OTOH Judy only handles word keys (hash is more general,
it handles anything with a comparison and hash function).
However the code is horrible, full of macros, and a lot of work would be
required to rewrite it in ATS. We’d use templates to replace the macros.
And we’d want to use the type system to prove correctness.
This would be an interesting job to do because Judy is the best.
And it isn’t used much for some reason (perhaps because the code
is unmaintainable 
Judy does have one downside in a modern context: it is not compatible
with a plugin garbage collector because it is a digital trie (keys are
split into non-contiguous byte streams which means some pointers
to objects will be invisible to a collector not trained in Judy).
My own GC knows about Judy though
- I have another library which I would think is suitable for
conversion to ATS: a precise garbage collector. Which uses
Judy mentioned above. However it is currently a C++ library.
The virtual dispatch is actually used as follows: the allocator
used is abstract. The GC itself is split into an abstraction and
implementation, the core implementation is not thread safe.
A wrapper implementation is provides as well which is thread safe.
To convert to C is possible, just using a record of function pointers.
The GC is not entirely trivial. It’s a precise naive mark/sweep collector
driven by compiler generated tables. The main sweep mechanism
uses an array of offsets to find pointers. Judy arrays provide repetition
counts to allow variable length arrays to be handled.
When sweeping, the recursive descent posts pointers into a buffer
for later analysis until a fixed recursion depth is reached. Then the
scan falls out and the analysis routine runs through the buffer.
This mechanism is complex, a proof of correctness would be really
valuable.
This GC could also be used with ATS is the ATS compiler could be taught
how to generate the RTTI tables required to run the GC.
Unlike Judy, which it relies upon, the collector is not a very large
piece of code. The longest function is about one page.
-
I have a number of other libraries which would be better written
in ATS than C++ (and also some I do NOT have which I would like
to write). -
More difficult: my compiler (Felix) generates C++ from a high level
language. It is basically a souped up type safe macro processor
which uses libraries to define Felix types and functions in terms of C++ types
and functions. Then it churns away and emits C++.
It would be good to emit ATS as well. The ATS code would then be translated
by the ATS compiler into C which would then be compiled as C++ into a library
which is linked to the rest of the code. It’s essential that ATS compiler emits
C code which is also compliant C++ code (the primary requirement is to note
that C++ REQUIRES an explicit cast converting from a void * to another pointer
type, C doesn’t: there are some other issues: C++ has strongly typed enums
for example, C doesn’t).
This is a particularly hard project because it would be useless unless
Felix can be trained to emit suitable types and proof values.
[The Felix compiler doesn’t have to understand them, but it does have
to be able to sequence and compose them]
All these points above require one thing: ATS has to be able to generate
(a) libraries (not programs)
(b) functions with specified names and interfaces
© extern “C” wrappers
(d) C++ compilant C code
I believe ATS can do (a) and (b). © is a trivial mod.
(d) would require rewriting the compiler as required to ensure
casts are used where required, and enums are used in a suitable
way (enums in C++ are NOT integers).
john skaller
ska...@users.sourceforge.net
http://felix-lang.org
