prolog - Cómo enumerar combinaciones usando DCG con CLP(FD) y múltiples restricciones

clpfd implicit-state-passing (2)

@lurker ya ha dado una excelente respuesta, y me gustaría hacer algunas observaciones complementarias.

En primer lugar, sería de gran ayuda si publicara nuevas preguntas si surge la necesidad de analizar un tema en particular con más detalle. Veo que los problemas que ha planteado ahora están relacionados temáticamente, y me gustaría dar una descripción general que espero aborde los aspectos centrales. Sin embargo, cada uno de estos temas se puede discutir con mucho más detalle, y la presentación de nuevas preguntas valdría la pena para permitir más espacio para descripciones más elaboradas.

Comienzo con la versión que llamaré su versión inicial :

e_b(t, B, B, U, U). e_b(u(E), B0, B1, U0, U2) :- U1 #= U0 + 1, e_b(E, B0, B1, U1, U2). e_b(b(E0, E1), B0, B3, U0, U2) :- B1 #= B0 + 1, e_b(E0, B1, B2, U0, U1), e_b(E1, B2, B3, U1, U2). e_b(U, B, Es) :- U #=< Us, B #=< Bs, e_b(Es, 0, Bs, 0, Us).

Esto resuelve la primera pregunta:

¿Se puede usar CLP (FD) con esta solución y, de ser así, cómo?

