quarta-feira, 10 de junho de 2009




















Sobrecarga
de Operadores







Rafael
de Andrade Castro







Henrique
Augusto Diniz Ribeiro













O que é um
operador?







Um operador é
a parte de um código fonte que modifica um conteúdo de
uma variável, ou declara o seu valor inicial. Ex.
Multiplicação (*), Divisão(/), Adição(+),
Atribuição(=). Os operadores são nativos da
linguagem, ou seja, cada linguagem possui seus operadores definidos.
Os operadores possuem o conceito de serem unário ou binário,
ou seja, podem utilizar dois operandos ou apenas um.





Os operadores em uma
linguagem de programação são apenas símbolos
que por trás existem funções que determinam o
que aquele símbolo faz com o valor, as funções
de operadores são pré-definidas apenas para os tipos
primitivos de variáveis, no qual essas funções
não têm como serem alteradas, pelo fato de que elas já
são nativas da linguagem, isso faz com que mesmo utilizando a
sobrecarga destes operadores não tem como fugir de sua
funcionalidade natural.







A sobrecarga de
operadores é feito a partir de objetos de uma classe, que são
dados abstratos, sendo assim para sobrecarregar operadores é
obrigatório que a linguagem tenha recursos de orientação
a objeto.







Observações:













  • Não se pode criar novos
    operadores, apenas sobrecarregar operadores já existentes.









  • Não se pode alterar a
    propriedade do operador, ou seja, se ele é binário sua
    sobrecarga deverá permanecer binária, se ele for
    unário sua sobrecarga deverá permanecer unária.






Operadores que podem ser sobrecarregados:



Operadores que não
podem ser sobrecarregados:



Exemplo
de sobrecarga de operadores unários:







class
ponto







{







private:







intx,y;







public:







ponto(int
x1=0, int y1=0)







{







x=x1;







y=y1;








}//constructor







Ponto
operator++() //função operadores pré fixada







{







x++;







y++;







return
ponto(x,y)







}







void
printpt()const //imprime ponto







{







cout<<”(”<<x<<”,”<<y<<”)”;







}







};















void
main()







{







ponto
p1,p2(2,3),p3; //declara e inicializa







cout<<”\n
p1= ”;







p1.printpt();
//imprime







}







Observe.:
p1++; é equivalente a p1.operator++();















Exemplo
de sobrecarga de operadores binários:







class
venda







{







venda
operador+(venda v) const; //função operadora







}







venda
venda :: operator + (venda v) const //soma dois objetos







{







int
pec = npecas + v.pecas;







float
pre = preco + v.pecas;







return
venda(pec,pre);







}















void
main()







{







Venda
A(58,12734.53), B(30,6000.30),T;







T=A+B;







}















Somando
objetos da classe ponto: funções operadoras







Class
ponto







