Abstracção de dados
Até este momento todos os programas que escrevemos manipulam instâncias de tipos já existentes, nunca considerámos novos tipos de dados. É no entanto desejável que possamos representar e utilizar diferentes tipos de informação nos nossos programas e que não existem na linguagem que estamos a utilizar para os escrever.
A abstracção em programação
Uma abstracção é uma descrição simplificada de uma entidade com foco nas propriedades mais relevantes para o contexto em que estamos, deixando de parte propriedades não relevantes e pormenores.
Por exemplo, uma pessoa pode ser caracterizada pelo nome, morada, estado civil, género, data e local de nascimento, etc. É importante notar que algumas destas propriedades são já elas abstracções como o local de nascimento. Dependo da aplicação, estas propriedades podem não ser todas relevantes e/ou podem faltar outras. Por exemplo, numa aplicação para calcular o IRS, seria importante incluir o número de identificação fiscal, mas o género é irrelevante.
A abstracção é portanto um conceito fundamental em programação. Os programas são de facto construções abstractas que podem ser executadas por um computador.
Até este momento utilizámos abstracções procedimentais, o que nos permite abstrair o como é que uma função faz daquilo que faz, e que nos permite substituir funções por outras funções que fazem o mesmo ainda que o possam fazer forma diferente ou mais eficiente.
Quando falamos de estruturas de dados e tipos de informação estamos a falar de abstracções de dados, o equivalente às abstracções procedimentais mas para dados. O objectivo é novamente separar o modo como a estrutura de dados pode ser utilizada, e o que representa, da forma como é construída e representada a partir de outros tipos de dados e de outras estruturas de dados.
A título de exemplo podemos considerar as listas em Python. Ainda que saibamos o que representam e como fazer uso das mesmas, utilizando por exemplo operações pré-definidas, não sabemos como é que as listas em Python são representadas internamente. Por outro lado, desde que as listas continuem a representar a entidade que esperamos e que o modo de utilização seja o mesmo, a implementação interna no Python poderá mudar sem que tenhamos de modificar os nossos programas. Esta é uma propriedade fundamental dos tipos de dados abstractos.
Um tipo de dados abstracto é em geral caracterizado pelo conjunto de operações que suporta e pelo conjunto de instâncias ou entidades associadas. Este conjunto de instâncias denomina-se de domínio do tipo e cada instância no conjunto denomina-se elemento do tipo.
Exemplo: vectores
Consideremos um tipo de dados abstracto para representar vectores num espaço bidimensional. Operações a suportar:
cria_vector(x, y), que dados dois número reais $x$ e $y$, retorna o vector $(x,y)$;vector_abcissa(v), que dado um vector $v$, retorna a abcissa;vector_ordenada(v), que dado um vector $v$, retorna a ordenada;e_vector(e), que dada um qualquer elemento $e$, reconhece se o mesmo é um vector ou não;vector_igual(u,v), que dados dois vectores, indica se os mesmos são ou não iguais;esreve_vector(v), que dado um vector $v$, retorna um string que o representa.
Tal como veremos mais tarde, nesta especificação temos respectivamente um construtor, dois selectores, um reconhecedor, um teste e um transformador. Estas operações são essenciais na abstracção de dados e permitem-nos separar o modo como o tipo de dados pode ser utilizado da forma como o tipo de dados é representado e operado internamente. A representação retornada pela operação escreve_vector diz-se representação externa por oposição à representação interna utilizada para representar o tipo de dados internamente.
def cria_vector(x, y):
if not (isinstance(x, (float, int)) and isinstance(y, (float, int))):
raise ValueError('cria_vector: x and y must be numbers')
return (x, y)
def vector_abcissa(v):
if not e_vector(v):
raise ValueError('vector_abcissa: v must be a vector')
return v [0]
def vector_ordenada(v):
if not e_vector(v):
raise ValueError('vector_abcissa: v must be a vector')
return v[1]
def e_vector(e):
return isinstance(e, tuple) \
and len(e) == 2 \
and isinstance(e[0], (float, int)) \
and isinstance(e[1], (float, int))
def vector_igual(u,v):
if not (e_vector(v) and e_vector(u)):
raise ValueError('vector_igual: u and v must be vectors')
return v[0] == u[0] and v[1] == u[1]
def escreve_vector(v):
if not e_vector(v):
raise ValueError('vector_abcissa: v must be a vector')
return str(v)Exercício: Implemente uma função que dados dois vectores calcula o seu produto interno. Verifique se ao modificarmos a representação interna do vector é necessário modificar a implementação do cálculo do produto interno.
Exemplo: segundo projecto de 2014/2015
import random
# = = = Constantes = = = #
NLINHAS = 4
NCOLUNAS = 4
DIRECOES = 'NSEW'
# = = = = T.A.D. coordenada = = = = #
#
# Um elemento do tipo coordenada e'
# representado como um tuplo de dois
# elementos cujo primeiro elemento
# corresponde a linha e cujo segundo
# elemento corresponde a coluna.
#
# = = = = = = = = = = = = = = = = = = #
# Construtor:
def cria_coordenada(l, c):
''' cria_coordenada : int x int -> coordenada
cria_coordenada(l, c) cria uma coordenada correspondente ao par
(l, c). '''
if l < 1 or l > NLINHAS or c < 1 or c > NCOLUNAS:
raise ValueError ('cria_coordenada: argumentos invalidos')
return (l, c)
# -- Fim: cria_coordenada -- #
# Selectores:
def coordenada_linha(c):
''' coordenada_linha : coordenada -> int
coordenada_linha(c) devolve a linha correspondente a coordenada c.'''
return c[0]
# -- Fim: coordenada_linha -- #
def coordenada_coluna(c):
''' coordenada_coluna : coordenada -> int
coordenada_coluna(c) devolve a coluna correspondente a coordenada
c.'''
return c[1]
# -- Fim: coordenada_coluna -- #
# Reconhecedor:
def e_coordenada(arg):
''' e_coordenada : universal -> logico
e_coordenada(arg) devolve True caso arg seja do tipo coordenada e
False em caso contrario.'''
return isinstance(arg, tuple) and \
len(arg) == 2 and \
isinstance(arg[0], int) and \
isinstance(arg[1], int) and \
1 <= arg[0] <= NLINHAS and \
1 <= arg[1] <= NCOLUNAS
# -- Fim: e_coordenada -- #
# Teste:
def coordenadas_iguais(c1, c2):
''' coordenadas_iguais : coordenada x coordenada -> logico
coordenadas_iguais(c1, c2) devolve True caso c1 seja igual a c2 e
False em caso contrario.'''
return c1 == c2
# -- Fim: coordenadas_iguais -- #
# = = = = T.A.D. tabuleiro = = = = #
#
# Um tabuleiro e' representado como
# uma lista com 5 elementos, os quatro
# primeiros correspondendo 'as linhas
# do tabuleiro de 2048, e o ultimo 'a
# respectiva pontuacao.
#
# = = = = = = = = = = = = = = = = = = #
# Construtor:
def cria_tabuleiro():
''' cria_tabuleiro : {} -> tabuleiro
cria_tabuleiro() devolve um novo tabuleiro vazio com score inicial
0.'''
return [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], 0]
# -- Fim: cria_tabuleiro -- #
# Selectores:
def tabuleiro_posicao(t, c):
''' tabuleiro_posicao : tabuleiro x coordenada -> int
tabuleiro_posicao(t, c) devolve o valor da posicao do tabuleiro
correspondente 'a coordenada c.'''
if not e_coordenada(c):
raise ValueError ('tabuleiro_posicao: argumentos invalidos')
return t[coordenada_linha(c) - 1][coordenada_coluna(c) - 1]
# -- Fim: tabuleiro_posicao -- #
def tabuleiro_pontuacao(t):
''' tabuleiro_pontuacao : tabuleiro -> int
tabuleiro_pontuacao(t) devolve o valor da pontuacao associado ao
tabuleiro t.'''
return t[-1]
# -- Fim: tabuleiro_pontuacao -- #
def tabuleiro_posicoes_vazias(t):
''' tabuleiro_posicoes_vazias : tabuleiro -> lista
tabuleiro_posicoes_vazias(t) devolve uma lista contendo as coordenadas
de todas as posicoes vazias do tabuleiro t.'''
lista = []
for l in range(NLINHAS):
for c in range(NCOLUNAS):
if t[l][c] == 0:
lista = lista + [cria_coordenada(l + 1, c + 1)]
return lista
# -- Fim: tabuleiro_posicoes_vazias -- #
# Modificadores:
def tabuleiro_preenche_posicao(t, c, v):
''' tabuleiro_preenche_posicao : tabuleiro x coordenada x int -> tabuleiro
tabuleiro(t, c, v) coloca o valor v na posicao correspondente 'a
coordenada c do tabuleiro t.'''
if not e_coordenada(c):
raise ValueError ('tabuleiro_preenche_posicao: argumentos invalidos')
if not isinstance(v, int):
raise ValueError ('tabuleiro_preenche_posicao: argumentos invalidos')
t[coordenada_linha(c) - 1][coordenada_coluna(c) - 1] = v
return t
# -- Fim: tabuleiro_preenche_posicao -- #
def tabuleiro_actualiza_pontuacao(t, pont):
''' tabuleiro_actualiza_pontuacao : tabuleiro x int -> tabuleiro
tabuleiro_actualiza_pontuacao(t, p) actualiza a pontuacao do tabuleiro
t em p unidades.'''
if not isinstance(pont, int) or pont < 0 or pont % 4 != 0:
raise ValueError ('tabuleiro_actualiza_pontuacao: argumentos invalidos')
t[-1] = t[-1] + pont
return t
# -- Fim: tabuleiro_actualiza_pontuacao -- #
def tabuleiro_reduz(t, direcao):
''' tabuleiro_reduz : tabuleiro x string -> tabuleiro
tabuleiro(t, d) reduz o tabuleiro t na direcao d.'''
def trata_linha(linha):
''' trata_linha : lista -> lista
trata_linha(l) reduz a linha l de acordo com as regras do 2048,
correspondente a uma jogada com direcao do inicio para o fim da
lista. A funcao e' recursiva e resolve a linha do fim para o
inicio. Actualiza (nao localmente) o score do tabuleiro.'''
if len(linha) < 2:
return linha
# Combina dois numeros iguais no final da linha
elif linha[-2] == linha[-1] != 0:
linha[-2] = 0
linha[-1] = 2 * linha[-1]
linha[:-1] = trata_linha(linha[:-1])
tabuleiro_actualiza_pontuacao(t, linha[-1])
# Elimina espaco no final da linha
elif linha[-1] == 0:
linha[1:] = trata_linha(linha[:-1])
linha[0] = 0
# Elimina espaco na penultima casa da linha
elif linha[-2] == 0:
linha[1:-1] = linha[:-2]
linha[1:] = trata_linha(linha[1:])
linha[0] = 0
# Ultima posicao fixa, trata resto da linha
else:
linha[:-1] = trata_linha(linha[:-1])
return linha
# -- Fim: trata_linha -- #
def inverte(t):
''' inverte : tabuleiro -> tabuleiro
inverte(t) inverte a ordem dos elementos em cada linha de t.'''
for l in range(NLINHAS):
for c in range(NCOLUNAS//2):
t[l][c], t[l][NCOLUNAS - c - 1] = t[l][NCOLUNAS - c - 1], t[l][c]
return t
# -- Fim: inverte -- #
def transpoe(t):
''' transpoe : tabuleiro -> tabuleiro
transpoe(t) transpoe as linhas/colunas de t.'''
for l in range(NLINHAS):
for c in range(l):
t[l][c], t[c][l] = t[c][l], t[l][c]
return t
# -- Fim: transpoe -- #
def reduz_horizontal(t):
''' reduz : tabuleiro -> tabuleiro
reduz(t) efecuta a reducao das linhas do tabuleiro t
correspondente a uma jogada na direcao "E".'''
for i in range(NLINHAS):
trata_linha(t[i])
return t
# -- Fim: reduz_horizontal -- #
# Corpo principal da funcao reduz
TRANSFORMA = {'N' : lambda t : inverte(transpoe(t)),
'S' : transpoe,
'E' : lambda t : t,
'W' : inverte}
REVERTE = {'N' : lambda t : transpoe(inverte(t)),
'S' : transpoe,
'E' : lambda t : t,
'W' : inverte}
if direcao not in DIRECOES:
raise ValueError ('tabuleiro_reduz: argumentos invalidos')
REVERTE[direcao](reduz_horizontal(TRANSFORMA[direcao](t)))
return t
# -- Fim: reduz -- #
# Reconhecedores:
def e_tabuleiro(arg):
''' e_tabuleiro : universal -> logico
e_tabuleiro(arg) devolve True se o seu argumento for do tipo
tabuleiro e False em caso contrario.'''
if not isinstance(arg, list) or len(arg) != NLINHAS + 1:
return False
if not isinstance(arg[-1], int) or arg[-1] < 0 or arg[-1] % 4 != 0:
return False
for i in range(len(arg) - 1):
if not isinstance(arg[i], list) or len(arg[i]) != NCOLUNAS:
return False
else:
for el in arg[i]:
if not isinstance(el, int):
return False
return True
# -- Fim: e_tabuleiro -- #
def tabuleiro_terminado(t):
''' tabuleiro_terminado : tabuleiro -> logico
tabuleiro_terminado(t) devolve True caso o tabuleiro t corresponda
a um jogo terminado, e False em caso contrario.'''
for l in range(NLINHAS):
for c in range(NCOLUNAS):
if t[l][c] == 0:
return False
elif l > 0 and t[l][c] == t[l-1][c]:
return False
elif c > 0 and t[l][c] == t[l][c-1]:
return False
return True
# -- Fim: tabuleiro_terminado -- #
# Teste:
def tabuleiros_iguais(t1, t2):
''' tabuleiros_iguais : tabuleiro x tabuleiro -> logico
tabuleiros_iguais(t1, t2) devolve True caso t1 seja igual a t2 e
False em caso contrario.'''
return t1 == t2
# -- Fim: tabuleiros_iguais -- #
# Transformador de saida:
def escreve_tabuleiro(t):
''' escreve_tabuleiro : tabuleiro -> {}
escreve_tabuleiro(t) escreve para o ecra o tabuleiro de 2048 t.'''
if not e_tabuleiro(t):
raise ValueError ('escreve_tabuleiro: argumentos invalidos')
for l in range(NLINHAS):
for c in range(NCOLUNAS):
print('[', tabuleiro_posicao(t, cria_coordenada(l + 1, c + 1)), ']', end=' ')
print()
print('Pontuacao:', tabuleiro_pontuacao(t))
# Funcoes auxiliares:
def copia_tabuleiro(t):
''' copia_tabuleiro : tabuleiro -> tabuleiro
copia_tabuleiro(t) devolve um novo tabuleiro com a mesma configuracao
que o tabuleiro t.'''
if not e_tabuleiro(t):
raise ValueError ('copia_tabuleiro: argumentos invalidos')
tnovo = cria_tabuleiro()
for l in range(NLINHAS):
for c in range(NCOLUNAS):
coord = cria_coordenada(l + 1, c + 1)
tabuleiro_preenche_posicao(tnovo, coord, tabuleiro_posicao(t, coord))
tabuleiro_actualiza_pontuacao(tnovo, tabuleiro_pontuacao(t))
return tnovo
# -- Fim: copia_tabuleiro -- #
def preenche_posicao_aleatoria(t):
''' preenche_posicao_aleatoria : tabuleiro -> tabuleiro
preenche_posicao_aleatoria(t) modifica o tabuleiro t, preenchendo
uma posicao aleatoria com o valor 2, com probabilidade 0.8, ou 4,
com probabilidade 0.2.'''
valor = 2 if random.random() < 0.8 else 4
coord = random.choice(tabuleiro_posicoes_vazias(t))
tabuleiro_preenche_posicao(t, coord, valor)
return t
# -- Fim: preenche_posicao_aleatoria -- #
def pede_jogada():
''' pede_jogada : {} -> string
pede_jogada() pede ao utilizador para introduzir uma jogada.'''
jogada = input('Introduza uma jogada (N, S, E, W): ')
while jogada == '' or jogada not in DIRECOES:
jogada = input('Jogada invalida.\nIntroduza uma jogada (N, S, E, W): ')
return jogada
# -- Fim: pede_jogada -- #
def joga_2048():
''' joga_2048 : {} -> {}
joga_2048() permite jogar um jogo de 2048.'''
t = cria_tabuleiro()
preenche_posicao_aleatoria(t)
preenche_posicao_aleatoria(t)
while not tabuleiro_terminado(t):
escreve_tabuleiro(t)
jogada = pede_jogada()
if copia_tabuleiro(t) != tabuleiro_reduz(t, jogada):
preenche_posicao_aleatoria(t)
print('Jogo terminado.')
if __name__ == "__main__":
joga_2048()Exercício: Identifique onde é que são violadas as barreiras de abstracção neste programa.