29 mai 2010

Implementarea unei stive in Clips

; fapte de indeplinit
(deffacts init
(push 5)
(pop)
(push abc)
(push 12)
(top)
(pop)
(top)
)

(defrule stack_init
; nu avem nici o condiţie în LHS; regula se execută la începutul programului
=>
; se iniţializează stiva cu un fapt vid
; celelalte reguli nu se vor aprinde decât dacă există un fapt stack
(assert (stack))
)

(defrule stack_push
?f1 <- (push ?element)
?f2 <- (stack $?stacklist)
=>
; o regulă se aplică o singură dată pentru aceeaşi condiţie
; în acest caz se şterge f1 pentru că se schimbă f2 şi deci se schimbă LHS ca întreg
(retract ?f1 ?f2)
; se introduce elementul în stivă
(assert (stack ?element $?stacklist))
(printout t "Push: " ?element crlf)
)

(defrule stack_pop
?f1 <- (pop)
?f2 <- (stack ?element $?stacklist)
=>
(retract ?f1 ?f2)
; se scoate elementul din stivă
(assert (stack $?stacklist))
(printout t "Pop: " ?element crlf)
)

(defrule stack_top
(top)
(stack ?element $?stacklist)
=>
(printout t "Top: " ?element crlf)
; aici nu avem nevoie să ştergem fapte, LHS rămâne neschimbată
)

27 mai 2010

CLIPS

;; rezolvarea problemei cu lupul, capra, varza si taranul care trebuie sa treaca podul
(deffacts fapte
(fail 0 1 1 0)
(fail 1 0 0 0)
(fail 0 1 1 1)
(fail 1 1 0 0)
(fail 0 0 1 1)
(fail 1 0 0 1)
(stop 0 0 0 0)
)

(deffunction fct
(?x)
(mod (+ 1 ?x) 2)
)

(defrule Taran
(stop ?t ?l ?c ?v)
(not (fail ?t1&~?t ?l ?c ?v))
=>
(assert (stop (fct ?t) ?l ?c ?v))
)

(defrule Capra
(stop ?t ?l ?t ?v)
(not (fail ?t1&~?t ?l ?c1&~?t ?v))
=>
(assert (stop (fct ?t) ?l (fct ?t) ?v))
)

(defrule Varza
(stop ?t ?l ?c ?t)
(not (fail ?t1&~?t ?l ?c ?v1&~?t))
=>
(assert (stop (fct ?t) ?l ?c (fct ?t)))
)

(defrule Lup
(stop ?t ?t ?c ?v)
(not (fail ?t1&~?t ?l1&~?t ?c ?v))
=>
(assert (stop (fct ?t) (fct ?t) ?c ?v))
)


;; un program care filtreaza numai elementele pozitive dintr-un sir

;; REZOLVARE
;; folosim un mic truc, retragem elementele negative.
;; pentru conditii mai complexe, se putea folosi not pe
;; conditia ceruta in problema.
(deffacts pb3 (rez3 6 -5 4 3 -2 -1 0))

(defrule filter-pos
?f <- (rez3 $?start ?x&:(< ?x 0) $?end)
=>
(retract ?f)
(assert (rez3 $?start $?end)))

25 mai 2010

Demonstrarea unui scop cf. unui set de clauze Horn

-- Un nucleu pentru demonstrarea unui scop conform unui set de clauze Horn.
-- Procedura de inferenta: rezolutie
-- Metoda de demonstrare: reducere la absurd
-- Strategie control: parcurgere in adincime a arborelui AND-OR al demonstratiei
-- CG mai, 2010

module Resolution where

data Subst a = VoidSubst | Bindings [(String,a)] deriving Show

solve goal all_props = solve' [goal] all_props VoidSubst where
solve' [] props subst = (True,subst) -- Frunza
solve' goals [] subst = (False,subst)
solve' (goal:goals) (prop:props) subst = -- nod OR
let (flag1,subst1) = unify goal (head prop) subst
in if flag1
then let (flag2,subst2) = solve' ((tail prop)++goals) all_props subst1 --nod AND
in if flag2 then (True,subst2)
else solve' (goal:goals) props subst
else solve' (goal:goals) props subst

unify term1 term2 subst = (term1==term2,VoidSubst)

--- O reprezentare simpla pentru termeni fara variabile

data Constant = Maria | Ion | Fred | Gigi deriving (Eq,Show)
data Predicate a = Iubeste a a | Human a | Prieten a a deriving (Eq,Show)

