Lesson19

Nesta aula veremos a metodologia para criar novos tipos abstractos de dados e o que se entende por barreiras de abstracção.

Metodologia dos tipos abstractos de dados

Um tipo de dados caracteriza-se por uma colecção de operações que podem ser efectuadas sobre os elementos desse tipo, e pelo conjunto de elementos do tipo, i.e., pelo seu domínio.

A ideia fundamental da metodologia dos tipos abstractos de dados é separar o modo como os elementos de um tipo são utilizados do modo como esses elementos são representados e como as operações sobre os mesmos são implementadas.

Passos a seguir:

1. identificação das operações básicas;
2. axiomatização das operações básicas;
3. escolha de uma representação (interna) para os elementos do tipo;
4. concretização das operações básicas.

Operações básicas

As operações básicas sobre os elementos de um tipo devem compreender um conjunto mínimo de operações que caracterizam o tipo e dividem-se em seis grupos:

• construtores, que permitem construir novos elementos do tipo;
• selectores, que permitem aceder às propriedades e partes dos elementos do tipo;
• modificadores, que permitem modificar e alterar os elementos do tipo;
• transformadores, que permitem transformar elementos do tipo em elementos de outro tipo;
• reconhecedores, que permitem reconhecer elementos como sendo do tipo, podendo também permitir distinguir elementos do tipo com características particulares;
• testes, que permitem efectuar interrogações sobre elementos do tipo ou comparações entre elementos do tipo.

Nota-se que na definição de um tipo podem não ser contempladas operações de todos estes grupos. Por exemplo, se o tipo for imutável, não faz sentido existirem modificadores.

O conjunto de operações básicas para um dado tipo denomina-se por assinatura do tipo.

Uma vez que a definição de um tipo e do conjunto de operações básicas associadas é independente da linguagem de programação, sendo um definição abstracta, é em geral utilizada a notação matemática na caracterização do tipo. Em particular já vimos exemplos do uso de tal notação na aula anterior.

Vejamos como exemplo o tipo (imutável) complexo. Construtores:

cria_complexo : real x real --> complexo
cria_complexo(x, y) tem como valor o número complexo (x + y i).

cria_complexo_zero : {} --> complexo
cria_complexo_zero() tem como valor o número complexo (0 + 0 i).

Selectores:

complexo_parte_real : complexo --> real
complexo_parte_real(z) tem como valor a parte real de z.

complexo_parte_imaginaria : complexo --> real
complexo_parte_imaginaria(z) tem como valor a parte imaginária de z.

Reconhecedores:

e_complexo : universal --> lógico
e_complexo(u) tem valor verdadeiro se e só se u é um número complexo.

e_complexo_zero : complexo --> lógico
e_complexo_zero(z) tem como valor verdadeiro se e só se a parte real e a parte imaginária são ambas 0.

e_imaginario_puro : complexo --> lógico
e_imaginario_puro(z) tem como valor verdadeiro se e só se z tem parte real 0 e parte imaginária diferente de 0.

Testes:

complexo_igual : complexo x complexo --> lógico
complexo_igual(z, w) tem valor verdaeiro se e só se z e w corresponderem ao mesmo número complexo.

Transformadores:

complexo_para_string: complexo --> string
complexo_para_string(z) tem como valor a string com a representação externa de z, neste caso na forma 'x + y i'.

Aqui estamos apenas a considerar transformadores de saída. Podemos também definir transformadores de entrada que, dada a representação externa, têm como valor um elemento do tipo transformando a representação externa na representação interna considerada.

A assinatura neste caso é:

cria_complexo : real x real --> complexo
cria_complexo_zero : {} --> complexo
complexo_parte_real : complexo --> real
complexo_parte_imaginaria : complexo --> real
e_complexo : universal --> lógico
e_complexo_zero : complexo --> lógico
e_imaginario_puro : complexo --> lógico
complexo_igual : complexo x complexo --> lógico
complexo_para_string: complexo --> string

Notar que, ao especificarmos as operações desta forma, obtemos uma separação entre a utilização e a realização/implementação do tipo de dados.

Axiomatização

A axiomatização específica que propriedades e relações têm de ser satisfeitas pelas operações básicas. Vejamos uma axiomatização para o exemplo dos números complexos.

Conjunto de axiomas, ou seja, expressões lógicas que têm de ser verdadeiras para qualquer realização/implementação do tipo complexo:

e_complexo(cria_complexo(x, y))

e_complexo(cria_complexo_zero())

e_complexo_zero(cria_complexo_zero())

complexo_igual(cria_complexo_zero(), cria_complexo(0, 0))

e_imaginario_puro(cria_complexo(0, y)), para qualquer y != 0.

