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