[m-dev.] interpreting C datastructures as Mercury terms

[Fergus Henderson]

On 07-May-1998, Thomas Charles CONWAY <conway at cs.mu.OZ.AU> wrote:
> Here's one for you all.
> 
> In the new profiler that I'm working on, I generate a big tree-like
> structure representing the calltree of the program. This structure
> is generated by C code in the runtime (with cooperation from the
> generated code). It would be nice for the profiler tool to be able
> to use io__read or io__read_binary to read in the data generated
> by the profiling run. Correspondingly it would be nice to be able
> to have the runtime call back to Mercury to write out the structure
> with io__write{,_binary} at the end of the profiling run. For this
> to work, the C representation of the tree must be such that I can
> write a collection of Mercury type definitions that have a corresponding
> structure. So far, there are two problems with this:
> 
> 1) Array-like structures.
> There are structures that have the form
> typedef struct FOO {
> 	Word	this;
> 	Word	that;
> 	Word	**others;
> } Foo;
> 
> The problem that this represents is that I can't write a single
> Mercury type that represents all the different arities that Foo
> could have. I guess using a Mercury array representation would be
> possible, but anyway this one isn't the really interesting case.
> 
> 2) List-like structures.
> There are a number of structures that are of the form:
> typedef struct BAR {
> 	strcut BAR	*next;
> 	Word		*this;
> 	Word		*that;
> } Bar;
> 
> Now, you could write the following type declaration:
> 
> :- type bar
> 	--->	bar(bar, this_type, that_type)
> 	;	nil.
> 
> However, the tag assignment rules mean that all the recursive pointers
> need to be tagged which is a pain in C. If we could convince the compiler
> to use the opposite to the usual tag assignment (ie 0 to bar/n and 1 to nil)
> the problem would go away - rather than using NULL to represent the empty
> list of Bars, we use 1 (appropriately macroized and cast of course) and
> the bar-pointers can be used without explicit tagging.
> 
> Is there a nice way of convincing the compiler to use this kind of tag
> assignment?

Currently, there's basically two ways of getting Mercury and C to share
data structures:

	(a) Define the data structures in C,
	    and provide some way of getting Mercury
	    to understand the C data structures;

	(b) define the data structures in Mercury,
	    and provide some way of getting C
	    to understand the Mercury data structures.

One problem with (a) is that C data structures
such as arrays without bounds information
or undiscriminated unions are fundamentally
unsafe, because misuses result in undefined behaviour --
there's no way to provide runtime error checking.
This doesn't fit very well with Mercury.

Thus, in cases where it is feasible, (b) will probably
work better, IMHO.

Currently, Mercury doesn't really provide too much
help for sharing data structures.  You can define
concrete data structures in Mercury and export them
as ADTs to C, or vice versa, but you have to do
quite a bit of tedious work definition access
functions.  In addition, when accessing the data
structure from the non-native language, access
is going to be less efficient, since it needs
to be done via an access function.
(This is mainly a problem in the case of
exporting to C.)

We have previously discussed adding support
for `pragma export_type' or something like that
to automate this tedium and to avoid the
efficiency problems.  I think this is a good idea.
It's just something we haven't gotten around to yet.

Ada has `pragma Convention(Language)' which you
can attach to the declarations of data structures
to say that they should be layed out according to
the conventions expected by the specified language;
for example, `Convention(C)' on an array means there's
no bounds information attached, and `convention(Fortran)'
on a 2D array means that it is in row-major rather than
column major order.  However, implementing that sort
of thing would be quite a lot of work.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.