Forzar variable para reasignar(Prolog)

primes (3)

No estás pensando en el problema de una manera "Prolog". En particular, tratar de "reasignar" una variable no es la forma de Prolog. Las variables están ligadas en el camino de satisfacer objetivos y subobjetivos, y en lugar de reasignar un valor, a menudo ordenamos que el código lleve una variable "acumulador", solo para pasar su valor a otra variable "final" en la última etapa de un cálculo .

Retroceder y recursividad son cosas diferentes. Retroceder ocurre cuando un objetivo (o sub-objetivo) falla, y el "motor" de Prolog intenta satisfacer ese objetivo de una manera diferente. Si nos quedamos sin reglas diferentes, etc. para satisfacer el objetivo, entonces falla. (Que puede hacer que el motor Prolog retroceda a un objetivo secundario anterior e intente satisfacerlo de una manera diferente).

La recursión es cuando un predicado se define en términos de sí mismo, es decir, si invocar el predicado puede hacer que se invoque el mismo predicado de nuevo como un subgrupo.

Para hacer muchas tareas en Prolog tenemos que pensar en ellas en términos de recursión en lugar de iteración, como sería natural en un lenguaje de procedimiento. Es por esto que recurrimos a variables de "acumulador", que a los ojos no acostumbrados les parecen argumentos adicionales y posiblemente innecesarios en un predicado.

Sin embargo, una vez que vea la idea en acción, puede obtener cierto grado de satisfacción al poder aplicar el concepto de nuevas maneras.

Tomemos como un problema modelo sumar los números en una lista dada. El enfoque ingenuo sería escribir:

sum(List,Sum).

donde la List es una lista de números y Sum debe ser nuestra salida, manteniendo la suma de valores prescrita en la lista.

La idea básica es bastante natural, usted considera la Head y la Tail de la lista, y si la lista no está (todavía) vacía, quiere "reasignar" Sum = Sum + Head , luego proceder recursivamente para abordar la Tail (hasta que la lista está vacía y tenemos la Sum que queríamos).

Pero esto no tiene sentido en Prolog, porque no puede cambiar el valor de Sum de la misma manera que lo permite un lenguaje de procedimiento. Aquí es donde se agrega un argumento de acumulador a nuestro predicado y hace el mismo trabajo, pero de una manera que le gusta a Prolog.

sumAux([ ],Sum,Sum). sumAux([H|T],Accum,Sum) :- NewAccum is Accum + H, sumAux(T,NewAccum,Sum). sum(List,Sum) :- sumAux(List,0,Sum).

Aquí hemos introducido un predicado "auxilar" sumAux/3 con un argumento adicional, y hemos definido sum/2 en términos de ese predicado estableciendo el argumento central "acumulador" a cero, pero pasando los argumentos List y Sum junto con .

Un poco de reflexión sobre cómo funciona esto compensará sus esfuerzos, y pronto espero que aplique este paradigma en todo tipo de formas novedosas (como contar primos circulares).

La tarea es tomar en dos variables, un número entre 0 y 10,000 y un número de cuántos números primos circulares hay entre 1 y ese número.

Tengo problemas para pasar la copia de seguridad de la copia de seguridad a través de la recursión (creo que se llama "backtracing"). Obtengo el número correcto y estoy bastante seguro de que tengo el concepto resuelto, el problema que tengo es que arroja una error cuando trato de reasignar una variable (?!)

Aquí está el código:

circPrimeCompare(Below, NumCirc):- RealNum is 0, circPrimeCompare(1, Below, RealNum, []), print(''R: ''), print(RealNum), nl, (NumCirc =:= RealNum). circPrimeCompare(_, 0, _, _). circPrimeCompare(N, 1, _, _):- prime(N), print(''aaa''). circPrimeCompare(X, Below, RealNum, L):- ( prime(X), X<Below -> print(X), nl, numDigits(X, Y), rotate(X, Y, N2), ( prime(N2) -> RealNum2 is RealNum + 1 ; RealNum2 is RealNum ), X2 is X + 1, ( not(circPrimeCompare(X2, Below, RealNum2, L)) -> RealNum = RealNum2, print(RealNum), nl ; RealNum = RealNum2, print(RealNum), nl ), print(''RealNum2: ''), print(RealNum), nl ; ( X<Below -> X2 is X + 1, RealNumPass is RealNum, ( not(circPrimeCompare(X2, Below, RealNumPass, L)) -> RealNum = RealNumPass, print(RealNum), nl ; RealNum = RealNumPass, print(RealNum), nl ), print(''RealNum: ''), print(RealNum), nl ) ).

Aquí está el rastro:

Fail: (26) circPrimeCompare(10, 10, 4, []) ? creep ^ Exit: (25) not(user:circPrimeCompare(10, 10, 4, [])) ? creep Call: (25) 4=4 ? creep Exit: (25) 4=4 ? creep ... Exit: (24) circPrimeCompare(9, 10, 4, []) ? creep ^ Fail: (23) not(user:circPrimeCompare(9, 10, 4, [])) ? creep Call: (23) 4=4 ? creep Exit: (23) 4=4 ? creep ... Exit: (22) circPrimeCompare(8, 10, 4, []) ? creep ^ Fail: (21) not(user:circPrimeCompare(8, 10, 4, [])) ? creep **Call: (21) 3=4 ? creep Fail: (21) 3=4 ? creep** Redo: (21) numDigits(7, _G589) ? creep

La parte en negrita es lo que me está arrojando. Realmente no entiendo por qué está actuando de esta manera. ¿Es porque las variables son esencialmente de un solo uso? ¿Alguna idea de cómo arreglarlo?

