tutorial sintaxis portable online elementos ejemplos descargar prolog

prolog - sintaxis - Definición más compacta



prolog tutorial (7)

Con las sugerencias de Guy coder esto esta mas cerca?

unfold([], []). unfold([H|T], [[a|H], [b|H]|L]) :- unfold(T, L). ab([], [[]]). ab([_|N1],L):- ab(N1, L1), unfold(L1, L). word(X):- length(List,_), ab(List,Values), member(X,Values).

word/1 dada word/1 ,

word(W) :- abs(ABs), ABs = W. abs([]). abs([AB|ABs]) :- abs(ABs), ab(AB). ab(a). ab(b). ?- word(W). W = [] ; W = [a] ; W = [b] ; W = [a,a] ; W = [b,a] ; W = [a,b] ; W = [b,b] ; W = [a,a,a] ; W = [b,a,a] ; W = [a,b,a] ; W = [b,b,a] ; W = [a,a,b] ; W = [b,a,b] ; W = [a,b,b] ; W = [b,b,b] ; W = [a,a,a,a] ...

cómo se ve una definición más compacta de word/1 , de lo contrario, la terminación de escritura idéntica y el conjunto de soluciones, equidad, con las siguientes restricciones:

  1. No se utilizan elementos incorporados como (=)/2 .

  2. No se utilizan construcciones de control como ('','')/2 o (;)/2 , o call/1 .

  3. Utiliza un hecho, una regla recursiva y una regla para word/1 .

Quizás más sencillo es pedir los términos F1 ... F4 en:

word(W) :- p(F1). p(F2). p(F3) :- p(F4).

Para el registro: la propiedad explotada aquí está estrechamente relacionada con la indecidibilidad de la terminación de una única cláusula binaria. La alabanza va a:

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier y Jörg Würtz. Una cláusula de bocina binaria es suficiente STACS ''94 .

Entonces, para aclarar, ¿la solución prevista es una instancia del siguiente esquema?

combine(X,Y,[X,Y]). product(P,Xs,Ys,PXYs) :- product1(Xs,Ys,PXYs,P). product1([],_,[],_). product1([X|Xs],Ys,PXYs0,P) :- product1(Ys,X,P,PXYs0,PXYs1), product1(Xs,Ys,PXYs1,P). product1([],_,_) --> []. product1([Y|Ys],X,P) --> { call(P,X,Y,PXY) }, [PXY], product1(Ys,X,P). ?- product(combine,[a,b],[a,b],R). R = [[a, a], [a, b], [b, a], [b, b]].

¿Donde cada ocurrencia de una variable Args significa cero o más términos y presumiblemente (pero no necesariamente) el fact y la recursive_rule son en realidad el mismo functor?

Está bien, así que no es una respuesta todavía.

Lo más cerca que tuve fue:

s_s1([],[a]). s_s1([b|T],[a|T]). s_s1([a|T],[b|T2]):- s_s1(T,T2). word([]). word(W2):- word(W), s_s1(W,W2).

Lo que tampoco cumple con los criterios ni da las soluciones adecuadas!

Entonces, luego pensé que podríamos intentar usar Prolog para encontrar la respuesta. La estructura está dada, así que necesitamos buscar los argumentos.

%First define the first 16 correct solutions.. correct_sols(X):- X=[ [], [a], [b], [a,a], [b,a], [a,b], [b,b], [a,a,a], [b,a,a], [a,b,a], [b,b,a], [a,a,b], [b,a,b], [a,b,b], [b,b,b], [a,a,a,a] ]. %Then a mi provable(true, _) :- !. provable((G1,G2), Defs) :- !, provable(G1, Defs), provable(G2, Defs). provable(BI, _) :- predicate_property(BI, built_in), !, call(BI). provable(Goal, Defs) :- member(Def, Defs), copy_term(Def, Goal-Body), provable(Body, Defs). %From 4 Vars find 16 solutions to word(X) vars_16sols(Vars,List):- Vars =[Args,Args0,Args1,Argsx], findnsols(16,X,provable(word(X),[ a(Args)-true, a(Args0)-a(Args1), word(X)-a(Argsx)] ),List). %Evaluate the score, for the solutions found how many match correct evaluate_score(Solutions,Score):- correct_sols(C), maplist(correct_test_tf,C,Solutions,TrueFalse), findall(_,member(true,TrueFalse),Matches), length(Matches,Score). %The main search, give a form for the starting 4 arguments, if they match all 16 correct stop. startingargs_solution(Start,Sol):- vars_16sols(Start,SolsStart), evaluate_score(SolsStart,Score), Score =16, SolsStart=Sol. %Othewise refine args, and try again. startingargs_solution(Start,Sol):- vars_16sols(Start,SolsStart), evaluate_score(SolsStart,Score), Score <16, start_refined(Start,Refined), startingargs_solution(Refined,Sol).