{







ponto
operador + (ponto p) const //soma dois objetos







{







return
ponto(x+p.x,y+p.y);







}







ponto
operador + (int n) const //soma um número a um objeto







{







return
ponto(x+n,y+n);













}















void
main()







{







p3=p1+p2;







p4=p1+5;







}















Observe.:
p4=p1+5;







É
equivalente a p4=p1.operator+(5); por isso não podemos
escrever instruções p4=5+p1; que seriam interpretadas
como: p4=5.operator+(p1)//errado















Expressões
Lógicas


















Quando
uma expressão lógica é calculada dentro do
programa, é feita a seguinte associação numérica
com o valor da expressão:







verdadeiro
– 1







falso
– 0







Mais
genericamente o valor zero está associado ao valor lógico
falso, enquanto que qualquer valor diferente de zero está
associado ao valor lógico verdadeiro.







Assim,
uma comparação como por exemplo a > b, quando
calculada, tem associado a si o valor 1 se a > b (verdadeira) e 0
se a <= b (falsa).







Da
mesma forma uma expressão aritmética como por exemplo a
+ b, pode ser considerada falsa ou verdadeira, conforme seu valor
seja zero ou diferente de zero.







O
programa abaixo mostra algumas variações e exemplos da
utilização de expressões aritméticas como
lógicas e vice-versa. Verifique o que será impresso
abaixo:







#include
<stdio.h>







int
main()







{char
a;







int
b;







int
x = 0, y = 1;







//
os valores atribuidos a “a” e “b” são
zero e um, dependendo se a







//
expressão é verdadeira ou falsa







a
= x < y;







cout<<"\n
(1) valor de a = "<<a;







a
= x < y && y > 0;







cout<<"\n
(2) valor de a = "<<a;







a
= x > y;







cout<<"\n
(3) valor de a = “<<a;







b
= x+y < x*y x == y;







cout<<"\n
(4) valor de a = "<<b;
















//
comparações







if
(1) cout<<\n (5) sempre verdadeiro";







if
(-5) cout<<\n (6) sempre verdadeiro";







if
(0) ;







else
cout<<"\n (7) sempre falso";







if
(1 == 1) cout<<"\n (8) sempre verdadeiro";







if
(0 == 0) cout<<"\n (9) sempre verdadeiro";
















//
a também pode receber valores aritméticos entre 0 e 255







a
= x * y;







if
(a) cout<<”\n (10) verdadeiro quando a diferente de zero
- a = ”<<a;







else
cout<<"\n (10) falso quando a igual a zero - a = ”<<a;
















//
a e b como valores lógicos







a
= x * y;







b
= x + y;







if
(a && b)







cout<<"\n
(11) verdadeiro se a e b não zero: a = “<<a<<”b
= "<<b;







else
cout<<"\n (11) falso se a ou b são zero: a =
“<<a<<”b = “<<b;
















b
= 0;







while
(1) // a repetição será infinita







{if
(b++ > 4) break; // força a saída







cout<<"\n
(“<<11+b<<”) valor de b = “<<b;







}







//
outro exemplo de while







a
= 1;







b
= 0;







while
(a)







{cout<<"\n
(“<<18+b<<”) valor de a = “<<a<<”
valor de b = ”<<b;







a
= (b++) < 3;







}







cout<<"\n
(“<<18+b<<”) valor final de a = “<<a<<”
e de b = “<<b;







}







(1)
valor de a = 1







(2)
valor de a = 1







(3)
valor de a = 0







(4)
valor de a = 0







(5)
sempre verdadeiro







(6)
sempre verdadeiro







(7)
sempre falso







(8)
sempre verdadeiro







(9)
sempre verdadeiro







(10)
falso quando a igual a zero - a = 0







(11)
falso se a ou b são zero: a = 0 b = 1







(12)
valor de b = 1







(13)
valor de b = 2







(14)
valor de b = 3







(15)
valor de b = 4







(16)
valor de b = 5







(18)
valor de a = 1 valor de b = 0







(19)
valor de a = 1 valor de b = 1







(20)
valor de a = 1 valor de b = 2







(21)
valor de a = 1 valor de b = 3







(22)
valor final de a = 0 e de b = 4
















Assim
supondo int x,y; as seguinte expressões lógicas são
equivalentes:







(x
&& y) (x != 0 && y != 0) !(x == 0 y == 0)







(x
y) (x != 0 y!= 0) !(x == 0 && y == 0)







Lembram-se
daquele problema que dada uma sequência terminada por zero,
calcular a soma dos elementos da sequência?







int
soma, x;







:







:







x
= 1; soma = 0;







while
(x)







{







cin>>x;







soma
= soma + x;







}







cout<<“o
valor da soma = “<<soma;







Otimização
do Cálculo de Expressões Lógicas

















Quando
se usa uma expressão composta, com os operadores && e
(and e or), o compilador otimiza o cálculo das mesmas,
muitas vezes não as calculando até o fim, quando o seu
valor já está determinado no meio do cálculo.







Por
exemplo, considere a expressão (a > b && c > d).
Se a > b já é falso, não é necessário
verificar se c > d, pois o resultado da expressão já
será falso. O mesmo ocorre com (a > b c > d). Se a >
b é verdadeiro, a expressão é verdadeira
independente se c > d ou não.







Normalmente
os compiladores da linguagem c usam esta regra como padrão,
sendo possível alterá-la através de uma opção
de compilação para que o cálculo seja completo.







Em
alguns casos, o resultado pode ser diferente, pois o cálculo
da expressão completa tem efeitos colaterais. De uma maneira
geral o uso de expressões que pressupõe a otimização
deve ser feito com muito cuidado, para evitar tais efeitos
colaterais.







Considere
por exemplo a seguinte solução para verificar se x é
igual a algum elemento de um vetor a de n elementos.







i
= 0;







while
(i < n && a[i] != x) i++;







Considerando
o caso em que x não é igual a nenhum dos elementos, se
o cálculo da expressão for otimizada, o programa sai do
while quando i = n e não realiza a comparação
a[i] != x, pois se realizasse estaria errado, pois o elemento a[n]
está fora dos n elementos considerados.







Invertendo
agora a expressão acima:







i
= 0;







while
(a[i] != x && i < n) i++;







Embora
a operação && seja comutativa, a solução
está errada, pois quando i = n a comparação a[n]
!= x será efetuada, pois vem antes que a comparação
i < n.
















Referencias















http://pt.wikibooks.org/wiki/Programar_em_C%2B%2B/Sobrecarga_de_operadores















Deitel,Harvey
M. C++ Como Programar. Tradução Carlos Arthur
Lang Lisbôa e Maria Lúcia Blank Lisboa. Porto Alegre.
Reimpressão Bookman,2001

































segunda-feira, 8 de junho de 2009

SUBPROGRAMAS


Subprogramas são blocos de construção fundamentais de programas e, portanto, estão entre os conceitos mais importantes no projeto de linguagens de programação.


Introdução:
Duas facilidades de abstração fundamentais podem ser incluídas em uma linguagem de programação: abstração de processos e abstração de dados.
O primeiro computador programável, a Máquina Analítica de Babbage, construída na década de 1980, tinha capacidade de reutilizar coleções de cartões de instruções em diversos lugares diferentes em um programa quando isso era conveniente. Em uma linguagem de programação moderna, essa coleção de instruções era escrita como um subprograma. Tal reutilização resulta em diversos tipos diferentes de economia, de espaço de memória a tempo de codificação.




Características gerais do subprograma:
Cada subprograma tem um único ponto de entrada.
Toda unidade de programa chamadora é suspensa durante a execução do programa chamado, o que implica na existência de somente um subprograma em execução em qualquer momento dado.
O controle sempre torna ao chamador quando a execução do subprograma encerra-se
Definições básicas:
Uma definição de subprograma descreve a interface e as ações da abstração de subprograma. Uma chamada a subprograma é a solicitação explícita para executar o programa. Diz-se que um subprograma é ativo se, depois de ter sido chamado, ele iniciou a execução, mas ainda não a concluiu.
Um cabeçalho de subprograma, a primeira linha da definição, serve a diversos propósitos, como especificando que a unidade sintática seguinte é uma definição de subprograma de algum tipo particular.
void adder (parâmetros)
serviria como o cabeçalho de uma função chamada adder, em que void indica que ela não retorna um valor.
O perfil parâmetro de um subprograma é o número, a ordem e o tipo de seus parâmetros formais. O protocolo de um subprograma é seu perfil de parâmetros mais, se for uma função, seu tipo de retorno. Em linguagens em que os subprogramas tem tipos, estes são definidos pelo protocolo do subprograma.
As declarações do subprograma são comuns em programas C, onde são chamadas de protótipos. Elas também são usadas na Ada e no Pascal, nas quais, às vezes, são chamadas de declarações forward ou externas.

Parâmetros
Os subprogramas tipicamente descrevem computações. Há duas maneiras pelas quais um subprograma pode ganhar acesso aos dados que devem processar: pelo o acesso direta a variáveis não-locais ou pela passagem de parâmetros.
Em algumas situações, é conveniente ser capaz de transmitir computações, em dedados, como parâmetros a subprogramas.
Os parâmetros no cabeçalho de subprograma são chamados de parâmetros formais. Por vezes, recebe o nome de variáveis burras, porque não as são no sentido usual: em alguns casos, vinculam-se no armazenamento somente quando o subprograma é chamado o que frequentemente se dá em algumas variáveis de programa.
As instruções de chamada a subprogramas incluem o nome dele uma lista de parâmetros a serem vinculados a seus formais. Esses parâmetros são chamados de reais.
Em quase todas as linguagens de programação, a correspondência entre parâmetros reais e formais – ou a vinculação de ambos – é feita simplesmente pela posição: o primeiro parâmetro real é vinculado ao primeiro formal e assim por diante. Eles são chamados de parâmetros posicionais.
Quando as listas são longas, o escritor do programa pode cometer mais erros quanto à ordem de parâmetros da lista. Uma solução para o problema é fornecer parâmetros nomeados, nos quais o nome do parâmetro formal a que um parâmetro real deve estar vinculado é especificado com este último.

Procedimentos e funções
Há duas categorias distintas de subprogramas: Procedimentos (procedures) e funções: ambos podem ser vistos como abordagens para estender a linguagem. Procedimentos são coleções de instruções que definem computações parametrizadas. Estas, por sua vez, são ativadas por instruções de chamadas simples.
As funções lembram estruturalmente os procedimentos, mas são semanticamente modeladas em funções matemáticas. Se uma delas for um modelo confiável, não produzirá nenhum efeito colateral; ou seja, a função não modificará seus parâmetros, nem quaisquer variáveis definidas fora dela.
As funções definem novos operadores determinados pelo usuário. Por exemplo, se uma linguagem não tiver um operador de exponenciação, pode-se escrever uma função que retorna o valor de um de seus parâmetros elevado à potência de outro.
Por exemplo, considere o seguinte cabeçalho de função e de chamada:
void sort (int list[], int listlen);
...
sort (scores, 100);
Os métodos do Java e do C++ são similares ao do C.

Questões de projeto referentes aos subprogramas
Subprogramas são estruturas complexas nas linguagens de programação. Isto quer dizer que uma extensa lista de questões está envolvida em seu projeto. Uma questão evidente é a escolha do método ou dos métodos de passagem de parâmetros a serem usados.
Ambientes de referências locais
Os subprogramas geralmente tem permissão para definir suas próprias variáveis, definindo assim, os ambientes de referência locais. Variáveis que são definidas dentro do subprograma são chamadas variáveis locais, porque o acesso a elas normalmente é restrito ao subprograma no qual são definidas.
No ALGOL 60 e em suas linguagens descendentes, as variáveis locais em um subprograma são, como padrão, stack-dinâmicas. Em funções C e C++, as variáveis locais são stack-dinâmicas, a menos que seja especificamente declaradas como static. Por exemplo, na seguinte função C (ou C++), a variável soma é estática e cont é stack-dinâmica.
Int somador (int list[], int listlen)
{
Static int soma = 0
Int cont;
For (cont= 0; <>
Métodos de passagem de parâmetros
Os métodos de passagem de parâmetros são as maneiras pelas quais se transmitem parâmetros para subprogramas chamados e/ou de subprograma chamados
Modelos semânticos de passagem de parâmetros
Os parâmetros formais são caracterizados por três modelos semânticos distintos:
1-eles podem receber dados do parâmetro real correspondente;
2-podem transmitir dados ao parâmetro real;
3-podem fazer ambos
Os três modelos semânticos são chamados modo entrada (in mode), modo saída (out mode) e modo entrada/saída (inout mode), respectivamente.
Passagem de parâmetros por valor
Quando um parâmetro é passado por valor, o valor do parâmetro real é usado para inicializar o parâmetro formal correspondente que, então age como uma variável local no subprograma, implementando assim, a semântica de modo de entrada.
Passagem de parâmetros por resultado
A passagem por resultado é um modelo de implementação para parâmetros em modo saída. Quando um parâmetro é passado por resultado, nenhum valor é transmitido para o subprograma.
Passagem de parâmetros por valor-resultado
A passagem por valor-resultado é um modelo de implementação de parâmetros em modo entrada/saída no qual valores reais são transferidos. Ela é, com efeito, uma combinação de passagem por valor e por resultado.
Passagem de parâmetros por referência
A passagem por referência é o segundo modelo de implementação de parâmetros em modo entrada/saída. Entretanto, em vez de transmitir valores de dados para lá e para cá, como na passagem de valor-resultado, o método de passagem por referência transmite um caminho de acesso, usualmente apenas um endereço, para o subprograma chamado. Isso proporciona o caminho de acesso à célula que armazena o parâmetro real.
A vantagem da passagem por referência é que o próprio processo de passagem é eficiente, tanto em termos de tempo como de espaço. Não é necessário espaço duplicado, nem qualquer atividade de cópia.
Passagem de parâmetros por nome
A passagem por nome é um método de transmissão de parâmetros em modo entrada/saída que não corresponde a um único modelo de implementação. Quando parâmetros são passados por nome, o parâmetro real é, com efeito, textualmente substituído para o parâmetro formal que corresponde em todas as suas ocorrências no subprograma.
Métodos de passagem de parâmetros das principais linguagens
O FORTRAN sempre usou o modelo semântico de modo entrada/saída para a passagem de parâmetros.
O ALGOL introduziu o método de passagem por nome.
O C usa passagem por valor. Obtêm-se a semântica da passagem por referência usando ponteiros como parâmetros.
O C++ inclui um tipo de ponteiro especial, chamado tipo de referência, entre outras linguagens.
Parâmetros de verificação de tipos
Agora é amplamente aceito que a confiabilidade de software exige que os tipos de parâmetros reais sejam verificados quanto à coerência com os tipos dos parâmetros formais correspondentes.
Arrays multidimensionais como parâmetros
as funções de associação de armazenamento são usadas para associar os valores de índice das referências a elementos de arrays multidimensionais a endereços na memória. Podemos ilustrar:
void fun (int matriz[] [])
{
...
}
Void main ()
{
Int mat [] [];
...
Fun (mat);

}

Considerações de projeto
Das importantes considerações estão envolvidas na escolha de métodos de passagem de parâmetros: eficiência, e se é necessária uma transferência unidirecional ou bidirecional de dados.
Parâmetros que são nomes de subprogramas
Ocorre um grande número de situações em programação mais convenientementes manipuladas se nomes de subprograma puderem ser enviados como parâmetros a outros subprogramas. Uma das mais comuns ocorre quando um subprograma precisa provar alguma função matemática. Por exemplo, um subprograma queue faz integração numérica estima a area sob o gráfico de uma função provando-a em uma série de diferentes pontos.
Subprogramas sobrecarregados
Um operador sobrecarregado é o que tem múltiplos significados. O significado de uma instância particular de um operador sobrecarregado é determinado pelos typos de sues operands. Por exemplo, se o operador * tiver dois operados de ponto flutuante em um programa C, isso especificará uma multiplicação de ponto-flutuante. Mas, se o mesmo operador tiver dois operados inteiros, isso especificará uma multiplicação de números inteiros.
Um subprograma sobrecarregado tem o mesmo nome que outro no mesmo ambiente de referênciamento.
Subprogramas genéricos
Um subprograma genérico ou polimórfico leva parâmetros de diferentes tipos em várias ativações. Os subprogramas sobrecarregados apresentam uma espécie particular de polimorfismo chamado polimorfismo ad hoc. Um tipo mais geral deste último é apresentado pelas funções da APL. Por causa da vinculação dinâmica de tipos da APL, os tipos de parâmetros podem permanecer sem ser especificados; eles simplesmente são vinculados ao tipo de parâmetros reais correspondentes.
Subprogramas genéricos em Ada
A Ada apresenta um poliformismo paramétrico por meio de uma construção que suporta a criação de múltiplas versões de unidades de programa para aceitar parâmetros de diferentes tipos de dados.
Uma vez que as unidades de programas desse tipo são genéricas por natureza, às vezes elas são chamadas unidades genéricas.
A classificação genérica nada mais é do que um modelo para um procedimento.
Lembre-se de que a Ada não permite que subprogramas sejam passados a outros subprogramas.
Funções genéricas em C++
As funções genéricas em C++ tem o nome descritivo de funções modelo. A definição de uma função modelo tem a forma geral:
Template <>
- Uma definição de função que pode incluir os parametros da classe
Cada parametro da classe tem a forma
Class identificador
Compilação separada e independente
A capacidade de compilar parte de um programa sem a necessidade de compilá-lo por inteiro é fundamental para a construção de sistemas de software grandes. Com essa capacidade, somente os módulos de um sistema em modificação pão pecisam ser recompilados durante o desenvolvimento e manipulação.
Existem duas abordagens distintas para compilar partes de um programa. O termo compilação separada significa que as unidades de compilação podem ser compiladas em tempos diferentes, mas elas não são independentes uma da outra. Em algumas linguagens, mais notavelmente no C e no FORTRAN 77, a compilação independente é permitida; com ela as unidades de programa podem ser compiladas sem informações sobre quaisquer outras unidades de programas.
A característica mais importante da compilação independente é que as interfaces entre as unidades compiladas separadamente não são verificadas quanto à coerência de tipos.
Efeitos colaterais funcionais
Devido aos problemas dos efeitos colaterais de funções que são chamadas em expressões, os parâmetros para funções sempre devem estar em modo de entrada (in mode).
Tipos de valores retornados
A maioria das linguagens de programação imperativas restringem os tipos que podem ser retornados por suas funções.
A Ada está sozinha entre as linguagens imperativa em termos que suas funções podem retornar
valores de qualquer tipo.
Acessando ambientes não-locais
As variáveis não-locais (escopo ecstatic e o scoop dynamic) de um subprograma são visíveis dentro dele, ma’s não declaradas localmente. As variáveis globais são visíveis em todas as unidades de programa.
O principal problema de usar o escopo estático como o meio de compartilhar variáveis não-locais é o seguinte: uma boa quantidade da estrutura do programa pode ser ditada pela acessibilidade de subprogramas e de variáveis não-locais a outros subprogramas, em vez de soluções de problema bem trabalhadas.
Dois tipos de problemas decorrem do escopo dinâmico. Primeiro, durante o intervalo de tempo que se inicia quando a execução de subprograma é iniciada e que se encerra quando é finalizada, as variáveis locais do subprograma são visíveis a quaisquer outros subprogramas em execução, independente da proximidade textual deles. O segundo é a incapacidade de fazer estaticamente a verificação de tipos de referências a não-locais.
Blocos COMMON do FORTRAN
O FORTRAN oferece acessos a blocos de armazenamento global por meio de sua instrução COMMON. Pode haver qualquer número desses blocos, sendo que todos, menos um, devem ser nomeados. Um bloco comum é criado quando a primeira instrução COMMON que menciona o nome dele é encontrado pelo compilador.
Na maioria dos casos, os dados em bloco COMMON devem ser compartilhados usando os mesmos nomes e tipos de variável.
A definição do FORTRAN 90 declara que COMMON é um dos “recursos desaprovados”, o que significa que ela pode ser incluída em somente mais uma versão do FORTRAN.
Declarações e módulos externos
As linguagens Módula-2 e Ada usam o escopo estático como um meio de compartilhar dados entre unidades de programa. Usando o método alternativo de compartilhamento dados, cada módulo pode especificar exatamente os outros módulos para os quais é necessário acesso, nem mais, nem menos.
Em linguagens orientadas a objeto como o C++ e o Java, uma classe pode ser usada para encapsular coleções de dados para ser compartilhadas entre outras classes.
Variáveis globais definidas em outros arquivos de código C incluídos em um programa também podem ser acessadas por funções que as declaram como externas.
Operadores sobrecarregados definidos pelo usuário
Os operadores podem ser sobrecarregados pelo usuário em programas Ada e C++. Como um exemplo disso, considere a seguinte função Ada que sobrecarrega o operador de multiplicação (*) para computar o produto pontual de dois arrays. O produto pontual de dois arrays é a soma dos produtos de cada um dos pares de elementos correspondentes de dois arrays.
Temos que saber quando a sobrecarga de um operador pode ser boa, ou, pode-se ter muita sobrecarga, mas, isso é uma questão de gosto. O argumento contra a demasiada sobrecarga de operador é principalmente uma questão de legibilidade.
Co-rotinas
Uma co-rotina é um tipo especial de subprograma. Em vez da relação mestre-escravo entre o subprograma chamador e o chamado que existe nos subprogramas convencionais, as co-rotinas chamadoras e chamadas estão em uma base mais igual. De fato, o mecanismo de controle de co-rotinas frequentemente é chamado modelo de controle unitário simétrico.
As co-rotinas tem múltiplos pontos de entrada, controladas pelas próprias co-rotinas. Elas também tem os meios para manter seus status entre as ativações.
Tipicamente, as co-rotinas são criadas em uma aplicação por uma unidade de programa chamada unidade-mestra, a qual não é uma co-rotina. Quando criadas, elas executam seu código de inicialização e, depois, retornam o controle a essa unidade-mestra. Se uma execução de co-rotina atingir o final de sua seção de código, o controle será transferido para a unidade-mestra que as criou.
Um exemplo de problema que pode ser resolvido com coleção de co-rotinas é a simulação de um jogo de cart.
Post por: Hamilton & Ingrid
Sistemas de Informação IV

sábado, 6 de junho de 2009


Programação Lógica

Rômulo Gama, Diego Augusto, Eduardo Assis

Programação lógica é um paradigma de programação que faz uso da lógica matemática. John McCarthy [1958] foi o primeiro a publicar uma proposta de uso da lógica matemática para programação.

A primeira linguagem de programação lógica foi a Planner, a qual permitia a invocação orientada a padrões de planos procedimentais de asserções e de objetivos. Com a necessidade de adaptação aos sistemas de memória muito limitada, que eram disponíveis quando ela foi desenvolvida. A linguagem Planner usava estruturas de controle de backtracking, de tal forma que apenas um único caminho computacional tinha que ser armazenado por vez. Em seguida, o Prolog foi desenvolvido como uma simplificação do Planner que permitia a invocação orientada a padrões apenas a partir de objetivos (também baseado em backtracking).

A partir do Planner, foram desenvolvidas as linguagens de programação QA-4, Popler, Conniver, e QLISP. As linguagens de programação Mercury, Visual Prolog, Oz e Frill, foram desenvolvidas a partir do Prolog. Atualmente existem linguagens de programação lógica concorrentes (não baseadas em backtracking) derivadas do Planner (por exemplo, a Ether) e derivadas do Prolog (Shapiro).

História

A programação lógica é uma idéia que tem sido investigada no contexto da inteligência artificial pelo menos desde o momento em que John McCarthy propôs: "programas para manipular com sentenças instrumentais comuns apropriadas à linguagem formal (muito provavelmente uma parte do cálculo de predicado)". O programa básico formará conclusões imediatas a partir de uma lista de premissas. Essas conclusões serão tanto sentenças declarativas quanto imperativas. Quando uma sentença imperativa é deduzida, o programa toma uma ação correspondente.

Base na Lógica Matemática

O sentido da programação lógica é trazer o estilo da lógica matemática à programação de computadores. Matemáticos e filósofos encontram na lógica uma ferramenta eficaz para desenvolvimento de teorias. Vários problemas são naturalmente expressos como teorias. Dizer que um problema precisa de solução frequentemente equivale a perguntar se uma nova hipótese é consistente com uma teoria existente ou se é conseqüência dela. A lógica proporciona uma maneira de demonstrar se uma questão é verdadeira ou falsa.

O processo de construir uma demonstração é bem conhecido, portanto a lógica é um meio confiável de responder perguntas. Sistemas de programação lógica automatizam

este processo. A inteligência artificial teve uma influência importante no desenvolvimento da programação lógica.


As proposições são indicadas pelas letras latinas minúsculas: p, q, r, s, t.

Exemplo:



Prolog

Escolhemos a linguagem de programação Prolog, para exemplificar. A linguagem de programação Prolog foi explicitamente apresentada como baseada na lógica matemática. A base dessa alegação era que um programa Prolog podia literalmente ser lido como um conjunto de fórmulas em um fragmento da lógica de primeira ordem, herdando o modelo de teoria e demonstração da lógica de primeira ordem.

Prolog foi desenvolvida em 1972 por Alain Colmerauer. Ela veio de uma colaboração entre Colmerauer em Marselha e Robert Kowalski em Edinburgo. Colmerauer estava trabalhando na compreensão da linguagem natural, usando lógica para representar semânticas e usando resolução para questionamento-resposta. Durante o verão de 1971, Colmerauer e Kowalski descobriram que a forma clausal da lógica poderia ser usada para representar gramáticas formais e que demonstrações do teorema da resolução poderia ser usado para análise gramatical. Eles observaram que algumas demonstrações de teoremas, como o da hiper-resolução, comportavam-se como analisadores ascendentes e outros, como resolução-SL (1971), comportavam-se como analisadores descendentes.

Durante o seguinte verão de 1972, Kowalski, novamente trabalhando com Colmerauer, observou que resolução-SL trata cláusulas universalmente quantificadas na forma declarativa de implicações.

 
B1 e … e Bn implica H.
 
 

como procedimentos de objetivo-redução

para mostrar/resolver H, mostrar/resolver B1 e … e Bn.

Essa interpretação dupla declarativa/procedimental depois foi formalizada na notação do Prolog

H :- B1, …, Bn.

que pode ser lida (e usada) tanto declarativamente como procedimentalmente. Tornou-se também claro que tais cláusulas poderiam ser restringidas para definir cláusulas ou cláusulas de Horn, em que H, B1, …, Bn são todos os predicados atômicos, e que resolução-SL poderia ser restrita (e gerada) para LUSH ou resolução-SLD.

Colmerauer, com Philippe Roussel, usou essa interpretação dupla de cláusulas assim como a base do Prolog, a qual foi implementada no verão e outono de 1972. O primeiro programa na linguagem, também escrito em 1972 e implementado em Marseille, foi um sistema francês de pergunta-resposta. A interpretação procedimental de Kowalski e LUSH foi depois descrita em um memorando em 1973, publicado em 1974.

A relação próxima entre interpretação declarativa e processual resulta numa característica típica das linguagens de programação lógica, embora a relação se torne mais complexa quando há negação, disjunção e outros quantificadores são permitidos em programas.



Exemplo: Queens Prolog é um exercício muito simples, mostrando o básico do jogo estratégico programação. O código fonte está disponível apenas para Turbo Prolog.

Limitações para o uso da Lógica Matemática para a Programação

John MacCarthy propôs que a lógica matemática fosse usada como o fundamento para a epistemologia de sistemas de computadores. Sob a liderança de Marvin Minsky e Seymour Papert, uma abordagem diferente baseada em procedimentos processuais foi desenvolvida no MIT. Quando o Planner foi desenvolvido, levantou-se o a questão sobre o relacionamento entre as duas abordagens.

Robert Kowalski desenvolveu a tese que "computação pode concebida dedução" teve boa aceitação ao citar o slogan "a computação é uma dedução controlada," que ele atribuiu a Pat Hayes em seu artigo de 1988 no início da história do Prolog. Ao contrário de Kowalski e Hayes, Carl Hewitt desenvolveu a tese de que a dedução lógica era incapaz de executar computação concorrente em sistemas abertos. A resposta à questão sobre a relação entre as abordagens lógica e procedimental é que a abordagem procedimental tem uma semântica matemática diferente (ver semântica denotacional) da semântica da lógica matemática (ver teoria dos modelos).

Programação Lógica Concorrente

Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. desenvolveram uma família de sistemas concorrentes de passagem de mensagens do tipo Prolog, usando unificação de variáveis compartilhadas e fluxo de estrutura de dados para mensagens. Esforços foram feitos para basear esses sistemas em lógica matemática, e elas foram usadas como a base para o Projeto Japonês da Quinta Geração de Computadores.

Como o modelo de atores, os sistemas com o Prolog concorrente são baseados em passagem de mensagens e conseqüentemente estavam sujeitos à mesma indeterminação. Esta foi a base de um argumento de Carl Hewitt e Gul Agha sugerindo que os sistemas com Prolog concorrente nem eram dedutivos nem lógicos.

Programação Lógica de Ordem Superior

Diversos pesquisadores estenderam a programação lógica com as características da programação de ordem superior derivadas da lógica de ordem superior, tais como variáveis de predicado. Tais linguagens incluem as extensões do Prolog HiLog e λProlog.

Programação Lógica Linear

Basear a programação lógica na lógica linear resultou no projeto de linguagens de programação lógica que são consideravelmente mais custosas do que aquelas baseadas na lógica clássica. Programas com cláusulas de Horn (Prolog) podem apenas representar uma mudança de estado pela mudança em argumentos para predicados. Na programação lógica linear, pode-se usar a lógica linear como ambiente para dar suporte à mudança de estado. Alguns projetos iniciais das linguagens de programação lógica baseadas na lógica linear, incluem LO [Andreoli & Pareschi, 1991], Lolli [Hodas & Miller, 1994], ACL [Kobayashi & Yonezawa, 1994], e Forum [Miller, 1996].O Fórum proporciona a interpretação direcionada a objetivos de toda a lógica linear.