WAM的替代品 [英] Alternatives to the WAM

问题描述

我记得曾经读过，与WAM大致同时发明了至少两个其他替代方案.有指针吗?

解决方案

在WAM之前，Clocksin提供了ZIP.它的设计仍然非常有趣. SWI-Prolog使用它.而且B-Prolog逐渐从WAM设计过渡到ZIP.当然，通过这种方式，开发了许多新的创新.另一种选择是VAM.

与1993年的比较是:

http://www.complang.tuwien .ac.at/ulrich/papers/PDF/binwam-nov93.pdf

与此同时，最有趣的架构开发与B-Prolog有关.

WAM与邮编

WAM和ZIP之间的主要区别在于谓词参数的精确接口.在WAM中，所有参数都通过寄存器传递，即实际寄存器或内存中的至少固定位置. ZIP通过堆栈传递所有参数.

让我们考虑一个最小的例子:

p(R1,R2,R3,L1,L2,L3) :-  % WAM                % ZIP
                         % store L1...L3      % nothing
                         % nothing            % push R1..R3
                         % init X1..X3        % push X1..X3
   q(R1,R2,R3,X1,X2,X3),
                         % put unsafe X1..X3  % push X1..X3
                         % load       L1..L3  % push L1..L3
   r(X1,X2,X3,L1,L2,L3).

在调用q之前:

对于在相同位置(R1..R3)传递给第一个目标的参数，WAM不需要执行任何操作.对于二进制子句来说，这尤其有趣-即，在结尾处恰好有一个常规目标的子句. WAM在这里表现出色.

其他参数L1..L3需要存储在本地.因此，对于这些参数，register接口没有任何好处.

另一方面，ZIP不需要保存参数-它们已经保存在堆栈中.这不仅对具有多个目标的子句有益，而且对其他中断目标(如约束或中断)也有好处.

缺点是，ZIP必须再次按下R1..R3.

两者都必须初始化X1..X3并将它们存储在堆栈中.

呼叫q:

调用q时，WAM必须为X1..X3和L1..L3分配堆栈空间，因此需要分配6个单元格，而ZIP需要R1..R3,L1..L3,X1..X3.因此，在这里，WAM的空间效率更高.此外，WAM允许对环境进行修整(对于更复杂的情况)，这对于ZIP来说是不可能的.

在调用r之前:

此r是最后一个调用，并且在没有选择点的情况下，系统会尝试释放此子句的空间.

对于WAM，必须检查存在变量X1..X3 仍然是未实例化的局部变量()，如果将它们移到堆上-这很昂贵，但很少发生. L1..L3刚刚被加载.就是这样，WAM现在可以安全地重新分配本地帧.因此，最后一次通话优化非常便宜.

对于ZIP，一切都必须照常进行.然后只有额外的扫描才能检查堆栈上的所有值，并相应地移动它们.那是相当昂贵的.可以进行一些优化，但是仍然远远超出WAM的功能. ((一个可能的改进是按相反的顺序推送参数.然后，变量L1..L3可能留在了它们的位置.因此这些变量将不需要任何处理.我还没有看到这样的实现(尚未).))/p>

I remember once reading that there were at least two other alternatives invented roughly at the same time as the WAM. Any pointers?

解决方案

Prior to the WAM, there was the ZIP by Clocksin. Its design is still very interesting. SWI-Prolog uses it. And also B-Prolog has slowly migrated from a WAM design towards the ZIP. Of course, on that way many new innovations were developed. Another alternative is the VAM.

A comparison as of 1993 is:

http://www.complang.tuwien.ac.at/ulrich/papers/PDF/binwam-nov93.pdf

In the meantime, the most interesting architectural developments are related to B-Prolog.

WAM vs. ZIP

The key difference between the WAM and the ZIP is the precise interface for a predicate's arguments. In the WAM, the arguments are all passed via registers, that is, either real registers or at least fixed locations in memory. The ZIP passes all arguments via the stack.

Let's consider a minimal example:

p(R1,R2,R3,L1,L2,L3) :-  % WAM                % ZIP
                         % store L1...L3      % nothing
                         % nothing            % push R1..R3
                         % init X1..X3        % push X1..X3
   q(R1,R2,R3,X1,X2,X3),
                         % put unsafe X1..X3  % push X1..X3
                         % load       L1..L3  % push L1..L3
   r(X1,X2,X3,L1,L2,L3).

Prior to calling q:

The WAM does not need to do any action for arguments that are passed on to the first goal at the very same positions (R1..R3). This is particularly interesting for binary clauses - that is, clauses with exactly one regular goal at the end. Here the WAM excels.

The other arguments L1..L3 need to be stored locally. So for these arguments, the register interface did not do anything good.

The ZIP on the other hand does not need to save arguments - they are already saved on the stack. This is not only good for clauses with more than one goal, but also for other interrupting goals like constraints or interrupts.

As a downside, the ZIP must push again R1..R3.

Both have to initialize X1..X3 and store them on the stack.

Calling q:

When calling q, the WAM has to allocate stack space for X1..X3 and L1..L3 thus 6 cells, whereas the ZIP needs R1..R3,L1..L3,X1..X3. So here, the WAM is more space efficient. Also, the WAM permits environment trimming (for more complex situations) which is next-to-impossible for the ZIP.

Prior to calling r:

This r is the last call, and systems try to free the space for this clause, provided no choice point is present.

For the WAM, the existential variables X1..X3 have to be checked for being still uninstantiated local variables (put_unsafe), and if, they are moved onto the heap - that's expensive, but occurs rarely. L1..L3 are just loaded. That's all, the WAM can now safely deallocate the local frame. So last call optimization is dirt cheap.

For the ZIP, everything has to be pushed as usual. Then only, an extra scan has to examine all the values on the stack and moves them accordingly. That's rather expensive. Some optimizations are possible, but it is still much more than what the WAM does. ((A possible improvement would be to push arguments in reverse order. Then the variables L1..L3 might be left in their location. So these variables would not need any handling. I have not seen such an implementation (yet).))

这篇关于WAM的替代品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！