Todavía tendríamos que definir:

  1. correct_test_tf / 3
  2. start_refined / 2 con algunas restricciones, como el tamaño de los términos para args (debe ser razonable para ser una "definición compacta", y qué cosas deben incluirse, es decir, al menos a y b algún lugar y probablemente [] .

Claramente no ha terminado y no estoy seguro de si será posible hacer esto, pero pensé que publicaría una respuesta para ver qué tiene que decir la gente ... ¡La búsqueda es ingenua en este momento!

Esto solo está probando las primeras 16 soluciones, pero tal vez eso sea adecuado para obtener una respuesta correcta.

¡Quizás esto sea más difícil que resolver la pregunta por sí mismo!

La solución que he encontrado es:

word(W) :- p([[]|Ls], Ls, W). p([W|_], _, W). p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- p(Ws, Ls, W).

Consulta de muestra y respuesta:

?- word(W). W = [] ; W = [a] ; W = [b] ; W = [a, a] ; W = [b, a] ; W = [a, b] ; W = [b, b] ; W = [a, a, a] ; W = [b, a, a] ; W = [a, b, a] ; W = [b, b, a] ; W = [a, a, b] ; W = [b, a, b] ; W = [a, b, b] ; W = [b, b, b] ; W = [a, a, a, a] ; W = [b, a, a, a] ; etc.

Estoy usando una lista de diferencias para materializar de manera incremental las soluciones que quiero que informe el nivel superior.

Mi más cercano aún.

fact(Args). recursive_rule(Args0) :- recursive_rule(Args1). word(W) :- recursive_rule(Args).


unfold20([], []). unfold20([H|T], [[a|H], [b|H]|L]) :- unfold20(T, L). member20(X, [X|_]). member20(X, [_|Tail]) :- member20(X, Tail). swap20(R,R) :- write(''swap20 R: ''),write(R),nl. swap20(In,L) :- write(''swap20 In: ''),write(In),nl, unfold20(In,L), swap20(L,_), write(''swap20 L: ''),write(L),nl. word20(W) :- swap20([[]],L), write(''word20 L: ''),write(L),nl, member20(W,L), write(''word20 W: ''),write(W),nl.

Si miras verás que no sirve de nada ; que estoy seguro es un problema que algunas personas están teniendo. Además, todas las reglas son lo suficientemente simples como para que puedan integrarse en los requisitos mediante el uso de argumentos adicionales. por ejemplo, unfold(A,B) se convertiría en unfold(A,B,C,D) o una variación.

El problema con esta versión es que recibo las respuestas correctas a medida que avanza la evaluación, simplemente las está devolviendo al nivel superior.

p.ej

?- word20(X). swap20 R: [[]] word20 L: [[]] word20 W: [] X = [] ; swap20 In: [[]] swap20 R: [[a],[b]] swap20 L: [[a],[b]] word20 L: [[a],[b]] word20 W: [a] X = [a] ; word20 W: [b] X = [b] ; swap20 In: [[a],[b]] swap20 R: [[a,a],[b,a],[a,b],[b,b]] swap20 L: [[a,a],[b,a],[a,b],[b,b]] swap20 L: [[a],[b]] word20 L: [[a],[b]] word20 W: [a] X = [a] ; word20 W: [b] X = [b] ; swap20 In: [[a,a],[b,a],[a,b],[b,b]] swap20 R: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]] swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]] swap20 L: [[a,a],[b,a],[a,b],[b,b]] swap20 L: [[a],[b]] word20 L: [[a],[b]] word20 W: [a] X = [a] ; word20 W: [b] X = [b] ; swap20 In: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]] swap20 R: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]] swap20 L: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]] swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]] swap20 L: [[a,a],[b,a],[a,b],[b,b]] swap20 L: [[a],[b]] word20 L: [[a],[b]] word20 W: [a] X = [a]

