FACULDADE DE INFORMÁTICA - PUCRS
46180-04 TEORIA DA COMPUTABILIDADE
T 590
PROF.: Carlos A. Prolo
TRABALHO
ENTREGA e APRESENTAÇÃO: 01/07/2008
GRUPOS DE até 2 alunos
(upload no moodle e entrega do material escrito até 8h20)
ARITMÉTICA DE NÚMEROS INTEIROS COM FORMALISMO DE KLEENE
Neste trabalho você vai implementar funções aritméticas básicas sobre números inteiros utilizando o formalismo de Kleene.
As operações a serem implementadas são a soma, a subtração e a multiplicação. As operações deverão ser implementadas na
linguagem do interpretador para o formalismo de Kleene disponível na página moodle da disciplina, usando como base o
arquivo biblioteca divisao.kln.
Como o formalismo é baseado em números naturais, primeiro temos que estabelecer uma convenção de como representar
números inteiros codificados como números naturais. Partindo da noção de que um número inteiro i pode ser visto como um
par (s, m), onde s é o sinal (usaremos a convenção de 0 para positivo e 1 para negativo), e m é a magnitude ou valor absoluto
(com o pequeno inconveniente de que há duas representações para o 0), codificaremos os inteiros assim:
codigo(s, m) = 2 ∗ magnitude + s.
Embora existam formas mais genéricas de codificação de pares de naturais, esta é conveniente aqui por várias razões:
1. É simples;
2. Fica fácil de olhar um código e descobrir se ele representa um número positivo (quando o código é par) ou um número
negativo (quando o código é impar).
3. As funções inversas também são simples. Dado um código cn:
sinal(cn) = mod(cn, 2);
magnitude(cn) = div(cn, 2).
Ou seja, o sinal é o resto da divisão inteira por 2, e a magnitude é o quociente da divisão inteira por 2.
A seguir mostra-se como planejar a implementação da soma, usando os conhecimentos (algoritmos) para aritmética com
representação sinal-magnitude. Este primeiro algoritmo é procedural.
int somaint (cx,cy) {
sinalx = cx % 2;
sinaly = cy % 2;
magx = cx / 2;
magy = cy / 2;
if (sinalx == sinaly) {
sinal = sinalx; // ou sinaly, tabnto faz
mag = magx+magy;
}
else {
if (magx>=magy) {
sinal = sinalx;
mag = magx - magy; // subtração de naturais
}
else {
sinal = sinaly;
mag = magy - magx; // subtração de naturais
}
}
return (codifica(sinal,mag));
}
Agora, um algoritmo funcional:
nat sinal(c) = mod (c,dois)
nat mag(c) = div (c,dois)
nat sinalsoma(cx,cy) =
cond (eq(sinal(cx), sinal(cy)),
sinal(cx),
cond (geq(mag(cx), mag(cy)),
sinal(cx),
sinal(cy)))
nat magsoma(cx,cy) =
cond (eq(sinal(cx), sinal(cy)),
som (mag(cx), mag(cy))
cond (geq(mag(cx), mag(cy)),
sub(mag(cx), mag(cy)),
sub(mag(cy), mag(cx))))
nat somaint (cx, cy) =
codifica (sinalsoma(cx,cy), magsoma(cx,cy))
O diagrama abaixo mostra o grafo de aplicação das funções, organizado de maneira a sugerir uma implementação um pouco
mais eficiente na linguagem de Kleene.
CX
SOMAINT
CY
p12
p12
p22
p22
sinal
mag
sinal
mag
SOMA−AUX
p24
p44
(magx) (magy)
p14
p34
(sinalx) (sinaly)
EQ
GEQ
p14
(sinalx)
p24
p44
p24
p44
p44
p24
(magx) (magy) (magx) (magy) (magy) (magx)
p14
p34
(sinalx) (sinaly)
COND
p14
p34
(sinalx) (sinaly)
p24
p44
(magx) (magy)
EQ
SOM
COND
GEQ
SUB
SUB
COND
COND
CODIFICA
Após implementada a função o usuário deverá poder executar a função somaint passando como argumentos, por exemplo,
11 e 8 (representando, respectivamente os números inteiros −5 e 4,) e o interpretador dará como resultado 3 (que é o código do
−1). Além da soma deverão ser implementadas subtração e multiplicação.
INFORMAÇÕES GERAIS:
O grupo deve entregar até as 8h20 da data de entrega:
• pessoalmente: as listagens (impressas) com o programa .kln com identificação dos componentes do grupo e um
documento (impresso, também devidamente identificado) com a descrição de funcionamento, decisões tomadas, casos
de teste, nomes dos arquivos que contém o programa, etc.
• através de upload no moodle: um arquivo zipado com o material acima. Não usar .rar!!
IMPORTANTE: Em caso de fraude acadêmica (cópia de trabalho) será atribuído grau zero aos envolvidos.