Lambda the Ultimate

inactiveTopic 1983-1993: The Wonder Years of Sequential Prolog Implementation
started 10/24/2003; 3:33:15 PM - last post 10/25/2003; 1:57:51 AM
Ehud Lamm - 1983-1993: The Wonder Years of Sequential Prolog Implementation  blueArrow
10/24/2003; 3:33:15 PM (reads: 12995, responses: 2)
1983-1993: The Wonder Years of Sequential Prolog Implementation
Peter directed me to this paper of his, in reply to a question following his very interesting post regarding the history of Prolog.

If you are interested in how Prolog is implemented (WAM and the like), you should definitely read this paper. But even if the implementation details don't really interest you, the paper is worth a look, since it gives insights on the history of Prolog systems, and some useful clues about the semantics of Prolog.

The discussion of tail call optimizations (called "last call optimization" in the paper) is interesting. From what I remember (it was a while ago that I checked) Prolog doesn't mandate this. Strange for a language so recursion oriented.

Figure 1 showing the correspondence between logical and imperative concepts, is used in the presentation of the WAM, but is also a nice summary of the different semantic uses of the major Prolog constructs.

Integrating constraint solving inside Prolog is also discussed.


Posted to logic/declarative by Ehud Lamm on 10/24/03; 3:34:56 PM

Peter Van Roy - Re: 1983-1993: The Wonder Years of Sequential Prolog Implementation  blueArrow
10/25/2003; 1:02:06 AM (reads: 361, responses: 1)
The discussion of tail call optimizations (called "last call optimization" in the paper) is interesting. From what I remember (it was a while ago that I checked) Prolog doesn't mandate this. Strange for a language so recursion oriented.

Actually, all Prolog compilers do tail call optimization, starting with David Warren's DEC-10 compiler in 1980. The WAM was designed in 1983 and has tail call optimization built in. Some early Prolog interpreters (like C-Prolog, a very popular one until the early 1980s) did not do it. I guess the early Prolog users (in the 1970s and early 1980s) were already so impressed that Prolog could go as fast as it did (there was an aura of magic hanging around Prolog in those days), that they didn't mind too much the lack of tail call optimization.

Ehud Lamm - Re: 1983-1993: The Wonder Years of Sequential Prolog Implementation  blueArrow
10/25/2003; 1:57:51 AM (reads: 369, responses: 0)
Thanks for the clarification.