PDF de programación - Temas de “Programación declarativa”

Temas de “Programación declarativa”

(2005–06)

José A. Alonso Jiménez
Andrés Cordón Franco

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 1 de Octubre de 2005 (versión de 6 de noviembre de 2006)

2

José A. Alonso y Andrés Cordón

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera espe-
cificada por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera
una obra derivada, sólo puede distribuir la obra generada bajo una licencia
idéntica a ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licen-
cia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta
licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Índice general

1. Introducción a Prolog

2. Listas, operadores y aritmética

3. Estructuras

4. Retroceso, corte y negación

5. Programación lógica de segundo orden

6. Estilo y eficiencia en programación lógica

7. Aplicaciones de PD:

problemas de grafos y el problema de las reinas

8. Procesamiento de lenguaje natural

Bibliografía

5

17

27

39

49

65

85

97

118

3

4

José A. Alonso y Andrés Cordón

Capítulo 1

Introducción a Prolog

5

6

José A. Alonso y Andrés Cordón

1Programacióndeclarativa(2005–06)Tema1:IntroducciónaPrologJoséA.AlonsoJiménezAndrésCordónFrancoGrupodeLógicaComputacionalDpto.CienciasdelaComputacióneInteligenciaArtificialUniversidaddeSevilla2Objetivosdelcurso•Lógicacomosistemadeespecificaciónylenguajedeprogramación.•Principios:◮Programas=Teorías.◮Ejecución=Búsquedadepruebas.◮Programación=Modelización.•Prolog=ProgramminginLogic.•Relacionesconotroscampos:◮Inteligenciaartificial.◮Sistemasbasadosenelconocimiento.◮Procesamientodellenguajenatural.•Pensardeclarativamente.Programación declarativa (2005–06)

7

3Declarativovs.imperativo•Paradigmas:◮Imperativo:Sedescribecómoresolverelproblema.◮Declarativo:Sedescribequéeselproblema.•Programas:◮Imperativo:Unasucesióndeinstrucciones.◮Declarativo:Unconjuntodesentencias.•Lenguajes:◮Imperativo:Pascal,C,Fortran.◮Declarativo:Prolog,Lisppuro,ML,Haskell,DLV,Smodels.•Ventajas;◮Imperativo:Programasrápidosyespecializados.◮Declarativo:Programasgenerales,cortosylegibles.4Historiadelaprogramaciónlógica•1960:Demostraciónautomáticadeteoremas.•1965:Resoluciónyunificación(Robinson).•1969:QA3,obtenciónderespuesta(Green).•1972:ImplementacióndeProlog(Colmerauer).•1974:Programaciónlógica(Kowalski).•1977:PrologdeEdimburgo(Warren).•1981:ProyectojaponésdeQuintaGeneración.•1986:Programaciónlógicaconrestricciones.•1995:EstándarISOdeProlog.8

José A. Alonso y Andrés Cordón

5DeducciónPrologenlógicaproposicional•Basedeconocimientoyobjetivo:◮Basedeconocimiento:•Regla1:Siunanimalesunguladoytienerayasnegras,entoncesesunacebra.•Regla2:Siunanimalrumiayesmamífero,entoncesesungulado.•Regla3:Siunanimalesmamíferoytienepezuñas,entoncesesungulado.•Hecho1:Elanimalesmamífero.•Hecho2:Elanimaltienepezuñas.•Hecho3:Elanimaltienerayasnegras.◮Objetivo:Demostrarapartirdelabasedeconocimientosqueelanimalesunacebra.6DeducciónPrologenlógicaproposicional•Programa:es_cebra:−es_ungulado,tiene_rayas_negras.%R1es_ungulado:−rumia,es_mamífero.%R2es_ungulado:−es_mamífero,tiene_pezuñas.%R3es_mamífero.%H1tiene_pezuñas.%H2tiene_rayas_negras.%H3•Sesión:>plWelcometoSWI−Prolog(Multi−threaded,Version5.3.14)Copyright(c)1990−2003UniversityofAmsterdam.?−[animales].Yes?−es_cebra.YesProgramación declarativa (2005–06)

9

7DeducciónPrologenlógicaproposicional•Árboldededucción:es_mamifero,:− rumia, tiene_rayas_negras.:− es_mamifero, tiene_pezuñas, tiene_rayas_negras. tiene_rayas_negras.:− es_ungulado,:− tiene_pezuñas, tiene_rayas_negras.:−.:− es_cebra.R1R3R2H1H2:− tiene_rayas_negras.H3FalloExito8DeducciónPrologenlógicaproposicional•DemostraciónporresoluciónSLD:es_ungulado :− es_mamifero, tiene_pezuñas.es_cebra :− es_ungulado, tiene_rayas_negras.:− tiene_pezuñas, tiene_rayas_negras.:− es_mamifero, tiene_pezuñas, tiene_rayas_negras.:− es_ungulado, tiene_rayas_negras.:− tiene_rayas_negras.:−.:− es_cebra.tiene_rayas_negras.tiene_pezuñas.es_mamifero.10