{-
1. Un termen este reprezentat ca un tuplu (predicat val1 val2 ... valn)
De exemplu tuplul (Iubeste Maria Ion) sta pentru iubeste(Maria,Ion)

2. O propozitie este o implicatie (clauza Horn) term1 ^ term2 ^ ... ^ termn => term, n>=1,
si este reprezentata prin lista [term, term1, term2, ..., termn]
De exemplu,
[Human Ion, Iubeste Maria Ion, Human Maria] sta pentru propozitia
iubeste(Maria,Ion) ^ human(Maria) => human(Ion)

3. Propozitia particulara True => term (axioma) este reprezentata prin term
De exemplu,
[Human Maria] sta pentru propozitia True => human(Maria)

4. Propozitiile sunt date ca o lista [prop1,prop2,...,propm]

-}

propozitii = [
[Human Maria],
[Human Ion, Iubeste Maria Ion, Human Maria],
[Human Fred, Human Ion, Prieten Ion Fred],
[Human Gigi],
[Prieten Ion Fred],
[Iubeste Maria Ion]
]

{-
solve (Human Ion) propozitii
solve (Human Fred) propozitii
solve (Human Gigi) propozitii

-}

17 mai 2010

Protocoale pentru posta electronica

Anatomia mesajelor e-mail

Un mesaj e-mail a fost întotdeauna transmis in format plain-text. Chiar si prin adăugarea attachmenturilor, mesajele de e-mail sunt trimise tot ca mesaje plain-text, prin folosirea unor mecanisme de codificare (uuencode/uudecode, MIME/BASE64). Un mesaj este format dintr-o secţiune de headere, urmata de o secţiune cu conţinutul mesajului. Structura headerelor este descrisa in RFC 822, RFC 1521 si RFC 1806, ele având in general următoarea structura:
- Unul sau mai multe headere Received: , care indica ce cale a fost urmata de mesaj de la sursa pana la destinaţie
- Mime-Version: versiunea mime folosita, 1.0 in general
- Content-Type: text/plain pentru mesaje text, multipart/mixed pentru mesaje cu ataşamente
- Subject: - subject-ul mesajului
- Date: - data si ora când a fost trimis mesajul
- Message ID: - un ID pentru mesaj, folosit pentru identificarea in mod unic a unui mesaj
- From: - numele si adresa de mail a expeditorului
- To: - numele si adresa de mail a destinatarului
- Cc: - carbon copy - alţi destinatari

Mesajele cu ataşamente pot folosi una din următoarele tehnici pentru codificarea acestora:
  • uuencode - la începuturile e-mail-ului, fişierele care se doreau trimise prin email trebuiau convertite in format text si invers prin folosirea utilitarelor numite uuencode/uudecode. Si in zilele de azi, unii clienţi de mail adaugă ataşamentele la sfârşitul mesajelor, codificându-le cu algoritmul folosit de uuencode.
  • MIME / Base64 - aceasta tehnologie este cea recomandata pentru trimiterea de mesaje cu ataşamente.
In terminologia folosita de sistemele de e-mail, exista 3 actori in cadrul sistemului de e-mail. Aceştia pot fi situaţi pe 3 maşini diferite sau pot co-exista pe acelaşi computer:
  • Mail User Agent (MUA), sau client de e-mail - aceasta este aplicaţia folosita de utilizator pentru a citi si trimite mesaje email. El nu primeşte direct mesaje, acesta fiind rolul Mailbox Server-ului.
  • Mailbox Server, sau server de e-mail - acesta este calculatorul/serverul care primeşte si stochează mesajele.
  • Mail Transfer Agent (MTA), sau "router" de e-mail - aceasta este aplicaţia care primeşte si retrimite mesajele spre un alt MTA sau spre un Mailbox Server.
Protocolul SMTP este folosit si de către clienţii de mail când se trimit mesaje e-mail. Astfel, pentru a trimite un mesaj clienţii de mail (MUA) se conectează la serverele SMTP (MTA) si comunica prin protocolul SMTP. In schimb, la transferul mesajelor recepţionate intre Mailbox Server si clientul de mail
se folosesc alte protocoale, cele mai cunoscute fiind POP3 (POP versiunea 3) si IMAP.

