Re: Pros and cons of high-level intermediate languages

acha@CS.CMU.EDU (Anurag Acharya):
> Olivier.Ridoux@irisa.fr (Olivier Ridoux)
> writes about something called abstract memory that solves problems relating
> to GC as well as tail recursion.
>
> I would like to know more about "abstract memory" and how it solves these
> problems.
>


Our research on the implementation of logic programming languages has been
focused on memory management. We isolated its basic requirements and
packaged them first in hardware, second in a software library. A first
generation of the software packaging was only an emulator of the hardware.
Current generation is "pure" software and could not be translated into
hardware easily. This memory is called MALI (Memoire Adaptee au Langages
Indeterministes - Memory for non-deterministic languages). It is merely a
store for an abstract data-type.


The basic idea of the hardware may help understanding the general
architecture of an application using MALI. It is an extension board for
PC-like computers. The program and the interpreter (or generated code)
are stored and runned on the PC. Every run-time storage is delegated to
the MALI board which runs a garbage collector as a parallel background
task. Every time the interpreter wants to create or consult an object it
asks politely to MALI which suspends the GC task and replies to the
interpreter. More parallelism can be achieved when an answer can be
returned before all the house-keeping is done. Result: the latency of the
MALI board was smaller than the write/read cycle of the PC. In software,
the idea is the same though we get rid of parallelism.


Back to Anurag's question.


The memory is abstract in the sense that it implements an abstract
data-type. A fundamental point is that the memory management is packaged
in the memory. The job of the MM is to compute an optimal representation
of the data-type. It is optimal with respect to the theory of the
data-type.


The game of using an abstract memory for implementing a language is to
design an iterative operational semantics for the language and to map the
variable of the iteration (the state) on the abstract-data type. It may
be that the MM is no more optimal because of the new theory added by the
mapping. That is why different classes of languages need different kinds
of abstract memory. However, one should strive to find abstract memories
that encompass wide classes of language (e.g. MALI for sequential
depth-first search logic programming).


The GC problem is solved because the scheme only uses C for bounded
dynamic allocation. MALI is used for every unbounded dynamic allocation:
mainly, continuations. Tail-recursion is solved because there is no
recursion in the C part. In fact, there is no tail-recursion either since
the scheme is continuation based.


The positive fact of using an abstract memory is that with a minimal care
it solves the MM problem.


The negative fact is that generality has a cost. E.g. to map something
that is more or less a procedure call onto the abstract memory is probably
more costly than to map it on a C procedure call. The mere dialog with
the abstract memory may cost some procedure call. We are trying to make
the connection with MALI as light are possible, but it is still too heavy.


A software version of MALI (MALIv06) is available on ftp:
                  ftp.irisa.fr
                  cd maliv06
It contains a tutorial and reference manual in DVI format. The
tutorial gives the implementation of a simple intermediary machine for
executing Prolog.


Hoping it helps,


Olivier Ridoux
--

Return to the comp.compilers page.
Search the comp.compilers archives again.