<< Previous exercise (4.78) | Index | Next exercise (5.1) >>
I think this exercise can be shamelessly ripped off the Indiana Technical Report on eu-Prolog: https://legacy.cs.indiana.edu/ftp/techreports/TR155.pdf
Haha, nope, I lied, they also rename variables.
As a food for thought, there is "Logic Programming: A Classified Bibliography", also I found something similar in "On Implementing Prolog In Functional Programming" by Mats Carlsson.
There is also an attempted solution by skanev: https://github.com/skanev/playground/blob/master/scheme/sicp/04/79.scm , but I think that he misses the point, although I am not sure.
Switching from a quick-and-dirty variable renaming function to an environment structure like the rest of Scheme would have to involve an implementation that solves the problem of carrying around frames that are never evaluated. I would propose what Daniel P. Friedman and David S. Wise referred to as "Suicidal Suspensions" in their seminal 1976 paper on non-strict evaluation in Lisp, "Cons Should Not Evaluate Its Arguments," where they proved such a method would not involve more calls to eval/apply than McCarthy's strict interpreter. This would entail terminating all unevaluated environments once a given query has returned, which means both that the system should use the occasion to batch evaluate this set of environments (ideally using the linear-time tree-based search from exercise 4.76), as well as checking for repetition in its history in order to prevent infinite loops (along the lines of exercise 4.67), as either would be particularly disastrous once the offending environments have been disposed of.