🚀 go-pugleaf

csa09@seq1.keele.ac.uk (Paul Singleton) writes:

>I had forgotten that the circumstances in which I use difference lists in
>place of regular lists are special: is 'single threaded' established jargon
>for these conditions?  if so it is a useful term.

I am not sure that `single-threadedness' is a good term.  There seem
to be several independent properties involved for the introduction of
difference-lists to be safe.  These are identified and named in [1],
but I don't know that our terminology is optimal either.

>Presumably the single-threadedness (or otherwise) of an argument in a
>program be determined statically?

If you refer to the problem of when difference-lists can safely replace
lists in a Sterling-Shapiro style transformation, then a fairly complex
set of dataflow analyses seem necessary.  Below are the three references
that I know of in the area.

As to analysis, the necessary dataflow analyses must be approximate since
the properties involved are undecidable in general.  As to synthesis, in
[1,2] we are concerned with preserving both success and failure, whereas
[3] is based on unfold/fold techniques which I think do not necessarily
preserve finite failure. 

As somebody mentioned, unification of difference-lists is not faithful
to the unification of the lists they represent, but furthermore, and
independently (I think), the predicate used to concatenate difference-
lists is not always faithful to the customary definition of append.
There are examples of this in [1,2].

Harald Sondergaard
The University of Melbourne

[1] K. Marriott and H. Sondergaard.  Difference-list transformation
    for Prolog.  Submitted to New Generation Computing.

[2] K. Marriott and H. Sondergaard.  Prolog program transformation
    by introduction of difference-lists.  In Proc. Int. Computer
    Science Conf. 88, pages 206-213.  IEEE Computer Society, 1988.

[3] J. Zhang and P. Grant.  An automatic difference-list transformation
    algorithm for Prolog.  In Y. Kodratoff, editor, Proc. 1988 ECAI,
    pages 320-325.  Pitman, 1988.