Интересно, есть ли какая-либо реализация Пролога, которая позволяет оставлять рекурсию в предложениях. Моя интуиция заключается в том, что если реализация использует поиск цели в ширину, она может поддерживать левую рекурсию. Но я не совсем уверен. Обратите внимание, что меня не очень интересует эффективность.Любая реализация Prolog, которая позволяет оставлять рекурсию?
ответ
Ваша интуиция верна, но Prolog использует глубину первого поиска по дизайну (см. Разрешение SLDNF here) и с вескими причинами, то это ограничение легко избежать.
OTOH, Ciao Prolog предлагает extension.
Вы можете имитировать ширину первой рекурсии, используя мета-интерпретатор, как это сделано, например, here для левого рекурсивного DCG (левые рекурсивные грамматики являются обычным случаем), но это не простой способ следовать.
IMO самое распространенное расширение, которое могло бы приблизить/удовлетворить ваш запрос, равно tabling, вы можете найти его в YAP Prolog, XSB, B-Prolog.
Ссылка на какой-то материал на табуляции действительно будет полезной. :) –
Большое спасибо, CapelliC. – day
или с итерационным углублением. ну, вы сказали, что вам не нужна эффективность ... :) –
Спасибо за предложение, Уилл. Итеративное углубление на самом деле работает лучше. Я попробовал расширение BF Ciao с небольшим примером, получил stackoverflow (no pun;). – day