José A. Alonso y Andrés Cordón

9DeducciónPrologenlógicarelacional•Basedeconocimiento:◮Hechos1-4:6y12sondivisiblespor2ypor3.◮Hecho5:4esdivisiblepor2.◮Regla1:Losnúmerosdivisiblespor2ypor3sondivisiblespor6.•Programa:divide(2,6).%Hecho1divide(2,4).%Hecho2divide(2,12).%Hecho3divide(3,6).%Hecho4divide(3,12).%Hecho5divide(6,X):−divide(2,X),divide(3,X).%Regla110DeducciónPrologenlógicarelacional•Símbolos:◮Constantes:2,3,4,6,12◮Relaciónbinaria:divide◮Variable:X•InterpretacionesdelaRegla1:◮divide(6,X):-divide(2,X),divide(3,X).◮Interpretacióndeclarativa:(∀X)[divide(2,X)∧divide(3,X)→divide(6,X)]◮Interpretaciónprocedimental.•Consulta:¿Cuálessonlosmúltiplosde6??−divide(6,X).X=6;X=12;NoProgramación declarativa (2005–06)

11

11DeducciónPrologenlógicarelacional•Árboldededucción::− divide(6,X).:− divide(2,X), divide(3,X).:−.:−.:− divide(3,12).:− divide(3,4).:− divide(3,6).Respuesta X=6FalloRespuesta X=12R1H2{X/4}H1 {X/6}H3 {X/12}H4H5•Comentarios:◮Unificación.◮Cálculoderespuestas.◮Respuestasmúltiples.12DeducciónPrologenlógicafuncional•Representacióndelosnúmerosnaturales:0,s(0),s(s(0)),...•Definicióndelasuma:0+Y=Ys(X)+Y=s(X+Y)•Programasuma(0,Y,Y).%R1suma(s(X),Y,s(Z)):−suma(X,Y,Z).%R2•Consulta:¿Cuáleslasumades(0)ys(s(0))??−suma(s(0),s(s(0)),X).X=s(s(s(0)))Yes12

José A. Alonso y Andrés Cordón

13DeducciónPrologenlógicafuncional•Árboldededucción::− suma(s(0),s(s(0)),X0).:− suma(0,s(s(0)),Z1).:−.suma(0,Y2,Y2).{Y2/s(s(0)), Z1/s(s(0))}Resp.: X = X0 = s(Z1) = s(s(s(0)))suma(X1,Y1,Z1).{X1/0,Y1/s(s(0)),X0/s(Z1)}suma(s(X1),Y1,s(Z1)) :−14DeducciónPrologenlógicafuncional•Consulta:◮¿Cuáleslarestades(s(s(0)))ys(s(0))?◮Sesión:?−suma(X,s(s(0)),s(s(s(0)))).X=s(0);NoProgramación declarativa (2005–06)

13

