La interpretación algorítmica de la programación en lógica se basa en el concepto de procedimiento de los lenguajes imperativos tradicionales. Un programa será la definición de un conjunto de procedimientos, y una invocación de ejecución será precisamente la invocación de un procedimiento. El control general corresponderá, entonces, a la ejecución de procedimientos, que serán activados mediante una invocación, y que al terminar devolverán el control al procedimiento invocante. El pasaje de parámetros adquirirá un papel más importante que en el sentido tradicional, ya que de la adecuación de los parámetros reales y formales (que es lo que corresponde al concepto de unificación ya visto) dependerá si un cierto procedimiento es susceptible de ser invocado o no.
La diferencia esencial entre el concepto de procedimientos que serán presentados en lo que sigue, y el símil de los lenguajes imperativos, radica en el aspecto no determinístico de la programación en lógica.
En un lenguaje como Pascal, el orden en que se van a ejecutar las instrucciones del programa está dado explícitamente por el usuario. Una invocación a un procedimiento implica que cuando deba ejecutarse la misma, el control será transferido al procedimiento, que se identifica sin ambigüedades en la misma invocación. En cambio en programación en lógica, una invocación puede provocar la activación de más de un procedimiento. Cada uno de ellos implica un camino de ejecución posible. Habiendo tomado una decisión de cuál camino escoger es posible que el camino seleccionado no produzca una solución, en el sentido del fracaso del proceso inferencial que se vio en el capítulo anterior. Dicho problema no implica que no exista una solución en los otros caminos que fueron descartados, por lo que se hace necesario volver al punto de decisión y escoger otra alternativa. Por otro lado, podría suceder que se obtenga una solución en la primera decisión, pero al estar evaluando relaciones, es posible que existan más soluciones por los otros caminos. También en este caso es necesario volver al punto de decisión y explorar todas las alternativas posibles. Las implementaciones de programación en lógica deben contemplar las alternativas expuestas, y utilizan el mecanismo de backtracking para resolverlo.