Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Tipos Lineales
Tipos Lineales 2
Tipos lineales I
En los ordenadores la información se almacena normalmente de manera secuencial: secuencias de bits, secuencias de bloques, secuencias de registros, ...En muchos lenguajes (Prolog, Haskell, ...) se incorpora un tipo lista predefinido para facilitar la organización secuencial de la información.Las listas se corresponden con las sucesiones finitas de valoresde un mismo tipo.Un tipo lista obedece a alguno de los patrones siguientes:Lista = Nil | Elt × Lista ó ListaNv = Elt | Elt × ListaNvLos tipos lineales admiten una generación similar a las listas y se diferencian en las operaciones adicionales.
Tipos Lineales 3
Tipos lineales II
Cada tipo lineal utiliza:Un criterio para la formación de las secuencias que siempre se puede reducir al de las listas.Un criterio para acceder a los componentes de una secuencia: primero, último, actual, cualquiera.Un criterio para eliminar elementos: primero, último, actual, cualquiera.
Según sean estos criterios tendremos distintos tipos lineales:Pilas (acceso y eliminación del último elemento)Colas (acceso y eliminación del primer elemento)Anillos (acceso y eliminación del elemento actual)Cadenas (acceso y eliminación de cualquier elemento)
Tipos Lineales 4
Pilas
(fmod PILA [X :: TRIV] issorts Pila[X] PilaNv[X] .subsort PilaNv[X] < Pila[X] .
op pilaV : -> Pila[X] [ctor] .op apilar : Elt.X Pila[X] -> PilaNv[X] [ctor] .
op cima : PilaNv[X] -> Elt.X .op desapilar : PilaNv[X] -> Pila[X] ....
endfm)
pilaV apilar(E1,pilaV) apilar(E2,apilar(E1,pilaV)) ...
Tipos Lineales 5
Colas
(fmod COLA [X :: TRIV] issorts Cola[X] ColaNv[X] .subsort ColaNv[X] < Cola[X] .
op colaV : -> Cola[X] [ctor] .op enCola : Elt.X Cola[X] -> ColaNv[X] [ctor] .
op primero : ColaNv[X] -> Elt.X .op avanzar : ColaNv[X] -> Cola[X] ....
endfm)
colaV enCola(E1,colaV) enCola(E2,enCola(E1,colaV))...
Tipos Lineales 6
Anillos
(fmod Anillo [X :: TRIV] is sorts Anillo[X] AnilloNv[X] .subsort AnilloNv[X] < Anillo[X] .
op anilloV : -> Anillo[X] [ctor] .op enganchar : Elt.X Anillo[X] -> AnilloNv[X] [ctor] .
op actual : AnilloNv[X] -> Elt.X .op avanzar retroceder : Anillo[X] -> Anillo[X] .op desenganchar : Anillo[X] -> Anillo[X] .
...endfm)
anilloV enganchar(E1,anilloV) enganchar(E2,enganchar(E1,anilloV))...
Tipos Lineales 7
Listas Genéricas I
(fmod LISTA [X :: TRIV] isincluding MACHINE-INT .sorts Lista[X] ListaNv[X] .subsort ListaNv[X] < Lista[X] .
op nil : -> Lista[X] [ctor] .op _:_ : Elt.X Lista[X] -> ListaNv[X] [ctor] .
op cabeza : ListaNv[X] -> Elt.X .op cola : ListaNv[X] -> Lista[X] .op _++_ : Lista[X] Lista[X] -> Lista[X] .op longitud : Lista[X] -> MachineInt .op tomar_de_ : MachineInt Lista[X] -> Lista[X] . *** lo que se puedaop quitar_de_ : MachineInt Lista[X] -> Lista[X] . *** lo que se pueda
Tipos Lineales 8
Listas Genéricas II
op pos : Elt.X Lista[X] -> MachineInt . *** 0 si no estaop posinm : Elt.X MachineInt Lista[X] -> MachineInt . op inversa : Lista[X] -> Lista[X] .
vars E E1 : Elt.X . var N : MachineInt .vars L L1 : Lista[X] .eq cabeza(E:L) = E .eq cola(E:L) = L .eq nil ++ L = L .eq (E:L) ++ L1 = E : (L ++ L1) .eq longitud(nil) = 0 .eq longitud(E:L) = 1 + longitud(L) .
Tipos Lineales 9
Listas Genéricas III
ceq tomar N de L = nil if N <= 0 or L == nil .ceq tomar N de (E:L) = E:(tomar (N-1) de L) if N > 0 .
ceq quitar N de L = L if N <= 0 or L == nil .ceq quitar N de (E:L) = quitar (N-1) de L if N > 0 .
eq pos(E,L) = posinm(E,1,L) .eq posinm(E,N,nil) = 0 .ceq posinm(E,N,E1:L) = N if E == E1 .ceq posinm(E,N,E1:L) = posinm(E,N+1,L) if E =/= E1 .
eq inversa(nil) = nil .eq inversa(E:L) = inversa(L) ++ (E:nil) .
endfm)
Tipos Lineales 10
Ejercicios
Definir la operación para invertir listas con ayuda de una función inmersora que utilice un acumulador con una inversa parcial.Demostrar aplicando inducción estructural que
∀ L : Lista[X] • (L ++ nil = L)Demostrar aplicando inducción estructural que
∀ L L1 L2 : Lista[X] • ((L ++ L1) ++ L2 = L ++ (L1 ++ L2))Demostrar aplicando inducción estructural que∀ L L’ : Lista[X] • (inversa(L ++ L’) = inversa(L’) ++ inversa(L))
Tipos Lineales 11
Listas de Enteros
(view IntM from TRIV to MACHINE-INT issort Elt to MachineInt .
endv)
(fmod LISTA-INT is protecting LISTA[IntM] .
endfm)
Tipos Lineales 12
Listas de Listas de Enteros
(view LIntM from TRIV to LISTA-INT issort Elt to Lista[IntM] .
endv)
(fmod LISTA-LINT is protecting LISTA[LIntM] .
endfm)
Tipos Lineales 13
Listas de números primos I
(fmod LISTA-PRIMOS is protecting LISTA[IntM] .
op _a_ : MachineInt MachineInt -> Lista[IntM] .op elimMult : MachineInt Lista[IntM] -> Lista[IntM] .op criba : Lista[IntM] -> Lista[IntM] .op primos-hasta : MachineInt -> Lista[IntM] .
vars M N : MachineInt .var L : Lista[IntM] .
Tipos Lineales 14
Listas de números primos II
eq M a N = if M > N then nil else M : ((M + 1) a N ) fi .
eq elimMult(N, nil) = nil .eq elimMult(N, M : L) =
if M % N == 0 then elimMult(N, L) else M : elimMult(N, L) fi .
eq criba(nil) = nil .eq criba(M : L) = M : criba(elimMult(M, L)) .ceq primos-hasta(N) = nil if N < 1 .ceq primos-hasta(N) = 1 : criba(2 a N) if N >= 1 .
endfm)
Tipos Lineales 15
Listas Ordenadas I
(view Ord from TRIV to TOSET issort Elt to Elt .
endv)
(fmod LISTAORD [X :: TOSET] is protecting LISTA[Ord][X] .sorts ListaOrd[X] ListaOrdNv[X] .subsorts ListaOrdNv[X] < ListaNv[Ord][X]
ListaOrd[X] < Lista[Ord][X] .
op ordenada?_ : Lista[Ord][X] -> Bool .
Tipos Lineales 16
Listas Ordenadas II
op insertar : Elt.X ListaOrd[X] -> ListaOrdNv[X] .op ord-ins : Lista[Ord][X] -> ListaOrd[X] .
op mezclar : ListaOrd[X] ListaOrd[X] -> ListaOrd[X] .op ord-mez : Lista[Ord][X] -> ListaOrd[X] .
ops minimo maximo : ListaNv[Ord][X] -> Elt.X .op ord-min : Lista[Ord][X] -> ListaOrd[X] .
op menores-ig mayores : Lista[Ord][X] -> ListaOrd[X] .op ord-rap : Lista[Ord][X] -> ListaOrd[X] .
...endfm)
Tipos Lineales 17
Colas de prioridad
(fmod ColaP [X :: TOSET] issorts ColaPNv[X] ColaP[X] .subsort ColaPNv[X] < ColaP[X] .op colaPV : -> ColaP[X] [ctor] .op insertar : Elt.X ColaP[X] -> ColaPNv[X] [ctor] .op min : ColaPNv[X] -> Elt.X .op avanzar-min : ColaPNv[X] -> ColaP[X] .
...endfm)
Tipos Lineales 18
Cadenas I
(fmod CADENA [X :: TOSET] is protecting MACHINE-INT .sorts Cadena[X] CadenaNv[X] Elt?[X] .subsorts Elt.X < CadenaNv[X] < Cadena[X] .subsort Elt.X < Elt[X] .
op * : -> Cadena[X] [ctor] .op __ : Cadena[X] Cadena[X] -> Cadena[X] [ctor] .vars C1 C2 C3 : Cadena[X] . Var C : CadenaNv[X] .mb C1 C : CadenaNv[X] .mb C C1 : CadenaNv[X] .eq (C1 C2) C3 = C1 (C2 C3) .eq * C1 = C1 .eq C1 * = C1 .
Tipos Lineales 19
Cadenas II
op long : Cadena[X] -> MachineInt .op caracter : MachineInt Cadena[X] -> Elt?[X] .op pos-car : Elt.X Cadena[X] -> MachineInt .op subcadena : MachineInt MachineInt Cadena[X] -> Cadena[X] .op pos-subc : Cadena[X] Cadena[X] -> MachineInt .
op _<_ : Cadena[X] Cadena[X] -> Bool .ops pref? suf? subc? : Cadena[X] Cadena[X] -> Bool .
...
endfm)
Tipos Lineales 20
Implementación I
Para la implementación segura de tipos en un lenguaje de programación es necesario que dicho lenguaje disponga de algún mecanismo de abstracción que permita la ocultación y proteja las estructuras ocultas:Módulos de biblioteca (Modula-2 y C)
Interfaz + ImplementaciónClases (Java)
Control de visibilidad para cada componente
Tipos Lineales 21
Implementación II
En lenguajes declarativos, que incorporan el tipo lista como tipo predefinido, los tipos lineales se representan sobre listas implementando sólo las operaciones propias de cada tipo lineal.
En lenguajes imperativos (Pascal, Modula2, C, C++), que no permiten la definición directa de estructuras recursivas, hay que utilizar una combinación de registro y puntero a registro para representar los pares (Elt,Lista).
Tipos Lineales 22
Implementaciones Imperativas I
MODULA-2TYPE Lista = POINTER TO Nodo1;
Nodo1 = RECORD ult :Telem; sig :Lista END;
Ctypedef struct Nodo1* Lista;struct Nodo1 {Telem ult; Lista sig};
JAVAclass Lista {
private Object ult;private Lista sig;...
}
Tipos Lineales 23
Implementaciones Imperativas II
En principio, un tipo lineal se puede representar como un puntero a un registro (el último elemento de la estructura).
Por cuestiones de eficiencia algunos tipos lineales se definen como registros que contienen varios punteros: La implementación de colas se puede mejorar utilizando un puntero adicional al primer elemento de la cola.
La implementación de anillo se puede mejorar utilizando un puntero adicional en cada registro al elemento anterior y conectando el último elemento con el primero y viceversa, para facilitar los giros.
Tipos Lineales 24
Implementaciones Imperativas III
Las operaciones se pueden implementar como funciones o como procedimientos que transforman un argumento.Las operaciones de consulta se suelen implementar como funciones.Las operaciones de transformación (constructoras y operaciones de eliminación de elementos) se implementan como procedimientos que modifican un argumento.