15DeducciónPrologenlógicafuncional•Árboldededucción::− suma(X0,s(s(0)),s(s(s(0))).:− suma(X1,s(s(0)),s(s(0))).:−.:− suma(X2,s(s(0)),s(0)).suma(s(X3),Y3,s(Z3)) :−suma(X3,Y3,Z3).{X2/s(X3),Y3/s(s(0)),Z3/0}{X1/0, Y2/s(s(0))}suma(0,Y2,Y2).Resp: X=X0=s(X1)=s(0):− suma(X3,s(s(0)),0).Fallosuma(s(X1),Y1,s(Z1)) :−suma(X1,Y1,Z1).{X0/s(X1),Y1/s(s(0)),Z1/s(s(0))}suma(s(X2),Y2,s(Z2)) :−suma(X2,Y2,Z2).{X1/s(X2),Y2/s(s(0)),Z2/s(0)}16DeducciónPrologenlógicafuncional•Consulta:◮Pregunta:¿CuálessonlassolucionesdelaecuaciónX+Y=s(s(0))?◮Sesión:?−suma(X,Y,s(s(0))).X=0Y=s(s(0));X=s(0)Y=s(0);X=s(s(0))Y=0;No14

José A. Alonso y Andrés Cordón

17DeducciónPrologenlógicafuncional•Árboldededucción::− suma(X0,Y0,s(s(0))).:−.R2 {X0/s(X1), Y1/Y0, Z1/s(0)}:− suma(X1,Y0,s(0)).R1 {X1/0, Y2/s(0), Y0/s(0)}X=s(0)Y=s(0)R2 {X1/s(X2), Y2/Y0, Z2/0}R1 {X2/0, Y3/0, Y2/0}R1 {X0/0, Y1/s(s(0)), Y0/s(s(0)).:−.X=0Y=s(s(0)):− suma(X2,Y0,0).:−.X=s(s(0))Y=018DeducciónPrologenlógicafuncional•Consulta:◮Pregunta:resolverelsistemadeecuaciones1+X=YX+Y=1◮Sesión:?−suma(s(0),X,Y),suma(X,Y,s(0)).X=0Y=s(0);NoProgramación declarativa (2005–06)

15

19DeducciónPrologenlógicafuncional•Árboldededucción::− suma(s(0),X0,Y0) suma(X0,Y0,s(0)).:− suma(0,X0,Z1), suma(X0,s(Z1),s(0)).:− suma(X0,s(X0),s(0)).:−.X=0Y=s(0):− suma(X3,s(X0),0).R2 {X1/0, Y1/X0, Y0/s(Z1)}R1 {Z1/X0}R1 {X0/0}FalloR2 {X0/s(X3),Y3/s(X0),Z3/0}20Bibliografía•J.A.AlonsoyJ.BorregoDeducciónautomática(Vol.1:Construcciónlógicadesistemaslógicos)(Ed.Kronos,2002)◮Cap.2:IntroducciónalaprogramaciónlógicaconProlog.•I.BratkoPrologProgrammingforArtificialIntelligence(2nded.)(Addison–Wesley,1990)◮Cap.1:“AnoverviewofProlog”.◮Cap.2:“SyntaxandmeaningofPrologprograms”.•W.F.ClocksinyC.S.MellishProgramminginProlog(FourthEdition).(SpringerVerlag,1994)◮Cap.1:“Tutorialintroduction”.◮Cap.2:“Acloserlook”.16

José A. Alonso y Andrés Cordón

Capítulo 2

Listas, operadores y aritmética

17

18

José A. Alonso y Andrés Cordón

1Programacióndeclarativa(2005–06)Tema2:Listas,operadoresyaritméticaJoséA.AlonsoJiménezAndrésCordónFrancoGrupodeLógicaComputacionalDpto.CienciasdelaComputacióneInteligenciaArtificialUniversidaddeSevilla2Listas:Definicióndelistas•Definicióndelistas:◮Lalistavacía[]esunalista.◮SiLesunalista,entonces.(a,L)esunalista.•Ejemplos:?−.(a,.(b,[]))=[a,b]Yes?−.(X,Y)=[a].X=aY=[]?−.(X,Y)=[a,b].X=aY=[b]?−.(X,.(Y,Z))=[a,b].X=aY=bZ=[]Programación declarativa (2005–06)

19

3Listas:Escrituraabreviada•Escrituraabreviada:[X|Y]=.(X,Y)•Ejemplosconescrituraabreviada:?−[X|Y]=[a,b].X=aY=[b]?−[X|Y]=[a,b,c,d].X=aY=[b,c,d]?−[X,Y|Z]=[a,b,c,d].X=aY=bZ=[c,d]4Listas:Concatenación:Definición•Concatenacióndelistas(append):◮Especificación:conc(A,B,C)severificasiCeslalistaobtenidaescribiendoloselementosdelalistaBacontinuacióndeloselementosdelalistaA;esdecir,1.SiAeslalistavacía,entonceslaconcatenacióndeAyBesB.2.SiAesunalistacuyoprimerelementoesXycuyorestoesD,entonceslaconcatenacióndeAyBesunalistacuyoprimerelementoesXycuyorestoeslaconcatenacióndeDyB.Porejemplo,?−conc([a,b],[b,d],C).C=[a,b,b,d]◮Definición1:conc(A,B,C):−A=[],C=B.conc(A,B,C):−A=[X|D],conc(D,B,E),C=[X|E].◮Definición2:conc([],B,B).conc([X|D],B,[X|E]):−conc(D,B,E).20

José A. Alonso y Andrés Cordón

5Listas:Concatenación:Consultas•Concatenacióndelistas(append):◮Nota:Analogíaentreladefinicióndeconcyladesuma,◮Consulta:¿Cuáleselresultadodeconcatenarlaslistas[a,b]y[c,d,e]??−conc([a,b],[c,d,e],L).L=[a,b,c,d,e]◮Consulta:¿Quélistahayqueañadirlealalista[a,b]paraobtener[a,b,c,d]??−conc([a,b],L,[a,b,c,d]).L=[c,d]◮Consulta:¿Quédoslistashayqueconcatenarparaobtener[a,b]??−conc(L,