DCGs implemented with delimited continuations

Also the Prolog version is exactly that. Shift/1 captures the forward continuation up to the matching reset/3 and causes reset/3 to succeed. There is no backtracking in this process and the continuation (a term on the stack) thus shares all (logical) variables with the environment at the point where we aborted the execution (shift). You can do something else and continue where you were by calling the continuation. That is what happens in the DCG story, but what you can also achieve using the intercept interface, which is typically faster and doesn’t suffer from some subtle interaction with cuts of delimited continuations.

Tabling uses them differently. Here the continuations are copied in permanent memory (say assert, though it uses internal alternatives). Now you can execute the continuation any time later and as many times as you want. The copy looses the variable bindings and thus you must make the copy together with a term representing the variables that must be shared with the environment. Now we can copy the continuation+vars back to the stacks, unify the vars and call the continuation.

3 Likes