prolog - Alternativas a la WAM
warren-abstract-machine (3)
Recuerdo una vez que leí que había al menos otras dos alternativas inventadas aproximadamente al mismo tiempo que la WAM. Cualquier punteros?
Antes de la WAM, estaba el ZIP de Clocksin. Su diseño sigue siendo muy interesante. SWI-Prolog lo usa. Y también B-Prolog ha migrado lentamente de un diseño WAM a ZIP. Por supuesto, de esa manera se desarrollaron muchas innovaciones nuevas. Otra alternativa es el VAM.
Una comparación a partir de 1993 es:
http://www.complang.tuwien.ac.at/ulrich/papers/PDF/binwam-nov93.pdf
Mientras tanto, los desarrollos arquitectónicos más interesantes están relacionados con B-Prolog.
WAM vs. ZIP
La diferencia clave entre el WAM y el ZIP es la interfaz precisa para los argumentos de un predicado. En el WAM, todos los argumentos se pasan a través de registros, es decir, registros reales o al menos ubicaciones fijas en la memoria. El ZIP pasa todos los argumentos a través de la pila.
Consideremos un ejemplo mínimo:
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).
Antes de llamar a q :
El WAM no necesita realizar ninguna acción para los argumentos que se transmiten al primer objetivo en las mismas posiciones ( R1..R3 ). Esto es particularmente interesante para las cláusulas binarias, es decir, cláusulas con exactamente un objetivo regular al final. Aquí sobresale el WAM.
Los otros argumentos L1..L3 deben almacenarse localmente. Así que para estos argumentos, la interfaz de registro no hizo nada bueno.
El ZIP, por otro lado, no necesita guardar argumentos, ya están guardados en la pila. Esto no solo es bueno para cláusulas con más de un objetivo, sino también para otros objetivos de interrupción como restricciones o interrupciones.
Como inconveniente, el ZIP debe empujar de nuevo R1..R3 .
Ambos tienen que inicializar X1..X3 y almacenarlos en la pila.
Llamando q :
Al llamar a q , el WAM debe asignar espacio de pila para X1..X3 y L1..L3 tanto, 6 celdas, mientras que el ZIP necesita R1..R3,L1..L3,X1..X3 . Así que aquí, el WAM es más eficiente en el espacio. Además, el WAM permite el recorte del entorno (para situaciones más complejas) que es casi imposible para el ZIP.
Antes de llamar a r :
Esta es la última llamada, y los sistemas intentan liberar el espacio para esta cláusula, siempre que no haya un punto de elección presente.
Para el WAM, las variables existenciales X1..X3 deben ser revisadas para ver si todavía son variables locales no put_unsafe ( put_unsafe ), y si se mueven al montón, eso es costoso, pero ocurre raramente. L1..L3 se acaba de cargar. Eso es todo, el WAM ahora puede desasignar de forma segura el marco local. Así que la optimización de la última llamada es muy barata.
Para el ZIP, todo tiene que ser empujado como de costumbre. Solo entonces, un escaneo adicional tiene que examinar todos los valores en la pila y los mueve en consecuencia. Eso es bastante caro. Algunas optimizaciones son posibles, pero aún es mucho más que lo que hace el WAM. ((Una posible mejora sería empujar los argumentos en orden inverso. Entonces, las variables L1..L3 podrían dejarse en su ubicación. Por lo tanto, estas variables no necesitarían ningún manejo. No he visto tal implementación (todavía).))
En la nota técnica titulada Un conjunto de instrucciones abstractas de Prolog , Warren también hace referencia a otro compilador de Bowen, Byrd y Clocksin. Sin embargo, dice que las dos arquitecturas tienen mucho en común, por lo que no sé si ese compilador podría realmente considerarse como una alternativa.
No estoy seguro de si esto es lo que quieres decir, pero las dos primeras implementaciones de Prolog fueron un intérprete escrito en Fortran por Colmerauer et al. y un compilador nativo DEC PDP-10 de Warren et al.
Warren menciona esto en su prólogo a la Reconstrucción Tutorial de WAM de Ait-Kaci. Si esto no es lo que quiere decir, puede encontrarlo en ese documento o en sus referencias.