Sí , CLP (FD) obviamente se puede usar: ya lo estamos haciendo. Tenga en cuenta que conscientemente llamo a esta versión como la "inicial", porque simplemente ignoro todos los intentos que usan (is)/2 o (=:=)/2 . Simplemente use (#=)/2 cuando razone sobre números enteros, y benefíciese de su mayor generalidad sobre la aritmética de bajo nivel.

El principal problema con esta versión es que las consultas que deben finalizar no finalizan :

?- e_b(1, 2, Es), false. nontermination

¿Por qué es este el caso? Para encontrar un motivo, utilizo secciones de falla , reduciendo todo el programa a fragmentos que puedo entender más fácilmente. Para esto, simplemente inserto llamadas de false/0 en algunos puntos del programa.

Puedes probar puntos arbitrarios. Por ejemplo, mantengamos e_b/3 sin cambios , y cambie e_b/5 a:

e_b(t, B, B, U, U). e_b(u(E), B0, B1, U0, U2) :- U1 #= U0 + 1, false, ~~e_b(E, B0, B1, U1, U2)~~. e_b(b(E0, E1), B0, B3, U0, U2) :- B1 #= B0 + 1, e_b(E0, B1, B2, U0, U1), false, ~~e_b(E1, B2, B3, U1, U2)~~.

Estoy usando texto ~~tachado~~ para marcar objetivos que no pueden causar la no determinación . Incluso con esta versión modificada , obtenemos:

?- e_b(1, 2, Es), false. nontermination

¡Esto significa que la siguiente versión simplificada del programa aún exhibe la no determinación!

e_b(t, B, B, U, U). e_b(u(E), B0, B1, U0, U2) :- U1 #= U0 + 1. e_b(b(E0, E1), B0, B3, U0, U2) :- B1 #= B0 + 1, e_b(E0, B1, B2, U0, U1).

Estoy haciendo todo esto solo para descomponer el problema en partes más manejables. Que esta posibilidad exista es una gran atracción de la programación lógica. ¡Buena suerte aplicando tal técnica a otros lenguajes de programación, o incluso encontrando tal enfoque!

Ahora, la versión simplificada no informa las respuestas:

?- e_b(1, 2, Es). Es = u(_1064) ; Es = b(t, _1066) ; Es = b(u(_1070), _1066) ; Es = b(b(t, _1072), _1066) .

Pero, como dije, nuestra consulta tampoco finaliza de manera universal incluso con este programa simplificado:

?- e_b(1, 2, Es), false. nontermination

Para corregir el problema en la versión inicial, debemos corregirlo también en este fragmento. ¡No hay forma de evitarlo! Dicho de otra manera, mientras exista este problema de terminación en la versión simplificada, la versión inicial tampoco terminará.

Centrémonos, por tanto, en la versión simplificada, y primero ajustamos las variables para que no aparezcan más variables individuales . Estos problemas han surgido porque hemos eliminado algunos de los objetivos, y ahora simplemente estamos vinculando los pares de nuevo correctamente:

e_b(t, B, B, U, U). e_b(u(_), B, B, U0, U1) :- U1 #= U0 + 1. e_b(b(E0, _), B0, B, U0, U) :- B1 #= B0 + 1, e_b(E0, B1, B, U0, U).

Aquí está la consulta de nuevo:

?- e_b(1, 2, Es), false. nontermination

De hecho, la siguiente versión aún más simple aún muestra la no determinación:

e_b(t, B, B, U, U). ~~e_b(u(_), B, B, U0, U1) :-~~ ~~U1 #= U0 + 1.~~ e_b(b(E0, _), B0, B, U0, U) :- B1 #= B0 + 1, e_b(E0, B1, B, U0, U).

Aquí, simplemente eliminé una cláusula completa , haciendo que esto sea equivalente a:

e_b(t, B, B, U, U). e_b(b(E0, _), B0, B, U0, U) :- B1 #= B0 + 1, e_b(E0, B1, B, U0, U).

Entonces, ¿por qué esta versión simplificada no termina?

Como referencia, aquí está el programa completo del que estamos hablando en este momento:

e_b(t, B, B, U, U). e_b(b(E0, _), B0, B, U0, U) :- B1 #= B0 + 1, e_b(E0, B1, B, U0, U). e_b(U, B, Es) :- U #=< Us, B #=< Bs, e_b(Es, 0, Bs, 0, Us).

Con la consulta problemática aún siendo:

?- e_b(1, 2, Es). nontermination

Ahora, en este caso, de nuevo no obtenemos una solución , aunque esperamos una. ¿Cómo podemos depurar esto? Hagamos lo más obvio (si lo piensas): pregúntale a Prolog qué soluciones hay . Hacemos esto al plantear la consulta más general , donde todos los argumentos son variables nuevas:

?- e_b(A, B, Es). Es = t, A in inf..0, B in inf..0 ; Es = b(t, _3532), A in inf..0, B in inf..1 ; Es = b(b(t, _3550), _3544), A in inf..0, B in inf..2 .

Ahora ya hay primeros signos de problemas en estas respuestas. Por ejemplo, ¿quién ha oído hablar de árboles con profundidad negativa ?

Hagamos cumplir requisitos más razonables publicando:

?- A #>= 0, B #>= 0, e_b(A, B, Es). A = B, B = 0, Es = t ; A = 0, Es = b(t, _8094), B in 0..1 ; A = 0, Es = b(b(t, _8112), _8106), B in 0..2 .

Esto se ve mucho mejor, pero no soluciona el problema central. Para obtener el comportamiento de terminación para consultas más específicas, necesita encontrar una manera de mantener la búsqueda limitada . Dejo esto como un ejercicio por ahora, y lo aliento a que presente una nueva pregunta si desea obtener más información al respecto. ¡Enfócate en este simple fragmento por ahora!

Ahora a la segunda pregunta:

¿Cuándo se requiere el uso de longitud / 2 para restringir el tamaño de los resultados de DCG y cuándo se puede usar CLP (FD)?

length/2 se puede usar para generar listas de mayor longitud . Los DCG siempre describen listas . En Prolog, es natural usar la longitud de una lista como medida de algo . Por ejemplo, podemos usar la longitud de una lista como medida de la profundidad de los términos que está tratando de encontrar. Esto es adecuado porque Prolog proporciona una sintaxis agradable para las listas, y puede ser más conveniente razonar simbólicamente que razonar numéricamente .

Al razonar sobre enteros , use restricciones CLP (FD) . Por lo tanto, si decide usar un número entero como la medida de algo, use las restricciones CLP (FD).

Esto nos lleva a la tercera pregunta:

¿Qué otros medios están disponibles para causar profundización iterativa con DCG?

length/2para describir las listas de longitud creciente es, con mucho, la forma más natural, si el propio DCG toma esta medida en cuenta en la lista que describe. Sin embargo, también se pueden utilizar otras formas, si se utiliza un dedicado argumento o argumentos par de pasar al estado de la medida alrededor.

Las dos últimas preguntas se relacionan:

¿Cómo iba a convertir la solución no DCG de nuevo en una versión DCG? Como mi DCG se vuelven más complejos que voy a necesitar más variables de restricción. ¿Existe una práctica estándar en la manera de manejar esto, o simplemente seguir el enjuague y repetir la metodología?

Cada vez que vea un patrón de la forma V0y el rightarrow; V1&flecha correcta; V2Y rightarrow; ... y rightarrow; Ves decir, una variable que se pasa simplemente a lo largo de un cuerpo cláusula, se puede utilizar DCG notación semicontext pasarlo alrededor implícita . Su código exhibe este patrón, y así DCG son aplicables.

Para una variable, utilice una lista de un solo elemento que contiene solo esa variable. Si desea pasar alrededor de más de una variable, utilice una lista que contiene un solo término de la forma f(...), la captura de todas las variables que desea pasar alrededor. Esto también merece su propia pregunta.

Tengo una nota final sobre la elección de la representación . Por favor, intente con el siguiente, utilizando, por ejemplo GNU Prolog o cualquier otro sistema Prolog conformes:

| ?- write_canonical([op(add),[Left,Right]]). ''.''(op(add),''.''(''.''(_18,''.''(_19,[])),[]))

Esto demuestra que este es un lugar derrochador representación, y al mismo tiempo evita que el tratamiento uniforme de todas las expresiones que generan, la combinación de varias desventajas.

Puede que esto sea más compacto, por ejemplo, el uso de Left+Right, o hacer que todos los términos disponibles de manera uniforme utilizando, por ejemplo op_arguments(add, [Left,Right]), op_arguments(number, [1])etc.

Esta pregunta parte de la respuesta de Mat al algoritmo de mejora para enumerar árboles binarios que tiene solo un valor de entrada que determina el número de todos los nodos para el árbol binario y la necesidad de poder tener dos valores de entrada, siendo uno el número de nodos unarios y el otro es la cantidad de nodos binarios.

Si bien pude derivar una solución al usar listing / 1 y enhebrar variables de estado adicionales:

e(t, B, B, U, U). e(u(E), B0, B1, [_|U0], U1) :- e(E, B0, B1, U0, U1). e(b(E0, E1), [_|B0], B2, U0, U2) :- e(E0, B0, B1, U0, U1), e(E1, B1, B2, U1, U2). e(U,B,Es) :- length(Bs, B), length(Us, U), e(Es,Bs,[],Us,[]).

Nota: Vea la salida de Prolog a continuación.

No estaba satisfecho con el uso de length / 2 como una restricción ya que no es obvio en su uso y no estaba usando DCG. De otros intentos previos a otros problemas, sabía que usar números como restricción fallaría, por ejemplo

e_a(t, B, B, U, U). e_a(u(E), B0, B1, U0, U2) :- U1 is U0 + 1, e_a(E, B0, B1, U1, U2). e_a(b(E0, E1), B0, B3, U0, U2) :- B1 is B0 + 1, e_a(E0, B1, B2, U0, U1), e_a(E1, B2, B3, U1, U2). e_a(U,B,Es) :- U =:= Us, % Arguments are not sufficiently instantiated 1=:=_2692 B =:= Bs, e_a(Es,0,Bs,0,Us). ?- e_a(1,2,Es).

Sin embargo, al buscar encontré el uso de CLP (FD) con DCG, y decidí probar eso.

:-use_module(library(clpfd)). e_b(t, B, B, U, U). e_b(u(E), B0, B1, U0, U2) :- U1 #= U0 + 1, e_b(E, B0, B1, U1, U2). e_b(b(E0, E1), B0, B3, U0, U2) :- B1 #= B0 + 1, e_b(E0, B1, B2, U0, U1), e_b(E1, B2, B3, U1, U2). e_b(U,B,Es) :- U #=< Us, B #=< Bs, e_b(Es,0,Bs,0,Us). ?- e_b(1,2,Es).

sin embargo, eso da como resultado un ciclo infinito que no devuelve resultados.
Nota: Entiendo los conceptos de CLP (FD) pero mi uso práctico con este es casi nulo.

Entonces las preguntas son:

¿Se puede usar CLP (FD) con esta solución y, de ser así, cómo?
¿Cómo convertiría la solución no DCG a una versión DCG?

Suplemento

Código de inicio y listado

e(number) --> []. e(u(Arg)) --> [_], e(Arg). e(b(Left,Right)) --> [_,_], e(Left), e(Right). ?- listing(e). e(t, A, A). e(u(A), [_|B], C) :- e(A, B, C). e(b(A, C), [_, _|B], E) :- e(A, B, D), e(C, D, E).

Salida Prolog

?- e(1,2,Es). Es = u(b(t, b(t, t))) ; Es = u(b(b(t, t), t)) ; Es = b(t, u(b(t, t))) ; Es = b(t, b(t, u(t))) ; Es = b(t, b(u(t), t)) ; Es = b(u(t), b(t, t)) ; Es = b(u(b(t, t)), t) ; Es = b(b(t, t), u(t)) ; Es = b(b(t, u(t)), t) ; Es = b(b(u(t), t), t) ; false.

Listado de respuestas

Para aquellos que no estén familiarizados con DCG, una herramienta de importación para tener en su caja de herramientas de Prolog es la lista / 1 que convertirá el DCG a Prolog estándar.

p.ej

?- listing(expression).

Para las siguientes listas también cambié el nombre de las variables a mano para que sean más fáciles de seguir y comprender. Cuando DCG se convierte a Prolog estándar, pueden aparecer dos variables adicionales como los dos últimos argumentos de un predicado. Aquí he cambiado sus nombres. Comenzarán con S0 como el penúltimo argumento y luego progresarán como S1 , S2 , y así sucesivamente hasta que sean el último argumento. Además, si uno de los argumentos de entrada se enhebra a través del código, he cambiado el nombre, por ejemplo, U a U0 y así sucesivamente. También agregué como comentarios las restricciones clp (fd).

Usando el listado / 1 en parte de la respuesta:

% DCG expression(U, B, E) --> terminal(U, B, E) | unary(U, B, E) | binary(U, B, E). % Standard Prolog expression(U, B, E, S0, S1) :- ( terminal(U, B, E, S0, S1) ; unary(U, B, E, S0, S1) ; binary(U, B, E, S0, S1) ).

% DCG terminal(0, 0, t) --> [t]. % Standard Prolog terminal(0, 0, t, [t|S0], S0).

% DCG unary(U, B, u(E)) --> { U1 #>= 0, U #= U1 + 1 }, [''u(''], expression_1(U1, B, E), ['')'']. % Standard Prolog unary(U0, B, u(E), S0, S4) :- true, clpfd:clpfd_geq(U1, 0), % U1 #>= 0 ( integer(U0) -> ( integer(U1) -> U0=:=U1+1 % U #= U1 + 1 ; U2=U0, clpfd:clpfd_equal(U2, U1+1) % U #= U1 + 1 ) ; integer(U1) -> ( var(U0) -> U0 is U1+1 % U #= U1 + 1 ; U2 is U1+1, % U #= U1 + 1 clpfd:clpfd_equal(U0, U2) ) ; clpfd:clpfd_equal(U0, U1+1) % U #= U1 + 1 ), S1=S0, S1=[''u(''|S2], expression_1(U1, B, E, S2, S3), S3=['')''|S4].

% DCG binary(U, B, b(E1, E2)) --> { U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1 }, [''b(''], expression_1(U1, B1, E1), expression_1(U2, B2, E2), ['')'']. % Standard Prolog binary(U0, B0, b(E1, E2), S0, S5) :- true, clpfd:clpfd_geq(U1, 0), % U1 #>= 0 true, clpfd:clpfd_geq(U2, 0), % U2 #>= 0 ( integer(U0) -> ( integer(U1), integer(U2) -> U0=:=U1+U2 % U #= U1 + 1 ; U3=U0, clpfd:clpfd_equal(U3, U1+U2) % U #= U1 + 1 ) ; integer(U1), integer(U2) -> ( var(U0) -> U0 is U1+U2 % U #= U1 + 1 ; U3 is U1+U2, % U #= U1 + 1 clpfd:clpfd_equal(U0, U3) ) ; clpfd:clpfd_equal(U0, U1+U2) % U #= U1 + 1 ), true, clpfd:clpfd_geq(B1, 0), % B1 #>= 0 true, clpfd:clpfd_geq(B2, 0), % B2 #>= 0 ( integer(B0) -> ( integer(B1), integer(B2) -> B0=:=B1+B2+1 % B #= B1 + B2 + 1 ; B3=B0, clpfd:clpfd_equal(B3, B1+B2+1) % B #= B1 + B2 + 1 ) ; integer(B1), integer(B2) -> ( var(B0) -> B0 is B1+B2+1 % B #= B1 + B2 + 1 ; B3 is B1+B2+1, % B #= B1 + B2 + 1 clpfd:clpfd_equal(B0, B3) ) ; clpfd:clpfd_equal(B0, B1+B2+1) % B #= B1 + B2 + 1 ), S1=S0, S1=[''b(''|S2], expression_1(U1, B1, E1, S2, S3), expression_1(U2, B2, E2, S3, S4), S4=['')''|S5].

Referencias al código fuente de SWI-Prolog

Si desea ver la fuente que traduce clp (fd) o DCG a prólogo estándar, aquí están los enlaces.

Notas

Piense en estos como mis notas personales en caso de que tenga que volver a esta pregunta en el futuro. No tiene sentido mantenerlos para mí si pueden ayudar a otros.

Con respecto a

¿Cuándo se requiere el uso de longitud / 2 para restringir el tamaño de los resultados de DCG y cuándo se puede usar CLP (FD)?

Después de ver el listado del código que usa clp (fd) como una restricción, puedo empezar a entender por qué se usa la construcción de listas paralelas y el uso de length/2 . No esperaba que el código fuera tan complejo.

Con respecto a cómo clp (fd) evita causar el error

Los argumentos no están suficientemente instanciados 1 =: = _ 2692

se puede ver que comprueba si la variable está vinculada o no

p.ej

integer(U1) var(U0)

Evolución del código

En base a la respuesta de @lurker pude convertir el código en esto, que es para poder generar todas las combinaciones de árboles unarios-binarios únicos con una lista de operaciones unarias, una lista de operaciones binarias y una lista de terminales. Si bien puede generar las combinaciones de las expresiones, aún necesita un paso intermedio para reorganizar el orden de los elementos en las tres listas antes de ser utilizado para generar las expresiones que necesito.

% order of predicates matters e( Uc , Uc , Bc , Bc , [Terminal|Terminal_s], Terminal_s , Unary_op_s , Unary_op_s , Binary_op_s , Binary_op_s , t , Terminal ). e( [_|Uc0], Uc1, Bc0 , Bc1, Terminal_s_0 , Terminal_s_1, [Unary_op|Unary_op_s_0], Unary_op_s_1, Binary_op_s_0 , Binary_op_s_1, u(E0) , [op(Unary_op),[UE]] ) :- e(Uc0 , Uc1, Bc0 , Bc1, Terminal_s_0 , Terminal_s_1, Unary_op_s_0 , Unary_op_s_1, Binary_op_s_0 , Binary_op_s_1, E0 , UE ). e( Uc0 , Uc2, [_|Bc0], Bc2, Terminal_s_0 , Terminal_s_2, Unary_op_s_0 , Unary_op_s_2, [Binary_op|Binary_op_s_0], Binary_op_s_2, b(E0, E1), [op(Binary_op),[L,R]] ) :- e(Uc0 , Uc1, Bc0 , Bc1, Terminal_s_0 , Terminal_s_1, Unary_op_s_0 , Unary_op_s_1, Binary_op_s_0 , Binary_op_s_1, E0 , L ), e(Uc1 , Uc2, Bc1 , Bc2, Terminal_s_1 , Terminal_s_2, Unary_op_s_1 , Unary_op_s_2, Binary_op_s_1 , Binary_op_s_2, E1 , R ). e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls) :- length(Bs, Bc), length(Us, Uc), e(Us,[], Bs,[], Terminal_s, _, Unary_op_s, _, Binary_op_s, _, Es, Ls). e(Unary_op_s, Binary_op_s, Terminal_s, Es, Ls) :- length(Unary_op_s,Uc), length(Binary_op_s,Bc), length(Terminal_s,Ts), Tc is Bc + 1, Ts == Tc, e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls).

