abstraccion

Home Page

Title Page

Contents

La Abstracci´n de Datos: T´cnica
o
e
Fundamental en Programaci´n
o
Profesor: Juan Francisco Diaz
jdiaz@eisc.univalle.edu.co

Asistente de Docencia: Gerardo M. Sarria M.
Page 1 of 100

gsarria@eisc.univalle.edu.co

April 10, 2002
Go Back

Full Screen

Close

Quit

Home Page

Title Page

Concepto General
Contents

La t´cnica deabstracci´n de datos se usa para localizar todas las
e
o
partes de un programa que son dependientes de la representaci´n.
o

Page 2 of 100

La abstracci´n de datos divide un tipo de dato en dos partes: una
o
interfaz que dice qu´ representa el tipo de dato, cu´les son las operae
a
ciones de los datos y cu´les propiedades deben tener dichas operaciones;
a
y una implementaci´n que proveeuna representaci´n espec´
o
o
ıfica de los
datos y un c´digo para las operaciones que hacen uso de esa representaci´n.
o
o

Go Back

Un tipo de dato que es abstracto se denomina Tipo Abstracto de
Dato (TAD).

Full Screen

Close

Quit

El resto del programa fuera del tipo de dato, llamado el cliente del
tipo de dato, manipula el nuevo dato s´lo mediante las operaciones
oespecificadas en la interfaz.

Home Page

Title Page

Concepto General (cont.)
Contents

Page 3 of 100

Toda la representaci´n de los datos debe estar en el c´digo de la
o
o
implementaci´n. Se usar´ la notaci´n v para “la representaci´n del dato
o
a
o
o
v”.
Ejemplo 1:
El tipo de dato entero no negativo
La interfaz consiste de cuatro entidades: una constante zero y tresprocedimientos, iszero?, succ, y pred.
El comportamiento de los procedimientos se especifica as´
ı:
zero = 0

Go Back

#t
#f
(succ n ) = n + 1
(pred n + 1 ) = n
(iszero? n ) =

Full Screen

Close

Quit

n=0
n=0
(n ≥ 0)
(n ≥ 0)

Home Page

Title Page

Contents

Page 4 of 100

Go Back

Full Screen

Close

Quit

Concepto General (cont.)
La especificaci´n anterior no dicec´mo se representar´n los enteros
o
o
a
no negativos, simplemente asegura que zero tendr´ que estar limitado a
a
la representaci´n de 0, que el procedimiento succ, dada la representaci´n
o
o
de n, debe retornar la representaci´n del entero n + 1, etc.
o
De all´ (la especificaci´n), se pueden escribir programas que manipulan
ı
o
los enteros no negativos, asegurando que ser´ncorrectos, no importa cu´l
a
a
sea la representaci´n que se use.
o
Ejemplo 2:
(define plus
(lambda (x y)
(if (iszero? x)
y
(succ (plus (pred x) y)))))
satisfar´ (plus x y ) = x + y , no importa la implementaci´n de
a
o
enteros no negativos que se use.

Home Page

Title Page

Concepto General (cont.)
Contents

Tres posibles representaciones para los enteros no negativos pueden
ser:1. Representaci´n Unaria: Donde un entero no negativo n es represeno
tado por una lista de n s´
ımbolos ’#t’.
0 = ()
n + 1 = (cons #t n )
Page 5 of 100

En esta representaci´n, se satisface la especificaci´n escribiendo
o
o
Go Back

Full Screen

Close

Quit

(define
(define
(define
(define

zero ’())
iszero? null?)
succ (lambda (rep_n) (cons #t rep_n)))
pred cdr)

HomePage

Concepto General (cont.)
Title Page

Contents

2. Representaci´n de N´meros de Scheme: Se usa la representaci´n ino
u
o
terna de n´meros de Scheme. n = n
u
(define
(define
(define
(define

Page 6 of 100

Go Back

3. Representaci´n Bignum: Los n´meros son representados en base N ,
o
u
para alg´n entero grande N . Dicha representaci´n es una lista que
u
o
consistede n´meros entre 0 y N − 1.
u
n =

Full Screen

zero 0)
iszero? zero?)
succ (lambda (rep_n) (+ rep_n 1)))
pred (lambda (rep_n) (- rep_n 1)))

()
n=0
(cons r q ) n = qN + r, 0 ≤ r < N

Luego si N = 16, entonces
Close

Quit

33 = (1 2)
258 = (2 0 1)

((1 × 160 ) + (2 × 161 ))
((2 × 160 ) + (0 × 161 ) + (1 × 162 )).

Home Page

Interfaz: define-datatype
Title Page...