Eduard Gamonal

Avís: article orientat a estudiants d’Enginyeries en Informàtica de la FIB – UPC. Basat en les explicacions a classe del professor Enric Rodríguez.

La programació lògica es cursa en les assignatures d’«introducció a la lògica» i a «lògica per a la informàtica». La utilitat directa per un fíber és: calcular respostes pel concurs «Cifras y letras» o trobar una manera de resoldre el problema de missioners i caníbals. També es fa servir per calcular horaris de l’ACB o els mateixos de la FIB.

Problema de concatenació

Inducció per concatenació:

concat([], L, L).
concat([X|Y1], Y2, [X|Y3]) :- concat(Y1, Y2, Y3).

Vegem que si L1, L2 són llistes i L3 és una variable, aleshores la consulta

edu@debian:~$ prolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- concat(L1, L2, L3)

instancia (unifica) L3 amb la concatenació de L1 i L2.

Cas base

L1 és la llista buida []. Per la primera clàusula, tenim que L3 queda instanciada a L2, de manera que L3 s’instancia correctament.

Cas inductiu

Suposem que la llista L1 té almenys un element, és a dir, és de la forma [X | Y1]. Y1 amb longitud n+1. Aleshores, per hipòtesi d’inducció, la consulta

| ?- concat(Y1, L2, L3)

on Y3 és una variable, instancia Y3 a la concatenació de Y1 i Y2. Y1 té longitud n.
Per la segona clàusula, la consulta

| ?- concat([X|Y1], L2, L3).

instancia L3 a [X|Y3], que és la concatenació de X, Y1, Y2. Per tant, L3 queda instanciada correctament.

Avís: article orientat a estudiants d’Enginyeries en Informàtica de la FIB – UPC. Basat en les explicacions a classe del professor Enric Rodríguez.

La programació lògica es cursa en les assignatures d’«introducció a la lògica» i a «lògica per a la informàtica». La utilitat directa per un fíber és: calcular respostes pel concurs «Cifras y letras» o trobar una manera de resoldre el problema de missioners i caníbals. També es fa servir per calcular horaris de l’ACB o els mateixos de la FIB.

Introducció

Avui en dia fem servir les bases de dades relacionals. Tenim diverses taules amb continguts i entre ells diem quina relació tenen. Per exemple, si tenim una taula de ciutats i una altra de codis postals, en lloc de guardar quin codi postal pertany a cada ciutat, diem amb SQL «El codi 08030 i el 08080» pertanyen a Barcelona.

Seguint l’exemple dels apunts de classe, podríem tenir un model de base de dades deductiu en comptes de relacional. Nosaltres definim un concepte, i la base de dades ens dóna les respostes.

Ho aclarim:

Expressem les dades de la nostra base de dades com relacions o tuples:

pare(joan, pere)
pare(maria, pere)
germà(pere, vicent)
germà(pere, albert)
pare(x,y) = ‘y és pare de x’
germà(x,y) = ‘y és germà de x’

Imaginem-nos que volem incloure a la base de dades la relació tiet(x,y), que signifiqui ‘y és tiet de x’. Hi ha dues opcions:

1. Afegir a la base de dades totes les relacions possibles de tiet. Per exemple:
   tiet(joan, vicent); tiet(joan, albert), …Aquest enfocament té l’inconvenient que pot arribar a tenir un nombre quadriàtic de noves relacions i també que es poden introduir inconsistències.
2. Podem afegir una regla deductiva que permeti deduir quan hi ha relació de ‘tiet’ entre dos individus.

Adoneu-vos que la darrera expressió és una clàusula de Horn, que Prolog adora.

Així doncs, podem veure la nostra base de dades com un conjunt de clàusules:

Observació: totes les clàusules de la base de dades són de Horn. A més a més, totes tenen exactament un literal positiu. D’aquest tipus de clàusules se’n diu clàusules de programa.

A la mateixa base de dades vista com un programa prolog, s’escriuria

pere(joan,pere).
pere(maria,pere).
germa(pere, vicenç).
tiet(X,Y) :- pare(X,Z), germa(Z,Y)

Atenció: fixeu-vos que hi ha un punt al final de cada línia.

Les consultes de programes lògics (bases de dades) es fan mitjançant clàusules de Horn amb tots els literals negatius. Per aquest motiu, a aquest tipus de clàusules se les anomena clàusules objectiu.

Per exemple, sigui F la conjunció de les clàusules 1,2,3,4,5 anteriors. Imaginem que estem interessats en fer la següent consulta a la base de  dades:

Aquest problema és equivalent a veure que és insatisfactible.

Vegem amb resolució que el següent conjunt de clàusules és instat:

Resolució:
Clàusules 5+6

amb
Generen la 7:

Resolem la 7 amb la 1

amb

Afegim la clàusula 8:
8.

i resolem la 8 amb la 3

Una resposta a la consulta és u -> joan; v -> vicent.

Have you lost something? You may fall in love with the find command. GNU Find tells you where a file is, given a condition. You shall use regular expressions and parameters related to lots of file features, like last access date, last modification date, its i-node, the file format of the device where it’s being saved, etc.

The syntax is find dir1 … dirM cond1 .. condN. It will search the directory tree rooted at each diri, for i = 1 to M, all files matching conditions cond1 to condN evaluated from left to right.

Let’s see some examples:

1. find /bin -links +1
   Searches files in /bin and its subdirectories having 1 or more hard links.
2. find /bin -links +1 -type f
   Idem, but only matches regular files (-type f).
3. find -size +8k -printf ‘%p %s\n’
   If no directory root is given, the default is . (the working one). This command seeks files whose size is at least 8KB and writes its name and size.
4. find . -name core -exec rm -i {} \; -print
   Looks for files called «core» (-name core), asks for confirmation to delete them (-exec rm -i {} \;) and, after all, prints their name (-print). Notice that you can run any command with «-exec». In rm -i, -i stands for «Ask for a confirmation», and «{}» means «the file matching the conditions». «-exec» must be closed with «\;».
5. find /usr/include -name ‘*.h’ -exec grep -H SIGCHLD {} \;
   Looks from /usr/include on all files with the extension .h (-name ‘*.h’, with quotes to avoid the shell understanding the * as a metacharacter and letting the find command use it) and having the string «SIGCHLD». That is, for each file that has matched the conditions, «grep -H SIGCHLD» is run.
6. find -atime +1 -type f -exec mv {} TMP \;
   Moves files that haven’t been accessed today (-atime +1) to the dir called TMP, in our working directory.

Thanks FIB.