Arxius

Introducció a Prolog i gprolog

Escrit al 2006-01-11 00:00:00 per cpina

En aquest article es veurà una introducció al llenguatge de programació Prolog (explicant, molt per sobre, el paradigma de programació lògic, diferent dels típics paradigmes imperatius o orientat a objectes, més coneguts).

L'article és vàlid per qui coneix Prolog però no sap utilitzar el compilador/intèrpret gprolog (lliure). També és suficient per qui vol veure quins aspectes tenen els programes amb Prolog, amb alguns exemples, etc.

Això sí, és un tema una mica dur de llegir...
Renúncia de responsabilitat: malauradament no sóc un expert amb Prolog. Així que és possible que s'hagi utilitzat algun concepte de forma no el més adequada. S'ha intentat que sigui fàcil de llegir, breu, però no incorrecte. Si hi ha alguna errada m'ho podeu fer arribar per correu electrònic: carles ARROBA pinux.info

Índex



  • Introducció
  • Instal·lar un compilador Prolog
  • Primer programa amb Prolog
  • Ordre d'avaluació
  • Seguir una traça
  • Llegir el codi d'un fitxer
  • Compilació
  • Petits exemples
  • Reflexió
  • Enllaços


    Introducció


    Molta gent programa en llenguatges de programació molt típics. Segur que sona molt familiar C, C++, Java, Perl, Python, scripts en Bash, etc.

    Tots aquests llenguatges de programació tenen un paradigma quasi comú: o bé són llenguatges imperatius o bé són llenguatges orientats a objectes (a més a més normalment es pot veure l'orientació a objectes com una capa per sobre dels imperatius).

    Es poden anomenar els següents paradigmes de programació (en alguns casos estan combinats):


  • Imperatiu. Per exemple C. Aquest paradigma inclou assignacions, bucles, funcions, etc.
  • Orientat a objectes. C++ i Java segurament són els més famosos. Simula és considerat el primer llenguatge de programació orientat a objectes, i Smalltalk és considerat un predecessor de Java. Inclou objectes, instanciar-ne, fer-ne de nous, métodes, etc.
  • Programació funcional. Lambda calculus és considerat el primer llenguatge funcional. Uns més moderns poden ser LISP (una implementació lliure és CLISP). Per entendre-ho en breus paraules, utilitzant programació funcional "pura" no hi ha assignació de variables ni bucles iteratius. S'evita qualsevol tipus d'efecte col·lateral pel fet d'executar una funció.
  • Programació lògica. El més famós és Prolog (Logic Programming). No hi ha iteracions com a tal, ni funcions, ni condicionals. Quan es comenta això tothom té curiositat... i com es programa? Ho veurem.
  • Programació orientada a events. Enlloc de ser totalment seqüencial, depén de l'interacció que faci l'usuari amb el programa. La programació visual sol utilitzar aquest tipus de paradigma.


    Hi ha molta informació sobre aquest tema a la Wikipedia. Paradigmes de programació (també en castellà), article que té enllaços a varis articles amb els paradigmes de programació comentats anteriorment i altres.

    En aquest article s'intentarà satisfer la curiositat de veure un parell de programes en Prolog, però no s'explicarà (ni molt menys) totes les possibilitats de Prolog, com funciona internament, etc. Per començar caldria una base de matemàtica lògica que no s'explicarà, sinó que només es vol veure una petita mostra de què es pot fer i com es pot fer. L'article també és útil per qui coneix alguna altra implementació de Prolog (com pot ser Visual Prolog) i vol donar els primers passos amb gprolog. La programació és semblant però primer un es pot sentir una mica desorientat de la nova manera d'interactuar amb el compilador.

    Instal·lant un compilador de Prolog


    Els dos compiladors lliures més utilitzats de Prolog són gprolog (gnu-Prolog) i swi-prolog. En aquest article es farà servir gprolog, tot i que amb swi-prolog seria molt semblant. Els dos accepten tenir funcions realitzades amb C (seguint certa nomenclatura) així que no ens hauriem de sentir limitats en cap aspecte (en el sentit que, si Prolog no tingués sockets podriem fer un wrapper a les crides de sockets en C).

    En Debian (o Ubuntu, etc.) es pot instal·lar el paquet "gprolog". A altres distribucions segurament hi ha un paquet equivalent. Aquest paquet conté compilador (per si volem generar binaris executables, com es fa amb el "gcc") i també l'intèrpret (que facilita el procés de proves i aprenentatge).

    Un cop el tenim instal·lat podem executar-lo amb "gprolog". gprolog quedarà a l'espera de noves ordres:

    carles@pinux:~$ gprolog
    GNU Prolog 1.2.18
    By Daniel Diaz
    Copyright (C) 1999-2004 Daniel Diaz
    | ?-


    Si es vol sortir de gprolog s'ha d'executar el predicat "halt". Tot predicat amb Prolog acaba amb ".". Per tant, per sortir, s'executarà:

    halt.


    Primer programa en prolog


    Prolog no és com un dels llenguatges imperatius més freqüentment coneguts, sinó que es basa en "fets" (facts) i "regles" (rules).

    Els fets


    El conjunt de fets formaran una base de dades de coneixement. Prolog consultarà aquests fets per saber certa informació. Un exemple de fet és:

    persona(jordi).


    És a dir, indiquem que "jordi" SÍ que és una persona. Prolog assumeix que qualsevol fet no conegut és fals (assumpció del món tancat).

    Cal també indicar que "jordi", com que és una cadena, ha d'anar en minúscules (o entre cometes). Si s'escriu "Jordi" Prolog interpretarà que és un símbol.

    Ara es veurà com es pot fer amb gprolog. S'executarà gprolog, i s'escriurà "consult(user).". La regla "consult" llegeix un fitxer ".pl" per treballar-hi, però el cas especial "user" serveix perqué esperi l'entrada de teclat.

    Llavors escriurem "persona(jordi).". Si no es volen escriure més fets, es farà "Control+D" (per indicar que ja ha acabat l'entrada de teclat).

    Si llavors s'escriu "persona(joan)." ens dirà "No". En canvi si s'executa "persona(jordi)." contestarà "yes", ja que en "jordi" és una persona. Veiem-ho:


    carles@pinux:~$ gprolog
    GNU Prolog 1.2.18
    By Daniel Diaz
    Copyright (C) 1999-2004 Daniel Diaz
    | ?- consult(user).
    compiling user for byte code...
    persona(jordi).

    user compiled, 2 lines read - 236 bytes written, 5062 ms

    (1 ms) yes
    | ?- persona(joan).

    no
    | ?- persona(jordi).

    yes
    | ?-

    Nota: Prolog interpreta els "textes" en minúcula com a cadenes, en canvi si comencen amb majúscula com simbols (un tipus de variables). Així que és case-sensitive i cal anar en compte per això.

    Les regles


    Normalment es treballa en conjuncions (AND's) i les regles són certes quan tots els fets o regles del seu llistat són certs. En el següent exemple es defineixen 4 fets (es defineix una persona que es diu "jordi", un gos que es diu "showen", un mascle que és en "jordi" i una femella, la "showen"). Finalment es fa una regla: X serà home si és una persona i és mascle.

    persona(jordi).
    gos(showen).
    mascle(jordi).
    femella(showen).

    home(X):-persona(X),mascle(X).

    Estrictament aquesta regla diu "ser home implica ser persona i ser mascle". Es pot entendre com "si és persona i mascle és un home". O bé "serà un home si és una persona i és mascle".

    Repetint els passos de l'apartat anterior (gprolog, consult(user)., escriure els fets, control+D) llavors es pot executar:

    | ?- home(showen).

    no
    | ?- home(jordi).

    yes
    | ?-

    Es pot veure que la X en la última regla és una variable, l'àmbit de les quals només és el de la regla definida.

    Entrada/sortida


    Prolog intenta interpretar els predicats tan com si són d'entrada com si són de sortida. Si es fan aquests fets:


    persona(jordi).
    persona(carla).
    persona(maria).
    persona(joan).


    Ja se sap que es pot demanar "jordi és una persona"? I contestarà "yes" o "no". Però amb Prolog també es pot fer "digues totes les persones" (pregunta molt simple aquest cas però que pot tenir gràcia altres casos):

    persona(Y).

    Retornarà:

    | ?- persona(Y).

    Y = jordi ? ;

    Y = carla ? ;

    Y = maria ? ;

    Y = joan

    (1 ms) yes
    | ?-

    Veure que, per tal de continuar, amb gprolog cal presionar ";" (en altres Prologs pot no fer falta).
    També es pot presionar "a", que indica "all" i donarà tots els resultats seguits.
    Per tant, amb aquest conjunt de predicats tan es pot demanar "és jordi una persona?" com "digues totes les persones" (o, afegint fets i una regla, totes les dones, homes, etc.)

    Ordre d'avaluació


    Prolog, quan es troba una regla, intenta veure si els fets que la componen, i d'esquerre a dreta, són certs. Primer comprova el de més a l'esquerre, a continuació el següent, etc.

    En cas que una regla no sigui certa, intenta aplicar backtracking. Això és, si una regla o un fet pot tenir varis resultats i havia agafat el primer, intentarà provar-ho amb el segon. Tot això automàtic, ens ve gratis amb Prolog! No s'ha d'implementar backtracking, ho fa sol. Per fer-se una idea, a l'entrada de la Wikipedia hi ha implementat l'algorisme d'ordenació Quicksort amb 5 regles (Quicksort és un algorisme recursiu, idoni per implementar-lo amb Prolog). Amb C ocuparia segurament mitja pàgina o una pàgina, i molt més enrevessat.

    Seguir una traça


    Un fet és una regla que és certa sempre. Per tant com a fet es pot tenir una regla del tipus:

    home(jordi):-write(jordi),nl.

    (nl: new line, salt de línia)
    La regla anterior escriu "jordi" per pantalla, i fa un salt de línia. Tant el predicat "write" com "nl" tornen cert, així que si s'intenta saber si hi ha un home anomenat "jordi", s'escriurà, es farà un salt de línia i serà cert que hi ha un home anomenat "jordi". Això pot ajudar per seguir la traça d'alguna execució.

    Ara es farà:

    persona(jordi):-write(pjordi),nl.
    persona(carla):-write(pcarla),nl.
    persona(maria):-write(pmaria),nl.
    persona(joan):-write(pjoan),nl.

    mascle(jordi):-write(mjordi),nl.
    mascle(joan):-write(mjoan),nl.

    femella(carla):-write(fcarla),nl.
    femella(maria):-write(fmaria),nl.

    dona(X):-persona(X),femella(X).


    I com a regla per executar, es fa:

    dona(Y).

    Presionant ";" es veuran els dos resultats que hi ha, però a més a més es pot comprovar l'ordre d'avaluació comentat anteriorment.

    Llegir el codi d'un fitxer


    Fins ara s'han fet petites execucions, escrivint cada cop l'entrada, però en programes més llargs això és incòmode. Si es vol tenir en un fitxer, es farà un fitxer de nom "programa.pl" amb el conjunt de fets i regles, i llavors des de gprolog:

    consult(programa).

    Si es copien els anteriors fets i regles dins un fitxer, es faria de la següent forma:

    carles@pinux:~$ gprolog
    GNU Prolog 1.2.18
    By Daniel Diaz
    Copyright (C) 1999-2004 Daniel Diaz
    | ?- consult(programa).
    compiling /home/carles/programa.pl for byte code...
    /home/carles/programa.pl compiled, 12 lines read - 1922 bytes written, 24 ms

    (1 ms) yes
    | ?- dona(Y).


    Compilació


    Potser es desitja generar un fitxer executable amb un programa que s'hagi fet amb Prolog. En aquest cas el procés és una mica diferent. Per exemple, es pot tenir un fitxer amb el següent contingut:

    inicial:-dona(Y),write(adeu),nl,halt.

    persona(jordi):-write(pjordi),nl.
    persona(carla):-write(pcarla),nl.
    persona(maria):-write(pmaria),nl.
    persona(joan):-write(pjoan),nl.

    mascle(jordi):-write(mjordi),nl.
    mascle(joan):-write(mjoan),nl.

    femella(carla):-write(fcarla),nl.
    femella(maria):-write(fmaria),nl.

    dona(X):-persona(X),femella(X).

    :-initialization(inicial).

    El "initialization" vindria a ser com el "main" de C, per on comença el programa. És un fet, i executarà "inicial". Al final de "inicial" hi ha halt, en cas contrari quan un usuari executi aquest fitxer hi haurà prolog a l'espera de noves ordres.

    Per compilar-lo és de la següent forma:

    carles@pinux:~/catux/prolog$ gplc comp.pl
    comp.pl:1 warning: singleton variables [Y] for inicial/0
    carles@pinux:~/catux/prolog$

    El warning és perqué la variable Y no es fa servir enlloc més (és com un "unusued variable"). Amb Prolog hi ha una variable anomenada anònima, representada amb el caràcter "_". Si canviem la Y per la variable anònim ja no ens mostrarà aquest warning.

    Petits exemples


    Hi ha una sèrie d'exemples, típics de Prolog (relacionats amb representació del coneixement) que són molt intuïtius (i fàcils de trobar a Internet).
    En canvi hi ha exemples amb poca tradició de Prolog, que la gent li sembla difícil de fer en Prolog que no ho són tant. Aqusts són els que es veuran a continuació.

    Majoria d'edat (i predicat cut)


    Demanarà a l'usuari que escrigui la seva edat, i dirà si és menor o major d'edat.
    Una primera aproximació és:

    major :- write('Escriu la teva edat: '),read(EDAT),comprova(EDAT).
    comprova(E) :- E>=18,write('Ets major d edat'),nl.
    comprova(E) :- E<18,write('Ets menor d edat'),nl.


    Prolog escriu la pregunta, llegeix la resposta i comprova l'edat. Veure que si un és major, entra a la primera regla (el primer predicat és cert -E>=18-, per tant passa al segon predicat -write- que retorna cert i finalment escriu una nova línia). Després Prolog, que intenta trobar totes les solucions, fa el mateix amb la segona, que no es compleix (ja que E no serà menor que 18 si era major).

    Nota: quan l'usuari escriu l'edat cal acabar amb un ".". Si té 20 anys, l'usuari ha d'escriure "20."

    Si s'hagués fet, pensant amb una estructura if then else:

    comprova(E) :- E>=18,write('Ets major d edat'),nl.
    comprova(E) :- write('Ets menor d edat'),nl.

    Quan és major d'edat també escriure que és menor. La primera regla es compliria, i la segona també. En aquest cas, es pot utilitzar el predicat "cut" a la primera regla, que indica que si s'ha arribat al "cut" (representat per "!") no es faci backtracking en la regla que es trobi:

    major :- write('Escriu la teva edat: '),read(EDAT),comprova(EDAT).
    comprova(E) :- E>=18,write('Ets major d edat'),nl,!.
    comprova(E) :- write('Ets menor d edat'),nl.


    Comptador endarrera


    En aquest cas es farà un comptador endarrera. És a dir, comptar de 10 fins a 0:

    comptar(X) :- X>0,write(X),nl,Y is X-1,comptar(Y),write('retornant').
    comptar(_) :- write('FINAL'),nl.

    I el predicat a executar és comptar(10).
    Si es prova, es veurà com demana que premem ";" si es volen més solucions (o bé "a" si les volem totes). El programa aquest és recursiu, i com que tots els predicats hauran tornat cert interpreta que una solució és pujar un nivell de recursivitat (quan està fent el write de "retornant"), dos nivells, fins a tots els nivells.

    Si es vol evitar tenir totes les solucions es pot fer d'aquesta manera:

    comptar(X) :- X>0,write(X),nl,Y is X-1,comptar(Y),!.
    comptar(_) :- write('FINAL'),nl.

    Amb l'ajuda del cut es quedarà a la primera solució, sense intentar trobar-ne més.

    Recorrer una llista


    Amb Prolog l'usuari pot definir nous tipus de dades (no es veurà aquí) o bé utilitzar llistes (es pot fer un símil amb els arrays).

    Les llistes estan representades de la forma [10,12,8,7,15].

    Si es vol recòrrer una llista es pot fer de la següent manera:

    imprimir([H|T]):-write(H),write('-'),imprimir(T).
    imprimir([]).

    I llavors començar l'execució de la següent forma:

    | ?- imprimir([10,20,10,40]).

    H i T són dues lletres qualsevol, que en cas volen dir "Head" i "Tail". Head contindrà el primer element de la llista, Tail el demés. S'imprimeix el qué val el primer element (enlloc d'imprimir es podria fer qualsevol operació, buscar un element, sumar, etc.) i es crida amb la resta de la llista.

    Cal la segona línia ( imprimir([]). ) ja que sinó imprimiria la llista però acabaria amb "no" enlloc de "yes" (no es podria "unificar" quan la llista és buida, ja que no tindria ja l'estructura [H|T] requerida en la primera regla). Si acaba amb "no" seria difícil utilitzar aquestes regles en altres programes, ja que sempre fallaria al imprimir la llista.

    Sumar els elements d'una llista


    Aquest és l'últim exemple, de moment. Sumarà els elements d'una llista:

    sumar([H|T],S_ENT,S_SURT):-write(H),write('-'),sumar(T,S_ENT + H,Y),S_SURT is Y.
    sumar([],S_ENT,S_ENT).

    Si s'executa (recordar fer un consult(user). o d'un fitxer) es veurà:


    | ?- sumar([10,20,5,2],0,X).
    10-20-5-2-

    X = 37

    (1 ms) yes
    | ?-

    El qué fa, és, enlloc d'imprimir els números, fer-ne sumes.

    Pot costar de veure, ja que normalment (si més no jo) s'està poc acostumat a la programació recursiva. S'anirà cridant a cada imprimir amb la suma anterior més el número actual. Quan s'arribi a l'últim "sumar" es retornarà per la sortida el S_ENT, ja que cal propagar-ho de tornada. De tornada es va retornant el Y, mitjançant S_SURT, fins que Prolog ens ensenyarà el resultat.

    Reflexió


    Prolog és un llenguatge de programació amb un paradigma que s'hi està poc habituat. Per programar bé en Prolog caldria no pensar "en imperatiu" i "adaptar-ho", sinó directament pensar en Prolog.

    Hi ha una sèrie de casos, sobretot dins la representació de coneixement, que és més natural fer-ho en Prolog que en altres llenguatges (tan natural que, tot i no saber gaire Prolog surten les regles sense pensar-ho).

    Hi ha altres casos que és més natural fer-ho amb llenguatges imperatius. De totes maneres, des de Prolog es poden executar funcions en C (i vice-versa!) amb la qual cosa es pot tenir el millor dels dos mons junts.

    Per poder escollir el millor llenguatge per cada cos cal coneixer-los, sinó no es podrà escollir bé. El despreci a alguns llenguatges sol venir del desconeixement d'aquests.

    Enllaços



  • Cridar codi C des de Prolog.
  • Llibre de Wikibooks sobre programació amb Prolog.
  • Un curs de gprolog


    Nota


    Si algú ha arribat aqui, és possible que més endavant es faci un article continuació d'aquest -amb dedicatòria al lector/lectora- o bé un de la mateixa temàtica però amb Lisp.
  • Categories: Articles


    Comentaris

    • Come on lads, give us another story

      Escrit al 2009-12-01 14:42:24 per Susan Ho

    Arxius