Lambda the Ultimate

inactiveTopic Warren's Abstract Machine
started 8/1/2001; 10:19:07 AM - last post 2/18/2004; 3:01:22 AM
Ehud Lamm - Warren's Abstract Machine  blueArrow
8/1/2001; 10:19:07 AM (reads: 1731, responses: 5)
Warren's Abstract Machine
In 1983 David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard for implementing Prolog compilers.

The book: Warren's Abstract Machine: A Tutorial Reconstruction and slides from lectures on the WAM, are available online.

Essential if you are interested in how Prolog can be implemented.


Posted to Logic/Declerative by Ehud Lamm on 8/1/01; 10:25:34 AM

Ehud Lamm - Re: Warren's Abstract Machine  blueArrow
2/2/2004; 12:13:00 AM (reads: 199, responses: 0)
It seems that the link is dead. Go here instead.

Peter Van Roy - Re: Warren's Abstract Machine  blueArrow
2/9/2004; 10:44:17 AM (reads: 151, responses: 0)
Wow! A discussion on the venerable WAM! The WAM, which enabled a generation of people to implement Prolog easily, and which stopped progress in Prolog implementation technology for a generation (literary license: a generation = a decade). To see how to go beyond the WAM in Prolog implementation, check out Andrew Taylor's thesis and Peter Van Roy's thesis, which appeared at nearly the same time.

Brent Fulgham - Re: Warren's Abstract Machine  blueArrow
2/13/2004; 2:18:36 PM (reads: 116, responses: 0)
Peter -- I have many questions for you!

I am fascinated with the idea of constraint logic programming and logic languages in general, but have never found them to be well-suited for real use due to performance and limitations in the kinds of work that can be done (or more likely, my understanding of Prolog is too limited to allow certain types of applications to be written.)

1. What ever became of the Aquarius prolog implementation -- did you become bored with Prolog and move on to bigger and better? 2. How did Aquarius perform compared to GNU Prolog, which has a quite fast Prolog -> native compiler.

Peter Van Roy - Re: Warren's Abstract Machine  blueArrow
2/18/2004; 2:50:21 AM (reads: 90, responses: 0)
1. What ever became of the Aquarius prolog implementation -- did you become bored with Prolog and move on to bigger and better?

You can still get the source code of Aquarius, but it's not maintained any more. Note that we made a full system, with essentially all Quintus built-ins, that was able to compile itself. We made a Prolog interpreter that was just a meta-interpreter written in Prolog, but that was only 1 to 2 times slower than C-Prolog (a fast C-based Prolog interpreter). After Aquarius I became frustrated with Prolog's limitations as a language. At DEC PRL I worked with Hassan Aït-Kaci to implement his LIFE language, a nice successor to Prolog. We were partners in a European project called ACCLAIM, that also included SICS (who were doing AKL) and Saarland University (who were doing Oz). AKL is the first language to make a true synthesis of Prolog and concurrent logic languages (something which the Japanese FGCS never succeeded in doing). Oz is a kind of successor to AKL and LIFE, it is both more expressive and simpler than either.

2. How did Aquarius perform compared to GNU Prolog, which has a quite fast Prolog -> native compiler.

Actually, GNU Prolog is still WAM-based. Even the native code generation goes through a WAM intermediate stage. For small programs, Aquarius is much faster than GNU Prolog because of its global analysis and because it directly compiles to a simpler instruction set. For larger programs, the difference is smaller, because the analysis doesn't do as well (it does not handle aliasing well) and because the time spent in built-ins becomes proportionally larger.

Peter Van Roy - Re: Warren's Abstract Machine  blueArrow
2/18/2004; 3:01:22 AM (reads: 82, responses: 0)
I am fascinated with the idea of constraint logic programming and logic languages in general, but have never found them to be well-suited for real use due to performance and limitations in the kinds of work that can be done.

Can you be more specific in what the limitations are? Systems like GNU Prolog and SICStus Prolog are actually quite fast, and certainly plenty fast enough for most general-purpose application work. There are many varieties of constraint programming systems, e.g., also including Oz, Claire, Numerica, and ILOG Solver, that have different advantages and disadvantages. If your problem is well-suited for constraint programming (e.g., you're doing optimization, scheduling, or planning, for a problem with a complex specification that can change often), then all the systems mentioned above are powerhouses. There are dozens to hundreds of man-years of work in them.