(Y sí, me doy cuenta de que este es realmente un código realmente terrible. Nunca había escrito nada en Prolog antes de esta tarea).

Un lenguaje de prólogo común es, como se ha notado, usar predicados ''auxiliares'' que están sembrados con un acumulador para realizar el trabajo. Además, ayuda a descomponer el problema en partes más pequeñas y sencillas. A menudo tendrás lo que llamo un ''predicado público'' que no hace mucho excepto imponer restricciones e invocar un predicado auxiliar ''privado'' que hace todo el trabajo. A menudo, ese predicado auxiliar tendrá el mismo nombre que el predicado público con una aridad diferente ( foo/3 en oposición al foo/2 del predicado público, por ejemplo). Algo como esto:

% % count the number of circular primes below the specified % upper limit. % count_circular_primes( Max , Cnt ) :- integer(Max) , Max >= 1 , Max =< 10000 , count_circular_primes( Max , 0 , Cnt ) .

El predicado auxiliar aquí, count_circular_primes/3 usa un valor de acumulador que se identifica como 0. Parece algo así como:

count_circular_primes( 0 , Cnt , Cnt ) . count_circular_primes( N , T , Cnt ) :- N > 0 , is_circular_prime(N) , T1 is T + 1 , N1 is N - 1 , count_circular_primes(N1,T1,Cnt) .

Notarás que aquí es donde ocurre todo el recuento. Lo único que queda por hacer es determinar si un entero en particular es un primo circular o no. ¡Fácil!

También notará que la variable de resultado Cnt no está unificada con nada hasta que se complete toda la operación recursiva. Cuando N llega a cero, el acumulador T se unifica con el resultado.

Ahora que el marco está en su lugar, pensemos en cómo determinar si un solo entero es un primo circular o no. Eso debería ser bastante fácil:

¿Es el número principal?
Trátelo como un buffer circular y gire los dígitos 1 lugar a la izquierda
Repite hasta llegar al principio.

Así es como haría una rotación de listas. Retroceder producirá todo el conjunto de rotaciones de lista:

rotate(Xs,Ys) :- append(A,[B|C],Xs) , % get the prefix (A) , suffix (C) and current item (B) from Xs append(C,A,D) , % append the suffic (C) to the prefix (A) to get the leftmost bit (B) append([B],D,Ys) % append the current item (B) to the leftmost bit (D) to get the rotation .

Así es cómo funciona: append/3 se puede usar para generar todas las posibles combinaciones de prefijo / sufijo para una lista específica. Si digo append(Prefix,Suffix,[1,2,3,4]) el conjunto completo de soluciones devuelto a través de back-tracking es

Prefix Suffix ========= ========= [] [1,2,3,4] [1] [2,3,4] [1,2] [3,4] [1,2,3] [4] [1,2,3,4] []

Una vez que puede generar las rotaciones, se puede usar findall/3 para obtener toda la solución configurada como una lista, dada una entrada particular. Entonces, dado el anterior predicado rotate/2 , puedo decir algo como:

findall( X , rotate( [1,2,3,4] , X ) , Rotations ).

Rotations se unificarán con esta lista de listas:

[ [1,2,3,4] , [2,3,4,1] , [3,4,1,2] , [4,1,2,3] ]

Una vez que tenga el conjunto de rotaciones, todo lo que tiene que hacer es evaluar si representa o no un número primo. Puedes hacer eso con forall/2 , en esta línea:

forall( member(Rotation,Rotations), is_prime(Rotation) )

Las cosas se ponen un poco más complicadas si no tienes permitido usar findall/3 y forall/2 , pero creo que esto te debería seguir.

"retroceder" es el nombre del concepto; significa volver sobre uno mismo, renegar de la decisión de uno si ha sido desafortunado. En los programas de Prolog tenemos reglas que muestran qué sub-objetivos deben ser probados, para que el objetivo principal ( jefe de la regla ) se considere probado. Cuando hay varias reglas, podemos intentar primero; y si luego resulta que no se puede probar, volvemos al último punto de decisión y tratamos de probar la siguiente regla, si está disponible.

En el futuro, instanciamos nuestras variables, dándoles valores. Una vez que se determina un valor para una variable, no se puede cambiar, mientras seguimos adelante para demostrar nuestro objetivo. Cuando decimos que X=2 , nos comprometemos con esta elección. Ahora no podemos decir que X=5 , entonces seríamos mentirosos, y nuestra "prueba" carecería de valor.

La esencia de Prolog es que, mientras avanzamos hacia la demostración de nuestro objetivo y tomamos varias decisiones sobre qué es qué, recogemos esos valores en lo que se conoce como sustitución , un mapeo entre variables y sus valores, que no es contradictorio; y cuando alcanzamos el objetivo final, este conjunto de valores para nuestras variables es nuestra respuesta.

Pero cuando fallamos y debemos retroceder, todas las instancias que hemos realizado hasta el momento se deshacen, en el orden inverso.

Específicamente, NumCirc =:= RealNum no es una asignación. Es una comparación numérica que puede ser verdadera o falsa. Si es cierto, decimos que el objetivo NumCirc =:= RealNum tiene éxito (está demostrado). Si es falso, decimos que el objetivo falló y, por lo tanto, damos marcha atrás.

Otro concepto clave es la unificación : cuando decimos X = Y , afirmamos que ambos son lo mismo. Por supuesto 4=4 tiene éxito, y 3=4 falla.

Y sí, Prolog es esencialmente un lenguaje establecido una vez (sin retroceso, que deshace la tarea, no la cambia , haciendo que la variable no sea asignada nuevamente).