A nice article and neat little demo. While it serves as a foil for the point the author was making, I feel like Prolog depth first search (DFS) is almost used

A nice article and neat little demo. While it serves as a foil for the point the author was making, I feel like Prolog depth first search (DFS) is almost used as a straw-man by many. It's not that the problem the OP points out never occurred to the inventors of Prolog. Quite the opposite, in fact: in the "game" of evaluating a logic program, the naive search space of possible "moves" is astronomical. In the beginning, no one knew how to deal with it. Selective linear definite clause resolution (SLD) is simply the (obvious in hindsight, but surprising at the time) observation that taking the clauses one at a time is a viable strategy. Once you've committed to taking clauses one at a time, taking the clauses in the order-as-written is a natural choice. I read a paper which compared DFS, iterative-DFS (DFS with a varying max depth), and breadth-first-search (BFS). The conclusion of the article was that iterative-DFS performed best overall, but that BFS was a viable alternative (the paper author advocates for BFS). However my reading of the graphs and data presented was that for the problems on which it was suited, plain DFS was really not that bad. Intuitively, I would ascribe that to this: you have to do the work eventually, and at the lowest level the CPU is doing one thing at a time anyway. Where that evaluation strategy falls down, as the OP demonstrates, is when the answer is needed before the clause which computes the answer has been seen. In the Prolog-work-alike C++ library I have experience using (not designed by me), a way this is got around is by having program fragments able to operate with partially-filled in data as much as possible, and delaying evaluation of things that really do need the complete data until the end. This loses some of the "declarative programming" benefit of logic programming: you're having to manually ensure order. But you should really be writing functional code which delays real I/O as long as possible regardless of what kind of programming you're doing. I spent a lot of cycles (brainpower) trying to think of a way to make this less dependent on the order of clauses, while still being efficient. That's a harder problem than it looks.