[Haskell-cafe] Reference for technique wanted

[Claus Reinke]

>> 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
>
> Savvy Prolog programmers wouldn't *DREAM* of
> using an infix constructor here.

Well, you got me there, I'm not a savvy Prolog programmer
anymore, so I took the '\' for difference lists straight from
Sterling&Shapiro, who employ it for clarity over efficiency.

http://books.google.de/books?id=w-XjuvpOrjMC&pg=PA284&lpg=PA283&ots=4WF3_NFXOt&dq=difference+lists+Prolog

Since my argument was about common origin of ideas
vs differences in representation/implementation, I chose
representations that I considered suggestive of the ideas.

>> 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
>
> Eh?  The scope of *identifiers* is strictly LOCAL in Prolog.
> Logic *variables* don't *have* scope.

I was thinking of abstract declarative semantics, where
variables (even logic ones) are replaced by substitution.

If you make the quantifiers explicit, the identifiers become
alpha-convertible, so their names are irrelevant, and the
scope is given explicitly, as the part of the program enclosed
by the quantifiers. But since variables can be passed around
in Prolog, one needs to move the quantifiers out of the way,
upwards (called "scope extrusion" in process calculi, which
have the same issue).

You end up with no upper bound for the quantifiers - in
that sense, logic variables have a "global" scope, because
the quantifiers must enclose all parts of the program to
which the variables have been passed.

>> To close the circle: I understand that difference lists in
>> Prolog might have been a declarative translation of
>> in-place updating in Lisp lists:-)
>
> It seems unlikely.  Prolog was born as a grammar formalism
> (metamorphosis grammars) and the idea of a non-terminal as
> a relation between a (starting point, end point) pair owes
> nothing to Lisp.

I suspect you've researched the history of Prolog in more
detail than I have, so I'll just remind you that Prolog wouldn't
have been successful without efficient implementations
(including structure sharing), and that both implementers
and early users tended to be aware of implementation
aspects and of Lisp - they wanted to leave behind the impure
aspects of Lisp, but they wanted their implementations of
'Predicate Logic as a Programming Language' to be as
efficient as Lisp implementations.

One example reference:

    Warren, Pereira, Pereira; 1977
    Prolog - The Language and its Implementation
        compared with Lisp
    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.7097

On page 111, we find:

    The characteristics of the "logical" variable are as follows.
    An "incomplete" data structure (ie. containing free variables)
    may be returned as a procedure's output. The free variables
    can later be filled in by other procedures, giving the effect
    of implicit assignments to a data structure (cf. Lisp's rplaca,
    rplacd).

This mindset - wanting to program declaratively, but
being aware of implementation issues that might help
efficiency, and being aware of "how competing languages
do it", has persisted till today, and continues to fuel advances
(e.g., the way that logic programming could fill in incomplete
structures without traversing them again prompted the
development of circular programming techniques in
functional languages - recursion and non-strictness allow
variables to be bound by the result of a computation
that already distributes those variables over a structure).

Also, I thought that Prolog had two origins - one in
grammars, the other in logic as a programming language.

Claus