Seguiré trabajando en esto antes de la fecha límite, pero si alguien es capaz de usar lo que tengo aquí, felicitaciones, solo le pido que me dé crédito si alguna parte de esto lo ayudó a obtener la respuesta.

El predicado de unfold se basa en esta answer SO. Credito a salva

member es un viejo amigo. Observe que comienza con [[]] y no [] .

swap he creado este predicado. He cambiado de trabajo por una variación diferente, pero la variación falla por una razón diferente.

Suplemento

Salida del depurador de la respuesta de mat

Miré la respuesta de Mat más de cerca con un depurador porque podría contener la respuesta a un problema similar donde puedo generar las respuestas pero no devolverlas de forma independiente a Top.

La respuesta de Mat se copió aquí para referencia.

swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]] swap20 L: [[a,a],[b,a],[a,b],[b,b]] swap20 L: [[a],[b]]

La parte de interés está muy a la derecha como comentarios. Le sugeriría que copie desde aquí y pase a una aplicación que le permita ver toda la línea sin envolverla u ocultarla.

La columna de la izquierda se creó con SWI-Prolog ejecutando la consulta con trace y los comentarios de la derecha se crearon ejecutando la consulta con gtrace y copiando a mano los valores y anotando el nivel de sangría.

p([W|_], _, W). p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- p(Ws, Ls, W). word(W) :- p([[]|Ls], Ls, W).

No es una solución, sino una visión hacia una solución.

Esto comenzó con el uso de DCG

abs4 --> []. abs4 --> abs4, ([a] | [b]).


?- phrase(abs4,X). X = [] ; X = [a] ; X = [b] ; X = [a, a] ; X = [a, b] ; X = [b, a] ; X = [b, b] ; X = [a, a, a] ; X = [a, a, b] ; X = [a, b, a] ; X = [a, b, b] ; X = [b, a, a] ; X = [b, a, b] ; X = [b, b, a] ; X = [b, b, b] ; X = [a, a, a, a] ; X = [a, a, a, b] ;

luego mirando el listado

?- listing(abs4). abs4(A, A). abs4(A, C) :- abs4(A, B), ( B=[a|C] ; B=[b|C] ).

y el uso de member para eliminar el ; .

word5(W) :- abs5(W,[]). abs5(A, A). abs5(A, C) :- abs5(A, [D|C]), member5(D,[a,b]). member5(X, [X|_]). member5(X, [_|Tail]) :- member5(X, Tail).


?- word5(X). X = [] ; X = [a] ; X = [b] ; X = [a, a] ; X = [a, b] ; X = [b, a] ; X = [b, b] ; X = [a, a, a] ; X = [a, a, b] ; X = [a, b, a] ; X = [a, b, b] ; X = [b, a, a]

Normalmente los publicaría como una sola respuesta, pero @false me pidió que los mantuviera separados.

Si leíste mis comentarios y respuestas, verás que era consciente de que tenía que pasar el resultado de una iteración a la siguiente iteración. Lo que me dio una idea de eso fue usar un predicado de producto cruzado que encontré en

"The Craft of Prolog" por Richard A. O''Keefe pg. 243

Si usted es serio acerca de aprender Prolog, el libro es un deber tener.

Para citar el Prefacio

Hay muchos libros introductorios de Prolog. Este no es uno de ellos. Piense en ello como "segundos pasos en Prolog". Si ya ha leído uno de los libros de introducción, si ha tomado un curso de introducción a Prolog, si ha escrito uno o dos programas de Prolog, y si se pregunta por qué sigue siendo difícil escribir buenos programas de Prolog, este libro es destinado a ayudarte. El propósito del libro es mostrarte cómo puedes escribir programas Prolog que funcionen, que no lleven una cantidad de tiempo irrazonable y que estén lo suficientemente limpias como para mostrárselo a tus amigos.

