Programming Paradigms

Introduction

• Imperativa:
  • Procedural: ;
  • Orientada a objetos: .
• Declarativa:
  • Funcional: ;
  • Lógica: .

Language Evaluation Criteria

• Readability

  • Simplicity
  • Orthogonality
  • Data types
  • Syntax design

• Writability

  • Support for abstraction
  • Expressivity

• Reliability

  • Type checking
  • Exception handling
  • Restricted aliasing

Procedural Programming

Object Oriented Programming

Logic Programming

Prolog usa as três cláusulas de Horn apresentadas como elementos de linguagem para construção de programas. Utilizando o operador :- (dois pontos traço) para representar a operação de implicação $\leftarrow$, e , (vírgula) para a conjunção $\wedge$, tem-se os seguintes elementos de linguagem:

• regras: cláusulas definitivas no formato H :- G1, ..., Gn., onde Gi lê-se objetivo;
• fatos: cláusulas unitárias no formato H.; e
• consultas: cláusulas objetivo no formato ?- G1, ..., Gn..

Sobre a sintaxe da linguagem cabe reforçar que todos o elementos terminam com . (ponto) e que nas consultas o operador de implicação :- é substituído por ?-.

Uma questão importante relacionada a utilização de cláusulas de Horn é que o processo de dedução ou prova de programas é significativamente simplificado por causa da sua sintaxe simples. Embora essa simplificação reduza o poder de expressão da lógica de predicados, é conhecido que com a utilização cláusulas de Horn é possível construir programas com a mesma representatividade computacional da máquina de Turing. Ou seja, a utilização de cláusulas de Horn permite escrever programas para tudo que é conhecido como computável.

Basics

Considere o seguinte programa composto por três fatos.

love(romeo, juliet).
love(paris, juliet).
love(juliet, juliet).

Esse programa representa um dos possíveis universos de discurso do argumento apresentado no início da Seção Predicate Logic. Temos na premissa que $(\exists y)(\forall x)Lxy$, ou seja, um universo de discurso em que existe pelo menos um indivíduo que é amado por todos. No exemplo acima, esse indivíduo é juliet. Com o programa definido, é possível criar cláusulas de consulta.

?- love(romeo, juliet).
true.

NOTA - É possível experimentar programação em Prolog na plataforma on-line SWISH.

Nesse exemplo, o objetivo da consulta love(romeo, juliet) tem como resultado o valor verdade true. Isso quer dizer que o Prolog encontrou uma forma de demonstrar que o objetivo é verdadeiro com base no programa escrito. Considere agora as seguintes consultas.

?- love(romeo, paris).
false.

?- love(juliet, romeo).
false.

No primeiro caso, love(romeo, paris), o Prolog não encontrou uma forma de provar o objetivo e, por isso, o considerou falso (false). É importante destacar que a linguagem considera que o universo de discurso é fechado e, portanto, tudo aquilo que ela não consegue provar é considerado por ela falso. Veja que isso também é reforçado pela segunda consulta do exemplo. O programa também conclui que love(juliet, romeo) é falso, pois não há como concluir isso com base no programa apresentado.

Uma consulta em Prolog pode ser mais generalista através da utilização de variáveis. Por exemplo, é possível com objetivo love(rome, X) buscar por uma solução para X que torne o objetivo verdadeiro.

?- love(romeo, X).
X = juliet.

Nesse caso, tem-se como resposta uma solução para a variável X. De forma ainda mais geral, é possível criar a consulta love(X, Y), onde o Prolog tentará encontrar termos que possam substituir as variáveis X e Y a fim de tornar a consulta verdadeira.

?- love(X, Y).
X = romeo,
Y = juliet ;
X = paris,
Y = juliet ;
X = Y, Y = juliet.

Onde o símbolo , representa a conjunção $\wedge$ , e o símbolo ; representa a disjunção $\vee$ (ou inclusivo).

Em Prolog, as respostas a uma cláusula consulta podem ser dos seguintes tipo.

1. Uma avaliação da cláusula objetivo: true ou false; ou
2. Uma solução: podendo ser única ou um conjunto de soluções.

Deduction

No exemplo a seguir, inspirado no livro do Harry J. Gensler, tem-se um conjunto de fatos sobre uma festa em que o dinheiro de Herman foi roubado.

1. Alice doesn’t love money.
2. Bob loves money.
3. Carol knew where the money was.
4. David works for Herman.
5. All who stole money love money.
6. All who stole money knew where the money was.
7. All who work for Herman hate Herman.
8. All who hate Herman stole money.

