A teoria dos tipos abstractos de informação diz que o conceito fundamental para a abstracção de dados é a definição de uma interface entre a implementação dos dados e a sua utilização. Essa interface é constituida por funções que se podem classificar em categorias: construtores, selectores, reconhecedores e testes. Estas funções são definidas em termos dos objectos mais primitivos que implementam o tipo de dados que se quer definir.
Os construtores são as funções que criam um objecto composto a partir dos seus elementos mais simples. Por exemplo, a função racional é um construtor para o tipo racional.
Os selectores são as funções que recebem um objecto composto e devolvem as suas partes. As funções numerador e denominador são exemplos de selectores.
Os reconhecedores são as funções que reconhecem certos objectos especiais do tipo de dados que se está a definir. A função zerop é um reconhecedor para o tipo número do Lisp.
Finalmente, os testes são funções que comparam objectos do tipo que se está a definir. A função =racional é um exemplo de uma função desta categoria. Como se pode verificar pela função =racional, por vezes, os testes são implementados usando os próprios selectores.
Para que abstracção de dados seja correctamente realizada, é fundamental definir o conjunto de construtores, selectores, reconhecedores e testes. Todos os programas que pretenderem utilizar aquele tipo de dados são obrigados a usar apenas aquelas funções. Isso permite que se possa alterar a implementação do tipo de dados sem afectar os programas que o utilizam.
A implementação de estruturas de dados complexas só é correctamente realizada quando se segue esta metodologia com extremo rigor.
Exercício 38
Defina o teste >racional.
Quando um tipo abstracto de informação tem de interagir com um utilizador, quer para lhe pedir uma descrição de um elemento do tipo, quer para lhe apresentar uma descrição de um elemento do tipo, usa os denominados transformadores de entrada/saída. A função escreve-racional é um exemplo de um transformador de saída para o tipo racional. Ela limita-se a a apresentar uma representação compreensível de um número racional. O transformador de entrada realiza a operação inversa, i.e., constroi um elemento do tipo abstracto a partir de uma representação fornecida.