Aquí hay una pequeña variación que utilicé para una variación que no funcionó.

?- word(W). Call: (8) word(_822) ? creep % word(W) :- Call: (9) p([[]|_1010], _1010, _822) ? creep % p([[]|Ls], Ls, W). Exit: (9) p([[]|_1010], _1010, []) ? creep % p([W|_], _, W). % W = [] Exit: (8) word([]) ? creep % p([[]|Ls], Ls, W). % W = [] W = [] ; Redo: (9) p([[]|_1010], _1010, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [] Ws = [[a],[b]|Ls] Call: (10) p([[a], [b]|_1028], _1028, _822) ? creep % p(Ws, Ls, W). % W0 = [] Ws = [[a],[b]|Ls] Exit: (10) p([[a], [b]|_1028], _1028, [a]) ? creep % p([W|_], _, W). % W = [a] Exit: (9) p([[], [a], [b]|_1028], [[a], [b]|_1028], [a]) ? creep % p(Ws, Ls, W). % W = [a] W0 = [] Ws = [[a],[b]|Ls] Exit: (8) word([a]) ? creep % p([[]|Ls], Ls, W). % W = [a] Ls = [[a],[b]|_2312] W = [a] ; Redo: (10) p([[a], [b]|_1028], _1028, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls] Call: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep % p(Ws, Ls, W). % W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls] Exit: (11) p([[b], [a, a], [b, a]|_1052], _1052, [b]) ? creep % p([W|_], _, W). % W = [b] Exit: (10) p([[a], [b], [a, a], [b, a]|_1052], [[a, a], [b, a]|_1052], [b]) ? creep % p(Ws, Ls, W). % W = [b] W0 = [a] Ws = [ [b],[a,a],[b,a]|Ls] Exit: (9) p([[], [a], [b], [a, a], [b, a]|_1052], [[a], [b], [a, a], [b, a]|_1052], [b]) ? creep % p(Ws, Ls, W). % W = [b] W0 = [] Ws = [[a],[b],[a,a],[b,a]|_2324] Ls = [ [a,a],[b,a]|_2324] Exit: (8) word([b]) ? creep % p([[]|Ls], Ls, W). % W = [b] Ls = [[a],[b],[a,a],[b,a]|_2324] W = [b] . Redo: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls] Call: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep % p(Ws, Ls, W). % W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls] Exit: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, [a, a]) ? creep % p([W|_], _, W). % W = [a,a] Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b]|Ls] Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [a] Ws = [ [b],[a,a],[b,a],[a,b],[b,b]|_2348] Ls = [ [a,b],[b,b]|_2348] Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...]|_1076], [[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep % p(Ws, Ls, W). % W = [a,a] W0 = [] Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348] Ls = [ [a,a],[b,a],[a,b],[b,b]|_2348] Exit: (8) word([a, a]) ? creep % p([[]|Ls], Ls, W). % W = [a,a] Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348] W = [a, a] ; Redo: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep Call: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, _822) ? creep % p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :- % W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls] Exit: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, [b, a]) ? creep % p(Ws, Ls, W). % W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls] Exit: (12) p([[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [[a, a, a], [b, a, a]|_1100], [b, a]) ? creep % p([W|_], _, W). % W = [b,a] Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b], [a, a|...], [b|...]|_1100], [[a, b], [b, b], [a, a, a], [b, a, a]|_1100], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [a,a] Ws = [ [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls] Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [b] Ws = [ [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,a,a],[b,a,a]|_2372] Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...], [...|...]|...], [[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [a] Ws = [ [b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,b],[b,b],[a,a,a],[b,a,a]|_2372] Exit: (8) word([b, a]) ? creep % p(Ws, Ls, W). % W = [b,a] W0 = [] Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] Ls = [ [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372] W = [b, a] ; % p([[]|Ls], Ls, W). % W = [b,a] Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]