Protocolul POP (Post Office Protocol) este destinat folosirii in mod "offline" si este cel mai vechi dintre cele doua protocoale. In paradigma POP, mesajele sunt stocate pe un server, iar un client de mail interoghează periodic serverul, aducând mesajele noi pe calculatorul utilizatorului. După ce un mesaj este descărcat, este şters de pe server. In continuare, toate procesările asupra mesajelor sunt făcute pe calculatorul utilizatorului.

Protocolul IMAP (Internet Message Access Protocol) poate face si procesare offline, dar este in general folosit pentru accesul "online" la mail. In modul online, mesajele sunt stocate tot pe un server, dar clientul nu copiază pur si simplu mesajele pe calculatorul utilizatorului. Se foloseşte un mod de comunicaţie interactiv, in care clientul poate cere doar headere de mesaje, doar anumite mesaje, sau poate căuta mesaje care respecta anumite criterii. Mesajele pot fi marcate ca "deleted" sau "answered" si acest marcaj este făcut pe server. Pe scurt, protocolul IMAP permite manipularea mesajelor de la distanta ca si cum ar fi stocate local.

Urmatorul program implementeaza un client simplu de smtp folosind socketsi tcp. Se apeleaza folosind ca parametru adresa serverului care accepta sa gazduiasca clientul (accepta telnet). In continuare, trimite la adresa de e-mail specificata mesaje de la un "expeditor" oarecare...


#include "sys/socket.h"
#include "netinet/in.h"
#include "arpa/inet.h"
#include "unistd.h"
#include "sys/types.h"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "errno.h"

#define SMTP_PORT 25
#define MAXLEN 500

/**
* Citeste maxim maxlen octeti din socket-ul sockfd. Intoarce
* numarul de octeti cititi.
*/
ssize_t Readline (int sockd, void *vptr, size_t maxlen) {
ssize_t n, rc;
char c, *buffer;

buffer = vptr;

for ( n = 1; n<=maxlen-1; n++ ) {
if ( (rc = read(sockd, &c, 1)) == 1 ) {
*buffer++ = c;
if ( c == '\n' )
break;
}
else if ( rc == 0 ) {
if ( n == 1 )
return 0;
else
break;
}
else {
if ( errno == EINTR )
continue;
return -1;
}
}

*buffer = 0;
return n;
}

/**
* Trimite o comanda SMTP si asteapta raspuns de la server.
* Comanda trebuie sa fie in buffer-ul sendbuf.
* Sirul expected contine inceputul raspunsului pe care
* trebuie sa-l trimita serverul in caz de succes (de ex. codul
* 250). Daca raspunsul semnaleaza o eroare se iese din program.
*/
void send_command(int sockfd, char sendbuf[], char *expected) {
char recvbuf[MAXLEN];
int nbytes;
char CRLF[3];

CRLF[0] = 13; CRLF[1] = 10; CRLF[2] = 0;
strcat(sendbuf, CRLF);
printf("Trimit: %s", sendbuf);
write(sockfd, sendbuf, strlen(sendbuf));
nbytes = Readline(sockfd, recvbuf, MAXLEN - 1);
recvbuf[nbytes] = 0;
printf("Am primit: %s", recvbuf);
if (strstr(recvbuf, expected) != recvbuf) {
printf("Am primit mesaj de eroare de la server!\n");
exit(-1);
}
}

int main(int argc, char **argv) {
int sockfd;
int port = SMTP_PORT;
struct sockaddr_in servaddr;
char server_ip[15];
char sendbuf[MAXLEN];
char recvbuf[MAXLEN];

if (argc != 2) {
printf("Utilizare: ./send_msg adresa_server");
exit(-1);
}
strcpy(server_ip, argv[1]);

if ( (sockfd = socket(AF_INET, SOCK_STREAM, 0))<0>
printf("Eroare la creare socket.\n");
exit(-1);
}

/* formarea adresei serverului */
memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons(port);

if (inet_aton(server_ip, &servaddr.sin_addr)<=0) {
printf("Adresa IP invalida.\n");
exit(-1);
}

/* conectare la server */
if (connect(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr))<0>
printf("Eroare la conectare\n");
exit(-1);
}

Readline(sockfd, recvbuf, MAXLEN -1);
printf("Am primit: %s\n", recvbuf);

sprintf(sendbuf, "HELO `adresa_ip_aici`");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "mail from: Anonymous@yahoo.com");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "rcpt to: yourSecretLover@yahoo.com");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "data");
send_command(sockfd, sendbuf, "354");

sprintf(sendbuf, "secret message from a secret person\n.");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "quit");
send_command(sockfd, sendbuf, "221");

