[Haskell-cafe] Reference for technique wanted

[Claus Reinke]

> To simplify, the difference in persistence between the two
> representations is enough to consider them very different
> as it makes a dramatic difference in interface.

Interesting discussion. I still think it is the same idea,
namely to represent not-yet-known list tails by variables,
embedded into two different kinds of languages.

    \rest->start++rest
    [start|rest]\rest        -- '\' is an infix constructor

The differences arise from the different handling of
variables and scoping in those languages:

- functional languages: explicit, local scopes, variables
    are bound by injecting values from outside the scope
    (applying the binding construct to values); scoped
    expressions can be copied, allowing multiple
    instantiations of variables

- logic languages: implicit, global scopes, variables
    are bound by finding possible values inside the scope
    (unifying bound variables); outside of non-determinism/
    sets-of-solutions handling, only non-scoped terms can
    be copied, allowing single instantiation only

If current functional language implementations had not
abandoned support for reducing under binders, one could
float out the binder for a difference list, and get limitations
closer to those of logic languages (though binding to values
would then become much more unwieldy).

If logic languages allowed local binders in terms, one could
copy difference lists more easily (though substitution and
unification would then involve binders).

So, yes, the realization of the idea is different, as are the
language frameworks, and the junk in the representations,
but the idea is the same.

Btw, functional language implementations not reducing
under binders also implies that functional difference list
operations are not shared to the same extent as logic
difference list operations are - copying a closure copies
un-evaluated expressions, to be re-evaluated every
time the closure is opened with different variable bindings,
so the functional representation is not as efficient as the
logical one, in most implementations.

I can't confirm the reference, but several authors point
to this for an early description

[CT77] Clark, K.L.; Tärnlund, S,Å:
A First Order Theory of Data and Programs.
In: Inf. Proc. (B. Gilchrist, ed.), North Holland, pp. 939-944, 1977.

To close the circle: I understand that difference lists in
Prolog might have been a declarative translation of
in-place updating in Lisp lists:-)

Claus