complexo_parte_real(cria_complexo(x, y)) = x, para quaisquer x e y.

complexo_parte_imaginaria(cria_complexo(x, y)) = y, para quaisquer x e y.

complexo_igual(cria_complexo(x, y), cria_complexo(x, y)), para quaisquer x e y.

complexo_igual(z, cria_complexo(complexo_parte_real(z),complexo_parte_imaginaria(z))), se e_complexo(z), indefinido caso contrário.

Representação interna

O terceiro passo consiste na escolha de uma representação interna para os elementos do tipo, tendo por base outros tipos existentes ou já definidos.

Na escolha da representação interna é em geral importante ter em conta aspectos de eficiência relativos à realização das operações básicas.

No caso dos números complexos, numa implementação em Python, podemos utilizar um dicionário com duas chaves, real e imaginario.

Realização/implementação das operações básicas

O quarto e último passo consiste na realização/implementação das operações básicas definidas no primeiro passo, tendo em conta a assinatura, a axiomatização definida no segundo passo, e a representação interna escolhida no terceiro passo.

Implementação em Python dos números complexos:

def cria_complexo(x, y):
    if not(isinstance(x, (int, float)) and isinstance(y, (int, float))):
        raise ValueError('cria_complexo: argumentos invalidos, x e y tem de ser numeros')
    return {'real' : x, 'imaginario' : y}

def cria_complexo_zero():
    return cria_complexo(0, 0)

def complexo_parte_real(z):
    if not e_complexo(z):
        raise ValueError('complexo_parte_real: z tem de ser um complexo')
    return z['real']

def complexo_parte_imaginaria(z):
    if not e_complexo(z):
        raise ValueError('complexo_parte_imaginaria: z tem de ser um complexo')
    return z['imaginario']

def e_complexo(x):
    if isinstance(x, (dict)):
        if len(x) == 2 and 'real' in x and 'imaginario' in x:
            return isinstance(x['real'] , (int, float)) \
                and isinstance(x['imaginario'] , (int, float))
    return False

def e_complexo_zero(z):
    if not e_complexo(z):
        raise ValueError('complexo_parte_imaginaria: z tem de ser um complexo')
    return zero(complexo_parte_real(z)) and zero(complexo_parte_imaginaria(z))

def e_imaginario_puro(z):
    if not e_complexo(z):
        raise ValueError('complexo_parte_imaginaria: z tem de ser um complexo')
    return zero(complexo_parte_real(z)) and not zero(complexo_parte_imaginaria(z))

def complexo_igual(z, w):
    if not(e_complexo(z) and e_complexo(w)):
        raise ValueError('complexo_parte_imaginaria: z e w tem de ser complexos')
    return zero(complexo_parte_real(z) - complexo_parte_real(w)) \
           and zero(complexo_parte_imaginaria(z) - complexo_parte_imaginaria(w))

def complexo_para_string(z):
    if not e_complexo(z):
        raise ValueError('complexo_parte_imaginaria: z tem de ser um complexo')
    return str(complexo_parte_real(z)) + '+' + str(complexo_parte_imaginaria(z)) + 'i'

def zero(x):
    return abs(x) < 0.0000001

Uma vez que que a parte real e a parte imaginária são números reais em geral e que estamos a utilizar elementos do tipo float para representar esses números, é necessário definir a função zero que testa se um dado valor é zero a menos de um erro admissível (neste caso 0.0000001) para evitar problemas de precisão resultantes de operações sobre elementos do tipo float.

Barreiras de abstracção.

Um vez definido um tipo, dada a assinatura das operações básicas, podemos utilizar esse tipo da mesma forma que utilizamos outros tipos pré-definidos. Neste âmbito, qualquer manipulação de elementos do tipo deve ser realizada através das operações básicas para esse tipo.

A definição de um tipo de dados abstracto implica a definição de uma nova abstracção e define uma barreira entre os programas (ou partes do programa) que utilizam a abstracção de dados e os programas (ou partes do programa) que realizam/implementam a abstracção de dados. Esta barreira denomina-se por barreira de abstracção.

A violação destas barreiras de abstracção, como a utilização indevida das representações internas por partes do programa que não na implementação das operações básicas, corresponde a uma má prática de programação e deve ser evitada pelas seguintes razões:

1. A manipulação directa da representação interna de um tipo faz com que o programa dependa dessa representação, fazendo com que o programa deixe de funcionar e tenha de ser revisto se porventura a realização do tipo for revista e a sua representação interna actualizada, por exemplo com vista a melhorar a eficiência das operações básicas.
2. O programa passa ser menos compreensível e de difícil escrita uma vez que manipulação directa de uma estrutura interna leva a que se perca a abstracção corresponde ao uso do tipo abstracto de dados.