Esta es la parte que necesito

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],_,Ls);true. Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(neg), [[op(ln), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [op(ln), [[number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]], [number(2)]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]], [number(2)]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[op(ln), [[number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[op(ln), [[number(1)]]]]], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [op(sub), [[number(1)], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]], [number(2)]]] ; true.

Y esta es una buena forma rápida de ver que son únicos.

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],Es,_);true. Es = u(u(b(t, b(t, t)))) ; Es = u(u(b(b(t, t), t))) ; Es = u(b(t, u(b(t, t)))) ; Es = u(b(t, b(t, u(t)))) ; Es = u(b(t, b(u(t), t))) ; Es = u(b(u(t), b(t, t))) ; Es = u(b(u(b(t, t)), t)) ; Es = u(b(b(t, t), u(t))) ; Es = u(b(b(t, u(t)), t)) ; Es = u(b(b(u(t), t), t)) ; Es = b(t, u(u(b(t, t)))) ; Es = b(t, u(b(t, u(t)))) ; Es = b(t, u(b(u(t), t))) ; Es = b(t, b(t, u(u(t)))) ; Es = b(t, b(u(t), u(t))) ; Es = b(t, b(u(u(t)), t)) ; Es = b(u(t), u(b(t, t))) ; Es = b(u(t), b(t, u(t))) ; Es = b(u(t), b(u(t), t)) ; Es = b(u(u(t)), b(t, t)) ; Es = b(u(u(b(t, t))), t) ; Es = b(u(b(t, t)), u(t)) ; Es = b(u(b(t, u(t))), t) ; Es = b(u(b(u(t), t)), t) ; Es = b(b(t, t), u(u(t))) ; Es = b(b(t, u(t)), u(t)) ; Es = b(b(t, u(u(t))), t) ; Es = b(b(u(t), t), u(t)) ; Es = b(b(u(t), u(t)), t) ; Es = b(b(u(u(t)), t), t) ; true.

