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

Question

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

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

или же

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

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

Answer 1

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

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

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

LP ⊆ CLP

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

LP ≈ CLP

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

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

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

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

? - {факториал (N, F) }.ОШИБКА: необработанное исключение: 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(ℛ) также является целью! Проверьте это:

? - записать_каноническое ({a,b,c}).
{' '(А,','(б, в))}
правда.

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

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

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

Независимо от того, помечаете ли вы предикат библиотеки как "ограничение" или нет, не имеет значения: все предикаты можно рассматривать как ограничения, поскольку они могут только ограничивать ответы, но никогда не ослаблять их.

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

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