[Haskell-cafe] Reference for technique wanted

[Richard O'Keefe]

On 2/11/2010, at 10:44 PM, Claus Reinke wrote: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),

Structure sharing came from theorem proving work at Edinburgh.
Later, *more* efficient, implementations, abandoned it.

> 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.

At Edinburgh, the rival wasn't Lisp but Pop-2; specifically
the WonderPop implementation on the DEC-10.

Of possible interest to people in this list is that Pop-2
handled input as lazy lists.  As Robin Popplestone wrote:

	While I (at least) did not understand the issue of
	lazy evaluation, still less know how to implement it in
	general, we hoisted aboard Landin’s preaching about
	streams at least to the extent of providing what we
	called dynamic lists – any lists in POP-2 could in
	effect be lazily extended in the tl (or CDR) direction.
	This was handy for writing the compiler: the compiler
	proper operated on a token-list which it could
	parse functionally.

If you want to trace list differences back to something other
than grammars, the idea of lists gradually materialising on
the right (rather than _changing_ once built) was well known
to everyone in the AI department at Edinburgh because of this.

> 
> 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).

There they are *explaining* things to Lisp programmers;
not giving the origin of an idea.

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

See http://en.wikipedia.org/wiki/Definite_clause_grammar
This was specifically the focus of Alain Colmerauer.

You may be thinking of Cordell Green's 'The use of
theorem-proving techniques in question-answering
systems".
> 
> Claus
> 
>