Si ha estado leyendo los comentarios, entonces sabe que uno puede utilizar esto con una sola lista como restricción o sin lista como restricción.

Si desactiva la lista como restricciones usando

e(Uc, Bc, Terminal_s, Unary_op_s, Binary_op_s, Es, Ls) :- e(_,[], _,[], Terminal_s, _, Unary_op_s, _, Binary_op_s, _, Es, Ls).

Usted obtiene

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],_,Ls);true. Ls = [number(0)] ; Ls = [op(neg), [[number(0)]]] ; Ls = [op(neg), [[op(ln), [[number(0)]]]]] ; Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [number(1)]]]]]]] ; Ls = [op(neg), [[op(ln), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(neg), [[op(ln), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [number(1)]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[number(1)]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ; Ls = [op(neg), [[op(add), [[number(0)], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [number(1)]]]]] ; Ls = [op(neg), [[op(add), [[op(ln), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [number(1)]]], [op(ln), [[number(2)]]]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]], [number(2)]]]]] ; Ls = [op(neg), [[op(add), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]], [number(2)]]]]] ; Ls = [op(add), [[number(0)], [number(1)]]] ; Ls = [op(add), [[number(0)], [op(neg), [[number(1)]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(neg), [[op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [number(2)]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[number(1)], [op(neg), [[op(ln), [[number(2)]]]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [number(2)]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[number(1)]]], [op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[number(0)], [op(sub), [[op(neg), [[op(ln), [[number(1)]]]]], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [number(1)]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(ln), [[op(sub), [[number(1)], [number(2)]]]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[number(1)], [op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[op(neg), [[number(0)]]], [op(sub), [[op(ln), [[number(1)]]], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]] ; Ls = [op(add), [[op(neg), [[op(ln), [[number(0)]]]]], [op(sub), [[number(1)], [number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(ln), [[op(sub), [[number(0)], [number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [number(1)]]]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[number(0)], [op(ln), [[number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(neg), [[op(sub), [[op(ln), [[number(0)]]], [number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[number(2)]]]]] ; Ls = [op(add), [[op(sub), [[number(0)], [number(1)]]], [op(neg), [[op(ln), [[number(2)]]]]]]] ; Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[number(1)]]]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(sub), [[number(0)], [op(neg), [[op(ln), [[number(1)]]]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [number(1)]]], [op(ln), [[number(2)]]]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[number(0)]]], [op(ln), [[number(1)]]]]], [number(2)]]] ; Ls = [op(add), [[op(sub), [[op(neg), [[op(ln), [[number(0)]]]]], [number(1)]]], [number(2)]]] ; true.

?- e([neg,ln],[add,sub],[[number(0)],[number(1)],[number(2)]],Es,_);true. Es = t ; Es = u(t) ; Es = u(u(t)) ; Es = u(u(b(t, t))) ; Es = u(u(b(t, b(t, t)))) ; Es = u(u(b(b(t, t), t))) ; Es = u(b(t, t)) ; Es = u(b(t, u(t))) ; Es = u(b(t, u(b(t, t)))) ; Es = u(b(t, b(t, t))) ; Es = u(b(t, b(t, u(t)))) ; Es = u(b(t, b(u(t), t))) ; Es = u(b(u(t), t)) ; Es = u(b(u(t), b(t, t))) ; Es = u(b(u(b(t, t)), t)) ; Es = u(b(b(t, t), t)) ; Es = u(b(b(t, t), u(t))) ; Es = u(b(b(t, u(t)), t)) ; Es = u(b(b(u(t), t), t)) ; Es = b(t, t) ; Es = b(t, u(t)) ; Es = b(t, u(u(t))) ; Es = b(t, u(u(b(t, t)))) ; Es = b(t, u(b(t, t))) ; Es = b(t, u(b(t, u(t)))) ; Es = b(t, u(b(u(t), t))) ; Es = b(t, b(t, t)) ; Es = b(t, b(t, u(t))) ; Es = b(t, b(t, u(u(t)))) ; Es = b(t, b(u(t), t)) ; Es = b(t, b(u(t), u(t))) ; Es = b(t, b(u(u(t)), t)) ; Es = b(u(t), t) ; Es = b(u(t), u(t)) ; Es = b(u(t), u(b(t, t))) ; Es = b(u(t), b(t, t)) ; Es = b(u(t), b(t, u(t))) ; Es = b(u(t), b(u(t), t)) ; Es = b(u(u(t)), t) ; Es = b(u(u(t)), b(t, t)) ; Es = b(u(u(b(t, t))), t) ; Es = b(u(b(t, t)), t) ; Es = b(u(b(t, t)), u(t)) ; Es = b(u(b(t, u(t))), t) ; Es = b(u(b(u(t), t)), t) ; Es = b(b(t, t), t) ; Es = b(b(t, t), u(t)) ; Es = b(b(t, t), u(u(t))) ; Es = b(b(t, u(t)), t) ; Es = b(b(t, u(t)), u(t)) ; Es = b(b(t, u(u(t))), t) ; Es = b(b(u(t), t), t) ; Es = b(b(u(t), t), u(t)) ; Es = b(b(u(t), u(t)), t) ; Es = b(b(u(u(t)), t), t) ; true.

De cualquier forma es útil, solo tengo una preferencia personal por las generadas a partir de las restricciones por razones relacionadas con el proyecto que las usa.

La siguiente evolución vino refiriéndose a la respuesta de Mat.

e([number(0)] , t1 ) --> []. e([number(1)] , t2 ) --> []. e([number(2)] , t3 ) --> []. e([op(neg),[Arg]] , u1(E) ) --> [_], e(Arg,E). e([op(ln),[Arg]] , u2(E) ) --> [_], e(Arg,E). e([op(add),[Left,Right]], b1(E0,E1) ) --> [_,_], e(Left,E0), e(Right,E1). e([op(sub),[Left,Right]], b2(E0,E1) ) --> [_,_], e(Left,E0), e(Right,E1). e(EL,Es) :- length(Ls, _), phrase(e(EL,Es), Ls). es_count(M, Count) :- length([_|Ls], M), findall(., phrase(e(_,_), Ls), Sols), length(Sols, Count).

No mostraré los resultados ni explicaré esto en detalle ya que debería ser trivial en este momento. Es de destacar que genera dos tipos diferentes de resultados, el primero como una lista y el segundo como términos compuestos.

Original 5 preguntas

La pregunta original tenía 5 partes, pero en lugar de crear una nueva pregunta para esa respuesta, se eliminaron partes de esta pregunta para que la respuesta dada por lurker pudiera permanecer aquí.

¿Se puede usar CLP (FD) con esta solución y, de ser así, cómo?
¿Cuándo se requiere el uso de longitud / 2 para restringir el tamaño de los resultados de DCG y cuándo se puede usar CLP (FD)?
¿Qué otros medios están disponibles para causar profundización iterativa con DCG?
¿Cómo convertiría la solución no DCG a una versión DCG?
A medida que mi DCG se vuelva más compleja necesitaré más variables de restricción. ¿Existe una práctica estándar sobre cómo manejar esto o simplemente seguir la metodología de enjuague y repetición ?

Analizador de expresión de árbol básico con contadores

Suponiendo una representación de término compuesto para árboles unarios binarios ( p . Ej. , b(t,u(b(t,t,))) ), aquí hay un analizador básico. CLP (FD) generalmente se recomienda para razonar sobre enteros.

expression(U, B, E) :- terminal(U, B, E). expression(U, B, E) :- unary(U, B, E). expression(U, B, E) :- binary(U, B, E). terminal(0, 0, t). unary(U, B, u(E)) :- U1 #>= 0, U #= U1 + 1, expression(U1, B, E). binary(U, B, b(E1,E2)) :- U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1, expression(U1, B1, E1), expression(U2, B2, E2).

Hay un par de cosas que he hecho intencionalmente aquí. Una es usar CLP (FD) para darme más razonamiento relacional sobre los conteos para términos unarios y binarios. La otra cosa que he hecho es poner primero la cláusula simple expression/3 que no hace recursividad. De esta forma, Prolog llegará primero a las terminales en el proceso de explorar posibles soluciones.

Ejemplos de ejecuciones:

| ?- expression(1,2,E). E = u(b(t,b(t,t))) ? a E = u(b(b(t,t),t)) E = b(t,u(b(t,t))) E = b(t,b(t,u(t))) E = b(t,b(u(t),t)) E = b(u(t),b(t,t)) E = b(u(b(t,t)),t) E = b(b(t,t),u(t)) E = b(b(t,u(t)),t) E = b(b(u(t),t),t) (1 ms) no

| ?- expression(U, B, E). B = 0 E = t U = 0 ? ; B = 0 E = u(t) U = 1 ? ; B = 0 E = u(u(t)) U = 2 ? ; ...

Usando un DCG para representación secuencial

Un DCG se usa para analizar secuencias. El término compuesto se puede analizar como una secuencia de tokens o caracteres, que pueden, mediante el uso de un DCG, asignarse al término compuesto mismo. Podríamos, por ejemplo, representar el término de árbol compuesto b(t,u(b(t,t))) como [b, ''('', t, u, ''('', b, ''('', t, t, '')'', '')'', '')''] . Entonces podemos usar un DCG e incluir esa representación. Aquí hay un DCG que refleja la implementación anterior con este formato de secuencia:

expression(U, B, E) --> terminal(U, B, E) | unary(U, B, E) | binary(U, B, E). terminal(0, 0, t) --> [t]. unary(U, B, u(E)) --> [u, ''(''], { U1 #>= 0, U #= U1 + 1 }, expression(U1, B, E), ['')'']. binary(U, B, b(E1, E2)) --> [b, ''(''], { U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1 }, expression(U1, B1, E1), expression(U2, B2, E2), ['')''].

De nuevo, puse el terminal//3 como el primer curso de consulta para la expression//3 . Puede ver el paralelismo entre esto y la versión que no es DCG. Aquí hay ejemplos de ejecuciones.

| ?- phrase(expression(1,2,E), S). E = u(b(t,b(t,t))) S = [u,''('',b,''('',t,b,''('',t,t,'')'','')'','')''] ? a E = u(b(b(t,t),t)) S = [u,''('',b,''('',b,''('',t,t,'')'',t,'')'','')''] E = b(t,u(b(t,t))) S = [b,''('',t,u,''('',b,''('',t,t,'')'','')'','')''] E = b(t,b(t,u(t))) S = [b,''('',t,b,''('',t,u,''('',t,'')'','')'','')''] E = b(t,b(u(t),t)) S = [b,''('',t,b,''('',u,''('',t,'')'',t,'')'','')''] E = b(u(t),b(t,t)) S = [b,''('',u,''('',t,'')'',b,''('',t,t,'')'','')''] E = b(u(b(t,t)),t) S = [b,''('',u,''('',b,''('',t,t,'')'','')'',t,'')''] E = b(b(t,t),u(t)) S = [b,''('',b,''('',t,t,'')'',u,''('',t,'')'','')''] E = b(b(t,u(t)),t) S = [b,''('',b,''('',t,u,''('',t,'')'','')'',t,'')''] E = b(b(u(t),t),t) S = [b,''('',b,''('',u,''('',t,'')'',t,'')'',t,'')''] no | ?- phrase(expression(U,B,E), S). B = 0 E = t S = [t] U = 0 ? ; B = 0 E = u(t) S = [u,''('',t,'')''] U = 1 ? ; B = 0 E = u(u(t)) S = [u,''('',u,''('',t,'')'','')''] U = 2 ? ...

Esperemos que esto responda la pregunta n. ° 1 y tal vez n. ° 4 por ejemplo. El problema general de convertir cualquier conjunto de predicados a un DCG, sin embargo, es más difícil. Como mencioné anteriormente, DCG es realmente para manejar secuencias.

Usar length/2 para controlar el orden de la solución

En respuesta al n. ° 2, ahora que tenemos una solución DCG que generará soluciones de manera adecuada, podemos controlar el orden de las soluciones dadas utilizando length/2 , que proporcionará soluciones en orden de longitud en lugar de profundidad. Puede limitar la longitud desde el principio, lo que es más eficaz y eficiente que restringir la longitud en cada paso de la recursión, que es redundante:

?- length(S, _), phrase(expression(U,B,E), S). B = 0 E = t S = [t] U = 0 ? ; B = 0 E = u(t) S = [u,''('',t,'')''] U = 1 ? ; B = 1 E = b(t,t) S = [b,''('',t,t,'')''] U = 0 ? ; B = 0 E = u(u(t)) S = [u,''('',u,''('',t,'')'','')''] U = 2 ? ; B = 1 E = u(b(t,t)) S = [u,''('',b,''('',t,t,'')'','')''] U = 1 ? ; B = 1 E = b(t,u(t)) S = [b,''('',t,u,''('',t,'')'','')''] U = 1 ? ; B = 1 E = b(u(t),t) S = [b,''('',u,''('',t,'')'',t,'')''] U = 1 ? ...

Si estuviera usando la representación secuencial del árbol unario-binario para las soluciones restrictivas, no para el análisis sintáctico, me desharía de los paréntesis ya que no son necesarios en la representación:

unary(U, B, u(E)) --> [u], { U1 #>= 0, U #= U1 + 1 }, expression(U1, B, E). binary(U, B, b(E1, E2)) --> [b], { U1 #>= 0, U2 #>= 0, U #= U1 + U2, B1 #>= 0, B2 #>= 0, B #= B1 + B2 + 1 }, expression(U1, B1, E1), expression(U2, B2, E2).

Es probable que sea un poco más eficiente ya que hay un menor número de longitudes de lista que corresponden a secuencias no válidas. Esto resulta en:

| ?- length(S, _), phrase(expression(U, B, E), S). B = 0 E = t S = [t] U = 0 ? ; B = 0 E = u(t) S = [u,t] U = 1 ? ; B = 0 E = u(u(t)) S = [u,u,t] U = 2 ? ; B = 1 E = b(t,t) S = [b,t,t] U = 0 ? ; B = 0 E = u(u(u(t))) S = [u,u,u,t] U = 3 ? ; B = 1 E = u(b(t,t)) S = [u,b,t,t] U = 1 ? ; B = 1 E = b(t,u(t)) S = [b,t,u,t] U = 1 ? ; B = 1 E = b(u(t),t) S = [b,u,t,t] U = 1 ? ; B = 0 E = u(u(u(u(t)))) S = [u,u,u,u,t] U = 4 ? ; B = 1 E = u(u(b(t,t))) S = [u,u,b,t,t] U = 2 ? ; ...

Entonces, si tiene una definición recursiva de un término general, Term , que puede expresarse como una secuencia (por lo tanto, utilizando un DCG), entonces la length/2 puede usarse de esta manera para restringir las soluciones y ordenarlas por la duración de secuencia, que corresponde a algún orden de los términos originales. De hecho, la introducción de la length/2 puede evitar que su DCG recurra infinitamente sin presentar ninguna solución, pero preferiría que la DCG se comportara mejor desde el principio intentando organizar la lógica para recorrer primero las terminales.