Podemos traduzi-los para lógica de predicados a fim de verificar se é possível identificar culpados e inocentes.

did_not_stole(X, money) :- does_not_love(X, money).
does_not_love(alice, money).
hate(X, herman) :- works(X, herman).
knew_where_was(carol, money).
knew_where_was(X, money) :- stole(X, money).
love(bob, money).
love(X, money) :- stole(X, money).
stole(X, money) :- hate(X, herman).
works(david, herman).

Nessa tradução, um dos fatos originais é que Alice não gosta de dinheiro. Como a falha em provar resulta em false. Deve-se reescrever um novo predicado, no caso does_not_love(alice, money). Como a regra love(X, money) :- stole(X, money) é importante para inocentar Alice, devemos reescreve-la considerando o novo predicado does_not_love(X, Y). Como a tabela verdade de $(P \rightarrow Q)$ é igual a $(\neg Q \rightarrow \neg P)$, é possível reescrever a regra como sendo did_not_stole(X, money) :- does_not_love(X, money). Dessa forma, é possível realizar uma consulta para, com base no fatos, provar a culpabilidade e a inocência.

term@languages$ swipl -q party.pl 
?- stole(X, money).
X = david.

?- did_not_stole(X, money).
X = alice.

Com base nos fatos, não é possível concluir sobre a culpa ou inocência de Bob, Carol ou Herman.

NOTA - O programa utilizado nesse exemplo está disponível no arquivo party.pl no repositório. Uma versão estendida está disponível no arquivo party-plus.pl.

Calculation

O cálculo do fatorial de $n$ é um dos problemas clássicos para introduzir conceitos aritméticos e de recursão em um linguagem de programação. A relação fatorial $F(n,r)$ é verdadeira se $r=n!$. Por definição, $F(0,1)$ é verdadeiro e pode-se tratá-lo como fato. Porém, para o caso de $n>0$, aqui representado por $B(n,0)$, é possível definir recursivamente o fatorial a partir da multiplicação $n \times r_1$, onde $r_1$ é termo da relação $F(n_1,r_1)$, para $n_1=n-1$ . Escrevendo a relação de subtração como $M(n,1)$ e a de multiplicação como $P(n,r_1)$, é possível definir a seguinte cláusula definitiva ou regra $$F(n,r) \leftarrow B(n,0) \wedge I(n_1, M(n,1)) \wedge F(n_1,r_1) \wedge I(r, P(n,r_1)) \text{ ,}$$ onde o predicado $I(a,b)$ é verdadeiro se é possível vincular o termo $b$ ao termo não vinculado $a$.

Nessa cláusula definitiva é primeiro verificado pela avaliação do primeiro literal se $n>0$. Se verdadeiro, o segundo literal vincula à variável $n_1$ o valor $n-1$. A resolução do terceiro literal pelo sistema de dedução irá vincular a variável $r_1$ o valor do $(n-1)!$ a partir de sucessivas resoluções até encontrar como caso base o fato $F(0, 1)$. Com a vinculação de $r_1$, o quarto literal vincula à variável $r$ o resultado de $n \times r_1$, concluindo a inferência de $F(n,r)$.

O programa a seguir implementa essas cláusulas utilizando > para o predicado $B$, is para o predicado $I$, - para o predicado $M$ e * para o predicado $P$.

factorial(0, 1).
factorial(N, R) :- >(N, 0),
                   is(N1, -(N, 1)),
                   factorial(N1, R1),
                   is(R, *(N, R1)).

Com base no programa pode-se verificar o resultado das seguintes consultas.

term@laguages$ swipl -q factorial.pl
?- factorial(0, R).
R = 1 .

?- factorial(5, R).
R = 120 .

NOTA - O programa utilizado nesse exemplo está disponível no arquivo factorial.pl no repositório. Também é possível encontrar exemplos para o teste de primalidade no arquivo prime.pl e cálculo de raiz exata no arquivo root.pl.

Functional Programming

term@laguages$ clisp -q
[1]> (set 'code '(+ 1 2))
(+ 1 2)
[2]> (set 'new_code (cons '- (cdr code)))
(- 1 2)
[3]> (eval code)
3
[4]> (eval new_code)
-1

Modifying code

(set 'code '(+ 1 2))
(set 'new_code (cons '- (cdr code)))
(write (eval code))
(terpri)
(write (eval new_code))

References

[1] Sebesta, Robert W. Concepts of programming languages. Pearson Education, Inc, 2012.