close(sockfd);
}

Protocolul HTTP

HTTP (HyperText Transfer Protocol - protocol pentru transfer de hipertext) este protocolul standard folosit in Web. HTTP este un protocol ASCII simplu. O interactiune HTTP consta dintr-o cerere de tip text, urmata de un raspuns care consta in fisierul transferat (ca mesaj în format standard MIME). Se poate spune ca protocolul HTTP este format din multimea cererilor (uzual GET, POST) de la programele de navigare catre servere si din multimea raspunsurilor trimise de acestea (antetele si corpurile mesajelor sunt asemanatoare cu cele din standardul MIME).
HTTP cunoaste mai multe versiuni succesive si este in continua evolutie; ultimele versiuni de MIME sunt foarte flexibile, avand o deschidere pentru viitoare aplicatii obiectuale.
HTTP este utilizat de catre navigatoare, dar ar putea fi folosit si de catre o persoana aflata la un terminal pentru a "discuta" direct cu un server Web, folosind o conectare TCP (de exemplu, prin programul telnet).

Programul urmator se conecteaza la adresa IP a unui server (de exemplu google) si citeste de la consola un cuvant, pe care il trimite serverului, iar fluxul de informatii care rezulta (din cautare de exemplu) este transferat intr-un fisier numit rezultat.html. Cererea folosita este GET.

#include "sys/socket.h"
#include "netinet/in.h"
#include "arpa/inet.h"
#include "unistd.h"
#include "sys/types.h"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "errno.h"

#define HTTP_PORT 80
#define MAXLEN 500000

ssize_t Readline (int sockd, void *vptr, size_t maxlen) {
ssize_t n, rc;
char c, *buffer;
buffer = vptr;

for ( n = 1; n<=maxlen-1; n++ ) {
if ( (rc = read(sockd, &c, 1)) == 1 ) {
*buffer++ = c;
if ( c == '\n' )
break;
}
else if ( rc == 0 ) {
if ( n == 1 )
return 0;
else
break;
}
else {
if ( errno == EINTR )
continue;
return -1;
}
}
*buffer = 0;
return n;
}


void send_command (FILE *g, int sockfd, char sendbuf[]) {
char recvbuf[MAXLEN];
int nbytes;
char CRLF[3];

CRLF[0] = 13; CRLF[1] = 10; CRLF[2] = 0;
strcat(sendbuf, CRLF);
write(sockfd, sendbuf, strlen(sendbuf));
nbytes = Readline (sockfd, recvbuf, MAXLEN - 1);
recvbuf[nbytes] = 0;
fprintf(g,"%s", recvbuf);
}

int main(int argc, char **argv) {
int sockfd;
int port = HTTP_PORT;
struct sockaddr_in servaddr;
char server_ip[15];
char sendbuf[MAXLEN];
char recvbuf[MAXLEN];

if (argc != 2) {
printf("Utilizare: ./send_msg adresa_server");
exit(-1);
}
strcpy(server_ip, argv[1]);

if ( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0 ) {
printf("Eroare la creare socket.\n");
exit(-1);
}

memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons(port);

if (inet_aton(server_ip, &servaddr.sin_addr) <= 0 ) {
printf("Adresa IP invalida.\n");
exit(-1);
}

if (connect(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr)) < 0 ) {
printf("Eroare la conectare\n");
exit(-1);
}

char word[30];
scanf("%s", word);
FILE * g = fopen("rezultat.html","w");

char *c = (char*)malloc(100*sizeof(char));
c = strcat(c,"GET /search?q=");
c = strcat(c, word);
c = strcat(c, " HTTP/1.0\n");

printf("%s\n",c);
sprintf(sendbuf, "%s", c);
while(1)
send_command(g,sockfd, sendbuf);

close(sockfd);
}

12 mai 2010

Toate drumurile intre doua noduri

Un algoritm simplu pentru determinarea tuturor cailor pe care se poate ajunge de la un nod la altul intr-un graf:

List p; // o lista curenta
PathList x; // un vector cu toate caile posibile
Nod s, d; // sursa, destinatie

PathFind (Nod c) {

p = p U c; //adauga nodul curent la sfarsitul listei
Pentru fiecare nod v adiacent cu c {
Daca (v==d) atunci
Salveaza lista p in x;
Altfel
daca (v nu e in p)
PathFind(v);
}
Sterge ultima poz din p;
}