Правильный способ написания рекурсивных функций в CLP(R) с Прологом

Я очень запутался в том, как CLP работает в Прологе. Мне не только трудно увидеть преимущества (я вижу их в конкретных случаях, но мне трудно их обобщить), но, что более важно, я с трудом могу придумать, как правильно написать рекурсивный предикат. Что из следующего было бы правильной формой с точки зрения CLP(R)?

factorial(0, 1).
factorial(N, F):- {
  N > 0,
  PrevN = N - 1,
  factorial(PrevN, NewF),
  F = N * NewF}.

or

factorial(0, 1).
factorial(N, F):- {
  N > 0,
  PrevN = N - 1,
  F = N * NewF},
  factorial(PrevN, NewF).

Другими словами, я не уверен, когда мне следует писать код вне ограничений. Мне первый случай показался бы более логичным, потому что PrevN и NewF относятся к ограничениям. Но если это так, мне любопытно посмотреть, в каких случаях полезно использовать предикаты вне ограничений в рекурсивной функции.


person Bram Vanroy    schedule 10.01.2017    source источник


Ответы (1)


В вашем посте есть несколько пересекающихся вопросов и проблем, вероятно, слишком много, чтобы последовательно ответить на ваше полное удовлетворение в одном посте.

Поэтому я хотел бы сначала изложить несколько общих принципов, а затем на их основе сделать несколько конкретных замечаний по поводу выложенного вами кода.

Во-первых, я хотел бы обратиться к тому, что я считаю наиболее важным в вашем случае:

ЛП ЦЛП

Это просто означает, что CLP можно рассматривать как надмножество логического программирования (LP). Можно спорить о том, следует ли считать их правильным надмножеством или, на самом деле, имеет еще больше смысла рассматривать их как обозначающие одно и то же понятие. По моему личному мнению, логическое программирование без ограничений гораздо труднее понять и гораздо менее полезно, чем с ограничениями. Учитывая, что даже самые первые пролог-системы имели такое ограничение, как dif/2, а также то, что важные встроенные предикаты, такие как (=)/2, идеально соответствуют понятию «ограничения», границы, если они вообще существуют, кажутся мне несколько искусственными, предполагая, что:

ЛП ЦЛП

Как бы то ни было, ключевой концепцией при работе с CLP (любого рода) является то, что ограничения доступны как предикаты и используются в программах на Прологе, как и все другие предикаты. .

Следовательно, независимо от того, есть ли у вас цель factorial(N, F) или { N > 0 }, по крайней мере, в принципе это одно и то же: оба означают, что что-то выполняется.

Обратите внимание на синтаксис: ограничения CLP() имеют форму { C }, что соответствует {}(C) в префиксной нотации.

Обратите внимание, что цель factorial(N, F) не является ограничением CLP()! Также нет следующего:

?- { factorial(N, F) }.
ERROR: Unhandled exception: type_error({factorial(_3958,_3960)},...)

Таким образом, { factorial(N, F) } также не является ограничением CLP()!

Таким образом, ваш первый пример не может работать по одной только этой причине. (Кроме того, у вас есть синтаксическая ошибка в заголовке предложения: factorial (, поэтому он также вообще не компилируется.)

Когда вы научитесь работать с решателем ограничений, ознакомьтесь с предоставляемыми им предикатами. Например, CLP() предоставляет {}/1 и несколько других предикатов, а также имеет специальный синтаксис для определения отношений, которые содержат числа с плавающей запятой (в данном случае).

Другие решатели ограничений предоставляют свои собственные предикаты для описания сущностей их соответствующих доменов. Например, CLP(FD) предоставляет (#=)/2 и несколько других предикатов для определения целых чисел. dif/2 позволяет рассуждать о любом термине Пролога. И так далее.

С точки зрения программиста, это точно то же самое, что и использование любого другого предиката вашей системы Prolog, независимо от того, является ли он встроенным или полученным из библиотеки. В принципе, все то же самое:

Цель типа list_length(Ls, L) можно прочитать так: «Длина списка Ls равна L».

Цель типа { X = A + B } можно прочитать так: число X равно сумме чисел A и B. Например, если вы используете CLP(Q), ясно, что в данном случае речь идет о рациональных числах.

Во втором примере тело предложения представляет собой союз формы (A, B), где A — ограничение CLP(), а B — цель формы factorial(PrevN, NewF) .

Дело в том, что ограничение CLP() является также целью! Проверьте это:

?- write_canonical({a,b,c}).
{','(a,','(b,c))}
true.

Итак, вы просто используете {}/1 из library(clpr), который является одним из предикатов, которые он экспортирует.

Вы правы в том, что PrevN и NewF относятся к ограничениям. Однако factorial(PrevN, NewF) не является частью мини-языка, реализуемого CLP() для обработки чисел с плавающей запятой. Поэтому вы не можете включить эту цель в часть, относящуюся к CLP().

С точки зрения программиста, главная привлекательность CLP заключается в том, что он вписывается в «нормальное» логическое программирование до такой степени, что его практически невозможно отличить от него: просто предикаты и записываются, как и все другие цели.

Пометите ли вы библиотечный предикат как «ограничение» или нет, почти не имеет значения: Все предикаты можно рассматривать как ограничения, поскольку они могут только ограничивать ответы, но никогда расслабьте их.

Обратите внимание, что оба примера, которые вы публикуете, являются рекурсивными! Это совершенно нормально. На самом деле рекурсивные предикаты, скорее всего, будут в большинстве ситуаций, в которых вы будете использовать ограничения в будущем.

Однако для конкретного случая факториала лучше подходят ограничения CLP(FD) вашей системы Prolog, поскольку они полностью посвящены рассуждениям о целых числах<. /эм>.

person mat    schedule 10.01.2017
comment
Спасибо за обширный ответ. Я предполагаю, что часть, которую мне трудно обойти, - это то, как работает решатель ограничений внутри Prolog. Например, учитывая, что второй приведенный мной пример кода верен, мое первоначальное представление об ограничениях было неверным. Я думал, что блок ограничений был первым решен (как первая цель в списке целей), но он не мог содержать нерешенных переменных. Другими словами, я не понимал, как рекурсивный вызов может находиться за пределами/после фигурных скобок, если блоку ограничения нужны значения, которые он производит. - person Bram Vanroy; 10.01.2017
comment
Основная привлекательность логического программирования в целом заключается в том, что оно в значительной степени освобождает вас от таких процедурных соображений. Если вы только начинаете изучать Пролог и ограничения, сосредоточьтесь на четком декларативном описании, независимом от того, как упорядочены цели. Пока вы придерживаетесь чистого и монотонного подмножества Пролога (к которому также относятся все ограничения), вы можете свободно переупорядочивать все свои цели и узнавать о процедурных аспектах на любом этапе, даже позже. Как это работает внутри Пролога, понять гораздо труднее. Например, как (=)/2 работает внутри Пролога? - person mat; 10.01.2017
comment
Например, хороший способ прочесть второй пример — сказать: Если это так, что N > 0, и это так, что ... и т. д., < b>тогда верно factorial(N, F). То, как вы упорядочиваете ограничения, может иметь процедурный эффект, но не позволяйте этому отвлекать вас от смысла предложения и от того факта, что вы можете свободно изменять порядок целей, не затрагивая декларативный смысл. - person mat; 10.01.2017